Programação Linear 10

Prévia do material em texto

ENP153 –Programação Linear
Aula 10 – Dualidade em Programação Linear
DUALIDADE
 Cada problema de Programa de Programação Linear está
associado a um outro problema de PL que chamamos de
Problema Dual
 O problema original é chamado de Problema Primal
DUALIDADE
 Caso 1: Se o Primal é ilimitado, então o Dual é inviável
 Caso 2: Se o Dual é ilimitado, então o Primal é inviável
 Caso 3: O Primal e o Dual são limitados
 Os valores das funções objetivo das soluções ótimas são
iguais. Se 𝑧∗ é a solução ótima do Primal e 𝑤∗ é a solução
ótima do Dual, então 𝑧∗ = 𝑤∗
 Caso 4: O Primal e o Dual são inviáveis
DUALIDADE
DUALIDADE
DUALIDADE
DUALIDADE
DUALIDADE
 Problema primal
DUALIDADE
 Problema dual
DUALIDADE
TEOREMA DAS FOLGAS COMPLEMENTARES
 𝑥∗, 𝑠∗ é uma solução viável ótima do Primal e 𝑦∗, 𝑡∗ é
uma solução viável ótima do Dual se, e somente se, para
todo 𝑗 ∈ 1,… , 𝑛 , 𝑥𝑗𝑡𝑗 = 0; e, para todo 𝑖 ∈ 1, … ,𝑚 ,
𝑦𝑖𝑠𝑖 = 0, onde 𝑛 é o número de variáveis do primal e 𝑚 é o
número de restrições do primal