Faculdade de Engenharia Eng.

Celso Daniel
Engenharia de Produo

Pesquisa Operacional II
Profa. Dra. Llian Ktia de Oliveira



4. Dualidade
O termo dualidade refere-se ao fato de que cada modelo de Programao Linear consiste de 2
formas. A primeira, ou original, chamada de primal e a segunda forma do modelo chamada de
dual. Como seria esperado, as propriedades de uma das formas do modelo esto relacionadas com as
propriedades da outra. Como resultado disto possvel, dada a soluo tima de uma das formas do
modelo, encontrar a soluo tima da outra forma do modelo. A soluo do chamado modelo dual
fornece informaes significativas sobre as questes econmicas existentes em qualquer modelo de
Programao Linear.

4.1. Introduo
A cada modelo de Programao Linear, contendo coeficientes

, e
ij i j
a b c corresponde um outro
modelo, denominado DUAL, formado por esses mesmos coeficientes, porm dispostos de maneira
diferente. Ao modelo original, d-se o nome de PRIMAL.
PROBLEMA PROBLEMA
PRIMAL DUAL

Considere o problema clssico da dieta:

Determinar a dieta que satisfaz os padres nutritivos
alimentos
1 2 3 4 5
Necessidades
mnimas
Protenas 3 4 5 3 6 42
Sais minerais 2 3 4 3 3 24
Custo 25 35 50 33 36

Temos que
i
x : quantidade do alimento i presente na dieta. Assim, o modelo dado por:

Pesquisa Operacional II Profa. Dra. Llian Ktia de Oliveira

2

1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
Min 25 35 50 33 36
sujeito a:
3 4 5 3 6 42
2 3 4 3 3 24
0, 1,...5
i
z x x x x x
x x x x x
x x x x x
x i
= + + + +
+ + + +
+ + + +
=
(Problema Primal)

PRIMAL: problema do cozinheiro
DUAL: problema do vendedor de plulas

O vendedor de plulas de protenas e plulas de sais minerais prope ao cozinheiro substituir a
dieta de alimentos por uma dieta de plulas onde:
1. A plula de uma unidade de protena custar w
1
. A plula de uma unidade de sais minerais custar
w
2
.
2. Os preos w
1
e w
2
sero fixados arbitrariamente pelo vendedor de plulas.
3. O vendedor garante que as plulas sero mais baratas que qualquer alimento.

1 2
1 2
1 2
1 2
1 2
3 2 25 alimento 1
4 3 35 alimento 2
5 4 50 alimento 3
3 3 33 alimento 4
6 3 36 alimento 5
w w
w w
w w
w w
w w
+
+
+
+
+

4. Os preos devem ser no-negativos.
5. A renda do vendedor de plulas, que l procurar maximizar com a fixao dos preos :

1 2
Renda 42 24 w w = = + .

Observao: Ser vantajoso para o cozinheiro suspender a dieta de alimentos e comprar as plulas do
vendedor?

Pesquisa Operacional II Profa. Dra. Llian Ktia de Oliveira

3

1 2
1 2
1 2
1 2
1 2
1 2
Max 42 24
sujeito a:
3 2 25
4 3 35
5 4 50
3 3 33
6 3 36
0, 1,2
i
w w
w w
w w
w w
w w
w w
w i
= +
+
+
+
+
+
=
(Problema Dual)
ou seja,

( )
( ) ( )
1 2
1 2
1 2
42
( )
24
sujeito a:
3 4 5 3 6
25 35 50 33 36
2 3 4 3 3
, 0
w w w
w w
w w

Matricialmente,
(PP)
Min ( )
sujeito a:

0
z x cx
Ax b
x
=

(PD)
Max ( )
sujeito a:

0
w wb
wA c
w
=

