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?

enter image description here


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.


$\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.

  • $\begingroup$ What book is this? $\endgroup$ – Alec Teal May 14 '14 at 20:13
  • 1
    $\begingroup$ Introduction to Linear Optimization by Bertsimas and Tsitsiklis $\endgroup$ – Tori Jan 22 '19 at 2:51

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.