Resolver os modelos em programação linear, usando o método Simplex.
Max.
z=0,2 × 1+2 × 2+4 × 3
Sujeito a:
{
x_{1}+2 x_{2} ≤ 20
3 x_{1}+x_{3} ≤ 50
x_{1}+x_{2}-x_{3} ≤ 15
x_{1} ≥ 0, x_{2} ≥ 0, x_{3} ≥ 0
}

Passo 1

O enunciado pede maximizar a função objetivo e encontrar os valores das variáveis que satisfazem as restrições. Informações dadas:
  • Função objetivo a maximizar:
z = 0,2x_{1} + 2x_{2} + 4x_{3}.
  • Restrições:
\begin{cases} x_{1} + 2x_{2} \le 20,\\[4pt] 3x_{1} + x_{3} \le 50,\\[4pt] x_{1} + x_{2} - x_{3} \le 15, \end{cases}
com não negatividade:
x_{1}\ge 0,\quad x_{2}\ge 0,\quad x_{3}\ge 0.
Objetivo final: resolver este problema por programação linear usando o método Simplex, isto é, encontrar a solução ótima (valores de x_{1},x_{2},x_{3}) e o valor máximo de z.]

Passo 2

Transformar em forma padrão (igualdades) introduzindo variáveis de folga (slack) s_{1},s_{2},s_{3}\ge 0\): \[\begin{cases} x_{1} + 2x_{2} + s_{1} = 20,\\[4pt] 3x_{1} + x_{3} + s_{2} = 50,\\[4pt] x_{1} + x_{2} - x_{3} + s_{3} = 15. \end{cases}
Na forma padrão a base inicial natural é (s_{1},s_{2},s_{3})\] com \((x_{1},x_{2},x_{3})=(0,0,0) e (s_{1},s_{2},s_{3})=(20,50,15). Explicação curta sobre slack: cada s_{i} mede quanto sobra na desigualdade; assim passamos a trabalhar com igualdades, necessárias para montar o tableau do Simplex.]

Passo 3

Montar o tableau inicial do Simplex. Colunas: x_{1},x_{2},x_{3},s_{1},s_{2},s_{3} e term. à direita (RHS). A linha da função objetiva apresentamos os custos reduzidos iniciais c_j - z_j (inicialmente z_j=0 porque a base tem custos zero):
Tabela inicial (linhas correspondem a s_{1},s_{2},s_{3} como variáveis básicas):
Linha s_{1}:
\begin{array}{ccccccc} x_{1} & x_{2} & x_{3} & s_{1} & s_{2} & s_{3} & \text{RHS}\\\\ 1 & 2 & 0 & 1 & 0 & 0 & 20 \end{array}
Linha s_{2}:
\begin{array}{ccccccc} 3 & 0 & 1 & 0 & 1 & 0 & 50 \end{array}
Linha s_{3}:
\begin{array}{ccccccc} 1 & 1 & -1 & 0 & 0 & 1 & 15 \end{array}
Linha objetivo (custos c_j): (c_{1},c_{2},c_{3},c_{s1},c_{s2},c_{s3})=(0,2,4,0,0,0) onde c_{1}=0,2. Como z_j=0 inicialmente, os custos reduzidos são simplesmente os c_j:
c_j - z_j = (0,2,4,0,0,0).
Regra do Simplex para maximização: enquanto existir alguma entrada positiva em c_j - z_j, podemos aumentar z escolhendo a variável com maior valor positivo para entrar na base.

Passo 4

Escolha da variável que entra na base (regra da maior redução positiva): os c_j - z_j são
x_{1}:0,2,\quad x_{2}:2,\quad x_{3}:4.
Maior valor é para x_{3} ( 4), logo x_{3} entra na base.
Agora regra da razão mínima (para decidir quem sai): calcular \text{RHS}/\text{coef}_{x_{3}} apenas para coeficientes positivos na coluna de x_{3}.
  • Linha s_{1}: coeficiente de x_{3} é 0 → não restrição (não conta).
  • Linha s_{2}: coeficiente de x_{3} é 1 >0 → razão 50/1 = 50.
  • Linha s_{3}: coeficiente de x_{3} é -1 <0 → não conta.
