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:
Resolver o PL usando o método do simplex (ou seja, encontrar a solução ótima primal).
Escrever o problema dual correspondente.
Dizer qual é a solução do dual.
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
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:
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:
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 é:
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 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.
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.