Dualidade: Escrever o dual do PPL abaixo
\begin{aligned} \min z= & 2 x_{1}+x_{2}+4 x_{3} \text { sujeito a: } \\\ & -2 x_{1}+x_{2}+x_{3} \geqslant 1 \\\ & x_{1}-2 x_{2}+x_{3} \geqslant-1 \\\ & x_{1} \geqslant 0, x_{2} \geqslant 0 \text { e } x_{3} \geqslant 0 \end{aligned}

Passo 1

O que o enunciado dá e o que pede.
Dado o problema de programação linear § abaixo:
\begin{aligned} \min z &= 2x_{1}+x_{2}+4x_{3} \\\ \text{sujeito a:}\quad & -2x_{1}+x_{2}+x_{3} \geqslant 1 \\\ & x_{1}-2x_{2}+x_{3} \geqslant -1 \\\ & x_{1}\geqslant 0,\\ x_{2}\geqslant 0,\\ x_{3}\geqslant 0 \end{aligned}
O que se pede: escrever o dual desse problema primal (isto é, formular o problema dual correspondente).
Passo 1 concluído — identifiquei o objetivo (minimizar) e listei todas as restrições e condições de não negatividade.

Passo 2

Escolha do método e ideia central (sem jargão técnico pesado).
Vou derivar o dual usando a construção via multiplicadores (Lagrangeanos) associando uma variável dual a cada restrição do primal. A intuição rápida: cada restrição do primal gera uma variável no dual; como o primal é minimização com restrições do tipo `` \geqslant’’, os multiplicadores associados serão não negativos — vou explicar por quê no próximo passo.

Passo 3

Definir as variáveis duais e o vetor b (o lado direito das restrições).
Associe uma variável dual a cada restrição primal:
\text{variáveis duais: } y_{1}\\ \text{para a 1ª restrição},\quad y_{2}\\ \text{para a 2ª restrição}.áªçãªçã
O vetor dos termos do lado direito das restrições é
b=\begin{pmatrix}1\\\ -1\end{pmatrix},
pois a 1ª restrição tem 1 no lado direito e a 2ª tem -1.

Passo 4

Explicar por que as variáveis duais y_{1},y_{2} têm sinal não negativo.
Rápida aula: ao formar o Lagrangeano para uma restrição do tipo \text{(expressão)} \geqslant \text{constante}ã usamos um multiplicador y\ge 0 e subtraímos y vezes a diferença para montar o Lagrangeano. Se permitíssemos y negativo, ao minimizar sobre x\ge0 o termo linear em x poderia ir para -\infty. Portanto, para garantir que a função dual seja bem comportada (não dê -\infty indevidamente), os multiplicadores correspondentes a restrições do tipo `` \geqslant’’ no primal são não negativos. Assim:
y_{1}\geqslant 0,\quad y_{2}\geqslant 0.

Passo 5

Formar o Lagrangeano e obter as desigualdades do dual (condição de finitude).
Escrevo o Lagrangeano (forma enxuta, sem derivar todo o cálculo, mas com a ideia): se c=(2,1,4)^{T} é o vetor dos coeficientes da função objetivo do primal e A é a matriz das restrições, o Lagrangeano é
L(x,y)=c^{T}x - y^{T}(A x - b)= (c^{T}-y^{T}A)x + y^{T}b.
Para que g(y)=\inf_{x\ge0} L(x,y) seja finito (não -\infty), o coeficiente de cada x_{j} em (c^{T}-y^{T}A) tem de ser não negativo (porque x_{j}\ge0). Isso dá a condição matricial
A^{T}y \le c.
Vou calcular A explicitamente a partir das restrições do primal.

Passo 6

Escrever a matriz A e calcular A^{T}y componente a componente.
As restrições fornecem a matriz A (cada linha é os coeficientes de x_{1},x_{2},x_{3} em cada restrição):
A=\begin{pmatrix} -2 & 1 & 1\\[4pt] 1 & -2 & 1 \end{pmatrix}.
Logo, A^{T} é 3\times 2 e, para y=(y_{1},y_{2})^{T},
A^{T}y= \begin{pmatrix} -2 & 1\\[2pt] 1 & -2\\[2pt] 1 & 1 \end{pmatrix} \begin{pmatrix}y_{1}\\[2pt]y_{2}\end{pmatrix} = \begin{pmatrix} -2y_{1}+y_{2}\\[4pt] y_{1}-2y_{2}\\[4pt] y_{1}+y_{2} \end{pmatrix}.
A condição A^{T}y\le c (com c=(2,1,4)^{T}) gera, componente a componente, as desigualdades
-2y_{1}+y_{2}\le 2,
y_{1}-2y_{2}\le 1,
y_{1}+y_{2}\le 4.]

Passo 7

Determinar a função objetivo do dual.
A função objetivo do dual é b^{T}y (maximizar), onde b=\begin{pmatrix}1\\\ -1\end{pmatrix}. Portanto:
\text{objetivo do dual:}\quad \max\; b^{T}y = \max\; (1)\,y_{1} + (-1)\,y_{2} = \max\; (y_{1}-y_{2}).

Passo 8

Juntar tudo: escrever o problema dual final e explicar cada parte.
Resumindo, o dual é um problema de maximização com variáveis y_{1},y_{2} sujeitas às desigualdades obtidas e à não negatividade:
\begin{aligned} \max\; & y_{1}-y_{2}\\[4pt] \text{sujeito a:}\; & -2y_{1}+y_{2}\le 2\\[4pt] & y_{1}-2y_{2}\le 1\\[4pt] & y_{1}+y_{2}\le 4\\[4pt] & y_{1}\ge 0,\\ y_{2}\ge 0. \end{aligned}
Breve interpretação: cada desigualdade vem da exigência de que o coeficiente associado a x_{1},x_{2},x_{3} no Lagrangeano não permita o infimum ir a -\infty; a função objetivo é formada por combinar os lados direitos do primal com os y.]

Resposta

\begin{aligned} \max\; & y_{1}-y_{2}\\[4pt] \text{sujeito a:}\; & -2y_{1}+y_{2}\le 2\\[4pt] & y_{1}-2y_{2}\le 1\\[4pt] & y_{1}+y_{2}\le 4\\[4pt] & y_{1}\ge 0,\\ y_{2}\ge 0 \end{aligned}]

Exercícios relacionados