Teoria da Dualidade

Investigação Operacional

Teoria da Dualidade

2013/2014

Problema Dual
Associado a um PPL (primal) existe um outro problema, que se designa por problema linear dual ou, simplesmente, dual.
O par primal-dual tem as seguintes propriedades:
 são representações matemáticas do mesmo problema real,
 a resolução de um deles constitui a resolução simultânea do outro,
 a solução de um está completamente determinada pela solução do outro,

 o dual do dual é o primal.
Forma Canónica do Primal:

Forma Canónica do Dual:

Max

z = CT X

Min

s.a.:

AX ≤ b

s.a.:

X≥0
( P)



Max z
s.a :

2 x1

 4 x2

x1

 x2



2

2 x1

 3 x2



3

x1 , x2  0

( D)

w = bT Y

ATY ≥ C
Y≥0
Min w
s.a :



2 y1

 3 y2

y1

 2 y2



2

y1

 3 y2



4

y1 , y2  0

Na forma canónica do problema do primal, não se exige que os termos independentes das restrições tenham componentes não negativas. 2

Interpretação económica:

(P)

Max z 

n



cjxj

Max z 

j 1

n

s.a.



a ij x j  bi ,

i  1, ..., m

n

s.a.

a

j  1, ..., n



xj

ij x j

 si  bi ,

m



x j , si  0,
Min w 

bi yi

i  1, ..., m

m

b y i m

a ij yi  c j ,

j  1, ..., n; i  1, ..., m

i

i 1

i 1

m

j

j 1

x j  0,

s.a.

c j 1

j 1

( D) Min w 

n

j  1, ..., n

j 1

yi  0 , i  1, ..., m

s.a.

a

ij

yi  t j  c j ,

j  1, ..., n

j 1

yi , t j  0 , i  1, ..., m; j  1, ..., n

Primal: z - o lucro total; cj - o lucro produzido por unidade de produto j aij - as unidades de recurso i afectas à produção de uma unidade da produto j; si - quantidade de recurso i não utilizada bi - a quantidade de recurso i disponível
Dual:
w - representa a valorização total dos recursos disponíveis yi - varáveis de decisão duais – representam a valorização unitária a imputar a