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.
Best Answer
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 ?