linear programmingtwo-phase-simplex
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).
The Bertsimas states the reduced cost such that $\bar c_j=c_j-c_B' B^{-1} A_j$ on the page 84.
You need to calculate the inverse matrix and then do the matrix multiplication but 3 equations and 5 variables -- have to choose some $B$. $B=I_3$ because we have $y_1,y_2,y_3$ in the base and the reduced costs are zero in the beginning. Then we get very simple calculations below.
Trials
$\bar c_1=c_1-(1,1,1)I_3(1,1,-1)^T=c_1-1=0-1=-1$
$\bar c_2=c_2-(1,1,1)I_3(3,2,-4)^T=c_2-(3+2-4)=-1$
$\bar c_3=c_3-(1,1,1)I_3(0,0,3)^T=c_3-3=-3$
$\bar c_4=c_4-(1,1,1)I_3(4,-3,0)^T=c_4-(4-3)=-1$
$\bar c_5=c_5-(1,1,1)I_3(1,1,3)^T=c_5-(2)=-2$
$\bar c_6=c_6-(1,1,1)I_3(1,0,0)^T=1-1=0$
$\bar c_7=c_7-(1,1,1)I_3(0,1,0)^T=1-1=0$
$\bar c_8=c_8-(1,1,1)I_3(0,0,1)^T=1-1=0$
so $\bar c =(-1,-1,-3,-1,-2,0,0,0)$.
This worked because we are trying to minimize $0+0+0+0+0+y_1+y_2+y_3$ so similarly to the traditional simplex we use the coeffients for $c_i$ here.
I can almost get the same result as on your slides but $\bar{c}'=[5,82/7,0,0,0]$, perhaps there is a small typo in the slide?
The basic idea is to use the formula for the reduced cost:
$$\bar c_j = c_j -\bf{c_B}B^{-1}A_j$$
where $\bar{c}_j$ means the reduced cost (not vector!) and $c_j$ denotes the terms in the minimization like $$\bf{c}'\bf{x}=c_1x_1+c_2x_2+c_3x_3+c_4x_4+c_5x_5=2x_1+3x_2+3x_3+x_4-2x_5$$
where $c_1=2$, $c_2=3$ and so on.
Calculations
Best Answer
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.