Exercícios de Branch e Bound Resolvidos-2023 1

UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 1 EXERCÍCIOS DE BRANCH & BOUND 1) Seja o pli e o quadro ótimo associado ao primeiro nó da árvore branch and bound. min Z = 2X1 + X2 sa 4X1 + 3X2  6 3X1 + X2  3 X1 + X2  3 X1, X2 Z+ a) Indique no gráfico todas as soluções viáveis do pli b) Aplique mais duas etapas do algoritmo branch and bound a partir da variável X1 gerando 2 nós da árvore na resolução do pli. X1 = 0 Base X1 X2 E1 E2 F1 F2 b Z 1/5 2/5 -12/5 X2 1 - 3/5 4/5 6/5 X1 1 1/5 - 3/5 3/5 F1 2/5 - 1/5 1 6/5 F2 1 0 0 1 0 Base X1 X2 E1 E2 F1 F2 b Z 1/5 2/5 -12/5 X2 1 - 3/5 4/5 6/5 X1 1 1/5 - 3/5 3/5 F1 2/5 - 1/5 1 6/5 F2 - 1/5 3/5 1 - 3/5 Base X1 X2 E1 E2 F1 F2 b Z 1 1 -3 X2 1 -1 -3 3 X1 1 0 1 0 F1 1 1 2 0 E1 1 -3 -5 3 ^Solução inteira UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 2 X1 >= 1 Base X1 X2 E1 E2 F1 E3 b Z 1/5 2/5 -12/5 X2 1 - 3/5 4/5 6/5 X1 1 1/5 - 3/5 3/5 F1 2/5 - 1/5 1 6/5 E3 -1 0 0 1 -1 Base X1 X2 E1 E2 F1 E3 b Z 1/5 2/5 -12/5 X2 1 - 3/5 4/5 6/5 X1 1 1/5 - 3/5 3/5 F1 2/5 - 1/5 1 6/5 E3 1/5 -3/5 1 -2/5 Base X1 X2 E1 E2 F1 E3 b Z 1/3 2/3 -8/3 X2 1 - 1/3 4/3 2/3 X1 1 0 -1 1 F1 1/3 1 - 1/3 4/3 E2 - 1/3 1 -5/3 2/3 ^Solução não inteira com Z inferior à solução já encontrada 2) Resolva via o PLI via branch and bound e construa a árvore. maximize Z = 5x1 + 4x2 sujeito a 3x1+4x2 ≤ 10 x1,x2 ∈ Z+ Iteração Level Restrição adicionada Solução Z X1 X2 Ótima 15 3 0 1 0 Não inteira 16.65 3.33 0 2 1 X1<= 3 Não inteira 16 3 0.25 3 1 X1>= 4 Inviável 4 2 X2<= 0 INTEIRA 15 3 0 5 2 X2>=1 INTEIRA 14 2 1 3) Resolva o PLI via branch and bound. maximize Z=1000x1+ 700x2 + 800x3 sujeito a 5000x1 + 6000x2 + 4000x3  10000 x1,x2,x3  {0, 1} UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 3 Construa a árvore. Mostre apenas os quadros simplex inicial e final da resolução do PL relaxado (PL 0) e todos os quadros da resolução do 1º nó (PL 1) gerado a partir do PL 0 via introdução da restrição do tipo “” (utilize apenas conceitos de pós otimização para resolver o PL 1) Iteração Level Restrição adicionada Solução Z X1 X2 X3 Ótima 2.000 2 0 0 1 0 Não inteira 2.000 0 0 2,5 2 1 X3<= 2 Não inteira 2.000 0,4 0 2 3 1 X3>= 3 Inviável 4 2 X1=0 Não inteira 1.833,33 0 0,333 2 5 2 X1>= 1 Não inteira 2.000 1 0 1,25 6 3 X2=0 INTEIRA 1.600 0 0 2 7 3 X2>=1 INTEIRA 1.500 0 1 1 8 3 x3<=1 Não inteira 2.000 1,2 0 1 9 3 X3=2 Inviável 10 4 X1=1 Não inteira 1.916,666 1 0,1666 1 11 4 X1>=2 INTEIRA 2.000 2 0 0 4) Considere o seguinte problema de programação inteira. max Z = 3x1 + 17x2 + 10x3 sa 2x1 + 11x2 + 6x3 ≤ 10 x1, x2, x3 ∈ Z+ Resolva o problema usando o método Branch and Bound. Iteração Level Restrição adicionada Solução Z X1 X2 X3 Ótima 16 2 0 1 1 0 Não inteira 16.667 0 0 1.667 2 1 X3<= 1 Não inteira 16.1818 0 0.3636 1 3 1 X2<= 0 INTEIRA 16 2 0 1 4 2 X2>= 1 Inviável 5 2 X3>= 2 Inviável UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 4 5) Considere o problema de programação inteira-PLI max Z = 3X1 + 7X2 s. a 1X1 + 0X2 ≤ 7 2 5X1 − 4X2 ≤ 10 1 2 X1 + 2X2 ≤ 9 X1, X2 ∈ ℤ+ O pl relaxado do PLI é obtido ignorando que as variáveis são inteiras. O quadro ótimo do pl relaxado é Base X1 X2 F1 F2 F3 b Z 0 0 9/4 0 7/2 315/8 X1 1 0 1 0 0 7/2 F2 0 0 -6 1 2 7 X2 0 1 -1/4 0 1/2 29/8 A solução ótima é Z* = 34 e X* = (2,4). Considerando X23, temos Z = 30 e X = (3, 3). Utilizando as informações dadas, faça iterações do método branch-and-bound para mostrar que X* é solução ótima. Iteração Level Restrição adicionada Solução Z X1 X2 Ótima 34 2 4 1 0 Não inteira 39,375 3,5 3,625 2 1 X1<=3 Não inteira 35,25 3 3,75 3 1 X1>=4 Inviável 4 2 X2<=3 INTEIRA 30 3 3 5 2 X2>=4 INTEIRA 34 2 4 6) Resolver o problema de programação inteira via Branch and Bound min Z = x1 - 5x2 as 2x1 + 3x2  10 x1, x2  Z+ Iteração Level Restrição adicionada Solução Z X1 X2 Ótima -15 0 3 1 0 Não inteira -16,666 0 3,333 2 1 X2<=3 INTEIRA -15 0 3 3 1 X2>=4 Inviável UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 5 7) Resolver o problema de programação inteira via Branch and Bound max Z = 2x + 3y sa −x + y ≤ 2 x + y ≤ 5 2x + y ≤ 14 x, y ≥ 0 Iteração Level Restrição adicionada Solução Z X Y Ótima 13 2 3 1 0 Não inteira 13,5 1,5 3,5 2 1 X<=1 Não inteira 11 1 3 3 1 Y>=2 INTEIRA 13 2 3 8) Foi utilizado o algoritmo de “Branch-and-Bound" para resolver um problema de programação inteira (minimização), tendo sido gerados e resolvidos os seguintes subproblemas: Represente a árvore de problemas correspondente a esta resolução, indicando nos ramos a restrição adicionada em cada ramificação, e diga qual é a solução ótima. Árvore: UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 6 Para obtenção da árvore de problemas correspondente aos subproblemas apresentados no enunciado, é nnecessário ter em conta que o valor da função objetivo “piora” à medida que se desce na árvore (tem um maior valor neste caso, dado que se trata de um problema de minimização), dado que a descida na árvore corresponde à introdução de restrições adicionais. A primeira ramificação teve que ser feita em x1, dado que: - em nenhum dos restantes subproblemas existe uma solução com x1 ∈ ]5; 6[ (consequência de se ter imposto x1 ≤ 5 e x1 ≥ 6); - se a ramificação tivesse sido em x2, todos os restantes subproblemas teriam que ter x2 ≤ 2 ou x2 ≥ 3, mas o subproblema G contradiz essa assumpção. 9) Considere um problema de maximização exclusivamente com variáveis inteiras. Resolvendo o problema através de “Branch-and-Bound", obtém-se, num dado estágio, a seguinte árvore: a) Qual é, nesta altura, o melhor limite superior sobre a solução inteira ótima? O melhor limite superior sobre a solução inteira ótima no momento de resolução retratado na árvore é dado pela solução do problema PL5 e é igual a 75. Qualquer solução inteira que surja a partir da exploração desse nó terá um valor da função objetivo ≤ 75 b) Qual é, nesta altura, o melhor limite inferior sobre a solução inteira ótima? Os limites inferiores são dados por valores de soluções admissíveis (variáveis já inteiras) que ainda se desconhece se são ou não ótimas. Neste caso temos já 2 soluções inteiras, para PL6 e para PL4. A que tem o maior valor da função objetivo fornece o melhor limite inferior, 70 neste caso. c) Indique que nós já foram explorados e explique porquê. Já foram explorados os nós PL1, PL2, PL3 e PL7 porque já tem ramos. Os nós PL4 e PL6 já foram explorados porque deram origem a soluções inteiras. UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 7 O nó PL8 já está explorado porque corresponde a um problema sem solução admissível. O nó PL9 já foi explorado porque pode ser cortado. Corresponde a um problema com solução ótima não inteira e com um valor para a função objetivo inferior ao valor da solução inteira do problema PL6. d) Indique os nós que ainda não foram explorados e explique porquê. O nó PL5 ainda não foi explorado, dado que corresponde a um problema com solução ótima não inteira, mas com um valor para a função objetivo superior ao valor da melhor solução inteira obtida até o momento (problema PL6). e) Já foi atingida a solução ótima do problema inteiro? Por quê? Não se sabe ainda se já foi obtida a solução ótima do problema inteiro, porque ainda há nós por explorar (PL5). Só quando os melhores limites inferiores e superiores coincidirem é que se pode afirmar que a melhor solução inteira obtida é a ótima. f) Qual o valor máximo do erro absoluto sobre a solução ótima inteira, se o algoritmo for terminado neste ponto? O valor máximo do erro absoluto sobre a solução ótima inteira, se o algoritmo for terminado neste ponto será 5, isto é, a diferença entre os melhores limites superior e inferior. 10) Para um problema de maximização, foi desenvolvida uma árvore de “Branch-and-Bound" como a representada na figura. Na árvore está representada a ordem de criação dos nós, bem como os limites superiores (majorantes) e inferiores (minorantes), sempre que disponíveis. a) Que informação se pode extrair desta árvore? Pode-se extrair da árvore que: - o melhor limite superior até ao momento é 76 (máximo valor da função objetivo de entre os nós ainda não explorados); - o melhor limite inferior é 49 (valor da função objetivo da melhor solução inteira obtida até ao momento). b) Que nós se encontram explorados? Já foram explorados os nós 0, 1, 2, 3, 4, 5, 10 e 11 porque já têm ramos. Os nós 8 e 14 já foram explorados porque deram origem a soluções inteiras. O nó 7 já está explorado porque corresponde a um problema sem solução admissível. Os nós 6 e 13 já foram explorados porque podem ser cortados. Correspondem a problemas com solução ótima não inteira e com um valor para a função objetivo inferior ao valor da solução inteira do problema do nó 8. c) Sugira que estratégia poderá ter sido adotada no desenvolvimento da árvore. A estratégia adotada no desenvolvimento da árvore foi a de ramificar o nó ainda não explorado e com maior valor de função objetivo.