2
$\begingroup$

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.

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

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 ?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.