TEORIA DA DUALIDADE

Prévia do material em texto

TEORIA DA DUALIDADE 
O PROBLEMA DUAL
 
Uma das mais importantes descobertas no início do desenvolvimento da Programação Linear foi o conceito de dualidade e suas muitas ramificações importantes. Esta descoberta revelou que todo o problema de Programação Linear tem associado a ele outro problema de Programação Linear chamado dual. As relações entre o problema dual e o problema original (chamado de primal) provam ser úteis de diversas maneiras. O problema dual é um modelo associado ao original, que traz a interpretabilidade econômica para os valores de recursos e para os coeficientes da função objetivo. Esta interpretabilidade serve para amenizar essas dúvidas impostas pela hipótese de certeza do problema de programação linear.
TEORIA DA DUALIDADE
COMPARAÇÃO DA FORMA DOS PROBLEMAS PRIMAL E DUAL
 
A cada modelo de Programação Linear, corresponde um outro modelo, denominado dual, formado por esses mesmos coeficientes, porém dispostos de maneira diferente, utilizando-se o conceito de matriz transposta.
Seja o problema primal assim definido:
a 11 x 1 + a 12 x 2 + .......... + a 1n x n  b 1	(y 1)
a 21 x 1 + a22 x 2 + .......... + a n2 x n  b 2	(y 2)
................................................................................
a m1 x 1 + a m2 x 2 + ......... + a mn x n  b m	(y m)
 
Z Max = c 1 x 1 + c 2 x 2 + ......... + c n x n
TEORIA DA DUALIDADE
COMPARAÇÃO DA FORMA DOS PROBLEMAS PRIMAL E DUAL
Associando-se a cada restrição i do primal uma variável y 1, conforme o indicado acima, o problema dual é assim definido:
  
a 11 y 1 + a2 1 y 2 + .......... + am 1 y m  c 1	
a 12 y 1 + a 2 2y 2 + .......... + a m 2 y m  c 2	
................................................................................
a 1n y 1 + a2n y 2 + ......... + a mn x m  c n	
 
Z Mín = b 1 y 1 + b 2 y 2 + ......... + bn x m
TEORIA DA DUALIDADE
Para ilustrar a teoria, vejamos agora um exemplo numérico:
-         Modelo matemático primal:
 	 2 X1 + X2  16 
 X1 + 2X2  11 
 X1 + 3X2  15 
 
 ZMáx. = 300 X1 + 500 X2 
 
-         O modelo matemático dual associado ao modelo matemático primal:
 2 Y 1 + Y 2 + Y 3  300
 Y 1 + 2Y 2 + 3Y 3  500
 Z Min = 16 Y 1 + 11Y 2 + 15 Y 3
TEORIA DA DUALIDADE
Comparando os modelos primal e dual, verificamos que:
-         As restrições do dual são do tipo , ao passo que as do primal são do tipo ;
-         O número de incógnitas do dual (m valores de yi) é igual ao número de restrições do primal;
-         O número de restrições do dual é igual ao numero de incógnitas do primal (n valores de xj);
-         A matriz dos coeficientes do dual é a transposta da matriz dos coeficientes do primal;
-         A função objetivo do dual é de minimização, ao passo que a do primal é de maximização;
-         Os termos constantes das restrições do dual são os coeficientes da função objetivo do primal; e
-         Os coeficientes da função objetivo do dual são os termos constantes das restrições do primal.
TEORIA DA DUALIDADE
EXEMPLO DA SOLUÇÃO GRÁFICA DO PRIMAL E DUAL
Para facilitar o entendimento, vamos utilizar um exemplo de modelo matemático primal com duas variáveis (X1 e X2), com apenas duas inequações: 
- Primal					- Dual
	 X1 + 2 X 2  3 (3; 1,5)	 Y1 + Y 2  5 (5; 5)	
	 X1 + X 2  2 (2; 2)	 2 Y1 + Y 2  7 (3,5; 7)
  
