Simplex Duas Fases 1
Quando usamos o método simplex duas fases?
a) Para restrições do tipo maior ou igual, a variável de folga tem coeficiente negativo.
b) Restrições de igualdade não possuem variáveis de folga.
c) Se uma destas duas restrições (, =) fizer parte do pl, não há solução básica viável inicial
conveniente para utilizar o Simplex e, portanto, o método de duas fases é usado.
Para que possamos utilizar o método simplex, geramos, então, uma solução básica artificial através
da adição de variáveis artificiais e cada uma das restrições dos tipos “” e “=”.
Fase I
Na fase I, tentamos encontrar um solução básica viável inicial para o pl original, para isto a variável
artificial deve ser “conduzida” a zero. Para fazer isso, uma função objetivo artificial (W) é criada,
que é a soma de todas as variáveis artificiais. A nova função objetivo é minimizada sujeito às
restrições do problema original usando o método simplex. No final da Fase I, surgem três casos:
i) Se o valor mínimo de W* 0 e alguma variável artificial aparecer na base em nível positivo, o pl
original não tem solução viável e o procedimento de otimização termina. O pl é inviável.
ii) Se o valor mínimo de W* = 0 e nenhuma variável artificial aparecer na base, então uma solução
básica viável para o pl original foi obtida. O pl é viável
iii) Se o valor mínimo de W* = 0 e uma ou mais variáveis artificiais aparecerem na base em nível
zero, então uma solução viável para o pl original existe e deve ser gerada. Devemos cuidar
dessa variável artificial e garantir que ela nunca fique positiva durante os cálculos da Fase II. O
pl é viável
Quando a Fase I resulta em ii) ou iii), seguimos para a Fase II para encontrar uma solução ótima
para o pl original.
Fase II
A solução básica viável encontrada no final da Fase I agora é usada como uma solução inicial para o
pl original. Significa que o quadro/tableau final encontrado na Fase I se torna o quadro inicial para
a Fase II na qual a função objetivo artificial é substituída pela função objetivo original. O método
simplex é então aplicado para chegar à solução ótima do pl.
EXEMPLO A
min Z = 4X1 + 3X2 + 9X3
sa 2X1 + 4X2 + 6X3 ≤ 15
1X1 + 1X2 + 1X3 = 9/2
6X1 + 1X2 + 6X3 ≥ 12
X1, X2, X3 ≥ 0
Primeiro passamos o pl para a forma padrão, adicionando variáveis de excesso, de folga, e
artificiais, onde necessário.
Como a restrição 1 é do tipo '≤' é necessária a variável de folga F.
Como a restrição 2 é do tipo '=' é necessária a variável de artificial A1.
Como a restrição 3 é do tipo '≥' é necessária a variável de excesso E e a variável artificial A2.
Simplex Duas Fases 2
min Z = 4 X1 + 3 X2 + 9 X3 max Z = -4 X1 -3 X2 -9 X3 + 0 F + 0 E + 0 A1 + 0 A2
sa sa
2 X1 + 4 X2 + 6 X3 ≤ 15 2 X1 + 4 X2 + 6 X3 + 1 F = 15
1 X1 + 1 X2 + 1 X3 = 9/2 1 X1 + 1 X2 + 1 X3 + 1 A1 = 9/2
6 X1 + 1 X2 + 6 X3 ≥ 12 6 X1 + 1 X2 + 6 X3 -1 E + 1 A2 = 12
X1, X2, X3 ≥ 0 X1, X2, X3, F, E, A1, A2 ≥ 0
min W = 1 A1 + 1 A2 max -W = -1 A1 - 1 A2 max -W +1 A1 + 1 A2 = 0
sa sa sa
2 X1 + 4 X2 + 6 X3 + F = 15 2 X1 + 4 X2 + 6 X3 + F = 15 2 X1 + 4 X2 + 6 X3 + F = 15
1 X1 + 1 X2 + 1 X3 + 1 A1 =9/2 1 X1 + 1 X2 + 1 X3 + 1 A1 = 9/2 1 X1 + 1 X2 + 1 X3 + 1 A1 = 9/2
6 X1 + 1 X2 + 6 X3 – E + A2 = 12 6 X1 + 1 X2 + 6 X3 – E + A2 = 12 6 X1 + 1 X2 + 6 X3 – E + A2 = 12
X1, X2, X3, F, E, A1, A2 ≥ 0 X1, X2, X3, F, E, A1, A2 ≥ 0 X1, X2, X3, F, E, A1, A2 ≥ 0
Fase I
Base X1 X2 X3 F E A1 A2 b
-W 1 1
F 2 4 6 1 15
A1 1 1 1 1 9/2
A2 6 1 6 -1 1 12
Base X1 X2 X3 F E A1 A2 b
-W -7 -2 -7 0 1 -33/2 min
F 2 4 6 1 15 15/2
A1 1 1 1 1 9/2 9/2
A2 6 1 6 -1 1 12 12/6
Base X1 X2 X3 F E A1 A2 b
-W - 5/6 0 0 -1/6 7/6 -5/2 min
X2 11/3 4 1 1/3 -1/3 11 3
A1 5/6 0 1/6 1 -1/6 5/2 3
X1 1 1/6 1 -1/6 1/6 2 12
Base X1 X2 X3 F E A1 A2 b
-W 10/11 5/22 -1/11 12/11 0 min
X2 1 12/11 3/11 1/11 -1/11 3 33
A1 -10/11 - 5/22 1/11 1 -1/11 0 0
X1 1 9/11 - 1/22 - 2/11 2/11 1 ---
Base X1 X2 X3 F E A1 A2 b
-W 1 1 0
X2 1 2 1/2 -1 0 3
E -10 -5/2 1 11 -1 0
X1 1 -1 - 1/2 2 0 3/2
Solução ótima Fim da Fase I.
Simplex Duas Fases 3
W*=A1=A2 = 0 Existe solução viável, assim podemos passar para a Fase II para resolver o pl
original.
Fase II
Base X1 X2 X3 F E b Base X1 X2 X3 F E b
-Z 4 3 9 0 -Z 7 1/2 0 -15
X2 1 2 1/2 3 X2 1 2 1/2 3
E -10 -5/2 1 0 E -10 -5/2 1 0
X1 1 -1 -1/2 3/2 X1 1 -1 -1/2 3/2
Solução ótima Fim da Fase II
X1 = 3/2, X2 = 3, X3 = 0, Z = 15
EXEMPLO B
max Z = 4X1 + 3X2 max Z = 4X1 + 3X2 min W = A max -W + A = 0
sa 2X1 + 4X2 ≤ 15 sa 2X1 + 4X2 + F = 15 sa 2X1 + 4X2 + F = 15 sa 2X1 + 4X2 + F = 15
1X1 + 1X2 = 10 1X1 + 1X2 +A = 10 1X1 + 1X2 +A = 10 1X1 + 1X2 +A = 10
X1, X2 ≥ 0 X1, X2, F, A ≥ 0 X1, X2, F, A ≥ 0 X1, X2, F, A ≥ 0
Passamos o pl para a forma padrão, adicionando variáveis de excesso, de folga, e artificiais, onde
necessário:
Como a restrição 1 é do tipo '≤' é necessária a variável de folga F.
Como a restrição 3 é do tipo '=' é necessária a variável de artificial A.
Fase I
Base X1 X2 F A b
-W 1
F 2 4 1 15
A 1 1 1 10
Base X1 X2 F A b
-W -1 -1 -10 min
F 2 4 1 15 15/2
A 1 1 1 10 10
Base X1 X2 F A b
W 1 1/2 -5/2
X1 1 2 1/2 15/2
A -1 -1/2 1 5/2
Solução ótima Fim da Fase I.
W*=-5/2 Não existe Fase II (não existe solução viável para o pl original).