Há apenas uma razão válida: 50 na linha de s_{2}, então s_{2} sai da base e x_{3} entra. O pivô é o elemento 1 na interseção da linha s_{2} e coluna x_{3}.

Passo 5

Executar o pivoteamento para tornar a coluna de x_{3} coluna básica (1 na linha do pivô e 0 nas outras linhas).
A linha de pivô ( s_{2}) já tem 1 na coluna x_{3}, portanto mantemos:
\text{Linha }x_{3}: \quad (x_{1},x_{2},x_{3},s_{1},s_{2},s_{3}\,|\,\text{RHS}) = (3,0,1,0,1,0 \,|\,50).
Eliminar x_{3} das outras linhas:
  • Linha s_{1} tem coeficiente 0 em x_{3} → não muda: (1,2,0,1,0,0\,|\,20).
  • Linha s_{3} tem coeficiente -1 em x_{3}. Novo s_{3} = \text{antigo }s_{3} + 1\times (\text{linha }x_{3}): (1,1,-1,0,0,1\,|\,15) + (3,0,1,0,1,0\,|\,50) = (4,1,0,0,1,1\,|\,65).
Agora a base é (s_{1},x_{3},s_{3}) com RHS (20,50,65).

Passo 6

Recalcular os custos reduzidos c_j - z_j após a troca de base. Explicação do cálculo: para cada coluna j, calcula-se z_j = \sum_{B} c_B \cdot a_{B,j} (onde c_B são os custos das variáveis básicas e a_{B,j} os coeficientes das colunas nas linhas básicas). Aqui a única variável básica com custo não nulo é x_{3} com c_{3}=4. Então:
  • Para coluna x_{1}: z_{1} = 4 \times (\text{coef de }x_{1}\text{ na linha }x_{3}) = 4\times 3 = 12. Logo c_{1}-z_{1} = 0,2 - 12 = -11,8.
  • Para coluna x_{2}: z_{2} = 4 \times 0 = 0. Logo c_{2}-z_{2} = 2 - 0 = 2.
  • Para coluna x_{3}: z_{3} = 4 \times 1 = 4. Logo c_{3}-z_{3} = 4 - 4 = 0.
  • Para s_{1}: z = 4 \times 0 = 0 \Rightarrow c - z = 0-0 = 0.
  • Para s_{2}: z = 4 \times 1 = 4 \Rightarrow c - z = 0 - 4 = -4.
  • Para s_{3}: z = 4 \times 0 = 0 \Rightarrow c - z = 0.
Resumo dos c_j - z_j depois do primeiro pivô:
x_{1}:-11,8,\quad x_{2}:2,\quad x_{3}:0,\quad s_{1}:0,\quad s_{2}:-4,\quad s_{3}:0.
Como há uma entrada positiva ( x_{2} com 2), ainda não estamos ótimos. Portanto x_{2} entra na base.

Passo 7

Aplicar a razão mínima para a coluna de x_{2} (para decidir quem sai):
Olhar as razões \text{RHS}/\text{coef}_{x_{2}} apenas onde o coeficiente de x_{2} é positivo.
  • Linha s_{1}: coeficiente 2>0 → razão 20/2 = 10.
  • Linha x_{3} (antigo s_{2}): coeficiente 0 → não conta.
  • Linha s_{3}: coeficiente 1>0 → razão 65/1 = 65.
Menor razão é 10 na linha s_{1}, então s_{1} sai e x_{2} entra. Pivô é elemento 2 na linha s_{1}, coluna x_{2}.

Passo 8