Observaes:
1. Os termos constantes das restries do dual so os coeficientes da funo objetivo do primal.
2. Os coeficientes da funo objetivo do dual so os termos constantes das restries do primal (os
vetores c e b invertem de posio).
3. No problema primal (PP)
minimiza-se o custo de uma dieta, satisfazendo condies mnimas de boa alimentao.
as variveis so quantidades de alimentos.
4. No problema dual (PD)
maximiza-se a renda da venda de plulas, garantindo que a dieta de plulas ser sempre mais
econmica que a de alimentos.
As variveis so os preos das plulas (nutrientes)
5.
o nmero de incgnitas do dual (dois valores de w
i
) igual ao nmero de restries do primal.

Pesquisa Operacional II Profa. Dra. Llian Ktia de Oliveira

4
O nmero de restries do dual igual ao nmero de incgnitas do primal (5 valores de x
i
).
Logo, h correspondncia, uma a uma, entre

Varivel do Restrio do
Primal Dual

alimento

Restrio do Varivel do
Primal Dual

nutriente
ou seja,
alimento
uma varivel do Primal
Fornece uma restrio do Dual

nutriente vice-versa.
6. A matriz de coeficientes do dual a transposta dos coeficientes do primal.

Exemplos
1. Determinar o dual do seguinte modelo de PL:

1 2 3
1 2 3
1 2 3
Max 6 2
sujeito a:
7 4
2 3 5
0, 1,...3
= + +
+
+ +
=
i
z x x x
x x x
x x x
x i
(PP)














Pesquisa Operacional II Profa. Dra. Llian Ktia de Oliveira

5
2. Determinar o dual do seguinte modelo de PL, representando graficamente ambos os modelos.

1 2
1 2
1 2
1 2
Max 3 4
sujeito a:
1
0
, 0
= +

+

z x x
x x
x x
x x
(PP)




























Pesquisa Operacional II Profa. Dra. Llian Ktia de Oliveira

6
4.2. Propriedades da dualidade
1. O dual do dual o primal.
2. Se a restrio k do primal igualdade, ento a varivel
k
w do dual sem restrio de sinal, isto ,
pode ter valor positivo, zero ou negativo.
3. Se a p-sima varivel do primal sem restrio de sinal, ento a p-sima restrio do dual uma
igualdade.

Exemplo:

1 2
1
2
1 2
1 2
Min 5 2
sujeito a:
3
4
2 9
0, livre
= +

=
+

z x x
x
x
x x
x x
(PP)




















Pesquisa Operacional II Profa. Dra. Llian Ktia de Oliveira

7
Uma caracterstica importante a comparao dos processos de ciclos entre o primal e o dual.
O primal parte de uma soluo vivel do problema original e vai melhorando-a passo a passo, at que
atinja o valor timo, enquanto o problema dual parte de uma soluo invivel ao problema original
(vivel para o dual) e tenta, passo a passo, chegar a uma soluo vivel para o problema original (que
a tima). A Figura 1 representa este processo no caso de existncia de uma soluo tima, para um
problema primal de maximizao.


PRIMAL Soluo vivel inicial
Passo um

Passo n-1
Soluo tima Passo n
Passo n DUAL
Passo n-1

Passo um
Soluo vivel inicial

Figura 1. Mtodo simplex aplicado ao primal e ao dual.

4.3. Teorema bsico da dualidade
Seja a representao algbrica do problema primal e respectivo dual abaixo:

(PP)
1
1
Min ( )
sujeito a:

0, 1,...,
1,...,
=
=
=

=
=

n
j j
j
n
ij j i
j
j
z x c x
a x b
x j n
i m

(PD)
1
1
Max ( )
sujeito a:

0, 1,...,
1,...,

=
=
=

=
=

m
i i
i
m
i ij j
i
i
w wb
wa c
w i m
j n


1. Se o problema primal (minimizar) e o dual tiverem solues compatveis finitas, ento Z para
qualquer soluo compatvel do primal e qualquer soluo compatvel do dual.
D
0
D
1
D
n-1
Z
0
Z
1
Z
n-1
Z
*
=D
*
Valor deZ eD

