Pesquisa Operacional

1. Problema Dual

O conceito de dualidade refere-se ao fato de que todo problema de programação linear está associado a outro problema de programação linear. A primeira é chamada de primal (problema original) e a segunda forma é chamada de dual. Os modelos primal e dual são completamente inter-relacionados de tal maneira que a solução ótima de um fornece informação completa sobre o outro. Significa que ao se calcular a solução ótima de uma, é possível calcular a solução ótima do outro.
Em determinadas situações, a quantidade de cálculos necessária para resolver um modelo linear pelo método Simplex pode ser reduzida. O modelo primal pode ser substituído por um modelo dual como solução mais rápida.

EXEMPLO:
PRIMAL:

MAX z = 2x1+x2
SA

x1+5x210 x1+3x26 2x1+2x28 x1 0 , x2 0

Tableau Final
BASE
x1 x3 0 x4 0 x1 1
-Z
0

x2
4
2
1
-1

DUAL:

x3
1
0
0
0

x4

x5
-1/2
-1/2
1/2
-1

0
1
0
0

bi
6
2
4
-8

Solução ótima do primal:
Z= 8 x1=4 x2=0 x3=6
Solução ótima do dual:
W=8 y1=0 y2=0 y3=1

x4=2

x5=0

y4=0

y5=1

x4=2

x5=0

y4=0

y5=1

MIN W = 10y1+6y2+8y3
SA

y1+y2+2y3 2 y1+3y2+2y3 1 y1 0 , y2 0, y3 0

Tableau Final
BASE
y1 y5 -4 y3 0,5
-Z

6

y2
-2
0,5

y3
0
1

y4
-1
-0,5

y5
1
0

bi
1
1

2

0

4

0

-8

Fonte: www.ecnsoft.net/?file_id=131

Solução ótima do primal:
Z= 8 x1=4 x2=0 x3=6
Solução ótima do dual:
W=8 y1=0 y2=0 y3=1

2

RELAÇÕES ENTRE PRIMAL E DUAL
Dual
Tem soluções viáveis
Primal

Ótima

Tem
Ótima
Possível soluções Ilimitado Impossível viáveis Sem
Inviável Impossível soluções viáveis

Sem soluções viáveis
Inviável

Ilimitado
Impossível
Impossível

Impossível
Possível

Possível

Possível

Fonte: www.ecnsoft.net/?file_id=131

RESUMO PARA TRANSFORMAÇÃO PRIMAL-DUAL
Restrições de Desigualdade
PRIMAL
MIN
S.A.
Com

T

Z= C X
AX  B
X0

DUAL
MAX W= BTY
S.A.
AT Y  C