Exercícios - 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 x₁ + x₂ -2x₁ + 2x₂ ≤ 3 7x₁ + 3x₂ ≤ 22 x₁, x₂ ∈ Z⁺² b) z = max 3x₁ + 7x₂ x₁ ≤ 3,5 5x₁ - 4x₂ ≤ 10 4/7x₁ + 2x₂ ≤ 9 x₁, x₂ ∈ Z⁺² 4. Considere o seguinte problema linear inteiro: z = max 8x₁ + 14x₂ + 4x₃ + 18x₄ 7x₁ + 12x₂ + 4x₃ + 15x₄ ≤ 37 x₁, x₂, x₃, x₄ ∈ {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. 3x₁ + 4x₂ ≤ 12 ou 5x₁ + 2x₂ ≤ 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. Definem-se as variáveis binárias yₖ tais que: Σₖ yₖ = 1, com cada yₖ ∈ {0, 1} A restrição será então alterada para Σᵢ aᵢⱼxⱼ = Σₖ bₖ * yₖ a) Analise se a formulação a seguir é uma alternativa para representar a mesma condição. Σᵢ aᵢⱼxⱼ = bₖⱼ yₖ ∀ 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. Σₖ yₖ = 1 3. Considere o seguinte problema linear inteiro: z = max 10x₁ + 15x₂ + 36x₃ + 20x₄ + 15x₅ + 18x₆ + 20x₇ 10x₁ + 17x₂ + 49x₃ + 30x₄ + 11x₅ + 21x₆ + 31x₇ ≤ 100 x₁, x₂, x₃, x₄, x₅, x₆, x₇ ∈ {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 otimalidade 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?