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.
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:
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).
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:
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:
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}
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 é:
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).
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).
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.