Capitulo 8: Dualidade
O que é um modelo Dual?
De acordo com Andrade, E.L (2009): “ Todo problema de programação linear, que chamaremos de
primal, traz com sigo uma segundo problema, chamado dual, sendo ambos completamente interrelacionados, de tal maneira que a solução ótima de um fornece informações completas sobre o
outro.”
Para que precisamos estudar o modelo Dual?
 Devido às interpretações econômicas que o modelo Dual nos proporciona
 O modelo Dual pode ter uma solução mais fácil do que o original (primal), pois o número de
restrições e variáveis pode ser diferente
Capitulo 8: Dualidade
Vamos supor o seguinte modelo matemático:
1) Variáveis de decisão
X1: Quantidade de produção do produto 1
X2: Quantidade de produção do produto 2
X3: Quantidade de produção do produto 3
2) Função Objetivo (maximizar o lucro)
Max Z= 2X1+4X2+3X3
3) Restrições
Mão de Obra
Matéria Prima
Horas de Máquinas
X1 + X2+ 2X3≤10
3X1+
+ X3≤5
2X2+ X3≤6
Com X1, X2 e X3≥0
Esse é o modelo original, chamado de Primal
Capitulo 8: Dualidade
Vamos agora, transformar o modelo Primal em um modelo Dual. Apenas para uma questão didática,
vamos organizar o modelo da seguinte maneira (forma matricial), e vamos seguir os passos abaixo
1) Transformamos a função objetivo de “Maximizar” para “Minimizar”
2) Para cada restrição (são 3 no exemplo), criamos uma variável Y
3) Colocar cada Y na função objetivo do Dual e dar ao seu coeficiente o valor máximo da restrição a
que se refere
PRIMAL
DUAL
Max Z= 2X1+ 4X2+ 3X3
X1 + X2+ 2X3≤10
3X1+
Min Z= 10Y1 +5Y2 +6Y3
Y1
+ X3≤5
Y2
2X2+ X3≤6
Y3
Capitulo 8: Dualidade
Agora que já temos a Função Objetivo do Dual, vamos definir as restrições:
4) Cada variável de decisão do Primal, corresponde a uma restrição no Dual, cujo limite (bi) será o
coeficiente da variável Primal na função objetivo. Os coeficientes das restrições do Primal para a
mesma variável (X1, por exemplo) se transformarão nos coeficientes das variáveis Y do Dual. O sinal
da inequação deverá ser trocado: onde tiver “≤” deverá ser colocado “≥”
Analogamente, para os coeficientes de X2 e X3, teremos:
PRIMAL
DUAL
Max Z= 2X1+ 4X2+ 3X3
MinW= 10Y1+5Y2+6Y3
Restrições
Restrições
1X1 + X2+ 2X3≤10
Y1
1Y1+ 3Y2+ 0Y3 ≥2
3X1+
+ X3≤5
Y2
1Y1+ 0Y2+ 2Y3 ≥4
2X2+ X3≤6
Y3
2Y1+ 1Y2+ 1Y3 ≥3
Capitulo 8: Dualidade
Assim, teremos os dois modelos da seguinte forma:
PRIMAL
DUAL
Max Z= 2X1+ 4X2+ 3X3
Min W= 10Y1+5Y2+6Y3
Sujeito a:
Sujeito a
X1+ X2+2X3 ≤10
Y1+3Y2 ≥2
3X1+ X3 ≤5
Y1+2Y3 ≥4
2X2+ X3 ≤6
2Y1+Y2+Y3 ≥3
X1, X2 e X3 ≥0
Y1, Y2 e Y3 ≥0
Capitulo 8: Dualidade
Assim, os conceitos básicos para a criação de um problema Dual através de um Primal se resumem
da seguinte maneira:
•Para cada restrição de um Primal, teremos uma variável no Dual;
•Os limites das restrições do Primal (constantes que chamamos de bi) serão os coeficientes na
Função Objetivo do Dual;
•A maximização no Primal se transforma em minimização no Dual e a minimização, em
maximização;
•Quando as restrições do Primal forem “≤”, no Dual serão “≥” e vice-versa;
•A solução ótima obtida é a mesma para ambos os problemas
•Nota 1*: Tanto no Primal quanto no Dual, as variáveis (X ou Y) serão sempre positivas (ou seja:
“≥0”)
•Nota 2: O Dual do Primal é o Primal do Dual.
*Exceto quando uma das restrições tiver sinal de igualdade. Nesse caso a variável correspondente é
irrestrita em sinal.
Capitulo 8: Dualidade
Interpretação Econômica do Dual
Num modelo de maximização dos lucros, o Dual se refere à capacidade dos recursos de gerar lucros.
Dado o exemplo abaixo (Andrade E. L., 2009), vamos fazer a interpretação do modelo Dual:
Problema Primal:
Problema Dual:
Max. Z= 5X1+6X2
Min. W= 14Y1+9Y2+58Y3
Sujeito a:
Sujeito a:
X1+2X2≤14 (Recurso A)
Y1+Y2+7Y3 ≥5
X1+ X2≤9
2Y1+Y2+4Y3 ≥6
(Recurso B)
7X1+4X2≤58 (Recurso C)
X1 e X2 ≥ 0
Onde: X1 é a quantidade do Produto 1 e X2 a
do Produto 2
Y1, Y2 e Y3 ≥ 0
Capitulo 8: Dualidade
O Simplex do problema Dual seria:
Y1
Y2
Y3
Y4
Y5
b
0
1
10
-2
1
4
1
0
-3
1
-1
1
0
0
10
4
5
50
1) Qual o valor de Z do Primal?
1) Max Z = min. W = 50
2) Quais as variáveis básicas?
2) Y1 e Y2
3) Quais as variáveis não básicas?
3) Y3, Y4 e Y5
4) Qual o valor de Y1 e o que significa?
4) Y1 é igual a 1 (coluna b) e é chamado de utilidade
marginal. Ele representa a primeira restrição, que é o
recurso A. O valor 1 atribuído a ele, significa que a cada 1
unidade a mais desse recurso, o lucro é acrescido de 1
unidade. Inversamente, para cada 1 unidade perdida nesse
recurso, o lucro é subtraído de 1 unidade também.
5) Y2 é igual a 4 (utilidade marginal). Ele representa a
segunda restrição, que é o recurso B. O valor 4 atribuído a
ele, significa que a cada 1 unidade a mais desse recurso, o
lucro é acrescido de 4 unidades. Inversamente, para cada 1
unidade perdida nesse recurso, o lucro é subtraído de 4
unidades também.
5) Qual o valor de Y2 e o que significa?
Capitulo 8: Dualidade
O Simplex do problema Dual seria:
Y1
Y2
Y3
Y4
Y5
b
0
1
10
-2
1
4
1
0
-3
1
-1
1
0
0
10
4
5
50
6) Qual o valor de Y3 e o que significa?
6) Y3 é uma variável não básica, por isso seu valor é 0. Ele
representa o recurso C. Significa que uma variação unitária
na sua disponibilidade não causará nenhum efeito no lucro
final.
7) O recurso C é escasso?
7) Não. A folga desse recurso é de 10 unidades e pode ser
vista na linha que representa W (última linha).
8) Qual o valor de Y4 e o que significa?
8) Y4 é uma variável não básica, por isso seu valor é 0. Na
linha que representa W, o coeficiente 4 indica que serão
produzidos 4 Produto1.
Se ele fosse diferente de 0 (variável não básica) o seu valor
(na coluna b) significaria um lucro marginal negativo (que
seria o quanto o lucro seria menor se fossemos obrigado a
produzir o Produto1)
Capitulo 8: Dualidade
O Simplex do problema Dual seria:
Y1
Y2
Y3
Y4
Y5
b
0
1
10
-2
1
4
1
0
-3
1
-1
1
0
0
10
4
5
50
9) Qual o valor de Y5 e o que significa?
10) Quanto você pagaria para comprar
1 unidade do recurso B?
11) Quanto você pagaria para comprar
1 unidade do recurso C?
9) Y5 é uma variável não básica, por isso seu valor é 0. Na
linha que representa W, o coeficiente 5 indica que serão
produzidos 5 Produto2.
Se ele fosse diferente de 0 (variável não básica) o seu valor
(na coluna b) significaria um lucro marginal negativo (que
seria o quanto o lucro seria menor se fossemos obrigado a
produzir o Produto2)
10) O recurso B é escasso e cada unidade dele aumentará
o lucro em $4, por isso, poderíamos pagar qualquer valor
abaixo de $4 (somando-se seus custos)
11) O recurso C está sobrando. Não deve ser comprado
Capitulo 8: Dualidade
Exercicio 8.1
Fazer o Dual e a interpretação do modelo Dual:
Problema Primal:
Problema Dual:
Max. Z= 13X1+4X2
Min. W= 80Y1+60Y2+50Y3
Sujeito a:
Sujeito a:
2X1+1X2≤80 (Recurso A)
X1+ X2≤60
(Recurso B)
X1≤50
(Recurso C)
X1 e X2 ≥ 0
Onde: X1 é a quantidade do Produto 1 e X2 a
do Produto 2
2Y1+Y2+Y3 ≥13
Y1+Y2
≥4
Y1, Y2 e Y3 ≥ 0
Capitulo 8: Dualidade
O Simplex do problema Dual seria:
Y1
Y5
b
0
1
2,5
1
0
6,5
0
520
0
Y2
20
Y3
10
Y4
40
1) Qual o valor de Z do Primal?
1) Max Z = min. W = 520
2) Quais as variáveis básicas?
2) Y1 e Y5
3) Quais as variáveis não básicas?
3) Y2, Y3 e Y4
4) Qual o valor de Y1 e o que significa?
4) Y1 é igual a 6,5 (coluna b) e é chamado de utilidade
marginal. Ele representa a primeira restrição, que é o
recurso A. O valor 6,5 atribuído a ele, significa que a cada 1
unidade a mais desse recurso, o lucro é acrescido de 6,5
unidade. Inversamente, para cada 1 unidade perdida nesse
recurso, o lucro é subtraído de 6,5 unidade também.
5) Y2 é uma variável não básica, por isso seu valor é 0. Ele
representa o recurso B. Significa que uma variação unitária
na sua disponibilidade não causará nenhum efeito no lucro
final.
5) Qual o valor de Y2 e o que significa?
6) O recurso B é escasso?
6) Não. A folga desse recurso é de 20 unidades e pode ser
vista na linha que representa W (última linha).
Capitulo 8: Dualidade
O Simplex do problema Dual seria:
Y1
Y5
b
0
1
2,5
1
0
6,5
0
520
0
Y2
20
Y3
10
Y4
40
7) Qual o valor de Y4 e o que significa?
7) Y4 é uma variável não básica, por isso seu
valor é 0. Na linha que representa W, o
coeficiente 40 indica que serão produzidos 40
Produto1.
8) Qual o valor de Y5 e o que significa?
8) Y5 é igual a 2,5 (coluna b) e significa um lucro marginal
negativo. Não será produzido nenhum produto 2, mas, se
fossemos obrigado a produzir lo, cada unidade produzida
traria um prejuízo de $2,5