Programação Linear: dualidade e Simplex em Duas Fases

1. Planejamento de produção — maximização

Uma empresa fabrica dois produtos, A e B, com lucros unitários de R$ 150 e R$ 50, respectivamente. A produção de A está limitada a 30 unidades por semana. Cada unidade de qualquer um dos produtos utiliza duas horas de uma máquina, disponível durante 80 horas semanais. Toda a produção pode ser vendida.

1. Defina as variáveis de decisão e construa o modelo de maximização do lucro.
2. Explique por que as restrições possuem sentido “menor ou igual”.
3. Obtenha o modelo dual de minimização.
4. Resolva os dois modelos com o Solver e compare os valores ótimos.

Dados correspondentes à aba Exercicio2-dual.

2. Produção com três recursos — maximização

Uma indústria produz A, B e C. A tabela apresenta o consumo de recursos por unidade produzida.

1. Construa o modelo que maximiza o lucro.
2. Obtenha seu dual de minimização.
3. Resolva o primal com o Solver e determine os recursos totalmente utilizados.
4. Calcule e interprete as folgas dos recursos.

Dados correspondentes à aba Exercicio3-dual.

3. Planejamento de dois produtos — maximização

Uma empresa obtém lucros de R$ 3 e R$ 5 por unidade dos produtos A e B. A produção de A não pode ultrapassar quatro unidades. Cada unidade de B consome duas horas de acabamento, cuja disponibilidade é de 12 horas. Na montagem, A consome três horas por unidade e B consome duas, havendo 18 horas disponíveis.

1. Formule o modelo de maximização.
2. Escreva seu dual de minimização.
3. Resolva ambos com o Solver.
4. Identifique a restrição primal com folga positiva e compare essa folga com o valor da variável dual correspondente.

Dados correspondentes à aba Exercicio4-dual.

4. Dois produtos e três recursos — modelagem e interpretação

Uma fábrica produz P1 e P2, com lucros unitários de R$ 5 e R$ 6. Os consumos e as disponibilidades são:

1. Construa os modelos primal de maximização e dual de minimização.
2. Explique o significado econômico das variáveis duais.
3. Verifique a viabilidade do plano \(x_1=4,\;x_2=5\) e calcule seu lucro e suas folgas.
4. Utilize o Solver para verificar se esse plano é ótimo.

Dados do exemplo de interpretação econômica de cap4.html.

5. Construção do dual — modelo fornecido

Considere:

1. Identifique a matriz \(A\) e os vetores \(b\) e \(c\).
2. Construa o dual, explicitando os domínios das variáveis.
3. Explique a quantidade de variáveis e de restrições estruturais do dual.
4. Resolva os dois modelos com o Solver e confira a igualdade dos valores ótimos.

Modelo do exemplo de construção do dual de cap4.html.

6. Dualidade com restrição de igualdade

Considere:

1. Construa o dual de minimização.
2. Explique o domínio da variável dual associada à igualdade.
3. Represente essa variável como diferença de duas variáveis não negativas.
4. Confira os modelos primal e dual com o Solver, respeitando os domínios definidos.

7. Contratação de serviços — minimização

Uma empresa contratará quantidades de dois serviços, A e B, com custos de R$ 3 e R$ 5 por unidade. Deve contratar pelo menos quatro unidades de A e seis de B. Cada unidade de A fornece três unidades de atendimento, enquanto cada unidade de B fornece duas. O atendimento total deve ser de pelo menos 18 unidades.

1. Construa o modelo de minimização do custo.
2. Introduza variáveis de excesso nas restrições.
3. Explique o significado de cada excesso no contexto.
4. Verifique se contratar quatro unidades de A e seis de B atende às exigências e calcule o custo.

Contextualização dos dados da aba Exercicio1.

8. Mistura de ingredientes — minimização

Uma mistura pode utilizar três ingredientes. Seus custos e contribuições por quilograma são:

Não há exigência adicional de massa total.

1. Construa o modelo de custo mínimo.
2. Transforme as restrições em igualdades com variáveis de excesso.
3. Acrescente variáveis artificiais e escreva a função auxiliar da Fase 1.
4. Resolva o modelo original com o Solver e interprete os excessos.

Dados do exemplo de duas fases de cap4.html.

9. Compra de insumos com capacidade limitada — minimização

