Durante a resolução, mostre as variáveis que ENTRAM e SAEM da base.
Ao finalizar, mostre os VALORES das variáveis NÃO BÁSICAS, das variáveis BÁSICAS e da FUNÇÃO OBJETIVO.
Passo 1
O que o problema pede e que informações temos.
Pede: resolver a programação linear por Simplex. Mostrar o modelo na forma padrão; durante a resolução mostrar as variáveis que ENTRAM e SAEM da base; no final mostrar os VALORES das variáveis NÃO BÁSICAS, das variáveis BÁSICAS e da FUNÇÃO OBJETIVO.
Dados do enunciado (aqui só números que pegamos do próprio enunciado):
Função objetivo a maximizar: \displaystyle f_{\max}=3x_{1}+2x_{2}+4x_{3}.
O enunciado exige também que apresentemos o modelo na forma padrão (igualdades com variáveis de folga) — faremos isso no próximo passo.
Passo 2
Colocar o modelo na forma padrão (introduzir variáveis de folga) e escrever a base inicial.
Para transformar cada desigualdade do tipo \leq em igualdade, adiciona-se uma variável de folga não negativa.
Introduzir \,s_{1}\ge0 para a primeira restrição e \,s_{2}\ge0 para a segunda. O modelo em forma padrão fica:\begin{aligned} & x_{1}+x_{2}+x_{3}+s_{1}=10,\\\ & 2x_{1}+x_{2}+3x_{3}+s_{2}=20,\\\ & x_{1},x_{2},x_{3},s_{1},s_{2}\geq 0, \end{aligned}com objetivo \displaystyle \max z=3x_{1}+2x_{2}+4x_{3}.
Explicação pedagógica curta: a forma padrão é útil porque nos dá uma solução básica inicial óbvia: tomar as folgas como básicas e as variáveis originais como zero. Ou seja, base inicial \{s_{1},s_{2}\} com x_{1}=x_{2}=x_{3}=0, s_{1}=10, s_{2}=20.
Vamos agora montar o tableau inicial do Simplex para maximização. Usamos a equação de objetivo na forma \,z-3x_{1}-2x_{2}-4x_{3}=0.
Passo 3
Tableau inicial e explicação das regras do Simplex que vamos usar.
Tableau inicial (linhas: duas equações de restrição e a equação de z):
Seleção da variável que entra: para maximização escolhe-se uma coluna com coeficiente negativo na linha z (custo reduzido negativo). Normalmente escolhe-se o mais negativo (regra do maior ganho imediato) — aqui são -3,-2,-4.
Seleção da variável que sai (teste da razão): para a coluna escolhida, calcula-se a razão \text{RHS}/\text{coef}_{\text{linha}} apenas para linhas com coeficiente positivo na coluna. A linha com menor razão determina a variável que sai (garante viabilidade).
Faz-se o pivoteamento: divide-se a linha pivô pelo elemento pivô para torná-lo 1 e zera-se a coluna nas outras linhas.
Repetir até que não haja mais coeficientes negativos na linha z (ótimo atingido).
Vamos aplicar essas regras passo a passo. Sempre indicarei qual variável ENTRA e qual SAÍ.
Passo 4
Primeira iteração: escolher variável que entra e que sai; pivotar.
Observando a linha z: os coeficientes são -3,-2,-4. O mais negativo é -4, portanto a variável que ENTRA é \,x_{3}.
Fazer o teste da razão para a coluna de \,x_{3}:
Para a linha de s_{1}: \dfrac{10}{1}=10.
Para a linha de s_{2}: \dfrac{20}{3}=\dfrac{20}{3}\approx 6{,}666.
A menor razão é \dfrac{20}{3}, logo a variável que SAI é \,s_{2}.
Resumo desta iteração: entra \,x_{3}, sai \,s_{2}.
Pivô: elemento na interseção da linha s_{2} com a coluna x_{3}, que vale 3. Primeiro dividimos a linha pivô por 3:
Observação pedagógica: agora a base é \{s_{1},x_{3}\}. A solução corrente é x_{1}=0,\;x_{2}=0,\;x_{3}=\dfrac{20}{3},\;s_{1}=\dfrac{10}{3},\;s_{2}=0 e valor objetivo z=\dfrac{80}{3}\approx 26{,}67. Ainda há coeficientes negativos na linha z (-\tfrac{1}{3} e -\tfrac{2}{3}), então não estamos ótimos.
Passo 5
Segunda iteração: escolher variável que entra e que sai; pivotar.
Na linha z os coeficientes negativos são -\tfrac{1}{3} (coluna x_{1}) e -\tfrac{2}{3} (coluna x_{2}). O mais negativo é -\tfrac{2}{3}, então a variável que ENTRA é \,x_{2}.
Fazer o teste da razão para a coluna de \,x_{2} (considerar apenas linhas com coeficiente positivo nessa coluna):
Para a linha de s_{1}: \dfrac{\text{RHS}}{\text{coef}}=\dfrac{10/3}{2/3}=5.
Para a linha de x_{3}: \dfrac{20/3}{1/3}=20.
A menor razão é 5, portanto a variável que SAI é \,s_{1}.
Resumo desta iteração: entra \,x_{2}, sai \,s_{1}.
Pivô: elemento na interseção da linha s_{1} com a coluna x_{2}, que vale \tfrac{2}{3}. Primeiro dividimos a linha pivô por \tfrac{2}{3} (ou multiplicar por \tfrac{3}{2}):
Observação pedagógica: agora a base é \{x_{2},x_{3}\}. Os coeficientes na linha z (reduced costs) são todos não-negativos, então alcançamos a solução ótima do Simplex.
Passo 6
Interpretar a solução final e calcular os valores das variáveis (básicas e não-básicas) e o valor da função objetivo.
Pela forma padrão das linhas básicas, os valores das variáveis básicas são os RHS das suas linhas:
x_{2}=\;5 (linha de x_{2}),
x_{3}=\;5 (linha de x_{3}).
As variáveis não-básicas (as que não aparecem como base) são x_{1},s_{1},s_{2}; na solução básica atual, elas valem zero:
x_{1}=0,\;s_{1}=0,\;s_{2}=0.
Verificação direta na forma original:
As restrições dão x_{1}+x_{2}+x_{3}+s_{1}=10 \Rightarrow 0+5+5+s_{1}=10\Rightarrow s_{1}=0.
Segunda restrição: 2\cdot0+5+3\cdot5+s_{2}=20\Rightarrow 5+15+s_{2}=20\Rightarrow s_{2}=0.
Valor da função objetivo:z=3x_{1}+2x_{2}+4x_{3}=3\cdot0+2\cdot5+4\cdot5=10+20=30.