<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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&amp;$z = -7x_1 + 2x_2 + 7x_3 - x_4$\\subject to&amp;$4x_1 - x_2 +
x_3 + 2x_4 \leq 8$\\&amp; $6x_1 + 3x_2 + 2x_3 - 5x_4 \leq 25$\\&amp;$0
\leq x_1 \leq 1$\\&amp;$0 \leq x_2 \leq 11$\\&amp;$0 \leq x_3 \leq 9$\\&amp;$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&amp;$z$&amp;$x_1$&amp;$x_2$&amp;$x_3$&amp;$x_4$&amp;$s_1$&amp;$s_2$&amp;&amp;Ratio\\ \hline
$s_1$&amp;0&amp;4&amp;$-1$&amp;1&amp;2&amp;1&amp;0&amp;8&amp;8\\
$s_2$&amp;0&amp;6&amp;3&amp;2&amp;$-5$&amp;0&amp;1&amp;25&amp;$\frac{25}{2}$\\ \hline
&amp;1&amp;7&amp;$-2$&amp;$-7$&amp;1&amp;0&amp;0&amp;0
\end{tabular}

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

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

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

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

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

\begin{tabular}{c|ccccccc|c}
Basic&amp;$z$&amp;$x_1$&amp;$x_2$&amp;$x_3'$&amp;$x_4'$&amp;$s_1$&amp;$s_2$\\ \hline
$x_2$&amp;0&amp;$-\frac{2}{5}$&amp;1&amp;0&amp;$\frac{9}{5}$&amp;$-\frac{2}{5}$&amp;$\frac{1}{5}$&amp;$\frac{9}{5}+9=\frac{54}{5}$\\
$x_3;$&amp;0&amp;$-\frac{18}{5}$&amp;0&amp;1&amp;$\frac{1}{5}$&amp;$-\frac{3}{5}$&amp;$-\frac{1}{5}$&amp;$-\frac{4}{5}+1=\frac{1}{5}$\\
&amp;1&amp;$\frac{157}{5}$&amp;0&amp;0&amp;$\frac{6}{5}$&amp;$\frac{17}{5}$&amp;$\frac{9}{5}$&amp;$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$&amp;$\delta\geq-\frac{1}{2}$\\
$\frac{1}{5}-\frac{3}{5}\delta\leq9$&amp;$\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$&amp;$\delta\leq\frac{1}{9}$\\
$\frac{1}{5}+\frac{1}{5}\delta\leq9$&amp;$\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&amp;\leq&amp;\frac{157}{2}\\ \delta&amp;\geq&amp;-\frac{2}{3}\\
\delta&amp;\leq&amp;\frac{17}{2}\\ \delta&amp;\geq&amp;-9
\end{eqnarray*}

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

\end{description}




\end{document}
</pre></body></html>