Programação Linear Inteira Métodos e Algoritmos-2020-1

17 Programação Linear Inteira – Métodos e Algoritmos © 2020 Prof. Sérgio F. Mayerle 17 Programação Linear Inteira – Métodos e Algoritmos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 2 of 14  Técnicas de resolução em programação inteira  Método de branch and bound  Algoritmo branch and bound  Exemplo numérico  Planos de corte de Gomory  Algoritmo de Gomory  Exemplo Numérico 17 Programação Linear Inteira – Métodos e Algoritmos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 3 of 14 Técnicas de resolução em programação inteira Diversas técnicas de resolução podem ser aplicadas na solução de problemas de programação inteira. Para este tipo de problema existem métodos genéricos de resolução:  Algoritmo de branch and bound  Algoritmo de cortes de Gomory e métodos específicos para problemas de programação linear binária:  Algoritmo de Balas  Relaxação Lagrangeana  Meta heurísticas o Genetic Algorithm o Tabu Search o Simulated Annealing o Guided Local Search o Ant System 17 Programação Linear Inteira – Métodos e Algoritmos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 4 of 14 Método de branch and bound Definição 1 Seja o problema de programação linear inteira mista apresentado na forma:   . : T Max z c x s a x M    onde 1,..., { | , 0 , } n j k M x R Ax b x u x Z        . Definição 2 Seja o problema de programação linear inteira mista relaxado, obtido a partir de    , na forma:   . : T Max z c x s a x M    onde { | , 0 } n M x R Ax b x u      . Note-se que M  M . Proposição 1  Se    não tem solução, então    também não terá solução;  Se * x é a solução ótima de    e * , 1,..., jx Z j k    , então * x é a solução ótima de    . 17 Programação Linear Inteira – Métodos e Algoritmos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 5 of 14 Proposição 2 Seja * x a solução ótima de    , com jx* Z pelo menos para algum 1,..., j k  . Sejam os conjuntos:     * 1 | , 0 , n j j M x R Ax b x u x x              * 2 | , 0 , n j j M x R Ax b x u x x          onde x     é o maior inteiro menor ou igual que x, e x     é o menor inteiro maior ou igual que x. Assim:  Se    admite solução ótima *x , então     * 1 2 x M M   ;  Se     * 1 1 x M e     * 2 2 x M são soluções que maximizam Tc x, sobre os conjuntos M 1 e   M 2 , respectivamente, e: o se * * (1) (2) T T c x  c x e se * x(1) satisfaz as condições de integridades definidas para    , então * x(1) é a solução ótima de    ; o se * * (1) (2) T T c x  c x e se * x(2) satisfaz as condições de integridades definidas para    , então * x(2) é a solução ótima de    .   1 M   2 M M   * 1 x   * 2 x Figura 1 – Diagrama de Venn para soluções do problema relaxado 17 Programação Linear Inteira – Métodos e Algoritmos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 6 of 14 Algoritmo branch and bound P1 Gere uma lista vazia  para armazenar LP’s. Resolva    . Se    não tem solução viável, então PARE; neste caso    também não terá solução viável. Em caso contrário, inclua    na lista. P2 Escolha, entre os LP's de  , o problema  r  cujo valor da solução ótima seja o máximo. Se mais de um problema atende esta condição, desempate de qualquer forma, mas sempre a favor de soluções que satisfaçam as condições de integridade de    . P3 Retire  r  de  e, se a solução de  r  satisfiz as condições de integridade de    , PARE com sucesso: a solução ótima de    foi encontrada. Em caso contrário, tome uma variável inteira que não satisfaz a condição de integridade, isto é jx* Z , e gere dois novos LP's, pela agregação das seguintes restrições adicionais:     * ,1 * ,2 r j j r j j x x x x               Resolva  r,1  e  r,2  , e inclua em  aquele que tiver solução. P4 Se a  estiver vazia, então PARE com fracasso:    não tem solução viável. Em caso contrário volte ao Step 2. Observações  São aplicadas técnicas de análise de pós- otimalidade, através das quais uma iteração dual é suficiente para encontrar a solução do problema descendente partindo-se da solução do problema ancestral imediato;  Na prática descartam-se LP's tais que z é menor que   * 1 rz z     , onde *z é o maior valor de rz entre soluções inteiras conhecidas. 17 Programação Linear Inteira – Métodos e Algoritmos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 7 of 14 Exemplo numérico Seja o problema    : 1 2 3 1 2 3 1 2 3 1 2 3 3 3 13 . : 3 6 7 8 6 3 7 8 0 , , 5 e inteiros Max z x x x s a x x x x x x x x x               0  1 2 3 16,00 2,67 2,67 0,00 z x x x       1  1 2 3 15,71 2,00 2,00 0,29 z x x x       2  Inviável 1 x  2 1 3 x    4  1 2 3 15,00 0,33 0,33 1,00 z x x x       3  1 2 3 13,00 2,00 2,33 0,00 z x x x     3 x  0 3 1 x    6  Inviável   5  1 2 3 14,86 0,00 0,00 1,14 z x x x     1 x  0 1 1 x    8  1 2 3 13,50 0,00 0,17 1,00 z x x x       7  Inviável 3 x  2 3 1 x   10  1 2 3 13,00 0,00 0,00 1,00 z x x x       9  Inviável 2 x 1 2 x  0 17 Programação Linear Inteira – Métodos e Algoritmos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 8 of 14 Planos de corte de Gomory O método de planos de corte buscam obter uma aproximação da envoltória convexa da região viável de um problema da programação inteira que contenha um ponto extremo correspondente a uma solução ótima. Essa aproximação é obtida por meio de cortes ou desigualdades válidas, adicionadas ao problema original. Definição Uma desigualdade 0 x  é uma desigualdade válida para n X  R se é válida para todo x  X . Em outras palavras, uma desigualdade é válida se o conjunto n X  R situa-se num dos semi-espaços definidos pelo hiperplano 0 x  . Proposição O procedimento geral para a construção de uma desigualdade válida para o conjunto   : , n X x Ax b x Z    , tal que A é uma matriz m n  com colunas   1,... n a a e m u  R , conhecido como procedimento de Chvatal-Gomory, é descrito a seguir:  a desigualdade 1 n T T j j j u a x u b    é válida para X pois u  0 e 1 n j j j a x b     a desigualdade 1 n T T j j j u a x u b        é válida para X pois u  0  a desigualdade 1 n T T j j j u a x u b            é válida para X pois x é inteiro e, portanto 1 n T j j j u a x       é inteiro 17 Programação Linear Inteira – Métodos e Algoritmos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 9 of 14 Corte de Gomory Seja um problema de programação inteira     max | , T n z c x Ax b x Z      e sua relaxação linear     0 max | , T n z c x Ax b x R      Considere a solução ótima de  0  , em que B x representa o vetor de variáveis básicas e R x o vetor de variáveis não básicas. Então podemos reescrever  0  , considerando a base da solução ótima, como: 1 1 1 ˆ ˆ . : T T B R R B R B n Max z z c B R c x s a x B Rx B b x x R                onde, considerando ser a solução ótima para  0  , ˆ 0 B x  e 1 0 T T B R c B R c    . Se a solução em questão não satisfaz as restrições de integridade, então, para alguma linha do sistema de equações tem-se:   1 1 ˆ ˆ ˆ , ˆ ˆ i i i i i j i T B R B B i R B n m B ij R B j x B i R x x x a x x x a x x             com ˆ iB x não inteiro, para algum 1,..., i m  . O corte de Chavátal-Gomory para esta linha i é: 1 ˆ ˆ i j i n m B ij R B j x a x x              Subtraindo desta expressão a anterior, tem-se:   1 1 1 ˆ ˆ ˆ ˆ ˆ ˆ ˆ ˆ i j i j i i j i i n m n m B ij R B ij R B B j j n m ij ij R B B j x a x x a x x x a a x x x                                  Esta última inequação é, então, acrescida ao problema  r  , dando origem ao problema linear  r 1    . A nova solução deste problema poderá ser obtida com a realização de (poucas) iterações duais. 17 Programação Linear Inteira – Métodos e Algoritmos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 10 of 14 Algoritmo de Gomory P1 Inicialização. Construa  0  . Faça r  0 . P2 Reotimização. Resolva  r  usando o método simplex primal-dual. P3 Otimalidade. Se a solução é inteira, então PARE com sucesso: a solução ótima de    foi encontrada. P4 Escolha uma linha i com ˆ iB x não inteiro. Construa o correspondente corte de Gomory e insira-o no problema  r  , formando  r 1    . Faça 1 r  r  e volte ao Step 2. 17 Programação Linear Inteira – Métodos e Algoritmos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 11 of 14 Exemplo numérico Seja o problema de programação linear inteira: 1 2 1 2 1 1 2 2 1 2 1 2 5 . : 7 5 13 3 2 17 , , , Max z x x s a x x S x x S x x S S Z          Resolvendo o problema relaxado, tem-se: Z X1 X2 S1 S2 RHS X1 0,0000 1,0000 0,0000 0,0690 0,1724 3,8276 X2 0,0000 0,0000 1,0000 -0,1034 0,2414 2,7586 Z 1,0000 0,0000 0,0000 0,4483 0,6207 16,3793 Considerando que esta solução não é inteira, e escolhendo a linha de 1x para construção do corte de Gomory: 1 2 1 2 3 0,0690 0,1724 0,8276 0,0690 0,1724 0,8276 S S S S S      Incluindo esta equação no problema, obtém-se: 17 Programação Linear Inteira – Métodos e Algoritmos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 12 of 14 Z X1 X2 S1 S2 S3 RHS X1 0,0000 1,0000 0,0000 0,0690 0,1724 0,0000 3,8276 X2 0,0000 0,0000 1,0000 -0,1034 0,2414 0,0000 2,7586 S3 0,0000 0,0000 0,0000 -0,0690 -0,1724 1,0000 -0,8276 ◄ Z 1,0000 0,0000 0,0000 0,4483 0,6207 0,0000 16,3793 ▲ E, aplicando uma iteração dual: Z X1 X2 S1 S2 S3 RHS X1 0,0000 1,0000 0,0000 0,0000 0,0000 1,0000 3,0000 X2 0,0000 0,0000 1,0000 -0,2000 0,0000 1,4000 1,6000 S2 0,0000 0,0000 0,0000 0,4000 1,0000 -5,8000 4,8000 Z 1,0000 0,0000 0,0000 0,2000 0,0000 3,6000 13,4000 Considerando ser esta uma solução não inteira, e escolhendo a linha de 2 S , obtém-se o segundo corte de Gomory: 1 3 1 3 4 0,4 0,2 0,8 0,4 0,2 0,8 S S S S S      Incluindo esta equação no problema, obtém-se: 17 Programação Linear Inteira – Métodos e Algoritmos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 13 of 14 Z X1 X2 S1 S2 S3 S4 RHS X1 0,0000 1,0000 0,0000 0,0000 0,0000 1,0000 0,0000 3,0000 X2 0,0000 0,0000 1,0000 -0,2000 0,0000 1,4000 0,0000 1,6000 S2 0,0000 0,0000 0,0000 0,4000 1,0000 -5,8000 0,0000 4,8000 S4 0,0000 0,0000 0,0000 -0,4000 0,0000 -0,2000 1,0000 -0,8000 ◄ Z 1,0000 0,0000 0,0000 0,2000 0,0000 3,6000 0,0000 13,4000 ▲ E, aplicando a iteração dual: Z X1 X2 S1 S2 S3 S4 RHS X1 0,0000 1,0000 0,0000 0,0000 0,0000 1,0000 0,0000 3,0000 X2 0,0000 0,0000 1,0000 0,0000 0,0000 1,5000 -0,5000 2,0000 S2 0,0000 0,0000 0,0000 0,0000 1,0000 -6,0000 1,0000 4,0000 S1 0,0000 0,0000 0,0000 1,0000 0,0000 0,5000 -2,5000 2,0000 Z 1,0000 0,0000 0,0000 0,0000 0,0000 3,5000 0,5000 13,0000 Considerando que esta solução é inteira, foi determinada a solução ótima do propblema inicialmente proposto. Variável Valor 1x 3,00 2x 2,00 1S 2,00 2 S 4,00 z 13,00 17 Programação Linear Inteira – Métodos e Algoritmos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 14 of 14 F I M (© 2020 Prof. Sérgio Mayerle)