Reduced cost zero for the two-phase Simplex?

Question

I cannot understand the line -12, -4, -5, 1, 1, -1, 0, 0, 0. Now the formula $\bf c - \bf A ^t \bf y$ when $c=0$ will result into the line. It is just many times a dot product: for example, 0-(1*5+1*1+1*6)=-12. But why is $c=0$ here?

This problem is a part of two-phase Simplex but probably the same with most Simplexes.

P.s. Page 116 in the Bertsimas -book (1997).

Answer 1

Wrong!

"Now the formula $c−A^ty$ when $c=0$ will result into the line." You would get something like $(1\times 8)-(3\times 8)$ so the matrix dimensions are totally wrong.

Correct

The reduced cost formula is $\bar c_j =c_j - c_B^T B^{-1} A_j$, more about the reduced calculations here. By this you can calculate the top line.

The example

$$\min y_1+y_2+y_3$$ so $c_1=c_2=c_3=c_4=c_5=0$, $c_6=c_7=c_8=1$, $x_B=(x_6,x_7,x_8)$ and $c_B=(1,1,1)$. And $B=I_3$, the 3-identity-matrix. Then for example $$\bar c_1=c_1-c_B^T A_1=-(1,1,1)^T (2,1,2)=-(2+1+2)=-5.$$

Your homework is to read the page 84 in Bertsimas again.

Perhaps related

1. Optimality conditions and Directions in Simplex method

2. Reduced cost vector in the phase I of the Two-phase simplex?

3. Optimum exists but not extreme point in Standard Form LP problem?

Answer 2

In the first phase of the simplex method it is convenient to choose the objective function $z=y_1 + \cdots + y_n$ where the $y_i$ variables are the auxiliary variables and $z$ is the objective value of the current tableau(not every textbook writes the $z$ out explicitly). Recall that the auxiliary are introduced to make a starting basis obvious: simply take the set of auxiliary variables as the starting basis. By minimizing this choice of objective if there is a basic feasible solution to the original problem, then this linear program will have an optimal solution with optimal value 0, that is, we can find a solution where all the auxiliary variables are 0. Said another way, we have found values for the $x$ variables such that all the equations are satisfied (without using the $y$'s to pick up any infeasibility).

Now let us look at the mechanics of choosing the initial starting basis to be the set of auxiliary variables $y_1$, $y_2$ and $y_3$. Since these variables are basic, the $x$ variables are non-basic which means $x_1=\cdots=x_5=0$. Thus, $y_1=5$, $y_2=1$ and $y_3=6$.

We can write the objective row as $z=y_1 + y_2 + y_3$, where $z$ is the objective value of the current simplex tableau. The objective row of a simplex tableau is written as $z-y_1-y_2-y_3$ (some books have an explicit column for $z$ which makes this clear). The objective row of a simplex tableau is expressed only in terms of the non-basic variables. Since the objective row is $z-y_1-y_2-y_3$ we simply use the fact that with the current tableau $$ y_1 = 5 - 2x_1 - x_2 + x_3 $$ $$ y_2 = 1 - - x_2 +x_4$$ $$ y_3 = 6 - 2x_1 - 3x_2 - x_5$$ Substituting this into $z-y_1-y_2-y_3$ we obtain $$ -12 -4x_1 - 5x_2 + x_3 + x_4 - x_5$$ for the objective row.

The big-M's are used to accelerate driving the auxiliary variables out of the basis. Hopefully this helps.