Dualidade

!"
#
%
&

$
'(
(

Tema da aula de hoje
->Dualidade
• Formulação do dual
• Teoremas básicos
• Propriedades

Dualidade
A cada modelo de Programação Linear, a partir de agora
denominado de problema Primal (P), corresponde um outro
denominado de problema Dual (D).
No problema primal, busca-se a otimização dos níveis de
atividades das variáveis de decisão, entendidas como asvariáveis
reais do problema em análise.

Dualidade
No problema dual, a preocupação se dá com os recursos
disponíveis.
Além disso, as soluções dos dois problemas estão de tal modo
inter-relacionados que, na solução ótima do problema Primal, é
possível reconhecer-se a solução Dual.
Inversamente, na solução ótima do Dual identifica-se a
solução Primal.

Dualidade
Dado o PPL:
Max z = CXs.a.
AX B
X0
Em contrapartida está associado a este problema chamado
dual, que pode ser determinado pela transposta da matriz:

Min w=BY
s.a.
AT Y C
Y0

Dualidade

Propriedade 1) O dual do dual é o primal.
1) Troca-se os sinais da função objetivo para
buscar-se a maximização da expressão
simétrica e multiplicam-se as desigualdades
por (-1) para invertê-las, obtendo-se o
problema(P’).
2) Ao primal, aplica-se, então a transformação
básica para o dual (D’)
3) Fazer a transformação da função objetivo
do problema (D’) para maximização e
multiplicando-se as restrições por (-1) para
alterar seus sentidos, resulta o modelo (D).

Propriedades
Propriedade 1 - O dual do problema dual é igual ao problema primal.
Exemplo 2:
max

max Z = 2 x1 − 2 x 2 + x 3

Z = 2 x1 − 2x 2 + x 3
s .a

s .a
x 1 + x 2 + x 3 ≥ 10
3 x 1 − 2 x 2 − 2 x 3 ≥ 20
x 1 − x 2 − x 3 ≥ 25

− x1 − x 2 − x 3 ≤ − 10

(P)

− 3 x1 + 2 x 2 + 2 x 3 ≤ − 20
− x1 + x 2 + x 3 ≤ − 25

x1 , x 2 , x 3 ≥ 0

x1 , x 2 , x 3 ≥ 0

o dual de (P’) é:
min

D = − 10 y 1 − 20 y

2

− 25 y 3

s .a
− y1 − 3 y

2

− y3 ≥ 2

− y1 + 2 y

2

+ y3 ≥ −2

2

+ y3 ≥ 1

− y1 + 2 yy1 , y 2 , y 3 ≥ 0

(P’)

vi = − yi

Mudança de variáveis:
min

D = 10 v 1 + 20 v

2

+ 25 v 3

s .a
v1 + 3 v

2

+ v3 ≥ 2

v1 − 2 v

2

− v3 ≥ − 2

v1 − 2 v

2

− v3 ≥ 1

v1 , v 2 , v 3 ≤ 0

Propriedades
Propriedade 1 - O dual do problema dual é igual ao problema primal.
Exemplo (continuação da demonstração):
min

D = 10 v 1 + 20 v

2

+ 25 v 3

s.a
v1 + 3 v

2

+ v3 ≥ 2

v1 − 2 v

2

− v3 ≥ − 2

v1 − 2 v

2

− v3 ≥ 1

v1 , v
max

,v3 ≤ 0

2

R = 2 x1 − 2 x

2

+ x3

s .a
x1 + 1v

2

+ v 3 ≤ 10

3 x1 − 2 v

2

x1 − 1 x

− x 3 ≤ 25

x1 , x

2

2

− 2 v 3 ≤ 20

, x3 ≥ 0

Propriedades
Propriedade 2 - Se uma restrição do problema (P) é do tipo (=), então a
variável correspondente noproblema (D) é “irrestrita em sinal”.

Determinar o dual do problema (P):
(P) max Z = 3x1 – 4x2
Sujeito a 5x1 – 3x2 ≤ 4
–2x1 + 5x2 = 7
x1, x2 ≥ 0
Para o modelo (P) recair no padrão desejado, pode-se, em lugar da igualdade,
escrever duas desigualdades, com sentidos opostos. A seguir, multiplicando-se a
última delas por (–1) tem-se o modelo (P’) com três desigualdades de mesmo
sentido (≤),compatíveis com a maximização:
(P´) max Z = 3x1 – 4x2
Sujeito a 5x1 – 3x2 ≤ 4 [y1]
–2x1 + 5x2 ≤ 7 [y2]
2x1 – 5x2 ≤ -7 [y3]
x1, x2 ≥ 0

Propriedades
Propriedade 2
(D´) Min D = 4y1 + 7y2 - 7y3
Sujeito a 5y1 – 2y2 + 2y3 ≥ 3
–3y1 + 5y2 -5y3 ≥ -4
y1, y2, y3 ≥ 0
Observando-se os coeficientes das variáveis y2 e y3, nota-se que uma é inversa da
outra. Isto sugere a transformação devariáveis w= y2 -y3 , que leva ao modelo (D):
(D) Min D = 4y1 + 7w
Sujeito a 5y1 – 2w ≥ 3
–3y1 + 5w ≥ -4
y1≥ 0, w irrestrito em sinal

Para escrever o modelo (P) de acordo com padrão,
deve-se multiplicar a segunda restrição por (–1),
passando ao modelo (P’ ), ao qual aplica-se a
transformação básica, que leva ao modelo (D’ ):

Caso se faça a seguinte troca de variável: w = – y2,
o sistema...