Slide Programação Linear Análise de Pós Otimalidade-2020 1

11 Programação Linear – Análise de Pós Otimalidade © 2020 Prof. Sérgio F. Mayerle 11 Programação Linear – Análise de Pós Otimalidade EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 2 of 17  Condição de otimalidade e viabilidade  Análise sobre os coeficientes de RHS  Análise sobre os coeficientes da função objetivo  Inclusão de variável  Inclusão de restrições  Exemplo numérico 11 Programação Linear – Análise de Pós Otimalidade EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 3 of 17 Condição de Otimalidade e Viabilidade Seja a partição do problema de problema de programação linear padrão em sua solução ótima, dada por:   . : 0 B T T B R R B R B R x Max z c c x x s a B R b x x x                          Assim, as seguintes condições são satisfeitas: 1 0 ˆ 0 R B x x B b        (condição de viabilidade) 1 0 T T B R z c B R c      (condição de otimalidade) Para que a base corrente mantenha-se ótima depois de alguma alteração nos parâmetros do problema, é necessário que estas condição sejam preservadas. 11 Programação Linear – Análise de Pós Otimalidade EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 4 of 17 Análise sobre os Coeficientes de RHS Seja uma variação  no r-ésimo componente do vetor b, isto é, o novo vetor RHS passa a ser r b b  e   . Para manter a viabilidade da base corrente deve-se garantir que:       1 1 1 1 1 0 0 0 ˆ , 0 B B r B r B B x B b x B b e x B b B e x x B r                     onde B 1( , )   r representa a r-ésima coluna da matriz 1 B . Ou, para cada linha do sistema: 1 1 1 1 1 1 ˆ ( , ) 0 ˆ ( , ) 0 ( , ) ˆ ( , ) ˆ ( , ) 0 ( , ) se se Bi Bi Bi Bi Bi x x B i r x B i r B i r B i r x x B i r B i r                            11 Programação Linear – Análise de Pós Otimalidade EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 5 of 17 Análise sobre os Coeficientes da Função Objetivo Coeficientes das variáveis não-básicas Seja uma variação  no r-ésimo componente do vetor T R c , isto é, o novo vetor passa a ser T T T R R r c c  e   . Para manter a otimalidade da base corrente deve-se garantir que:   1 1 1 0 0 0 0 T T B R T T T B R r T T T B R r T r z c B R c z c B R c e z c B R c e z z e                          Ou, para cada elemento do vetor: 0 qualquer se se T r r r z z e j r z z j r                       Coeficientes das variáveis básicas Seja uma variação  no r-ésimo componente do vetor T B c , isto é, o novo vetor passa a ser T T T B B r c c  e   . Para manter a otimalidade é necessário que:   1 1 1 1 0 0 0 ( , ) 0 T T B R T T T B r R T r z c B R c z c e B R c z z e B R z z B r R                            Assim, para cada elemento do vetor, tem-se: 0 0 se se j rj rj rj j j rj rj z y y y z z y y                    onde 1( , ) rj j y B r R    . 11 Programação Linear – Análise de Pós Otimalidade EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 6 of 17 Inclusão de Variável Dado um PPL e sua solução ótima, a inclusão na base de uma variável  x n 1  qualquer somente ocorre caso a condição de otimalidade abaixo, não seja satisfeita pela variável a ser incluída:       1 1 1 1 0 T B n n n z c B a c         onde  c n 1  é o coeficiente desta variável na função objetivo, e  a n 1  é o correspondente vetor de coeficientes nas restrições. Caso  1 0 z n    a variável  x n 1  entra na base através de uma iteração primal; em caso contrário, a solução corrente se mantém ótima, sem que a variável  x n 1  entre na base. Inclusão de Restrição Dado um PPL e sua solução ótima, com a inclusão de uma restrição adicional pode ocorrer o caso da condição de viabilidade não ser satisfeita. Seja a restrição adicional:     1 1 1 n j m j m j a x b      Com a inclusão da variável de folga tem-se a equação:             1 1 1 1 1 1 1 1 n n j j m j m m m m m j j j a x S b S b a x                Se, considerando a solução ótima do PPL, tem-se  1 0 S m   , então a inclusão da restrição mantém viável a solução atual. Em caso contrário, se  1 0 S m   , uma nova solução poderá ser obtiva mediante a realização de iterações duais, escolhendo  1 0 S m   para ser excluída da base. 11 Programação Linear – Análise de Pós Otimalidade EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 7 of 17 Exemplo Numérico 1 2 3 1 2 3 1 2 3 1 2 3 10 2 1 . : 12 2 2 20 , , 0 Max z x x x s a x x x x x x x x x           Para este problema a seguinte partição é ótima:     1 1 1 2 3 2 1 1 1 1 2 0 10 0 2 0 1 2 1 1 0 12 2 1 0 1 2 1 20 T B B T R R S x B B c x x x x R c b S                                                   Isto é:         1 1 1 2 12 2 0 ˆ 0 1 2 20 10 0 1 1 2 1 1 0 0 10 2 1 0 3 9 5 0 0 0 0 1 2 1 2 1 xB B b z                                                 11 Programação Linear – Análise de Pós Otimalidade EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 8 of 17 Análise sobre os coeficientes de RHS Para 1b tem-se: 1 1 ˆ 2 2 1 ( , ) 1 ( ,1) 2 0 ? Linha 1: Linha 2: Bi x B i r B i                                  Para 2b tem-se: 1 1 1 ˆ 2 4 1 2 ( , ) 0.5 ( ,2) ˆ 1 2 10 20 ( , ) 0.5 20 4 Linha 1: Linha 2: Bi Bi x B i r B i x B i r                                             Resumo:  ib Coeficiente ib Atual Mínimo Máximo Mínimo Máximo 1b 12,00 -2,00 +INF 10,00 +INF 2b 20,00 -20,00 4,00 0,00 24,00 11 Programação Linear – Análise de Pós Otimalidade EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 9 of 17 Análise dos coeficientes não-básicos da FO Para 2 T (1) R c  c tem-se: 1 3   z  Para 3 T (2) R c  c tem-se: 2 9   z  Análise dos coeficientes básicos da FO Para 1 T (2) B c  c tem-se: 1 2 (2, ) j j y B R          1 21 21 2 22 22 3 23 23 1 3 1: 0 1 2 1 2 6 1 1 2 1 9 2: 0 1 2 1 9 2 1 0 5 3: 0 1 2 1 2 10 1 1 2 6 z j y y z j y y z j y y                                                                    Resumindo os resultados na tabela abaixo, tem-se:  jc Coeficiente jc Atual Mínimo Máximo Mínimo Máximo 1 T (2) B c  c 10,00 -6,00 +INF 4,00 +INF 2 T (1) R c  c 2,00 -INF +3,00 -INF 5,00 3 T (2) R c  c 1,00 -INF +9,00 -INF 10,00 11 Programação Linear – Análise de Pós Otimalidade EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 10 of 17 Inclusão de variável Considere o PPL 1 2 3 1 2 3 1 2 3 1 2 3 10 2 1 . : 12 2 2 20 , , 0 Max z x x x s a x x x x x x x x x           Para o qual tem-se a seguinte partição ótima:             1 1 1 2 3 2 1 1 1 1 1 2 0 10 0 2 0 1 2 1 1 0 12 2 1 0 1 2 1 20 1 1 2 12 2 0 ˆ 0 1 2 20 10 0 1 1 2 1 1 0 0 10 2 1 0 3 9 5 0 0 0 0 1 2 1 2 1 T B B T R R B S x B B c x x x x R c b S x B b z                                                                                                   11 Programação Linear – Análise de Pós Otimalidade EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 11 of 17 Considere que uma nova variável deve ser incluída, denotada por 4 x  0 , com os seguintes dados: 4 4 1 7 1 c a         Então, tem-se:         1 1 1 1 4 0 1 1 2 1 0 10 7 2 0 0 1 2 1 T B n n n z c B a c z                            Portanto, 4x deve entrar na base. Verificando a variável que sai da base, tem-se:   1 4 4 1 1 2 1 1/ 2 0 1 2 1 1/ 2 ˆ 2 10 min min | 0 min , 4 1/ 2 1/ 2 iB r i ik i i ik a B a x a a                                           Este resultado denota a necessidade de excluir a variável 1S (primeira variável básica) para que 4x possa entrar na base. 11 Programação Linear – Análise de Pós Otimalidade EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 12 of 17 Assim tem-se a nova partição dada por:     4 1 1 2 3 1 2 1 1 2 1 7 10 1 2 1 1 1 1 1 0 12 2 1 0 0 1 2 0 1 20 T B B T R R x x B B c x x x x R c b S S                                                      Obtendo a solução para esta partição tem-se:         1 1 2 1 12 4 ˆ 1 1 20 8 4 ˆ 7 10 108 8 2 1 1 1 1 0 7 10 2 1 0 0 5 9 4 3 1 1 1 2 0 1 B T B B T T B R x B b z c x z c B R c                                                     E, portanto esta é a solução ótima do problema. 11 Programação Linear – Análise de Pós Otimalidade EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 13 of 17 Inclusão de restrição Considere o PPL 1 2 3 1 2 3 1 2 3 1 2 3 10 2 1 . : 12 2 2 20 , , 0 Max z x x x s a x x x x x x x x x           Para o qual tem-se a seguinte partição ótima:             1 1 1 2 3 2 1 1 1 1 1 2 0 10 0 2 0 1 2 1 1 0 12 2 1 0 1 2 1 20 1 1 2 12 2 0 ˆ 0 1 2 20 10 0 1 1 2 1 1 0 0 10 2 1 0 3 9 5 0 0 0 0 1 2 1 2 1 T B B T R R B S x B B c x x x x R c b S x B b z                                                                                                   11 Programação Linear – Análise de Pós Otimalidade EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 14 of 17 Verifique qual a nova solução ótima caso seja incluída a restrição 1 2 3 1 2 1 8 x x x    . Calculando o valor da folga desta restrição tem-se: 1 2 3 3 3 1 2 3 3 1 2 1 1 8 8 1 2 1 8 1 10 2 0 1 0 2 0 x x x S S x x x S                   Assim, há necessidade do cálculo da nova solução ótima para o problema. Com a inclusão desta nova equação tem-se a seguinte partição:     1 1 1 3 2 3 2 1 1 0 1 1 2 0 0 2 0 0 1 2 0 0 10 0 0 1 1 0 1 2 1 1 1 0 12 1 2 1 2 1 0 20 2 1 0 8 T B B T R R S x x B B c S x x x R c b S                                                                        de onde obtém-se: 1 1 1 2 0 12 2 ˆ 0 1 2 0 20 10 0 1 2 1 8 2 xB B b                                      11 Programação Linear – Análise de Pós Otimalidade EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 15 of 17       1 1 1 2 0 1 1 0 0 10 0 0 1 2 0 1 2 1 2 1 0 3 9 5 0 1 2 1 2 1 0 T T B R z c B R c z                               Considerando que 3 2 S   , esta variável deve sair da base, através de uma iteração dual. Recuperando a 3ª linha para realização do teste de razão dual:   1 1 1 2 0 1 1 0 3 1 (3, ) 0 0 1 0 1 2 0 1 2 1 0 2 2 0 1 2 1 2 1 0 3 9 5 max , , 10 3/ 2 0 1/ 2 k B R                                             Desta forma, entra na base a variável 2 S . A nova partição da base fica: 11 Programação Linear – Análise de Pós Otimalidade EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 16 of 17     1 1 1 2 2 3 3 1 1 0 1 0 1 0 2 1 0 0 1 0 10 0 0 1 0 0 1 2 1 1 0 12 1 2 0 2 1 0 20 2 1 1 8 T B B T R R S x x B B c S x x x R c b S                                                                        de onde obtém-se:         1 1 1 0 1 12 4 ˆ 0 0 1 20 8 0 1 2 8 4 1 0 1 1 1 0 0 10 0 0 0 1 1 2 0 2 1 0 18 9 10 0 1 2 2 1 1 4 ˆ ˆ 0 10 0 8 80 4 B T T B R T B B x B b z c B R c z c x                                                                               Esta, portanto, é a nova solução ótima após inclusão da restrição. 11 Programação Linear – Análise de Pós Otimalidade EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 17 of 17 F I M (© 2020 Prof. Sérgio Mayerle)