Teoria da Dualidade na Otimização Linear

Prévia do material em texto

Otimização Linear
Profª : Adriana
Departamento de Matemática
adriana@fc.unesp.br
wwwp.fc.unesp.br/~adriana
Dualidade
✓ A Teoria da Dualidade é um dos mais importantes
tópicos da Programação Linear (PL).
✓ Estudos mostraram que associado a cada modelo
de PL (denominado Primal) há outro modelo
(denominado Dual ) com várias propriedades.
✓ A Dualidade possibilitou o surgimento de
variações do Método Simplex (Método Dual
Simplex ou Métodos Primais-Duais).
Relaxação lagrangiana e o 
problema dual
Problema de otimização linear na forma padrão
Problema 
Primal
matriz mxn
Exemplo:
Possíveis padrões 
de corte
Deseja-se cortar bobinas de aço com largura L = 1 metro e 
pesando 1 tonelada para produzir 108 toneladas de sub-
bobinas de 0,4m e 120 toneladas de 0,3m. O peso total das 
bobinas em estoque cortadas deve ser mínimo. 
Relaxação lagrangiana e o 
problema dual
2 bobinas x 0,4m 
= 0,8m = 4/5
xj: quantidade (em toneladas) de bobinas cortadas segundo 
o padrão de corte j. 
Relaxação lagrangiana e o 
problema dual
✓ Se houver um aumento na demanda de uma das sub-
bobinas, qual é o impacto disso sobre a necessidade de
cortar mais bobinas?
✓ Se considerarmos que o “vetor de recursos” b é
passível de perturbações (incerteza na previsão de
demanda), então a restrição b - Ax = 0 não precisa ser
satisfeita exatamente e podemos analisá-la como um
vetor y = b – Ax.
x* = (35 200 0)T
f (x*) = 235
Relaxação lagrangiana e o 
problema dual
Análise do modelo matemático 
sob outro ponto de vista → novo 
modelo: problema dual
y = b – Ax
Perturbação no vetor b → Ax = b–y (sinal de y é
irrelevante)
✓ Resíduo: y = b-Ax (yi = bi-aix, em que ai =linha i de A) 
✓ Restrição original: y = 0
✓ “Penalidade” ou “custo” por desvio na equação i: i
✓ iyi : custo adicional de perturbar o recurso i em yi
unidades 
Relaxação lagrangiana e o 
problema dual
Problema lagrangiano – problema associado
Relaxação lagrangiana e o 
problema dual
Para cada  = (1, 2, ..., m)
Minimizar f(x) + 1y1 + 2y2 + ... + mym
sujeito a: x ≥ 0
em que y = b - Ax
Função lagrangiana (f.o. do problema lagrangiano):
L(x,) = f(x) + 1y1+ 2y2 +...+mym (função lagrangiana)
= cTx + Ty
= cTx + T(b-Ax)
= (cT- TA)x+ Tb
Seja A = [a1, a2, ..., an] e c = (c1, c2, ..., cn)
(cT- TA) = (c1 - 
Ta1, c2 - 
Ta2 ... cn - 
Tan) 
L(x1, ..., xn, ) = (c1 - 
Ta1)x1 + (c2 - 
Ta2 )x2 + ... + (cn - 
Tan)xn + 
Tb
Relaxação lagrangiana e o 
problema dual
y = b - Ax
L(x1, ..., xn, ) = (c1 - 
Ta1)x1 + (c2 - 
Ta2 )x2 + ... + (cn - 
Tan)xn + 
Tb
Problema lagrangiano (função dual)
g() = min [ (cT- TA)x+ Tb ] 
x  0
g() = min {(c1 - 
Ta1)x1 + (c2 - 
Ta2 )x2 + ... + (cn - 
Tan)xn + 
Tb}
x0
g() = min L(x,) 
x  0
g() = min𝑥1≥0 {(c1 - 
Ta1)x1} + min𝑥2≥0 {(c2 - 
Ta2 )x2} + ... + 
+ min𝑥𝑛≥0 {(cn - 
Tan)xn}+ 
Tb
Relaxação lagrangiana e o 
problema dual
Decomposição em subproblemas menores
0,0,0
120
10
9
5
3
0
1080
5
2
5
4
..
min
321
321
321
321

