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

Passo 1

O enunciado dá um problema de programação linear (PL) e pede que se resolva pelo método do simplex, escreva o problema dual correspondente e interprete os resultados (quais restrições são ativas/inativas, variação marginal do valor ótimo se cada restrição for marginalmente relaxada, etc.). As informações fornecidas são:
  • Função objetivo a maximizar: f=x+y.
  • Restrições: \begin{aligned} &x+2y \leq 6,\\\ &3x+2y \leq 12,\\\ &x,\\ y \ge 0. \end{aligned}
  • O que se pede:
    1. Resolver o PL usando o método do simplex (passo a passo).
    2. Escrever o problema dual correspondente.
    3. Dizer qual é a solução do dual.
    4. Interpretar resultados: restrições ativas/inativas e variação marginal do valor ótimo se cada RHS for levemente relaxado.

Passo 2

Colocar o problema em forma padrão (introduzir variáveis folga). Para transformar cada desigualdade do tipo \le em equação, introduzimos as folgas \,s_1 e \,s_2, ambas \ge0:
\begin{aligned} x+2y+s_1 &= 6,\\\\ 3x+2y+s_2 &= 12,\\\ x,y,s_1,s_2 &\ge0. \end{aligned}
A função objetivo é \max f = x+y. No método do simplex é comum escrever a equação do objetivo como
z - x - y = 0,
onde z representa o valor da função objetivo que queremos maximizar.

Passo 3

Identificar a solução factível básica inicial: tomar x=0, y=0 e então s_1=6, s_2=12. Essa é uma solução básica factível inicial (as folgas são as variáveis básicas iniciais). Nesse ponto f=0. Agora preparamos o tableau / sistema para começar a aplicar pivots do simplex.
Escrevendo as equações (forma conveniente para pivoteamento):
\begin{aligned} s_1 &= 6 - x - 2y,\\\ s_2 &= 12 - 3x - 2y,\\\ z &= x + y. \end{aligned}

Passo 4

Regra do simplex (lembrete didático curto e prático):
  • Mantemos sempre as equações na forma “variável básica = RHS - combinações de variáveis não-básicas”.
  • Na linha do objetivo escrevemos z = RHS + coeficientes \times variáveis não-básicas. Para maximização: se existe alguma variável não-básica cuja presença aumenta z ao ser aumentada (veremos isso pelos coeficientes na linha do z), ainda não chegamos ao ótimo; escolhemos uma variável que aumenta z (variável que entra), e aplicamos o teste da razão mínima para escolher qual variável básica sai.
  • Teste da razão mínima: para cada equação básica B_i = b_i - \sum a_{ij} x_j, se na coluna da variável que entra o coeficiente na equação é positivo (na forma B_i + a_{ij} x_j = b_i isso corresponde a a_{ij}>0), calculamos b_i / a_{ij} e a menor razão determina a variável que sai (garante factibilidade).
Vou aplicar essas regras passo a passo.

Passo 5

Primeira iteração: identificar variável que entra.
Da forma escrita:
z = x + y = 0 + 1\cdot x + 1\cdot y.
Aumentar x ou y aumenta z (coeficientes positivos), então podemos escolher entre x e y. Vou escolher x para entrar (poderia escolher y, dá caminho equivalente). Agora aplicar teste da razão mínima para ver quem sai.
Nas restrições (escritas como s_1 = 6 - x - 2y e s_2 = 12 - 3x - 2y), olhando apenas a coluna de x (coeficientes de x nas equações escritas como s_i = b_i - a_{i1} x - \dots):
  • Para s_1: coeficiente de x é 1 (veja forma s_1 = 6 - 1\cdot x - 2y), razão 6/1 = 6.
  • Para s_2: coeficiente de x é 3, razão 12/3 = 4.
    A menor razão é 4, então s_2 sai da base e x entra. O pivot está no coeficiente 3 da segunda equação.

Passo 6

Executar o pivot para trazer x para a base (faço a troca simbólica reescrevendo as equações resolvendo a segunda por x e substituindo nas outras equações).
Da segunda equação:
3x + 2y + s_2 = 12 \quad\Rightarrow\quad x = 4 - \tfrac{2}{3}y - \tfrac{1}{3}s_2.
Substituir essa expressão de x em s_1 e em z:
Em s_1:
s_1 = 6 - x - 2y = 6 - \Big(4 - \tfrac{2}{3}y - \tfrac{1}{3}s_2\Big) - 2y = 2 - \tfrac{4}{3}y + \tfrac{1}{3}s_2.
Em z:
z = x + y = \Big(4 - \tfrac{2}{3}y - \tfrac{1}{3}s_2\Big) + y = 4 + \tfrac{1}{3}y - \tfrac{1}{3}s_2.
Agora as variáveis básicas são x e s_1; as não-básicas são y e s_2. Reescrevendo no formato padrão (variável básica + combinações das não-básicas = RHS):
\begin{aligned} x &+ \tfrac{2}{3}y + \tfrac{1}{3}s_2 = 4,\\\ s_1 &+ \tfrac{4}{3}y - \tfrac{1}{3}s_2 = 2,\\\ z &- \tfrac{1}{3}y + \tfrac{1}{3}s_2 = 4. \end{aligned}

