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.
\begin{cases}\min & f=2 x+2 y \\\ \text { s.a. } & 3 x+y \geq 6 \\\ & -4 x+2 y \geq 2 \\\ & x, y \geq 0\end{cases}

Passo 1

Vou listar claramente o que o enunciado dá e pede.
O enunciado fornece o problema primal:
\begin{aligned} \min\quad & f=2x+2y\\\ \text{s.a.}\quad & 3x+y\ge 6\\\ & -4x+2y\ge 2\\\ & x,y\ge 0. \end{aligned}
O que é pedido:
  • Resolver o problema usando o método do simplex.
  • Escrever o problema dual correspondente.
  • Dizer qual é a solução do dual.
  • Interpretar os resultados: quais restrições são ativas/inativas, qual a variação marginal (senso sombra) no valor ótimo da função objetivo se cada restrição for marginalmente relaxada, etc.
Informações relevantes extraídas do enunciado:
  • Coeficientes da função objetivo: c_x=2,\;c_y=2.
  • Duas restrições do tipo \ge com vetores de coeficientes (3,1) e (-4,2) e lados direitos 6 e 2.
  • Variáveis não negativas: x,y\ge 0.

Passo 2

Comentário sobre o método a usar (por que simplex e qual forma):
O enunciado pede o simplex. Como aqui temos apenas duas variáveis, a ideia fundamental do simplex (percorrer soluções básicas viáveis, que em 2D correspondem aos vértices da região viável) torna-se muito prática: em vez de montar toda a tabela do two-phase, podemos listar as possíveis soluções básicas viáveis (vértices) — isto é perfeitamente consistente com o espírito do simplex (cada vértice corresponde a uma base). Vou portanto identificar os vértices (interseções de pares de restrições / eixos), verificar quais são viáveis e avaliar a função objetivo em cada um — o melhor entre eles é a solução ótima simplex.
Explicação rápida (didática) do porquê isso corresponde ao simplex:
  • No método do simplex, uma solução básica viável é obtida escolhendo um conjunto de m variáveis básicas (aqui m=2, número de restrições) e resolvendo as igualdades correspondentes.
  • Graficamente em 2 variáveis, isso é exatamente o encontro de duas retas (duas restrições transformadas em igualdades).
  • Portanto, listar interseções e avaliar o objetivo é equivalente a testar as bases possíveis no simplex.

Passo 3

Encontrar os vértices candidatos (todas as interseções relevantes entre as restrições e os eixos) e testar viabilidade.
As retas correspondentes às restrições (em igualdade) são:
\text{(1)}\quad 3x+y=6\qquad\text{e}\qquad \text{(2)}\quad -4x+2y=2.
Também consideramos interseções com os eixos [x=0) e y=0 quando aplicável (pois x,y\ge0).
Calculemos as interseções:
  • Interseção de (1) com (2): resolver o sistema
\begin{cases} 3x+y=6,\\[4pt] -4x+2y=2. \end{cases}
Resolvo isolando y\] da primeira: \(y=6-3x. Substituo na segunda:
-4x +2(6-3x) = 2 \quad\Rightarrow\quad -4x +12 -6x = 2 \quad\Rightarrow\quad -10x = -10 \quad\Rightarrow\quad x=1.
Então y=6-3\cdot1=3. Resultado: ponto (1,3).
  • Interseção da restrição (1) com o eixo x=0: pôr x=0 em (1) dá y=6. Ponto (0,6).
  • Interseção da restrição (1) com o eixo y=0: pôr y=0 em (1) dá x=2. Ponto (2,0) — mas é preciso testar a segunda restrição para viabilidade.
  • Interseção da restrição (2) com o eixo x=0: pôr x=0 em (2) dá 2y=2\Rightarrow y=1. Ponto (0,1).
  • Interseção da restrição (2) com o eixo y=0: pôr y=0 em (2) dá -4x=2\Rightarrow x=-\tfrac12, não admissível pois x\ge0.
Agora testar viabilidade (as desigualdades originais) para cada candidato:
  • (1,3): verificar
    3\cdot1+3=6\\ (\text{ok, igual}),\qquad -4\cdot1+2\cdot3 = -4+6=2\\ (\text{ok, igual}).
    Então (1,3) é viável.
  • (0,6): verificar
    3\cdot0+6=6\\ (\text{ok, igualdade}),\qquad -4\cdot0 +2\cdot6 =12\ge2\\ (\text{ok}).
    Então (0,6) é viável.
  • (2,0): verificar
    3\cdot2+0=6\\ (\text{ok}),\qquad -4\cdot2+2\cdot0=-8\ge2\\ ?\\ \text{Não.}ã
    Portanto (2,0) não é viável.
  • (0,1): verificar
    3\cdot0+1=1\ge6\\ ?\\ \text{Não.}ã
    Portanto (0,1) não é viável.
Conclusão: na primeira região do 1º quadrante os vértices viáveis são apenas (1,3) e (0,6). (Isto corresponde às possíveis bases viáveis que o simplex consideraria.)]

