2.4.2.1 Exerćicios

\operatorname{Max} Z=5 x_{1}+5 x_{2}+3 x_{3}

sujeito `a :

x_{1}+3 x_{2}+x_{3} \leq 3
-x_{1}+3 x_{3} \leq 2
2 x_{1}-x_{2}+2 x_{3} \leq 5,
2 x_{1}+3 x_{2}-x_{3} \leq 2,
x_{1}, x_{2}, x_{3} \geq 0

Passo 1

O enunciado pede para maximizar
Z = 5x_{1} + 5x_{2} + 3x_{3}
sujeito a
\begin{cases} x_{1} + 3x_{2} + x_{3} \le 3,\\\\ -\,x_{1} + 3x_{3} \le 2,\\\\ 2x_{1} - x_{2} + 2x_{3} \le 5,\\\\ 2x_{1} + 3x_{2} - x_{3} \le 2,\\\ x_{1},x_{2},x_{3}\ge0. \end{cases}
O conteúdo aqui é Programação Linear e vamos usar o Método Simplex, que precisa transformar todas as desigualdades em igualdades com variáveis de folga e depois iterar pivôs até atingir a solução ótima.

Passo 2

Introduzimos as variáveis de folga s_{1},s_{2},s_{3},s_{4}\ge0 para obter o sistema inicial
\begin{aligned} x_{1} + 3x_{2} + x_{3} + s_{1} &= 3,\\\\ -\,x_{1} + 3x_{3} + s_{2} &= 2,\\\\ 2x_{1} - x_{2} + 2x_{3} + s_{3} &= 5,\\\\ 2x_{1} + 3x_{2} - x_{3} + s_{4} &= 2, \end{aligned}
com base inicial (s_{1},s_{2},s_{3},s_{4}) e ponto (0,0,0). A função-objetivo na forma de linha Zero é
Z - 5x_{1} - 5x_{2} - 3x_{3} = 0.

Passo 3

Na primeira iteração, verificamos os custos reduzidos e vemos que x_{1} tem maior coeficiente positivo na linha-zero, então entra na base. Fazendo o teste de razão \frac{\text{lado direito}}{\text{coef. de }x_{1}}>0, obtemos as razões 3,\,2.5,\,1 e escolhemos a mínima, 1, na 4ª restrição. Logo s_{4} sai da base e pivotamos sobre o coeficiente de x_{1} na 4ª linha, obtendo a nova base (s_{1},s_{2},s_{3},x_{1}).

Passo 4

Na segunda iteração, recalculamos os custos reduzidos e vemos que x_{2} ainda pode entrar com custo negativo (aumenta Z). Fazendo o teste de razão nas linhas com coeficiente positivo de x_{2}, as razões são aproximadamente 1{,}33 e 2; a menor é 1{,}33 na 1ª linha, então s_{1} sai e pivotamos, passando a base para (x_{2},s_{2},s_{3},x_{1}).

Passo 5

Na terceira iteração, o único candidato real para entrar é x_{3}. Aplicamos novamente o teste de razão e encontramos a menor razão igual a 1 na 2ª linha, de modo que s_{2} sai da base. Pivotamos nessa linha, e a base final torna-se (x_{2},x_{3},s_{3},x_{1}).

Passo 6

Com a base (x_{1},x_{2},x_{3},s_{3}) e as variáveis de folga não-básicas zeradas, lemos diretamente:
x_{1} = 1,\quad x_{2} = \tfrac{1}{3},\quad x_{3} = 1,\quad s_{3} = \tfrac{4}{3}.
Substituindo na função-objetivo,
Z = 5(1) + 5\bigl(\tfrac{1}{3}\bigr) + 3(1) = 5 + \tfrac{5}{3} + 3 = \tfrac{29}{3}.

Resposta

x_{1}=1,\;x_{2}=\tfrac{1}{3},\;x_{3}=1 com valor ótimo Z=\tfrac{29}{3}.

Exercícios relacionados