Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 0 down vote accepted

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.

share|cite|improve this answer
What book is this? – Alec Teal May 14 '14 at 20:13

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.