Pesquisa Operacional II Profa. Dra. Llian Ktia de Oliveira

8
Matematicamente falando, isso pode ser representado pela equao:
1 1
n m
j j i i
j i
Z c x wb
= =
= =

.
2. Se ambos os problemas tiverem solues factveis (ou soluo compatvel finita) ento existe uma
soluo tima para cada problema tal que
* *
Z = .
Em outras palavras, o valor factvel mnimo da funo objetivo do primal igual ao valor factvel
mximo da funo objetivo do dual.
Sabe-se, pela definio de valor timo que
*
Z Z e que
*
, isto , a funo z do primal
assume valores cada vez menores at atingir
*
Z e a funo do dual assume valores cada vez
maiores at atingir
*
.
Desse modo a relao Z , que deve ser sempre satisfeita para quaisquer solues factveis do
primal e do dual, tende para a igualdade, pois Z vai diminuindo e vai aumentando.
Matematicamente falando, isso pode ser representado pela equao:
* * * *
1 1
n m
j j i i
j i
Z c x w b
= =
= = =

,
onde:

*
j
x : valor da varivel j do primal na soluo tima do primal;

*
i
w : valor da varivel i do dual na soluo tima do dual.

4.4. Decorrncias
As possveis relaes entre os problemas primal e dual so as seguintes:
1. Se um dos problemas tiver soluo vivel e sua funo objetivo for limitada (portanto, tiver uma
soluo tima), ento o outro tambm ter.
2. Se um dos problemas tiver solues viveis, porm uma funo objetivo ilimitada (portanto, sem
soluo tima), ento o outro no ter solues viveis.
3. Se um dos problemas no tiver soluo vivel, ento o outro no ter solues viveis ou ter
solues ilimitadas.

O Quadro 1 a seguir representa de forma resumida as regras de correspondncias entre o primal
e o dual.


Pesquisa Operacional II Profa. Dra. Llian Ktia de Oliveira

9

Problema de
Minimizao
Problema de
Maximizao

Varivel


irrestrita


=
Restrio
Restrio


=


irrestrita
Varivel

Quadro 1. Regras de Correspondncias entre os problemas primal e dual.

4.5. Extenses do teorema bsico da dualidade
Em relao ao par de problemas duais, exatamente uma e somente uma das afirmaes
verdadeira:
1. Ambos os problemas tem soluo tima finita;
2. Um deles tem valor timo ilimitado e o outro infactvel;
3. Ambos so infactveis.

Exerccio:
Consideremos os seguintes problemas primal e dual:
(PP)
1 2
1 2
1 2
1 2
Max ( )
sujeito a:
1
1
, 0
=

+

z x x x
x x
x x
x x
(PD)
1 2
1 2
1 2
1 2
Max ( )
sujeito a:
1
1
, 0
= +

+

w w w
w w
w w
w w

Represente graficamente cada um dos problemas e verifique que ambos so infactveis.








Pesquisa Operacional II Profa. Dra. Llian Ktia de Oliveira

10

































Pesquisa Operacional II Profa. Dra. Llian Ktia de Oliveira

11
Resumindo
(PP) timo finito
(PP) ilimitado
(PD) ilimitado
(PP) infactvel
(PD) infactvel

(PD) timo finito
(PD) infactvel
(PP) infactvel
(PD) ilimitado/infactvel
(PP) ilimitado/infactvel

4.6. Teorema das folgas complementares
A relao entre os problemas primal e dual maior do que indica o teorema bsico da
dualidade. No apenas os valores timos das funes objetivos so iguais como tambm as solues
bsicas do primal e do dual esto interligadas.
O teorema das folgas complementares permite a determinao da soluo tima do dual, a partir
da soluo tima do primal e vice-versa.
Consideremos o par de problemas:

(PP) (PD)
(I)
1
1
Min ( )
sujeito a:

0, 1,...,
1,...,
=
=
=

=
=

n
j j
j
n
ij j i
j
j
z x c x
a x b
x j n
i m

