2.1.2 Exerćlcios

  1. Maximizar a fun, c~ao-objetivo Z
\operatorname{Max} Z=2 x_{1}-x_{2}+x_{3}
sujeito `a :
\begin{aligned} 3 x_{1}+x_{2}+x_{3} & \leq 60 \\ x_{1}-x_{2}+x_{3} & \leq 10 \\ x_{1}+x_{2}-x_{3} & \leq 20 \\ x_{1}, x_{2}, x_{3} & \geq 0 \end{aligned}

Passo 1

O enunciado pede para maximizar a função objetivo
\operatorname{Max}Z = 2x_{1} - x_{2} + x_{3}
sujeito às restrições
\begin{aligned} 3x_{1} + x_{2} + x_{3} &\le 60,\\\ x_{1} - x_{2} + x_{3} &\le 10,\\\ x_{1} + x_{2} - x_{3} &\le 20,\\\ x_{1},x_{2},x_{3} &\ge 0. \end{aligned}
O conteúdo principal é Programação Linear e vamos usar o Método Simplex, que exige passar o problema para a forma-padrão com variáveis de folga e depois iterar pivôs até encontrar a solução ótima.

Passo 2

Introduzimos as variáveis de folga s_{1},s_{2},s_{3}\ge0 para transformar as desigualdades em igualdades:
\begin{aligned} 3x_{1}+x_{2}+x_{3}+s_{1}&=60,\\\ x_{1}-x_{2}+x_{3}+s_{2}&=10,\\\ x_{1}+x_{2}-x_{3}+s_{3}&=20. \end{aligned}
Na forma de tabela Simplex inicial, temos a base \{s_{1},s_{2},s_{3}\} e a equação-objetivo escrita como
-Z +2x_{1}-x_{2}+x_{3}=0.

Passo 3

Montamos a tabela inicial (listo apenas coeficientes relevantes):
\begin{array}{c|cccccc|c} \text{Base} & x_{1} & x_{2} & x_{3} & s_{1} & s_{2} & s_{3} & \text{RHS}\\hline Z & 2 & -1 & 1 & 0 & 0 & 0 & 0\\\ s_{1} & 3 & 1 & 1 & 1 & 0 & 0 & 60\\\ s_{2} & 1 & -1 & 1 & 0 & 1 & 0 & 10\\\ s_{3} & 1 & 1 & -1 & 0 & 0 & 1 & 20 \end{array}
A solução básica inicial é x_{1}=x_{2}=x_{3}=0, s_{1}=60, s_{2}=10, s_{3}=20, com Z=0.

Passo 4

Calculamos os custos reduzidos c_j - z_j na linha Z. Como o coeficiente de x_{1} é o maior positivo, x_{1} entra na base. Fazemos o teste da razão mínima entre RHS e coeficiente de x_{1} nas restrições:
\frac{60}{3}=20,\quad \frac{10}{1}=10,\quad \frac{20}{1}=20.
O menor valor é 10, na linha de s_{2}, logo s_{2} sai da base e pivotamos em (\text{linha }s_{2},x_{1}). Após o pivô, obtemos uma nova tabela com base \{s_{1},x_{1},s_{3}\} e valores atualizados.

Passo 5

Recalculamos os custos reduzidos na nova tabela. O único coeficiente positivo na linha Z resta em x_{2}, então x_{2} entra. Fazemos novamente o teste da razão mínima nas linhas onde o coeficiente de x_{2} é positivo:
\frac{\text{RHS}_{s_{1}}}{4}=7{,}5,\quad \frac{\text{RHS}_{s_{3}}}{2}=5.
O menor é 5, na linha que antes era s_{3}, então s_{3} sai da base e pivotamos em (\text{linha }s_{3},x_{2}). Após este segundo pivô, a base passa a ser \{s_{1},x_{1},x_{2}\}.

Passo 6

Na tabela resultante, todos os custos reduzidos c_j - z_j para variáveis não-básicas são não positivos, o que indica que atingimos a solução ótima. Lemos então
x_{1}=15,\quad x_{2}=5,\quad x_{3}=0,
e o valor ótimo da função é
Z=2\cdot 15 -5 +0 = 25.

Resposta

x_{1}=15,\quad x_{2}=5,\quad x_{3}=0,\quad Z_{\max}=25.

Exercícios relacionados