\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

QUESTION

\begin{description}

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

\begin{tabular}{lll}
maximize&$\sum\limits^n_{j=1} c_jx_j$\\subject to&$x_j \geq
0$&$j=1,\ldots,n$\\&$\sum\limits^n_{j=1} 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$. Prove that a basic feasible solution is an extreme point of
the convex set of feasible solutions.


\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.

\item[(c)]
Explain what is meant by {\it soft} constraints, and indicate
how they are incorporated into a linear programming problem.



\item[(d)]
Find and evaluate all basic feasible solutions of the linear
programming problem

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


Verify that if the vector $(x_1,x_2,x_3,x_4)$ is a feasible
solution, then the vector $(x_1+1,x_2,x_3+2,x_4+1)$ is also a
feasible solution.  What can you conclude about the problem?

\end{description}

ANSWER


\begin{description}

\item[(a)]
Assume that the variables of the LP problem are $\mathbf{x}$ and
the constraints are $\mathbf{x}\geq\mathbf{0}$ and
$A\mathbf{x}=\mathbf{b}$. Let
$\mathbf{x}=\left(\begin{array}{c}\mathbf{x}^B\\\mathbf{x}^N\end{array}\right)\
A=(A^B\ A^N)$, so that constraints are

$$A^B\mathbf{x}^B+A^N\mathbf{x}^N=\mathbf{b}$$

Let $\mathbf{x}^B=A^{-1}_B(\mathbf{b}-A^N\mathbf{x}^N)$ define a
basic feasible solution $\mathbf{x}^B=A^{-1}_B\mathbf{b}\
\mathbf{x}_N=\mathbf{0}$. Suppose

\begin{equation}
\mathbf{x}=\lambda\mathbf{x}_1+(1-\lambda)\mathbf{x}_2
\end{equation}

for feasible solutions $\mathbf{x}_1,\mathbf{x}_2$, where
$\mathbf{x}_1\neq  \mathbf{x}_2$ and $0<\lambda<1$.

Let $\mathbf{x}_1=\left(\begin{array}{c}\mathbf{x}_1^B\\
\mathbf{x}_1^N\end{array}\right)$ and
$\mathbf{x}_2=\left(\begin{array}{c}\mathbf{x}_2^B\\
\mathbf{x}_2^N\end{array}\right)$. From (1),
$\mathbf{x}_1^N=\mathbf{x}_2^N=\mathbf{0}$, since otherwise
$\mathbf{x}^N\neq\mathbf{0}$. For feasibility,

\begin{tabular}{lll}
$A^B\mathbf{x}_1^B=\mathbf{b}$&giving&$\mathbf{x}_1^B=(A^B)^{-1}\mathbf{b}$\\
$A^B\mathbf{x}_2^B=\mathbf{b}$&giving&$\mathbf{x}_2^B=(A^B)^{-1}\mathbf{b}$\\
\end{tabular}

Thus $\mathbf{x}_1^B=\mathbf{x}_2^B$ to give
$\mathbf{x}_1=\mathbf{x}_2$, which contradicts the initial
assumption $\mathbf{x}_1\neq\mathbf{x}_2$.

\item[(b)]
Cycling occurs when a previously generated tableau reappears at
some later iteration. To avoid cycling

\begin{itemize}

\item
perturbation: add the vector
$(\epsilon,\epsilon^2,\ldots,\epsilon^m)$ for small positive
$\epsilon$ to the right hand sides to avoid degeneracy.

\item
Bland's smallest subscript rule: the pivot column is the one with
a nagative $x$ coefficient which has the smallest subscript on the
variable; for equal smallest ratios, choose a row containing a
basic variable with the smallest subscript.

\end{itemize}

\item[(c)]
Soft constraints are ones which should preferably be satisfied,
but can be varied at a cost. A soft constraint

$$a_{i1}x_1+\ldots a_{in}x_n=b_i$$

is replaced by

$$a_{i1}x_1+\ldots+a_{in}x_n+u_i-v_i=b_i\ u_i\geq0,\ v_i\geq0$$

and a contribution $\alpha_ou_i+\beta_iv_i$ for suitable chosen
$\alpha_i,\beta_i$ is added to the cost in the objective function.

\item[(d)]

\begin{center}
\begin{tabular}{cccc}
\hline Basic&Value&Feasible&$z$\\ \hline $x_1,x_2$&$6,-2$&No\\
$x_1,x_3$&$3,\frac{1}{2}$&Yes&17\\
$x_1,x_4$&$\frac{11}{4},-\frac{1}{4}$&No\\ $x_12,x_3$&2,1&Yes&18\\
$x_2,x_4$&$\frac{22}{13},-\frac{6}{13}$&No\\
$x_3,x_4$&$-\frac{11}{2},-3$&No\\ \hline
\end{tabular}
\end{center}

\begin{eqnarray*}
(x_1+1)&+&x_2+2(x_3+2)-5(x_4+1)\\ &=&x_1+x_2+2x_3-5x_4=4\\
3(x_1+1)&+&5x_2-2(x_3+2)+(x_4+1)\\ &=&3x_1+5x_2-2x_3+x_4=8
\end{eqnarray*}

The objective function value of the solution is

$$s(x_1+x)+7x_2+4(x_3+2)+9(x_4+1)=5x_1+7x_2+4x_3+9x_4+22$$

Since any feasible solution can be increased by 22 without
affecting feasibility, the problem is unbounded.

\end{description}




\end{document}