Dualidade
UFOP - ICEA
Prof.: Guido Pantuza
CEA 406
Dualidade
• Seja o PPL, doravante chamado de PPL primal:
min f ( x)  c1 x1  c2 x2
s.a. :
a11 x1  a12 x2  b1
a21 x1  a22 x2  b2
a31 x1  a32 x2  b3
xi  0
 i  1, 2
• Associado a este PPL, existe um PPL, chamado PPL dual:
max f ( x)  b1u1  b2u2  b3u3
s.a :
a11u1  a12u2  a13u3  c1
a21u1  a22u2  a23u3  c2
ui  0 i  1, 2, 3
UFOP - ICEA
Prof.: Guido Pantuza
2
Dualidade
• Uma indústria dispõe de três recursos A,B,C .
• Produz dois produtos P1 e P2.
• Lucro unitário de $ 5 e $ 6
Lucro
P1
P2
5
6
Disponibilidade
UFOP - ICEA
Recurso
A B C
1 1 7
2 1 4
14 9
Prof.: Guido Pantuza
56
CEA 406
Dualidade
• Primal:
max F ( x)  6 x1  5 x2
s.a. :
1x1  2 x2  14
1x1  1x2  9
7 x1  4 x2  56
xi  0
UFOP - ICEA
 i  1, 2
Prof.: Guido Pantuza
CEA 406
Dualidade:
Regras de transformação
Primal
Dual
Restrição

=

qq.
Variável


qq.


=


MIN
Dual
UFOP - ICEA
Variável
MAX
Restrição
Primal
Prof.: Guido Pantuza
Prof.: Guido Pantuza
5
CEA 406
Dualidade
• Dual:
min f ( x) 14u1  9u2  56u3
s.a. :
1u1  1u2  76u3  5
2u1  1u2  4u3  6
ui  0
UFOP - ICEA
 i  1, 2, 3
Prof.: Guido Pantuza
CEA 406
Dualidade
Vantagens:
• Em situações na qual a matriz de coeficientes
do primal tem maior número de linhas do que
de colunas:
Dual
A base no DUAL é menor!!!
UFOP - ICEA
Prof.: Guido Pantuza
7
Dualidade:
Vantagens
• É possível “cercar” a solução ótima. (Considere
um PPL primal de minimização)
UFOP - ICEA
Prof.: Guido Pantuza
8
UFOP - ICEA
Prof.: Guido Pantuza
CEA 406
Dualidade:
Vantagens
• É possível “cercar” a solução ótima. (Considere
um PPL primal de minimização)
f(x)
(valor do primal)
x* = u*
fD(x)
UFOP - ICEA
(valor do dual)
Prof.: Guido Pantuza
10
Dualidade
Interpretação Econômica
• Seja o par de PPL’s:
m
n
min  bi ui  f D (u )
max  c j x j  f ( x)
j 1
i 1
n
s.a :  aij x j  bi i  1,...,m
j 1
xj  0
s.a :  aijui  c j j  1,...,n
j  1,...,n
PRIMAL
UFOP - ICEA
m
i 1
ui  0
i  1,...,m
DUAL
Prof.: Guido Pantuza
11
Dualidade
• Uma indústria dispõe de três recursos A,B,C .
• Produz dois produtos P1 e P2.
• Lucro unitário de $ 5 e $ 6
Lucro
P1
P2
5
6
Disponibilidade
UFOP - ICEA
Recurso
A B C
1 1 7
2 1 4
14 9
Prof.: Guido Pantuza
56
CEA 406
Dualidade
Solução:
UFOP - ICEA
VB x1 x2 x3 x4 x5
x2 0 1 1 -1 0
x1 1 0 -1 2 0
b
5
4
x5
0
0
3 -10 1
8
0
0
1
50
4
Prof.: Guido Pantuza
0
CEA 406
Dualidade
Solução Dual:
UFOP - ICEA
VB
u1
u2
u3
u4
u5
b
x2
0
1
10
-2
1
4
x5
1
0
-3
1
-1
1
0
0
8
4
5
50
Prof.: Guido Pantuza
CEA 406
Dualidade
VB
u1
u2
u3
u4
u5
b
u2
0
1
10
-2
1
4
u1
1
0
-3
1
-1
1
0
0
8
4
5
50
VB x1
x2 0
x1 1
x2
1
0
x3
1
-1
x4
-1
2
x5
0
0
b
5
4
x5
0
0
3
-10
1
8
0
0
1
4
0
50
UFOP - ICEA
u é chamado
shadow price,
dual, valor
incremental,
efficiency price,
valor implícito,
etc.
CEA 406