PO Simplex Revisão

Prévia do material em texto

Extra
E-1
PESQUISA OPERACIONAL I 
– REVISÃO
max min f = x1 + x2
s/a x1 + x2 >= 2
x1 - x2 <= 1
x1 <= 2
x1, x2 >= 0
Revisão 
Resolução Gráfica
Extra
E-2
A
D
C
B
Solução
Maximizar f= +∞
Solução Ilimitada
Minimizar
Solução Múltipla
B: x1 = 0, x2 = 2 f = 2
C: x1 = 1.5, x2 = 0.5 f = 2
x1
x2
Forma Padrão
x1 + x2 - x3 = 2
x1 - x2 + x4 = 1
x1 + x5 = 2
f= +∞
x1 x2 x3 x4 x5 x6
0 0 0 0 0 1 f
1 1 -1 0 0 1 2
1 -1 0 1 0 0 1
1 0 0 0 1 0 2
-1 -1 1 0 0 0 f-2
x6 1 1 -1 0 0 1 2
x4 1 -1 0 1 0 0 1
x5 1 0 0 0 1 0 2
0 0 0 0 0 1 f
x2 1 1 -1 0 0 1 2
x4 2 0 -1 1 0 1 3
x5 1 0 0 0 1 0 2
Revisão
SIMPLEX Fase 1
Extra
E-3
Como f = 0 
o sistema é factível
min f = x6
s/a x1 + x2 >= 2
x1 – x2 <= 1
x1 <= 2
x1, x2 >= 0
Arrumar a BASE
x1 + x2 - x3 + x6 = 2
x1 - x2 + x4 = 1
x1 + x5 = 2
x1 x2 x3 x4 x5
1 1 0 0 0 f
1 1 -1 0 0 2
2 0 -1 1 0 3
1 0 0 0 1 2
0 0 1 0 0 f-2
x2 1 1 -1 0 0 2
x4 2 0 -1 1 0 3
x5 1 0 0 0 1 2
Revisão
SIMPLEX Fase 2
Extra
E-4
max min f = x1 + x2
s/a x1 + x2 >= 2
x1 – x2 <= 1
x1 <= 2
x1, x2 >= 0
Solução
Maximizar f= +∞
Solução Ilimitada 
x3 é candidata a entrar na base, mas não há 
bloqueio para seu crescimento
Minimizar
Solução Múltipla
B: x1 = 0, x2 = 2 f = 2
C: x1 = 1.5, x2 = 1.5 f = 2 (se x1 entrar na BASE)
c1 = 0 
mas x1 não está
na BASE
Arrumar a BASE
x1 x2 x3 x4 x5 x6
0 0 0 0 0 1 f
1 -2 1 -1 0 1 3
1 1 0 0 1 0 4
Tarefa
Tarefa Simplex
T-5
min f = x1 + x2 - x3
s/a x1 – 2*x2 + x3 >= 3
x1 + x2 <= 4
x1, x2, x3 >= 0
Exercício
Arrumar a BASE
FASE 1
x1 x2 x3 x4 x5
0 0 0 0 1 f
1 1 -1 0 1 2
0 1 0 1 0 3
-1 -1 1 0 0 f-2
x5 1 1 -1 0 1 2
x4 0 1 0 1 0 3
0 0 0 0 0 f
x1 1 1 -1 0 1 2
x4 0 1 0 1 0 3
x1 x2 x3 x4
-1 1 0 0 f
1 1 -1 0 2
0 1 0 1 3
0 2 -1 0 f+2
x1 1 1 -1 0 2
x4 0 1 0 1 3
-2 0 1 0 f-2
x2 1 1 -1 0 2
x4 -1 0 1 1 1
-1 0 0 -1 f-3
x2 0 1 0 1 3
x3 -1 0 1 1 1
max f = - x1 + x2
s/a x1 + x2 >= 2
x2 <= 3
x1, x2 >= 0
Fase 1
Fase 2
x1 x2 x3 x4 x5
0 0 0 0 1 f
1 1 -1 0 1 2
0 1 0 1 0 3
-1 -1 1 0 0 f-2
x5 1 1 -1 0 1 2
x4 0 1 0 1 0 3
0 0 0 0 0 f
x2 1 1 -1 0 1 2
x4 -1 0 1 1 -1 1
x1 x2 x3 x4
-1 1 0 0 f
1 1 -1 0 2
-1 0 1 1 1
-2 0 1 0 f-2
x2 1 1 -1 0 2
x4 -1 0 1 1 1
-1 0 0 -1 f-3
x2 0 1 0 1 3
x3 -1 0 1 1 1
max f = - x1 + x2
s/a x1 + x2 >= 2
x2 <= 3
x1, x2 >= 0
Fase 1
Fase 2
x1 x2 x3 x4 x5
0 0 0 0 1 f
-1 1 -1 0 1 2
0 1 0 1 0 3
1 -1 1 0 0 f-2
x5 -1 1 -1 0 1 2
x4 0 1 0 1 0 3
0 0 0 0 0 f
x2 -1 1 -1 0 1 2
x4 1 0 1 1 -1 1
x1 x2 x3 x4
-1 1 0 0 f
-1 1 -1 0 2
1 0 1 1 1
0 0 1 0 f-2
x2 -1 1 -1 0 2
x4 1 0 1 1 1
-1 0 0 -1 f-3
x2 0 1 0 1 3
x3 1 0 1 1 1
max f = - x1 + x2
s/a - x1 + x2 >= 2
x2 <= 3
x1, x2 >= 0
Fase 1
Fase 2
x1 x2 x3 x4 x5
0 0 0 0 1 f
-1 1 -1 0 1 2
1 1 0 1 0 3
1 -1 1 0 0 f-2
x5 -1 1 -1 0 1 2
x4 1 1 0 1 0 3
0 0 0 0 0 f
x2 -1 1 -1 0 1 2
x4 2 0 1 1 -1 1
x1 x2 x3 x4
-1 1 0 0 f
-1 1 -1 0 2
2 0 1 1 1
0 0 1 0 f-2
x2 -1 1 -1 0 2
x4 2 0 1 1 1
-2 0 0 -1 f-3
x2 1 1 0 1 3
x3 2 0 1 1 1
max f = - x1 + x2
s/a - x1 + x2 >= 2
x1 + x2 <= 3
x1, x2 >= 0
Fase 1
Fase 2