Método Simplex para Programação Linear

Prévia do material em texto

1
1. Montar um dicionário inicial
2. Olhando a equação do z, escolha uma variável não-
básica xin cujo aumento melhoraria a solução corrente 
do dicionário (coeficiente negativo se for minimização, 
positivo se for maximização). Se não houver tal 
variável, a solução corrente é ótima.
3. Calcule o máximo valor para xin que não torne uma 
variável básica negativa. Se esse valor for infinito, o 
PL é ilimitado. Caso contrário, escolha uma variável 
xout que bloqueou o crescimento de xin.
4. A variável xin entra na base, xout sai da base. Atualize o 
dicionário colocando xin isolado do lado esquerdo, xout
vai pro lado direito. Volte para o Passo 2.
Método Simplex
2
� Isso só é óbvio quando a matriz A já contém uma base 
viável que seja uma matriz-identidade.
� Por exemplo, quando todas as restrições são do tipo ≤
e o vetor b for não-negativo, as variáveis de folga 
definem uma base-identidade viável.
� Em geral, não existe maneira simples de montar o 
primeiro dicionário.
� Apenas saber se existe alguma solução para um PL 
pode ser difícil!
Como montar o dicionário inicial?
3
Pesquisa Operacional I
Inicialização do método simplex
Prof.: Eduardo Uchoa
uchoa@producao.uff.br
http://www.logis.uff.br/~uchoa/POI
4
O método do M Grande
x12
x
2
3
Exemplo: Minimizar x1 – 2 x2
sujeito a x1 + x2 ≥ 2
- x1 + x2 ≥ 1
x2 ≤ 3
x1, x2 ≥ 0
5
Colocando o PL no formato padrão
Exemplo: Minimizar x1 – 2 x2
sujeito a x1 + x2 ≥ 2
- x1 + x2 ≥ 1
x2 ≤ 3
x1, x2 ≥ 0
Min x1 – 2 x2
s . a x1 + x2 - x3 = 2
- x1 + x2 - x4 = 1
x2 + x5 = 3
x1, x2, x3 , x4 , x5 ≥ 0
As variáveis de folga/excesso não servem para obter uma
base identidade viável (se as duas primeiras
igualdades forem multiplicadas por -1, o vetor b fica com
valores negativos).
6
O método do M Grande
Adicionar duas variáveis artificiais ao PL para que exista uma base viável que
seja uma identidade!
Note que as variáveis de folga/excesso são “variáveis reais” do PL (não mudam o 
problema) e possuem coeficiente zero na F.O.
Já as novas variáveis artificiais mudam o problema e, portanto, devem receber o 
coeficienteM (um número arbitrariamente grande, tendendo ao infinito) se o 
problema for de minimização e –M se for de maximização.
Exemplo: Minimizar x1 – 2 x2
sujeito a x1 + x2 ≥ 2
- x1 + x2 ≥ 1
x2 ≤ 3
x1, x2 ≥ 0
Min x1 – 2 x2 + M x6 + M x7
s . a x1 + x2 - x3 + x6 = 2
- x1 + x2 - x4 + x7 = 1
x2 + x5 = 3
x1, x2, x3 , x4 , x5, x6 , x7 ≥ 0
7
O método do M Grande
Notar que:
1. As variáveis x5, x6 e x7 definem uma base identidade viável para o PL 
modificado => É fácil montar o dicionário inicial para esse PL.
2. Mas o valor da F.O. da solução associada é muito ruim, pior do que o 
custo de qualquer solução que não use essas variáveis (ou seja, em
que elas estejam zeradas).
Exemplo: Minimizar x1 – 2 x2
sujeito a x1 + x2 ≥ 2
- x1 + x2 ≥ 1
x2 ≤ 3
x1, x2 ≥ 0
Min x1 – 2 x2 + M x6 + M x7
s . a x1 + x2 - x3 + x6 = 2
- x1 + x2 - x4 + x7 = 1
x2 + x5 = 3
x1, x2, x3 , x4 , x5, x6 , x7 ≥ 0
8
O método do M Grande
Logo:
• Se o PL original tiver solução viável => a solução ótima do PL 
modificado vai ser a solução ótima do PL original (as variáveis artificiais
serão não-básicas e terão valor zero).
• Se o PL original for inviável => a solução ótima do PL modificado vai ter
alguma variável artificial não-zerada.
Exemplo: Minimizar x1 – 2 x2
sujeito a x1 + x2 ≥ 2
- x1 + x2 ≥ 1
x2 ≤ 3
x1, x2 ≥ 0
Min x1 – 2 x2 + M x6 + M x7
s . a x1 + x2 - x3 + x6 = 2
- x1 + x2 - x4 + x7 = 1
x2 + x5 = 3
x1, x2, x3 , x4 , x5, x6 , x7 ≥ 0
9
( )
6 1 2 3
7 1 2 4
5 2
1 2 3 4
1º dicionário
2
1
3
3 2 2
x x x x
x x x x
x x
z M x M x Mx Mx
= − − +
= + − +
= −
= + − + + +
x12
x
2
3
O método do M Grande
A solução associada (0,0) viola duas restrições
do problema original
10
( )
6 1 2 3
7 1 2 4
5 2
1 2 3 4
1º dicionário
2
1
3
3 2 2
x x x x
x x x x
x x
z M x M x Mx Mx
= − − +
= + − +
= −
= + − + + +
O método do M Grande
11
( )
6 1 2 3
7 1 2 4
5 2
1 2 3 4
1º dicionário
2
1
3
3 2 2
x x x x
x x x x
x x
z M x M x Mx Mx
= − − +
= + − +
= −
= + − + + +
{ }2
2
min 2,1,3
1
x
x
=
=
O método do M Grande
12
( )
6 1 2 3
7 1 2 4
5 2
1 2 3 4
1º dicionário
2
1
3
3 2 2
x x x x
x x x x
x x
z M x M x Mx Mx
= − − +
= + − +
= −
= + − + + +
{ }2
2
min 2,1,3
1
x
x
=
=
O método do M Grande
13
( )
6 1 2 3
7 1 2 4
5 2
1 2 3 4
2 7
1º dicionário
2
1
3
3 2 2
 entra na base e sai da base