Passo 4

Avaliar a função objetivo em cada vértice viável (passo equivalente a comparar valores nas bases testadas pelo simplex).
  • Em (1,3):
f(1,3) = 2\cdot1 + 2\cdot3 = 2 + 6 = 8.
  • Em (0,6):
f(0,6) = 2\cdot0 + 2\cdot6 = 12.
Comparando: 8 < 12. Assim o mínimo ocorre em (1,3) com valor ótimo f_{\min}=8.
Comentário simplex-style: (1,3) é uma solução básica viável (duas restrições ativas = base), e é a melhor entre as bases testadas — portanto é ótima (em problemas lineares finitos, comparar bases é o que o simplex faz ao pivoteamento).

Passo 5

Escrever o problema dual e resolver (didático: como construir o dual).
Regra geral (caso usado aqui): para o primal na forma
\min\{c^T x\;|\;A x \ge b,\; x\ge0\},
o dual é
\max\{b^T u\;|\;A^T u \le c,\; u\ge0\}.
Aplicando isso ao nosso primal:
  • b=(6,2)^T.
  • A matriz A tem linhas (3,1) e (-4,2).
  • c=(2,2)^T.
Logo o dual é
\begin{aligned} \max\quad & g=6u_1+2u_2\\\ \text{s.a.}\quad & 3u_1 -4u_2 \le 2\\\ & u_1 + 2u_2 \le 2\\\ & u_1,u_2\ge 0. \end{aligned}
Agora resolvemos o dual. Novamente é um problema em 2 variáveis; podemos resolver graficamente/listando vértices das desigualdades:
As retas correspondentes às igualdades são
3u_1 -4u_2 = 2,\qquad u_1+2u_2=2,
com u_1,u_2\ge0.
Interseção dessas duas igualdades: isolo u_1 = 2 - 2u_2 da segunda e substituo na primeira:
3(2-2u_2) - 4u_2 = 2 \quad\Rightarrow\quad 6 -6u_2 -4u_2 =2 \quad\Rightarrow\quad -10u_2 = -4 \quad\Rightarrow\quad u_2 = \tfrac{2}{5}.
Então u_1 = 2 -2\cdot\tfrac{2}{5} = 2 - \tfrac{4}{5} = \tfrac{6}{5}.
Verifico que u_1,u_2\ge0 e as desigualdades são satisfeitas com igualdade (por construção). O valor objetivo é
g\!\left(\tfrac{6}{5},\tfrac{2}{5}\right) = 6\cdot\tfrac{6}{5} + 2\cdot\tfrac{2}{5} = \tfrac{36}{5} + \tfrac{4}{5} = \tfrac{40}{5} = 8.
Isso bate com o valor ótimo primal por dualidade forte (confirmação extra de que ambos ótimos valem 8).

Passo 6

