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.
\left\{\begin{aligned} \max & f=5 x+y+8 z \\\ \text { s.a. } & 2 x-4 y+z \leq 42 \\\ & 2 x+3 y-z \leq 42 \\\ & 6 x-y+3 z \leq 42 \\\ & x, y, z \geq 0\end{aligned}\right.

Passo 1

Vou listar claramente o que o enunciado nos dá e o que ele pede.
  • O problema primal é:
\begin{aligned} \max\\ & f=5x+y+8z\\\ \text{s.a. } & 2x-4y+z\le 42\\\ & 2x+3y-z\le 42\\\ & 6x-y+3z\le 42\\\ & x,y,z\ge 0. \end{aligned}
  • O que o enunciado pede:
    • Resolver esse PL pelo método do simplex (ou seja, encontrar a solução ótima e mostrar o procedimento do simplex).
    • Escrever o problema dual correspondente.
    • Dizer qual é a solução do dual.
    • Interpretar os resultados: quais restrições estão ativas (binding) ou inativas, valores das folgas (slacks), e a variação marginal (preço sombra) do valor ótimo quando cada restrição é marginalmente relaxada.

Passo 2

Colocar o primal em forma apropriada para aplicar o simplex: introduzimos variáveis de folga (slacks) \,s_1,s_2,s_3\ge0 para transformar desigualdades em igualdades. Escrevendo as igualdades:
\begin{aligned} 2x-4y+z+s_1 &= 42,\\\\ 2x+3y-z+s_2 &= 42,\\\\ 6x-y+3z+s_3 &= 42, \end{aligned}
com x,y,z,s_1,s_2,s_3\ge0. A função objetivo em forma de equação para o tableau é
Z = 5x + y + 8z.
Explicação curta (didática): as variáveis de folga representam quanto sobra entre o lado direito e o lado esquerdo de cada restrição. No tableau inicial, a base inicial natural é s_1=42,\;s_2=42,\;s_3=42 e x=y=z=0. O objetivo do simplex é, iterativamente, entrar com variáveis não-básicas que aumentem Z e pivotar até que nenhum aumento seja possível.

Passo 3

Montagem do tableau inicial (conceito): escrevemos as equações das restrições e a expressão de Z em termos das variáveis não-básicas. O tableau inicial corresponde às equações do Passo 2 com base (s_1,s_2,s_3).
Tabela inicial (coeficientes das equações):
\begin{array}{r|rrr|rrr|r} & x & y & z & s_1 & s_2 & s_3 & \text{RHS}\\hline \text{(1)} & 2 & -4 & 1 & 1 & 0 & 0 & 42\\\ \text{(2)} & 2 & 3 & -1 & 0 & 1 & 0 & 42\\\ \text{(3)} & 6 & -1 & 3 & 0 & 0 & 1 & 42\\hline Z & -5 & -1 & -8 & 0 & 0 & 0 & 0 \end{array}
Comentário didático: na linha Z os coeficientes são -c_j. Para escolher a variável que entra na base, procuramos o coeficiente mais negativo na linha Z (maior potencial de aumento de Z). (Regra usada aqui: entrada pelo maior coeficiente negativo; poderia usar outra regra anti-ciclagem, mas a mais simples serve.)

Passo 4

Primeira iteração do simplex — escolha da variável de entrada e da saída.
  • Observando a linha Z, o coeficiente mais negativo é -8 (variável \,z), então \,z entra na base.
  • Teste da razão (min ratio) para escolher variável que sai: consideramos apenas linhas onde coeficiente de z é positivo.
    • Linha (1): coeficiente de z é 1>0, razão 42/1=42.
    • Linha (2): coeficiente de z é -1<0, ignorar.
    • Linha (3): coeficiente de z é 3>0, razão 42/3=14.
  • A menor razão é 14 (linha (3)), então s_3 sai e z entra. Pivotamos na linha (3), coluna z.
Operação de pivot: dividir a linha (3) por 3 para tornar o pivô igual a 1:
\text{nova (3)}:\quad 2x - \tfrac{1}{3}y + z + \tfrac{1}{3}s_3 = 14.

Passo 5

Atualizar as demais equações eliminando z usando a nova linha (3).
  • Eliminar z da linha (1): nova (1) = (1) − 1×(nova (3)):
    0x +\Big(-4 -\big(-\tfrac{1}{3}\big)\Big)y +0z +1s_1 -\tfrac{1}{3}s_3 = 28,
    que simplifica para
    -\tfrac{11}{3}y + s_1 -\tfrac{1}{3}s_3 = 28.
  • Eliminar z da linha (2): nova (2) = (2) + 1×(nova (3)) (pois coef de z em (2) é -1):
    4x + \tfrac{8}{3}y + s_2 + \tfrac{1}{3}s_3 = 56.
  • Atualizar Z: substituir z pela expressão da nova (3) em Z=5x+y+8z.
    Substituindo z = 14 -2x +\tfrac{1}{3}y -\tfrac{1}{3}s_3, obtemos
    Z = 112 -11x + \tfrac{11}{3}y -\tfrac{8}{3}s_3.
Estado após a 1ª iteração (base atual (s_1,s_2,z)):
\begin{aligned} &-\tfrac{11}{3}y + s_1 -\tfrac{1}{3}s_3 = 28,\\\ &4x + \tfrac{8}{3}y + s_2 + \tfrac{1}{3}s_3 = 56,\\\ &2x -\tfrac{1}{3}y + z + \tfrac{1}{3}s_3 = 14,\\\ &Z = 112 -11x + \tfrac{11}{3}y -\tfrac{8}{3}s_3. \end{aligned}
Didática: agora as variáveis não-básicas são x,y,s_3. Para aumentar Z escolhemos variável não-básica com coeficiente positivo em Z (pois Z está escrito como Z = \text{const} + \sum (\text{coef})\cdot(\text{não-básicas})ãá). Aqui o coef de y em Z é \tfrac{11}{3}>0, então y é candidato a entrar.

Passo 6

Segunda iteração — y entra, escolha da variável que sai:
  • Coeficientes de y nas linhas:
    • linha (1): coef -\tfrac{11}{3}<0 (não é elegível para min ratio),
    • linha (2): coef \tfrac{8}{3}>0 → razão 56/(\tfrac{8}{3}) = 21,
    • linha (3): coef -\tfrac{1}{3}<0 (não elegível).
  • A única linha elegível é a (2), então s_2 sai e y entra. Pivotamos na linha (2) coluna y.
Dividindo a linha (2) por \tfrac{8}{3} (ou multiplicando por \tfrac{3}{8}) para obter coeficiente 1 em y:
\text{nova (2)}:\quad \tfrac{3}{2}x + y + \tfrac{3}{8}s_2 + \tfrac{1}{8}s_3 = 21.

Passo 7

Eliminar y das outras equações e atualizar Z.
  • Atualizar linha (1): nova (1) = (1) + \tfrac{11}{3}×(nova (2)):
    \tfrac{11}{2}x + s_1 + \tfrac{11}{8}s_2 + \tfrac{1}{8}s_3 = 105.
  • Atualizar linha (3): nova (3) = (3) + \tfrac{1}{3}×(nova (2)):
    \tfrac{5}{2}x + z + \tfrac{1}{8}s_2 + \tfrac{3}{8}s_3 = 21.
  • Atualizar Z: substituir y = 21 -\tfrac{3}{2}x -\tfrac{3}{8}s_2 -\tfrac{1}{8}s_3 em Z = 112 -11x + \tfrac{11}{3}y -\tfrac{8}{3}s_3. Fazendo as contas:
    Z = 189 -\tfrac{33}{2}x -\tfrac{11}{8}s_2 -\tfrac{25}{8}s_3.
Estado final do tableau (base (s_1,y,z)):
\begin{aligned} &\tfrac{11}{2}x + s_1 + \tfrac{11}{8}s_2 + \tfrac{1}{8}s_3 = 105,\\\ &\tfrac{3}{2}x + y + \tfrac{3}{8}s_2 + \tfrac{1}{8}s_3 = 21,\\\ &\tfrac{5}{2}x + z + \tfrac{1}{8}s_2 + \tfrac{3}{8}s_3 = 21,\\\ &Z = 189 -\tfrac{33}{2}x -\tfrac{11}{8}s_2 -\tfrac{25}{8}s_3. \end{aligned}

Passo 8

Verificação de otimalidade e leitura da solução primal.
  • As variáveis não-básicas agora são x,s_2,s_3. Observe os coeficientes de x,s_2,s_3 na expressão de Z:
    \;-\tfrac{33}{2},\; -\tfrac{11}{8},\; -\tfrac{25}{8}, todos não positivos.
  • Para maximização, quando todos os coeficientes de não-básicas na expressão de Z são ≤0, chegamos à solução ótima.
Tomando x=s_2=s_3=0 (não-básicas = 0), obtemos das equações:
\begin{aligned} s_1 &= 105,\\\ y &= 21,\\\ z &= 21. \end{aligned}
Portanto a solução ótima primal é
x=0,\qquad y=21,\qquad z=21,
com valor da função objetivo
f_{\max}=Z=5\cdot0 + 1\cdot21 + 8\cdot21 = 21 +168 = 189.
Didática: a folga s_1=105 mostra que a primeira restrição não está totalmente usada (é inativa). As folgas s_2=0 e s_3=0 indicam que as restrições 2 e 3 estão ativas (binding) na solução ótima.

Passo 9

Escrever o problema dual (forma canônica) e explicar a relação primal-dual.
Para o primal no formato \max c^T x s.t. Ax\le b, x\ge0, o dual é \min b^T p s.t. A^T p \ge c, p\ge0.
Aqui b=(42,42,42)^T. Chamando as variáveis duais de p_1,p_2,p_3 (associadas às restrições 1,2,3), o dual é:
\begin{aligned} \min\\ & w = 42(p_1+p_2+p_3)\\\ \text{s.a. } & 2p_1 + 2p_2 + 6p_3 \ge 5 \quad &(\text{para }x)\\\ & -4p_1 + 3p_2 - p_3 \ge 1 \quad &(\text{para }y)\\\ & p_1 - p_2 + 3p_3 \ge 8 \quad &(\text{para }z)\\\ & p_1,p_2,p_3 \ge 0. \end{aligned}

Passo 10

Resolver o dual e interpretar via complementaridade (complementary slackness).
  • Pela complementaridade: se na solução primal x_j>0 então a j-ésima desigualdade do dual é satisfeita com igualdade; se uma restrição primal i é estritamente não ativa (folga positiva) então p_i=0.
  • Na solução primal encontrada temos x=0,\;y=21,\;z=21 e as folgas s_1=105,\;s_2=0,\;s_3=0.
    • Da folga s_1=105>0 decorre p_1=0.
    • Como y>0 e z>0, as desigualdades duais correspondentes a y e z devem ser iguais (binding).
Com p_1=0, impomos as igualdades:
\begin{aligned} 3p_2 - p_3 &= 1,\\\\ - p_2 + 3p_3 &= 8. \end{aligned}
Resolvendo:
  • Da primeira: p_3 = 3p_2 -1.
  • Substituindo na segunda: -p_2 + 3(3p_2 -1) =8 \Rightarrow -p_2 +9p_2 -3 =8 \Rightarrow 8p_2 =11 \Rightarrow p_2 = \tfrac{11}{8}.
  • Então p_3 = 3\cdot\tfrac{11}{8} -1 = \tfrac{33}{8} - \tfrac{8}{8} = \tfrac{25}{8}.
Verificação da primeira desigualdade (para x):
2p_1 +2p_2 +6p_3 = 0 +2\cdot\tfrac{11}{8} +6\cdot\tfrac{25}{8} = \tfrac{22+150}{8} = \tfrac{172}{8} = \tfrac{43}{2} =21{,}5 \ge 5,
satisfeita (estritamente).
Cálculo do objeto dual:
w = 42\big(p_1+p_2+p_3\big) = 42\big(0 + \tfrac{11}{8} + \tfrac{25}{8}\big) = 42\cdot\tfrac{36}{8} = 42\cdot\tfrac{9}{2} = 189.
Assim o dual ótimo é
p_1=0,\qquad p_2=\tfrac{11}{8},\qquad p_3=\tfrac{25}{8},
com valor ótimo w_{\min}=189, que coincide com f_{\max} como previsto pelo teorema da dualidade forte.

Passo 11

Interpretação econômica / sensibilidade (preços sombra e folgas) — explicação didática:
  • Preço sombra p_i é a taxa de variação (marginal) do valor ótimo da função objetivo primal por unidade de aumento do RHS da restrição i (para pequenas variações), assumindo que a base ótima não mude.
    • p_1=0: relaxar (aumentar) a RHS da restrição 1 em uma unidade não altera o valor ótimo (margem zero) — a restrição 1 está inativa (há folga grande s_1=105), portanto é não restritiva naquele ponto.
    • p_2=\tfrac{11}{8}=1{,}375: relaxar a restrição 2 em uma unidade (aumentar o lado direito de 42 para 43) aumenta f_{\max} aproximadamente em 1{,}375, desde que a base ótima permaneça a mesma.
    • p_3=\tfrac{25}{8}=3{,}125: relaxar a restrição 3 em uma unidade aumenta f_{\max} aproximadamente em 3{,}125 (novamente, para pequenas variações sem troca de base).
  • Quais restrições estão ativas/inativas:
    • Restrição 1: inativa (folga s_1=105 positiva) → p_1=0.
    • Restrição 2: ativa (folga s_2=0) → p_2>0.
    • Restrição 3: ativa (folga s_3=0) → p_3>0.
  • Complementaridade: as variáveis primitivas e as desigualdades duais satisfazem a complementaridade (por exemplo, s_1>0 \Rightarrow p_1=0; y>0\Rightarrow desigualdade dual para y é igualdade, etc.), verificado numericamente.
  • Observação prática: esses preços sombra são válidos enquanto pequenas variações nos b_i não mudarem a base ótima. Se a variação for grande o suficiente para fazer uma troca de base, o preço sombra pode mudar e é necessário recalcular.

Resposta

Primal ótimo: x=0,\; y=21,\; z=21,\; f_{\max}=189.
Dual (formulado): \displaystyle \min\; w=42(p_1+p_2+p_3) s.a. \;2p_1+2p_2+6p_3\ge5,\;-4p_1+3p_2-p_3\ge1,\;p_1-p_2+3p_3\ge8,\;p_i\ge0.
Dual ótimo: p_1=0,\; p_2=\tfrac{11}{8},\; p_3=\tfrac{25}{8},\; w_{\min}=189.
Folgas e atividade das restrições: s_1=105 (restrição 1 inativa), s_2=0 (restrição 2 ativa), s_3=0 (restrição 3 ativa).
Variação marginal do ótimo ao relaxar a RHS de cada restrição (preços sombra): variação por unidade = p_1=0,\; p_2=\tfrac{11}{8}=1{,}375,\; p_3=\tfrac{25}{8}=3{,}125.

Exercícios relacionados