Question 4. (2.0) Considere o problema
\begin{aligned} \min & -x_{1}-x_{2} \\\ & 2 x_{1}+x_{2}-x_{3}=6 \\\ & x_{1}+2 x_{2}-x_{4}=4 \\\ & x_{1}, x_{2}, x_{3}, x_{4} \geq 0 \end{aligned}
(a) Resolva o problema usando o método primal(ou dual) do simplex. Considere como base inicial B=\left[\begin{array}{ll}a_{1} & a_{4}\end{array}\right].
(b) Acrescente a restrição x_{1} \geq 2 ao problema e em seguida encontre a base ótima para o novo problema.

Passo 1

O enunciado pede para resolver o PL
minimizar -x_{1}-x_{2}
sujeito a
2x_{1}+x_{2}+x_{3}=6
x_{1}+2x_{2}+x_{4}=4 \,x_{i}\ge0.
Vamos trabalhar no formato de maximização z=x_{1}+x_{2} e usar o método do simplex primal. A base inicial dada é
B = [a_{1},\,a_{4}],
isto é, as variáveis básicas são x_{1} e x_{4}.

Passo 2

Calcular a BFS inicial para B=[a_{1},a_{4}].
A matriz básica e o vetor-lado direito são
B=\begin{pmatrix}2&0\\\ 1&1\end{pmatrix}, \quad b=\begin{pmatrix}6\\\ 4\end{pmatrix}.
Então
B^{-1} =\begin{pmatrix}\tfrac12&0\\\ -\tfrac12&1\end{pmatrix}, \quad \begin{pmatrix}x_{1}\x_{4}\end{pmatrix} = B^{-1}\,b =\begin{pmatrix}3\\\ 1\end{pmatrix}.
Logo x_{2}=x_{3}=0 e o valor da função-objetivo é
z = x_{1}+x_{2} = 3.

Passo 3

Calcular os custos reduzidos. Os vetores de custos são \,c=(1,1,0,0), para maximizar, e \,c_{B}=(1,0).
O vetor dos multiplicadores satisfaz
u^{T}B = c_{B}^{T} \;\Longrightarrow\; u = c_{B}^{T}B^{-1} = (1,0)\begin{pmatrix}\tfrac12&0\\\ -\tfrac12&1\end{pmatrix} = \bigl(\tfrac12,0\bigr).
Para x_{2} (coluna a_{2}=(1,2)^{T}):
r_{2} = c_{2} \;-\;u^{T}a_{2} = 1 - \bigl(\tfrac12,0\bigr)\cdot\begin{pmatrix}1\\\ 2\end{pmatrix} = \tfrac12 > 0,
logo x_{2} entra.
A direção básica é
d = B^{-1}a_{2} = \begin{pmatrix}\tfrac12&0\\\ -\tfrac12&1\end{pmatrix} \begin{pmatrix}1\\\ 2\end{pmatrix} = \begin{pmatrix}\tfrac12\\tfrac32\end{pmatrix}.
Razão mínima \min\{\tfrac{3}{1/2},\,\tfrac{1}{3/2}\}=\tfrac23 indica que sai x_{4}. Faz-se o pivô e a nova base torna-se \{x_{1},x_{2}\}.

Passo 4

Com a base \{a_{1},a_{2}\},
B=\begin{pmatrix}2&1\\\ 1&2\end{pmatrix}, \quad B^{-1}=\tfrac13\begin{pmatrix}2&-1\\\ -1&2\end{pmatrix}, \quad b=\begin{pmatrix}6\\\ 4\end{pmatrix}.
A solução básica é
\begin{pmatrix}x_{1}\x_{2}\end{pmatrix} = B^{-1}b = \frac13\begin{pmatrix}2&-1\\\ -1&2\end{pmatrix} \begin{pmatrix}6\\\ 4\end{pmatrix} = \begin{pmatrix}\tfrac83\\tfrac23\end{pmatrix},
com x_{3}=x_{4}=0. Calcula-se u=\tfrac13(1,1) e verifica-se que os custos reduzidos de x_{3},x_{4} são não-positivos, confirmando a otimalidade.
O valor ótimo é
z = x_{1}+x_{2} = \frac{10}{3},
ou seja \min(-x_{1}-x_{2})=-\tfrac{10}{3}.

Passo 5

(b) Acrescenta-se a restrição x_{1}\ge2, que equivale a
-\,x_{1} + x_{5} = -2, \quad x_{5}\ge0.
Formamos o sistema alargado e propomos a base \{a_{1},a_{2},a_{5}\}.

Passo 6

Resolver
\begin{pmatrix} 2&1&0\\\\ 1&2&0\\\\ -1&0&1 \end{pmatrix} \begin{pmatrix}x_{1}\x_{2}\x_{5}\end{pmatrix} = \begin{pmatrix}6\\\ 4\\\ -2\end{pmatrix} \;\Longrightarrow\; x_{1}=\tfrac83,\; x_{2}=\tfrac23,\; x_{5}=\tfrac23,
com x_{3}=x_{4}=0. Os multiplicadores (\tfrac13,\tfrac13,0) geram custos reduzidos não-positivos para x_{3},x_{4}, então a base \{x_{1},x_{2},x_{5}\} permanece ótima.

Resposta

(a) Base ótima \{x_{1},x_{2}\} com
x_{1}=\tfrac83,\quad x_{2}=\tfrac23,\quad x_{3}=x_{4}=0,
valor ótimo \min(-x_{1}-x_{2})=-\tfrac{10}{3}.
(b) Com a nova restrição, a base ótima é \{x_{1},x_{2},x_{5}\} e
x_{1}=\tfrac83,\quad x_{2}=\tfrac23,\quad x_{5}=\tfrac23,\quad x_{3}=x_{4}=0.

Exercícios relacionados