Proglinear4 - Metodo 2 fases continuacao proglinear 3

Prévia do material em texto

Capítulo 2. Programação Linear 
 
 Apontamentos de Investigação Operacional 29 Alberto Mulenga 
 
 
 
 
 
 
Sujeito à 








0,,,,,,
1200064
1600448
2154321
2154321
2154321
aaxxxxx
aaxxxxx
aaxxxxx
 
Maximizar Za = -12x1 - 10x2 -4x3 + 1x4 + 1x5 +0a1+ 0a2 – 28 
 
Tabela inicial simpelx 
Base x1 x2 x3 x4 x5 a1 a2 bi 
 a1 
 a2 
 8 4 4 -1 0 1 0 
 4 6 0 0 -1 0 1 
16  (2) 
12  (3) 
 W -16 -12 -5 0 0 0 0 0 
 Za -12 -10 -4 1 1 0 0 -28 
1
a
 Fase (iteração 1) 
Base x1 x2 x3 x4 x5 a1 a2 bi 
 x1 
 a2 
 1 1/2 1/2 -1/8 0 1/8 0 
 0 4 -2 1/2 -1 -1/2 1 
2  l1’=1/8*l1 (4) 
4  l2’=l2-4l1’ (1) 
 W 0 -4 3 -2 0 2 0 32  l3’=l3+16l1’ 
 Za 0 -4 2 -1/2 1 3/2 0 -4  l4’=l4+12l1’ 
1
a
 Fase (iteração 2) 
base x1 x2 x3 x4 x5 a1 a2 bi 
 x1 
 x2 
 1 0 3/4 -3/16 1/8 3/16 -1/8 
 0 1 -1/2 1/8 -1/4 -1/8 1/4 
3/2 l1’=l1 – 1/2l2’ 
 1  l2’= ¼*12 
 W 0 0 1 -3/2 -1 3/2 1 36  l3’=l3+4l2’ 
 Za 0 0 0 0 0 1 1 0  l4’=l4+4l2’ 
 
Como na última linha o valor da função objectivo artificial é igual a zero, a fase 1 termina 
e a solução encontrada é solução básica inicial para a fase 2. 
 
Tabela inicial simplex (2
a
 fase) 
 
base x1 x2 x3 x4 x5 bi 
 x1 
 x2 
 1 0 3/4 -3/16 1/8 
 0 1 -1/2 1/8 -1/4 
3/2  l1’=l1 – 1/2l2’ (2) 
 1  l2’= ¼*12 (neg) 
 W 0 0 1 -3/2 -1 36  l3’=l3+4l2’ 
 
Lembre-se que o objectivo é de minimizar, portanto os inicadores da linha pivô devem 
ser todos negativos. 
 
 2
a
 fase (iteração 1) 
base x1 x2 x3 x4 x5 bi 
 X3 
 x2 
 4/3 0 1 -1/4 1/6 
 2/3 1 0 0 -1/6 
2  l1’=4/3l1 
2  l2’=12+1/2l1’ 
 W -4/3 0 0 -5/4 -7/6 34  l3’=l3 - l1’ 
Solução x1= 0; x2 = 2; x3 = 2; x4 = 0; x5 = 0; Wmin = 34 
 
Capítulo 2. Programação Linear 
 
 Apontamentos de Investigação Operacional 30 Alberto Mulenga 
 
 
 
 
 
 
Exemplo 2.12. Resolver o problema pelo método de duas fases: 
Minimizar W = 4x1 + x2 
Sujeito à 











0,
32
634
33
21
21
21
21
xx
xx
xx
xx
 
Resolução 
Minimizar W = 4x1 + x2 + 0(x3+x4+0x5) + 0(a1+a2+a3) 
Sujeito à 











0,,,,,,,
300002
6000034
300003
32154321
32154321
32154321
32154321
aaaxxxxx
aaaxxxxx
aaaxxxxx
aaaxxxxx
 
 
Tabela inicial simplex (1
a
 fase) 
base x1 x2 x3 x4 x5 a1 a2 a3 bi 
 a1 
 a2 
 a3 
 3 1 -1 0 0 1 0 0 
 4 3 0 -1 0 0 1 0 
 1 2 0 0 -1 0 0 1 
 3  (1) 
 6  (3/2) 
 3  (3) 
 W -4 -1 0 0 0 0 0 0 0 
 Za -8 -6 1 1 1 0 0 0 -12 
1
a
 Fase (Iteração 1) 
