Exercício 3

Utilizando o método simplex tabular, resolva o problema de programação linear abaixo:
\begin{aligned} \operatorname{Min} Z & =-2 x_{1}+x_{2}-x_{3} \\\ \text { s.r. } \quad 3 x_{1}+x_{2}+x_{3} & \leq 60 \\\ x_{1}-x_{2}+2 x_{3} & \leq 10 \\\ x_{1}+x_{2}-x_{3} & \leq 20 \\\ x_{1}, x_{2}, x_{3} & \geq 0 \end{aligned}

Passo 1

O enunciado pede: minimizar a função objetivo
\displaystyle Z = -2x_{1} + x_{2} - x_{3}
sujeito às restrições
\begin{aligned} 3x_{1}+x_{2}+x_{3} &\le 60,\\\ x_{1}-x_{2}+2x_{3} &\le 10,\\\ x_{1}+x_{2}-x_{3} &\le 20,\\\ x_{1},x_{2},x_{3} &\ge 0. \end{aligned}
Informações relevantes fornecidas:
  • Variáveis de decisão: \,x_{1},x_{2},x_{3}\, com \,x_i\ge0.
  • Três desigualdades do tipo \le (podemos introduzir variáveis folga).
  • Objetivo é minimizar Z.
    As perguntas implícitas: encontrar os valores de \,x_{1},x_{2},x_{3}\, que minimizam Z e o valor mínimo de Z.

Passo 2

Estratégia (sem detalhes técnicos profundos ainda): o método simplex tabular funciona naturalmente para maximização. Para usar o simplex clássico transformamos a minimização em maximização multiplicando a função objetivo por -1. Definimos
W = -Z = 2x_{1}-x_{2}+x_{3},
e vamos maximizar W sujeito às mesmas restrições. Depois, o valor ótimo de Z será Z=-W_{\max}.
Também introduzimos variáveis de folga (slack) \,s_{1},s_{2},s_{3}\ge0 para transformar as desigualdades em igualdades:
\begin{aligned} 3x_{1}+x_{2}+x_{3}+s_{1} &= 60,\\\ x_{1}-x_{2}+2x_{3}+s_{2} &= 10,\\\ x_{1}+x_{2}-x_{3}+s_{3} &= 20. \end{aligned}
A solução básica inicial é s_{1}=60,\;s_{2}=10,\;s_{3}=20 com x_{1}=x_{2}=x_{3}=0.

Passo 3

Montamos o tableau inicial (colunas: x_{1},x_{2},x_{3},s_{1},s_{2},s_{3}; RHS = termos independentes). Coeficientes de W (a maximizar) são c=(2,\,-1,\,1,\,0,\,0,\,0). A tabela inicial (representação compacta) é:
Linha 1 (equação 1, base s_{1}, c_{B}=0):
(3,\;1,\;1,\;1,\;0,\;0\mid 60)
Linha 2 (equação 2, base s_{2}, c_{B}=0):
(1,\;-1,\;2,\;0,\;1,\;0\mid 10)
Linha 3 (equação 3, base s_{3}, c_{B}=0):
(1,\;1,\;-1,\;0,\;0,\;1\mid 20)
Linha objetivo (custos reduzidos c_j - z_j; inicialmente z_j=0 porque c_B=0):
(c_j - z_j) = (2,\;-1,\;1,\;0,\;0,\;0 \mid 0)
Explicação rápida: escolhemos como variável a entrar aquela com maior custo reduzido positivo (pois maximizamos W).

Passo 4

Primeira iteração — escolha da variável a entrar: x_{1} tem c_{1}-z_{1}=2 (maior positivo), entra na base. Fazemos teste de razão (RHS dividido pelo coeficiente positivo na coluna de x_{1}) para determinar a linha pivô:
\begin{aligned} \text{linha 1: } &60/3 = 20,\\\ \text{linha 2: } &10/1 = 10,\\\ \text{linha 3: } &20/1 = 20. \end{aligned}
Menor razão é 10 -> pivô na linha 2, elemento pivô = 1 (coeficiente de x_{1} na linha 2). Tornamos essa linha a linha básica de x_{1} dividindo por 1 (já está 1). Agora eliminamos x_{1} das demais linhas.
Linha 2 (nova, base x_{1}, c_B=2):
(1,\;-1,\;2,\;0,\;1,\;0\mid 10).
Atualizamos linha 1: linha1 := linha1 − 3·linha2
(0,\;4,\;-5,\;1,\;-3,\;0\mid 30).
Atualizamos linha 3: linha3 := linha3 − 1·linha2
(0,\;2,\;-3,\;0,\;-1,\;1\mid 10).
Calculamos agora os custos reduzidos c_j - z_j. Regra: z_j = \sum c_B \cdot (\text{coluna }j) onde o somatório é sobre linhas básicas; agora c_B=(0,2,0) correspondendo às bases (s_1,x_1,s_3). Como somente x_{1} tem c_B\neq0 e sua linha é a linha 2, temos z_j = 2\times(\text{entrada na linha 2 da coluna }j). Portanto
z = 2\cdot(1,\,-1,\;2,\;0,\;1,\;0) = (2,\,-2,\;4,\;0,\;2,\;0).
Logo
c_j - z_j = (2-2,\; -1 -(-2),\; 1-4,\; 0-0,\;0-2,\;0-0) = (0,\;1,\;-3,\;0,\;-2,\;0).
O valor atual de W (RHS da função objetivo) é W = \sum c_B \cdot (\text{RHS}) = 0\cdot30 + 2\cdot10 + 0\cdot10 = 20.

