(5,5 pontos) Resolva o problema de programação linear abaixo usando o método Simplex.
\operatorname{Max} f=3 x_{1}+2 x_{2}+4 x_{3}
Sujeito a :
\begin{aligned} & x_{1}+x_{2}+x_{3} \leq 10 \\\ & 2 x_{1}+x_{2}+3 x_{3} \leq 20 \\\ & x_{1}, x_{2}, x_{3} \geq 0 \end{aligned}
Observações:
  • Coloque o modelo na forma padrão.
  • 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}.
    • Restrições: \begin{aligned} & x_{1}+x_{2}+x_{3}\leq 10,\\\ & 2x_{1}+x_{2}+3x_{3}\leq 20,\\\ & x_{1},x_{2},x_{3}\geq 0. \end{aligned}
  • 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):
\begin{array}{c|ccccc|c} \text{Base} & x_{1} & x_{2} & x_{3} & s_{1} & s_{2} & \text{RHS}\\hline s_{1} & 1 & 1 & 1 & 1 & 0 & 10\\\ s_{2} & 2 & 1 & 3 & 0 & 1 & 20\\hline z & -3 & -2 & -4 & 0 & 0 & 0 \end{array}
  • Regras (resumo didático):
    1. 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.
    2. 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).
    3. Faz-se o pivoteamento: divide-se a linha pivô pelo elemento pivô para torná-lo 1 e zera-se a coluna nas outras linhas.
    4. 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:
    \text{Linha }x_{3} \leftarrow \frac{1}{3}\text{Linha }s_{2}: \qquad \left(\frac{2}{3},\;\frac{1}{3},\;1,\;0,\;\frac{1}{3}\;\Big|\;\frac{20}{3}\right).
  • Atualizar a linha s_{1} para zerar a coluna x_{3} (subtrair 1 vez a nova linha x_{3} da antiga s_{1}):
    \text{Linha }s_{1}\leftarrow \text{Linha }s_{1}-1\cdot\text{Linha }x_{3}:
    calculando coeficientes:
    \left(\frac{1}{3},\;\frac{2}{3},\;0,\;1,\;-\frac{1}{3}\;\Big|\;\frac{10}{3}\right).
  • Atualizar a linha z para zerar a coluna x_{3} (somar 4 vezes a nova linha x_{3} à linha z, pois o coeficiente era -4):
    \text{Linha }z\leftarrow \text{Linha }z+4\cdot\text{Linha }x_{3}:
    que dá:
    \left(-\frac{1}{3},\;-\frac{2}{3},\;0,\;0,\;\frac{4}{3}\;\Big|\;\frac{80}{3}\right).
  • Tableau após a primeira iteração:
\begin{array}{c|ccccc|c} \text{Base} & x_{1} & x_{2} & x_{3} & s_{1} & s_{2} & \text{RHS}\\hline s_{1} & \dfrac{1}{3} & \dfrac{2}{3} & 0 & 1 & -\dfrac{1}{3} & \dfrac{10}{3}\\\ x_{3} & \dfrac{2}{3} & \dfrac{1}{3} & 1 & 0 & \dfrac{1}{3} & \dfrac{20}{3}\\hline z & -\dfrac{1}{3} & -\dfrac{2}{3} & 0 & 0 & \dfrac{4}{3} & \dfrac{80}{3} \end{array}
  • 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}):
    \text{Linha }x_{2}\leftarrow \frac{1}{(2/3)}\text{Linha }s_{1}= \left(\frac{1}{2},\;1,\;0,\;\frac{3}{2},\;-\frac{1}{2}\;\Big|\;5\right).
  • Eliminar x_{2} das outras linhas:
    • Atualizar linha x_{3}: subtrair \tfrac{1}{3} da nova linha x_{2} (pois coeficiente atual é \tfrac{1}{3}):
      \text{Linha }x_{3}\leftarrow \text{Linha }x_{3}-\tfrac{1}{3}\text{Linha }x_{2}= \left(\frac{1}{2},\;0,\;1,\;-\frac{1}{2},\;\frac{1}{2}\;\Big|\;5\right).
    • Atualizar linha z: somar \tfrac{2}{3} vezes a nova linha x_{2} (pois coeficiente era -\tfrac{2}{3}):
      \text{Linha }z\leftarrow \text{Linha }z+\tfrac{2}{3}\text{Linha }x_{2}= \left(0,\;0,\;0,\;1,\;1\;\Big|\;30\right).
  • Tableau após a segunda iteração (ótimo alcançado pois não há coeficientes negativos na linha z):
\begin{array}{c|ccccc|c} \text{Base} & x_{1} & x_{2} & x_{3} & s_{1} & s_{2} & \text{RHS}\\hline x_{2} & \dfrac{1}{2} & 1 & 0 & \dfrac{3}{2} & -\dfrac{1}{2} & 5\\\ x_{3} & \dfrac{1}{2} & 0 & 1 & -\dfrac{1}{2} & \dfrac{1}{2} & 5\\hline z & 0 & 0 & 0 & 1 & 1 & 30 \end{array}
  • 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.
  • Relembrando o que entrou/ saiu nas iterações:
    • Iteração 1: entrou \,x_{3}, saiu \,s_{2}.
    • Iteração 2: entrou \,x_{2}, saiu \,s_{1}.

Resposta

Variáveis não-básicas: x_{1}=0,\;s_{1}=0,\;s_{2}=0
Variáveis básicas: x_{2}=5,\;x_{3}=5
Valor da função objetivo: z_{\max}=30

Exercícios relacionados