METODO SIMPLEX DE DUAS FASES

Prévia do material em texto

ISPUNA INVESTITIGAÇÃO OPERACIONAL 
3º Ano/AGE docente: Jorge Filipe Tagire 
 
2. RESOLUÇÃO DOS PROBLEMAS DE PROGRAMAÇÃO LINEAR PELO 
MÉTODO SIMPLEX DE DUAS FASES 
 
 
2.1. Minimização com restrições da forma  
O processo iterativo do método simplex sempre exige uma solução básica inicial a partir da 
qual se busca uma solução óptima. Nos problemas de maximização esta solução básica 
inicial era formada pelas variáveis de folga, já que as restrições eram do tipo (  ). Quando 
as restrições são do tipo (  ) ou (=), não existe essa solução básica inicial. 
Vejamos: 
Minimizar W =16x1 +12x2 + 5x3 
Sujeito à {
8𝑥1 + 4𝑥2 + 4𝑥3 ≥ 16
4𝑥1 + 6𝑥2 + 0𝑥3 ≥ 12
𝑥1, 𝑥2, 𝑥3 ≥ 0
 
Como devem ser introduzidas variáveis de excesso a forma padrão do problema de 
minimização é: 
Minimizar W = 16x1 +12x2 + 5x3 + 0x4 + 0x5 
Sujeito à {
8𝑥1 + 4𝑥2 + 4𝑥3 − 𝑥4 + 0𝑥5 = 16
4𝑥1 + 6𝑥2 + 0𝑥3 + 0𝑥4 − 𝑥5 = 12
𝑥1, 𝑥2, 𝑥3, 𝑥4, 𝑥5 ≥ 0
 
O processo de resolução anteriormente realizado leva as variáveis de excesso x4 e x5 a 
valores negativos ( x4 = −16 e x5 = −12 ), violando a condição de não negatividade. 
 
 
Conclusão: 
 
Para resolver este tipo de problemas são introduzidas algumas modificações nas equações 
das restrições em seguida pode se usar o procedimento dual, os métodos de duas fases, de 
grande M e o Dual simplex, que são modificações do método simplex directo.
ISPUNA INVESTITIGAÇÃO OPERACIONAL 
3º Ano/AGE docente: Jorge Filipe Tagire 
 
2.2. MÉTODO DE DUAS FASES 
 
Para os problemas de minimização na forma canónica, o método simplex em duas fases tem 
os seguintes passos: 
Passo 1. Introduzir as variáveis de excesso ( − xm+ n ) e artificiais( + ai ) para cada restrição. 
Passo 2. Criar uma nova função objectivo formada pela: 
• soma dos coeficientes das equações para a mesma variável tomados com o sinal 
negativo d = −(a11 +21 +... + an1); 
• soma dos coeficientes das variáveis artificiais que é igual a zero; 
• nova função objectivo que é igual a soma dos termos intependentes tomados com o 
sinal negativo ( Za = −(b1 + b2 + ... + bn ) 
Passo 3. Escreve-se a tabela inicial do simplex para a 1ª fase do processo de resolução do 
problema. 
Passo 4. Aplica-se normalmente o procedimento do método simplex, tomando-se como 
função objectivo a última linha. Quando a solução óptima for atingida dois casos podem 
ocorrer: 
• Za = 0 : neste caso foi obtida uma solução básica do problema original e o processo 
de solução deve continuar, desprezando-se as variáveis artificiais e os elementos da 
última linha. E o início da fase 2 do processo. 
• Za  0 : neste caso o problema original não tem solução viável. 
 
 
Exemplo 2.11. Resolva o seguinte problema pelo método de duas fases. 
Minimizar W = 16x1 +12x2 + 5x3 
 
Sujeito à {
8𝑥1 + 4𝑥2 + 4𝑥3 ≥ 16
4𝑥1 + 6𝑥2 + 0𝑥3 ≥ 12
𝑥1, 𝑥2, 𝑥3 ≥ 0
 
Resolução 
Minimizar W = 16x1 +12x2 + 5x3 + 0x4 + 0x5 + 0a1 + 0a2 
Sujeito à {
8𝑥1 + 4𝑥2 + 4𝑥3 − 𝑥4 + 0𝑥5 + 𝑎1 + 0𝑎2 = 16
4𝑥1 + 6𝑥2 + 0𝑥3 + 0𝑥4 − 𝑥5 + 0𝑎1 + 𝑎2 = 12
𝑥1, 𝑥2, 𝑥3, 𝑥4, 𝑥5, 𝑎1, 𝑎2 ≥ 0
 
 
Maximizar Za = −12x1 −10x2 − 4x3 +1x +1x5 + 0a1 + 0a2 − 28
ISPUNA INVESTITIGAÇÃO OPERACIONAL 
3º Ano/AGE docente: Jorge Filipe Tagire 
 
Tabela inicial simplex 
 
1ª fase (iteração 1) 
 
1ª fase (iteração 2) 
 
 
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 (2a fase) 
 
Lembre-se que é de minimizar, portanto os indicadores da linha pivô devem ser todos 
negativos. 
ISPUNA INVESTITIGAÇÃO OPERACIONAL 
3º Ano/AGE docente: Jorge Filipe Tagire 
 
 
2ª fase (iteração 1) 
 
 
Solução: x1 = 0; x2 = 2; x3 = 2; x4 = 0; x5 = 0; Wmin = 34 
 
 
Exemplo 2.12. Resolver o problema pelo método de duas fases: 
Minimizar W = 4x1 + x2 
Sujeito à {
3𝑥1 + 𝑥2 ≥ 3
4𝑥1 + 3𝑥2 ≥ 6
𝑥1 + 2𝑥2 ≥ 3
𝑥1, 𝑥2 ≥ 0
 
 
Resolução 
Minimizar W = 4x1 + x2 + 0(x3 + x4 + 0x5 ) + 0(a1 + a2 + a3 ) 
Sujeito à {
3𝑥1 + 𝑥2 − 𝑥3 + 0𝑥4 + 0𝑥5 + 𝑎1 + 0𝑎2 + 0𝑎3 = 3
4𝑥1 + 3𝑥2 + 0𝑥3 − 𝑥4 + 0𝑥5 + 0𝑎1 + 𝑎2 + 0𝑎3 = 6
𝑥1 + 2𝑥2 + 0𝑥3 + 0𝑥4 − 𝑥5 + 0𝑎1 + 0𝑎2 + 𝑎3 = 3
𝑥1, 𝑥2, 𝑥3, 𝑥4, 𝑥5, 𝑎1, 𝑎2, 𝑎3 ≥ 0
 
Maximizar Za= −𝟖𝒙𝟏 − 𝟔𝒙𝟐 + 𝟏𝒙𝟑 + 𝟏𝒙𝟒 + 𝟏𝒙𝟓 + 𝟎𝒂𝟏 + 𝟎𝒂𝟐 + 𝒂𝟑 − 𝟏𝟐 
Tabela inicial simplex (1ª fase) 
 
 
1ª fase (iteração 1) 
 
 
ISPUNA INVESTITIGAÇÃO OPERACIONAL 
3º Ano/AGE docente: Jorge Filipe Tagire 
1ª fase (iteração 2) 
 
1ª fase (iteração 3) 
 
Como na última linha o valor da ftmçã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ª fase) 
 
2ª fase (iteração 1) 
 
 
 
 
 Solução: 
x1 = 0; x2 = 3; x3 = 0; x4 = 3; x5 = 3; Wmin = 3 
 
 
 
 
 
 
 
ISPUNA INVESTITIGAÇÃO OPERACIONAL 
3º Ano/AGE docente: Jorge Filipe 
Tagire 
EXERCÍCIOS: 
1. Resolva os seguintes problemas de programação linear pelo método simplex de 
duas fases: 
 
a) Minimizar W =x1 +x2 
 Sujeito à {
2𝑥1 + 𝑥2 ≥ 16
𝑥1 + 2𝑥2 ≥ 14
𝑥1, 𝑥2 ≥ 0
 
 
b) Minimizar W = 5x1 +4x2 
 
 Sujeito à {
3𝑥1 + 𝑥2 ≥ 8
4𝑥1 + 4𝑥2 ≥ 15
𝑥1 + 𝑥2 ≥ 0
𝑥1, 𝑥2 ≥ 0
 
Resp: 𝑥1 = 1; 𝑥2 = 5; 𝑥3 = 0 ; 𝑥4 = 9 ; 𝑥5 = 0 ; 𝑊𝑚𝑖𝑛 = 25 
 
c) Minimizar W = 6x1 +8x2 + 12x3 
 
 Sujeito à {
𝑥1 + 3𝑥2 + 3𝑥3 ≥ 6
𝑥1 + 5𝑥2 + 5𝑥3 ≥ 4
−2𝑥1 − 2𝑥2 − 3𝑥3 ≤ −8
𝑥1, 𝑥2, 𝑥3 ≥ 0
 
Resp: 𝑥1 = 3; 𝑥2 = 1; 𝑥3 = 0 ; 𝑥4 = 0 ; 𝑥5 = 0 ; 𝑊𝑚𝑖𝑛 = 26