Considere o PPL a seguir.
\begin{aligned} \max & x_{1}-x_{2}+2 x_{3} \\\ & x_{1}+x_{2}+x_{3} \leq 6 \\\ & -x_{1}+2 x_{2}+3 x_{3} \leq 9 \\\ & x_{j} \geq 0, \quad j=1,2,3 \end{aligned}
(1) Resolva o problema (18)-(21) usando o método primal do simplex.
(2) Encontre o problema dual associado ao problema (18)-(21) e resolva o mesmo.
(3) Supondo que o lado direito da restrição (19) do problema (18)-(21) seja acrescido de uma unidade. A base ótima do problema (18)-(21) é ótima para o novo problema?
(4) Supondo que o vetor de custos do problema (18)-(21) seja alterado para (2, 1, 1). A base ótima do problema (18)-(21) é ótima para o novo problema?
(5) Se uma variável for incluída ao problema (18)-(21) com custo igual a -1 e com os coeficientes na restrições igual a (2,1). A base ótima do problema (18)-(21) é ótima para o novo problema?

Passo 1

O enunciado dá um problema de programação linear com três variáveis e duas restrições de tipo “ <=\)”. O objetivo é maximizar \[x_{1} - x_{2} + 2x_{3}
sujeito a
\begin{cases} x_{1} + x_{2} + x_{3} \le 6,\\\\ -\,x_{1} + 2x_{2} + 3x_{3} \le 9,\\\ x_{j}\ge0,\;j=1,2,3. \end{cases}
Para usar o método primal do simplex, vamos (a) introduzir as folgas s_{1},s_{2}\], (b) montar o tableau inicial, \text{(c)} escolher variável de entrada por coeficiente negativo no \(z-row e (d) pivotar até não haver mais coeficiente negativo no z-row.

Passo 2

Introduzindo s_{1},s_{2} temos o sistema
\begin{array}{r|cccccc} \text{Base} & x_{1} & x_{2} & x_{3} & s_{1} & s_{2} & \text{RHS} \\\ \hline s_{1} & 1 & 1 & 1 & 1 & 0 & 6 \\\ s_{2} & -1 & 2 & 3 & 0 & 1 & 9 \\\ \hline z & -1 & 1 & -2 & 0 & 0 & 0 \end{array}
em que a linha z armazena os \emph{reduced costs} -c_j. Como há coeficientes negativos em z nas colunas x_{1} e x_{3}, escolhemos primeiro x_{3} (maior valor absoluto de coeficiente negativo).

Passo 3

Pivot em coluna x_{3}, linha s_{2} ( \min\{6/1,\;9/3\}=3). Dividindo a linha s_{2} por 3 e atualizando as demais linhas:
\begin{array}{r|cccccc} \text{Base}&x_{1}&x_{2}&x_{3}&s_{1}&s_{2}&\text{RHS}\\hline s_{1}&4/3&1/3&0&1&-1/3&3\\\ x_{3}&-1/3&2/3&1&0&1/3&3\\hline z&-5/3&7/3&0&0&2/3&6 \end{array}
Agora em z só resta coeficiente negativo em x_{1}, logo x_{1} entra.

Passo 4

Pivot em coluna x_{1}, linha s_{1} ( \min\{3/(4/3)\}=9/4). Dividindo a linha s_{1} por 4/3 e atualizando:
\begin{array}{r|cccccc} \text{Base}&x_{1}&x_{2}&x_{3}&s_{1}&s_{2}&\text{RHS}\\hline x_{1}&1&1/4&0&3/4&-1/4&9/4\\\ x_{3}&0&3/4&1&1/4&1/4&15/4\\hline z&0&11/4&0&5/4&1/4&39/4 \end{array}
Não há mais coeficientes negativos em z: chegamos ao ótimo.

Passo 5

Da tabela final, as variáveis básicas são x_{1}=9/4, x_{3}=15/4 e as não-básicas x_{2}=s_{1}=s_{2}=0. O valor ótimo é
z^* \;=\; \frac{39}{4}.

Passo 6

O dual de
\max\{\,c^T x\mid A x\le b,\;x\ge0\}
é
\min\{\,b^T y\mid A^T y\ge c,\;y\ge0\}.
Aqui b=(6,9),
A=\begin{pmatrix}1&1&1\\\ -1&2&3\end{pmatrix}, \quad c=(1,-1,2).
O dual fica
\begin{aligned} \min\;6y_{1}+9y_{2}\\\ y_{1}-y_{2}\ge1,\\\ y_{1}+2y_{2}\ge-1\;(\text{redundante}),\\\ y_{1}+3y_{2}\ge2,\\\ y_{1},y_{2}\ge0. \end{aligned}
Pelo gráfico ou resolvendo o sistema de igualdades em
\{y_{1}-y_{2}=1,\;y_{1}+3y_{2}=2\} obtém-se
y_{1}=\frac54,\quad y_{2}=\frac14,
com custo mínimo 6\cdot\frac54+9\cdot\frac14=39/4, igual ao primal.

Passo 7

Supondo que o RHS da primeira restrição ( 6) vire 7, o novo b=(7,9). A base ótima é dada pelas colunas de x_{1},x_{3}, cujo inverso B^{-1} multiplicado em b gera
x_{B}=B^{-1}b=(3,4)\ge0.
Como as reduções de custo não mudam com alteração de b, a base continua viável e ótima.

Passo 8

Se o vetor de custos virar c'=(2,1,1), mantida a base \{x_{1},x_{3}\}, calculamos o reduced cost de s_{2} e achamos
r_{s_{2}} = 0 - c'_{B}\,B^{-1}a_{s_{2}} = +\frac14 >0.
Como há custo reduzido positivo, a base não é mais ótima.

Passo 9

Incluindo uma nova variável x_{4} com custo c_{4}=-1 e coluna a_{4}=(2,1), o reduced cost é
r_{4} = -1 - (1,2)\,B^{-1}\begin{pmatrix}2\\\ 1\end{pmatrix} = -\frac{15}{4}<0.
Não há custos reduzidos positivos, logo a base original permanece ótima.

Resposta

( 1) x^{*}=(9/4,0,15/4), z^{*}=39/4.
( 2) Dual: \min\{6y_{1}+9y_{2}\} sujeito a
\,y_{1}-y_{2}\ge1,\;y_{1}+3y_{2}\ge2,\;y\ge0.
Solução y^{*}=(5/4,1/4), valor 39/4.
( 3) Sim.
( 4) Não.
( 5) Sim.

Exercícios relacionados