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.
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:
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
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.
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).
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.
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.
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.
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.