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
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
BASE
X1
X2
X3
__________________________________
X2
0
1
1
X1
1
0
-1
_________________________________
-Z
0
0
2
Y2
X4
b
-1/2
2
1
1
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.