Zmáx = 5 X 1 + 7 X 2 		 Zmín = 3 Y 1 + 2 Y 2 
2 
TEORIA DA DUALIDADE
MÉTODO DUAL-SIMPLEX
 
O método Dual-Simplex lida diretamente com soluções básicas incompatíveis, porém “melhores que a ótima”, e procura achar a compatibilidade do problema. Ele lida com o problema exatamente como se o método simplex estivesse sendo, simultaneamente aplicado ao seu problema dual.
O método Dual-Simplex é bastante empregado em análise de sensibilidade, quando são feitas pequenas modificações no modelo. Além disso, algumas vezes é mais fácil começar com uma solução básica incompatível, porém “melhor que a ótima” e procurar a compatibilidade, do que obter uma solução compatível básica inicial e depois otimizá-la, como se faz no método simplex.
TEORIA DA DUALIDADE
Para exemplificar o método Dual-Simplex, vamos utilizar o mesmo exemplo:
	X1 + 2 X 2  3 
	X1 + X 2  2 
Zmáx o lucro= 5 X 1 + 7 X 2
Colocando as variáveis de folga nas inequações do modelo matemático primal e multiplicando a função objetivo por (-1):
X1 + 2 X 2 + X3 = 3 
	X1 + X 2 + X4 = 2 
- Zmáx o lucro = -5 X 1 - 7 X 2
TEORIA DA DUALIDADE
Construindo o primeiro quadro do simplex:
BASE	X1 X2	X3 X4	b
__________________________________
 X3		1 2 	1 0	3
 X4		1 1	0 1	2
_________________________________
 -Z	 -5 -7 0 0 0
TEORIA DA DUALIDADE
Aplicando as regras do simplex, chegamos ao 2º quadro do simplex:
BASE	X1 X2	X3 X4	b
__________________________________
 X2	 ½ 1	½ 0	3/2
 X4 ½ 0	-1/2 1	1/2
_________________________________
 -Z	 -3/2 0	7/2 0	21/2
TEORIA DA DUALIDADE
Aplicando as regras do simplex, chegamos ao 3º quadro do simplex:
BASE	X1 X2	X3 X4	b
__________________________________
 X2	 0 1	1 -1/2	1
 X1	 1 0	- 2	1
_________________________________
 -Z	 	0 0	2 3	12
TEORIA DA DUALIDADE
Colocando as variáveis de folga nas inequações do modelo matemático dual e multiplicando a função objetivo por (-1):
Y1 + Y 2 - Y3 = 5 
 2 Y1 + Y 2 - Y4 = 7 
- Zmín o custo = -3 Y 1 - 2 Y 2 
Para identificarmos a solução do dual, basta colocar no último quadro do simplex primal, onde temos as variáveis originais do modelo primal, as variáveis de folga do dual e onde ficam as variáveis de folga do primal, as variáveis originais do dual.
TEORIA DA DUALIDADE
	 Y3	Y4	Y1	Y2
BASE	X1	X2	X3	X4	b
__________________________________
 X2		 0	1	1	-1/2	1
 X1		1	0	-1	2	1
_________________________________
 -Z		0	0	2	3	12
TEORIA DA DUALIDADE
A identificação da solução no quadro do simplex é feita da seguinte maneira:
-         Primal: é a relação das variáveis da linha da base com os valores da coluna b, sendo portanto X1 = 1, X2 = 1, X3 = 0 e X4 = 0, e o valor máximo de lucro igual a 12.
-         Dual: é a relação das variáveis que estão na primeira linha, com os valores que estão na linha –Z, sendo portanto Y1 = 2, Y2 = 3, Y3 = 0 e Y4 = 0, e o valor mínimo de custo igual a 12.
 
Em resumo, quando trocamos a visão de maximização do lucro (diferença entre receita e custo) na fase primal, pela minimização de custos na fase dual, estamos considerando o benefício da produção.