Dualidade em Programação Linear

Prévia do material em texto

Prof. Célio Moliterno 
DUALIDADE 
 
Em determinadas situações, a quantidade de cálculos necessários para 
resolver um modelo linear pelo método Simplex pode ser reduzida. O 
modelo inicial, chamado de primal, pode ser substituído por outro modelo 
chamado dual, cuja a solução é mais rápida. Conhecida a solução do dual, 
conheceremos em conseqüência a solução do primal. 
 
DUAIS SIMÉTRICOS – (envolvem variáveis não negativas e restrições 
do tipo desigualdade). 
 
PRIMAL 
minimizar: z = CT X 
sujeito a: AX � B 
 com: X � 0 
 
DUAL 
maximizar: z = BT W 
 sujeito a: ATW � C 
 com: W � 0 
 
Exemplo: 
 
Primal ���� minimizar: z = 5x1 + 2x2 + x3 
 
 sujeito a: 2x1 + 3x2 + x3 � 20 
 6x1 + 8x2 + 5x3 � 30 
 7x1 + x2 + 3x3 � 40 
 x1 + 2x2 + 4x3 � 50 
 
 todas variáveis não negativas 
 
 
Dual � maximizar: z = 20w1 + 30w2 + 40w3 + 50w4 
 
 sujeito a: 2w1 + 6w2 + 7w3 + 1w4 � 5 
 3w1 + 8w2 + w3 + 2w4 � 2 
 w1 + 5w2 + 3w3 + 4w4 � 1 
 
 todas variáveis não negativas 
 
 
 
 
 Prof. Célio Moliterno 
DUAIS ASSIMÉTRICOS: 
 
 PRIMAL 
minimizar: z = CT X 
 sujeito a: AX = B 
 com: X � 0 
 
 
maximizar: z = CT X 
 sujeito a: AX = B 
 com: X � 0 
 
Exemplo: 
 
 Primal ���� maximizar: z = x1 + 3x2 – 2x3 
 
 sujeito a: 4x1 + 8x2 + 6x3 = 25 
 7x1 + 5x2 + 9x3 = 30 
 
 todas variáveis não negativas 
 
 Dual � minimizar: z = 25w1 + 30w2 
 
 sujeito a: 4w1 + 7w2 � 1 
 8w1 + 5w2 � 3 
 6w1 + 9w2 � -2 
 
Exemplo: 
 
 Primal ���� minimizar: z = 3x1 + x2 + 0x3 + 0x4 + Mx5 + Mx6 
 
 sujeito a: x1 + x2 – x3 + x5 = 7 
 2x1 + 3x2 – x4 + x6 = 8 
 todas variáveis não negativas 
 
 Dual � maximizar: z = 7w1 + 8w2 
 
 sujeito a: w1 + 2w2 � 3 
 w1 + 3w2 � 1 
 -w1 � 0 
 – w2 � 0 
 w1 � M 
 w2 � M 
DUAL 
maximizar: z = BT W 
 sujeito a: ATW � C 
 
minimizar: z = BT W 
 sujeito a: ATW � C 
 
com w1 e w2 não negativos 
 Prof. Célio Moliterno 
b) maximizar: z = 2x1 + 3x2 + x3 
 
 sujeito a: x1 + x2 � 10 
 2x1 + 4x2 – x3 = 20 
 
 x1 � 0, x2 � 0, x3 � 0 
 
d) maximizar: z = 2x1 + x2 
 
 sujeito a: x1 + 5x2 � 10 
 x1 + 3x2 � 6 
 2x1 + 2x2 � 8 
 
 x1 � 0, x2 � 0 
V. Folga 
 Sendo as terceira e quarta restrições serem equivalentes a w1 � 0 e w2 � 0 e 
devido a quinta e sexta restrições requerem simplesmente que as variáveis 
sejam finitas, o modelo Dual pode ser reduzido a 
 
 maximizar: z = 7w1 + 8w2 
 
 sujeito a: w1 + 2w2 � 3 
 w1 + 3w2 � 1 
 
 com w1 e w2 não negativos 
 
Exercícios: 
 
1) Determine o Dual do modelo de programação 
 
a) maximizar: z = 2x1 + 3x2 + x3 
 
 sujeito a: 3x1 + 4x2 + 2x3 � 10 
 2x1 + 6x2 + x3 � 20 
 x1 – x2 – x3 � 30 
 
 x1 � 0, x2 � 0, x3 � 0 
 
c) minimizar: z = 10x1 + 12x2 + 9x3 
 
 sujeito a: x1 + 2x2 + x3 � 1 
 x1 + x2 + 3x3 � 2 
 x1 + 4x2 – x3 � 3 
 
 x1 � 0, x2 � 0, x3 � 0 
 
2) Mostrar que ambos os modelos de programação Primal e Dual, 
referentes ao exercício 1d, apresentam o mesmo valor ótimo de Z. 
 
 Ultimo quadro Simplex Primal 
 
 x1 x2 x3 x4 x5 
 x3 a11 a12 a13 a14 a15 K1 
 x4 a21 a22 a23 a24 a25 K2 
 x1 a31 a32 a33 a34 a35 K3 
 C1 C2 C3 C4 C5 Z 
 