x x x x
x x x x
x x
z M x M x Mx Mx
x x
= − − +
= + − +
= −
= + − + + +
{ }2
2
min 2,1,3
1
x
x
=
=
O método do M Grande
14
( ) ( ) ( )
6 1 3 4 7
2 1 4 7
5 1 4 7
1 3 4 7
2º dicionário
1 2
1
2
2 1 2 2 2 2
x x x x x
x x x x
x x x x
z M M x Mx M x M x
= − + − +
= + + −
= − − +
= − + − + + − + + +
O método do M Grande
15
( ) ( ) ( )
6 1 3 4
2 1 4
5 1 4
7
7
7
71 3 4
2º dicionário
1 2
1
2
2 1 2 2 22
x x x x
x x x
x x x
z M M x M
x
x
x
x M M xx
+
−
+
= − + −
= + +
+
= − −
= − + − ++ − + +
Quando uma variável artificial sai da base, ela nunca mais volta 
(devido a seu custo infinito) => x7 pode ser retirada do dicionário
O método do M Grande
16
( ) ( )
6 1 3 4
2 1 4
5 1 4
1 3 4
2º dicionário
1 2
1
2
2 1 2 2
x x x x
x x x
x x x
z M M x Mx M x
= − + −
= + +
= − −
= − + − + + − +
A nova solução viola apenas uma restrição
O método do M Grande
x1
2
x
2
3
17
( ) ( )
6 1 3 4
2 1 4
5 1 4
1 3 4
2º dicionário
1 2
1
2
2 1 2 2
x x x x
x x x
x x x
z M M x Mx M x
= − + −
= + +
= − −
= − + − + + − +
O método do M Grande
18
1
1
1
min ,2
2
1
2
x
x
 
=  
 
=( ) ( )
6 1 3 4
2 1 4
5 1 4
1 3 4
2º dicionário
1 2
1
2
2 1 2 2
x x x x
x x x
x x x
z M M x Mx M x
= − + −
= + +
= − −
= − + − + + − +
O método do M Grande
19
( ) ( )
6 1 3 4
2 1 4
5 1 4
1 3 4
2º dicionário
1 2
1
2
2 1 2 2
x x x x
x x x
x x x
z M M x Mx M x
= − + −
= + +
= − −
= − + − + + − +
1
1
1
min ,2
2
1
2
x
x
 
