Aula 07 Métodos quantitativos para tomada de decisão

Prévia do material em texto

- -1
MÉTODOS QUANTITATIVOS PARA 
TOMADA DE DECISÃO
TEORIA DA DUALIDADE
- -2
Olá!
Ao final desta aula, você será capaz de:
- Entender que todo problema de Programação Linear, chamado primal, tem associado a ele outro problema de
Programação Linear, chamado dual.
1 O PROBLEMA DUAL
Uma das mais importantes descobertas no início do desenvolvimento da foi o conceito de Programação Linear
e suas muitas ramificações importantes.dualidade 
Esta descoberta revelou que todo o problema de Programação Linear tem associado a ele outro problema de
Programação Linear chamado dual.
Problema de Programação Linear
Problema de Programação Linear Dual
As relações entre o problema dual e o problema original (chamado de primal) provam ser úteis de diversas
maneiras.
2 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.
Saiba mais
Problema dual - 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 as dúvidas impostas pela hipótese de certeza do
problema de Programação Linear.
- -3
SAIBA MAIS
Vamos entender melhor o conceito de Programação Dual?
Exemplo
Seja o assim definido:problema primal
a x + a X +...........+ a x 
11 11 12 2 1n n
≤ b
1
 (y )
1
a x + a X +...........+ a x 
21 11 22 2 2n n
≤ b
2
 (y )
1
..................................................................
Z = C x + C x +.........+ C x
Max 1 1 2 2 n n
Associando-se a cada i do primal uma conforme indicado acima, o é assimrestrição variável y ,1 problema dual
definido
a y + a y +...........+ a y 
11 11 21 2 m1 m
≥ c
1
a y + a X +...........+ a y 
12 11 22 2 m2 m
≥ c
2
................................................................
a y + a y +...........+ a x 
n1 1 n2 2 mn m
≥ c
n
Z = b y + b y +.........+ b y
Min 1 1 2 2 n m
Para ilustrar a teoria que você acabou de estudar, veja agora um exemplo numérico.
Modelo matemático primal
2 X + X 1 2 ≤ 16
X1 + 2X2 ≤ 11
X1 + 3X2 ≤ 15
Z = 300 X + 500 XMáx. 1 2
Modelo matemático dual associado ao primal
2Y + Y + Y 1 2 3 ≥ 300
Y + 2Y + 3Y 1 2 3 ≥ 500
Z = 16Y + 11Y + 15YMin 1 2 3
Observe atentamente os dois modelos e procure identificar as características de cada um.
SAIBA MAIS
Depois, leia um comentário sobre essa comparação.
Comentário
Comparando os modelos e , verificamos que:primal dual
As do dual são do tipo ≥ ao passo que as do são do tipo restrições , primal ≤;
- -4
O número de do (m valores de y ) é ao número de do ;incógnitas dual 
i
igual restrições primal
O número de do é ao número de do (n valores de x );restrições dual igual incógnitas primal 
j
A do é a da matriz dos coeficientes do ;matriz dos coeficientes dual transposta primal
A do é de , ao passo que a do é de ;função objetivo dual minimização primal maximização
As são ostermos constantes das restrições do dual coeficientes da função objetivo do primal;
Os são oscoeficientes da função objetivo do dual termos constantes das restrições do primal.
3 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
 com apenas .(X1 e X2), duas inequações
Primal
X + 2X 1 2 ≤ 3 (3; 1,5)
X1 + X2 ≤ 2 (2; 2)
Z = 5 X + 7 XMáx. 1 2
Dual
Y + Y 1 2 ≥ 5 (5; 5)
2Y + Y 1 2 ≥ 7 (3,5; 7)
Z = 3Y + 2YMin 1 2
Conheça os dados do problema que aparecem na solução gráfica.
Dados do problema
• Substituindo os pontos solução na função objetivo do primal:
A (0; 1,5) -> Z = 5 (0) + 7 (1,5) = 10,5
Máx
•
- -5
B (1: 1) -> Z = 5 (1) + 7 (1) = 12
Máx
C (2: 0) -> Z = 5 (2) + 7 (0) = 10
Máx
O ponto solução é X = 1 e X = 1, que maximiza o lucro em 12.1 2
• Substituindo os pontos solução na função objetivo do dual:
A (0; 7) -> Z = 3 (0) + 2 (7) = 14
Min
B (2: 3) -> Z = 3 (2) + 2 (3) = 12
Min
C (5: 0) -> Z = 3 (5) + 2 (0) = 15
Min
O ponto solução é Y = 2 e Y = 3, que minimiza o lucro em 12.1 2
4 MÉTODO DUAL-SIMPLEX
Você conhece as características do ?Método Dual-Simplex
O método Dual-Simplex lida com o quê?
O lida diretamente com soluções básicas incompatíveis, porém “melhores que a ótima”, emétodo Dual-Simplex
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 é empregado em quê?
O é bastante empregado em análise de sensibilidade, quando são feitas pequenasmétodo Dual-Simplex 
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.
Para facilitar o entendimento do método, vamos utilizar um exemplo.
X + 2X 1 2 ≤ 3
X1 + X2 ≤ 2
Z = 5 X + 7 XMáx o lucro. 1 2
Colocando as variáveis de folga nas inequações do modelo matemático primal e multiplicando a função objetivo
por (-1) temos:
X + 2X + X =1 2 3 3
X1 + X2 + X = 24
-Z = -5X – 7XMáx o lucro 1 2
•
- -6
Veja como ficou a construção do primeiro quadro do simplex.
1º Quadro do Simplex
Aplicando as regras do simplex, chegamos aos quadros do simplex.
2º Quadro do Simplex
3º Quadro do Simplex
O próximo passo é colocar as variáveis de folga nas inequações do modelo matemático dual e multiplicar a
função objetivo por (-1). Veja o resultado dessa operação.
Y + Y - Y =1 2 3 5
2Y1 + Y2 - Y = 74
- -7
-Z = -3Y – 2XMin o custo 1 2
Agora é possível identificar a solução do dual.
Veja como fazê-lo.
Solução dual
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. Observe.
Veja como é feita a identificação da solução no quadro do simplex.
Primal: é a relação das variáveis da linha da base com os valores da coluna b, sendo portanto X = 1, X = 1, X = 
1 2 3
0 e X = 0, e o valor máximo de lucro igual a 12.
4
Dual: é a relação das variáveis que estão na primeira linha com os valores que estão na linha –Z, sendo portanto 
Y = 2, Y = 3, Y = 0 e Y = 0, e o valor mínimo de custo igual a 12.
1 2 3 4
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.
CONCLUSÃO
Nesta aula, você:
• Aprendeu que todo o problema de Programação Linear tem associado a ele outro problema de 
Programação Linear chamado dual;
• Compreendeu que 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;
• Descobriu que a interpretabilidade serve para amenizar as dúvidas impostas pela hipótese de certeza do 
problema de Programação Linear;
• Aprendeu que a cada modelo de Programação Linear, corresponde um outro modelo, denominado dual, 
•
•
•
•
- -8
• Aprendeu que 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;
• Aprendeu que 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, sendo bastante empregado em 
análise de sensibilidade, quando são feitas pequenas modificações no modelo;
• Aprendeu os procedimentos para aplicação do método Dual-simplex.
••
•