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

Question

I want to gather examples about the reduced cost in different cases, now for the Big-M method. I hope this makes the methods more accesible. So

How does the Big-M method work with the below?

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

Answer 1

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

• Meaning of the bar over $\bf{c}'$ in $\bf{\bar{c}}'=\bf c' -\bf c'_B \bf B^{-1} \bf A\geq \bf 0$?

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.