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.
Pede resolver o problema de programação linear (PL) pelo método do simplex, escrever o problema dual correspondente e dizer qual é a solução do dual, interpretando os resultados (quais restrições são ativas/inativas, variação marginal do valor ótimo se cada restrição for marginalmente relaxada, etc.).
Duas restrições do tipo \ge (isso implica, no método simplex direto, necessidade de variáveis de excesso e artificiais se formos trabalhar o primal).
Todas as constantes (coefs) já estão no enunciado: 5,1,9 e 2,2,10.]
Passo 2
Escolha do método e por quê (seguindo o algoritmo de escolha indicado).
O problema primal é uma minimização com duas restrições do tipo \ge. Aplicar simplex direto ao primal exigiria introduzir variáveis de excesso e variáveis artificiais e fazer a fase 1 (ou usar Big‑M). Isso gera cálculo extra.
Em vez disso, é mais simples e didático formar o problema dual (que será um problema de maximização com desigualdades do tipo \le) e resolver o dual com o método simplex padrão (forma canônica com folgas). Pelo teorema da dualidade forte, a solução ótima do dual dá o valor ótimo do primal e, via complementaridade, permite recuperar a solução primal.
Vou, portanto, formar o dual e resolver o dual pelo simplex (explico cada passo).
Passo 3
Formação do problema dual — regras e aplicação.
Regra utilizada (caso geral): para um primal na forma
minimizar c^T x\) sujeito a \(A x \ge b\), \(x\ge 0\),
o dual é
- maximizar \(b^T u\) sujeito a \(A^T u \le c\), \(u\ge 0\).
- Aplicando isso ao nosso problema:
- \(c=\begin{pmatrix}2\\[2pt]1\end{pmatrix}\), \(b=\begin{pmatrix}9\\[2pt]10\end{pmatrix}\) e
\[A=\begin{pmatrix}5 & 1\\[2pt]2 & 2\end{pmatrix}
(cada linha corresponde a uma restrição do primal).
Então o dual (chamando as variáveis do dual de u_1 e u_2, ambas \ge 0) é:
Observação: este é um problema de maximização com duas restrições (\le] e variáveis não negativas — pronto para aplicar o simplex padrão.]
Passo 4
Colocando o dual em forma padrão para simplex (introduzindo variáveis de folga) e inicialização.
Introduzimos variáveis de folga s_1\) e \(s_2\) (\(\ge 0\)) para transformar as desigualdades em igualdades:
\[\begin{cases} 5u_1+2u_2 + s_1 = 2\\[4pt] u_1+2u_2 + s_2 = 1\\[4pt] u_1,u_2,s_1,s_2\ge 0 \end{cases}
A função objetivo é w=9u_1+10u_2\]. No tableau inicial, as variáveis básicas são \(s_1=2 e s_2=1 (com u_1=u_2=0), e o valor inicial de w é 0.
Vou apresentar as iterações do simplex de forma clara (cada linha é uma equação da base). Começamos com base \{s_1,s_2\}.]
Passo 5
Primeira iteração do simplex no dual — escolha da variável que entra e pivoteamento.
Calculamos os custos reduzidos iniciais: coeficientes objetivo de u_1,u_2 são 9 e 10; ambos positivos (maximização), então entram candidatos.
Escolhemos a variável com maior custo reduzido: u_2 (coeficiente 10) entra na base.
Razões para escolha da linha pivô (razão RHS/coef coluna u_2):
Para a primeira equação: razão 2/2=1.
Para a segunda equação: razão 1/2=0,5.
Menor razão é 0,5 (linha 2), então a linha 2 é pivô e s_2 sai da base.
Pivoteando (dividindo a linha 2 por 2 e eliminando u_2 das outras linhas), obtemos a nova base \{s_1,u_2\} com a solução básica:
Linha 1 (nova): s_1 = 1 - 4u_1 + 1\cdot s_3 (aqui mostro a evolução numérica abaixo de forma direta).
Valor parcial do objetivo: w = 10 \cdot 0,5 = 5.
(Obs.: para economia de espaço e clareza, os cálculos elementares de eliminação são feitos explicitamente nos próximos passos; o pivô foi na linha 2, coluna u_2.)
Passo 6
Segunda iteração do simplex no dual — completar o pivoteamento e verificar optimalidade.
Depois do primeiro pivô, a tabela ficou com base \{s_1,u_2\} e os custos reduzidos indicavam que u_1 ainda tem custo reduzido positivo (valor 4 no novo tableau), então u_1 entra.
Cálculo das razões para a coluna u_1 com as duas linhas básicas:
Linha 1 (atualizada): RHS =1, coef. de u_1=4 → razão 1/4=0{,}25.
Linha 2 (atualizada, que é a linha de u_2): RHS =0{,}5, coef. de u_1=0{,}5 → razão 0{,}5/0{,}5=1.
Menor razão é 0{,}25 (linha 1). Logo s_1 sai e u_1 entra.
Pivoteando na linha 1 coluna u_1 (dividindo a linha por 4 e eliminando u_1 das demais linhas) obtemos a base \{u_1,u_2\}.
Verificação de optimalidade: todos os custos reduzidos das variáveis não básicas são \le 0 (maximização), portanto a solução é ótima.
Passo 7
Conclusão do dual e interpretação imediata (valores do dual e valor ótimo).
Solução ótima do dual:u_1^\star = \tfrac{1}{4},\qquad u_2^\star = \tfrac{3}{8}
Valor ótimo do dual:w^\star = 6.
Pelo teorema da dualidade forte, o valor ótimo do primal é igual a w^\star, isto é f_{\min}=6.
Passo 8
Recuperando a solução primal via complementaridade (explicando didaticamente o que é complementaridade).
Regra de complementaridade (explicada de forma simples): para primal e dual ótimos,
para cada variável primal x_j\): \(x_j>0\) implica que a \(j\)-ésima desigualdade do dual é exatamente satisfeita (é igualdade); e se a desigualdade do dual é estritamente menor que o limite, então \(x_j=0\).
- para cada variável dual \(u_i\): \(u_i>0\) implica que a \(i\)-ésima restrição primal é ativa (igualdade); se a \(i\)-ésima restrição primal é estrita (não é ativa), então \(u_i=0\).
- Aplicando isso:
- No dual, as duas desigualdades ficaram com igualdade na solução (verificável):
\[5u_1+2u_2 = 5\cdot\tfrac{1}{4} + 2\cdot\tfrac{3}{8} = 1{,}25+0{,}75 = 2,
Assim ambas as restrições do dual são ativas, o que permite que \(x\) e \(y\) sejam possivelmente positivos.
No primal, as duas variáveis dual u_1,u_2 são estritamente positivas (\tfrac{1}{4} e \tfrac{3}{8}). Pela complementaridade isso implica que ambas as restrições do primal são ativas (iguais).
Logo resolvemos o sistema das restrições ativas do primal:
Solução primal obtida:x^\star = 1,\qquad y^\star = 4,\qquad f(x^\star,y^\star)=2\cdot 1 + 4 = 6,confirmado com o valor dual 6.]
Passo 9
Interpretação das restrições ativas/inativas e interpretação econômica (sombra / preço dual).
Quais restrições do primal são ativas/inativas?
Ambas as restrições do primal são ativas na solução ótima: 5x+y=9 e 2x+2y=10 (substituindo x=1,y=4 ambas são satisfeitas com igualdade).
Interpretação dos multiplicadores duais (u_1,u_2) — chamados também de preços sombra:
u_1^\star=\tfrac{1}{4}=0{,}25 é o preço sombra associado à primeira restrição primal 5x+y\ge 9.
u_2^\star=\tfrac{3}{8}=0{,}375 é o preço sombra associado à segunda restrição primal 2x+2y\ge 10.
Significado prático (variação marginal do valor ótimo):
Em geral, para pequenas variações \Delta b_i no lado direito b_i da i-ésima restrição primal, a variação aproximada no valor ótimo do primal é\Delta f^\star \approx u_i^\star \cdot \Delta b_i,desde que a base ótima não mude (ou seja, para variações pequenas o suficiente).
Portanto:
Se o termo do primeiro lado direito \,9 aumentar em +1 (ou seja, tornarmos a restrição mais forte), o valor ótimo de f aumentaria aproximadamente 0{,}25 (aumenta porque o primal minimiza e um aumento em b_1 torna factivelmente mais custoso).
Se o lado direito 9 diminuir em 1 (relaxamento da restrição 1), o valor ótimo diminuiria aproximadamente 0{,}25.
Similarly, um aumento de 1 em b_2 (o 10 da segunda restrição) aumenta f^\star em aproximadamente 0{,}375; uma redução de 1 diminui f^\star em 0{,}375.
Observação importante: essas são variações marginais válidas somente enquanto a base ótima se mantiver (ou seja, para mudanças pequenas o suficiente). Se a variação for grande, a base pode mudar e os coeficientes sombra podem mudar também.
Passo 10
Outras interpretações úteis (complementos e sinais).
Todas as variáveis de folga / excesso no primal correspondentes às restrições são nulas porque ambas as restrições são ativas: não há folga positiva.
As variáveis x e y são básicas e positivas (não há variável com custo reduzido negativo no dual que for básica).
A solução não é degenerada aqui (os valores básicos são positivos: x=1,y=4).
Não há ambiguidade: solução primal única e dual única dada a estrutura não degenerada.