Passo 5

Segunda iteração — escolha da variável a entrar: coluna x_{2} tem custo reduzido 1>0, então x_{2} entra. Fazemos teste de razão usando coeficientes positivos da coluna x_{2}:
\begin{aligned} \text{linha 1: } &30/4 = 7{,}5,\\\ \text{linha 2: } &\text{coeficiente }-1\\ (\text{negativo})\\ \Rightarrow\\ \text{não é elegível},\\\ \text{linha 3: } &10/2 = 5. \end{aligned}ãéí
Menor razão é 5 -> pivô na linha 3, elemento pivô = 2. Dividimos a linha 3 por 2 para ter 1 na posição pivô.
Linha 3 (nova base x_{2}, c_B=-1) após divisão por 2:
(0,\;1,\;-3/2,\;0,\;-1/2,\;1/2\mid 5).
Eliminamos x_{2} das outras linhas:
Linha 1 := linha1 − 4·linha3
(0,\;0,\;1,\;1,\;-1,\;-2\mid 10).
Linha 2 := linha2 + 1·linha3 \quad (porque coeficiente era -1)
(1,\;0,\;1/2,\;0,\;1/2,\;1/2\mid 15).

Passo 6

Atualizamos os custos reduzidos com as novas bases. As variáveis básicas agora são (s_{1},x_{1},x_{2}) com c_B = (0,2,-1). Calculamos z_j = 0\cdot(\text{linha1}) + 2\cdot(\text{linha2}) + (-1)\cdot(\text{linha3}).
Multiplicando linhas:
2\cdot\text{linha2} = (2,\;0,\;1,\;0,\;1,\;1\mid 30),
(-1)\cdot\text{linha3} = (0,\;-1,\;3/2,\;0,\;1/2,\;-1/2\mid -5).
Somando:
z=(2,\;-1,\;5/2,\;0,\;3/2,\;1/2\mid 25).
Os custos reduzidos c_j - z_j são:
\begin{aligned} &c_{x_1}-z_{x_1}=2-2=0,\\\ &c_{x_2}-z_{x_2}=-1-(-1)=0,\\\ &c_{x_3}-z_{x_3}=1-\tfrac{5}{2}=-\tfrac{3}{2},\\\ &c_{s_1}-z_{s_1}=0-0=0,\\\ &c_{s_2}-z_{s_2}=0-\tfrac{3}{2}=-\tfrac{3}{2},\\\ &c_{s_3}-z_{s_3}=0-\tfrac{1}{2}=-\tfrac{1}{2}. \end{aligned}
O valor atual de W é W = 0\cdot10 + 2\cdot15 + (-1)\cdot5 = 30 -5 = 25.

Passo 7

Condição de otimalidade (para maximização): todos os custos reduzidos c_j - z_j devem ser ≤ 0. Aqui os custos reduzidos são (0,0,-\tfrac{3}{2},0,-\tfrac{3}{2},-\tfrac{1}{2}), todos ≤ 0. Portanto a solução atual é ótima para o problema de maximização de W.
Lemos a solução básica do tableau final:
  • linha 1 (base s_{1}): s_{1}=10;
  • linha 2 (base x_{1}): x_{1}=15;
  • linha 3 (base x_{2}): x_{2}=5.
    As variáveis não básicas são x_{3}=0,\;s_{2}=0,\;s_{3}=0.
Verificação rápida nas restrições originais:
\begin{aligned} 3x_{1}+x_{2}+x_{3} &= 3\cdot15 + 5 + 0 = 50 \le 60 \\ (\text{então }s_{1}=10),\\\ x_{1}-x_{2}+2x_{3} &= 15 - 5 + 0 = 10 \\ (\text{igual a }10, s_{2}=0),\\\ x_{1}+x_{2}-x_{3} &= 15 + 5 - 0 = 20 \\ (\text{igual a }20, s_{3}=0). \end{aligned}ã
Valor ótimo encontrado para W é W_{\max}=25. Lembrando que W=-Z, então o valor mínimo buscado é Z_{\min}=-W_{\max}=-25.

Resposta

x_{1}=15,\;x_{2}=5,\;x_{3}=0
Z_{\min}=-25

Exercícios relacionados