=  
 
=
O método do M Grande
20
( ) ( )
6 1 3 4
2 1 4
5 1 4
1 3 4
1 6
2º dicionário
1 2
1
2
2 1 2 2
 entra na base e sai da base
x x x x
x x x
x x x
z M M x Mx M x
x x
= − + −
= + +
= − −
= − + − + + − +
1
1
1
min ,2
2
1
2
x
x
 
=  
 
=
O método do M Grande
21
( )
4
1 3 4 6
2 3 4 6
5 3 4 6
3 4
1
6
3º dicionário
1 2 1 2 1 2 1 2
3 2 1 2 1 2 1 2
3 2 1 2 1
 entra na base e sai da base
2 1 2
1 25 1 3
2 2 2 2
x x x x
x x x x
x x x x
M
z x x x
x x
= + − −
= + + −
= − − +
+
= − − − +
O método do M Grande
22
( )
1 3 4
2 3 4
5 3 4
3
4
6
4
1
6
6
6
3º dicionário
1 2 1 2 1 2
3 2 1 2 1 2
3 2 1 2 1
 entra na base e sai d
1 2
a base
1 2
1 2
1 2
2
2
5 1 3
2 2 2
x x x
x x x
x x x
z x
x
x
x
xx
x x
M
−
−
+
+
+
= + −
= + +
= − −
= − − −
A variável artificialx6 pode ser eliminada
O método do M Grande
23
O método do M Grande
1
4
3 4
2 3 4
5 3 4
3
1
4
3º dicionário
1 2 1 2 1 2
3 2 1 2 1 2
3 2 1 2 1 2
5 1 3
2 2
 entra na base e sai da 
2
base
x x x
x x x
x x x
z x x
x x
= + −
= + +
= − −
= − − −
Todas as variáveis artificiais foram eliminadas. Logo, essa 
solução é viável para o problema original! Agora basta 
prosseguir com o método até a solução ótima.
x1
2
x
2
3
24
O método do M Grande
1
4
3 4
2 3 4
5 3 4
3
1
4
3º dicionário
1 2 1 2 1 2
3 2 1 2 1 2
3 2 1 2 1 2
5 1 3
2 2
 entra na base e sai da 
2
base
x x x
x x x
x x x
z x x
x x
= + −
= + +
= − −
= − − −
25
O método do M Grande
4
4
1 2 3 2
min ,
1 2 1 2
1
x
x
 
=  
 
=
1
4
3 4
2 3 4
5 3 4
3
1
4
3º dicionário
1 2 1 2 1 2
3 2 1 2 1 2
3 2 1 2 1 2
5 1 3
2 2
 entra na base e sai da 
2
base
x x x
x x x
x x x
z x x
x x
= + −
= + +
= − −
= − − −
26
O método do M Grande
4
4
1 2 3 2
min ,
1 2 1 2
1
x
x
 
=  
 
=
1
4
3 4
2 3 4
5 3 4
3
1
4
3º dicionário
1 2 1 2 1 2
3 2 1 2 1 2
3 2 1 2 1 2
5 1 3
2 2
 entra na base e sai da 
2
base
x x x
x x x
x x x
z x x
x x
= + −
= + +
= − −
= − − −
27
O método do M Grande
1 3 4
2 3 4
5 3 4
3 4
4 1
3º dicionário
1 2 1 2 1 2
3 2 1 2 1 2
3 2 1 2 1 2
5 1 3
2 2 2
 entra na base e sai da base
x x x
x x x
x x x
z x x
x x
= + −
= + +
= − −
= − − −
4
4
1 2 3 2
min ,
1 2 1 2
1
x
x
 
=  
 
