Take the 2-minute tour ×
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.

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

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

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

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|improve this answer
add comment

Your Answer

 
discard

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.