GST0559 Métodos Quantitativos para Tomada de Decisão Aula 07

Prévia do material em texto

MÉTODOS QUANTITATIVOS – AULA 7 – SEMESTRAL 
ANTONIO VIANA MATIAS
Rio de Janeiro, 2011
1
 AULA 7 - PROGRAMAÇÃO LINEAR: TEORIA DA DUALIDADE
AULA 07 – PROGRAMAÇÃO LINEAR: TEORIA DA DUALIDADE
Nesta aula serão abordados os seguintes assuntos:
- A teoria da dualidade;
- O método dual-simplex, para resolução de problemas de Programação Linear.
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. 
	
O PROBLEMA 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. 	
Exemplo 1
- Modelo matemático primal:
Linha 1 10 X1 + 10 X2  100 (10; 10)
Linha 2 3 X1 + 7 X2  42 (14; 6)
ZMáx. = 60 X1 + 40 X2
Modelo matemático dual:
	 10 Y 1 + 3 Y 2  60 (6; 20)
 10 Y 1 + 7 Y 2  40 (4; 5,7)
	 Z Min = 100 Y 1 + 42 Y 2 
	
SOLUÇÃO GRÁFICA
	
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.
Exemplo do método Dual-Simplex:
- Modelo matemático primal:
 10 X1 + 10 X2  100 ÷ 10 X1 + X2  10 
 3 X1 + 7 X2  42 
ZMáx. = 60 X1 + 40 X2
- Colocando as variáveis de folga:
 X1 + X2 + X3 = 10 
 3 X1 + 7 X2 + X4 = 42 
- ZMín. = - 60 X1 - 40 X2
Modelo matemático dual:
	 10 Y 1 + 3 Y 2  60 
 10 Y 1 + 7 Y 2  40 
	 Z Min = 100 Y 1 + 42 Y 2 
- Colocando as variáveis de folga:
 10 Y 1 + 3 Y 2 - Y3 = 60 
 10 Y 1 + 7 Y 2 - Y4 = 40 
- Z Min = - 100 Y 1 - 42 Y 2 
 	
	
Solução do Método Dual-Simplex
Modelo matemático primal:
 	 X1 = 10	 X2 = 0 X3 = 0 X4 = 12
 ZMáx. = 600
Modelo matemático dual:
 Y 1 = 6 3 Y 2 = 0 Y3 = 0 Y4 = 20 
 ZMín. = 600
	
Nesta aula você aprendeu:
A teoria da dualidade;
 O método dual-simplex, para resolução de problemas de Programação Linear.