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=x+2 y \\\ \text { s.a. } & x+4 y \leq 8 \\\ & x+y \leq 12 \\\ & x, y \geq 0\end{aligned}\right.

Passo 1

Vou listar claramente o que o enunciado dá e o que pede.
  • O problema primal é
\begin{aligned} \max\\ & f = x + 2y\\\ \text{s.a. } & x + 4y \le 8,\\\ & x + y \le 12,\\\ & x,y \ge 0. \end{aligned}
  • O que o enunciado pede:
    1. Resolver o PL usando o método do simplex (ou seja, encontrar a solução ótima primal).
    2. Escrever o problema dual correspondente.
    3. Dizer qual é a solução do dual.
    4. Interpretar os resultados: quais restrições são ativas/inativas na solução ótima, qual é a variação marginal do valor ótimo da função objetivo se cada restrição for marginalmente relaxada, e comentários relevantes (ex.: relação primal-dual, complementaridade).
  • Informações relevantes do enunciado:
    • Função objetivo linear a maximizar com coeficientes \,1 para x e \,2 para y.
    • Duas restrições do tipo `` \le’’ com termos constantes (RHS) \,8 e \,12.
    • Variáveis não negativas.

Passo 2

Transformação para a forma padrão com variáveis folga (slack) e ideia do simplex.
  • Introduzir variáveis de folga \,s_1 e \,s_2 para transformar as desigualdades em equalidades:
\begin{aligned} x + 4y + s_1 &= 8,\\\ x + y + s_2 &= 12,\\\ x,y,s_1,s_2 &\ge 0. \end{aligned}
  • A função objetivo (forma de trabalho para o tableau) escrevemos como
z - x - 2y = 0,
onde z é a variável que representa o valor objetivo a maximizar.
  • Interpretação do simplex (em linguagem simples): começamos com as variáveis básicas sendo as folgas s_1,s_2 (solução básica inicial x=0,y=0,s_1=8,s_2=12), e tentamos aumentar z trocando uma variável não básica por outra (entrando/saindo da base) enquanto mantemos a factibilidade. Escolhemos a variável que aumenta mais z (regra do custo reduzido) e usamos teste da razão para manter todas as variáveis básicas não negativas.

Passo 3

Montagem do sistema inicial (equações canônicas) que será usado para pivotar.
As equações são:
\begin{aligned} x + 4y + s_1 &= 8,\\\ x + y + s_2 &= 12,\\\ z - x - 2y &= 0. \end{aligned}
Nessa base inicial as variáveis básicas são \,s_1=8,\\ s_2=12,\\ z=0 e as não básicas são x=0,y=0.
Para aplicar o simplex, observamos a equação de z:
z = x + 2y.
Na forma canônica usada por pivot, fica equivalente a
z - x - 2y = 0.
Os coeficientes de x e y em z-linha são -1 e -2. Para maximização, procuramos coeficiente negativo mais negativo (mais “favorável” para entrar). Aqui o mais negativo é -2 (variável y). Logo y entra na base.

Passo 4

Primeiro pivot: entrar [y), sair a variável determinada pelo teste da razão.
  • Coeficientes de y nas duas equações das restrições são 4 (linha 1) e 1 (linha 2), ambos positivos, então aplicamos teste da razão
