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+y \\\ \text { s.a. } & 5 x+y \geq 9 \\\ & 2 x+2 y \geq 10 \\\ & x, y \geq 0\end{cases}

Passo 1

O que o enunciado pede e o que foi dado.
  • 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.).
  • O PL primal dado é:
\begin{cases} \min & f=2x+y\\[4pt] \text{s.a.} & 5x+y \ge 9\\[4pt] & 2x+2y \ge 10\\[4pt] & x,y\ge 0 \end{cases}
  • Informações importantes a listar:
    • Variáveis de decisão: x e y.
    • Objetivo: minimizar f=2x+y.
    • 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) é:
\begin{cases} \max & w=9u_1+10u_2\\[4pt] \text{s.a.} & 5u_1+2u_2 \le 2\\[4pt] & u_1+2u_2 \le 1\\[4pt] & u_1,u_2\ge 0 \end{cases}
  • 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\}.
  • Calcule o valor ótimo do objetivo com essa base:
    • u_1 = 0{,}25 = \tfrac{1}{4}.
    • u_2 = 0{,}375 = \tfrac{3}{8}.
    • w = 9\cdot 0{,}25 + 10\cdot 0{,}375 = 2{,}25 + 3{,}75 = 6.
  • 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,
u_1+2u_2 = \tfrac{1}{4} + 2\cdot\tfrac{3}{8} = 0{,}25 + 0{,}75 = 1.
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:
\begin{cases} 5x+y = 9\\[4pt] 2x+2y = 10 \end{cases}
  • Resolvendo: da segunda equação x+y=5\] então \(y=5-x. Substituindo na primeira:
5x + (5-x) = 9 \Rightarrow 4x+5=9 \Rightarrow x=1.
Então y=5-1=4.
  • 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.

Resposta

(x,y)=(1,4)
(u_1,u_2)=\bigl(\tfrac{1}{4},\tfrac{3}{8}\bigr)
f_{\min}=6

Exercícios relacionados