Programação Linear Algoritmo Primal-dual-2020-1

10 Programação Linear – Algoritmo Primal-Dual © 2020 Prof. Sérgio F. Mayerle 10 Programação Linear – Algoritmo Primal-Dual EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 2 of 12  Consideração inicial  Análise das trocas de base: primal x dual  Algoritmo Simplex Primal-Dual  Exemplo Resolvido 10 Programação Linear – Algoritmo Primal-Dual EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 3 of 12 Consideração Inicial Considere o PPL primal abaixo, em sua forma primal, com 1  , 2  e 3  as variáveis duais associadas às restrições: 1 2 1 2 1 1 2 2 1 2 3 1 2 100 150 1 2 20 ( ) 2 1 25 ( ) 3 1 30 ( ) , 0 Max s.a: z x x x x x x x x x x             Sabe-se que, para cada base do PPL primal existe uma base correspondente no PPL dual, tal que : PPL Primal PPL Dual Se jx está na base do primal... então j R está fora da base do dual Se jx está fora da base do primal... então j R está na base do dual Se iS está na base do primal... então i está fora da base do dual Se iS está fora da base do primal... então i está na base do dual Para cada troca de base no problema primal, uma variável é escolhida para entrar na base, para em seguida determinar a variável que deverá ser retirada da base. Esta troca de base tem correspondência no problema dual, onde a inclusão na base da variável primal induz a retirada da variável correspondente da base do dual. Por outro lado, a retirada da base de uma variável do problema primal, induz a entrada da variável dual correspondente na base. 10 Programação Linear – Algoritmo Primal-Dual EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 4 of 12 Análise das trocas de base: Primal x Dual Segue a resolução do PPL primal (P) e o dual (D) correspondente, com iterações realizadas par-a-par. PPL Primal (P) PPL Dual (D) 1 2 1 2 1 1 2 2 1 2 3 1 2 100 150 1 2 20 ( ) 2 1 25 ( ) 3 1 30 ( ) , 0 Max s.a: z x x x x x x x x x x             1 2 3 1 2 3 1 2 1 2 3 1 2 3 20 25 30 1 2 3 100 ( ) ( ) 2 1 1 150 , , 0 Min s.a: w x x                       Base Z X1 X2 S1 S2 S3 RHS S1 0 1 2 1 0 0 20 ◄ S2 0 2 1 0 1 0 25 S3 0 3 1 0 0 1 30 Z 1 -100 -150 0 0 0 0 ▲ X2 entra na base no lugar de S1 Base (-w) P1 P2 P3 R1 R2 RHS R1 0 -1 -2 -3 1 0 -100 R2 0 -2 -1 -1 0 1 -150 ◄ (-w) 1 20 25 30 0 0 0 ▲ R2 deixa a base para P1 entrar Base Z X1 X2 S1 S2 S3 RHS X2 0 0,5 1 0,5 0 0 10 S2 0 1,5 0 -0,5 1 0 15 S3 0 2,5 0 -0,5 0 1 20 ◄ Z 1 -25 0 75 0 0 1500 ▲ X1 entra na base no lugar de S3 Base (-w) P1 P2 P3 R1 R2 RHS R1 0 0 -1,5 -2,5 1 -0,5 -25 ◄ P1 0 1 0,5 0,5 0 -0,5 75 (-w) 1 0 15 20 0 10 -1500 ▲ R1 deixa a base para P3 entrar 10 Programação Linear – Algoritmo Primal-Dual EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 5 of 12 Base Z X1 X2 S1 S2 S3 RHS X2 0 -0 1 0,6 0 -0,2 6 S2 0 -0 0 -0,2 1 -0,6 3 X1 0 1 0 -0,2 0 0,4 8 Z 1 1E-14 0 70 0 10 1700 Esta solução é ótima para o problema primal ! Base (-w) P1 P2 P3 R1 R2 RHS P3 0 -6E-17 0,6 1 -0,4 0,2 10 P1 0 1 0,2 0 0,2 -0,6 70 (-w) 1 0 3 0 8 6 -1700 Esta solução é ótima para o problema dual ! Observem que os dois problemas tem o mesmo número de variáveis (por construção), mas neste caso o PPL primal tem mais equações que o dual. Assim, o dual é mais econômico do ponto de vista computacional. No exemplo, observa-se que cada troca de base realizada no PPL Primal, corresponde uma troca de base realizada no PPL Dual, como segue: Passo Iteração Primal Iteração Dual 1 Escolher uma variável não básica R kx para entrar na base, associada a um coeficiente 0  kz   Escolher uma variável básica B rx para sair da base, associada a um ˆ 0 B rx  2 Determinar a variável básica B rx para sair da base, de modo que: ˆ ˆ min | 0 B B B i r r ik i rk ik x x x a a a          Se não existe 0 ik a  , o PPL tem solução ilimitada, isto é, z   .  Determinar a variável não básica R kx para entrar na base, de modo que: max | 0 j R k k rj j rk rj z z x a a a                Se não existe 0 rj a  , o PPL não tem solução viável. 3 Fazer a troca de base, incluindo a variável R kx no lugar da variável B rx 10 Programação Linear – Algoritmo Primal-Dual EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 6 of 12 As iterações primais e duais podem ser realizadas de modo alternado, a depender da conveniência de cada momento. Enquanto que as iterações primais se encarregam de aumentar o valor da função objetivo, as iterações duais se encarregam de viabilizar a solução. 10 Programação Linear – Algoritmo Primal-Dual EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 7 of 12 Algoritmo Primal-Dual P1. Inicialização. Leia o PPL, inclua as variáveis de folga, coloque o PPL na forma padrão, e escolha uma base inicial (composta por vetores unitários). Construa o tableau. P2. Iteração Dual. Determine   | ˆ 0 B B i i S x x   . Se S   vá ao passo P5. Em caso contrário, escolha para sair da base alguma variável rxB S . P3. Determine a variável R kx para entrar na base através do seguinte teste de razão: max | 0 j R k k rj j rk rj z z x a a a                Se neste teste não existe 0 rj a  termine com fracasso, pois o PPL não admite solução viável. P4. Execute ( , ) B R r k TrocaBaseTableau x x e volte ao passo P2. P5. Iteração Primal. Determine   | 0 R j j S x z    . Se S   vá ao passo P8. Em caso contrário, escolha para entrar na base alguma variável kxR S . P6. Determine a variável B rx para sair da base através do seguinte teste de razão: ˆ ˆ min | 0 B B B i r r ik i rk ij x x x a a a              Se neste teste não existe 0 ik a  termine com fracasso, pois o PPL não admite solução finita. P7. Execute ( , ) B R r k TrocaBaseTableau x x e volte ao passo P5. P8. Finalização. Apresente a solução ótima do PPL e termine com sucesso. 10 Programação Linear – Algoritmo Primal-Dual EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 8 of 12 Considere os dados apresentados no tableau abaixo, onde o pivot da operação encontra-se assinalado: 1 2 2 1 11 12 1 1 1 2 21 22 2 2 2 1 2 1 2 1 2 ˆ ˆ ˆ ˆ ˆ R k B B k n B B k n B B r r r rk rn r B B m m m mk mn m k n Base x x x x RHS x a a a a x x a a a a x x a a a a x x a a a a x z z z z z z                                 Então a troca de base se dá através da execução do procedimento ( , ) B R r k TrocaBaseTableau x x descrito na coluna ao lado: Procedimento ( , ) B R r k TrocaBaseTableau x x Para 1,..., | i m i r    faça ik rk aux a a  Para 1,..., j n   faça ij ij rj a a a aux    ˆ ˆ ˆ B B B i i r x x x aux    FimPara k rk aux z a   Para 1,..., j n   faça j j rj z z a aux      ˆ ˆ ˆ B r z z x aux    rk aux  a Para 1,..., j n   faça / rj rj a a aux  ˆ ˆ / B B r r x x aux  Inclua R kx na base, na posição ocupada por B rx FimProc. 10 Programação Linear – Algoritmo Primal-Dual EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 9 of 12 Exemplo 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 20 10 30 8 . : 1 2 1 1 120 0 1 0 2 150 1 1 3 1 120 1 1 1 1 115 , , , 0 Max z x x x x s a x x x x x x x x x x x x x x x x x x x x                      Incluido as variáveis de folga nas restrições de desigualdade, tem-se o seginte sistema de equações representado na forma tableau: Base Z X1 X2 X3 X4 S1 S2 S3 RHS S1 0 1 2 1 1 1 0 0 120 S2 0 0 -1 0 -2 0 1 0 -150 S3 0 -1 -1 -3 -1 0 0 1 -120 ? 0 1 1 1 1 0 0 0 115 Z 1 -20 10 -30 8 0 0 0 0 A fim de formar a base inicial, precisamos escolher mais uma variável para compor a base. Escolhendo para tanto a variável X2, e usando como pivo o elemento que se encontra na 4ª linha para anular os demais elementos da coluna desta variável, tem-se como base inicial: 10 Programação Linear – Algoritmo Primal-Dual EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 10 of 12 Base Z X1 X2 X3 X4 S1 S2 S3 RHS S1 0 -1 0 -1 -1 1 0 0 -110 S2 0 1 0 1 -1 0 1 0 -35 S3 0 0 0 -2 0 0 0 1 -5 X2 0 1 1 1 1 0 0 0 115 Z 1 -30 0 -40 -2 0 0 0 -1150 Fazendo uma iteração dual na qual se escolhe a variável S1 para sair da base, determina-se que a variável X3 deve entrar na base. Realizando esta troca de base, tem-se: Base Z X1 X2 X3 X4 S1 S2 S3 RHS X3 0 1 4,44E-16 1 1 -1 0 0 110 S2 0 -2,22E-16 -4,44E-16 -2,22E-16 -2 1 1 0 -145 S3 0 2 0 0 2 -2 0 1 215 X2 0 -2,22E-16 1 -2,22E-16 -2,22E-16 1 0 0 5 Z 1 10 1,42E-14 7,11E-15 38 -40 0 0 3250 Fazendo agora uma iteração primal na qual se escolhe a variável S1 para entrar na base, determina-se que a variável S2 deve sair da base. Realizando a troca de base, tem-se: Base Z X1 X2 X3 X4 S1 S2 S3 RHS X3 0 1 0 1 -1 0 1 0 -35 S1 0 0 -2,22E-16 0 -2 1 1 0 -145 S3 0 2 0 0 -2 0 2 1 -75 X2 0 0 1 0 2 0 -1 0 150 Z 1 10 0 0 -42 0 40 0 -2550 10 Programação Linear – Algoritmo Primal-Dual EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 11 of 12 Fazendo novamente um iteração primal, na qual se escolhe X4 para entrar na base, determina-se que X2 deve sair da base. Desta forma tem-se, com esta troca de base, a seguinte solução: Base Z X1 X2 X3 X4 S1 S2 S3 RHS X3 0 1 0,5 1 0 0 0,5 0 40 S1 0 0 1 0 0 1 0 0 5 S3 0 2 1 0 0 0 1 1 75 X4 0 0 0,5 0 1 0 -0,5 0 75 Z 1 10 21 0 0 0 19 0 600 Todos os coeficientes de RHS são positivos, bem como os coeficientes da linha da função objetivo. Logo, a solução corrente é ótima. Segue a interpretação: Variável Valor Marginal X1 0 10 X2 0 21 X3 40 0 X4 75 0 S1 5 0 S2 0 19 S3 75 0 Z 600 1 Interpretação dos Resultados Na solução ótima as variáveis assumem os seguintes valores: 1 2 0 x  x  , 3 x  40 , 4 x  75 e z  600 . Quanto às restrições, a primeira apresenta folga 1 S  5 , a terceira apresenta excesso 3 S  75 , enquanto que as demais restrições não apresentam folga ou excesso. Do lado dos valores marginais, a cada unidade adicionada às variáveis 1x e 2x , diminui o valor da função objetivo em 10 e 21 unidades, respectivamente. Ao aumentar o coeficiente RHS da terceira restrição em uma unidade, o aumento da flexibilidade permite melhorar a função objetivo em 19 unidades. 10 Programação Linear – Algoritmo Primal-Dual EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 12 of 12 F I M (© 2020 Prof. Sérgio Mayerle)