Interpretação (complementaridade, ativos/inativos, variação marginal — “preços sombra”).
  1. Quais restrições primais são ativas/inativas na solução ótima primal (1,3)?
  • Ambas as restrições são ativas (binding): em (1,3) temos 3\cdot1+3=6 e -4\cdot1+2\cdot3=2. Portanto ambas são iguaisidades no ótimo.
  1. Quais desigualdades do dual são ativas/inativas na solução ótima dual (u_1,u_2)=(\tfrac{6}{5},\tfrac{2}{5})?
  • Ambas as desigualdades do dual são ativas (iguais): 3u_1-4u_2=2 e u_1+2u_2=2. Isto também é consistente com o fato de que as variáveis primais x e y são estritamente positivas ( x=1>0,\;y=3>0); pela complementaridade, variáveis primais positivas implicam que as restrições dual correspondentes são justas (igualdades).
  1. Relação complementar (explicando didaticamente):
  • Regra da complementaridade: para cada restrição primal i com variável dual u_i, se a restrição primal não está ativa então u_i=0. Aqui ambas estão ativas, por isso u_1,u_2 podem ser não nulos — de fato são positivos.
  • Para cada variável primal j, se x_j>0 então a correspondente restrição dual (sobre u) é igualdade. Aqui x_1>0,x_2>0 e ambas as restrições dual são iguais.
  1. Variação marginal no valor ótimo se uma restrição for marginalmente relaxada (interpretação do preço sombra):
  • Em termos gerais: para pequenas variações \Delta b no lado direito b do primal, a mudança aproximada no valor ótimo primal f^* é \Delta f^* \approx u^T \Delta b, onde u é a solução dual ótima. Aqui cada componente u_i é o “preço sombra” associado à restrição i.
  • No nosso caso, u_1=\tfrac{6}{5}=1{,}2 e u_2=\tfrac{2}{5}=0{,}4.
Interpretação numérica concreta:
  • Se a primeira restrição (aquela com RHS 6) for relaxada diminuindo seu RHS em 1 unidade (ou seja, de 6 para 5), a função objetivo mínima diminui aproximadamente em u_1\cdot 1 = \tfrac{6}{5}=1{,}2. (Relaxar uma restrição \ge significa tornar o lado direito menor; para minimização isso tende a reduzir o custo.)
  • Se a segunda restrição (RHS 2) for relaxada diminuindo seu RHS em 1 unidade (de 2 para 1), o valor ótimo diminui aproximadamente em u_2\cdot 1 = \tfrac{2}{5}=0{,}4.
Observação sobre sinal: a fórmula \Delta f^*\approx u^T\Delta b é válida com \Delta b signado (se \Delta b for negativo, o custo diminui). Por exemplo, diminuir b_1 em 1 (relaxar) corresponde a \Delta b_1=-1, então \Delta f^*\approx u_1(-1)=-1{,}2, ou seja o ótimo diminui em 1{,}2.
  1. Interpretação econômica / prática (de forma leve):
  • A primeira restrição é “mais cara” de relaxar: cada unidade de folga que se ganha na primeira restrição reduz o custo ótimo em 1{,}2, enquanto na segunda cada unidade reduziu somente 0{,}4. Logo, se eu puder gastar um recurso que torna a primeira restrição mais fácil, isso me traz maior redução no custo do que fazer o mesmo com a segunda.

Resposta

Primal ótimo: x=1,\;y=3 com f_{\min}=8.
Dual (formulado): \displaystyle \max\; g=6u_1+2u_2 sujeito a \displaystyle 3u_1-4u_2\le2,\; u_1+2u_2\le2,\; u_1,u_2\ge0.
Solução do dual: u_1=\tfrac{6}{5},\;u_2=\tfrac{2}{5} com g_{\max}=8.
Restrições ativas/inativas: ambas as restrições primais são ativas (iguais) em (1,3); ambas as restrições do dual são ativas em (\tfrac{6}{5},\tfrac{2}{5}).
Variação marginal (preços sombra): \displaystyle \frac{\partial f^*}{\partial b_1}=u_1=\tfrac{6}{5}=1{,}2 e \displaystyle \frac{\partial f^*}{\partial b_2}=u_2=\tfrac{2}{5}=0{,}4. Ou seja, reduzir o RHS da primeira restrição em 1 reduz o custo ótimo em aproximadamente 1{,}2; reduzir o RHS da segunda restrição em 1 reduz o custo ótimo em aproximadamente 0{,}4.

Exercícios relacionados