Considere o PPL a seguir.
e o seu dual.
onde
e
.
(1) Seja
uma solução viável para o problema (12)-(14) e
uma solução viável para o problema (15)-(17). Mostre que
.
(1) Seja
Passo 1
O enunciado traz o problema primal
e o dual
Queremos mostrar que, para qualquer viável
e
, vale a desigualdade de dualidade fraca
Passo 2
Como
e
, podemos multiplicar
por
à esquerda sem inverter o sinal, obtendo
Passo 3
Pela viabilidade dual temos
Como
, multiplicamos termo a termo e somamos, o que dá
Passo 4
Unindo as desigualdades dos passos anteriores, chega-se a
portanto