Lista de Exercícios Resolvendo Problemas de Programação Linear Inteira com Branch and Bound

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 2 Resolva o PLI via branch and bound e construa a árvore maximize Z 5x1 4x2 sujeito a 3x14x2 10 x1x2 Z 3 Resolva o PLI via branch and bound maximize Z1000x1 700x2 800x3 sujeito a 5000x1 6000x2 4000x3 10000 x1x2x3 0 1 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 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 5 Considere o problema de programação inteiraPLI 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 UNIVERSIDADE FEDERAL DO PARANÁ DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II PROF VOLMIR EUGÊNIO WILHELM 2 Z 0 0 94 0 72 3158 X1 1 0 1 0 0 72 F2 0 0 6 1 2 7 X2 0 1 14 0 12 298 A solução ótima é Z 34 e X 24 Considerando X23 temos Z 30 e X 3 3 Utilizando as informações dadas faça iterações do método branchandbound para mostrar que X é solução ótima 6 Resolver o problema de programação inteira via Branch and Bound min Z x1 5x2 as 2x1 3x2 10 x1 x2 Z 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 8 Foi utilizado o algoritmo de BranchandBound 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 9 Considere um problema de maximização exclusivamente com variáveis inteiras Resolvendo o problema através de BranchandBound obtémse num dado estágio a seguinte árvore UNIVERSIDADE FEDERAL DO PARANÁ DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II PROF VOLMIR EUGÊNIO WILHELM 3 a Qual é nesta altura o melhor limite superior sobre a solução inteira ótima b Qual é nesta altura o melhor limite inferior sobre a solução inteira ótima c Indique que nós já foram explorados e explique porquê d Indique os nós que ainda não foram explorados e explique porquê e Já foi atingida a solução ótima do problema inteiro Por quê f Qual o valor máximo do erro absoluto sobre a solução ótima inteira se o algoritmo for terminado neste ponto 10 Para um problema de maximização foi desenvolvida uma árvore de BranchandBound 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 b Que nós se encontram explorados c Sugira que estratégia poderá ter sido adotada no desenvolvimento da árvore