Exercício 5

Encontre a solução ótima do seguinte problema de programação linear pelo método simplex tabular:
\begin{aligned} \operatorname{Max} Z & =5 x_{1}+4 x_{2}+3 x_{3} \\\ \text { s.r. } \quad 2 x_{1}+3 x_{2}+x_{3} & \leq 5 \\\\ 4 x_{1}+2 x_{2}+2 x_{3} & \leq 11 \\\\ 3 x_{1}+2 x_{2}+5 x_{3} & \leq 8 \\\ x_{1}, x_{2}, x_{3} & \geq 0 \end{aligned}

Passo 1

O enunciado pede: encontrar a solução ótima do problema
\begin{aligned} \text{Max } Z &= 5x_{1}+4x_{2}+3x_{3} \\\ \text{s.a. } \quad 2x_{1}+3x_{2}+x_{3} &\le 5 \\\\ 4x_{1}+2x_{2}+2x_{3} &\le 11 \\\\ 3x_{1}+2x_{2}+5x_{3} &\le 8 \\\ x_{1},x_{2},x_{3} &\ge 0 \end{aligned}
Informações relevantes dadas:
  • Função objetivo: Z=5x_{1}+4x_{2}+3x_{3} a maximizar.
  • Três restrições lineares com sinais \le e termos à direita 5, 11 e 8.
  • Variáveis não-negativas: x_{1},x_{2},x_{3}\ge0.
    A partir daqui vamos aplicar o método simplex tabular passo a passo.

Passo 2

Passo inicial: transformar em forma padrão adicionando variáveis folga \;s_{1},s_{2},s_{3} (todas \ge0):
\begin{aligned} 2x_{1}+3x_{2}+x_{3}+s_{1} &= 5\\\\ 4x_{1}+2x_{2}+2x_{3}+s_{2} &= 11\\\\ 3x_{1}+2x_{2}+5x_{3}+s_{3} &= 8 \end{aligned}
Na solução inicial básica temos as variáveis básicas \;s_{1}=5,\;s_{2}=11,\;s_{3}=8 e x_{1}=x_{2}=x_{3}=0.
A tabela inicial (resumida) de coeficientes para as variáveis \{x_{1},x_{2},x_{3},s_{1},s_{2},s_{3}\} e RHS é:
\begin{array}{c|cccccc|c} \text{Base} & x_{1} & x_{2} & x_{3} & s_{1} & s_{2} & s_{3} & \text{RHS}\\hline s_{1} & 2 & 3 & 1 & 1 & 0 & 0 & 5\\\ s_{2} & 4 & 2 & 2 & 0 & 1 & 0 & 11\\\ s_{3} & 3 & 2 & 5 & 0 & 0 & 1 & 8\\hline & 5 & 4 & 3 & 0 & 0 & 0 & Z \end{array}
Explicação rápida do critério de escolha: para maximização escolhemos a variável não-básica com maior valor positivo de (C_j - Z_j); inicialmente Z_j=0 para todas, logo escolhemos a coluna com maior custo C_j.

Passo 3

Cálculo do primeiro pivô:
  • Valores de (C_j-Z_j) iniciais são simplesmente os custos C_j: \;5,\;4,\;3. O maior é \;5 (coluna de x_{1}), então x_{1} entra na base.
  • Razão (teste da razão mínima) para escolher linha que sai: só se consideram coeficientes positivos em coluna de x_{1}. \frac{\text{RHS}}{a_{i1}} = \frac{5}{2}=2{,}5,\quad \frac{11}{4}=2{,}75,\quad \frac{8}{3}\approx2{,}6667.O mínimo é 2{,}5 (primeira linha). Então pivotamos na posição correspondente ao coeficiente 2 em linha 1.
  • Operação de pivot: vamos transformar a linha 1 para que o coeficiente de x_{1} fique 1 dividindo a linha 1 por 2: \text{L1}\leftarrow\frac{1}{2}\text{L1}:\quad x_{1}+\tfrac{3}{2}x_{2}+\tfrac{1}{2}x_{3}+\tfrac{1}{2}s_{1}= \tfrac{5}{2}.
  • Eliminar x_{1} das outras linhas: \begin{aligned} \text{L2}\leftarrow \text{L2}-4\cdot\text{L1}:&\quad -4x_{2}+0x_{3}-2s_{1}+s_{2}=1,\\\ \text{L3}\leftarrow \text{L3}-3\cdot\text{L1}:&\quad -\tfrac{5}{2}x_{2}+\tfrac{7}{2}x_{3}-\tfrac{3}{2}s_{1}+s_{3}=\tfrac{1}{2}. \end{aligned}
  • Agora a base é \{x_{1},s_{2},s_{3}\} com custos \{5,0,0\}.

Passo 4

Atualizar custos reduzidos e decidir próximo pivô:
  • Para calcular Z_j (o valor atual contribuído pela base) usamos a soma Z_j=\sum c_B\cdot a_{ij}, onde c_B são os custos das variáveis básicas e a_{ij} as entradas das colunas. Aqui só x_{1} tem custo não-nulo 5, então Z_j=5\times (coluna de x_{1} na forma atual).
  • Calculando (C_j-Z_j) para as variáveis não-básicas (ex.: x_{2},x_{3}): \begin{aligned} Z_{x_{2}} &=5\cdot\tfrac{3}{2}=\tfrac{15}{2}=7{,}5 \Rightarrow C_{2}-Z_{2}=4-7{,}5=-3{,}5,\\\ Z_{x_{3}} &=5\cdot\tfrac{1}{2}=2{,}5 \Rightarrow C_{3}-Z_{3}=3-2{,}5=0{,}5. \end{aligned}Observação: x_{3} tem (C_j-Z_j)=0{,}5>0, logo ainda podemos melhorar a solução escolhendo x_{3} para entrar.
  • Coluna de x_{3} na tabela atual tem coeficientes \tfrac{1}{2},\;0,\;\tfrac{7}{2}. Fazemos o teste da razão usando apenas entradas positivas nessa coluna: \frac{5/2}{1/2}=5,\quad\text{(segunda linha coeficiente 0 não conta)},\quad\frac{1/2}{7/2}=\frac{1/2}{3,5}=\frac{1}{7}\approx0{,}142857.ãO menor é \tfrac{1}{7}, correspondente à terceira linha. Assim o pivot é o coeficiente \tfrac{7}{2} na linha 3; x_{3} entra e s_{3} sai.

