Programação Linear: Teoria da Dualidade

Prévia do material em texto

MÉTODOS QUANTITATIVOS PARA TOMADA DE DECISÃO
Aula 07: PROGRAMAÇÃO LINEAR (PL): TEORIA DA DUALIDADE
OBJETIVOS DA AULA:
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. 
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. O 
MATRIZ TRANSPOSTA
Seja A uma matriz do tipo m x n. Chamamos de transposta de A e indicaremos por At a matriz cujas colunas são ordenadas iguais às linhas de A, isto é:
 
	| 2 3 4 | 
A = |5 7 9 |
	|-3 5 0| 
Exemplo 1
- Modelo matemático primal:
Linha 1	 10 X1 + 10 X2 100 
Linha 2 3 X1 + 7 X2 42 
 
 ZMáx. = 60 X1 + 40 X2
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 DO MODELO MATEMÁTICO PRIMAL (MÉTODO GRÁFICO)
SOLUÇÃO DO MODELO MATEMÁTICO DUAL (MÉTODO GRÁFICO)
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 
 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 
_____________________________________
BASE X1 X2 X3 X4 b
_____________________________________
X3 10 10 1 0 100
_____________________________________
X4 3 7 0 1 42
_____________________________________
-Z -60 -40 0 0 0
BASE X1 X2 X3 X4 b
_____________________________________
X1 1 1 1/10 0 10
_____________________________________
X4 0 4 -3/10 1 12
_____________________________________
-Z 0 20 6 0 600
_____________________________________
Dividir a linha X3 por 10
Multiplicar a linha X1 por -3 e somar a linha X4
Multiplicar a linha X1 por 60 e somar a linha -Z
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
Na próxima aula você vai aprender:
Teoria dos Jogos: conceitos básicos;
- A estrutura de um jogo.