Objetivo: encontrar valores de (x_{1},x_{2}) que satisfazem as restrições e que minimizam \;4x_{1}+x_{2}.
Há uma equação de igualdade (primeira restrição), uma desigualdade do tipo \ge (segunda) e uma do tipo \le (terceira).
As variáveis são não-negativas: \;x_{1},x_{2}\ge 0.
Questão a responder: determinar a solução ótima (x_{1},x_{2}) e o valor mínimo da função objetivo.]
Passo 2
Escolher a versão adequada do método Simplex. Como há uma igualdade e uma desigualdade \ge, é prática padrão usar o método em duas fases (Two-Phase Simplex):
Fase 1: introduz-se variáveis artificiais para obter uma solução básica inicial viável e minimiza-se a soma das artificiais; se a soma mínima for zero, há solução básica viável do problema original.
Fase 2: com a base viável encontrada sem artificiais, resolve-se o problema original.
Vamos colocar todas as restrições em forma de igualdade adicionando folgas/excesso e variáveis artificiais quando necessário.
Transformação das restrições:
Primeira (igualdade): \;3x_{1}+x_{2}=3. Para obter uma base inicial, adiciona-se uma variável artificial \;a_{1}:
3x_{1}+x_{2}+a_{1}=3.
Segunda (\ge): \;4x_{1}+3x_{2}\ge6. Subtrai-se uma variável de excesso \;s_{2} e adiciona-se artificial \;a_{2}:
4x_{1}+3x_{2}-s_{2}+a_{2}=6.
Terceira (\le): \;x_{1}+2x_{2}\le4. Soma-se uma folga \;s_{3}:
x_{1}+2x_{2}+s_{3}=4.
Todas as variáveis são não-negativas:
x_{1},x_{2},s_{2},s_{3},a_{1},a_{2}\ge 0.
Base inicial natural para a Fase 1: \{a_{1},a_{2},s_{3}\} com valores de RHS 3,6,4 respectivamente.
Fase 1: minimizar
w=a_{1}+a_{2}.
Passo 3
Montar o tableau inicial da Fase 1 (colunas: x_{1},x_{2},s_{2},s_{3},a_{1},a_{2}; linhas: as três equações básicas e o objetivo w). Escrever as equações da base:
Linha a_{1}:
3x_{1}+1x_{2}+0s_{2}+0s_{3}+1a_{1}+0a_{2}=3.
Linha a_{2}:
4x_{1}+3x_{2}-1s_{2}+0s_{3}+0a_{1}+1a_{2}=6.
Linha s_{3}:
1x_{1}+2x_{2}+0s_{2}+1s_{3}+0a_{1}+0a_{2}=4.
Os coeficientes-custo para a Fase 1 são: c_{x_1}=0,\\ c_{x_2}=0,\\ c_{s_2}=0,\\ c_{s_3}=0,\\ c_{a_1}=1,\\ c_{a_2}=1.
Calcular o rótulo da função auxiliar w (linha objetivo) através de z_j=\sum_{B} c_B a_{ij} e r_j=c_j-z_j. Inicialmente a base é (a_1,a_2,s_3) com custos (1,1,0).
Como existem r_j<0 (para minimização isso indica possibilidade de reduzir w), escolhe-se a variável com menor r_j (mais negativa) para entrar: \;x_{1} entra (r_{x_1}=-7).
Aplicar o teste da razão mínima para escolher a variável que sai: dividir \text{RHS} / \text{coef}_{x_1} apenas para coeficientes positivos na coluna de x_{1}:
Menor razão é 1 (linha de a_{1}), então a_{1} sai e x_{1} entra. Pivotar na posição (linha a_{1}, coluna x_{1}), elemento pivô 3.
Dividindo a linha a_{1} por 3 e eliminando x_{1} das outras linhas obtém‑se a nova tabela (apresento apenas as linhas transformadas em forma equacional):
e as variáveis artificiais assumem valor zero: a_{1}=a_{2}=0. O valor da função auxiliar é
w=a_{1}+a_{2}=0,
logo existe solução viável para o problema original (soma das artificiais mínima igual a zero). Conclui-se a Fase 1 com sucesso.]
Passo 4
Preparar a Fase 2: remover as colunas das variáveis artificiais a_{1},a_{2} (elas saíram da base e valem zero) e resolver o problema original de minimização com base atual \{x_{1},x_{2},s_{3}\}.
A função objetivo original tem custos c_{x_1}=4,\\ c_{x_2}=1,\\ c_{s_2}=0,\\ c_{s_3}=0.
Usando a tabela final da Fase 1 (após remover as colunas artificiais), escrevemos as linhas básicas na forma atual (mostradas abaixo em ordem: linha de x_{1}, linha de x_{2}, linha de s_{3}):
Como existe r_{s_2}=-\tfrac{1}{5}<0, ainda não estamos em solução ótima para minimização: a variável s_{2} (coluna do excesso/slack) pode entrar e reduzir o valor da função objetivo.
Selecionar s_{2} como variável que entra. Aplicar teste da razão mínima nas linhas com coeficiente positivo na coluna de s_{2}:
linha x_{1}: coeficiente \tfrac{1}{5}>0: razão \dfrac{3/5}{1/5}=3.
linha x_{2}: coeficiente -\tfrac{3}{5}<0: não considerada.
linha s_{3}: coeficiente 1>0: razão \dfrac{1}{1}=1.
A menor razão é 1 (linha s_{3}), então s_{3} sai e s_{2} entra. Pivotar na linha de s_{3} (pivô = 1).
Fazendo as operações de linha, obtém-se a nova base \{x_{1},x_{2},s_{2}\} e as linhas atualizadas: