Big M Method
By Eman Nasser
12/5/2024 Big M 1
Example 1
• Solve the following linear programming (LP) problem :
• Max Z= x1 + x2
subject to
2x1 + 5x2 <= 6
x1 + x2 >= 2
and x1,x2 >= 0
12/5/2024 Big M 2
Solution
• As the constraint-1 is of type '≤' we
should add slack variable S1
• As the constraint-2 is of type '≥' we
should subtract surplus variable S2 and
add artificial variable A1
12/5/2024 Big M 3
Solution
12/5/2024 Big M 4
Solution
12/5/2024 Big M 5
Iteration 1
C(Z) X1 X2 S1 S2 A1 RHS
Z -1 -1 0 0 100 0
0 S1 2 5 1 0 0 6
-100 A1 1 1 0 -1 1 2
12/5/2024 Big M 6
C(Z) X1 X2 S1 S2 A1 RHS
Iteration 1 Z -1 -1 0 0 100 0
0 S1 2 5 1 0 0 6
-100 A1 1 1 0 -1 1 2
C(Z) X1 X2 S1 S2 A1 RHS
Z -101 -101 0 100 0 -200
0 S1 2 5 1 0 0 6
-100 A1 1 1 0 -1 1 2
12/5/2024 Big M 7
Iteration 1
Pivot Column
C(Z) X1 X2 S1 S2 A1 RHS
Z -101 -101 0 100 0 -200 Ratio
S1 2 5 1 0 0 6 3
A1 1 1 0 -1 1 2 2
Pivot Row (Ratio) = RHS / Pivot Column
12/5/2024 Big M 8
Iteration 1
Pivot Column
C(Z) X1 X2 S1 S2 A1 RHS
Z -101 -101 0 100 0 -200 Ratio
S1 2 5 1 0 0 6 3
A1 1 1 0 -1 1 2 2
The entering variable is x1. Pivot Row
The leaving basis variable is A1.
12/5/2024 Big M 9
C(Z) X1 X2 S1 S2 A1 RHS
Iteration 2
Z -101 -101 0 100 0 -200
S1 2 5 1 0 0 6
A1 1 1 0 -1 1 2
C(Z) X1 X2 S1 S2 A1 RHS
Z 0 0 0 -1 101 2
S1 0 3 1 2 -2 2
X1 1 1 0 -1 1 2
12/5/2024 Big M 10
C(Z) X1 X2 S1 S2 A1 RHS
Iteration 3 Z 0 0 0 -1 101 2
S1 0 3 1 2 -2 2
X1 1 1 0 -1 1 2
C(Z) X1 X2 S1 S2 A1 RHS
Optimal
Z 0 3/2 1/2 0 99 3
Solution
S2 0 3/2 1/2 1 -1 1 Z = 3 , X1 = 3 ,
X1 1 5/2 1/2 0 0 3
X2 = 0
12/5/2024 Big M 11
Example2
• Find solution using Simplex method (BigM method)
MIN Z = 2X1 + 5X2
X1 <= 5
2X2 = 12
3X1 + 2X2 >= 18
X1,X2 >= 0
12/5/2024 Big M 12
After Adding slack, surplus, artificial variables
As the constraint-2 is of type '=' we
should add artificial variable A1
12/5/2024 Big M 13
Iteration 1
X1 X2 S1 S2 A1 A2 RHS
Z -2 -5 0 0 -100 -100 0
0 S1 1 0 1 0 0 0 5
100 A1 0 2 0 0 1 0 12
100 A2 3 2 0 -1 0 1 18
12/5/2024 Big M 14
Iteration 1
X1 X2 S1 S2 A1 A2 RHS
Z -2 -5 0 0 -100 -100
0 S1 1 0 1 0 0 0 5
100 A1 0 2 0 0 1 0 12
100 A2 3 2 0 -1 0 1 18
X1 X2 S1 S2 A1 A2 RHS
Z 298 395 0 -100 0 0 3000 Ratio
S1 1 0 1 0 0 0 5 Ignore
A1 0 2 0 0 1 0 12 6
A2 3 2 0 -1 0 1 18 9
12/5/2024 Big M 15
X1 X2 S1 S2 A1 A2 RHS
Iteration 2 Z
S1
298
1
395
0
0
1
-100
0
0
0
0
0
3000
5
A1 0 2 0 0 1 0 12
A2 3 2 0 -1 0 1 18
X1 X2 S1 S2 A1 A2 RHS
Z 298 0 0 -100 -197.5 0 630
S1 1 0 1 0 0 0 5
X2 0 1 0 0 1/2 0 6
A2 3 0 0 -1 -1 1 6
• New pivot row = Old pivot row / pivot element
• New pivot row (X2) = ROW (A1)/ 2
• New (z) = old(z) – 395* new pivot row(x2)
12/5/2024 Big M 16
Iteration 2
X1 X2 S1 S2 A1 A2 RHS
Z 298 0 0 -100 -197.5 0 630 Ratio
S1 1 0 1 0 0 0 5 5
X2 0 1 0 0 1/2 0 6 ignore
A2 3 0 0 -1 -1 1 6 2
12/5/2024 Big M 17
X1 X2 S1 S2 A1 A2 RHS
Z 298 0 0 -100 -197.5 0 630
Iteration 3 S1 1 0 1 0 0 0 5
X2 0 1 0 0 1/2 0 6
A2 3 0 0 -1 -1 1 6
X1 X2 S1 S2 A1 A2 RHS
optimal solution :
Z 0 0 0 -0.7 -98.2 -99.3 34
X1=2, X2=6
S1 0 0 1 1/3 1/3 -1/3 3
X2 0 1 0 0 1/2 0 6 Min Z=34
X1 1 0 0 -1/3 -1/3 1/3 2
12/5/2024 Big M 18
Thank You ☺
12/5/2024 Big M 19