base x1 x2 x3 x4 x5 a1 a2 a3 bi 
 x1 
 a2 
 a3 
 1 1/3 -1/3 0 0 1/3 0 0 
 0 5/3 4/3 -1 0 -4/3 1 0 
 0 5/3 1/3 0 -1 -1/3 0 1 
 1  l1’=1/3l1 (3) 
 2  l2’=l2-4l1’ (6/5) 
 2  l3’=l3-l1’ (6/5) 
 W 0 1/3 -4/3 0 0 4/3 0 0 4  l4’=l4+4l1’ 
 Za 0 -10/3 -5/3 1 1 8/3 0 0 -4  l5’=l5+8l1’ 
1
a
 Fase (Iteração 2) 
base x1 x2 x3 x4 x5 a1 a2 a3 bi 
 x1 
 x2 
 a3 
 1 0 -3/5 1/5 0 3/5 -1/5 0 
 0 1 4/5 -3/5 0 -4/5 3/5 0 
 0 0 -1 1 -1 1 -1 1 
 3/5  l1’=l1-1/3l2’ (3) 
 6/5  l2’=3/5l2 (negativo) 
 0  l3’=l3-5/3l2’ (0) 
 W 0 0 -24/15 1/5 0 24/15 -1/5 0 18/5  l4’=l4-1/3l2’ 
 Za 0 0 1 -1 1 0 2 0 0  l5’=l5+10/3l2’ 
1
a
 Fase (Iteração 3) 
base x1 x2 x3 x4 x5 a1 a2 a3 bi 
 x1 
 x2 
 x4 
 1 0 -2/5 0 1/5 -2/5 0 1/5 
 0 1 1/5 0 -3/5 -1/5 0 3/5 
 0 0 -1 1 -1 1 -1 1 
 3/5  l1’=l1-1/5l3’ 
 6/5  l2’=l2+3/5l3’ 
 0  l3’=l3 
 W 0 0 -7/5 0 1/5 7/5 0 -1/5 18/5  l4’=l4-1/5l3’ 
 Za 0 0 0 0 0 1 1 1 0  l5’=l5+l3’ 
 
Capítulo 2. Programação Linear 
 
 Apontamentos de Investigação Operacional 31 Alberto Mulenga 
 
 
 
 
 
 
Como na última linha o valor da função objectivo artificial é igual a zero, a fase 1 termina 
e a solução encontrada é solução básica inicial para a fase 2. 
 
Tabela inicial simplex (2
a
 fase) 
base x1 x2 x3 x4 x5 bi 
 x1 
 x2 
 x4 
 1 0 -2/5 0 1/5 
 0 1 1/5 0 -3/5 
 0 0 -1 1 -1 
 3/5  (3) 
 6/5  (neg) 
 0  (neg) 
 W 0 0 -7/5 0 1/5 18/5  
2
a
 fase (iteração 1) 
base x1 x2 x3 x4 x5 bi 
 x5 
 x2 
 x4 
 5 0 -2 0 1 
 3 1 1 0 0 
 5 0 -3 1 0 
 3  l1’=5*l1 
 3  l2’=l2+3/5l1’ 
 3  l3’=l3+l1’ 
 W -1 0 -1 0 0 3  l4’=l4-1/5l1’ 
 
Solução x1= 0; x2 = 3; x3 = 0; x4 = 3; x5 = 3; Wmin = 3 
 
2.3.4 Maximização e minimização com restrições do tipo  ; ;  
 
Em todos os problemas anteriores foram consideradas restrições com um único tipo de 
sinal de desigualdade. Nesta secção vamos considerar o caso geral dos problemas de PL 
com o conjunto das restrições que apresentam os sinais de  ;  e  desde que não haja 
números negativos no segundo membro das equações das restrições. 
 
Exemplo: 
Maximizar Z = 2x1 + x2 
Sujeito à 








0,
2
10
21
21
21
xx
xx
xx
 
 
Introduzindo as variáveis de folga (+xi) de excesso (-xi) e apresentando a tabela inicial 
simplex teremos: 
 
Base x1 x2 x3 x4 bi 
 x3 
 x4 
 1 1 1 0 
-1 1 0 -1 
10 
 2 
 Z -2 -1 0 0 0 
 
Da tabela inicial, x1 e x2 não são básicas e x4 < 0, logo o conjunto {x1 = 0; x2 = 0; x3 = 10; 
x4 = -2; z = 0}, não é solução válida, poís viola a condição de não negatividade. 
 
Para resolver este tipo de problemas, introduz-se uma outra modificação no método 
simplex e usa-se o método de grande M.