# Show that if Phase I of the two-phase method ends with an optimal cost of zero then the reduced cost vector will always take the form $(0, 1)$

Consider a linear programming problem of the form:

minimize $$c^Tx$$

subject to:

$$Ax=b$$, $$x\geq0$$

where $$A$$ is an $$m\times n$$ matrix with linearly independent rows. Show that if Phase I of the two-phase method ends with an optimal cost of zero at a non-degenerate basic feasible solution then the reduced cost vector will always take the form $$(0, 1)$$ where there are $$n$$ zeroes and $$m$$ ones. Note that $$1$$ is a vector of ones.

My attempt: Want to Show that the ending basic feasible solution$$\begin{pmatrix} x\\ y\\ \end{pmatrix}$$ for Phase I has all of it's basic variables among the $$x_i$$ variable so that the basic components of the cost are all zero: $$c_B=0$$

Let $$(x,y)$$ be the basic feasible solution at the end of phase I. Suppose by contradiction that one of the basic variables is some $$y_j$$ (hence $$y_j\gt0$$). How can I show that this implies that the optimal cost of auxiliary problem is $$> 0$$ which contradicts the given that optimal cost of auxiliary problem is $$0$$? And how can I show that this implies that the cost vector $$c_B$$ is $$0$$? Finally how can I apply reduced cost formula to get conclusion? Need some hints.

• In addition, reduced cost formula is $\bar c_j =c_j - c_B^T B^{-1} A_j$ – WaterBro Nov 16 '19 at 23:34

When you apply phase I, you are looking for a feasible solution for $$Ax=b$$, so you introduce artificial variables $$a_1,...,a_m$$, one for each constraint, and consider the following minimization problem : $$\min\; a_1+...+a_m$$ subject to $$Ax+ I_m \pmatrix{a_1 \\...\\a_m} = b$$ where $$I_m$$ is the identity matrix of rank $$m$$.
The idea is that if the optimal solution of this problem is $$0$$, then you have found values for $$x$$ that satisfy $$Ax=b$$, and you are done (you have a starting point for phase II).
Now, if you have such values for $$x$$, and that this solution is non degenerate, then necessarily, $$x>0$$. In other words, the reduced cost for each $$x_1,...,x_n$$ is null. (Technically can you see why ?)
And if this solution is optimal and non degenerate, then all other reduced costs must be strictly positive. Given that you are minimizing $$a_1+...+a_m$$, (i.e., $$c_i=1$$ for all $$i=1,...,m$$) can you show that $$\hat{c}_i=1$$ for each artificial variable ?