Executar o pivoteamento para que na linha do pivô a coluna x_{2} fique com 1 e nas outras linhas com 0.
Primeiro normalizar a linha do pivô (dividir a linha s_{1} por 2):
\text{linha }x_{2}: \quad (x_{1},x_{2},x_{3},s_{1},s_{2},s_{3}\,|\,\text{RHS}) = \bigl(0{,}5,\;1,\;0,\;0{,}5,\;0,\;0\;\bigr|\;10\bigr).
Agora eliminar x_{2} das outras linhas:
  • Linha x_{3} já tem coeficiente 0 em x_{2} → permanece (3,0,1,0,1,0\,|\,50).
  • Linha s_{3} tem coeficiente 1 em x_{2}. Nova linha s_{3} = linha antiga s_{3} - 1 × linha x_{2}: (4,1,0,0,1,1\,|\,65) - (0{,}5,1,0,0{,}5,0,0\,|\,10) = (3{,}5,0,0{-}0{,}5,1,1\,|\,55).(isto é, x_{1}:4-0{,}5=3{,}5; s_{1}:0-0{,}5=-0{,}5; RHS: 65-10=55.)
Então a base agora é (x_{2},x_{3},s_{3}) com RHS (10,50,55) e as linhas são:
  • Linha x_{2}: (0{,}5,\;1,\;0,\;0{,}5,\;0,\;0\;|\;10).
  • Linha x_{3}: (3,\;0,\;1,\;0,\;1,\;0\;|\;50).
  • Linha s_{3}: (3{,}5,\;0,\;0,\;-0{,}5,\;1,\;1\;|\;55).

Passo 9

Recalcular c_j - z_j com a nova base cujos custos básicos são c_{x_{2}}=2 e c_{x_{3}}=4. Procedimento: para cada coluna j, z_j = 2\times(\text{coef na linha }x_{2}) + 4\times(\text{coef na linha }x_{3}).
Cálculos:
  • Para x_{1}: z_{1} = 2\cdot 0{,}5 + 4\cdot 3 = 1 + 12 = 13. Então c_{1}-z_{1} = 0,2 - 13 = -12,8.
  • Para x_{2}: z_{2} = 2\cdot 1 + 4\cdot 0 = 2. Então c_{2}-z_{2} = 2 - 2 = 0.
  • Para x_{3}: z_{3} = 2\cdot 0 + 4\cdot 1 = 4. Então c_{3}-z_{3} = 4 - 4 = 0.
  • Para s_{1}: z = 2\cdot 0{,}5 + 4\cdot 0 = 1. c - z = 0 - 1 = -1.
  • Para s_{2}: z = 2\cdot 0 + 4\cdot 1 = 4. c - z = 0 - 4 = -4.
  • Para s_{3}: z = 2\cdot 0 + 4\cdot 0 = 0. c - z = 0 - 0 = 0.
Todos os c_j - z_j são agora \le 0 (não há entrada positiva). Regra do Simplex: quando não existem custos reduzidos positivos para maximização, a solução atual é ótima.

Passo 10

Ler a solução básica atual (variáveis básicas e RHS) e obter a solução ótima:
  • Base: x_{2}=10 (linha x_{2} RHS), x_{3}=50 (linha x_{3} RHS), s_{3}=55 (linha s_{3} RHS).
  • Variáveis não-básicas x_{1}=0 (não aparece na base, portanto vale 0); também s_{1}=0 e s_{2}=0 por serem não-básicas (caso se queira).
Verificação rápida nas restrições:
\begin{aligned} x_{1} + 2x_{2} &= 0 + 2\cdot 10 = 20 \le 20,\\[4pt] 3x_{1} + x_{3} &= 0 + 50 = 50 \le 50,\\[4pt] x_{1} + x_{2} - x_{3} &= 0 + 10 - 50 = -40 \le 15, \end{aligned}
tudo consistente. Calcular o valor objetivo:
z = 0,2\cdot 0 + 2\cdot 10 + 4\cdot 50 = 0 + 20 + 200 = 220.
Interpretação final: solução ótima encontrada pelo Simplex é x_{1}=0,\;x_{2}=10,\;x_{3}=50 com valor máximo de z=220.]

Resposta

x_{1}=0
x_{2}=10
x_{3}=50
z_{\max}=220

Exercícios relacionados