<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

\begin{description}

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

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


where the constraint matrix $A = (a_{ij})$ has rank $m$, and $m &lt;
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)]
Suppose that there are artificial basic variables at the end
of phase 1 of the two-phase simplex method.  State the
circumstances under which phase 2 should be performed, and explain
what modifications are necessary to deal with these artificial
variables.

\item[(c)]
Solve the following linear programming problem with the dual
simplex method.

\begin{tabular}{ll}
Minimize&amp;$z = 16x_1 + 15 x_2 + 4x_3$\\subject to&amp;$x_1 \geq 0$,
$x_2 \geq 0$, $x_3 \geq 0$\\&amp;$2x_1 + 4x_2 + 5x_3 \geq 25 $\\&amp;$8x_1
+ 3x_2 - 4x_3  \geq 28$.
\end{tabular}


\end{description}


ANSWER


\begin{description}

\item[(a)]
After a renumbering of the variables, a basic feasible solution is
a vector $\mathbf{x}^T=(x_1,\ldots,x_m,0,\ldots,0)$ where
$x_j\geq0$ for $j=1,\ldots,m$ that satisfies the constraints. 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&gt;m$.
Let $\mathbf{a}_1,\ldots\mathbf{a}_r$ be the first $r$ columns of
A. Since $r&gt;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&lt;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)]
If $max\ z'&lt;0$, then the problem is infeasible, and phase 2 is not
executed. If $max\ z'=0$, then phase 2 is performed but with
modifications to ensure that artificial basic variables keep their
current zero values. For example, if in the pivot column some row
has an artificial basic variable which has a negative entry, then
this is chosen as the pivot element. Othervise the normal ratios
determine the pivot row.

\item[(c)]
An equivilent problem results if we maximize

$$z'=-16x_1-15x_2-4x_3$$

Introduce slack variables $s_1\geq0,\ s_2\geq0$

\begin{tabular}{c|cccccc|c}
Basic&amp;$z'$&amp;$x_1$&amp;$x_2$&amp;$x_3$&amp;$s_1$&amp;$s_2$\\ \hline
$s_1$&amp;0&amp;$-2$&amp;$-4$&amp;$-5$&amp;1&amp;0&amp;$-25$\\ $s_2$&amp;0&amp;$-8$&amp;$-3$&amp;4&amp;0&amp;1&amp;$-28$\\
\hline &amp;1&amp;16&amp;15&amp;4&amp;0&amp;0&amp;0\\ Ratio&amp;&amp;2&amp;5
\end{tabular}

\begin{tabular}{c|cccccc|c}
Basic&amp;$z'$&amp;$x_1$&amp;$x_2$&amp;$x_3$&amp;$s_1$&amp;$s_2$\\ \hline
$s_1$&amp;0&amp;0&amp;$-\frac{13}{4}$&amp;$-6$&amp;1&amp;$-\frac{1}{4}$&amp;$-18$\\
$x_1$&amp;0&amp;1&amp;$\frac{3}{8}$&amp;$-\frac{1}{2}$&amp;0&amp;$-\frac{1}{8}$&amp;$\frac{7}{2}$\\
\hline &amp;1&amp;0&amp;9&amp;12&amp;0&amp;2&amp;$-56$\\
Ratio&amp;&amp;&amp;$\frac{36}{13}$&amp;$\frac{4}{3}$&amp;&amp;8
\end{tabular}

\begin{tabular}{c|cccccc|c}
Basic&amp;$z'$&amp;$x_1$&amp;$x_2$&amp;$x_3$&amp;$s_1$&amp;$s_2$\\ \hline
$x_3$&amp;0&amp;0&amp;$\frac{13}{24}$&amp;1&amp;$-\frac{1}{6}$&amp;$\frac{1}{24}$&amp;3\\
$x_1$&amp;0&amp;1&amp;$\frac{31}{48}$&amp;0&amp;$-\frac{1}{12}$&amp;$-\frac{5}{48}$&amp;5\\
\hline &amp;1&amp;0&amp;$\frac{5}{2}$&amp;0&amp;2&amp;$\frac{3}{2}$&amp;$-92$
\end{tabular}

Optimal solution $x_1=5,\ x_2=0,\ x_3=3,\ z=92$

\end{description}




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