Passo 5

Executar o segundo pivot (detalhes das operações com frações — importante para prova sem calculadora):
  • Dividir a linha 3 pelo pivot \tfrac{7}{2} (equivalente a multiplicar por \tfrac{2}{7}): \text{L3}\leftarrow \frac{2}{7}\text{L3}:\quad -\tfrac{5}{7}x_{2}+x_{3}-\tfrac{3}{7}s_{1}+\tfrac{2}{7}s_{3}=\tfrac{1}{7}.
  • Eliminar x_{3} das outras linhas:
    • Na linha 1: eliminar \tfrac{1}{2}x_{3}: \text{L1}\leftarrow \text{L1}-\tfrac{1}{2}\text{L3}:cálculo coefficient-wise: \begin{aligned} x_{1} &+\Big(\tfrac{3}{2}-\big(-\tfrac{5}{14}\big)\Big)x_{2}+0\cdot x_{3}+\Big(\tfrac{1}{2}-\big(-\tfrac{3}{14}\big)\Big)s_{1}-\tfrac{1}{7}s_{3}=\tfrac{5}{2}-\tfrac{1}{14}. \end{aligned}Simplificando as frações isso dá x_{1}+\tfrac{13}{7}x_{2}+\tfrac{5}{7}s_{1}-\tfrac{1}{7}s_{3}=\tfrac{17}{7}.
    • Na linha 2: coeficiente de x_{3} já era 0, então permanece -4x_{2}-2s_{1}+s_{2}=1.
    • A linha 3 já está na forma pivot (com x_{3} com coeficiente 1): -\tfrac{5}{7}x_{2}+x_{3}-\tfrac{3}{7}s_{1}+\tfrac{2}{7}s_{3}=\tfrac{1}{7}.
  • Agora a base é \{x_{1},s_{2},x_{3}\} com custos \{5,0,3\}.

Passo 6

Verificar optimalidade calculando os custos reduzidos finais:
  • Calcular Z_j como Z_j=5\cdot(\text{col em L1})+0\cdot(\text{col em L2})+3\cdot(\text{col em L3}).
    Vamos aos principais (C_j-Z_j): \begin{aligned} Z_{x_{1}} &=5\cdot 1 + 0 + 3\cdot 0 =5 \Rightarrow C_{1}-Z_{1}=5-5=0,\\\ Z_{x_{2}} &=5\cdot\tfrac{13}{7} + 0 + 3\cdot\big(-\tfrac{5}{7}\big) = \tfrac{65}{7}-\tfrac{15}{7}=\tfrac{50}{7}\Rightarrow C_{2}-Z_{2}=4-\tfrac{50}{7}=-\tfrac{22}{7}<0,\\\ Z_{x_{3}} &=5\cdot 0 + 0 + 3\cdot 1 =3 \Rightarrow C_{3}-Z_{3}=3-3=0. \end{aligned}
  • Para as variáveis folga também os (C_j-Z_j) são não-positivos (calcularíamos da mesma maneira).
  • Critério de optimalidade do simplex: quando todos os (C_j-Z_j)\le 0 para um problema de maximização, a solução atual é ótima. Aqui não existem entradas positivas restantes, logo estamos ótimos.

Passo 7

Ler a solução ótima da tabela final:
  • As variáveis básicas e seus RHS (valores) são: x_{1}=\tfrac{17}{7},\quad s_{2}=1,\quad x_{3}=\tfrac{1}{7}.As variáveis não-básicas são x_{2}=0,\;s_{1}=0,\;s_{3}=0.
  • Valor da função objetivo: Z=5x_{1}+4x_{2}+3x_{3}=5\cdot\tfrac{17}{7}+4\cdot 0+3\cdot\tfrac{1}{7}=\tfrac{85}{7}+\tfrac{3}{7}=\tfrac{88}{7}.

Passo 8

Verificação rápida de consistência (substituir na restrição original para garantir que tudo bate):
\begin{aligned} 2x_{1}+3x_{2}+x_{3} &=2\cdot\tfrac{17}{7}+3\cdot 0+\tfrac{1}{7}=\tfrac{35}{7}=5,\\\\ 4x_{1}+2x_{2}+2x_{3} &=4\cdot\tfrac{17}{7}+0+2\cdot\tfrac{1}{7}=\tfrac{70}{7}=10\le 11,\\\\ 3x_{1}+2x_{2}+5x_{3} &=3\cdot\tfrac{17}{7}+0+5\cdot\tfrac{1}{7}=\tfrac{56}{7}=8. \end{aligned}
Tudo está consistente: duas restrições ativas (igualdade) e a segunda com folga s_{2}=1. A solução é viável e ótima.

Resposta

x_{1}=\tfrac{17}{7}
x_{2}=0
x_{3}=\tfrac{1}{7}
Z_{\max}=\tfrac{88}{7}

Exercícios relacionados