Considere o seguinte PPL.
\begin{aligned} \min & x_{1}-x_{2} \\\ & 2 x_{1}+x_{2}+x_{3}=4 \\\ & x_{1}+2 x_{2}+x_{4}=6 \\\ & x_{1}, x_{2}, x_{3}, x_{4} \geq 0 \end{aligned}
Resolva o PPL utilizando o método simplex revisado. Considere na base inicial as colunas a_{3} e a_{4}.

Passo 1

O enunciado pede para minimizar
\min\;x_{1}-x_{2}
sujeito a
2x_{1}+x_{2}+x_{3}=4, \quad x_{1}+2x_{2}+x_{4}=6, \quad x_{1},x_{2},x_{3},x_{4}\ge0.
O método simplex revisado requer que escolhamos uma base inicial. Vamos usar as colunas a_{3} e a_{4} como variáveis básicas.

Passo 2

Definimos o conjunto básico B=\{3,4\} e o não básico N=\{1,2\}.
As colunas da matriz A são
a_{1}=\begin{pmatrix}2\\\ 1\end{pmatrix},\; a_{2}=\begin{pmatrix}1\\\ 2\end{pmatrix},\; a_{3}=\begin{pmatrix}1\\\ 0\end{pmatrix},\; a_{4}=\begin{pmatrix}0\\\ 1\end{pmatrix},
logo
B=\bigl[a_{3}\;a_{4}\bigr] = \begin{pmatrix}1&0\\\ 0&1\end{pmatrix}, \quad B^{-1}=\begin{pmatrix}1&0\\\ 0&1\end{pmatrix}.
O vetor de custos é
c=(1,\,-1,\,0,\,0),
então
c_{B}=(0,0),\quad c_{N}=(1,-1).
A solução básica inicial é
x_{B}=B^{-1}b =\begin{pmatrix}4\\\ 6\end{pmatrix},
isto é, x_{3}=4,\;x_{4}=6 e x_{1}=x_{2}=0.

Passo 3

Calculamos o vetor de multiplicadores \,y resolvendo
B^{T}y=c_{B} \;\Longrightarrow\; y=(0,0).
Os custos reduzidos para j\in N são
r_{j}=c_{j}-y^{T}a_{j} \;\Longrightarrow\; r_{1}=1,\quad r_{2}=-1.
Como estamos minimizando, escolhemos a variável com r_{j}<0. Aqui r_{2}=-1, logo x_{2} entra na base.

Passo 4

O vetor de direção é
d = B^{-1}a_{2} = a_{2} =\begin{pmatrix}1\\\ 2\end{pmatrix}.
Fazemos o teste de razão \min\{x_{B,i}/d_{i}\}:
\frac{4}{1}=4,\quad\frac{6}{2}=3,
o mínimo é 3, correspondendo à segunda linha, logo x_{4} sai da base.

Passo 5

Atualizamos a base para B=\{3,2\}. A nova matriz básica é
B=\begin{pmatrix}1&1\\\ 0&2\end{pmatrix},
cuja inversa é
B^{-1}=\begin{pmatrix}1&-\tfrac12\\[6pt]0&\tfrac12\end{pmatrix}.
A solução básica passa a ser
x_{B}=B^{-1}b =\begin{pmatrix}1\\\ 3\end{pmatrix},
isto é, x_{3}=1,\;x_{2}=3 e x_{1}=x_{4}=0.
Os custos básicos agora são c_{B}=(0,\,-1).]

Passo 6

Resolvemos
B^{T}y=c_{B} \;\Longrightarrow\; y=(0,\,-\tfrac12).
Calculamos os custos reduzidos dos não básicos N=\{1,4\}:
r_{1}=c_{1}-y^{T}a_{1} =1-\bigl(0\cdot2+(-\tfrac12)\cdot1\bigr)=\tfrac32,
r_{4}=c_{4}-y^{T}a_{4} =0-\bigl(0\cdot0+(-\tfrac12)\cdot1\bigr)=\tfrac12.
Todos os r_{j}\ge0 indicam que a solução é ótima.

Resposta

x_{1}=0,\quad x_{2}=3,\quad x_{3}=1,\quad x_{4}=0 com valor ótimo
\min\,(x_{1}-x_{2})=0-3=-3.

Exercícios relacionados