=
28
O método do M Grande
4 1 3
2 1 3
5 3
1
1
1 3
4 entra na base e sai 
4º dicionár
da ba
io
1 2
2
1
4 3
s
2
e
x x x
x x x
x x x
z
x
x x
x
= − +
= − +
= + −
= − + −
x12
x
2
3
29
O método do M Grande
4 1 3
2 1 3
5 3
1
1
1 3
4 entra na base e sai 
4º dicionár
da ba
io
1 2
2
1
4 3
s
2
e
x x x
x x x
x x x
z
x
x x
x
= − +
= − +
= + −
= − + −
30
O método do M Grande
3
1
min
1
x
 
=  
 
4 1 3
2 1 3
5 3
1
1
1 3
4 entra na base e sai 
4º dicionár
da ba
io
1 2
2
1
4 3
s
2
e
x x x
x x x
x x x
z
x
x x
x
= − +
= − +
= + −
= − + −
31
O método do M Grande
3
1
min
1
x
 
=  
 
4 1 3
2 1 3
5 3
1
1
1 3
4 entra na base e sai 
4º dicionár
da ba
io
1 2
2
1
4 3
s
2
e
x x x
x x x
x x x
z
x
x x
x
= − +
= − +
= + −
= − + −
32
O método do M Grande
3
1
min
1
x
 
=  
 
4 1 3
2 1 3
5 1 3
1 3
3 5
4º dicionário
1 2
2
1
4 3 2
 entra na base e sai da base
x x x
x x x
x x x
z x x
x x
= − +
= − +
= + −
= − + −
33
O método do M Grande
4
4 1 5
2 5
3 1 5
5
1
1
5º dicionário
2
3
1
 entra na base e sai da bas
6
e
2
x x x
x x
x x x
z
x
x
x
x
= − −
= −
= + −
= − + +
34
O método do M Grande
4
4 1 5
2 5
3 1 5
5
1
1
5º dicionário
2
3
1
 entra na base e sai da bas
6
e
2
x x x
x x
x x x
z
x
x
x
x
= − −
= −
= + −
= − + +
Não existem variáveis que, 
quando aumentadas, resultem em 
redução do valor da função 
objetivo.
Logo, a solução encontrada neste 
dicionário é ótima.
35
O método do M Grande
4
4 1 5
2 5
3 1 5
5
1
1
5º dicionário
2
3
1
 entra na base e sai da bas
6
e
2
x x x
x x
x x x
z
x
x
x
x
= − −
= −
= + −
= − + +
Não existem variáveis que, 
quando aumentadas, resultem em 
redução do valor da função 
objetivo.
A solução associada a este 
dicionário é ótima e dada por:
x1 = 0 x2 = 3
Esta solução resulta em:
z = -6
x12
x
2
3
36
O método do M Grande
x1
5 1
0
1
5
x
2
5
1 0
Min 2 x1 + 4 x2
S.a 1,5 x1 + 4,0 x2 ≥ 24
3,0 x1 + 1,5 x2 ≥ 21
1,0 x1 + 1,0 x2 ≤ 8
x1, x2 ≥ 0
Min 2 x1 + 4 x2 +M x6 +M x7
1,5x1+ 4,0x2 - 1,0x3 + 1,0x6 = 24
3,0x1+ 1,5x2 - 1,0x4 + 1,0x7 = 21
1,0x1+ 1,0x2 + 1,0x5 = 8
x1, x2, x3 , x4 , x5 , x6 , x7 ≥ 0
37
O método do M Grande
( ) ( )
6 1 2 3
7 1 2 4
5 1 2
1 2 3 4
2 6
1º dicionário
324 4
2
321 3
2
8
4 9 8 11
45
2 2
 entra na base e sai da base e é eliminada do problema
x x x x
x x x x
x x x
M M
z M x x Mx Mx
x x
= − − +
= − − +
= − −
− −
= + + + +
{ }2
2
min 6,14,8
6
x
x
=
=
38
O método do M Grande
( ) ( ) ( )
2 1 3
7 1 3 4
5 1 3
1 3 4
1 5
2º dicionário
3 16
8 4
39 312
16 8
5 12
8 4
8 39 8 3
24 12
16 8
 entra na base e sai da base
x x x
x x x x
x x x
M M
z M x x Mx
x x
= − +
= − − +
= − −
− −
= + + + +
1
1
6 12 2
min , ,
3 8 39 16 5 8
16 5
x
x
 