w1 = C3 ; w2 = C4 ; w3 = C5 
 Ultimo quadro Simplex Dual 
 
 w1 w2 w3 w4 w5 
 w5 a11 a12 a13 a14 a15 K1 
 w3 a21 a22 a23 a24 a25 K2 
 C1 C2 C3 C4 C5 -Z 
 
Sol. do modelo 
Dual 
V. Excesso 
Sol. do modelo 
Primal x1 = C4, x2 = C5 
 Prof. Célio Moliterno 
3) Sabe-se que os alimentos – leite, carne, e ovos fornecem as quantidades 
de vitaminas dadas conforme a tabela abaixo 
 
Vitaminas Leite (litro) Carne (Kg) Ovos (dz) Quantidade 
diária minima 
A 0,25mg 2mg 10mg 1mg 
B 25mg 20mg 10mg 50mg 
D 2,5mg 200mg 10mg 10mg 
Custo 
Unitário R$2,20 R$17,00 R$4,20 
 
Deseja-se calcular quais quantidades de leite, carne e ovos, a fim de 
satisfazer as quantidades mínimas de nutrientes (vitaminas) a um 
mínimo custo. 
Resolvendo o problema, devemos encontrar as seguintes equações: 
 
Minimizar: Z = 2,2x1 + 17x2 + 4,2x3 
 
 sujeito a : vitamina A: 0,25x1 + 2x2 + 10x3 � 1 
 vitamina B: 25x1 + 20x2 + 10x3 � 50 
 vitamina D: 2,5x1 + 200x2 + 10x3 � 10 
 x1 � 0, x2 � 0, x3 � 0 
 
E assim devemos ter: 
 
Maximizar: Z = w1 + 50w2 + 10w3 
 
 Leite sintético:..............0,25w1 + 25w2 + 2,5w3 � 2,2 
 Carne:........................... 2w1 + 20w2 + 200w3 � 17 
 Ovos:............................ 10w1 + 10w2 + 10w3 � 4,2 
 
Interpretação econômica do Problema Dual 
 
Imaginemos que uma companhia farmacêutica fabrica essas vitaminas 
em pílulas e que o mercado consumidor obtenha os nutrientes a partir 
destas pílulas em vez de alimentos. O problema é determinar os preços 
máximos w1 , w2 e w3 por miligrama, para as pílulas de modo a 
maximizar a renda e, assim mesmo, manter-se competitivo com os 
alimentos em forma natural. Para manter-se competitivo, o custo dos 
nutrientes sintéticos oriundos de pílulas não pode ser superior ao custo 
C , dos mesmos nutrientes obtidos a partir de alimentos reais. Portanto, 
para primeira coluna, o leite sintético não pode ser mais caro que o 
natural. 
 Prof. Célio Moliterno 
V. Folga 
1) Solução: 
a) minimizar: z = 10w1 + 20w2 + 30w3 
 sujeito a: 3w1 + 2w2 + 1w3 � 2 
 4w1 + 6w2 – 1w3 � 3 
 2w1 + 1w2 – 1w3 � 1 w1 � 0, w2 � 0, W3 � 0 
 
 
b) minimizar: z = 10w1 + 20 w2 
 sujeito a: 1w1 + 2w2 � 2 
 1w1 + 4w2 � 3 
 -1w2 � 1 w1 � 0, w2 � 0 
 
 
c) maximizar: z = w1+ 2w2 + 3w3 
 sujeito a: w1 + w2 + w3 � 10 
 2w1 + w2 + 4w3 � 12 
 w1 + 3w2 – w3 � 9 w1 � 0, w2 � 0, w3 � 0 
 
 
d) minimizar: z = 10w1 + 6w2 + 8w3 
 sujeito a: 1w1 + 1w2 + 2w3 � 2 
 5w1 + 3w2 + 2w3 � 1 w1 � 0, w2 � 0, w3 � 0 
 
 
2) Solução 
 Primal Dual 
 x1 x2 x3 x4 x5 
x3 1 5 1 0 0 10 
x4 1 3 0 1 0 6 
x5 2
* 2 0 0 1 8 
 -2 -1 0 0 0 0 
 
 x1 x2 x3 x4 x5 
x3 0 4 1 0 -1/2 6 
x4 0 2 0 1 -1/2 2 
x1 1
 1 0 0 1/2 4 
 0 1 0 0 1 8 
 
 
 
Primal: x1 = 4; x2 = 0; Z = 8 
Dual: w1 = 0; w2 = 0; w3 = 1 
Sol. modelo 
Dual 
 w1 w2 w3 w4 w5 w6 w7 
 10 6 8 0 0 M M 
w6 1 1 2 -1 0 1 0 2 
w7 5* 3 2 0 -1 0 1 1 
 10 6 8 0 0 0 0 0 
 -6 -4 -4 1 1 0 0 -3 
 
 
 w1 w2 w3 w4 w5 
w5 -4 -5 0 -1 1 1 
w3 1/2 1/2 1 -1/2 0 1 
 6 2 0 4 0 -8 
 
 
 
Dual: w1 = 0; w2 = 0; w3 = 1 
Primal: x1 = 4; x2 = 0; Z =-(-8) 
 
Sol. Modelo 
Primal 
V. Excesso