or 'how not to be a Simplex widow'
It is true that the Big M method is very scary (hence the need for capitals there). It has been known to reduce grown men, even mathematical giants such as the famed Mr Baker, to tears, and their wives to sighing despair. In a spirit of community and utilitarianism, then, I have taken it upon myself to rid the world of this dark and looming spectre, by explaining it in the simplest possible terms.
That said, even the simplest possible terms may in some cases prove to be less simple than the reader may desire (or indeed require); should this be the case here, they are directed to an interesting and promising new paper on the fundamental mathematical axioms by Darren Powell - this promises to radically simplify all branches of mathematics (which hopefully includes Simplex and Big M, though some would dispute it), and could render even this infamous method simple or, better yet, obsolete.
The Big M method is an alternative form of two-stage simplex which requires only one objective function. (If the previous sentence made no sense to the reader, they are advised to stop reading now, as things will only get worse.) Instead of trying to minimise the sum of all artificial variables to 0 (as in the other method, which does not appear to have a name, and certainly does not merit one with capitals in), the Big M method uses the fact that any variable column which contains numbers other than 1 and 0 must necessarily be non-basic (and thus equal 0) at that point in the tableau (see figure 1).
| I | cs | ct | ms | mt | fs | ft | s1 | s2 | s3 | s4 | RHS |
| 1 | -45 | 0 | 0 | -30 | -10 | 0 | -75 | -320 | -60 | -180 | 15773.75 |
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | -1 | 0 | 14 |
| 0 | 1 | 1 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 0 | 5.25 |
| 0 | -1 | 0 | 0 | 1 | -1 | 0 | 0 | -1 | 0 | 0 | 3.5 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 14 |
| 0 | 1 | 0 | 0 | -1 | 1 | 0 | 0 | 1 | 0 | 0 | 2.5 |
| 0 | 7 | 0 | 0 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 3.5 |
| 0 | 0 | 0 | 1 | 1 | 5 | 0 | 0 | -1 | 0 | 0 | 35.5 |
| 0 | 9 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 4.75 |
Fig. 1: at this point in the tableau ct, ms and ft are basic,
while cs, mt and fs are clearly not
By writing the constraints in terms of artificial variables (as in all forms of two-stage simplex), then adding them into the objective function, multiplied by an arbitrarily large number M (which is arbitrary as the artificial variables will eventually reduce to 0 anyway), the tableau can then be manipulated to make all artificial variables contain an M in their column, which will then make it non-basic. Once this is done the columns can be removed and the second stage can proceed.
If that description sounded wordy, it is because Big M is difficult to describe in prose (as any self-respecting feared mathematical method should be). It is far simpler to go through the method step by step.
Here the method will be gone through step by step, taking as an example the infamous 'Simplex Widow' problem which led to the writing of this paper, and to the tragic loss of at least four D2 lessons (two further lessons remain in a critical condition; our thoughts are with them also).
That is, take the original problem:
subject to x + y >= 20
2x + 5y >= 70
7x + 3y >= 84
and turn it into:
subject to x + y - s1 + a1 = 20
2x + 5y - s2 + a2 = 70
7x + 3y - s3 + a3 = 84
(Note that this is the same process that would be used in any form of two-stage simplex.)
As the artificial variables will end up being 0 this will have no effect on the value. The artificial variables are added as a term
at the end of the function (where M is the aforementioned arbitrarily large number). The sign of this term depends on the aim of the LP problem: if it is a maximisation LP the sign is -, if it is a minimisation LP the sign is + (this has in the past proved a great stumbling-block to even our country's most eminent mathematicians, naming no names in particular). This gives us
subject to x + y - s1 + a1 = 20
2x + 5y - s2 + a2 = 70
7x + 3y - s3 + a3 = 84
It is forbidden by the Elder Gods to have artificial variables in the objective function (for the exact Commandment, see Codex Simplex chapter M page XXIIX), so an equation must be found for the sum of all artificial variables and substituted in. This is generally found by adding all the å constraints together and rearranging. Here this gives
which substitutes into the objective function, giving
and multiplies out (keeping each variable separate) to
Rearranging into a form suitable for the tableau gives:
This results in the following initial tableau:
| I | x | y | s1 | s2 | s3 | a1 | a2 | a3 | RHS |
| 1 | -2 + 10M | -1 + 9M | -M | -M | -M | 0 | 0 | 0 | 174M |
| 0 | 1 | 1 | -1 | 0 | 0 | 1 | 0 | 0 | 20 |
| 0 | 2 | 5 | 0 | -1 | 0 | 0 | 1 | 0 | 70 |
| 0 | 7 | 3 | 0 | 0 | -1 | 0 | 0 | 1 | 84 |
You will notice that the proliferation of Ms everywhere makes the tableau look difficult. And it is. But it's not impossible, so long as you keep the Ms separate from normal numbers (as if they were variables). As M is large and positive, both x and y in the above tableau are positive and can therefore be improved. The tableau progresses like so:
| I | x | y | s1 | s2 | s3 | a1 | a2 | a3 | RHS |
| 1 | 0 | -1/7 + 33/7M | -M | -M | -2/7 + 3/7M | 0 | 0 | 2/7 - 10/7M | 24 + 54M |
| 0 | 0 | 4/7 | -1 | 0 | 1/7 | 1 | 0 | -1/7 | 8 |
| 0 | 0 | 41/7 | 0 | -1 | 2/7 | 0 | 1 | -2/7 | 46 |
| 0 | 1 | 3/7 | 0 | 0 | -1/7 | 0 | 0 | 1/7 | 12 |
| I | x | y | s1 | s2 | s3 | a1 | a2 | a3 | RHS |
| 1 | 0 | 0 | -M | -1/29 + 4/29M | -8/29 + 3/29M | 0 | 1/29 - 33/29M | 8/29 - 32/29M | 251/29 + 119/29M |
| 0 | 0 | 0 | -1 | 4/29 | 3/29 | 1 | -4/29 | -3/29 | 119/29 |
| 0 | 0 | 1 | 0 | -7/29 | 2/29 | 0 | 7/29 | -2/29 | 113/29 |
| 0 | 1 | 0 | 0 | 3/29 | -5/29 | 0 | -3/29 | 5/29 | 77/29 |
| I | x | y | s1 | s2 | s3 | a1 | a2 | a3 | RHS |
| 1 | 0 | 0 | -1/4 | 0 | -1/4 | 1/4 - M | -M | 1/4 - M | 26 |
| 0 | 0 | 0 | -71/4 | 1 | 3/4 | 71/4 | -1 | -3/4 | 12 |
| 0 | 0 | 1 | -13/4 | 0 | 1/4 | 13/4 | 0 | -1/4 | 14 |
| 0 | 1 | 0 | 3/4 | 0 | -1/4 | -3/4 | 0 | 1/4 | 6 |
The tableau is now in the happy position of having Ms in every artificial column and nowhere else. This means that the artificial columns will now remain non-basic for the rest of the tableau and can thus be discarded, and the tableau can be completed as for one-stage simplex. In this case, no more improvements are possible, and so the final solution is
x = 6
y = 14
Some would say that the Big M method is utterly needless and fiddly and begs to be destroyed from human knowledge. Others would counter that it removes the need for two objective functions in two-stage simplex and that its premises are actually rather elegant. I am inclined to agree with the former party; however, since it is a proven fact that most mathematicians are insane intelligence-masochists, forever seeking techniques that will cause their minds yet more pain, it seems unlikely that this method will disappear in the foreseeable future. I hope this explanation of its workings has given the reader the reserves of courage and understanding needed for them to weather the difficult period until the happy day when Big M is once again no more than a letter of the alphabet.