=++
=++
++
xxx
xxx
xxx
as
xxx
Problema de corte 
Relaxação lagrangiana e o 
problema dual
Função dual 
0,0,0
120108])
10
9
1()
5
3
5
2
1()
5
4
1([),(min)(
321
213222111

++−+−−+−==
xxx
xxxxLg 
0,0,0
),(min)(
321
2211321

++++==
xxx
yyxxxxLg 
2132
0
221
0
11
0
120108)
10
9
1(min)
5
3
5
2
1(min)
5
4
1(min)(
321
 ++−+−−+−=

xxxg
xxx
Relaxação lagrangiana e o 
problema dual
2132
0
221
0
11
0
120108)
10
9
1(min)
5
3
5
2
1(min)
5
4
1(min)(
321
 ++−+−−+−=

xxxg
xxx
Relaxação lagrangiana e o 
problema dual
✓ Se algum coeficiente das variáveis x1, x2, x3 for negativo, 
então g() = - . 
✓ Se os coeficientes das variáveis forem nulos (𝜆1 =
5
4
, 
𝜆2 =
5
6
) então os coeficientes de x1, x2 são nulos e essas 
variáveis podem assumir quaisquer valores não-
negativos sem que a função dual g() se altere.
✓ Com 𝜆1 =
5
4
e 𝜆2 =
5
6
, o coeficiente de x3 > 0 (x3 = 1/4), o 
que implica x3 = 0 para minimizar g().
Restrições dos subproblemas
2132
0
221
0
11
0
120108)
10
9
1(min)
5
3
5
2
1(min)
5
4
1(min)(
321
 ++−+−−+−=

xxxg
xxx
Relaxação lagrangiana e o 
problema dual
✓ A primeira parte de L(x, ) , que depende de x1, x2, x3 é 
sempre -  ou zero. 
✓ Se for zero, então L(x, ) = 1081 + 120 2.
✓ A definição da função dual fornece uma desigualdade 
fundamental da teoria da dualidade: 
✓ limitantes inferiores para os problemas de minimização 
(superiores para problemas de maximização). 
✓ Essa estratégia é muito usada em otimização e é 
chamada relaxação. 
Problema dual
Considere R  S (R é uma relaxação de S) 
 Min xR f(x)  Min xS f(x), R  S
Se x0S é tq f(x0) = min {f(x), x  S} então x0 também pode 
ser um ponto de mínimo de f em R (como R  S, x0R) , 
ou um outro ponto de R pode ser ainda melhor.
Exemplificando...
Considere: R={xRn / x0}  S = {xRn / Ax=b, x0}
g() = Minx0 L(x,) = Minx0 [ c
Tx + T(b-Ax) ]
 MinAx=b, x0 [ c
Tx + T(b-Ax) ] 
= Min f(x)
sujeito a: Ax=b
x0
 f(x), xS
Teorema: g()  f(x), Rm e x tal que Ax=b, x0.
Problema dual
b-Ax=0
Pela definição da função dual...
S
R
Problema primal
f(x) 
xS
primal 
g() R 
dual
1,..., m são chamadas variáveis duais
Devemos procurar  que forneça o maior do limitantes inferiores 
Maximizar g() 
Rm
Problema dual
Definição: O maior limitante inferior para f(x), obtido pela 
função dual, define o problema dual:
A função dual fornece um 
limitante inferior para a f.o. 
primal. 
g() = Minimizarx0 L(x,) = [ (c
T- TA)x+ Tb ]
g() = Minimizar [ (c1 - 
T a1)x1 + (c2 - 
T a2)x2+...+ (cn - 
Tan)xn ] + b
T
x10, x20 ... xn0  variáveis independentes
Para cada escolha das variáveis duais, o problema
lagrangiano é facilmente resolvido como uma soma de n
subproblemas simples. 
g()= Min (c1 - 
T a1)x1 + Min (c2 - 
T a2)x2 +...+ Min (cn - 
Tan)xn + b
T
x10 x20 xn0
Problema dual
Resolução dos subproblemas:
Min (cj - 
Taj)xj 
xj0
T
T
0 se 0
se 0
ij j j
ij j j
x c
x c
 = − 

= − − 
λ a
λ a
Se cj - 
Taj < 0  g() = − → Limitante inferior óbvio!
Devemos escolher  tal que:
cj - 
Taj  0  g() = b
T
Assim: Taj  cj j = 1, ..., n  
TA  cT  AT  c
Problema dual
sem contribuição
xj = 0
Restrição dual
Definição: O conjunto de restrições AT   c é chamado 
de restrições duais e todo vetor  que satisfaça as restrições 
duais é chamado de solução dual factível
Problema primal:
Minimizar f (x) = cTx
sujeito a: Ax = b, x ≥ 0

Problema dual:
Maximizar g() = bT
sujeito a: AT   c
P = {xRn | Ax=b, x0 } D = { Rm | AT   c}
Região factível primal Região factível dual
Problema dual
Problema dual ↔ Problema primal
0,0,0
120
10
9
5
3
0
1080
5
2
5
4
min
321
321
321
321

=++
=++
++
xxx
xxx
xxx
xxx
1
10
9
0
1
5
3
5
2
10
5
4
120108max
21
21
21
21
+
+
+
+




1 2
1 2 1
1 2 2
1 2 3
1 2 3
max 108 120
4
0 1
5
2 3
1
5 5
9
0 1
10
0, 0, 0
 
  
  
  
  
+
+ + =
+ + =
+ + =
  
235)(
6
5
,
4
5
,0,0 2121
=
====


g
folgas
Região dual
gradiente 
do dual
Problema dual ↔ Problema primal
Podemos re-enunciar o teorema:
Problema primal:
Minimizar f (x) = cTx
sujeito a: Ax = b, x ≥ 0

Problema dual:
Maximizar g() = bT
sujeito a: AT   c
P = {xRn | Ax=b, x0 } D = { Rm | AT   c}
(g()  f(x), Rm e x | Ax=b, x0)
Teorema: g()  f(x), xP e D.
Teorema: O dual do problema dual é o primal.
O problema dual é um problema de otimização linear. Qual é 
o dual do dual?
Problema dual ↔ Problema primal
Problema Primal: minimizar, var não-negativas e restrições do tipo 
Min f(x) = c1x1+c2x2
a11x1+ a12x2 = b1
a21x1+ a22x2  b2
x1 0, x2  0
Min f(x) = c1x1+c2x2+0x3
a11x1+ a12x2 + 0x3 = b1
a21x1+ a22x2 + 1x3 = b2
x1 0, x2 0, x3  0

Max g() = b11+b2 2
a11 1 + a21 2  c1
a12 1 + a22 2  c2
0 1 + 1 2  0
Max g() = b11+b2 2
a11 1 + a21 2  c1
a12 1 + a22 2  c2
2  0
Restrição primal   variável dual associada à restrição  0
Problema Dual
Problema dual ↔ Problema primal
Problema Primal: minimizar, var não-negativas e restrições do tipo 
Min f(x) = c1x1+c2x2
a11x1+ a12x2 = b1
a21x1+ a22x2  b2
x1 0, x2  0
Min f(x) = c1x1+c2x2+0x3
a11x1+ a12x2 + 0x3 = b1
a21x1+ a22x2 - 1x3 = b2
x1 0, x2  0, x3  0

Max g() = b11+b2 2
a11 1 + a21 2  c1
a12 1 + a22 2  c2
0 1 - 1 2  0
Max g() = b11+b2 2
a11 1 + a21 2  c1
a12 1 + a22 2  c2
2  0
Restrição primal   variável dual associada à restrição  0
Problema Dual
Problema dual ↔ Problema primal
Problema Primal: maximizar, var não-negativas e restrições de igualdade
Max f(x) = c1x1+c2x2
a11x1+ a12x2 = b1
a21x1+ a22x2  b2
x1 0, x2  0

Max g() = b11+b2 2
a11 1 + a21 2  - c1
a12 1 + a22 2  - c2
2  0
Min -g() = b1(-1)+b2( -2) 
a11 (-1) + a21 ( -2) ≥ c1
a12 (-1) + a22 ( -2) ≥ c2
-2 ≥ 0
1  - 1 2  - 2 e g  - g
Primal (max) : Restrição primal ≤  variável dual associada à restrição 
Problema Dual

Min g() = b11 + b2 2
a11 1 + a21 2  c1
a12 1 + a22 2  c2
2  0
Min - f(x) = - c1x1-c2x2-0x3
a11x1+ a12x2 + 0x3 = b1
a21x1+ a22x2 + 1x3 = b2
x1 0, x2  0, x3  0
Problema dual ↔ Problema primal
Problema Primal: maximizar, var não-negativas e restrições de igualdade
Max f(x) = c1x1+c2x2
a11x1+ a12x2 = b1
a21x1+ a22x2 = b2
x1 0, x2  0
Min - f(x) = - c1x1 - c2x2
a11x1+ a12x2 = b1
a21x1+ a22x2 = b2
x1 0, x2  0

Max g() = b11+b2 2
a11 1 + a21 2  - c1
a12 1 + a22 2  - c2
Min -g() = -b11 - b2 2
- a11 1 - a21 2  - c1
- a12 1 - a22 2  - c2
1  - 1 2  - 2
Problema Dual

Min g() = b11 + b2 2
a11 1 + a21 2  c1
a12 1 + a22 2  c2
Primal (max) : Restrição primal =  variável dual associada à restrição é livre
Resumindo
Regras para construção do 
problema dual
Primal (dual) Dual (primal)
Minimização Maximização
Vetor de recursos Gradiente do objetivo
Gradiente do objetivo Vetor dos recursos
Restrição Variável
Variável Restrição
=

≥
Livre

≥
≥

Livre

≥
=
Exemplo
Escreva o dual a partir do problema primal:
1 2
1 2 3
1 2
1 2 3
max ( ) 2
2 3
3 4 5
0, , 0
f x x x
x x x
x x
x x livre x
= +
− + + 
+ 
 
Exemplo
Dual:
1 2
1 2 1
1 2 2
1 3
a a
1 2
min ( ) 3 5
2 3 1 ( 0)
4 2 ( )
0 ( 0)
0, 0 (1 rest e a 2 rest )
g
x
x livre
x
  
 
 

 
= +
− +  
+ =
 
   
Relações primais - duais
Problema primal:
Minimizar f (x) = cTx
sujeito a: Ax = b
x ≥ 0
Problema dual:
Maximizar g() = bT
sujeito a: AT   c
P = {xRn | Ax=b, x0 } D = { Rm | AT   c}
Região factível primal Região factível dual
Propriedade 1: Suponha que P  ( solução factível primal). O 
problema primal não tem solução ótima se e somente se D= (i.e., no 
caso de minimização, f(x) →- se e somente se não existir solução 
factível dual).
Primal:
maximizar
Propriedade 2: Suponha que D   ( solução factível 
dual). O Problema dual não tem solução ótima se e 
somente se P= (i.e. g() → se e somente se não existir 
solução factível primal).
Ambos os problemas (primal e dual) podem ser infactíveis, 
ou seja: P = e D=.
Relações primais - duais
Propriedade 4: Sejam x*  P e *  D. Se f(x*)=g(* ), então 
x* é solução ótima primal e * é solução ótima dual. 
A recíproca da propriedade 4 também é verdadeira. 
(Teoria das folgas complementares)
Relações primais - duais
Propriedade 3: O problema primal tem solução ótima se 
e somente se o dual tiver solução ótima.
Folgas complementares
P = {xRn | Ax=b, x0 } D = { Rm | AT   c}
Região factível primal região factível dual
Sejam xP e D e suponha que f(x)=g( ), isto é: cTx = Tb.
Substituindo Ax=b, segue-se que cTx = TAx, o que implica : 
(cT- TA)x=0.
1 1
2 2
1 1 1
2 2 2
1 2, 0, 0, , 0
n n
T T
T T
T
n
T T
n n n
a c a c
a c a c
A c
a c a c
  
  
   
  
  + =
 
 + = 
      
 
  + = 
vetor das 
variáveis de 
folga do dual
aj
T  = Taj e (c
T- TA)=(c1- 
Ta1, c2- 
Ta2,..., cn- 
Tan), segue que:
(cT- TA)x=0  (c1- 
Ta1)x1+ (c2- 
Ta2)x2+...+( cn- 
Tan)xn= 0 
1x1+  2x2 +...+  nxn = 0 em que j= cj- 
Taj ≥0.
Como xj = 0, j = 1, 2, ..., n, cada uma das parcelas é não-negativa
Logo: 1x1 = 0, 2x2 = 0, ...,  nxn = 0
1 1
2 2
1 1 1
2 2 2
1 2, 0, 0, , 0
n n
T T
T T
T
n
T T
n n n
a c a c
a c a c
A c
a c a c
  
  
   
  
  + =
 
 + = 
      
 
  + = 
Folgas complementares
Essa relação entre soluções ótimas primal e dual é chamada 
de folgas complementares.
Teorema (folgas complementares): As soluções xRn e  
Rm são ótimas, primal e dual respectivamente, se e 
somente se: 
j
, 0 ( é primal factível)
, 0 ( é dual factível)
0, 1,..., (folgas complementares)
T
j
Ax b x x
A c
x j n
   

= 
+ = 
= =
Folgas complementares
Equações não-lineares
Exemplo
0,0,0
120
10
9
5
3
0
1080
5
2
5
4
min
321
321
321
321

=++
=++
++
xxx
xxx
xxx
xxx
x* = (35 200 0)T
f (x*) = 235
Problema Primal 
Problema Dual 
0,0,0
1
10
9
0
1
5
3
5
2
10
5
4
120108max
321
321
221
121
21

=++
=++
=++
+





1
10
9
0
1
5
3
5
2
10
5
4
120108max
21
21
21
21
+
+
+
+




Exemplo
6
5
,
4
5
21 == 
0,0,0
1
10
9
0
1
5
3
5
2
10
5
4
120108max
321
321
221
121
21

=++
=++
=++
+





Uma solução dual para verificar as 
folgas complementares consiste 
em 1x1= 0, 2x2= 0 e 3x3= 0. 
Devido a solução do problema 
primal, 1= 0, 2= 0 (x1 > 0 e x2 > 0).
1= 0, 2= 0
1
5
3
5
2
10
5
4
21
21
=+
=+


Com esta solução, a terceira 
restrição dual é satisfeita com folga 
(3= 1/4), logo é factível dual.
Exemplo
235)(
6
5
,
4
5
21
=
==


g
f (x*) = 235 = g(*)
Solução 
ótima 
dual 
Resumindo...
x* = (35 200 0)T
6
5
,
4
5
21 == 
Solução 
Primal 
factível
Solução 
Dual 
factível 
Satisfazem as 
folgas 
complementares 
x* = (35 200 0)T
f (x*) = 235
Solução 
ótima 
primal 
Dualidade Forte
P = {xRn | Ax=b, x0 } D = { Rm | AT   c}
Região factível primal região factível dual
Sejam xP e   D. 
Das folgas complementares temos que Tx = 0 e T=(cT-
TA). Substituindo  temos (cT- TA) x=0 ou cTx= TAx . 
Como Ax = b para xP, f(x)= cTx = Tb = g(). 
Teorema (dualidade forte) : As soluções x*  P e *  D são 
ótimas, primal e dual respectivamente, se e somente se 
f(x*) = g(* ).
OBS: As folgas complementares fornecem um caminho para 
se calcular uma solução ótima de um dos problemas, 
quando se conhece a solução ótima do outro.
Exemplo
0,0,0
120
10
9
5
3
0
1080
5
2
5
4
min
321
321
321
321

=++
=++
++
xxx
xxx
xxx
xxx
x* = (35 200 0)T
f (x*) = 235
Problema Primal 
B=
4
5
2
5
0
3
5
→ 𝑥𝐵 =
𝑥1
𝑥2
=
108
200
𝑥𝑁 = (𝑥3)=(0)
 T = cBB
-1= (1 1) 
5
4
−5
6
0
5
3
=
5
4
5
6
Multiplicador simplex (Dual)
Propriedade: O vetor multiplicador simplex na solução 
ótima primal é uma solução ótima dual. 
Exemplo
Como o vetor multiplicador simplex é uma solução dual 
factível, os objetivos primal e dual coincidem. 
g() = Tb = cB
TB-1b = cB
Txb+cB
Txn = f(x)
A condição de otimalidade do problema primal garante que 
o vetor multiplicador seja uma solução ótima dual factível, 
ou seja, para todo i básico, 
 TB = cB
T  Tai = ci
As restrições duais associadas as variáveis básicas são 
satisfeitas com igualdade (restrições ativas em ).
Exemplo
Como o vetor multiplicador simplex é uma solução dual 
factível, os objetivos primal e dual coincidem. 
g() = Tb = cB
TB-1b = cB
Txb+cB
Txn = f(x)Além disso, as restrições duais associadas as variáveis básicas 
são satisfeitas com igualdade (supondo uma base ótima)
Custos relativos: cj - 
Taj ≥ 0 (para todo j não-básico)
Taj ≤ cj
Todas as restrições 
duais são satisfeitas e, 
portanto, T = cB
TB-1 é 
uma solução factível 
dual.