Two-stage Simplex and big-M methods
Studying this course? Keep your progress in one place.
Key facts
- A or constraint needs an artificial variable to give a starting solution, and a valid answer has .
- In big-M, maximise and eliminate from the row first.
- In two-stage, stage 1 maximises ; if the minimum of is 0 go to stage 2, otherwise there is no feasible solution.
- If is still positive at the end, the problem has no feasible solution.
- To minimise, maximise .
Why artificial variables
A or constraint has no ready starting solution, so an artificial variable is added and must be forced out.
A slack variable gives a ready-made start for . A or constraint does not: for the equation at gives , which is not allowed.
So add an artificial variable : , which starts with .
But has no meaning in the real problem. A genuine solution has . The big-M and two-stage methods force it out.
- slack
- surplus and artificial
- artificial
Why is a surplus variable alone not enough for ?
The big-M method
Penalise the artificial variable in the objective with a very large , and eliminate from the row.
Use one objective that penalises artificial variables. For a maximising problem subtract , where is a very large positive number. Since is basic, eliminate from the row: subtract the row.
For and , the row (columns ) becomes .
Choose the pivot column by comparing the coefficients of first: here . Ratios and , so the row is the pivot row.
- 1
Add artificial variable t
to the ≥ or = constraint
- 2
Penalise it
subtract Mt from the objective, M very large
- 3
Eliminate t from the P row
because t is basic
- 4
Pivot as usual
maximising with the new P row
In the big-M method, which column is chosen from and ?
Completing big-M
After leaves, one more iteration gives a row with no negatives. still positive at the end means no feasible solution.
After the first pivot ( row, column) the row is and the row is . Now has left the basis, so you can ignore its column.
The most negative entry is (the column). Only the row has a positive entry (, ratio 18), so it is the pivot row.
The result is a row , with no negatives. So , , (check: ).
- 1
First pivot
t leaves the basis
- 2
Ignore t
it is no longer basic
- 3
One more iteration
until the P row has no negatives
- 4
Check t
if t is still positive, there is no feasible solution
| Row y | Row s₁ | Row P | |
|---|---|---|---|
| x | 1/2 | 1/2 | -1 |
| y | 1 | 0 | 0 |
| s₁ | 0 | 1 | 0 |
| s₂ | -1/2 | 1/2 | -2 |
| t | 1/2 | -1/2 | 2+M |
| Value | 3 | 9 | 12 |
Row y
- x:
- 1/2
- y:
- 1
- s₁:
- 0
- s₂:
- -1/2
- t:
- 1/2
- Value:
- 3
Row s₁
- x:
- 1/2
- y:
- 0
- s₁:
- 1
- s₂:
- 1/2
- t:
- -1/2
- Value:
- 9
Row P
- x:
- -1
- y:
- 0
- s₁:
- 0
- s₂:
- -2
- t:
- 2+M
- Value:
- 12
The final tableau has in the basis. What does this mean?
The two-stage method
Stage 1 minimises the sum of the artificial variables. If it reaches 0, stage 2 optimises the original objective.
Stage 1 ignores profit and finds a feasible start. Define (the sum of the artificial variables) and minimise it, that is maximise .
Eliminate to get the row. For and : . Carry the row through stage 1 with the same row operations.
- If the minimum of is 0, go to stage 2.
- If it is positive, there is no feasible solution.
In stage 2, continue Simplex on the original row until no negatives remain.
- 1
Stage 1
minimise I, the sum of the artificial variables
- 2
Test I
I = 0 means a feasible start exists; I > 0 means no feasible solution
- 3
Stage 2
delete the Q row and artificial columns, then optimise the original P row
Stage 1 ends with minimum . What do you conclude?
A two-stage example
Stage 1 finds with ; stage 2 then moves to with .
Maximise subject to and .
Stage 1. Pivot on the 3 in the row ( column; ratios 10 and 2), giving and . The row becomes .
Stage 2. enters (ratios 6 and 12, so the row leaves), then enters (the row leaves). Final row : , , .
Minimising. Maximise . For with , , the result is , , .
| Row x | Row s₁ | Row P | |
|---|---|---|---|
| x | 1 | 0 | 0 |
| y | 1/3 | 2/3 | -13/3 |
| s₁ | 0 | 1 | 0 |
| s₂ | -1/3 | 1/3 | -2/3 |
| Value | 2 | 8 | 4 |
Row x
- x:
- 1
- y:
- 1/3
- s₁:
- 0
- s₂:
- -1/3
- Value:
- 2
Row s₁
- x:
- 0
- y:
- 2/3
- s₁:
- 1
- s₂:
- 1/3
- Value:
- 8
Row P
- x:
- 0
- y:
- -13/3
- s₁:
- 0
- s₂:
- -2/3
- Value:
- 4
The final answer is , . Is the constraint satisfied?
Try an exam question
A linear program has the constraint . (a) Write it as an equation using a surplus variable and an artificial variable . (b) Explain why is needed. (c) State how the objective is changed in the big-M method.
[4 marks]
- [1] with .
- [1]At the surplus alone gives , so there is no starting solution.
- [1]The artificial variable gives the starting basic solution .
- [1]Big-M: with very large, so is driven out of the solution.
That's the notes covered.
Carry on to the next subtopic.
Try a question
Which equation is the constraint after and are introduced?
1 mark, marked against the mark scheme
Which equation is the constraint after and are introduced?
1 mark, marked against the mark scheme