Avaliação 6 - Planos Cortantes - Otimização 2023-2

Avalia¸c˜ao 6 - Planos Cortantes 1. Quest˜ao 1 [10 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 usando a t´ecnica de planos cortantes, via m´etodo de Gomory- Chv´atal, contemplando as instru¸c˜oes a seguir. • Ao resolver o PPLI original relaxado: (A) Execute o m´etodo simplex at´e encontrar a solu¸c˜ao ´otima. Caso haja necessidade, pode executar o m´etodo das duas fases. (B) Exiba todas as tabelas intermedi´arias, indicando qual vari´avel entra e qual vari´avel sai da base. (C) 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 a sequˆencia de PPLIs relaxados: (D) Partindo da tabela ´otima do ´ultimo problema resolvido, gere a restri¸c˜ao que ser´a respons´avel pelo corte de Gomory-Chv´atal. (E) Na tabela ´otima do ´ultimo problema resolvido, acrescente a restri¸c˜ao gerada. 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. (F) Exiba todas as tabelas intermedi´arias, indicando qual vari´avel sai e qual vari´avel entra na 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 poder´a servir de base para as contas futuras (caso a solu¸c˜ao ´otima n˜ao seja totalmente inteira). ********* IMPORTANTE: ********* (H) Se mais de uma vari´avel ´otima original n˜ao for inteira, gere a restri¸c˜ao utilizando a linha da vari´avel que possui maior res´ıduo (valor ap´os a v´ırgula). (I) Se, ap´os a inser¸c˜ao de trˆes cortes, vocˆe ainda n˜ao tiver encontrado a solu¸c˜ao ´otima, inter- rompa a execu¸c˜ao.