\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

QUESTION

\begin{description}

\item[(a)]
Consider the linear programming problem

\begin{tabular}{lll}
maximize&$\sum_{j=1}^n c_jx_j$\\ subject to&$x_j \geq
0$&$j=1,\ldots,n$\\&$\sum_{j=1}^n a_{ij}x_j = b_i$&$i=1,\ldots,m,$
\end{tabular}

where the constraint matrix $A = (a_{ij})$ has rank $m$, and $m <
n$.  Explain briefly what is meant by a {\it basic feasible
solution\/} of this problem.  Prove that  an extreme point of the
convex set of feasible solutions is a basic feasible solution.

\item[(b)]
Give a brief explanation of the term {\it cycling}\/ in the
simplex method, and describe two methods by which cycling can be
avoided.  Explain briefly why the simplex method terminates after
a finite number of iterations when cycling does not occur.

\item[(c)]

\begin{description}

\item[(i)]
Solve the following linear programming problem using the dual sim
plex method.

\begin{tabular}{ll}
Minimize&$z = 5x_1 + 2 x_2 + 5x_3$\\subject to&$x_1 \geq 0$, $x_2
\geq 0$, $x_3 \geq 0$\\&$3x_1 +x_2 + 2x_3 \geq 4 $\\&$6x_1 + 3x_2
+ 5x_3  \geq 10$.
\end{tabular}

\item[(ii)]
 Suppose that the additional constraint

$$x_2 + 2x_3 \geq 3 $$

is imposed.  Obtain an optimal solution for this modified problem.

\end{description}

\end{description}


ANSWER



\begin{description}

\item[(a)]
Let $\mathbf{x}_0^T=(x_1^0,\ldots,x_r^0,0,\ldots,0)$ be an extreme
point in which the first $r$ components are positive, where $r>m$.
Let $\mathbf{a}_1,\ldots\mathbf{a}_r$ be the first $r$ columns of
A. Since $r>m,\ \mathbf{a}_1,\ldots\mathbf{a}_r$ are linearly
dependent, i.e. there exist $\lambda_1,\ldots,\lambda_r$, not all
zero such that

$$\lambda\mathbf{a}_1+\ldots+\lambda_r\mathbf{a}_r=\mathbf{0}$$

Let

$$\epsilon=min\left\{\frac{x_j^0}{|\lambda_j|}:\lambda_j\neq0,\
j=1,\ldots,r\right\}$$

and consider $\mathbf{x}_0+\epsilon\mathbf{\lambda},\
\mathbf{x}_2=\mathbf{x}_0-\epsilon\mathbf{\lambda}$, where
$\lambda^T=(\lambda_1,\ldots\lambda_r,0,\ldots,0)$. The definition
of $\epsilon$ ensures that $\mathbf{x}_1\geq\mathbf{0}$ and
$\mathbf{x}_2\geq\mathbf{0}$. Furthermore,

$$A\mathbf{x}_1=a(\mathbf{x|}_0+\epsilon\mathbf{\lambda})=\mathbf{b}\
A\mathbf{x}_2=A(\mathbf{x}_0-\epsilon\mathbf{\lambda})=\mathbf{b}$$

so $\mathbf{x}_1$ and $\mathbf{x}_2$ are feasible solutions.
However, $\mathbf{x}_0\frac{(\mathbf{x}_1+\mathbf{x}_2)}{2}$ which
is impossible if $\mathbf{x}_0$ is an extreme point. Thus $r\leq
m$. Also, $\mathbf{a}_1,\ldots\mathbf{a})_r$ are linearly
independent, or else the above argument shows that $\mathbf{x}_0$
is not an extreme point. If $r=m$, then $\mathbf{x}_0$ is a basic
feasible solution. If $r<m$, it is possible to select $m-r$
columns of $A$ which, together with
$\mathbf{a}_1,\ldots\mathbf{a}_r$ are linearly independent. The
corresponding variables define a basic feasible solution.

\item[(b)]
The simplex method cycles if a sequence of tableaus keeps
reappearing. To avoid cycling use

\begin{itemize}

