Programação Linear Dualidade-2020-1

09 Programação Linear – Dualidade © 2020 Prof. Sérgio F. Mayerle 09 Programação Linear – Dualidade EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 2 of 12  Dualidade  Interpretação econômica da dualidade  Resolver Primal ou Dual ? 09 Programação Linear – Dualidade EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 3 of 12 Dualidade Definição Dado um problema de programação linear (P), denominado de primal, apresentado na forma canônica abaixo: ( ) . : ( ) 0 (1.a) (1.b) (1.c) T P Max z c x s a Ax b x     Então sempre é possível contruir um segundo problema de programação linear (D), denominado de dual de (P), como segue: ( ) . : 0 (2.a) (2.b) (2.c) T T D Min w b s a A c       (P) relaciona-se com (D) através das seguintes proposições: Proposição 1  Seja *x a solução ótima de (P). Seja *  a solução ótima de (D). Então * * T T c x  b  .  Se (P) tem solução ilimitada, então (D) não tem solução.  Se o (P) não tem solução, então (D) tem solução ilimitada. Proposição 2 Seja *x a solução ótima de (P), e   A B R  a partição correspondente. Então * 1 T T B R c B R c     é a solução ótima de (D). 09 Programação Linear – Dualidade EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 4 of 12 Outras relações válidas pela dualidade Além da relação entre (P) e (D) apresentada na definição, tem-se as seguintes relações válidas pela dualidade: Problema Primal Problema Dual Ax  b   0 Ax  b   0 Restrição Ax  b Variável  qualquer x  0 AT   c x  0 AT   c Variável x qualquer Restrição AT   c FO Maximizar FO Minimizar 09 Programação Linear – Dualidade EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 5 of 12 Exemplo Seja o problema de programação linear, denominado de primal (P):     1 2 3 1 2 3 1 1 2 3 2 1 2 3 10 3 4 . : 1 2 3 12 2 1 2 10 , 0 qualquer Max z x x x s a x x x x x x x x x             Então o dual (D) correspondente será:       1 2 1 2 1 1 2 2 1 2 3 1 2 12 10 . : 1 2 10 2 1 3 3 2 4 0 qualquer Min w s a x x x                     09 Programação Linear – Dualidade EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 6 of 12 Interpretação Econômica da Dualidade Considere o problema de produção definido pelos dados da tabela abaixo: Recurso P1 P2 Disponibilidade (horas/sem) R1 2 1 1500 R2 0 1 1000 R3 1 3 1400 Lucro (R$/unid) 220 280 Uma possibilidade a ser considerada é utilizar os recursos disponíveis (R1, R2 e R3) na produção de produtos (P1 e P2), de modo a maximizar a contribuição desta produção para o lucro da empresa. Como variáveis de decisão têm-se 1x e 2x que representam as quantidades a serem produzidas semanalmente de cada um dos produtos; a disponibilidade semanal dos três recursos precisam ser consideradas como restrições; e como função objetivo considera-se a maximização do lucro total obtido com a produção. A formulação matemática deste problema é a seguinte:       1 2 1 2 1 2 2 1 2 3 1 2 220 280 . : 2 1 1500 1 1000 1 3 1400 , 0 x x s a x x x x x x x Max z            O Dual correspondente tem a seguinte formulação: 1 2 3 1 3 1 2 3 1 2 3 1500 1000 1400 . : 2 1 220 1 1 3 280 , , 0 s a Min W                     Enquanto o problema primal é associado à produção dos 2 produtos, o dual pode ser entendido como um problema de venda dos recursos aos preços 1  , 2  e 3  , de modo que cada “pacote” de recurso usado na produção de uma unidade de produto, produza um ganho pelo menos igual ao obtido quando alocados na produção. 09 Programação Linear – Dualidade EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 7 of 12 Resolver Primal ou Dual ? Resolvendo o PPL Primal       1 2 1 2 1 2 2 1 2 3 1 2 220 280 . : 2 1 1500 1 1000 1 3 1400 , 0 x x s a x x x x x x x Max z            Incluindo as variáveis de folga e montando o tableau tem-se: Base Z X1 X2 S1 S2 S3 RHS S1 0 2 1 1 0 0 1500 S2 0 0 1 0 1 0 1000 S3 0 1 3 0 0 1 1400 ◄ Z 1 -220 -280 0 0 0 0 ▲ X2 entra na base no lugar de S3 09 Programação Linear – Dualidade EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 8 of 12 Base Z X1 X2 S1 S2 S3 RHS S1 0 1,667 0 1 0 -0,33 1033,33 ◄ S2 0 -0,33 0 0 1 -0,33 533,333 X2 0 0,333 1 0 0 0,333 466,667 Z 1 -127 0 0 0 93,33 130667 ▲ X1 entra na base no lugar de S1 Base Z X1 X2 S1 S2 S3 RHS X1 0 1 -0 0,6 0 -0,2 620 S2 0 0 -0 0,2 1 -0,4 740 X2 0 0 1 -0,2 0 0,4 260 Z 1 0 0 76 0 68 209200 Solução ótima!!! 09 Programação Linear – Dualidade EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 9 of 12 Resolvendo o PPL Dual 1 2 3 1 3 1 2 3 1 2 3 1500 1000 1400 . : 2 1 220 1 1 3 280 , , 0 s a Min W                     Incluindo as variáveis de folga e as variáveis artificiais, montando o tableau em duas fase, tem-se: Base -Wa -W P1 P2 P3 R1 R2 d1 d2 RHS d1 0 0 2 0 1 -1 0 1 0 220 d2 0 0 1 1 3 0 -1 0 1 280 ◄ -W 0 1 1500 1000 1400 0 0 0 0 0 -Wa 1 0 -3 -1 -4 1 1 0 0 -500 ▲ Sai a variável d2 da base e entra P3 em seu lugar Base -Wa -W P1 P2 P3 R1 R2 d1 d2 RHS d1 0 0 1,67 -0,33 0 -1 0,33 1 -0,33 126,6667 ◄ P3 0 0 0,33 0,33 1 0 -0,33 0 0,33 93,33333 -W 0 1 1033 533 0 0 467 0 -467 -130667 -Wa 1 0 -1,67 0,33 0 1 -0,33 0 1,33 -126,667 ▲ Sai a variável d1 da base e entra P1 em seu lugar 09 Programação Linear – Dualidade EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 10 of 12 Base -Wa -W P1 P2 P3 R1 R2 d1 d2 RHS P1 0 0 1 -0,2 0 -0,6 0,2 0,6 -0,2 76 P3 0 0 0 0,4 1 0,2 -0,4 -0,2 0,4 68 -W 0 1 0 740 -0 620 260 -620 -260 -209200 -Wa 1 0 0 0 0 0 0 1 1 0 Esta é a solução ótima da 1ª fase, que zera o valor das variáveis artificiais, e portanto serve de solução inicial para a 2ª fase. Eliminando as variáveis artificiais, tem-se: Base -W P1 P2 P3 R1 R2 RHS P1 0 1 -0,2 0 -0,6 0,2 76 P3 0 0 0,4 1 0,2 -0,4 68 -W 1 0 740 -0 620 260 -209200 Que também é solução ótima para a 2ª fase!!! 09 Programação Linear – Dualidade EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 11 of 12 Resumindo as soluções       1 2 1 2 1 2 2 1 2 3 1 2 220 280 . : 2 1 1500 1 1000 1 3 1400 , 0 x x s a x x x x x x x Max z                1 2 3 1 3 1 1 2 3 2 1 2 3 1500 1000 1400 . : 2 1 220 1 1 3 280 , , 0 s a x x Min W                     Problema Primal Variável Valor z  1x 620 0 1 R 2x 260 0 2 R 1S 0 76 1  2 S 740 0 2  3 S 0 68 3  z 209200 1 1 209200 W z  Valor Variável Problema Dual Observe que:  na solução ótima, a cada variável básica do problema primal tem-se uma variável não-básica correspondente no problema dual, e vice-versa.  as variáveis estruturais do problema primal estão em associação com as variáveis de folga no dual, e vice-versa. 09 Programação Linear – Dualidade EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 12 of 12 F I M (© 2020 Prof. Sérgio Mayerle)