linear programmingtwo-phase-simplex
I am trying to understand the part in red. The left is the standard form problem and the right is the auxiliary problem. Now I can understand until the red i.e. $\bar c =(-1,-1,-3,-1,-2,0,0,0)$. The $c_B'x_B=5$ is $\sum_i y_i=2+2+1=5$ with the base $x_B=(0,0,0,0,0,1,1,1)$ where $y_i$ are the auxliary variables introduced in two-phase simplex.
How is the red i.e. the reduced cost calculated?
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.
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
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
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.