Considere o PPL a seguir
\begin{aligned} \min & 2 x_{1}+x_{2}+4 x_{3} \\\ & -2 x_{1}+x_{2}+x_{3} \geq 1 \\\ & -x_{1}+x_{2}-x_{3} \leq 1 \\\ & x_{1}, x_{2}, x_{3} \geq 0 \end{aligned}
Resolva o PPL usando o Teorema das Folgas Complementares.

Passo 1

O enunciado dá o PPL
\begin{aligned} \min\;&2x_{1}+x_{2}+4x_{3}\\\ &-2x_{1}+x_{2}+x_{3}\ge1\\\ &-x_{1}+x_{2}-x_{3}\le1\\\ &x_{1},x_{2},x_{3}\ge0 \end{aligned}
e pede para resolver usando o Teorema das Folgas Complementares. O conteúdo aqui é dualidade em Programação Linear e o Teorema das Folgas Complementares, que relaciona soluções ótimas primal e dual.

Passo 2

Formulamos o dual. Chamando y_{1} para a primeira restrição (tipo “ \ge”) e y_{2} para a segunda (tipo “ \le”), temos
\begin{aligned} \max\;&y_{1}+y_{2}\\\ &-2y_{1}-y_{2}\le2\\\ &\,y_{1}+y_{2}\le1\\\ &\,y_{1}-y_{2}\le4\\\ &y_{1}\le0,\;y_{2}\ge0. \end{aligned}

Passo 3

Resolvendo esse dual (por análise dos limites em y_{1}\le0, y_{2}\ge0 e das desigualdades), chega-se ao valor ótimo
\max(y_{1}+y_{2})=1.
Uma família de soluções ótimas é, por exemplo, (y_{1},y_{2})=(0,1), que satisfaz todas as restrições com valor objetivo 1.

Passo 4

Aplicamos Folgas Complementares com (y_{1},y_{2})=(0,1)\). 1. Para cada variável primal \(x_{j}\), se a folga na \(j\)-ésima restrição dual é positiva, então \(x_{j}=0\). As folgas são: \[\begin{cases} 2-(-2y_{1}-y_{2})=2-(-1)=3>0\quad\Rightarrow x_{1}=0,\\\\ 1-(y_{1}+y_{2})=1-1=0\quad\Rightarrow x_{2}\text{ livre (pode ser \(>0)},\ 4-(y_{1}-y_{2})=4-(-1)=5>0\quad\Rightarrow x_{3}=0. \end{cases}]
  1. Para cada restrição primal i, se y_{i}\neq0 então essa restrição primal vale igualdade. Como y_{2}=1\neq0, impomos -x_{1}+x_{2}-x_{3}=1.
Substituindo x_{1}=0 e x_{3}=0 nessa igualdade dá x_{2}=1.

Resposta

(x_{1},x_{2},x_{3})=(0,1,0) com valor ótimo 1.

Exercícios relacionados