\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

QUESTION

\begin{description}

\item[(a)]
Describe briefly the advantages of the revised simplex method
over the original simplex method in which the full tableau is
computed at each iteration.


\item[(b)]
Solve the following linear programming problem using the
revised simplex method.

\begin{tabular}{ll}
maximize&$z = 9x_1 - 4x_2 + 6x_3 + 8x_4$\\subject to&$x_1 \geq 0$,
$x_2 \geq 0$, $x_3 \geq 0$, $x_4 \geq 0$\\&$3x_1 + 3x_2 - 2x_3 +
5x_4 \leq 6 $\\&$x_1 -2x_2 + 2x_3 + 3x_4  \leq 6$.
\end{tabular}

If the right-hand side of the final constraint changes to
$6+\delta$, find for what range of values of $\delta$ the change
in the maximum value of $z$ is proportional to~$\delta$.

If the objective function coefficient of $x_2$ changes to
$-4+\delta$, find for what range of values of $\delta$ the change
in the maximum value of $z$ is proportional to~$\delta$.

\end{description}


ANSWER


\begin{description}

\item[(a)]
The amount of computation is significantly less for the revised
simplex method when the number of constraints is small compared to
the number of variables. The inaccuracies due to rounding errors
in the original simplex method are avoided in the revised simplex
method if the basis matrix is reinverted at regular periods. The
revised simplex method allows special routines for sparse matrix
manipulations to be exploited when the original constraint matrix
is sparse.

\item[(b)]

$$A=\left(\begin{array}{cccccc}3&3&-2&5&1&0\\
1&-2&2&3&0&1\end{array}\right)\
\mathbf{b}=\left(\begin{array}{c}6\\6\end{array}\right)$$

$$\mathbf{c}^T=(\begin{array}{cccccc}9&-4&6&8&0&0\end{array})$$

Let $x_5,x_6$ be the two slack variables

\begin{center}
\begin{tabular}{c|cc|c}
\hline $x_5$&1&0&6\\ $x_6$&0&1&6\\ \hline
\end{tabular}
\end{center}

\begin{description}

\item[Iteration 1]
$$\mathbf{c}_B^TA_B^{-1}=\left(\begin{array}{cc}0&0\end{array}
\right) \left(\begin{array}{cc}1&0\\0&1\end{array}\right)=\left(
\begin{array}{cc} 0&0\end{array}\right)$$

$$(\mathbf{c}_B^TA^{-1}_BA_N-\mathbf{c}_N^T)\mathbf{x}_N=(0-9)x_1$$

Entering variable is $x_1$

$A^{-1}_B\mathbf{a}_1=\left(\begin{array}{cc}1&0\\
0&1\end{array}\right)\left(\begin{array}{c}3\\1\end{array}\right)=
\left(\begin{array}{c}3\\1\end{array}\right)$
\begin{tabular}{cc}
RHS&Ratio\\ 6&2\\ 6&6
\end{tabular}

Leaving variable is $x_5$

\begin{center}
\begin{tabular}{c|cc|c}
\hline $x_1$&$\frac{1}{3}$&0&2\\ $x_5$&$-\frac{1}{3}$&1&4\\ \hline
\end{tabular}
\end{center}

\item[Iteration 2]
$$\mathbf{c}_B^TA_B^{-1}=\left(\begin{array}{cc}9&0\end{array}
\right) \left(\begin{array}{cc}\frac{1}{3}&0\\
-\frac{1}{3}&1\end{array}\right)=\left(\begin{array}{cc}3&0
\end{array} \right)$$

$$(\mathbf{c}_B^TA^{-1}_BA_N-\mathbf{c}_N^T)\mathbf{x}_N=\left(
\left(\begin{array}{cc}3&0\end{array}\right)
\left(\begin{array}{c}3\\ -2 \end{array}
\right)+4\right)x_2+\left(\left(\begin{array}{cc}3&0\end{array}
\right)\left(
\begin{array}{c}-2\\2\end{array}\right)-6\right)x_3$$

Entering variable is $x_3$

$A_B^{-1}a_3=\left(\begin{array}{cc}\frac{1}{3}&0\\-\frac{1}{3}
&1\end{array}\right)\left(\begin{array}{c}-2\\2\end{array}\right)
=\left(\begin{array}{c}-\frac{2}{3}\\
\frac{8}{3}\end{array}\right)$
\begin{tabular}{cc}
RHS&Ratio\\ 2&-\\ 4&$\frac{3}{2}$
\end{tabular}

Leaving variable is $x_6$

