Resolva os seguintes PL utilizando o método do simplex. Escreva o problema dual correspondente e diga qual é sua solução, interpretando os resultados obtidos, tais como, quais restrições são ativas e inativas, qual é a variação marginal no valor ótimo da função objetivo se cada restrição for marginalmente relaxada, etc.
\begin{cases}\min & f=3 x+8 y \\\ \text { s.a. } & 2 x+7 y \geq 9 \\\ & x+2 y \geq 4 \\\ & x, y \geq 0\end{cases}
Passo 1
O que o enunciado pede e o que nos foi dado.
O enunciado nos dá o problema primal (minimização):
Resolver este PL usando o método do simplex (obter a solução ótima (x,y) e o valor ótimo f_{\min}).
Escrever o problema dual correspondente e resolver o dual.
Interpretar os resultados: quais restrições são ativas/inativas, quais variáveis são básicas, e qual a variação marginal (preço-sombra) do valor ótimo quando cada restrição for marginalmente relaxada.
Informações relevantes (retomando em símbolos):
Função objetivo: f(x,y)=3x+8y.
Restrições (R1 e R2): 2x+7y\ge 9 e x+2y\ge 4.
Não-negatividade: x\ge0,\\ y\ge0.]
Passo 2
Decisão do método e por que: vou aplicar o método do simplex, mas é muito prático resolver o dual (um problema de maximização com duas variáveis e duas restrições do tipo [\le)) com o simplex e depois usar complementaridade para recuperar a solução primal. Isso é totalmente válido — é ainda a própria teoria do simplex/dualidade. Vou explicitar tudo passo a passo.
Primeiro, escrevemos o dual do problema primal dado. Regra usada (explicação rápida): para um primal do tipo
\min\; c^T x \quad\text{s.t.}\quad A x \ge b,\quad x\ge0,
o dual é
\max\; b^T u\quad\text{s.t.}\quad A^T u \le c,\quad u\ge0.
Aplicando isso ao nosso caso:
Vetor de RHS b=(9,4).
Matriz A=\begin{pmatrix}2&7\\[2pt]1&2\end{pmatrix} (linhas correspondem às restrições).
Comentário didático: aqui (u_1,u_2] são os multiplicadores (ou preços-sombra) associados às duas restrições do primal. Eles representam a variação marginal do valor ótimo do primal quando se altera levemente o RHS correspondente (mais detalhes depois).]
Passo 3
Resolvendo o dual pelo método do simplex. Primeiro colocamos o dual em forma apropriada (adicionando variáveis folga s_1,s_2\ge0):
Na linha z todos os coeficientes das variáveis de decisão u_1,u_2 são não-negativos (aqui zero), logo a solução é ótima.
Valores básicos (RHS das linhas onde as colunas formam identidade para u_1,u_2):
u_2 = \tfrac{5}{3} (linha R1),
u_1 = \tfrac{2}{3} (linha R2).
Valor ótimo do dual: z_{\max}=\dfrac{266}{21}=\dfrac{38}{3} (verificação: 9\cdot\tfrac{2}{3}+4\cdot\tfrac{5}{3}=\tfrac{18}{3}+\tfrac{20}{3}=\tfrac{38}{3}).
Usando complementaridade para recuperar a solução primal e checar tudo.
Regra de complementaridade (explicação didática simples):
Se em uma solução ótima do dual a desigualdade correspondente a uma variável primal [x_j) é estrita (não ligada), então x_j=0. Se for igualdade, x_j pode ser >0.
Mais diretamente: se x_j>0 então a restrição dual correspondente (coeficiente na linha z) deve ser exatamente igual (ou seja, c_j = (A^T u)_j). Isso dá condições lineares para x.
No nosso caso, as desigualdades do dual são
\begin{cases} 2u_1+u_2 \le 3 &\text{(relacionada a }x\text{)}\\[3pt] 7u_1+2u_2 \le 8 &\text{(relacionada a }y\text{)} \end{cases}
Ambas desigualdades são exatamente iguais (binding), ou seja, as duas restrições do dual são ativas. Pela complementaridade, isso permite que ambas as variáveis primais [x) e y sejam positivas. Então retomamos as restrições primais e as tornamos igualdades (porque os multiplicadores são positivos, as restrições primais também ficam ativas):
Resolver o sistema (restrições primais como iguais):
\begin{cases} 2x+7y=9,\\[3pt] x+2y=4. \end{cases}
Resolvendo (passo a passo):
Da segunda: x=4-2y\].
- Substituindo na primeira:
\[2(4-2y)+7y=9 \Rightarrow 8-4y+7y=9 \Rightarrow 8+3y=9 \Rightarrow 3y=1 \Rightarrow y=\tfrac{1}{3}.\]
- Então \(x=4-2\cdot\tfrac{1}{3}=4-\tfrac{2}{3}=\tfrac{12-2}{3}=\tfrac{10}{3}.
Confirmação de dualidade forte: f_{\min}=z_{\max}=\tfrac{38}{3} — tudo consistente.]
Passo 5
Interpretações e conclusões (o que significam os números):
Solução primal ótima (interpretada):
x^*=\dfrac{10}{3}\approx 3{,}333,
y^*=\dfrac{1}{3}\approx 0{,}333,
valor ótimo f_{\min}=\dfrac{38}{3}\approx 12{,}6667.
Solução dual ótima (preços-sombra):
u_1^*=\dfrac{2}{3},
u_2^*=\dfrac{5}{3},
valor ótimo z_{\max}=\dfrac{38}{3} (igual ao primal).
Restrições ativas/inativas:
No primal: ambas as restrições são ativas (iguais) na solução ótima:2x^*+7y^*=9,\qquad x^*+2y^*=4.Portanto não há folga (slack) nas restrições primais; os termos de folga correspondentes valem zero.
No dual: também ambas as restrições são ativas (isto é, as desigualdades do dual são iguaisidades), o que corresponde ao fato de que ambas as variáveis primais são estritamente positivas.
Variação marginal do valor ótimo se relaxarmos marginalmente cada restrição (interpretação do preço-sombra):
A variação marginal do valor ótimo f_{\min} em relação ao aumento infinitesimal do RHS da restrição 1 (o termo 9) é aproximadamente \dfrac{\partial f^*}{\partial b_1}=u_1^*=\tfrac{2}{3}. Ou seja, aumentar o RHS da R1 de uma unidade (maior exigência: ficar mais rígido) aumenta o custo mínimo em cerca de 0{,}6667.
A variação marginal em relação ao RHS da restrição 2 (o termo 4) é \dfrac{\partial f^*}{\partial b_2}=u_2^*=\tfrac{5}{3}\approx1{,}6667. Ou seja, aumentar b_2 em 1 unidade aumenta o custo mínimo em cerca de 1{,}6667.
Observação sobre sinal: aqui os u_i^* são positivos, o que faz sentido—para um problema de minimização com restrições do tipo \ge, aumentar a exigência (maior RHS) tipicamente aumenta o custo mínimo.
Quais variáveis são básicas/no básico:
No primal: as variáveis básicas na solução ótima são x e y (ambas positivas). As variáveis de folga do primal (se as tivéssemos explicitado, seriam as variáveis de excesso/sobra) seriam zero.
No dual: as variáveis básicas são u_1,u_2 (valores dados) e as folgas do dual são zero (restrições ativas).
Comentário prático para prova:
Resolver o dual quando ele é pequeno (poucas variáveis) frequentemente é mais rápido; depois use complementaridade (se u_i>0 então a i-ésima restrição primal é ativa; se uma desigualdade do dual é estrita então a variável primal correspondente é zero) para recuperar a solução primal.
Os preços-sombra u_i^* são as respostas imediatas para “quanto muda o custo mínimo se eu mudo um pouco o lado direito da i-ésima restrição”.
Restrições ativas no primal: ambas 2x+7y=9 e x+2y=4. Preços-sombra (variação marginal do custo mínimo ao aumentar o RHS): \partial f^*/\partial b_1=u_1^*=\tfrac{2}{3},\\ \partial f^*/\partial b_2=u_2^*=\tfrac{5}{3}.