Lista 2 - Método Simplex - 2023-1

UNIVERSIDADE FEDERAL DE OURO PRETO DEENP – ICEA – GRADUAÇÃO EM ENG A. DE PRODUÇÃO 2023/1 – ENP-153 : Programação Linear Segunda Lista de Exercícios de Programação Linear: Método Simplex, Teoria da Dualidade, Princípio de Decomposição de Dantzig-Wolfe Parte Ia: Programação Linear – Algoritmo SIMPLEX Questão 1: Seja o problema abaixo, onde se lê os estados inicial e final do algoritmo SIMPLEX nas tabela2 1 e 2: Pergunta-se: (a) Considerando o que o algoritmo SIMPLEX é sempre escrito para minimização, isto é, que custos reduzidos positivos indicam potencial de melhora a partir da base corrente, porque se pode afirmar que a tabela 2 é ótima? (b) Escreva as condições de complementariadade de folgas para o problema. Sabendo os valores ótimos para as variáveis primais x, é possível calcular os valores ótimos das variaveis duais u? Como? É possível ler diretamente os valores ótimos das variáveis duais na tabela 2? Onde? Porquê? (c) Baseando-se na ideia de que restrições folgadas correspondem a variáveis duais nulas na solução ótima, qual restrição está folgada? É possível ler isso diretamente na tabela? (d) Quanto o preço do produto 3 precisaria subir para que o mesmo estivesse no mix de produção ótimo? Qual é o custo de produção desse ítem? (e) E se tentassemos considerar um produto 4, tal que a4 = [3 2 1] T? Ele seria economicamente viável a partir de qual preço de mercado? (f) Em caso de choque de demanda, qual seria o valor de demanda máxima para centenas de caixas de copos de 6 oz. que alteraria a solução corrente? E no cenário oposto, qual seria o impacto se a demanda total por copos de 6 oz aumentasse de 8 para 14 centenas de caixas? Onde investir para ganhar mais? (g) Qual seria o significado de obter um custo reduzido de uma variável não-básica igual a zero? Questão 2: Considerando o Programa Linear dado abaixo: Seja ainda a solução x = [3, 9/2, 0, 1, 3/2], cujo valor de x0 é 36. Responda: (a) Esta solução é ótima? (b) Esta solução é é básica? Questão 3: Dado o programa linear abaixo, prove que o espaço de soluções do mesmo é não vazio e que todas as suas variáveis x são limitadas superiormente. Parte Ib – Teoria da Dualidade em Programação Linear: Questão 1: Seja um Programa Linear (PL) P, genérico, escrito em forma canônica: Aplique a Teoria da Dualidade ao PL P acima e obtenha as condições de otimalidade para Programação Linear. Questão 2: Partindo do PL P genérico dado na questão 1, prove que o dual do dual de P é o próprio P. Questão 3: Sabendo-se que o estado de uma restrição Dual de um PL genérico P é ‘folgado’, qual será o valor da variável Primal correspondente? Sabendo-se que o estado de uma variável Dual é ‘não-básica’ o que se pode afirmar sobre o valor da variável de folga da restrição Primal correspondente? Parte Ic - Produzindo o Programa Linear Dual: Questão 1: Sejam as formulações dadas abaixo. Produza os programas duais de suas relaxações de PL: (a) Facility Location Problem (Considere a Relaxação Linear): (b) Problema de Transbordo: (c) Problema de Atribuição: (d) Problema de Fluxo Máximo: (e) Problema de Caminho Mínimo: (f) Problema de Atribuição Generalizado: (g) Problema de Projeto de Redes com Carga Fixa: Parte II: Otimização de Grande Escala e Princípio de Decomposição Questão 1: Obtendo as formas algébricas do Programa Mestre de Dantzig-Wolfe e o do Subproblema Gerador de Collunas (a) Seja o problema de “Lot-Sizing” Capacitado Multiproduto: Considerando as restrições (2.9) como complicantes, produza o Programa-Mestre de Dantzig-Wolfe e o Subproblema Gerador de Colunas para (2.6)-(2.10) (b) Para a formulação de Localização de Hubs abaixo, considerando as restrições (3) como complicantes, repita o procedimento da questão (a): Questão 2: (a) Seja o PL de estrutura bloco-diagonal generalizado dado a seguir. Produza as expressões do Programa Mestre e do Subproblema de Dantzig-Wolfe para o Mesmo: (b) Faça o mesmo para os problemas dados a seguir: (i) (ii) (iii) Instruções de Execução: Ao trabalhar a lista de exercícios, o estudante precisa ter em mente que ele deve comprender a solução dos exercícios com profundidade. Somente assim estaremos habilitados a confecção tranquila dos TP’s. Auf Wiedersehen, Senhores!!!