# Reduced cost vector in the phase I of the Two-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?

-

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.

-
What book is this? – Alec Teal May 14 '14 at 20:13