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