\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

QUESTION

Solve the following linear programming problem using the bounded
variable simplex method.

\begin{tabular}{ll}
Maximize&$z = -7x_1 + 2x_2 + 7x_3 - x_4$\\subject to&$4x_1 - x_2 +
x_3 + 2x_4 \leq 8$\\& $6x_1 + 3x_2 + 2x_3 - 5x_4 \leq 25$\\&$0
\leq x_1 \leq 1$\\&$0 \leq x_2 \leq 11$\\&$0 \leq x_3 \leq 9$\\&$0
\leq x_4 \leq 5$.
\end{tabular}

\begin{description}

\item[(i)]
 For the first constraint, give the range 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 5$.

\item[(ii)]
If the objective function coefficient of $x_2$ changes to
$2+\delta$, for what range of values of $\delta$ is the change in
the maximum value of $z$ proportional to $\delta$?

\end{description}


ANSWER


\begin{tabular}{c|ccccccc|cc}
Basic&$z$&$x_1$&$x_2$&$x_3$&$x_4$&$s_1$&$s_2$&&Ratio\\ \hline
$s_1$&0&4&$-1$&1&2&1&0&8&8\\
$s_2$&0&6&3&2&$-5$&0&1&25&$\frac{25}{2}$\\ \hline
&1&7&$-2$&$-7$&1&0&0&0
\end{tabular}

\begin{tabular}{c|ccccccc|cc}
Basic&$z$&$x_1$&$x_2$&$x_3$&$x_4$&$s_1$&$s_2$&&Ratio\\ \hline
$x_3$&0&4&$-1$&1&2&1&0&8&1\\
$s_2$&0&$-2$&5&0&$-9$&$-2$&1&9&$\frac{9}{5}$\\ \hline
&1&35&$-9$&0&15&7&0&$56$
\end{tabular}

Perform simplex iteration and substitute $x_3'=9-x_3$.

\begin{tabular}{c|ccccccc|cc}
Basic&$z$&$x_1$&$x_2$&$x_3'$&$x_4$&$s_1$&$s_2$&&Ratio\\ \hline
$x_2$&0&$-4$&1&1&$-2$&$-1$&0&$-8+9=1$\\
$s_2$&0&18&0&$-5$&1&3&1&$49-45=4$\\ \hline
&1&$-1$&0&9&$-3$&$-2$&0&$-16+81=65$
\end{tabular}

\begin{tabular}{c|ccccccc|cc}
Basic&$z$&$x_1$&$x_2$&$x_3'$&$x_4$&$s_1$&$s_2$\\ \hline
$x_2$&0&32&1&$-9$&0&5&1&9&$\frac{2}{9}$\\
$x_4$&0&18&0&$-5$&1&3&1&4&$\frac{1}{5}$\\ \hline
&1&53&0&$-6$&0&7&3&77
\end{tabular}

Perform simplex iteration and substitute $x_4'=5-x_4$

\begin{tabular}{c|ccccccc|c}
Basic&$z$&$x_1$&$x_2$&$x_3'$&$x_4'$&$s_1$&$s_2$\\ \hline
$x_2$&0&$-\frac{2}{5}$&1&0&$\frac{9}{5}$&$-\frac{2}{5}$&$\frac{1}{5}$&$\frac{9}{5}+9=\frac{54}{5}$\\
$x_3;$&0&$-\frac{18}{5}$&0&1&$\frac{1}{5}$&$-\frac{3}{5}$&$-\frac{1}{5}$&$-\frac{4}{5}+1=\frac{1}{5}$\\
&1&$\frac{157}{5}$&0&0&$\frac{6}{5}$&$\frac{17}{5}$&$\frac{9}{5}$&$72\frac{1}{5}+6=78\frac{1}{5}$
\end{tabular}

Thus we have an optimal solution

$$x_1=0\ x_2=10\frac{4}{5}\ x_3'=\frac{1}{5}\ x_4'=0\
x_3=8\frac{4}{5}\ x_4=5\ z=78\frac{1}{5}$$


\begin{description}

\item[(i)]
If the right hand side of the first constraint is $8+\delta$, then
the right hand sides in the final tableau are
$\frac{54}{5}=\frac{2}{5}\delta\ \ \frac{1}{5}-\frac{3}{5}\delta$

For non-negativity, $\delta\leq27\ \delta\leq\frac{1}{3}$.

For basic variables to be in the range
\begin{tabular}{ll}$\frac{54}{5}-\frac{2}{5}\delta\leq11$&$\delta\geq-\frac{1}{2}$\\
$\frac{1}{5}-\frac{3}{5}\delta\leq9$&$\delta\geq-\frac{44}{3}$
\end{tabular}

Thus, the range is $-\frac{1}{2}\leq\delta\leq\frac{1}{3}$.

If $x_4\leq5$ is replaced by $x_4\leq5+\delta$, then right hand
sides become $\frac{54}{5}+\frac{9}{5}\delta\ \
\frac{1}{5}+\frac{1}{5}\delta$

For non-negativity, $\delta\geq-\frac{54}{9}\ \ \delta\geq-1$

For basic variables to be in range
\begin{tabular}{ll}$\frac{54}{5}+\frac{9}{5}\delta\leq11$&$\delta\leq\frac{1}{9}$\\
$\frac{1}{5}+\frac{1}{5}\delta\leq9$&$\delta\leq44$
\end{tabular}

Thus, the range is $-1\leq\delta\leq\frac{1}{9}$.

\item[(ii)]
For the new coefficient, the coefficient in the $z$-row are

$$z+\left(\frac{157}{5}-\frac{2}{5}\delta\right)x_1+\left(\frac{6}{5}+\frac{9}{5}
\delta\right)x_4'+\left(\frac{17}{5}-\frac{2}{5}\delta\right)s_1+\left(\frac{9}{5}
+\frac{1}{5}\delta\right)s_2=78\frac{1}{5}+\frac{54}{5}\delta$$

Thus, we require that

\begin{eqnarray*}
\delta&\leq&\frac{157}{2}\\ \delta&\geq&-\frac{2}{3}\\
\delta&\leq&\frac{17}{2}\\ \delta&\geq&-9
\end{eqnarray*}

so the range is $-\frac{2}{3}\leq\delta\leq\frac{17}{2}$

\end{description}




\end{document}