Considere o PPL
\begin{aligned} \min & 2 x_{1}+5 x_{2} \\\ & x_{1}+2 x_{2}-x_{3}=2 \\\ & 3 x_{1}+2 x_{2}-x_{4}=8 \\\ & x_{1}, x_{2} \geq 0 \end{aligned}
(1) Qual o intervalo em que o custo associado a variável x_{2} pode ser alterada de forma que a base ótima do problema (38)-(41) seja ótima para o problema alterado.
(2) Qual o intevarlo em que o lado direito da restrição (40) pode ser alterada de forma que a base ótima do problema (38)-(41) seja ótima para o problema alterado.

Passo 1

O problema é um PPL de minimização com variáveis \(x_{1},x_{2})) e variáveis de folga \(x_{3},x_{4}):
\begin{aligned} \min\;&2x_{1}+5x_{2}\\\ \text{s.a. }\;&x_{1}+2x_{2}-x_{3}=2,\\\ &3x_{1}+2x_{2}-x_{4}=8,\\\ &x_{1},x_{2},x_{3},x_{4}\ge0. \end{aligned}
Queremos
(1) o intervalo de variação do coeficiente c_{2} de x_{2} para que a mesma base ótima permaneça ótima;
(2) o intervalo de variação do lado direito da segunda restrição (que é igual a 8 para que essa base fique ainda viável e ótima.
O conteúdo é análise de sensibilidade em programação linear: vamos precisar achar a base ótima, calcular preços sombra (duais) e reduzir custos, depois ver como mudanças em c_{2} e no vetor b afetam a viabilidade e a otimalidade dessa base.

Passo 2

Encontrar a solução ótima do primal e a base associada. Como são duas restrições, testamos vértices em (x_{1},x_{2})\ge0 de \;x_{1}+2x_{2}\ge2 e \;3x_{1}+2x_{2}\ge8. Os candidatos são (x_{1},x_{2})=(0,4) com custo 20, e (x_{1},x_{2})=(8/3,0) com custo 2\cdot\frac{8}{3}=16/3\approx5{,}33.
Logo a solução ótima é
(x_{1},x_{2})=\Bigl(\tfrac{8}{3},0\Bigr).
Substituindo em \;x_{1}+2x_{2}-x_{3}=2 e 3x_{1}+2x_{2}-x_{4}=8
obtemos
x_{3}=\tfrac{8}{3}-2=\tfrac{2}{3},\quad x_{4}=3\cdot\tfrac{8}{3}-8=0.
Dessa forma podemos escolher como base B=\{x_{1},x_{3}\}, com x_{1}=\frac{8}{3}>0 e x_{3}=\frac{2}{3}>0, e variáveis não básicas x_{2}=0,\;x_{4}=0.

Passo 3

Calcular o vetor dual y e os reduzidos custos para testar variações em c_{2}.
A matriz básica é
A_{B}=\bigl[A_{1}\;A_{3}\bigr] =\begin{pmatrix}1 & -1\\\ 3 & 0\end{pmatrix},
com custos básicos c_{B}=(2,0). O seu inverso é
A_{B}^{-1}=\frac{1}{3}\begin{pmatrix}0 & 1\\\ -3 & 1\end{pmatrix}.
Então o preço sombra é
y^{T}=c_{B}^{T}A_{B}^{-1}=(2,0)\,\frac{1}{3}\begin{pmatrix}0 & 1\\\ -3 & 1\end{pmatrix} =(0,\tfrac{2}{3}).
A coluna de x_{2} é A_{2}=(2,2), assim o reduzido custo de x_{2} vale
\bar c_{2}=c_{2}-y^{T}A_{2} =c_{2}-\Bigl[0,\tfrac{2}{3}\Bigr]\!\cdot\!\begin{pmatrix}2\\\ 2\end{pmatrix} =c_{2}-\tfrac{4}{3}.
Para manter a base ótima precisamos de \bar c_{2}\ge0, ou seja
c_{2}-\tfrac{4}{3}\ge0 \quad\Longrightarrow\quad c_{2}\ge\tfrac{4}{3}.

Passo 4

Analisar variação do lado direito da segunda restrição. Seja o vetor b=(2,\,8+\Delta). A solução básica passa a ser
x_{B}=A_{B}^{-1}b =\frac{1}{3}\begin{pmatrix}0 & 1\\\ -3 & 1\end{pmatrix} \begin{pmatrix}2\\\ 8+\Delta\end{pmatrix} =\begin{pmatrix}\tfrac{8+\Delta}{3}\\[6pt]\tfrac{2+\Delta}{3}\end{pmatrix},
que corresponde a \bigl(x_{1},x_{3}\bigr). Para manter viabilidade precisamos
\tfrac{8+\Delta}{3}\ge0 \quad\text{e}\quad \tfrac{2+\Delta}{3}\ge0 \;\Longrightarrow\; \Delta\ge-2.
Não há limite superior em \Delta. Portanto o lado direito 8 pode variar para
8+\Delta\;\ge\;6 \quad\Longrightarrow\quad \text{variação em }[6,\infty).çã]

Resposta

(1) c_{2} pode variar em \bigl[\tfrac{4}{3},\infty\bigr).
(2) O lado direito da segunda restrição pode variar em [6,\infty).

Exercícios relacionados