Uma empresa pode comprar dois insumos, A e B, a R$ 2 e R$ 1 por quilograma. Cada quilograma fornece, respectivamente, quatro e três unidades de um componente necessário, cuja exigência mínima é seis unidades. O armazenamento de cada quilograma de A ocupa uma unidade de espaço; o de B ocupa duas. A capacidade disponível é de três unidades de espaço.

1. Construa o modelo de minimização.
2. Identifique a restrição que exige variável de excesso e a que admite variável de folga.
3. Prepare o modelo para duas fases, indicando uma base artificial inicial.
4. Resolva com o Solver e interprete o uso do espaço e o atendimento da exigência mínima.

Dados do exemplo de Dual-Simplex de cap4.html.

10. Folgas em um plano de produção

Considere o modelo:

Para o plano \((x_1,x_2,x_3)=(0,55,75)\):

1. Verifique a viabilidade.
2. Calcule a folga de cada restrição e identifique as restrições ativas.
3. Calcule o lucro.
4. Explique por que a existência de recurso ocioso, isoladamente, não permite concluir que o plano deixa de ser ótimo. Confira a otimalidade no Solver.

11. Excesso e inviabilidade

Considere:

1. Calcule os excessos associados aos planos \(A=(4,6)\) e \(B=(5,7)\).
2. Determine se \(C=(4,3)\) é viável, verificando todas as restrições.
3. Explique por que um valor negativo de “lado esquerdo menos limite mínimo” representa uma violação da restrição.
4. Acrescente a função \(\min z=3x_1+5x_2\). Compare os custos dos planos viáveis e confira o ótimo no Solver.

12. Folga, excesso e artificial

Considere:

1. Prepare o modelo para o método de duas fases, utilizando a construção usual com folga, excesso e artificiais.
2. Indique uma base inicial e os valores das variáveis básicas quando as demais são zero.
3. Escreva a função auxiliar da Fase 1.
4. Explique quais variáveis têm interpretação física e quais são auxiliares do algoritmo.
5. Resolva o modelo original no Solver e interprete a folga e o excesso.

13. Duas fases — exemplo 1 da planilha

Além do roteiro, explique por que a terceira restrição é redundante diante das duas primeiras.

Referência: aba Exercicio1; sentidos das desigualdades identificados pelos quadros com variáveis de excesso.

14. Duas fases — dual com duas variáveis

Além do roteiro, relacione esse modelo ao problema de produção do exercício 1 e compare seus valores ótimos.

Referência: aba Exercicio2-dual.

15. Duas fases — dual com três variáveis e três restrições

Além do roteiro, identifique a restrição dual com excesso positivo e relacione esse resultado ao valor da variável primal correspondente no exercício 2.

Referência: aba Exercicio3-dual.

16. Duas fases — dual com três variáveis e duas restrições

Além do roteiro, compare a solução dual com as folgas do primal do exercício 3.

Referência: aba Exercicio4-dual.

17. Conferência integrada de primal e dual

Utilize os modelos dos exercícios 2 e 15.

1. Organize, em uma planilha, as soluções primal e dual, os valores objetivos e os lados esquerdos das restrições.
2. Resolva ambos com o Solver.
3. Calcule a diferença entre os valores objetivos e verifique se ela é nula, admitindo tolerância de \(10^{-6}\).
4. Confira as relações de complementaridade: cada variável dual multiplicada pela folga primal correspondente e cada variável primal multiplicada pelo excesso dual correspondente devem resultar em zero, dentro da tolerância.
5. Interprete a ociosidade de R2 e a decisão de produzir ou não o produto A.

18. Relatório de verificação das soluções manuais

Utilize os quatro problemas resolvidos nos exercícios 13 a 16.

1. Monte uma tabela contendo solução manual, solução do Solver, valor objetivo por cada método e excessos em cada restrição.
2. Registre eventuais diferenças e investigue coeficientes, sentidos das desigualdades, não negatividade, fórmulas e arredondamentos.
3. Explique por que as variáveis artificiais não devem permanecer livres para atender às restrições na conferência do modelo original.
4. Explique a diferença entre confirmar numericamente o resultado e apresentar a sequência de quadros do método de duas fases.
5. Entregue a planilha de conferência e uma conclusão sobre a consistência dos resultados.