Exercícios - Branch-and-bound - Pesquisa Operacional 2 2022 2

3. Resolva os seguintes problemas abaixo pelo método Branch-and-Bound, utilizando o método gráfico para resolver os subproblemas de relaxação linear e faça a árvore B&B correspondente. a) z = max x1 + x2 -2x1 + 2x2 ≤ 3 7x1 + 3x2 ≤ 22 x1, x2 ∈ Z² b) z = max 3x1 + 7x2 x1 ≤ 3,5 5x1 - 4x2 ≤ 10 4/7 x1 + x2 ≤ 9 x1, x2 ∈ Z² 4. Considere o seguinte problema linear inteiro: z = max 8x1 + 14x2 + 4x3 + 18x4 7x1 + 12x2 + 4x3 + 15x4 ≤ 37 x1, x2, x3, x4 ∈ {0, 1} a) Resolva o problema pelo método Branch-and-Bound, utilizando o método analítico para resolver os subproblemas de relaxação linear. Resolva utilizando planilhas para fazer os cálculos ou faça as contas manualmente e coloque os valores em tabela. b) Faça a árvore Branch-and-Bound equivalente. c) Considerando a resolução deste exercício, indique em quais nós da árvore são encontradas soluções inteiras. 1. Considere que as duas restrições a seguir são mutuamente exclusivas ou disjuntivas. Reescreva as restrições usando uma variável binária para impor esta condição. 3x1 + 4x2 ≤ 12 ou 5x1 + 2x2 ≤ 10 2. Considere o texto de Alves e Delgado (1997) página 3, que trata sobre a modelagem de funções com N valores possíveis. [Caixa de texto: Restrição j: Σi aijxi = bj1 ou bj2 ou ... bjn] Definem-se as variáveis binárias yk, tais que: N Σ yk = 1, com cada yk ∈ {0, 1} k=1 A restrição será então alterada para Σy aijxij - ΣN bjk yk a) Analise se a formulação a seguir é uma alternativa para representar a mesma condição. Σy aijxij = bjk yk ∀ i, k b) Neste caso, a restrição abaixo ainda seria necessária? Justifique sua resposta estendendo as equações para explicar as duas formulações. N Σ yk = 1 k=1 5. Considere o seguinte problema linear inteiro: z = max 10x1 + 15x2 + 36x3 + 20x4 + 15x5 + 18x6 + 20x7 10x1 + 17x2 + 49x3 + 30x4 + 11x5 + 21x6 + 31x7 ≤ 100 x1, x2, x3, x4, x5, x6, x7 ∈ {0, 1} a) Resolva o problema pelo método Branch-and-Bound, utilizando o método analítico para resolver os subproblemas de relaxação linear. Considere a regra do melhor limitante superior como critério de seleção dos nós. Resolva utilizando planilhas para fazer os cálculos ou faça as contas manualmente e coloque os valores em tabela. b) Faça a árvore Branch-and-Bound equivalente. c) Suponha que o critério de escolha para seleção dos nós seja a busca em largura. Após a segunda etapa de ramificação, qual seria o gap de optimalidade da solução encontrada? 6. Podemos afirmar que o método Branch-and-Bound é um método de enumeração completa? Justifique sua resposta. 7. Como o método Branch-and-Bound prova que uma solução é ótima?