Avaliação 7 - Branch e Bound - Otimização 2023-2

Avalia¸c˜ao 7 - Branch & Bound 1. Quest˜ao 1 [7 pontos] (P) : Minimizar −3x1 − 2x2 sujeito a 2x1 + 5x2 ≤ 9 4x1 + 2x2 ≤ 9 x1 e x2 ≥ 0 x1 e x2 ∈ Z Resolva o PPLI acima utilizando o m´etodo Branch & Bound, contemplando as instru¸c˜oes a seguir. • Desenhe a ´arvore B&B gerada, e sobre ela sempre fa¸ca: (A) Numere cada n´o da ´arvore de acordo com a ordem que for resolvendo os problemas. (B) Indique em cada aresta da ´arvore qual foi a restri¸c˜ao “acrescentada” ao problema seguinte. (C) Quando um n´o for podado, coloque uma letra ao lado do dele para indicar se a poda ´e por infactibilidade (I), otimalidade (O) ou qualidade (Q). (D) Em cada n´o, indique o valor de z∗, que ´e a imagem ´otima obtida ao resolver o PPLI relaxado associado ao n´o. Os valores ´otimos de todas as vari´aveis devem ser listados/anotados logo ap´os o desenho ´arvore B&B. • Ao resolver o PPLI original relaxado (primeiro n´o): (E) Execute o m´etodo simplex at´e encontrar a solu¸c˜ao ´otima. Caso haja necessidade, pode executar o m´etodo das duas fases. (F) Exiba todas as tabelas intermedi´arias, indicando qual vari´avel entra e qual vari´avel sai da base. (G) Ao final, n˜ao deixe de exibir o valor ´otimo de cada vari´avel, assim como o valor da imagem ´otima. A tabela ´otima dever´a servir de base para as contas futuras (caso a solu¸c˜ao ´otima n˜ao seja totalmente inteira). • Ao resolver o PPLI relaxado dos demais n´os: (H) Na tabela ´otima do n´o do n´ıvel anterior (n´o que o gerou), acrescente a restri¸c˜ao indicada na aresta que os conecta. Atualize os valores de forma a ter uma tabela adequada para as vari´aveis listadas como b´asicas e encontre o novo ´otimo utilizando o m´etodo dual simplex. (I) Exiba todas as tabelas intermedi´arias, indicando qual vari´avel sai e qual vari´avel entra na base. (J) Ao final, n˜ao deixe de exibir o valor ´otimo de cada vari´avel, assim como o valor da imagem ´otima. A tabela ´otima poder´a servir de base para as contas futuras (caso a solu¸c˜ao ´otima n˜ao seja totalmente inteira). ********* IMPORTANTE: ********* (K) Para determinar a ordem de resolu¸c˜ao dos n´os, fa¸ca a resolu¸c˜ao utilizando busca em largura. (L) Se mais de uma vari´avel ´otima original n˜ao for inteira, ramifique utilizando a vari´avel orignal cujo res´ıduo (valor ap´os a v´ırgula) ´e mais pr´oximo de 0, 5. (M) Se, ap´os resolver todos os PPLIs relaxados de duas camadas de n´ıveis (n´o inicial, n´os filhos e n´os netos), vocˆe ainda n˜ao tiver encontrado a solu¸c˜ao ´otima, interrompa a execu¸c˜ao e exiba a melhor solu¸c˜ao inteira (se tiver alguma). 2. Quest˜ao 2 [3 pontos] Nesta quest˜ao, considere um Problema de Programa¸c˜ao Linear de minimiza¸c˜ao, com todas as vari´aveis inteiras, o qual chamaremos de “PPLI original”. Suponha que ele est´a sendo resolvido utilizando o m´etodo Branch & Bound; a ´arvore B&B obtida at´e o momento ´e exibida a seguir: onde, em cada n´o, o primeiro n´umero indica a ordem de resolu¸c˜ao do PPLI relaxado e a segunda informa¸c˜ao (z∗) ´e o valor da imagem ´otima obtida. IMPORTANTE: A ´arvore acima pode j´a estar completamente pronta ou ainda estar em constru¸c˜ao. Considerando as informa¸c˜oes presentes na ´arvore B&B e tamb´em que somente os n´os 5 e 20 possuem solu¸c˜ao inteira (x∗ ∈ Zn), responda/fa¸ca: (A) Indique o primeiro valor do limite inferior para o valor da imagem ´otima do PPLI original, assim como valores de todas as suas atualiza¸c˜oes ao longo da constru¸c˜ao da ´arvore. (B) Indique o primeiro valor do limite superior para o valor da imagem ´otima do PPLI original, assim como valores de todas as suas atualiza¸c˜oes ao longo da constru¸c˜ao da ´arvore. (C) Indique os n´os que j´a foram podados e por qual raz˜ao foram (infactibilidade, otimalidade ou qualidade). (D) Indique quais n´os ainda devem ser ramificados. (E) J´a foi obtida a solu¸c˜ao ´otima do PPLI original? Em todos os itens anteriores, sempre apresente uma breve justificativa.