Embed Size (px)
Citation preview
1
1. Montar um dicionário inicial2. 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 [email protected]
http://www.logis.uff.br/~uchoa/POI
4
O método do M Grande
x12
x 23
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 umabase identidade viável (se as duas primeirasigualdades forem multiplicadas por -1, o vetor b fica comvalores negativos).
6
O método do M GrandeAdicionar duas variáveis artificiais ao PL para que exista uma base viável queseja 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 coeficiente M (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, emque 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 artificiaisserã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 teralguma 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 23
O método do M Grande
A solução associada (0,0) viola duas restriçõesdo 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) => x
7pode 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
x12
x2
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
1min , 2
2
12
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
1min , 2
2
12
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
1min , 2
2
12
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
Mz 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 artificial x6 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.
x12
x2
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 2min ,
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 2min ,
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 2min ,
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
x2
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
1min
1x
=
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
1min
1x
=
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
1min
1x
=
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
x2
3
36
O método do M Grande
x15 1
015
x2
51 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 1145
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 Mz 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 324 12
16 8
entra na base e sai da base
x x x
x x x x
x x x
M Mz M x x Mx
x x
= − +
= − − +
= − −
− −= + + + +
1
1
6 12 2min , ,
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
Mx 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
Mx 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 artificiaistem 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 fasesFase 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 fasesFase 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 fasesFase 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 fasesFase 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 fasesFase 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 fasesFase 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 fasesFase 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 fasesFase 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
1min ,2
2
1 2
x
x
=
=
52
O método das duas fasesFase 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
1min ,2
2
1 2
x
x
=
=
53
O método das duas fasesFase 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
1min ,2
2
1 2
x
x
=
=
54
O método das duas fasesFase 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
x12
x2
3
55
Restaurando a FO originalFase 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 fasesFase 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 fasesFase 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 fasesFase 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 fasesFase 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 2min ,
1 2 1 2
1
x
x
=
=
60
O método das duas fasesFase 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 2min ,
1 2 1 2
1
x
x
=
=
61
O método das duas fasesFase 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 2min ,
1 2 1 2
1
x
x
=
=
62
O método das duas fasesFase 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 fasesFase 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 fasesFase 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 fasesFase 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 fasesFase 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 fasesFase 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 fasesFase 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 fasesFase 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
x12
x2
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.