=  
 
=
39
O método do M Grande
( ) ( ) ( )
2 3 5
7 3 4 5
1 3 5
1
3 4
5
5
3º dicionário
24 2 3
5 5 5
21 3 39
5 5 10
16 2 8
5 5 5
128
 entra na base e sai da ba
21 3
se
2 24 8 39
5 40 10
x x x
x x x x
x x x
M M
x
M
x Mx
x
z x
= + +
= + + +
= − −
+ + − +
= + + +
Coeficientes positivos, solução ótima.
40
O método do M Grande
( ) ( ) ( )
2 3 5
7 3 4 5
5 3 5
1
3 4
5
5
3º dicionário
24 2 3
5 5 5
21 3 39
5 5 10
16 2 8
5 5 5
128
 entra na base e sai da ba
21 3
se
2 24 8 39
5 40 10
x x x
x x x x
x x x
M M
x
M
x Mx
x
z x
= + +
= + + +
= − −
+ + − +
= + + +
Como há variável artificial com valor positivo na 
solução ótima, o problema original é inviável.
41
O método do M Grande
É possível executar o método de duas formas:
• Tratar M algebricamente (como estamos fazendo)
- Preferível, sempre funciona
•Atribuir um valor numérico suficientemente grande para M
-Em alguns raros casos pode ser difícil achar um valor adequado.
Valor baixo demais: o método termina com variável artificial 
positiva apesar de haver solução viável.
Valor alto demais: estouro numérico no computador
42
O método das duas fases
Uma alternativa para inicializar o método simplex
Na Fase 1, ignora-se a FO original. Na nova FO, as variáveis artificiais
tem coeficiente 1 e as demais 0.
Se a solução ótima desse PL modificado tiver z > 0 => PL original 
inviável.
Caso contrário, todas as variáveis artificiais foram eliminadas => 
a base inicial do PL original está pronta
Na Fase 2, restaura-se a FO original (de acordo com essa base) e 
resolve-se o PL
43
min Z - x1 + 2 x2
s. a x1 + x2 - x3 + x6 = 2
- x1 + x2 - x4 + x7 = 1
x2 + x5 = 3
x1, x2 , x3 , x4 , x5 , x6 , x7 ≥ 0
Exemplo: minimizar x1 – 2 x2
sujeito a x1 + x2 ≥ 2
- x1 + x2 ≥ 1
x2 ≤ 3
x1, x2 ≥ 0
O método das duas fases
FASE 1: min x6 + x7
s. a x1 + x2 - x3 + x6 = 2
- x1 + x2 - x4 + x7 = 1
x2 + x5 = 3
x1, x2 , x3 , x4 , x5 , x6 , x7 ≥ 0
44
O método das duas fases
Fase 1
6 1 2 3
7 1 2 4
5 2
2 3
2 7
4
 entra na base e sai da ba
1º dicionário
2
3
3
se
1
2
x x x x
x x x x
x x
z
x
x
x
x x
= − − +
= + − +
= −
= − + +45
O método das duas fases
Fase 1
6 1 2 3
7 1 2 4
5 2
2 3
2 7
4
 entra na base e sai da ba
1º dicionário
2
3
3
se
1
2
x x x x
x x x x
x x
z
x
x
x
x x
= − − +
= + − +
= −
= − + +
46
O método das duas fases
Fase 1
6 1 2 3
7 1 2 4
5 2
2 3
2 7
4
 entra na base e sai da ba
1º dicionário
2
3
3
se
1
2
x x x x
x x x x
x x
z
x
x
x
x x
= − − +
= + − +
= −
= − + +
{ }2
2
min 2,1,3
1
x
x
=
=
47
O método das duas fases
Fase 1
6 1 2 3
7 1 2 4
5 2
2 3
2 7
4
 entra na base e sai da ba
1º dicionário
2
3
3
se
1
2
x x x x
x x x x
x x
z
x
x
x
x x
= − − +
= + − +
= −
= − + +
{ }2
2
min 2,1,3
1
x
x
=
=
48
O método das duas fases
Fase 1
6 1 2 3
7 1 2 4
5 2
2 3 4
2 7
1º dicionário
2
1
3
3 2
 entra na base e sai da base