Passo 7

Checar optimalidade nesta tabela parcial:
A linha do z tem coeficiente de y igual a -\tfrac{1}{3} (na forma z + (\cdots)y + (\cdots)s_2 = \text{RHS} aparece como z - \tfrac{1}{3}y + \tfrac{1}{3}s_2 = 4). Como existe um coeficiente negativo associado a uma variável não-básica ( y), ainda podemos aumentar z fazendo y entrar (pela convenção usada: coeficiente negativo na linha de z indica variável que, se aumentada, melhora o objetivo). Portanto prosseguimos: y entra.
Aplicar teste da razão mínima para y. Nas equações básicas (na forma B_i + a_{ij} y = b_i), os coeficientes de y são:
  • Na equação de x: coeficiente de y é \tfrac{2}{3} (positivo), razão 4 / (\tfrac{2}{3}) = 4 \cdot \tfrac{3}{2} = 6.
  • Na equação de s_1: coeficiente de y é \tfrac{4}{3} (positivo), razão 2 / (\tfrac{4}{3}) = 2 \cdot \tfrac{3}{4} = \tfrac{3}{2} = 1{,}5.
    Menor razão é 1{,}5, então s_1 sai da base e y entra. Pivot na equação de s_1, elemento \tfrac{4}{3}.

Passo 8

Pivot para trazer y à base: resolvemos a equação de s_1 por y e substituímos.
Da equação de s_1:
s_1 + \tfrac{4}{3}y - \tfrac{1}{3}s_2 = 2 \quad\Rightarrow\quad \tfrac{4}{3}y = 2 - s_1 + \tfrac{1}{3}s_2
\Rightarrow\quad y = \tfrac{3}{4}\Big(2 - s_1 + \tfrac{1}{3}s_2\Big) = \tfrac{3}{2} - \tfrac{3}{4}s_1 + \tfrac{1}{4}s_2.
Substituir essa expressão de y nas outras equações (para x e z):
Para x (usando x = 4 - \tfrac{2}{3}y - \tfrac{1}{3}s_2):
x = 4 - \tfrac{2}{3}\Big(\tfrac{3}{2} - \tfrac{3}{4}s_1 + \tfrac{1}{4}s_2\Big) - \tfrac{1}{3}s_2 = 4 - 1 + \tfrac{1}{2}s_1 - \tfrac{1}{2}s_2 = 3 + \tfrac{1}{2}s_1 - \tfrac{1}{2}s_2.
Para z (usando z = 4 + \tfrac{1}{3}y - \tfrac{1}{3}s_2):
z = 4 + \tfrac{1}{3}\Big(\tfrac{3}{2} - \tfrac{3}{4}s_1 + \tfrac{1}{4}s_2\Big) - \tfrac{1}{3}s_2 = 4 + \tfrac{1}{2} - \tfrac{1}{4}s_1 + \tfrac{1}{12}s_2 - \tfrac{1}{3}s_2 = \tfrac{9}{2} - \tfrac{1}{4}s_1 - \tfrac{1}{4}s_2.
Agora as variáveis básicas são x e y; as não-básicas são s_1 e s_2. Reescrevendo em forma padrão:
\begin{aligned} x &- \tfrac{1}{2}s_1 + \tfrac{1}{2}s_2 = 3,\\\ y &+ \tfrac{3}{4}s_1 - \tfrac{1}{4}s_2 = \tfrac{3}{2},\\\ z &+ \tfrac{1}{4}s_1 + \tfrac{1}{4}s_2 = \tfrac{9}{2}. \end{aligned}
(Na forma anterior que eu vinha usando, é equivalente escrever x = 3 + \tfrac{1}{2}s_1 - \tfrac{1}{2}s_2, etc.)

Passo 9

Verificação de optimalidade final:
Na linha do z as variáveis não-básicas s_1 e s_2 aparecem com coeficientes negativos quando a escrita é feita como z = \tfrac{9}{2} - \tfrac{1}{4}s_1 - \tfrac{1}{4}s_2. Isso significa que aumentar qualquer variável não-básica ( s_1 ou s_2) diminui z; portanto não existe nenhuma variável não-básica que ao entrar aumente z. Logo a solução atual é ótima.
Leitura direta da solução ótima (fazendo s_1 = s_2 = 0, já que são não-básicas neste ponto):
x = 3,\qquad y = \tfrac{3}{2} = 1{,}5.
Valor ótimo:
f_{\max} = z = x+y = 3 + \tfrac{3}{2} = \tfrac{9}{2} = 4{,}5.

Passo 10

Escrever o problema dual correspondente (regra padrão para dual de um problema primal de maximização com restrições \le):
  • Cada restrição primal gera uma variável dual não-negativa.
  • Coeficientes dos x e y na matriz viram as colunas das desigualdades do dual.