\item
Perturbation method: perturb right hand sides to $b_i+\epsilon^o,\
i=1,\ldots,m$, where $0\ll\epsilon^m\leq\ldots\ll\epsilon$. The
perturbed problem will be non-degenerate, so cycling will not
occur.

\item
Bland's smallest subscript rule. By choosing the entering and
leaving variable to have the smallest subscript, cycling is
avoided.

\end{itemize}

When there is no cycling, the maximum number of feasible solutions
is $\frac{n!}{(m!(n-m)!)}$, where $m$ is the number of constraints
and $n$ is the number of variables. This determines the maximum
number of iterations.

\item[(c)]

\begin{description}

\item[(i)]
The problem is equivilent to maximizing
$\overline{z}=-5x_1-2x_2-5x_3$. Add slack variables $s_1\geq0,\
s_2\geq0$

\begin{tabular}{c|cccccc|c}
Basic&$\overline{z}$&$x_1$&$x_2$&$x_3$&$s_1$&$s_2$\\ \hline
$s_1$&0&$-3$&$-1$&$-2$&1&0&$-4$\\
$s_2$&0&$-6$&$-3$&$-5$&0&1&$-10$\\ \hline &1&5&2&5&0&0\\
\end{tabular}

\begin{tabular}{c|cccccc|c}
Basic&$\overline{z}$&$x_1$&$x_2$&$x_3$&$s_1$&$s_2$\\ \hline
$s_1$&0&$-1$&0&$-\frac{1}{3}$&1&$-\frac{1}{3}$&$-\frac{2}{3}$\\
$x_2$&0&2&1&$\frac{5}{3}$&0&$-\frac{1}{3}$&$\frac{10}{3}$\\ \hline
&1&1&0&$\frac{4}{3}$&1&$\frac{1}{3}$&$-\frac{22}{3}$
\end{tabular}

\begin{tabular}{c|cccccc|c}
Basic&$\overline{z}$&$x_1$&$x_2$&$x_3$&$s_1$&$s_2$\\ \hline
$x_1$&0&1&0&$\frac{1}{3}$&$-1$&$\frac{1}{3}$&$\frac{2}{3}$\\
$x_2$&0&0&1&1&2&$-1$&2\\ \hline
&1&0&0&$\frac{4}{3}$&1&$\frac{1}{3}$&$-\frac{22}{3}$
\end{tabular}

Thus, the optimal solution is $x_1=\frac{2}{3},\ x_2=2,\ x_3=0,\
z=\frac{22}{3}$.



\item[(ii)]
Include a slack variable $s_3\geq0$ in the new constraint


\begin{tabular}{c|ccccccc|c}
Basic&$\overline{z}$&$x_1$&$x_2$&$x_3$&$s_1$&$s_2$&$s_3$\\ \hline
$x_1$&0&1&0&$\frac{1}{3}$&$-1$&$\frac{1}{3}$&0&$\frac{2}{3}$\\
$x_2$&0&0&1&1&2&$-1$&0&2\\ $s_3$&0&0&0&$-1$&2&$-1$&1&$-1$\\
$s_3$&0&0&0&$-1$&2&$-1$&1&$-1$\\ \hline
&1&0&0&$\frac{4}{3}$&1&$\frac{1}{3}$&0&$-\frac{22}{3}$
\end{tabular}

\begin{tabular}{c|ccccccc|c}
Basic&$\overline{z}$&$x_1$&$x_2$&$x_3$&$s_1$&$s_2$&$s_3$\\ \hline
$x_1$&0&1&0&0&$-\frac{1}{3}$&0&$\frac{1}{3}$&$\frac{1}{3}$\\
$x_2$&0&0&1&2&0&0&$-1$&3\\ $s_2$&0&0&0&1&$-2$&1&$-1$&1\\ \hline
&1&0&0&1&$\frac{5}{3}$&0&$\frac{1}{3}$&$-\frac{23}{3}$
\end{tabular}

The new solution is $x_1=\frac{1}{3},\ x_2=3,\ x_3=0,\
z=\frac{23}{3}$


\end{description}

\end{description}




\end{document}