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?

enter image description 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).


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.

  • $\begingroup$ ...so it is not "reduced cost" there? It is just a substitution? Is this formula $\bf c - \bf A ^t \bf y$ misused? Did I make a placebo assumption that it was used somehow there? +1 and welcome to Math.SE! $\endgroup$ – hhh Aug 28 '12 at 2:05


"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.


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?


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.