\begin{center}
\begin{tabular}{c|cc|c}
\hline $x_1$&$\frac{1}{4}$&$\frac{1}{4}$&3\\
$x_3$&$-\frac{1}{8}$&$\frac{3}{8}$&$\frac{3}{2}$\\ \hline
\end{tabular}
\end{center}

\item[Iteration 3]
$$\mathbf{c}_B^TA_B^{-1}=\left(\begin{array}{cc}9&6\end{array}
\right)\left(\begin{array}{cc}\frac{1}{4}&\frac{1}{4}\\
-\frac{1}{8}&\frac{3}{8}\end{array}\right)=\left(\begin{array}
{cc}\frac{3}{2}&\frac{9}{2}\end{array}\right)$$

$$(\mathbf{c}_B^TA_B^{-1}A_N-\mathbf{c}_N^T)\mathbf{x}_N=\left(
\left(\begin{array}{cc}\frac{3}{2}&\frac{9}{2}\end{array}\right)
\left(\begin{array}{c}3\\-2\end{array}\right)+4\right)x_2$$

Entering variable is $x_2$

$A^{-1}_Ba_2=\left(\begin{array}{cc}\frac{1}{4}&\frac{1}{4}\\-
\frac{1}{8}&\frac{3}{8}\end{array}\right)\left(\begin{array}{c}3\\
-2\end{array}\right)=\left(\begin{array}{c}\frac{1}{4}\\-
\frac{9}{8}\end{array}\right)$
\begin{tabular}{cc}
RHS&Ratio\\ 3&12\\ $\frac{3}{2}$&-
\end{tabular}

Leaving variable is $x_1$

\begin{center}
\begin{tabular}{c|cc|c}
\hline $x_2$&1&1&12\\ $x_3$&1&$\frac{3}{2}$&15\\ \hline
\end{tabular}
\end{center}

\item[Iteration 4]

$$\mathbf{c}_B^TA_B^{-1}=\left(\begin{array}{cc}-4&\epsilon\end{array}
\right)\left(\begin{array}{cc}1&1\\1&\frac{3}{2}\end{array}\right)=
\left(\begin{array}{cc}2&5\end{array}\right)$$

\begin{eqnarray*}
(\mathbf{c}_B^TA^{-1}_BA_N-\mathbf{c}_B^T)\mathbf{x}_N&=&\left(\left(
\begin{array}{cc}2&5\end{array}\right)\left(\begin{array}{c}3\\1
\end{array}\right)-9\right)x_1\\
&+&\left(\left(\begin{array}{cc}2&5
\end{array}\right)\left(\begin{array}{c}5\\3\end{array}\right)-8\right)x_4\\
&+&\left(\left(\begin{array}{cc}2&5\end{array}\right)\left(\begin{array}{c}
1\\0\end{array}\right)-0\right)x_5\\
&+&\left(\left(\begin{array}{cc}2&5\end{array} \right)
\left(\begin{array}{c}0\\1\end{array}\right)-0\right)x_6\\
&=&2x_1+17x_4+2x_5+5x_6
\end{eqnarray*}

Thus, an optimal solution is

$$x_1=0,\ x_2=12,\ x_3=15,\ x_4=0\ \ z=42$$

\end{description}

The $s_2$ column of the final tableau is
$\left(\begin{array}{c}1\\\frac{3}{2}\end{array}\right)$. Thus, if
the last right hand side is $6+\delta$, the right hand sides in
the final tableau are
$\left(\begin{array}{c}12+\delta\\15+\frac{3}{2}\delta\\
42+5\delta\end{array}\right)$ giving $\delta\geq-12\
\delta\geq-10$

So the required range is $\delta\geq-10$

Use $A_B^{-1}$ to create the full tableau.

\begin{tabular}{c|ccccccc|c}
Basic&$z$&$x_1$&$x_2$&$x_3$&$x_4$&$x_5$&$x_6$\\ \hline
$x_2$&0&4&1&0&8&1&1&12\\
$x_3$&0&$\frac{9}{2}$&0&1&$\frac{19}{2}$&1&$\frac{3}{2}$&15\\
\hline &1&2&0&0&17&2&5&42\\
&&$+4\delta$&&&$+8\delta$&$+\delta$&$+\delta$&$+12\delta$
\end{tabular}

For the coefficient $(-4+\delta)x_2$, non-negativity in the $z$
row is maintained if $\delta$ satisfies $\delta\geq-\frac{17}{8}\
\delta\geq-2\ \delta\geq-5$.

Thus the required range is $\delta\geq-\frac{1}{2}$.


\end{description}




\end{document}