\frac{\text{RHS}}{\text{coeficiente de }y} = \begin{cases} 8/4 = 2 &\text{(linha 1)},\\\\ 12/1 = 12 &\text{(linha 2)}. \end{cases}
O menor quociente é 2\], portanto a primeira equação limita mais: \(s_1 sai da base e y entra na base.
  • Fazendo o pivot (resolver a 1ª equação para y e substituir nas demais) obtemos as equações atualizadas. Dividindo a 1ª equação por 4:
\frac{1}{4}x + y + \frac{1}{4}s_1 = 2 \quad\Rightarrow\quad y = 2 - \frac{1}{4}x - \frac{1}{4}s_1.
Substituindo nas outras duas equações:
Linha 2 (substituição em x + y + s_2 = 12):
x + \Big(2 - \frac{1}{4}x - \frac{1}{4}s_1\Big) + s_2 = 12
\Rightarrow \frac{3}{4}x - \frac{1}{4}s_1 + s_2 = 10.
Linha z (substituição em z - x - 2y = 0):
z - x - 2\Big(2 - \frac{1}{4}x - \frac{1}{4}s_1\Big) = 0
\Rightarrow z - x - 4 + \frac{1}{2}x + \frac{1}{2}s_1 = 0
\Rightarrow z - \frac{1}{2}x + \frac{1}{2}s_1 - 4 = 0
\Rightarrow z = 4 + \frac{1}{2}x - \frac{1}{2}s_1.
Resumo após o primeiro pivot (base: y, s_2):
\begin{aligned} y &= 2 - \frac{1}{4}x - \frac{1}{4}s_1,\\\ s_2 &= 10 - \frac{3}{4}x + \frac{1}{4}s_1,\\\ z &= 4 + \frac{1}{2}x - \frac{1}{2}s_1. \end{aligned}

Passo 5

Segundo pivot: decidir próxima variável a entrar.
  • Na expressão de z, os coeficientes das não-básicas x e s_1 são \frac{1}{2} e -\frac{1}{2}. Para maximização, uma variável não-básica com coeficiente positivo em z aumenta z se aumentada. O candidato a entrar é x (coeficiente \frac{1}{2}>0). s_1 não entra pois reduziria z.
  • Fazer teste da razão para x nas linhas das variáveis básicas y e s_2. Olhamos as expressões que dão as básicas em função de x:
y = 2 - \frac{1}{4}x - \frac{1}{4}s_1,\quad s_2 = 10 - \frac{3}{4}x + \frac{1}{4}s_1.
Tomando s_1=0 (não básica), as restrições para manter y,s_2\ge0 ao aumentar x são:
y\ge0 \Rightarrow 2 - \frac{1}{4}x \ge 0 \Rightarrow x \le 8,
s_2\ge0 \Rightarrow 10 - \frac{3}{4}x \ge 0 \Rightarrow x \le \frac{40}{3} \approx 13{,}33.
O menor limite é x\le 8 vindo da linha de y. Assim y sai da base e x entra, com valor máximo permitido x=8.

Passo 6

Executar o segundo pivot e obter a solução ótima.
  • A partir da equação original da primeira restrição x + 4y + s_1 = 8, resolver para x quando pivotamos (ou reescrever a relação básica):
x = 8 - 4y - s_1.
  • Substituindo esta relação nas outras equações (ou usando as expressões do passo anterior e substituindo y por sua expressão), obtemos, para a nova base (x, s_2), as equações:
\begin{aligned} x &= 8 - 4y - s_1,\\\ s_2 &= 4 + 3y + s_1,\\\ z &= 8 - 2y - s_1. \end{aligned}
  • Na base atual as variáveis não-básicas são y=0 e s_1=0. Substituindo y=0,s_1=0 obtemos a solução básica factível:
x = 8,\quad y = 0,\quad s_1 = 0,\quad s_2 = 4,
e o valor objetivo
z = 8.
  • Verificação de optimalidade: na forma final z = 8 - 2y - s_1, os coeficientes de y e s_1 são -2 e -1. Como para maximização nenhum coeficiente negativo na linha de z permite aumento de z (nessa convenção de escrita significa que aumentar qualquer não-básica diminui z), a solução atual é ótima. (Outra forma: não há variável não-básica com coeficiente positivo em z na forma que indica aumento do custo reduzido; a conclusão é: solução ótima é x=8,y=0.)

Passo 7

Construção do problema dual e resolução do dual.
  • Regra para construir o dual: o primal é um problema de maximização com duas restrições do tipo ``[\le)’’ e variáveis primal não-negativas. O dual será um problema de minimização com duas variáveis duales não-negativas (uma por restrição primal).
Denotando as variáveis duais por \,u_1 (para a primeira restrição) e \,u_2 (para a segunda), o dual é:
\begin{aligned} \min\\ & z_D = 8u_1 + 12u_2\\\ \text{s.a. } & u_1 + u_2 \ge 1 \quad\text{(coeficiente associado a }x\text{)}\\\ & 4u_1 + u_2 \ge 2 \quad\text{(coeficiente associado a }y\text{)}\\\ & u_1,u_2 \ge 0. \end{aligned}
  • Resolver o dual (método direto / gráfico / inspeção). Procuramos (u_1,u_2)\ge0 que minimize 8u_1+12u_2 sujeito às desigualdades.
Testes por inspeção:
  • Tentar u_1=1,u_2=0: verifica u_1+u_2 =1\ge1 e 4u_1+u_2 =4\ge2. Logo viável. Valor objetivo 8\cdot1 + 12\cdot0 = 8.
  • Tentar resolver as duas restrições como igualdades (ponto de interseção das fronteiras):
\begin{cases} u_1 + u_2 = 1,\\\\ 4u_1 + u_2 = 2, \end{cases}
subtraindo obtém 3u_1 = 1\Rightarrow u_1=\tfrac{1}{3},\\ u_2=\tfrac{2}{3}\]. Valor objetivo \(8\cdot\frac{1}{3} + 12\cdot\frac{2}{3} = \frac{8+24}{3}=\frac{32}{3}\approx 10{,}67, maior que 8. Como o dual é minimização e já encontramos (1,0) com valor 8, este é melhor (menor). Não se consegue valor menor que 8 devido à dualidade fraca (min dual ≥ max primal); como primal já tem solução z=8, pelo teorema da dualidade forte o ótimo dual deve ser 8. Assim a solução ótima do dual é
u_1 = 1,\quad u_2 = 0,
com valor ótimo z_D = 8.

Passo 8

Interpretação econômica/complementaridade e variação marginal (shadow prices).
  • Atividade das restrições (primal) na solução ótima (x,y)=(8,0):
    • Primeira restrição \,x + 4y \le 8: é ativa (binding) na solução ótima porque x + 4y = 8 (slack =0). Também se vê que a variável de folga s_1=0.
    • Segunda restrição \,x + y \le 12: é inativa (não binding) pois x + y = 8 < 12 (slack =4); a folga s_2=4>0.
  • Valores dos multiplicadores duais (preços sombra):
    • u_1 = 1 é o preço sombra associado à primeira restrição.
    • u_2 = 0 é o preço sombra associado à segunda restrição.
  • Interpretação da variação marginal do valor ótimo:
    • Uma pequena relaxação (aumento) da RHS da primeira restrição, b_1, por \Delta aumenta o valor ótimo primal em aproximadamente u_1\cdot\Delta = 1\cdot\Delta. Ou seja, cada unidade adicional permitida na primeira restrição aumenta o valor objetivo ótimo em 1 (desde que a base não mude).
    • Para a segunda restrição, u_2=0, então uma pequena alteração marginal (aumento) em b_2 não altera o valor ótimo primal, até que a base mude (isto é, o preço sombra é zero, não há ganho marginal para pequenas relaxações).
  • Relação de complementaridade (complementary slackness):
    • Como u_1>0, a restrição primal 1 é „ativa‟ (de fato s_1=0).
    • Como u_2=0, a restrição primal 2 pode ser estritamente não ativa (de fato s_2=4>0).
    • Para variáveis primais: a variável x está positiva ( x=8>0), então a restrição dual correspondente (coeficiente para x) deve ser ativa: u_1+u_2 = 1 — com u_1=1,u_2=0 isso é satisfeito. A variável y=0 não precisa ter a desigualdade dual associada saturada (na verdade 4u_1+u_2 = 4 > 2, ou seja, há folga na inequação dual relativa a y) — isso é consistente com y=0.

Passo 9

Intervalos de validade da base (sensibilidade simples das RHS) — até quando os preços-sombra permanecem válidos.
  • Para mantê-la mesma base básica final (variáveis básicas x e s_2), resolver a relação geral das variáveis básicas em função dos RHS (b_1,b_2) com y=0,s_1=0:
    • Das equações originais com y=0,s_1=0:
x = b_1,\qquad s_2 = b_2 - b_1.
Portanto a base permanece factível (com x\ge0,s_2\ge0) enquanto
b_1 \ge 0\quad\text{e}\quad b_2 - b_1 \ge 0 \iff b_2 \ge b_1.
  • Aplicando aos valores originais b_1=8,b_2=12:
    • b_1 pode aumentar até b_2 (ou seja, até 12) sem forçar a troca de base. Assim b_1 admite aumento até +4 unidades (de 8 até 12) mantendo a mesma base; admite decréscimo até 8 (até 0) antes de violar x\ge0.
    • b_2 pode variar para cima sem limite superior (mantém s_2=b_2-b_1\ge0); para diminuir, não pode ficar abaixo de b_1 (ou seja, b_2 mínimo igual a 8). Portanto pequenas relaxações positivas de b_2 não alteram o valor ótimo (preço sombra zero) enquanto b_2 \ge b_1 for respeitado.

Resposta

Primal ótimo: (x,y) = (8,0) com valor ótimo f_{\max} = 8.
Dual: \displaystyle \min\\ z_D = 8u_1 + 12u_2 s.a. \;u_1+u_2 \ge 1,\;4u_1+u_2 \ge 2,\;u_1,u_2\ge0.
Solução do dual: u_1=1,\\ u_2=0 com valor ótimo z_D=8.
Restrições ativas/inativas (primal): primeira restrição x+4y\le8 ativa (binding, folga 0); segunda restrição x+y\le12 inativa (folga 4).
Variação marginal do objetivo para pequenas relaxações das RHS: \partial f^*/\partial b_1 = u_1 = 1 (cada unidade extra na RHS da 1ª restrição aumenta f^* em +1); \partial f^*/\partial b_2 = u_2 = 0 (pequenas aumentos na RHS da 2ª restrição não alteram f^* enquanto a base permanecer).
Intervalos de validade da base (mantendo mesma solução básica x=b_1,\\ s_2=b_2-b_1): requer-se b_1\ge0 e b_2\ge b_1. Para os valores originais ( b_1=8,b_2=12), b_1 pode aumentar até 12 (aumentos até +4) e diminuir até 0; b_2 pode diminuir até 8 e aumentar sem limite, mantendo a mesma base.

Exercícios relacionados