TEORIA_DA_DUALIDADE

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
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.