\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 = -13x_1 + 10x_2 + 8x_3 - 10x_4- 22x_5$\\ subject
to&$-2x_1 +x_2 + 4x_3 - 2x_4 - 2x_5 \leq 5$\\&$-4x_1 + 2x_2 + x_3
- 2x_4 - 6x_5\leq 13$\\&$0 \leq x_1 \leq 1$\\&$0 \leq x_2 \leq
20$\\&$0 \leq x_3 \leq 4$\\&$0 \leq x_4 \leq 3$\\&$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&$z$&$x_1$&$x_2$&$x_3$&$x_4$&$x_5$&$s_1$&$s_2$&&Ratio\\
\hline $s_1$&0&$-2$&1&4&$-2$&$-2$&1&0&5&5\\
$s_2$&0&$-4$&2&1&$-2$&$-6$&0&1&13&$\frac{13}{2}$\\
&1&3&$-10$&$-8$&10&22&0&0&0
\end{tabular}

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

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

Make substitution $x'_4=3-x_4$

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

Make substitution $x_1'=1-x_1$

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

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

\end{description}




\end{document}