Lista - Pesquisa Operacional 2 2022-2

UNIVERSIDADE FEDERAL DE SÃO CARLOS Campus Sorocaba Rod. João Leme dos Santos (SP-264), Km 110 Bairro Itinga CEP 18052-780 – Sorocaba SP Fone: (55) 15 3229-7426 PESQUISA OPERACIONAL 2 – SAC LISTA DE EXERCÍCIOS 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. 3𝑥1 + 4𝑥2 ≤ 12 ou 5𝑥1 + 2𝑥2 ≤ 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. a) Analise se a formulação a seguir é uma alternativa para representar a mesma condição. ∑ 𝑎𝑖𝑗𝑥𝑗 = 𝑏𝑖𝑘𝑦𝑘 ∀ 𝑖, 𝑘 𝑗 b) Neste caso, a restrição abaixo ainda seria necessária? Justifique sua resposta estendendo as equações para explicar as duas formulações. ∑ 𝑦𝑘 = 1 𝑁 𝑘=1 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) b) 4. Considere o seguinte problema linear inteiro: 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 + 𝑥2 −2𝑥1 + 2𝑥2 ≤ 3 7𝑥1 + 3𝑥2 ≤ 22 𝑥1, 𝑥2 ∈ 𝑍+ 2 𝑧 = 𝑚𝑎𝑥 3𝑥1 + 7𝑥2 𝑥1 ≤ 3,5 5𝑥1 − 4𝑥2 ≤ 10 4 7 𝑥1 + 2𝑥2 ≤ 9 𝑥1, 𝑥2 ∈ 𝑍+ 2 𝑧 = 𝑚𝑎𝑥 8𝑥1 + 14𝑥2 + 4𝑥3 + 18𝑥4 7𝑥1 + 12𝑥2 + 4𝑥3 + 15𝑥4 ≤ 37 𝑥1, 𝑥2, 𝑥3, 𝑥4 ∈ {0; 1} UNIVERSIDADE FEDERAL DE SÃO CARLOS Campus Sorocaba Rod. João Leme dos Santos (SP-264), Km 110 Bairro Itinga CEP 18052-780 – Sorocaba SP Fone: (55) 15 3229-7426 5. Considere o seguinte problema linear inteiro: 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? 𝑧 = 𝑚𝑎𝑥 10𝑥1 + 15𝑥2 + 36𝑥3 + 20𝑥4 + 15𝑥5 + 18𝑥6 + 20𝑥7 10𝑥1 + 17𝑥2 + 49𝑥3 + 30𝑥4 + 11𝑥5 + 21𝑥6 + 31𝑥7 ≤ 100 𝑥1, 𝑥2, 𝑥3, 𝑥4, 𝑥5, 𝑥6, 𝑥7 ∈ {0; 1}