Lista - Método de Branch-and-bound bb - 2023-2

Universidade Estadual De Campinas Faculdade De Ciˆencias Aplicadas Lista 2: M´etodo branch-and-bound (B&B) Professor: Dr. Diego Jacinto Fiorotto Curso de Engenharia de Produc¸˜ao Disciplina: LE611 - Pesquisa operacional II 1. Responda `as seguintes perguntas, justificando. (a) Se a relaxac¸˜ao linear de um problema de programac¸˜ao inteira possui soluc¸˜ao ´otima, podemos afirmar que o problema de programac¸˜ao inteira tamb´em possui soluc¸˜ao ´otima? (b) Se a relaxac¸˜ao linear de um problema de programac¸˜ao inteira ´e infact´ıvel, podemos afirmar que o problema tamb´em ´e infact´ıvel? (c) Se um problema de programac¸˜ao inteira ´e infact´ıvel, podemos afirmar que sua relaxac¸˜ao linear tamb´em ´e infact´ıvel? (d) Se a relaxac¸˜ao linear de um problema de programac¸˜ao inteira possui infinitas soluc¸˜oes ´otimas, podemos afirmar que o problema de programac¸˜ao inteira tamb´em possui infinitas soluc¸˜oes ´otimas? (e) Se a relaxac¸˜ao linear de um problema de programac¸˜ao inteira ´e ilimitada, podemos afirmar que o problema de programac¸˜ao inteira tamb´em ´e ilimitado? (f) Ao aplicar o m´etodo branch-and-bound a um problema de minimizac¸˜ao, como obtemos limitantes inferiores e superiores? 2. Vocˆe tem 1800 g de um determinado f´armaco para fabricar c´apsulas: tipo A e tipo B. O tipo A requer 40 g do f´armaco e o tipo B 30 g. A quantidade de produc¸˜ao de capsulas tipo A deve ser menor ou igual ao dobro da produc¸˜ao de capsulas do tipo B. Cada c´apsula tipo A proporciona um benef´ıcio de R$ 2 e o tipo B R$ 1. Quantas unidades de c´apsulas de cada tipo devem ser fabricadas para que o benef´ıcio seja m´aximo? (a) Elabore o modelo de otimizac¸˜ao para auxiliar na toma de decis˜ao (b) Resolva o problema de programac¸˜ao inteira pelo m´etodo gr´afico. (c) Resolva o problema de programac¸˜ao inteira pelo m´etodo branch-and-bound de acordo com o seguinte: • Para a ordem de processamento dos n´os, use busca em largura. • Para resolver cada n´o (relaxac¸˜ao linear), utilize o m´etodo simplex por tabelas. • Para a selec¸˜ao da vari´avel a ser ramificada, utilize a regra da vari´avel mais fracion´aria. (d) A Figura 1 mostra a ´arvore de ramificac¸˜ao realizada pela busca em profundidade. Com base na figura, responda: • Justifique sob que crit´erio os n´os 2, 4, 6, 8, 10 e 11 foram podados. • Apresente uma soluc¸˜ao incumbente, em que n´o foi encontrada? • A soluc¸˜ao ´otima do problema foi encontrada? Em qual n´o? • Identifique as restric¸˜oes adicionadas para o subproblema do n´o 9, realize a relaxac¸˜ao linear usando o m´etodo gr´afico para este subproblema e fornec¸a uma soluc¸˜ao arredondada. Essa soluc¸˜ao ´e fact´ıvel? ´E ´otima? 1 Universidade Estadual De Campinas Faculdade De Ciˆencias Aplicadas Figura 1 3. Resolva os problemas de programac¸˜ao inteira: Min F(x1, x2) = 4x1 + 6x2 2x1 + 4x2 ≥ 6 4x1 + 3x2 ≥ 7 2 x1, x2 ∈ Z+ Max F(x1, x2) = x1 + x2 −2x1 + 2x2 ≤ 3 7x1 + 3x2 ≤ 22 x1, x2 ∈ Z+ (a) De forma gr´afica (b) Pelo branch-and-bound, utilizando duas estrategias de escolha de n´o: por profundidade e por largura 2