MATH 304 – MODULE 4
MR KENNETH N TERCERO
Introduction to the Big M Method
In this section, we will present a generalized version of the simplex method that
will solve both maximization and minimization problems with any combination
of ≤, ≥, = constraints
In order to use the simplex method on problems with mixed constraints, we
turn to a device called an artificial variable.
An artificial variable is a variable introduced into >= and = constraint to
ensure that we consider only basic feasible solutions, an artificial variable is
required to satisfy the nonnegative constraint.
Introduction to the Big M Method
To prevent an artificial variable from becoming part of an optimal solution to
the original problem, a very large “penalty” is introduced into the objective
function. This penalty is created by 8 choosing a positive constant M so large
that the artificial variable is forced to be 0 in any final optimal solution of the
original problem.
Big M Method: Form the Modified
Problem
If any problem constraints have negative constants on the right e, multiply
both sides by -1 to obtain a constraint with a nonnegative constant.
Remember to reverse the direction of the inequality if the constraint is an
inequality.
Introduce a slack variable for each constraint of the form ≤.
Introduce a surplus variable and an artificial variable in each ≥ constraint.
Introduce an artificial variable in each = constraint.
For each artificial variable a, add –Ma in case of maximizing objective
function and add +Ma in case of miniimizing objective function. Use the
same constant M for all artificial variables.
STEP BY STEP PROCESS
STEP 1: TRANSFORM THE LINEAR PROGRAMMING MODEL INTO EQUATION;
STEP 3: CHANGE THE M IN A1 AND A2 TO ZERO;
STEP 2: CONVERT THE SLE TO SIMPLEX TABLEAU;
STEP 4: CHECK THE OPTIMALITY;
STEP 5: DETERMINE THE PIVOT COLUMN;
STEP 6: DETERMINE THE PIVOT ROW (RATIO TEST);
STEP 7: PIVOTING
LINEAR PROGRAMMING MODEL
TAKE NOTE (INEQUALITIES):
PROBLEM SLE
MAXIMIZE 𝐏 = 𝒙 − 𝒚 + 𝟑𝒛 MAXIMAZATION + (-MA)
MINIMIZATION +(MA)
SUBJECT TO;
𝒙 + 𝒚 ≤ 𝟐𝟎 TAKE NOTE (CONSTRAINTS):
𝒙+𝒛=𝟓 INEQUALITIES SLE
𝒚 + 𝒛 ≥ 𝟏𝟎 ≤ +S
𝒙, 𝒚, 𝒛 ≥ 𝟎 = +A
>= -S AND +A
Introduction to the Big M Method
Example:
MAXIMIZE 𝐏 = 𝒙 − 𝒚 + 𝟑𝒛 + −𝑴𝑨𝟏 + (−𝑴𝑨𝟐 )
SUBJECT TO;
𝒙 + 𝒚 + 𝑺𝟏 = 𝟐𝟎
𝒙 + 𝒛 + 𝑨𝟏 = 𝟓
𝒚 + 𝒛 − 𝑺𝟐 + 𝑨𝟐 = 𝟏𝟎
𝒙, 𝒚, 𝒛, 𝑺𝟏 , 𝑺𝟐 , 𝑨𝟏 , 𝑨𝟐 ≥ 𝟎
STEP 1: TRANSFORM THE LINEAR PROGRAMMING MODEL INTO EQUATION
MAXIMIZE
−𝒙 + 𝒚 − 𝟑𝒛 + 𝑴𝑨𝟏 + 𝑴𝑨𝟐 + 𝑷 = 𝟎
SUBJECT TO;
𝒙 + 𝒚 + 𝑺𝟏 = 𝟐𝟎
𝒙 + 𝒛 + 𝑨𝟏 = 𝟓
𝒚 + 𝒛 − 𝑺𝟐 + 𝑨𝟐 = 𝟏𝟎
𝒙, 𝒚, 𝒛, 𝑺𝟏 , 𝑺𝟐 , 𝑨𝟏 , 𝑨𝟐 ≥ 𝟎
STEP 2: CONVERT THE SLE TO SIMPLEX TABLEAU
MAXIMIZE
−𝒙 + 𝒚 − 𝟑𝒛 + 𝑴𝑨𝟏 + 𝑴𝑨𝟐 + 𝑷 = 𝟎
SUBJECT TO;
𝒙 + 𝒚 + 𝑺𝟏 = 𝟐𝟎
𝒙 + 𝒛 + 𝑨𝟏 = 𝟓
𝒚 + 𝒛 − 𝑺𝟐 + 𝑨𝟐 = 𝟏𝟎
𝒙, 𝒚, 𝒛, 𝑺𝟏 , 𝑺𝟐 , 𝑨𝟏 , 𝑨𝟐 ≥ 𝟎
ROW x y z 𝑺𝟏 𝑺𝟐 𝑨𝟏 𝑨𝟐 P RHS
R1 1 1 0 1 0 0 0 0 20
R2 1 0 1 0 0 1 0 0 5
R3 0 1 1 0 -1 0 1 0 10
R4 -1 1 -3 0 0 M M 1 0
STEP 3: CHANGE THE M IN A1 AND A2 TO ZERO
ROW x y z 𝑺𝟏 𝑺𝟐 𝑨𝟏 𝑨𝟐 P RHS
R1 1 1 0 1 0 0 0 0 20
R2 1 0 1 0 0 1 0 0 5
R3 0 1 1 0 -1 0 1 0 10
R4 -1 1 -3 0 0 M M 1 0
ROW x y z 𝑺𝟏 𝑺𝟐 𝑨𝟏 𝑨𝟐 P RHS
R1 1 1 0 1 0 0 0 0 20
CHANGE M TO ZERO R2 1 0 1 0 0 1 0 0 5
R3 0 1 1 0 -1 0 1 0 10
𝐸𝑅𝑇𝐶 ∗ RPE + RTC → RTC
R4 -1 1 -3 0 0 M M 1 0
−𝑀 ∗ 𝑅2 + 𝑅4 → 𝑅4
ROW x y z 𝑺𝟏 𝑺𝟐 𝑨𝟏 𝑨𝟐 P RHS
R1 1 1 0 1 0 0 0 0 20
R2 1 0 1 0 0 1 0 0 5
R3 0 1 1 0 -1 0 1 0 10
R4 -M-1 1 -M-3 0 0 0 M 1 -5M
RO x y z 𝑺𝟏 𝑺𝟐 𝑨𝟏 𝑨𝟐 P RHS
W
R1 1 1 0 1 0 0 0 0 20
R2 1 0 1 0 0 1 0 0 5
𝐸𝑅𝑇𝐶 ∗ RPE + RTC → RTC
R3 0 1 1 0 -1 0 1 0 10
−𝑀 ∗ 𝑅3 + 𝑅4 → 𝑅4 R4 -M-1 1 -M-3 0 0 0 M 1 -5M
ROW x y z 𝑺𝟏 𝑺𝟐 𝑨𝟏 𝑨𝟐 P RHS
R1 1 1 0 1 0 0 0 0 20
R2 1 0 1 0 0 1 0 0 5
R3 0 1 1 0 -1 0 1 0 10
R4 -M-1 -M+1 -2M-3 0 M 0 0 1 -15M
The Big M Method
x y z s1 s2 A1 A2 P RHS
1 1 0 1 0 0 0 0 20
1 0 1 0 0 1 0 0 5
0 1 1 0 -1 0 1 0 10
-M-1 -M+1 -2M-3 0 M 0 0 1 -15M
Basic Variables: s1, A1, A2 and P
Non Basic Variables: x, y, z, s2
STEP 4: CHECK THE OPTIMALITY
ROW BV X Y z s1 s2 A1 A2 P RHS RATIO TEST
1 s1 1 1 0 1 0 0 0 0 20 20/0= UNDEFINED
2 A1 1 0 1 0 0 1 0 0 5 5/1 =5
3 A2 0 1 1 0 -1 0 1 0 10 10/1 = 10
4 P -M-1 -M+1 -2M-3 0 M 0 0 1 -15M
NOT OPTIMAL
ASSUME THAT M=10
X -> -M-1 = -10 -1 = -11
Y - > -M+1 = -10+1 = -9
Z -> -2(10) -3 = -23
STEP 5: DETERMINE THE PIVOT COLUMN
ROW BV X Y z s1 s2 A1 A2 P RHS
1 s1 1 1 0 1 0 0 0 0 20
2 A1 1 0 1 0 0 1 0 0 5
3 A2 0 1 1 0 -1 0 1 0 10
4 P -M-1 -M+1 -2M-3 0 M 0 0 1 -15M
STEP 6: DETERMINE THE PIVOT ROW
(RATIO TEST)
ROW BV X Y z s1 s2 A1 A2 P RHS RATIO TEST
1 s1 1 1 0 1 0 0 0 0 20 20/0= UNDEFINED
2 A1 1 0 1 0 0 1 0 0 5 5/1 =5
3 A2 0 1 1 0 -1 0 1 0 10 10/1 = 10
4 P -M-1 -M+1 -2M-3 0 M 0 0 1 -15M
STEP 7: PIVOTING
ROW BV X Y z s1 s2 A1 A2 P RHS RATIO TEST
1 s1 1 1 0 1 0 0 0 0 20 20/0= UNDEFINED
2 A1 1 0 1 0 0 1 0 0 5 5/1 =5
3 A2 0 1 1 0 -1 0 1 0 10 10/1 = 10
4 P -M-1 -M+1 -2M-3 0 M 0 0 1 -15M
Z = Entering Variable; A1 = Leaving Variable
ROW BV X Y z s1 s2 A1 A2 P RHS RATIO TEST
1 s1 1 1 0 1 0 0 0 0 20 20/0= UNDEFINED
2 z 1 0 1 0 0 1 0 0 5 5/1 =5
3 A2 0 1 1 0 -1 0 1 0 10 10/1 = 10
4 P -M-1 -M+1 -2M-3 0 M 0 0 1 -15M
ROW BV X Y z s1 s2 A1 A2 P RHS
R1 s1 1 1 0 1 0 0 0 0 20
𝐸𝑅𝑇𝐶 ∗ RPE + RTC → RTC R2 z 1 0 1 0 0 1 0 0 5
R3 A2 0 1 1 0 -1 0 1 0 10
−1 ∗ 𝑅2 + 𝑅3 → 𝑅3
R4 P -M-1 -M+1 -2M- 0 M 0 0 1 -15M
3
ROW BV X Y z s1 s2 A1 A2 P RHS
R1 s1 1 1 0 1 0 0 0 0 20
R2 z 1 0 1 0 0 1 0 0 5
R3 A2 -1 1 0 0 -1 -1 1 0 5
R4 P -M-1 -M+1 -2M-3 0 M 0 0 1 -15M
ROW BV X Y z s1 s2 A1 A2 P RHS
R1 s1 1 1 0 1 0 0 0 0 20
R2 z 1 0 1 0 0 1 0 0 5
𝐸𝑅𝑇𝐶 ∗ RPE + RTC → RTC
R3 A2 -1 1 0 0 -1 -1 1 0 5
(2𝑀 + 3) ∗ 𝑅2 + 𝑅4 → 𝑅4
R4 P -M-1 -M+1 -2M-3 0 M 0 0 1 -15M
ROW BV X Y z s1 s2 A1 A2 P RHS
R1 s1 1 1 0 1 0 0 0 0 20
R2 z 1 0 1 0 0 1 0 0 5
R3 A2 -1 1 0 0 -1 -1 1 0 5
R4 P M+2 -M+1 0 0 M 2M+3 0 1 -5M+15
STEP 4: CHECK THE OPTIMALITY
ROW BV X Y z s1 s2 A1 A2 P RHS
R1 s1 1 1 0 1 0 0 0 0 20
R2 z 1 0 1 0 0 1 0 0 5
R3 A2 -1 1 0 0 -1 -1 1 0 5
R4 P M+2 -M+1 0 0 M 2M+3 0 1 -5M+15
NOT OPTIMAL
STEP 5: DETERMINE THE PIVOT COLUMN
ROW BV X Y z s1 s2 A1 A2 P RHS
R1 s1 1 1 0 1 0 0 0 0 20
R2 z 1 0 1 0 0 1 0 0 5
R3 A2 -1 1 0 0 -1 -1 1 0 5
R4 P M+2 -M+1 0 0 M 2M+3 0 1 -5M+15
ASSUMING M = 10
X -> M+2 = 10+2 = 12
Y -> -M+1 = -10 +2 = -8
STEP 6: DETERMINE THE PIVOT ROW
(RATIO TEST)
ROW BV X Y z s1 s2 A1 A2 P RHS RATIO TEST
R1 s1 1 1 0 1 0 0 0 0 20 20/1 =20
R2 z 1 0 1 0 0 1 0 0 5 5/0 =
UNDEFINED
R3 A2 -1 1 0 0 -1 -1 1 0 5 5/1 =5
R4 P M+2 -M+1 0 0 M 2M+3 0 1 -5M+15
ROW BV X Y z s1 s2 A1 A2 P RHS RATIO TEST
R1 s1 1 1 0 1 0 0 0 0 20 20/1 =20
R2 z 1 0 1 0 0 1 0 0 5 5/0 =
UNDEFINED
R3 A2 -1 1 0 0 -1 -1 1 0 5 5/1 =5
R4 P M+2 -M+1 0 0 M 2M+3 0 1 -
5M+15
Y = ENTERING VARIABLE ; A2 = LEAVING VARIABLE
ROW BV X Y z s1 s2 A1 A2 P RHS RATIO
TEST
R1 s1 1 1 0 1 0 0 0 0 20 20/1 =20
R2 z 1 0 1 0 0 1 0 0 5 5/0 =
UNDEFIN
ED
R3 Y -1 1 0 0 -1 -1 1 0 5 5/1 =5
R4 P M+2 -M+1 0 0 M 2M+ 0 1 -
3 5M+15
STEP 7: PIVOTING
ROW BV X Y z s1 s2 A1 A2 P RHS
R1 s1 1 1 0 1 0 0 0 0 20
𝐸𝑅𝑇𝐶 ∗ RPE + RTC → RTC R2 z 1 0 1 0 0 1 0 0 5
(−1) ∗ 𝑅3 + 𝑅1 → 𝑅1 R3 y -1 1 0 0 -1 -1 1 0 5
R4 P M+2 -M+1 0 0 M 2M+3 0 1 -5M+15
ROW BV X Y z s1 s2 A1 A2 P RHS
R1 s1 2 0 0 1 1 1 -1 0 15
R2 z 1 0 1 0 0 1 0 0 5
R3 y -1 1 0 0 -1 -1 1 0 5
R4 P M+2 -M+1 0 0 M 2M+3 0 1 -5M+15
STEP 7: PIVOTING
ROW BV X Y z s1 s2 A1 A2 P RHS
R1 s1 2 0 0 1 1 1 -1 0 15
𝐸𝑅𝑇𝐶 ∗ RPE + RTC → RTC
R2 z 1 0 1 0 0 1 0 0 5
(𝑀 − 1) ∗ 𝑅3 + 𝑅4 → 𝑅4
R3 y -1 1 0 0 -1 -1 1 0 5
R4 P M+2 -M+1 0 0 M 2M+3 0 1 -5M+15
ROW BV X Y z s1 s2 A1 A2 P RHS
R1 s1 2 0 0 1 1 1 -1 0 15
R2 z 1 0 1 0 0 1 0 0 5
R3 y -1 1 0 0 -1 -1 1 0 5
R4 P 3 0 0 0 1 M+4 M-1 1 10
STEP 4: CHECK THE OPTIMALITY
ROW BV X Y z s1 s2 A1 A2 P RHS
R1 s1 2 0 0 1 1 1 -1 0 15
R2 z 1 0 1 0 0 1 0 0 5
R3 y -1 1 0 0 -1 -1 1 0 5
R4 P 3 0 0 0 1 M+4 M-1 1 10
OPTIMAL
ROW BV X Y z s1 s2 A1 A2 P RHS
R1 s1 2 0 0 1 1 1 -1 0 15
R2 z 1 0 1 0 0 1 0 0 5
R3 y -1 1 0 0 -1 -1 1 0 5
R4 P 3 0 0 0 1 M+4 M-1 1 10
BASIC VARIABLE NON BASIC VARIABLE X=0
S1 =15 X=0 Y=5
Z=5 S2 = 0 Z=5
Y=5 A1=0 P = 10
P =10 A2=0
SEATWORK #3 : BY PAIR