(II)
1
1
Max ( )
sujeito a:

0, 1,...,
1,...,

=
=
=

=
=

m
i i
i
m
i ij j
i
i
w wb
wa c
w i m
j n


*
x e
*
w so as solues timas, respectivamente de (PP) e (PD), se e somente se,
*
x e
*
w forem
solues viveis e tivermos:

* *
1
0
=

=

n
i ij j i
j
w a x b , 1,..., = i m (A)

* *
1
0
=

=

m
j i ij j
i
c w a x , 1,..., = j n (B)

Observao: Estas so as condies de folga complementar.


Pesquisa Operacional II Profa. Dra. Llian Ktia de Oliveira

12
O teorema de folga complementar muito importante. Ele indica que pelo menos um dos
termos em cada umas das expresses devem ser zeros, isto ,
1.
*
0 >
j
x
*
1
0
m
j i ij
i
c w a
=

=

, ou seja,
*
1
m
i ij j
i
w a c
=
=

(alimento em uso preo ajustado concorre com as plulas)
2.
*
0 =
j
x
*
1 =

m
j i ij
i
c w a
(alimento fora da dieta alimento caro)
3.
*
1 =
>

n
ij j i
j
a x b
*
0 =
i
w
(dieta farta no nutriente nutriente sem preo)
4.
*
0 >
i
w
*
1
0
=

=

n
ij j i
j
a x b , ou seja,
*
1
n
ij j i
j
a x b
=
=

(nutriente com preo usado no padro nutritivo mnimo)
5. Introduzindo as variveis de folga nos problemas (PP) (I) e (PD) (II), isto ,

1
1
1
Min ( )
sujeito a:

, 0, 1,...,
1,...,
=
+
=
+

n
j j
j
n
ij j n i i
j
j n
z x c x
a x x b
x x j n
i m



1
1
Max ( )
sujeito a:

, 0, 1,...,
1,...,

=
+
=
+

+ =

m
i i
i
m
i ij m j j
i
i m j
w wb
wa w c
w w i m
j n

Podemos exprimir as condies de folga complementar do seguinte modo:

Pesquisa Operacional II Profa. Dra. Llian Ktia de Oliveira

13

* *
1
0
+
=
=

n
n i ij j i
j
x a x b
* *
0
+
=
i n i
w x , 1,..., = i m

* *
1
0
n
m j j i ij
j
w c w a
+
=
=

* *
0
+
=
m j j
w x , 1,..., = j n .
Se chamarmos
1 2
, ,...,
n
x x x e
1 2
, ,...,
m
w w w de variveis dadas ou naturais de cada um dos
problemas, vemos pela prpria formulao do dual que cada varivel natural de um problema
corresponde a uma varivel de folga do seu dual e a cada varivel de folga do primal corresponde a
uma varivel natural do dual.
Dadas as solues timas
*
x e
*
w , verificamos que cada par de variveis definido pelas
equaes acima, ao menos uma ser nula.

4.7. Determinao da soluo tima de um problema a partir da soluo tima do seu dual
Seja o (PP)

1 2 3
1 2 3
1 2 3
1 2 3
Min ( ) 2 4
sujeito a:
2 1
2 1
, , 0
z x x x x
x x x
x x x
x x x
= + +
+ +
+

O dual (PD) ser:

1 2
1 2
1 2
1 2
1 2
Max ( )
sujeito a:
2 2
2 1
4
, 0
w w w
w w
w w
w w
w w
=
+

+

Colocando o (PP) na forma padro temos:

1 2 3
1 2 3 4
1 2 3 5
1 2 3 4 5
Min ( ) 2 4
sujeito a:
2 1
2 1
, , , , 0
z x x x x
x x x x
x x x x
x x x x x
= + +
+ + =
+ + =

Pesquisa Operacional II Profa. Dra. Llian Ktia de Oliveira

