Dualidade
Em Programação Linear
Lagrange e penalidades
• Lagrange estudou as relações entre o problema:
• Dados A aberto do Rn, f:A→R e h:A→Rm,
Minimize {f(x) / xєA e h(x)=0}
e o problema penalizado
MinimizexєA f(x)+<λ,h(x)>;
onde <λ,h(x)> corresponde a uma penalização;
Penalização
• Lembrando que
<λ,h(x)>=Σi=1,..m λi hi(x),
a idéia de Lagrange era que o Lagrangeano (a ser
minimizado) fosse “aumentado” para h(x)≠0,i.e,
MinimizexєA f(x)+<λ,h(x)>;
fosse penalizada de forma a
L(x,λ)= f(x)
se h(x)=0
L(x,λ)= “muito grande” se h(x)≠0,
onde L(x,λ)= f(x)+<λ,h(x)>;
Penalização ideal
a idéia de Lagrange pode ser vista como através
do Lagrangeano (a ser minimizado) tivéssemos uma
função objetivo “aumentada” para h(x)≠0,i.e,
MinimizeєA Θ(x);
fosse penalizada de forma a
Θ(x)= f(x) ↔ se h(x)=0
Θ(x)= +∞ ↔ se h(x)≠0,
onde Θ(x) é idealmente penalizada;
Lagrange para Programação Linear
Para o PLC:
MaximizexєX <c,x> onde X={x/x≥0 e Ax=b},
é natural pensarmos em penalizações tais que:
Maximizex≥0 Θ(x);
fosse penalizada de forma a
Θ(x)= <c,x> ↔ se b-Ax=0
Θ(x)= -∞
↔ se b-Ax≠0,
Lagrange para Programação Linear
Para o PLC:
MaximizexєX <c,x> onde X={x/x≥0 e Ax=b},
Maximizex≥0 Θ(x);
ser penalizada de forma a
Θ(x)= <c,x> ↔ se b-Ax=0
Θ(x)= -∞
↔ se b-Ax≠0,
podemos pensar em
Θ(x)= <c,x> +Σ i=1,...m pi (x)
onde
e
pi(x)=0
pi(x)=-∞
se (b-Ax)i =0
se (b-Ax)i ≠0
Lagrange para Programação Linear
Para o PLC:
MaximizexєX <c,x> onde X={x/x≥0 e Ax=b}, se queremos
Maximizex≥0 Θ(x);
Θ(x)= <c,x> +Σ i=1,...m pi (x)
onde pi(x)=0
se (b-Ax)i =0
e pi(x)=-∞
se (b-Ax)i ≠0
uma forma baseada no Lagrangeano é:
• Θ(x)= <c,x> +Σ i=1,...m infλiєR [λi(b-Ax)i] ou
Θ(x)= <c,x> + infλє Rm <λ,b-Ax>
Lagrange para Programação Linear
Para o PLC:
MaximizexєX <c,x> onde X={x/x≥0 e Ax=b}, se queremos
Maximizex≥0 Θ(x);
Θ(x)= <c,x> +Σ i=1,...m pi (x)
a forma baseada no Lagrangeano é:
• Θ(x)= <c,x> + infλє Rm <λ,b-Ax>
= infλє Rm <c,x> + <λ,b-Ax>
= infλє Rm L (x,λ)
Lagrange para Programação Linear
Para o PL≥:
MaximizexєX <c,x> onde X={x/x≥0 e Ax ≥ b}, se queremos
onde
e
Maximizex≥0 Θ(x);
Θ(x)= <c,x> +Σ i=1,...m pi (x)
pi(x)=0
se (b-Ax)i ≥ 0
pi(x)=-∞
se (b-Ax)i <0 (ie, não ≥0 )
a forma baseada no Lagrangeano é:
• Θ(x)= <c,x> +Σ i=1,...m infλi≥0 [λi(b-Ax)i] ou
Θ(x)= infλ≥0 (<c,x>+<λ,b-Ax>)= infλ≥0 L(x,λ)
Lagrange para Programação Linear
Para o Plgeral com x≥0 :
MaximizexєX <c,x> onde X={x/x≥0 e (b-Ax)i @i 0}, se queremos
onde
e
Maximizex≥0 Θ(x);
Θ(x)= <c,x> +Σ i=1,...m pi (x)
pi(x)=0
se (b-Ax)i @i 0
pi(x)=-∞
se (b-Ax)i não @i 0 )
a forma baseada no Lagrangeano é:
• Θ(x)= infλ conveniente (<c,x>+<λ,b-Ax>)
= inf λ conveniente L(x,λ)
EXERCÍCIO:
Apresente o minimax equivalente ao problema geral de PLmax, isto é ,
Especifique tudo para que o PLmax mais geral seja equivalente a
max (xєalgum conjunto) infλ conveniente L(x,λ)
-------------------------------------------Faça o mesmo para PLmin que será equivalente a um
min (xєalgum conjunto) supλ conveniente L(x,λ)
Teorema fraco de dualidade
• Maxinf L(x,λ) ≤ minsup L(x,λ)
isto é, dualidade dá limitantes
.
.
Teorema fraco de dualidade
• Maxinf L(x,λ) ≤ minsup L(x,λ)
isto é, dualidade dá limitantes
ILIMITAÇÂO implica INVIABILIDADE DUAL
.
.
Teorema fraco de dualidade
• Maxinf L(x,λ) ≤ minsup L(x,λ)
isto é, dualidade dá limitantes
Condição suficiente de otimalidade
.
Teorema fraco de dualidade
• Maxinf L(x,λ) ≤ minsup L(x,λ)
isto é, dualidade dá limitantes
Condição suficiente de otimalidade
Condição necessária????
Teorema forte de dualidade
• Maxinf L(x,λ) = minsup L(x,λ)
Condição necessária e suficiente de otimalidade
?
Teorema forte de dualidade
• Maxinf L(x,λ) = minsup L(x,λ)
Condição necessária e suficiente de otimalidade
MAS SERÁ QUE VALE????
Teorema forte de dualidade
• Maxinf L(x,λ) = minsup L(x,λ)
Condição necessária e suficiente de otimalidade
MAS SERÁ QUE VALE????
EM GERAL NÃO
Teorema forte de dualidade
para Programação Linear
• Maxinf L(x,λ) = minsup L(x,λ)
Condição necessária e suficiente de otimalidade
SERÁ QUE VALE????
EM GERAL SIM*
* Só não vale em uma situação pràticamente anomala
Algumas peculiaridades de PL
•
•
•
•
•
•
•
•
1- o dual de um PL é outro PL;
2345678-
Algumas peculiaridades de PL
•
•
•
•
•
•
•
•
1- o dual de um PL é outro PL;
2-o dual do dual de um PL é o problema original;
345678-
Algumas peculiaridades de PL
•
•
•
•
•
•
•
•
1- o dual de um PL é outro PL;
2-o dual do dual de um PL é o problema original;
3-(DLC)= dual do (PLC)
45678-
Algumas peculiaridades de PL
•
•
•
•
•
•
•
•
1- o dual de um PL é outro PL;
2-o dual do dual de um PL é o problema original;
3-(DLC)= dual do (PLC)
4-residuais e sinais de multiplicadores;
5678-
Algumas peculiaridades de PL
•
•
•
•
•
1- o dual de um PL é outro PL;
2-o dual do dual de um PL é o primal;
3- (DLC)= dual do (PLC)
4-residuais e sinais de multiplicadores;
5-Canonizar e dualizar = dualizar e canonizar
• 6- par (PLC, DLC)
• 7• 8-
Algumas peculiaridades de PL
•
•
•
•
•
1- o dual de um PL é outro PL;
2-o dual do dual de um PL é o primal;
3- (DLC)= dual do (PLC)
4-residuais e sinais de multiplicadores;
5-Canonizar e dualizar = dualizar e canonizar
• 6- par (PLC, DLC)
• 7-ilimitação e inviabilidade
• 8-
Algumas peculiaridades de PL
•
•
•
•
•
1- o dual de um PL é outro PL;
2-o dual do dual de um PL é o primal;
3- (DLC)= dual do (PLC)
4-residuais e sinais de multiplicadores;
5-Canonizar e dualizar = dualizar e canonizar
• 6- par (PLC, DLC)
• 7-ilimitação e inviabilidade
• 8-valor ótimo real
CNS de otimalidade
• Um ponto é solução de um Programa linear se
e só se existe um ponto viável dual tal que os
correspondentes (primal e dual)valores de função
objetivo são iguais.
CNS de otimalidade
• Um ponto é solução de um Programa linear se
e só se existe um ponto viável dual tal que os
correspondentes (primal e dual)valores de função
objetivo são iguais.
• Simplex como a luta por viabilidade dual
CNS de otimalidade
• Um ponto é solução de um Programa linear se
e só se existe um ponto viável dual tal que os
correspondentes (primal e dual)valores de função
objetivo são iguais.
• Simplex como a luta por viabilidade dual
• Folgas complementares
Três classes de métodos
baseadas no teorema forte de dualidade
• Um ponto é solução de um Programa linear se
e só se existe um ponto viável dual tal que os
correspondentes (primal e dual)valores de função
objetivo são iguais:
(impor duas das três e buscar a terceira)
• Simplex como a luta por viabilidade dual
• Simplex dual e P.D.: busca de viabilidade primal
• Métodos de redução de “gap”