Baixe o app para aproveitar ainda mais
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
Compartilhar