Slide - Algoritmo de Branch And Bound - 2024-1

PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) Na PI, como o próprio nome sugere, as variáveis são inteiras. Um problema de programação linear mista possui variáveis inteiras e reais. Quando as variáveis assumem os valores zero ou 1, tem-se um problema de programação 0-1 ou binária. Os PPI ampliam enormemente a variedade de situações em que modelos de PL podem ser aplicados como, por exemplo, modelos de localização, alocação de pessoal, decisões do tipo sim ou não, e outros. Uma primeira aproximação do Problema de Programação Linear Inteira (PPLI) é obtida resolvendo-se o PPL, ignorando-se o requisito de valores inteiros. Se a solução ótima do PPL for inteira, então esta é também a solução ótima do PPI. Caso contrário, pode-se arredondar a solução da primeira aproximação aos valores inteiros mais próximos (não recomendado) ou usar um método formal como, por exemplo, os métodos de branch and bound e corte. EXEMPLO 1: RESOLVER O PPLI: Max z = 10x1 + 6x2 s.a. r1: 9x1+ 5x2 <= 45 r2: -4x1 + 5x2 <= 5 r3: x1,x2 >= 0 e inteiras. SOLUÇÃO GRÁFICA: PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) CONJUNTO DE SOLUÇÕES FACTÍVEIS 9 -5/4 PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) SOLUÇÃO EXEMPLO 1: A SOLUÇÃO ÓTIMA DO PPLI É O PONTO (5, 0), COM z = 50. ENQUANTO O z DA SOLUÇÃO ARREDONDADA (3,3) É 48. PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) ALGORITMO DE BRANCH AND BOUND Se a primeira aproximação de um PPI contém uma variável não inteira, por exemplo, xj*, então: i1 < xj < i2, onde i1 e i2 são inteiros consecutivos e não negativos. Dois novos modelos de PPI são criados aumentando o PPI original com a restrição xj <=i1 ou com a restrição xj >=i2. Este procedimento, chamado bifurcação (branch), tem o efeito de contrair a região viável de um modo que elimina de considerações posteriores a solução corrente não inteira para xj preservando todas as soluções inteiras do problema original. Admita-se que a função objetivo deva ser, por exemplo, maximizada. A bifurcação continua até ser obtida uma primeira aproximação inteira, que é uma solução do PPI. O valor da função objetivo referente a esta primeira aproximação inteira torna-se um limite (bound) inferior para o problema e, todos os modelos, cujas primeiras aproximações, inteiras ou não, conduzem a valores da função objetivo menores do que o limite inferior, são descartados. PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) EXEMPLO 2. ALGORITMO DE BRANCH AND BOUND. Uma companhia de mobília produz mesas e cadeiras como parte de sua linha de móveis de jardim. A tabela abaixo mostra os recursos consumidos e os lucros de cada produto. Por simplicidade, assumiremos que somente 2 recursos são consumidos para produzir os móveis de jardim: madeira (310 metros de placa em estoque) e trabalho (113 horas disponíveis). O proprietário deseja determinar quantas mesas e cadeiras deveriam ser feitas para maximizar os lucros. Recurso\un. Mesa Cadeira Qtde. disponível Madeira(m de placa) 30 20 310 Trabalho(horas) 5 10 113 Lucro($) 6 8 PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) SOLUÇÃO EXEMPLO 2. X1 = QUANTIDADE DE MESAS PRODUZIDAS. X2 = QUANTIDADE DE CADEIRAS PRODUZIDAS. P1 MAX z = 6X1 + 8X2 S.A. (1) 30X1 + 20X2 <= 310 (2) 5X1 + 10X2 <= 113 X1,X2>=0 OBS.: INCLUINDO EM P1 A RESTRIÇÃO DE VARIÁVEIS INTEIRAS PARA X1 E X2, TEM-SE UM MODELO PARA O PROBLEMA DO EXEMPLO 2. 31/3 31/2 X2 (2) (1) 113/10 113/5 X1 4,2 4 5 SOLUÇÃO DE P1: (4,2; 9,2) E z= 98,8. RAMIFICANDO X1 (X1=4,2), OBTEMOS DOIS NOVOS PROBLEMAS: P2 E P3. P2 (X1<=4) P3 (X1>=5) 9,2 PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) P2 MAX z = 6X1 + 8X2 S.A. (1) 30X1 + 20X2 <= 310 (2) 5X1 + 10X2 <= 113 (3) X1 <=4 X1,X2>=0 SOLUÇÃO DE P2: (4;9,3) E z = 98,4. SOLUÇÃO EXEMPLO 2. 31/3 31/2 X2 (2) (1) 113/10 113/5 X1 4,2 4 5 Entre os 4 vértices da região viável de P2, o vértice A(4; 9,3) apresenta o maior valor para z, sendo então, a solução ótima de P2. P2 (X1<=4) P3 (X1>=5) 9,2 A 9,3 PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) P3 MAX z = 6X1 + 8X2 S.A. (1) 30X1 + 20X2 <= 310 (2) 5X1 + 10X2 <= 113 (3) X1 >=5 X1,X2>=0 SOLUÇÃO DE P3: (5;8) E z= 94. (1º BOUND – solução inteira) SOLUÇÃO EXEMPLO 2. SOLUÇÃO EXEMPLO 2. 31/3 31/2 X2 (2) (1) 113/10 113/5 X1 4,2 4 5 Entre os 3 vértices da região viável de P3, o vértice B(5; 8) apresenta o maior valor para z, sendo então, a solução ótima de P3. P2 (X1<=4) P3 (X1>=5) 9,2 A 9,3 B PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) SOLUÇÃO EXEMPLO 2. 31/3 31/2 X2 (2) (1) 113/10 113/5 X1 4,2 4 5 P4 (X2>=10) P5 (X2<=9) RAMIFICANDO X2 = 9,3 NO PROBLEMA P2, OBTEMOS OS PROBLEMAS P4 E P5. 9,3 9 10 P4 MAX z = 6X1 + 8X2 S.A. (1) 30X1 + 20X2 <= 310 (2) 5X1 + 10X2 <= 113 (3) X1 <=4 (4) X2>= 10 X1,X2>=0 SOLUÇÃO DE P4: (2,6;10) E z = 95,6 . PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) SOLUÇÃO EXEMPLO 2. 31/3 31/2 X2 (2) (1) 113/10 113/5 X1 4,2 4 5 P4 (X2>=10) P5 (X2<=9) 9,3 9 10 Entre os 3 vértices da região viável de P4, o vértice C(2,6; 10) apresenta o maior valor para z, sendo então, a solução ótima de P4. C PROGRAMAÇÃO INTEIRA (PI) P5 MAX z = 6X1 + 8X2 S.A. (1) 30X1 + 20X2 <= 310 (2) 5X1 + 10X2 <= 113 (3) X1 <=4 (4) X2<= 9 X1,X2>=0 SOLUÇÃO DE P5: (4;9) E z = 96. (2º BOUND – sol int) Problemas obtidos com a ramificação de X1=2,6 no problema P4 não terão z superior a 95,6 (z ótimo em P4). Portanto, o 2º BOUND (P5) é a solução ótima do PPL do exemplo 2. SOLUÇÃO EXEMPLO 2. 31/3 31/2 X2 (2) (1) 113/10 113/5 X1 4,2 4 5 P4 (X2>=10) P5 (X2<=9) 9,3 9 10 Entre os 4 vértices da região viável de P5, o vértice D(4; 9) apresenta o maior valor para z, sendo então, a solução ótima de P5. C PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA D PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) EXEMPLO 2. ÁRVORE DE SOLUÇÕES P1: X1=4,2; X2=9,2 e z = 98,8 P2: X1=4; X2=9,3 e z = 98,4 P3: X1=5; X2=8 e z = 94 P4: X1=2,6; X2=10 e z = 95,6 P5: X1=4; X2=9 e z = 96 X1<=4 X1>=5 X2>=10 X2<=9 (1º BOUND) (2º BOUND) – SOLUÇÃO ÓTIMA. PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) EXEMPLO 3. USE O ALGORITMO DE BRANCH AND BOUND PARA RESOLVER O SEGUINTE PPLI: (SOLUÇÃO GRÁFICA) Max z = 5x1 + 4x2 s.a (1) x1 + x2 <=5 (2) 10x1 + 6x2 < = 45 x1, x2 >=0 e inteiras. (1) (2) 5 5 4,5 45/6 SOLUÇÃO DE P1: MAX z; S.A. (1); (2) E x1,x2>=0. x1=3,75; x2=1,25 e z = 23,75. RAMIFICANDO x2, OBTEMOS OS PROBLEMAS P2 E P3 P3 (x2>=2) P2 (x2<=1) 2 1 1,25 Solução ótima de P1 (problema relaxado) C B PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) SOLUÇÃO DE P2 Max z = 5x1 + 4x2 s.a (1) x1 + x2 <=5 (2) 10x1 + 6x2 < = 45 (3) x2 <= 1 x1, x2 >=0 SOLUÇÃO DE P3 Max z = 5x1 + 4x2 s.a (1) x1 + x2 <=5 (2) 10x1 + 6x2 < = 45 (3) x2 >= 2 x1, x2 >=0 SOLUÇÃO EXEMPLO 3. Entre os 4 vértices da região viável de P2, o vértice B(3,9; 1) apresenta o maior valor para z, sendo então, a solução ótima de P2. x1=3,9; x2=1 e z=23,5. Problemas obtidos com a ramificação de x1=3,9 não terão solução inteira com z superior a 23. Portanto, a sol de P3 é ótima Entre os 3 vértices da região viável de P3, o vértice C(3; 2) apresenta o maior valor para z, sendo então, a solução ótima de P3. x1=3; x2=2 e z=23 (1º BOUND) SOLUÇÃO ÓTIMA EXEMPLO 4. A fábrica de acolchoados da Zeni acabou de acertar um contrato com a Prefeitura para participar da tradicional feira de outubro. Como nesta feira sempre vende tudo o que leva, a Zeni decidiu produzir o máximo, utilizando todo o estoque pois não conseguirá receber novo suprimento de matéria-prima até o final da feira. Produz três tamanhos de acolchoados: o normal, o grande e o extra- grande. O lucro para o normal é de R$ 3; o do grande é R$ 6; e para o extra-grande é de R$ 10. O estoque de tecido é de 30.000 metros e de lã é de 50.000 metros. Também disporá de 2.400 horas de trabalho, juntando toda sua equipe de costureiras. As necessidades de cada recurso por tipo de acolchoado estão no quadro a seguir: PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) EXEMPLO 4. Necessidade por acolchoado Tamanho Horas-Homem Metros de tecido Metros de lã Normal 4 10 15 Grande 6 12 20 Extra-Grande 9 14 21 A Zeni pretende maximizar o lucro. Resolva o PPLI utilizando o LINGO ou Excel para resolver os PPL oriundos do algoritmo branch and bound PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) SOLUÇÃO EXEMPLO 5. MODELO LINEAR. X1, X2,X3 = QUANTIDADE DOS ACOLCHOADOS NORMAL, GRANDE E EXTRA-GRANDE, RESPECTIVAMENTE. P1: MAX Z= 3X1+6X2+10X3 S.A. 4X1+6X2+9X3<=2400 10X1+12X2+14X3<=30000 15X1+20X2+21X3<=50000 X1,X2,X3>=0 E INTEIRAS. CONSIDERANDO A RELAXAÇÃO LINEAR EM P1, ENCONTRA-SE A SEGUINTE SOLUÇÃO ÓTIMA: X1=X2=0; X3=266,6 E z -= 2666,6. RAMIFICANDO X3, OBTEMOS OS PROBLEMA P2 (X3<266) E P3(X3>267). P3 É INVIÁVEL. SOLUÇÃO DE P2 É: X1=0; X2=1; X3=266 E z = 2666 (1º BOUND) SOLUÇÃO ÓPTIMA (EXEMPLO 2) PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) EXEMPLO 6. DADO O PPLI: Max z = 10x1 + 6x2 s.a. r1: 9x1+ 5x2 <= 45 r2: -4x1 + 5x2 <= 5 r3: x1,x2 >= 0 e inteiras. APLIQUE O ALGORITMO DE BRANCH AND BOUND E MONTE A ÁRVORE DE SOLUÇÕES. Utilize LINGO ou Excel para resolver os PPL oriundos do algoritmo branch and bound PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) SOLUÇÃO EXEMPLO 6. ÁRVORE DE SOLUÇÕES P1: X1=3,07; X2=3,46 e z = 51,5 P4: X1=3; X2=3 e z =48 1º BOUND P5: INVIÁVEL P6: X1=4,4; X2=1 e z=50,4. P7: INVIÁVEL P2: X1=3; X2=3,4 e z = 50,4 P3: X1=4; X2=1,8 e z = 50,8 P8: X1=4; X2=1 e z = 46. 2º BOUND P9: X1=5; X2=0 e z = 50. 3º BOUND. SOLUÇÃO ÓTIMA X1<=3 X1>=4 X2<=3 X2>=4 X2<=1 X2>=2 X1<=4 X1>=5