Two-stage Simplex and big-M methods

Two-stage Simplex and big-M methods

Spec 5.4 · Edexcel A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • A ≥\ge or == constraint needs an artificial variable tt to give a starting solution, and a valid answer has t=0t=0.
  • In big-M, maximise P=3x+4y−MtP=3x+4y-Mt and eliminate tt from the PP row first.
  • In two-stage, stage 1 maximises Q=−tQ=-t; if the minimum of II is 0 go to stage 2, otherwise there is no feasible solution.
  • If tt is still positive at the end, the problem has no feasible solution.
  • To minimise, maximise P=−CP=-C.

Why artificial variables

A ≥\ge 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 ≤\le. A ≥\ge or == constraint does not: for x+2y≥6x+2y\ge6 the equation x+2y−s2=6x+2y-s_2=6 at x=y=0x=y=0 gives s2=−6s_2=-6, which is not allowed.

So add an artificial variable tt: x+2y−s2+t=6x+2y-s_2+t=6, which starts with t=6t=6.

But tt has no meaning in the real problem. A genuine solution has t=0t=0. The big-M and two-stage methods force it out.

1234567812345xy(6, 0)(0, 3)x + 2y = 6
x + 2y ≥ 6 is satisfied on and above this line. At x = y = 0 the slack s₂ would be −6, so the origin is not feasible.

≤\le

  • slack

≥\ge

  • surplus and artificial

==

  • artificial

Why is a surplus variable alone not enough for x+2y≥6x+2y\ge6?

The big-M method

Penalise the artificial variable in the objective with a very large MM, and eliminate tt from the PP row.

Use one objective that penalises artificial variables. For a maximising problem subtract MtMt, where MM is a very large positive number. Since tt is basic, eliminate tt from the PP row: subtract M×M\times the tt row.

For x+y+s1=12x+y+s_1=12 and x+2y−s2+t=6x+2y-s_2+t=6, the PP row (columns x,y,s1,s2,tx,y,s_1,s_2,t) becomes −3−M, −4−2M, 0, M, 0∣−6M-3-M,\ -4-2M,\ 0,\ M,\ 0\mid-6M.

Choose the pivot column by comparing the coefficients of MM first: here yy. Ratios 121=12\frac{12}{1}=12 and 62=3\frac62=3, so the tt row is the pivot row.

  1. 1

    Add artificial variable t

    to the ≥ or = constraint

  2. 2

    Penalise it

    subtract Mt from the objective, M very large

  3. 3

    Eliminate t from the P row

    because t is basic

  4. 4

    Pivot as usual

    maximising with the new P row

Setting up the big-M objective.
  • P=3x+4y−MtP=3x+4y-MtP−3x−4y+Mt=0P-3x-4y+Mt=0

In the big-M method, which column is chosen from −3−M-3-M and −4−2M-4-2M?

Completing big-M

After tt leaves, one more iteration gives a PP row with no negatives. tt still positive at the end means no feasible solution.

After the first pivot (tt row, yy column) the yy row is 12,1,0,−12,12∣3\frac12,1,0,-\frac12,\frac12\mid3 and the PP row is −1,0,0,−2,2+M∣12-1,0,0,-2,2+M\mid12. Now tt has left the basis, so you can ignore its column.

The most negative entry is −2-2 (the s2s_2 column). Only the s1s_1 row has a positive entry (12\frac12, ratio 18), so it is the pivot row.

The result is a PP row 1,0,4,0,M∣481,0,4,0,M\mid48, with no negatives. So x=0x=0, y=12y=12, P=48P=48 (check: x+2y=24≥6x+2y=24\ge6).

  1. 1

    First pivot

    t leaves the basis

  2. 2

    Ignore t

    it is no longer basic

  3. 3

    One more iteration

    until the P row has no negatives

  4. 4

    Check t

    if t is still positive, there is no feasible solution

Finishing the big-M method.

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 t=2t=2 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 I=tI=t (the sum of the artificial variables) and minimise it, that is maximise Q=−tQ=-t.

Eliminate tt to get the QQ row. For x+y+s1=10x+y+s_1=10 and 3x+y−s2+t=63x+y-s_2+t=6: Q−3x−y+s2=−6Q-3x-y+s_2=-6. Carry the PP row through stage 1 with the same row operations.

  • If the minimum of II is 0, go to stage 2.
  • If it is positive, there is no feasible solution.

In stage 2, continue Simplex on the original PP row until no negatives remain.

  1. 1

    Stage 1

    minimise I, the sum of the artificial variables

  2. 2

    Test I

    I = 0 means a feasible start exists; I > 0 means no feasible solution

  3. 3

    Stage 2

    delete the Q row and artificial columns, then optimise the original P row

The two-stage method

Stage 1 ends with minimum I=3I=3. What do you conclude?

A two-stage example

Stage 1 finds x=2x=2 with Q=0Q=0; stage 2 then moves to y=10y=10 with P=50P=50.

Maximise P=2x+5yP=2x+5y subject to x+y≤10x+y\le10 and 3x+y≥63x+y\ge6.

Stage 1. Pivot on the 3 in the tt row (xx column; ratios 10 and 2), giving x=2x=2 and Q=0Q=0. The PP row becomes 0,−133,0,−23∣40,-\frac{13}{3},0,-\frac23\mid4.

Stage 2. yy enters (ratios 6 and 12, so the xx row leaves), then s2s_2 enters (the s1s_1 row leaves). Final PP row 3,0,5,0∣503,0,5,0\mid50: x=0x=0, y=10y=10, P=50P=50.

Minimising. Maximise P=−CP=-C. For C=2x+3yC=2x+3y with x+y≥4x+y\ge4, x+3y≤12x+3y\le12, the result is x=4x=4, y=0y=0, C=8C=8.

1234567891011246810xy(2, 0)(10, 0)(0, 6)(0, 10)x + y = 103x + y = 6
Maximise P = 2x + 5y: x + y ≤ 10 and 3x + y ≥ 6. Stage 1 finds the feasible point (2, 0); stage 2 moves to (0, 10) with P = 50.

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 x=0x=0, y=10y=10. Is the constraint 3x+y≥63x+y\ge6 satisfied?

Try an exam question

A linear program has the constraint 2x+y≥82x+y\ge8. (a) Write it as an equation using a surplus variable ss and an artificial variable tt. (b) Explain why tt is needed. (c) State how the objective P=x+3yP=x+3y is changed in the big-M method.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Which equation is the constraint after ss and tt are introduced?

1 mark, marked against the mark scheme

Revision notes