Primal:
\begin{aligned} \max\\ & z = x+y\\\ \text{s.a. }& x+2y \le 6,\\\ & 3x+2y \le 12,\\\ & x,y\ge0. \end{aligned}
Dual (variáveis u_1,u_2\ge0 correspondentes às duas restrições):
\begin{aligned} \min\\ & w = 6u_1 + 12u_2\\\ \text{s.a. }& u_1 + 3u_2 \ge 1\quad(\text{coeficiente de }x),\\\ & 2u_1 + 2u_2 \ge 1\quad(\text{coeficiente de }y),\\\ & u_1,u_2 \ge 0. \end{aligned}

Passo 11

Resolver o dual (método direto / complementaridade). Como nas soluções ótimas obtivemos x>0 e y>0, pelas condições de complementaridade de Karush–Kuhn–Tucker (ou complementaridade no simplex) as desigualdades do dual referentes a x e y devem ser ativas (iguais) no ótimo dual. Assim podemos resolver o sistema de igualdades:
\begin{aligned} u_1 + 3u_2 &= 1,\\\\ 2u_1 + 2u_2 &= 1. \end{aligned}
Resolver esse sistema: da segunda equação 2u_1 + 2u_2 =1 \Rightarrow u_1 = \tfrac{1-2u_2}{2}. Substituindo na primeira:
\tfrac{1-2u_2}{2} + 3u_2 = 1 \quad\Rightarrow\quad 1 - 2u_2 + 6u_2 = 2 \quad\Rightarrow\quad 4u_2 = 1 \quad\Rightarrow\quad u_2 = \tfrac{1}{4}.
Então u_1 = \tfrac{1-2(\tfrac{1}{4})}{2} = \tfrac{1- \tfrac{1}{2}}{2} = \tfrac{\tfrac{1}{2}}{2} = \tfrac{1}{4}.
Avaliar o objetivo dual:
w = 6u_1 + 12u_2 = 6\cdot\tfrac{1}{4} + 12\cdot\tfrac{1}{4} = \tfrac{6+12}{4} = \tfrac{18}{4} = \tfrac{9}{2},
que coincide com o valor ótimo primal (verificação da dualidade forte).

Passo 12

Interpretação dos resultados (didática e prática):
  • Solução primal ótima: \,x=3,\\ y=\tfrac{3}{2} e valor ótimo \,f_{\max}=\tfrac{9}{2}.
  • Solução dual ótima: \,u_1=\tfrac{1}{4},\\ u_2=\tfrac{1}{4} e valor ótimo \,w_{\min}=\tfrac{9}{2}.
  • Restrições ativas/inativas:
    • Ambas as restrições primais são ativas na solução ótima: x+2y = 3 + 2\cdot\frac{3}{2} = 6 e 3x+2y = 9 + 3 = 12. Portanto ambas são vinculadas (binding) e ambas as folgas são zero: s_1=s_2=0.
    • No dual, as duas desigualdades também são ativas (iguais) no ótimo, porque u_1 e u_2 são positivos e as desigualdades tornaram-se igualdades (complementaridade).
  • Variação marginal do valor ótimo ao relaxar cada restrição (interpretação dos preços sombra / multiplicadores duais):
    • O multiplicador dual u_1=\tfrac{1}{4} é o preço-sombra da primeira restrição. Significa que, para uma pequena variação \Delta no RHS da primeira restrição (isto é, mudar 6 para 6+\Delta com \Delta pequeno), o valor ótimo f^* aumenta aproximadamente em \tfrac{1}{4}\Delta.
    • Analogamente, para a segunda restrição o preço-sombra é u_2=\tfrac{1}{4}; aumentar o RHS da segunda restrição em \Delta aumenta f^* em aproximadamente \tfrac{1}{4}\Delta.
    • Observação prática: esses valores marginais são válidos enquanto a base ótima permanecer a mesma (isto é, enquanto as pequenas variações não mudarem o conjunto de restrições ativas). Aqui os dois preços-sombra são iguais, indicando que, localmente, ambas as restrições contribuem da mesma forma por unidade adicional de recurso na melhoria do objetivo.
  • Complementaridade: como x>0 e y>0 no ótimo primal, as desigualdades do dual correspondentes a x e y são iguaisidades no ótimo dual. Como u_1>0 e u_2>0, as duas restrições primais são também iguaisidades no ótimo primal — tudo consistente.

Resposta

Solução primal ótima: x=3,\\ y=\tfrac{3}{2}; f_{\max}=\tfrac{9}{2}.
Problema dual: \min w=6u_1+12u_2 s.a. u_1+3u_2\ge1,\\\ 2u_1+2u_2\ge1,\\ u_1,u_2\ge0. Solução dual ótima: u_1=\tfrac{1}{4},\\ u_2=\tfrac{1}{4}; w_{\min}=\tfrac{9}{2}.
Restrições ativas/inativas: ambas as restrições primais são ativas (binding), x+2y=6 e 3x+2y=12; folgas s_1=s_2=0.
Variação marginal do valor ótimo (preços-sombra): aumentar b_1 (RHS da 1ª restrição) em \Delta aumenta f^* em \tfrac{1}{4}\Delta; aumentar b_2 em \Delta aumenta f^* em \tfrac{1}{4}\Delta.

Exercícios relacionados