Question 3. (2.0) Considere o problema.
\begin{aligned} \min & 2 u_{1}+u_{2}+4 u_{3} \\\ & -2 u_{1}+u_{2}+u_{3} \geq 1 \\\ & u_{1}-2 u_{2}+u_{3} \geq-1 \\\ & u_{1}, u_{2}, u_{3} \geq 0 \end{aligned}
(a) Encontre o problema dual do problema (8)-(11).
(b) Resolva o problema (8)-(11) usando o Teorema das Folgas Complementares.

Passo 1

O enunciado apresenta o problema de programação linear
\begin{aligned} \min\;&2\,u_{1}+u_{2}+4\,u_{3}\\\ \text{s.a.}\;&-2\,u_{1}+u_{2}+u_{3}\ge1,\\\ &\;u_{1}-2\,u_{2}+u_{3}\ge-1,\\\ &\;u_{1},u_{2},u_{3}\ge0, \end{aligned}
e pede: (a) formular o problema dual; (b) resolver o primal usando o Teorema das Folgas Complementares. Vamos usar as regras padrão de dualidade e depois complementaridade para obter solução ótima.

Passo 2

Para formar o dual, atribuímos variáveis \;y_{1},y_{2}\ge0 às duas restrições do primal (ambas do tipo “ \ge”). O dual será um problema de maximização com as desigualdades “ \le” vindas da coluna de custos do primal. Escrevendo:
\begin{aligned} \max\;&1\cdot y_{1}+(-1)\cdot y_{2}=y_{1}-y_{2}\\\ \text{s.a.}\;& \begin{cases} -2\,y_{1}+1\cdot y_{2}\le2,\\\\ 1\,y_{1}-2\,y_{2}\le1,\\\\ 1\,y_{1}+1\,y_{2}\le4,\\\ y_{1},y_{2}\ge0. \end{cases} \end{aligned}

Passo 3

Vamos resolver o dual graficamente em (y_{1},y_{2}). As fronteiras são:
-2y_{1}+y_{2}=2,\quad y_{1}-2y_{2}=1,\quad y_{1}+y_{2}=4,
além de y_{1}=0 e y_{2}=0. Identificamos os vértices potenciais no primeiro quadrante:
(0,0),\;(1,0),\;(0,2),\;\bigl(3,1\bigr),\;\bigl(\tfrac23,\tfrac{10}3\bigr).

Passo 4

Calculamos y_{1}-y_{2} em cada vértice:
(0,0)\to0,\;(1,0)\to1,\;(0,2)\to-2,\;\bigl(\tfrac23,\tfrac{10}3\bigr)\to-\tfrac83,\;\bigl(3,1\bigr)\to2.
O máximo é 2 em \;(y_{1},y_{2})=(3,1). Logo o valor ótimo do dual é \;2.

Passo 5

Pela complementaridade, quando y_{i}>0\) a restrição \(i\) do primal é ativa; quando a desigualdade \(j\) do dual é estrita, a variável \(u_{j}=0\). Como \(y_{1}=3>0\) e \(y_{2}=1>0\), temos \[\begin{cases} -2\,u_{1}+u_{2}+u_{3}=1,\\\ \;u_{1}-2\,u_{2}+u_{3}=-1. \end{cases}
Das desigualdades do dual em relação a u_{j}\]: \[-2y_{1}+y_{2}=-5<2\implies u_{1}=0,\quad y_{1}-2y_{2}=1=1\implies u_{2}\ge0,\quad y_{1}+y_{2}=4=4\implies u_{3}\ge0.\] Com \(u_{1}=0, as duas equações viram
u_{2}+u_{3}=1,\quad -2u_{2}+u_{3}=-1.
Resolvendo, u_{2}=\tfrac23, u_{3}=\tfrac13.

Resposta

(a) Dual:
\begin{aligned} \max\;&y_{1}-y_{2}\\\ \text{s.a.}\;& \begin{cases} -2\,y_{1}+y_{2}\le2,\\\ y_{1}-2\,y_{2}\le1,\\\ y_{1}+y_{2}\le4,\\\ y_{1},y_{2}\ge0. \end{cases} \end{aligned}
(b) Solução ótima do primal: \;(u_{1},u_{2},u_{3})=(0,\tfrac23,\tfrac13), com valor mínimo 2.

Exercícios relacionados