x x x x
x x x x
x x
z x x x
x x
= − − +
= + − +
= −
= − + +
{ }2
2
min 2,1,3
1
x
x
=
=
49
O método das duas fases
Fase 1
6 1 3 4
2 1 4
5 1 4
1 3 4
2 7
2º dicionário
1 2
1
2
1 2
 entrou na base e saiu da base
e foi eliminada
x x x x
x x x
x x x
z x x x
x x
= − + −
= + +
= − −
= − + −
50
O método das duas fases
Fase 1
6 1 3 4
2 1 4
5 1 4
1 3 4
2º dicionário
1 2
1
2
1 2
x x x x
x x x
x x x
z x x x
= − + −
= + +
= − −
= − + −
51
O método das duas fases
Fase 1
6 1 3 4
2 1 4
5 1 4
1 3 4
2º dicionário
1 2
1
2
1 2
x x x x
x x x
x x x
z x x x
= − + −
= + +
= − −
= − + −
1
1
1
min ,2
2
1 2
x
x
 
=  
 
=
52
O método das duas fases
Fase 1
6 1 3 4
2 1 4
5 1 4
1 3 4
2º dicionário
1 2
1
2
1 2
x x x x
x x x
x x x
z x x x
= − + −
= + +
= − −
= − + −
1
1
1
min ,2
2
1 2
x
x
 
=  
 
=
53
O método das duas fases
Fase 1
6 1 3 4
2 1 4
5 1 4
1 3 4
1 6
2º dicionário
1 2
1
2
1 2
 entra na base e sai da base e
é eliminada
x x x x
x x x
x x x
z x x x
x x
= − + −
= + +
= − −
= − + −
1
1
1
min ,2
2
1 2
x
x
 
=  
 
=
54
O método das duas fases
Fase 1
1 3 4
2 3 4
5 3 4
3º dicionário
1 1 1
2 2 2
3 1 1
2 2 2
3 1 1
2 2 2
0
x x x
x x x
x x x
z
= + −
= + +
= − −
=
Fim da fase 1
Foi encontrada uma solução básica viável:
x1 = ½, x2 = 3/2, x5 = 3/2 z = 0
x1
2
x
2
3
55
Restaurando a FO original
Fase 2
1 3 4
2 3 4
5 3 4
1
1 2
4
Montando o 1º dicionário
1 2 1 2 1 2
3 2 1 2 1 2
3 2
 entra na base e s
1 2 1
ai da 
2
2
base
x x x
x x x
x
x
x x
x x
z x=
= + −
= + +
= − −
−
56
O método das duas fases
Fase 2
1 3 4
2 3 4
5 3 4
1
1 2
4
Montando o 1º dicionário
1 2 1 2 1 2
3 2 1 2 1 2
3 2
 entra na base e s
1 2 1
ai da 
2
2
base
x x x
x x x
x
x
x x
x x
z x=
= + −
= + +
= − −
−
A FO deve ser escrita em função das 
variáveis não-básicas x3 e x4
57
O método das duas fases
Fase 2
1
4
3 4
2 3 4
5 3 4
3
1
4
1º dicionário
1 2 1 2 1 2
3 2 1 2 1 2
3 2 1 2 1 2
5 1 3
2 2
 entra na base e sai da 
2
base
x x x
x x x
x x x
z x x
x x
= + −
= + +
= − −
= − − −
58
O método das duas fases
Fase 2
1
4
3 4
2 3 4
5 3 4
3
1
4
1º dicionário
1 2 1 2 1 2
3 2 1 2 1 2
3 2 1 2 1 2
5 1 3
2 2
 entra na base e sai da 
2
base
x x x
x x x
x x x
z x x
x x
= + −
= + +
= − −
= − − −
59
O método das duas fases
Fase 2
1
4
3 4
2 3 4
5 3 4
3
1
4
1º dicionário
1 2 1 2 1 2
3 2 1 2 1 2
3 2 1 2 1 2
5 1 3
2 2
 entra na base e sai da 
