\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$. 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&$z = 16x_1 + 15 x_2 + 4x_3$\\subject to&$x_1 \geq 0$, $x_2 \geq 0$, $x_3 \geq 0$\\&$2x_1 + 4x_2 + 5x_3 \geq 25 $\\&$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>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