14
e resolvendo pelo simplex temos a soluo tima
*
1
0 x = ,
*
2
2
3
x = ,
*
3
1
3
x = ,
*
4
0 x = ,
*
5
0 x = e
( )
*
2 z x = .
Resolvendo agora as condies de folga complementar, temos:
( )
* * * *
1 1 2 3
2 1 0 w x x x + + =
*
1
2 1
2*0 1 0
3 3
w

+ + =



( )
* * * *
2 1 2 3
2 1 0 w x x x + =
*
2
2 1
0 2* 1 0
3 3
w

+ =



( )
* * *
1 1 2
2 2 0 x w w + =
( )
* *
1 2
0 2 2 0 w w + =
( )
* * *
2 1 2
2 1 0 x w w =
( )
* *
1 2
2
2 1 0
3
w w = , ou seja,
* *
1 2
2 4 2 w w =
( )
* * *
3 1 2
4 0 x w w + =
( )
* *
1 2
1
4 0
3
w w + = , ou seja,
* *
1 2
4 w w + =
Das equaes acima temos que:

* *
1 2
* *
1 2
2 1
4
w w
w w
=

+ =

o que nos d
*
1
3 w = ,
*
2
1 w = e
( )
*
2 w = .

4.8. Interpretao econmica do problema dual
As variveis originais do problema dual so chamadas de diversas maneiras, dentre as quais
podemos citar Preo-Sombra (Shadow Price) e Valor Implcito. As variveis originais ( )
i
w do
problema dual esto associadas as variveis de folga/excesso introduzidas nas restries do problema
primal representam economicamente o valor marginal do recurso da restrio i em relao ao valor da
funo objetivo, isto , o valor pela qual a funo objetivo seria melhorada, caso a quantidade de
recurso i (representada pela constante da restrio b) fosse aumentada em uma unidade. A interpretao
econmica do teorema da folga complementar pode ser vista de diversas maneiras, dependendo dos
valores das variveis do primal e do dual na soluo tima. Vejamos as interpretaes dos quatro casos
a seguir, aplicados a um problema primal na forma padro.

Caso A:
* *
0 e 0
i n i
w x
+
= >
Como a varivel de folga
*
n i
x
+
maior que zero, na soluo tima (problema primal) temos:

Pesquisa Operacional II Profa. Dra. Llian Ktia de Oliveira

15

* * *
1 1
n n
ij j n i i ij j i
j j
a x x b a x b
+
= =
+ = <

.
Podemos dizer que nem todo recurso i est sendo consumido pelas n atividades, havendo,
portanto, sobra do recurso i. Logo o preo-sombra ( )
i
w deve ser zero.

Caso B:
* *
0 e 0
i n i
w x
+
> =
Como a varivel de folga
*
n i
x
+
igual a zero, na soluo tima (problema primal) temos:

* * *
1 1
n n
ij j n i i ij j i
j j
a x x b a x b
+
= =
+ = =

.
Podemos dizer que todo recurso i est sendo consumido pelas n atividades, no havendo,
portanto, sobra do recurso i. Logo o preo-sombra ( )
i
w deve ser maior que zero.

Caso C:
* *
0 e 0
j m j
x w
+
= >
Como a varivel de folga
*
i
x igual a zero, na soluo tima (problema dual) temos:

* * *
1 1
m m
i ij m j j i ij j
i i
w a w c w a c
+
= =
= >

.
*
1
m
i ij
i
w a
=

representa o valor implcito da produo de uma unidade do produto j. Isto nos leva a
concluir que esta atividade
( )
j
x no seria realizada, pois o custo seria maior que o valor benefcio da
mesma. Ou seja, j que
*
0
j
x = , este no ser produzido ou consumido.

Caso D:
* *
0 e 0
j m j
x w
+
> =
Como a varivel de folga
*
i
x maior que zero, significa que ela estar sendo produzida na
soluo tima. Isto que dizer que o valor implcito da produo de uma unidade do produto j
*
1
m
i ij
i
w a
=

deve ser igual a