<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 = -13x_1 + 10x_2 + 8x_3 - 10x_4- 22x_5$\\ subject
to&amp;$-2x_1 +x_2 + 4x_3 - 2x_4 - 2x_5 \leq 5$\\&amp;$-4x_1 + 2x_2 + x_3
- 2x_4 - 6x_5\leq 13$\\&amp;$0 \leq x_1 \leq 1$\\&amp;$0 \leq x_2 \leq
20$\\&amp;$0 \leq x_3 \leq 4$\\&amp;$0 \leq x_4 \leq 3$\\&amp;$0 \le x_5 \le
5$.
\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 \le 3$.

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

\end{description}


ANSWER


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


\begin{tabular}{c|cccccccc|cc}
Basic&amp;$z$&amp;$x_1$&amp;$x_2$&amp;$x_3$&amp;$x_4$&amp;$x_5$&amp;$s_1$&amp;$s_2$&amp;&amp;Ratio\\
\hline $s_1$&amp;0&amp;$-2$&amp;1&amp;4&amp;$-2$&amp;$-2$&amp;1&amp;0&amp;5&amp;5\\
$s_2$&amp;0&amp;$-4$&amp;2&amp;1&amp;$-2$&amp;$-6$&amp;0&amp;1&amp;13&amp;$\frac{13}{2}$\\
&amp;1&amp;3&amp;$-10$&amp;$-8$&amp;10&amp;22&amp;0&amp;0&amp;0
\end{tabular}

\begin{tabular}{c|cccccccc|cc}
Basic&amp;$z'$&amp;$x_1$&amp;$x_2$&amp;$x_3$&amp;$x_4$&amp;$x_5$&amp;$s_1$&amp;$s_2$&amp;&amp;Ratio\\
\hline $x_2$&amp;0&amp;$-2$&amp;1&amp;4&amp;$-2$&amp;$-2$&amp;1&amp;0&amp;5&amp;$\frac{15}{2}$\\
$s_2$&amp;0&amp;0&amp;0&amp;$-7$&amp;2&amp;$-2$&amp;$-2$&amp;1&amp;3&amp;$\frac{3}{2}$\\ \hline
&amp;1&amp;$-7$&amp;0&amp;32&amp;$-10$&amp;2&amp;10&amp;0&amp;50
\end{tabular}

\begin{tabular}{c|cccccccc|cc}
Basic&amp;$z'$&amp;$x_1$&amp;$x_2$&amp;$x_3$&amp;$x_4$&amp;$x_5$&amp;$s_1$&amp;$s_2$&amp;&amp;Ratio\\
\hline $x_2$&amp;0&amp;$-2$&amp;1&amp;$-3$&amp;0&amp;$-4$&amp;$-1$&amp;1&amp;8&amp;3\\
$x_4$&amp;0&amp;0&amp;0&amp;$-\frac{7}{2}$&amp;1&amp;$-1$&amp;$-1$&amp;$\frac{1}{2}$&amp;$\frac{3}{2}$&amp;$\frac{3}{2}$\\
\hline &amp;1&amp;$-7$&amp;0&amp;$-3$&amp;0&amp;$-8$&amp;0&amp;5&amp;65
\end{tabular}

Make substitution $x'_4=3-x_4$

\begin{tabular}{c|cccccccc|c}
Basic&amp;$z$&amp;$x_1$&amp;$x_2$&amp;$x_3$&amp;$x_4'$&amp;$x_5'$&amp;$s_1$&amp;$s_2$&amp;\\ \hline
$x_2$&amp;0&amp;$-2$&amp;1&amp;11&amp;4&amp;0&amp;3&amp;$-1$&amp;2+12=14\\
$x_5$&amp;0&amp;0&amp;0&amp;$\frac{7}{2}$&amp;1&amp;1&amp;1&amp;$-\frac{1}{2}$&amp;$-\frac{3}{2}+3=\frac{3}{2}$\\
&amp;1&amp;$-7$&amp;0&amp;25&amp;8&amp;0&amp;8&amp;1&amp;53+24=77
\end{tabular}

Make substitution $x_1'=1-x_1$

\begin{tabular}{c|cccccccc|cc}
Basic&amp;$z$&amp;$x_1'$&amp;$x_2$&amp;$x_3$&amp;$x_4'$&amp;$x_5$&amp;$s_1$&amp;$s_2$&amp;\\ \hline
$x_2$&amp;0&amp;2&amp;1&amp;11&amp;4&amp;0&amp;3&amp;$-1$&amp;16\\
$x_5$&amp;0&amp;0&amp;0&amp;$\frac{7}{2}$&amp;1&amp;1&amp;1&amp;$-\frac{1}{2}$&amp;$\frac{3}{2}$\\
&amp;1&amp;7&amp;0&amp;25&amp;8&amp;0&amp;8&amp;1&amp;84
\end{tabular}

Optimal solution

$$x_1;=0\ x_2=16\ x_3=0\ x_4'=0\ x_5=\frac{3}{2}$$

$$x_1=1\ x_2=16\ x_3=0\ x_4=3\ x_5=\frac{3}{2}\ z=84$$


\begin{description}

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

For non-negativity $16+3\delta\geq0,\ \delta\geq-\frac{16}{3},\
\frac{3}{2}+\delta\geq0\ \delta\geq-\frac{3}{2}$

For variables to remain within bounds $16+3\delta\leq20\
\delta\leq\frac{4}{3},\ \frac{3}{2}+\delta\leq5\
\delta\leq\frac{7}{2}$

Therefore the required range is
$-\frac{3}{2}\leq\delta\leq\frac{4}{3}$

If the upper bound constraint is $x_4\leq3+\delta$, then the
right-hand sides in the final tableau become $16+4\delta,\
\frac{3}{2}+\delta$.

For non negativity, $16+4\delta\geq0\ \delta\geq-4,\
\frac{3}{2}+\delta\geq0\ \delta\geq-\frac{3}{2}$

For variables to remain within their lower bounds
$16+4\delta\leq20\ \delta\leq1,\ \frac{3}{2}+\delta\leq5\
\delta\leq\frac{7}{2}$

Therefore the required range is $-\frac{3}{2}\leq\delta\leq1$

\item[(ii)]
The $z$ row of the final tableau becomes

\begin{tabular}{cccccccc}
$7+2\delta$&amp;0&amp;$25+11\delta$&amp;$8+4\delta$&amp;0&amp;$8+3\delta$&amp;$1-\delta$&amp;$84+16\delta$
\end{tabular}

For non-negativity $-2\leq\delta\leq1$

\end{description}




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