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):
\begin{cases} \min & f=3x+8y\\[4pt] \text{s.a.} & 2x+7y \ge 9\\[3pt] & x+2y \ge 4\\[3pt] & x,y\ge 0 \end{cases}
  • Perguntas implícitas que vamos responder:
    1. Resolver este PL usando o método do simplex (obter a solução ótima (x,y) e o valor ótimo f_{\min}).
    2. Escrever o problema dual correspondente e resolver o dual.
    3. 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).
  • Vetor de custos c=(3,8).
Logo o dual é
\begin{cases} \max & z=9u_1+4u_2\\[4pt] \text{s.a.} & 2u_1+u_2 \le 3\\[3pt] & 7u_1+2u_2 \le 8\\[3pt] & u_1,u_2\ge0. \end{cases}
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):
\begin{array}{rcrcrcr} 2u_1 &+& u_2 &+& s_1 &=& 3\\[3pt] 7u_1 &+& 2u_2 &+& s_2 &=& 8\\[3pt] \text{max }z &=& 9u_1 &+& 4u_2 & & \end{array}
Tabela inicial (representação compacta): variáveis (u_1,u_2,s_1,s_2).
Sistema inicial (solução básica simples com s_1=3,\\ s_2=8,\\ u_1=u_2=0).
Vou realizar iterações do simplex passo a passo (explicando cada operação):
Tabela inicial (coeficientes das equações com RHS):
\begin{array}{c|cccc|c} & u_1 & u_2 & s_1 & s_2 & \text{RHS}\\hline \text{(R1)} & 2 & 1 & 1 & 0 & 3\\\ \text{(R2)} & 7 & 2 & 0 & 1 & 8\\hline \text{(z)} & -9 & -4 & 0 & 0 & 0 \end{array}
Na linha de z temos os coeficientes -9,-4 porque estamos maximizando 9u_1+4u_2.
  • Escolha da coluna de entrada: escolhemos a variável com coeficiente mais negativo na linha z, aqui u_1 (coeficiente -9).
  • Razões para escolha da linha de saída: calculamos \text{RHS}/\text{coef coluna} só onde coeficiente da coluna >0:
    • R1: 3/2=1{,}5.
    • R2: 8/7\approx1{,}14286.
      Menor razão é 8/7, então a variável básica que sai é s_2. Pivotamos na entrada (linha R2, coluna u_1).
Pivoteamento 1 (dividir R2 por 7):
\text{R2} \leftarrow \frac{1}{7}\text{R2} \Rightarrow \text{R2}: [1,\;\tfrac{2}{7},\;0,\;\tfrac{1}{7}\;|\;\tfrac{8}{7}].
Atualizamos R1 e linha z eliminando a coluna u_1:
\text{R1}\leftarrow \text{R1}-2\cdot\text{R2},\qquad \text{z}\leftarrow \text{z}+9\cdot\text{R2}.
Fica:
\begin{array}{c|cccc|c} & u_1 & u_2 & s_1 & s_2 & \text{RHS}\\hline \text{(R1)} & 0 & \tfrac{3}{7} & 1 & -\tfrac{2}{7} & \tfrac{5}{7}\\\ \text{(R2)} & 1 & \tfrac{2}{7} & 0 & \tfrac{1}{7} & \tfrac{8}{7}\\hline \text{(z)} & 0 & -\tfrac{10}{7} & 0 & \tfrac{9}{7} & \tfrac{72}{7} \end{array}
  • Agora o coeficiente mais negativo em z é -\tfrac{10}{7} na coluna u_2. Então u_2 entra.
  • Razões para saída (coluna u_2):
    • R1: (5/7)/(3/7)=5/3.
    • R2: (8/7)/(2/7)=4.
      Menor razão é 5/3, então sai s_1. Pivotamos na entrada (R1, coluna u_2).
Pivoteamento 2 (dividir R1 por 3/7, isto é multiplicar por 7/3):
\text{R1}\leftarrow \frac{7}{3}\text{R1} \Rightarrow \text{R1}: [0,\;1,\;\tfrac{7}{3},\;-\tfrac{2}{3}\;|\;\tfrac{5}{3}].
Eliminamos u_2 das outras linhas:
\text{R2}\leftarrow \text{R2}-\tfrac{2}{7}\text{R1},\qquad \text{z}\leftarrow \text{z}+\tfrac{10}{7}\text{R1}.
Resultado final:
\begin{array}{c|cccc|c} & u_1 & u_2 & s_1 & s_2 & \text{RHS}\\hline \text{(R1)} & 0 & 1 & \tfrac{7}{3} & -\tfrac{2}{3} & \tfrac{5}{3}\\\ \text{(R2)} & 1 & 0 & -\tfrac{2}{3} & \tfrac{1}{3} & \tfrac{2}{3}\\hline \text{(z)} & 0 & 0 & \tfrac{10}{3} & \tfrac{1}{3} & \tfrac{266}{21} \end{array}
Observações:
  • 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}).
Portanto o dual tem solução ótima
u_1=\tfrac{2}{3},\qquad u_2=\tfrac{5}{3},\qquad z_{\max}=\tfrac{38}{3}.]

Passo 4

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}
Substituindo (u_1=\tfrac{2}{3},\ u_2=\tfrac{5}{3}]:
2\cdot\tfrac{2}{3}+\tfrac{5}{3}=\tfrac{4}{3}+\tfrac{5}{3}=\tfrac{9}{3}=3,
7\cdot\tfrac{2}{3}+2\cdot\tfrac{5}{3}=\tfrac{14}{3}+\tfrac{10}{3}=\tfrac{24}{3}=8.
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}.
Cálculo do valor objetivo primal:
f_{\min}=3x+8y=3\cdot\tfrac{10}{3}+8\cdot\tfrac{1}{3}=10+\tfrac{8}{3}=\tfrac{30+8}{3}=\tfrac{38}{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):
  1. 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.
  2. 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).
  3. 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.
  4. 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.
  5. 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).
  6. 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”.

Resposta

x^*=\tfrac{10}{3},\;y^*=\tfrac{1}{3},\;f_{\min}=\tfrac{38}{3}.
Dual: \displaystyle \max\\ z=9u_1+4u_2 s.a. \displaystyle 2u_1+u_2\le3,\;7u_1+2u_2\le8,\;u_1,u_2\ge0. Solução: u_1^*=\tfrac{2}{3},\;u_2^*=\tfrac{5}{3},\;z_{\max}=\tfrac{38}{3}.
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}.

Exercícios relacionados