\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

QUESTION


Solve the following linear programming problem.

\begin{tabular}{ll}
 Maximize&$z = 18x_1 +
3x_2 + x_3 + 16x_4+3x_5$\\subject to&$4x_1 + 2x_2 - x_3 + 3x_4 +
x_5 \leq 24$\\&$8x_1 +x_2 + x_3 + 4x_4 + 4x_5\leq 30$\\&$0 \leq
x_1 \leq 3$\\&$0 \leq x_2 \leq 9$\\&$0 \leq x_3 \leq 10$\\&$0 \leq
x_4 \leq 6$\\&$0 \le x_5 \le 15$.
\end{tabular}

\begin{description}

\item[(i)]
For the first constraint, give the range of values for the right
hand side within which the optimal basis remains unaltered. Also,
perform this ranging analysis for the upper bound constraint $x_4
\leq 6$.

\item[(ii)]
If the last constraint is altered to become $-3 \leq x_5 \leq 20$,
find how your solution is affected.

\end{description}

ANSWER

Add slack variables $s_1\geq0,s_2\geq0$, and use the bounded
variable simplex method.

\begin{tabular}{c|cccccccc|c}
Basic&$z$&$x_1$&$x_2$&$x_3$&$x_4$&$x_5$&$s_1$&$s_2$\\ \hline
$s_1$&0&4&2&$-1$&3&1&1&0&24\\ $s_2$&0&8&1&1&4&4&0&1&30\\ \hline
&1&$-18$&$-3$&$-16$&$-3$&0&0&0
\end{tabular}

Substitute $x_1'=3-x_1$

\begin{tabular}{c|cccccccc|c}
Basic&$z$&$x_1'$&$x_2$&$x_3$&$x_4$&$x_5$&$s_1$&$s_2$\\ \hline
$s_1$&0&$-4$&2&$-1$&3&1&1&0&12\\ $s_1$&0&8&1&1&4&4&0&1&6\\ \hline
&1&18&$-3$&0&13&0&4&78
\end{tabular}


\begin{tabular}{c|cccccccc|c}
Basic&$z$&$x_1'$&$x_2$&$x_3$&$x_4$&$x_5$&$s_1$&$s_2$\\ \hline
$s_1$&0&2&$\frac{5}{4}$&$-\frac{7}{4}$&0&$-2$&1&$-\frac{3}{4}$&
$\frac{15}{2}$\\
$x_4$&0&$-2$&$\frac{1}{4}$&$\frac{1}{4}$&1&1&0&$\frac{1}{4}$&
$\frac{3}{2}$\\ \hline &1&$-14$&1&3&0&13&0&4&78
\end{tabular}


Substitute $x_4'=6-x_4$

\begin{tabular}{c|cccccccc|c}
Basic&$z$&$x_1'$&$x_2$&$x_3$&$x_4'$&$x_5$&$s_1$&$s_2$\\ \hline
$s_1$&0&0&$\frac{3}{2}$&$-\frac{3}{2}$&$-1$&$-1$&1&$-\frac{1}{2}$
&$9-6=3$\\
$x_1'$&0&1&$-\frac{1}{8}$&$-\frac{1}{8}$&$\frac{1}{2}$&$-\frac{1}{2}
$&0&$-\frac{1}{8}$&$-\frac{3}{4}+3=\frac{9}{4}$\\ \hline
&1&0&$-\frac{3}{4}$&$\frac{5}{4}$&7&6&0&$\frac{9}{4}$&
$\frac{135}{2}+42=\frac{219}{2}$
\end{tabular}


\begin{tabular}{c|cccccccc|c}
Basic&$z$&$x_1$&$x_2$&$x_3$&$x_4$&$x_5$&$s_1$&$s_2$\\
$x_2$&0&0&1&$-1$&$-\frac{2}{3}$&$-\frac{2}{3}$&$-\frac{1}{3}$&2\\
$x_1'$&0&1&0&$-\frac{1}{4}$&$\frac{5}{12}$&$-\frac{7}{12}$&
$\frac{1}{12}$&$-\frac{1}{6}$&$\frac{5}{2}$\\
&1&0&0&$\frac{1}{2}$&$\frac{13}{2}$&$\frac{11}{2}$&$\frac{1}{2}$
&2&111
\end{tabular}


The optimal solution is $$x_1'=\frac{5}{2},\ x_2=2,\ x_3=0,\
x_4'=0,\ x_5=0$$ $$x_1=\frac{1}{2},\ x_2=2,\ x_3=0,\ x_4=6,\
x_5=0,\ z=111$$

\begin{description}

\item[(i)]
If the first RHS becomes $24+\delta$, the RJHS columns in the
final tableau becomes

\begin{eqnarray*}
2&+&\frac{2}{3}\delta\\ \frac{5}{2}&+&\frac{1}{12}\delta\\
11&+&\frac{1}{2}\delta
\end{eqnarray*}

For non-negativity $\delta\geq-3,\ \delta\geq-30$

For $$x_1'\leq3:\frac{5}{2}+\frac{1}{12}\delta\leq3\ \delta\leq6$$

$$x_2\leq9:2+\frac{2}{3}\delta\leq9\ \delta\leq\frac{21}{2}$$

The required range is $-3\leq\delta\leq6$

If the current $x_4'$ column is changed from $6-x_4$ to
$6+\delta-x_4$, the RHS's become

\begin{eqnarray*}
2&-&\frac{2}{3}\delta\\ \frac{5}{2}&+&\frac{5}{12}\delta\\
11&+&\frac{13}{2}\delta
\end{eqnarray*}

For non-negativity $\delta\leq3,\ \delta\geq-6$

For $$x_1'\leq3\ \frac{5}{2}+\frac{5}{12}\delta\leq3\
\delta\leq\frac{6}{5}$$

$$x_2\leq9\ 2-\frac{2}{3}\delta\leq9\ \delta\geq-\frac{21}{2}$$

The required range is $-6\leq\delta\leq\frac{6}{5}$

\item[(ii)]
Change the variable: $\overline{x}_5=x_5+3$, so that
$0\leq\overline{x}_5\leq23$. The tableau is

\begin{center}
\begin{tabular}{c|c}
$\overline{x}_5-3$\\ \hline $-\frac{2}{3}$&2\\
$-\frac{7}{12}$&$\frac{5}{2}$\\ \hline $\frac{11}{2}$&$111$
\end{tabular}
\end{center}

which becomes

\begin{center}
\begin{tabular}{c|c}
$\overline{x}_5$\\ $-\frac{2}{3}$&0\\
$-\frac{7}{12}$&$\frac{3}{4}$\\ \hline
$\frac{11}{2}$&$127\frac{1}{2}$
\end{tabular}
\end{center}

Thus $z$ increases by $\frac{33}{2}$, and the values of $x_1$ and
$x_2$ become $x_1=\frac{9}{4},\ x_2=0$.

\end{description}




\end{document}