2
base
x x x
x x x
x x x
z x x
x x
= + −
= + +
= − −
= − − −
4
4
1 2 3 2
min ,
1 2 1 2
1
x
x
 
=  
 
=
60
O método das duas fases
Fase 2
1
4
3 4
2 3 4
5 3 4
3
1
4
1º dicionário
1 2 1 2 1 2
3 2 1 2 1 2
3 2 1 2 1 2
5 1 3
2 2
 entra na base e sai da 
2
base
x x x
x x x
x x x
z x x
x x
= + −
= + +
= − −
= − − −
4
4
1 2 3 2
min ,
1 2 1 2
1
x
x
 
=  
 
=
61
O método das duas fases
Fase 2
1 3 4
2 3 4
5 3 4
3 4
4 1
1º dicionário
1 2 1 2 1 2
3 2 1 2 1 2
3 2 1 2 1 2
5 1 3
2 2 2
 entra na base e sai da base
x x x
x x x
x x x
z x x
x x
= + −
= + +
= − −
= − − −
4
4
1 2 3 2
min ,
1 2 1 2
1
x
x
 
=  
 
=
62
O método das duas fases
Fase 2
4 1 3
2 1 3
5 3
1
1
1 3
4 entra na base e sai 
2º dicionár
da ba
io
1 2
2
1
4 3
s
2
e
x x x
x x x
x x x
z
x
x x
x
= − +
= − +
= + −
= − + −
63
O método das duas fases
Fase 2
4 1 3
2 1 3
5 3
1
1
1 3
4 entra na base e sai 
2º dicionár
da ba
io
1 2
2
1
4 3
s
2
e
x x x
x x x
x x x
z
x
x x
x
= − +
= − +
= + −
= − + −
64
O método das duas fases
Fase 2
4 1 3
2 1 3
5 3
1
1
1 3
4 entra na base e sai 
2º dicionár
da ba
io
1 2
2
1
4 3
s
2
e
x x x
x x x
x x x
z
x
x x
x
= − +
= − +
= + −
= − + −
3 1x =
65
O método das duas fases
Fase 2
4 1 3
2 1 3
5 3
1
1
1 3
4 entra na base e sai 
2º dicionár
da ba
io
1 2
2
1
4 3
s
2
e
x x x
x x x
x x x
z
x
x x
x
= − +
= − +
= + −
= − + −
3 1x =
66
O método das duas fases
Fase 2
4 1 3
2 1 3
5 1 3
1 3
3 5
2º dicionário
1 2
2
1
4 3 2
 entra na base e sai da base
x x x
x x x
x x x
z x x
x x
= − +
= − +
= + −
= − + −
3 1x =
67
O método das duas fases
Fase 2
4
4 1 5
2 5
3 1 5
5
1
1
3º dicionário
2
3
1
 entra na base e sai da bas
6
e
2
x x x
x x
x x x
z
x
x
x
x
= − −
= −
= + −
= − + +
68
O método das duas fases
Fase 2
4
4 1 5
2 5
3 1 5
5
1
1
3º dicionário
2
3
1
 entra na base e sai da bas
6
e
2
x x x
x x
x x x
z
x
x
x
x
= − −
= −
= + −
= − + +
69
O método das duas fases
Fase 2
4
4 1 5
2 5
3 1 5
5
1
1
3º dicionário
2
3
1
 entra na base e sai da bas
6
e
2
x x x
x x
x x x
z
x
x
x
x
= − −
= −
= + −
= − + +
Fim da fase 2.
A solução associada ao 3º
dicionário é ótima e é dada 
por:
x1 = 0, x2 = 3
Z = -6
x1
2
x
2
3
Coeficientes positivos, solução ótima.
70
OBSERVAÇÃO
Este material refere-se às notas de aula do curso 
TEP117 (Pesquisa Operacional I) da Universidade 
Federal Fluminense (UFF) e foi criado a partir das 
notas do Prof. Rodrigo A. Scarpel do ITA 
(www.mec.ita.br/~rodrigo) e não pode ser 
reproduzido sem autorização prévia de ambos os 
autores. Quando autorizado, seu uso é exclusivo 
para atividades de ensino e pesquisa em 
instituições sem fins lucrativos.