DUALIDADE EM PROMACAO LINEAR

DUALIDADE EM PROGRAMAÇÃO LINEAR

INTRODUÇÃO A DUALIDADE

Todo problema de programação linear, que chamaremos  de primal, traz         consigo um segundo problema, chamado de dual, sendo ambos         completamente inter-relacionados, de tal maneira que a solução ótima de um fornece informações completas sobre o outro.

Montagem do Problema Dual

Seja o seguinte problema de programação linear, em forma literal:

[pic 1]

O dual do seguinte problema pode ser escrito da seguinte maneira:

[pic 2]

As variáveis yI são chamadas variáveis duais.

O problema dual, para os modelos em que as restrições são desigualdades do tipo ≤, é construído a partir do primal da seguinte maneira:

• 1. Cada restrição, em um problema, corresponde a uma variável no outro.
• 2. Os elementos do lado direito das restrições, em um problema, são os coeficientes da função objetivo do outro problema.
• 3. Se o objetivo de um problema é maximizar, o do outro será minimizar, e vice-versa.
• 4. O problema de maximização tem restrições com sentido (≤) e o problema de minimização tem restrições com o sentido (≥).
• 5. As variáveis de ambos os problemas são não-negativas.

Escreva o dual dos seguintes itens:

[pic 3]

[pic 4]

[pic 5]

b. [pic 6]

[pic 7]

1)

[pic 8]

[pic 9]

2) PROBLEMA DA DIETA

[pic 10]

O interesse do Governo é que as pessoas tenham uma dieta equilibrada (que atenda aos valores rnínimos dos nutrientes), mas, ao mesmo tempo, que tenha o menor custo possível. Como um modelo poderia ser construído de forma a capturar todos os interesses e restrições envolvidos no problema?

3) PROBLEMA DO MIX DE PRODUÇÃO

[pic 11]

4)

[pic 12]

1. A Calçados Romano possui três unidades de produção de calçados e 2 lojas que fazem as vendas dos produtos. A primeira unidade possui  1000 pares em estoque, a segunda 2000 e a terceira 2200. Para  a próxima semana, as lojas vão requerer 2500 e 2700 pares, respectivamente. O custo de transporte de 100 pares da unidade 1 para a loja 1 é de R$ 20. Os outros custos entre as unidades e lojas são oferecidos na tabela a seguir.

Unidade	Estoque [pares]	Custo de transporte da unidade para a loja [R$]
		1	2
1	1000	20	10
2	2000	5	8
3	2200	6	19
Demanda da loja		2500	2700

Os calçados podem ser deixados nos estoques, mas a demanda das lojas deve ser atendida. Com o intuito de minimizar custos de transporte,  formule um modelo.[pic 13]

...