Sendo dado o problema de programação linear
(P): \text { maximizar } z=3 x_{1}+5 x_{2}
sujeito a:
\begin{array}{rlrl} x_{1}+x_{3} & & = & 4 \\\ x_{2}+x_{4} & & = & 6 \\\\ 3 x_{1}+2 x_{2} & +x_{5} & = & 18 \\\ x_{j} \geq 0, j=1,2,3,4,5 . & & \end{array}
Verificar que as colunas associadas às variáveis x_{1}, x_{2}, x_{3} formam um base ótima do (P).

Passo 1

O problema é um PL em forma de igualdade
(P): \text{maximizar }z=3x_{1}+5x_{2}
sujeito a
\begin{cases} x_{1}+x_{3}=4,\\\ x_{2}+x_{4}=6,\\\\ 3x_{1}+2x_{2}+x_{5}=18,\\\ x_{j}\ge0,\;j=1,\dots,5. \end{cases}
Queremos checar que a base B=\{x_{1},x_{2},x_{3}\} é ótima, ou seja, que a solução básica associada é viável (primal factível) e que os custos reduzidos dos não‐básicos são \le0 (dual factível para maximização).

Passo 2

Com B=\{1,2,3\}, as variáveis não‐básicas são x_{4}=0 e x_{5}=0. Daí basta resolver o sistema para x_{1},x_{2},x_{3}:
Da segunda equação,
x_{2}+x_{4}=6\implies x_{2}=6.
Da terceira,
3x_{1}+2x_{2}=18\implies3x_{1}+2\cdot6=18\implies x_{1}=2.
Da primeira,
x_{1}+x_{3}=4\implies2+x_{3}=4\implies x_{3}=2.
Logo a solução básica é
(x_{1},x_{2},x_{3},x_{4},x_{5})=(2,6,2,0,0).

Passo 3

Verificamos viabilidade primal: todos os componentes são \ge0. Logo a solução é primal factível.

Passo 4

Vamos achar os multiplicadores simplex \pi\) resolvendo \[\pi^{T}B=c_{B}^{T},
onde
B=[\,a_{1}\;a_{2}\;a_{3}\,] =\begin{pmatrix}1&0&1\\\ 0&1&0\\\ 3&2&0\end{pmatrix}, \quad c_{B}=(3,5,0).
Escrevendo \pi=(\pi_{1},\pi_{2},\pi_{3}), as equações são
\pi^{T}a_{1}=3,\quad \pi^{T}a_{2}=5,\quad \pi^{T}a_{3}=0.
Isto dá o sistema
\begin{cases} \pi_{1}+3\pi_{3}=3,\\\ \pi_{2}+2\pi_{3}=5,\\\ \pi_{1}=0, \end{cases}
cuja solução é (\pi=(0,3,1)].

Passo 5

Calculamos os custos reduzidos dos não‐básicos x_{4} e x_{5}:
Para x_{4}, a_{4}=(0,1,0) e c_{4}=0,
r_{4}=c_{4}-\pi^{T}a_{4}=0-(0+3\cdot1+1\cdot0)=-3.
Para x_{5}, a_{5}=(0,0,1) e c_{5}=0,
r_{5}=c_{5}-\pi^{T}a_{5}=0-(0+3\cdot0+1\cdot1)=-1.
Como r_{4}\le0 e r_{5}\le0, a condição de optimalidade dual (para maximização) está satisfeita.

Resposta

As colunas associadas a x_{1},x_{2},x_{3} formam uma base ótima, com solução básica
(x_{1},x_{2},x_{3},x_{4},x_{5})=(2,6,2,0,0).

Exercícios relacionados