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:
Resolver o PL usando o método do simplex (passo a passo).
Escrever o problema dual correspondente.
Dizer qual é a solução do dual.
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:
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:
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):
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.
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):
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:
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.