# Example about the Reduced cost in the Big-M method?

2,423

The Big-M method can be seen as a special case of the Two-Phase Simplex, now instead of $$y_1,y_2,...,y_n$$ dummy vars to reformate the base, we use a large value $$M$$. It is calculated pretty similarly to the Two-Phase Simplex as you can see here for the problem. Again the fundamental idea is this reduced cost formula $$\bar{\bf{c'}_j}=c_j'-\bf{c'}_B B^{-1}A_j$$. The Bertsimas has something on the page 117 but not as explicitly calculated example as here. I hope it helps!

Related information

Example

where the $$15M$$ should be $$-15M$$, a typo, ie $$\bar{c}_0:=-\bf{c}_B'\bf{B}^{-1}b=-15M$$. The rest is pretty much the traditional Simplex. The key is the differences with M -- you consider this very large $$M$$ as a number, not as a limit for the positive infinite.

Hard part

I haven't yet solved this but I got infeasible base with $$[x_2,x_1,x_4]$$ and not optimum situation here. Then I zwitched $$x_4$$ and $$x_3$$ but the new base $$[x_2,x_1,x_2]$$ is infeasible and not optimum as well. I may have done some mistake somewhere -- calculating the big M terms errorsome unless some thinking mistake in my simplex.

Share:
2,423

Author by

### hhh

Updated on August 01, 2022

$$\min x_1-2x_2+x_4$$ $$\text{ s.t. } -x_1+x_2=1$$ $$x_2-2x_3+3x_4=10$$ $$x_1+x_3+4x_4=4$$ $$x_1,x_2,x_3,x_4\geq 0$$