Chapter (4)
Solving Linear Programming Problems: The Simplex Method
The Simplex Method in Tubular Form
Big M Method
Two Phase Method
Presented by Dr Yee Yee Htun CM- 401 1
The Simplex method in Tabular Form
3.1 Prototype Example
𝑀𝑎𝑥: 𝑍 = 3𝑥1 + 5𝑥2
Subject to 𝑥1 ≤ 4
2𝑥2 ≤ 12
3𝑥1 + 2𝑥2 ≤ 18
and 𝑥1 ≥ 0, 𝑥2 ≥ 0
Solution Augmented Form
𝑀𝑎𝑥: 𝑍 = 3𝑥1 + 5𝑥2 + 0𝑥3 + 0𝑥4 + 0𝑥5
Subject to 𝑥1 + 𝑥3 =4
2𝑥2 + 𝑥4 = 12
3𝑥1 + 2𝑥2 + 𝑥5 = 18
and 𝑥1 , 𝑥2, 𝑥3 , 𝑥4 , 𝑥5 ≥ 0, where 𝑥3 , 𝑥4 , 𝑥5 are called slack variables.
Presented by Dr Yee Yee Htun CM- 401 2
Iteration 0
Eq: 0 𝑍 − 3𝑥1 − 5𝑥2 = 0
Eq: 1 𝑥1 + 𝑥3 =4
Eq: 2 2𝑥2 + 𝑥4 = 12
Eq: 3 3𝑥1 + 2𝑥2 + 𝑥5 = 18
Pivot Data
Tubular Form
Basic Coefficient of Right
Iteration Eq: Ratio
Variable Sides
𝑍 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5
𝑍 (0) 1 -3 -5 0 0 0 0
𝑥3 (1) 0 1 0 1 0 0 4 -
0
𝑥4 (2) 0 0 2 0 1 0 12 6
𝑥5 (3) 0 3 2 0 0 1 18 9
Presented by Dr Yee Yee Htun CM- 401 3
Pivot Data
Basic Coefficient of Right
Iteration Eq: Ratio
Variable Sides
𝑍 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5
𝑍 (0) 1 -3 0 0 5/2 0 30
𝑥3 (1) 0 1 0 1 0 0 4 4
1
𝑥2 (2) 0 0 1 0 1/2 0 6 -
𝑥5 (3) 0 3 0 0 -1 1 6 2
𝑍 (0) 1 0 0 0 3/2 1 36
𝑥3 (1) 0 0 0 1 1/3 -1/3 2
2
𝑥4 (2) 0 0 1 0 1/2 0 6
𝑥1 (3) 0 1 0 0 -1/3 1/3 2
The optimal solution 𝑍 = 36 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑎𝑡 𝑥1 = 2, 𝑥2 = 6, 𝑥3 = 2, 𝑥4 = 0, 𝑥5 = 0
Presented by Dr Yee Yee Htun CM- 401 4
The Simplex method with unbounded solution
Example 𝑀𝑎𝑥: 𝑍 = 5𝑥1 + 𝑥2 + 3𝑥3 + 4𝑥4
Subject to 𝑥1 − 2𝑥2 + 4𝑥3 + 3𝑥4 ≤ 20
−4𝑥1 + 6𝑥2 + 5𝑥3 − 4𝑥4 ≤ 40
2𝑥1 − 3𝑥2 + 3𝑥3 + 8𝑥4 ≤ 50
and 𝑥1 ≥ 0, 𝑥2 ≥ 0, 𝑥3 ≥ 0, 𝑥4 ≥ 0
Solution Augmented Form
𝑀𝑎𝑥: 𝑍 = 5𝑥1 + 𝑥2 + 3𝑥3 + 4𝑥4 + 0𝑥5 + 0𝑥6 + 0𝑥7
Subject to
𝑥1 − 2𝑥2 + 4𝑥3 + 3𝑥4 + 𝑥5 = 20
−4𝑥1 + 6𝑥2 + 5𝑥3 − 4𝑥4 + 𝑥6 = 40
2𝑥1 − 3𝑥2 + 3𝑥3 + 8𝑥4 + 𝑥7 = 50
and 𝑥1 , 𝑥2, 𝑥3 , 𝑥4 , 𝑥5 , 𝑥6 , 𝑥7 ≥ 0, where 𝑥5 , 𝑥6 , 𝑥7 are called slack variables.
Presented by Dr Yee Yee Htun CM- 401 5
Iteration 0
Eq: 0 𝑍 − 5𝑥1 + 𝑥2 − 3𝑥3 − 4𝑥4 = 0
Eq: 1 𝑥1 − 2𝑥2 + 4𝑥3 + 3𝑥4 + 𝑥5 = 20
Eq: 2 −4𝑥1 + 6𝑥2 + 5𝑥3 − 4𝑥4 + 𝑥6 = 40
Eq: 3 2𝑥1 − 3𝑥2 + 3𝑥3 + 8𝑥4 + 𝑥7 = 50
Pivot Data
Tubular Form
Basic Coefficient of Right
Iteration Eq: Ratio
Variable Sides
𝑍 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑥6 𝑥7
𝑍 (0) 1 -5 1 -3 -4 0 0 0 0
𝑥5 (1) 0 1 -2 4 3 1 0 0 20 20
0
𝑥6 (2) 0 -4 6 5 -4 0 1 0 40 -
𝑥7 (3) 0 2 -3 3 8 0 0 1 50 25
Presented by Dr Yee Yee Htun CM- 401 6
Pivot Data
Pivot Data
Basic Coefficient of Right
Iteration Eq: Ratio
Variable Sides
𝑍 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑥6 𝑥7
𝑍 (0) 1 0 -9 17 11 5 0 0 100
𝑥1 (1) 0 1 -2 4 3 1 0 0 20
1
𝑥6 (2) 0 0 -2 21 8 4 1 0 120
𝑥7 (3) 0 0 1 -5 2 -2 0 1 10 10
𝑍 (0) 1 0 0 -28 28 -13 0 9 190
𝑥1 (1) 0 1 0 -6 7 -3 0 0 40
2
𝑥6 (2) 0 0 0 11 12 0 1 2 140 12.73
𝑥2 (3) 0 0 1 -5 2 -2 0 1 10
Presented by Dr Yee Yee Htun CM- 401 7
Basic Coefficient of Right
Iteration Eq: Ratio
Variable Sides
𝑍 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑥6 𝑥7
𝑍 (0) 1 0 0 0 655/11 -13 28/11 155/11 6010/11
𝑥1 (1) 0 1 0 0 149/11 -3 6/11 12/11 1280/11
3
𝑥3 (2) 0 0 0 1 12/11 0 1/11 2/11 140/11
𝑥2 (3) 0 0 1 0 82/11 -2 5/11 21/11 810/11
The solution is unbounded solution.
Presented by Dr Yee Yee Htun CM- 401 8
Simplex Method With No Standard Form
𝑀𝑎𝑥: 𝑍 = 90𝑥1 + 70𝑥2
Subject to 2𝑥1 + 𝑥2 ≤ 2
𝑥1 − 𝑥2 ≥ 2
and 𝑥1 ≥ 0, 𝑥2 ≥ 0
Solution Standard Form
𝑀𝑎𝑥: 𝑍 = 90𝑥1 + 70𝑥2
Subject to 2𝑥1 + 𝑥2 ≤ 2
−𝑥1 + 𝑥2 ≤ −𝟐
and 𝑥1 ≥ 0, 𝑥2 ≥ 0
The optimal solution is no feasible solution.
Presented by Dr Yee Yee Htun CM- 401 9
Big-M Method
Variables
≤ Slack Variable
≥ Surplus Variable
= Artificial Variable
Presented by Dr Yee Yee Htun CM- 401 10
Maximize Case
Example 𝑀𝑎𝑥: 𝑍 = 3𝑥1 + 5𝑥2
Subject to 𝑥1 ≤ 4
2𝑥2 ≤ 12
3𝑥1 + 2𝑥2 = 18
and 𝑥1 ≥ 0, 𝑥2 ≥ 0
Solution Artificial Problem
𝑀𝑎𝑥: 𝑍 = 3𝑥1 + 5𝑥2 − 𝑀𝑥5
Subject to 𝑥1 + 𝑥3 =4
2𝑥2 + 𝑥4 = 12
3𝑥1 + 2𝑥2 +𝑥5 = 18
and 𝑥1 , 𝑥2, 𝑥3 , 𝑥4 , 𝑥5 ≥ 0
Presented by Dr Yee Yee Htun CM- 401 11
Iteration 0
Eq: 0 𝑍 − 3𝑥1 − 5𝑥2 + 𝑀 𝑥5 = 0 Eq: 0 𝑍 − 3𝑥1 − 5𝑥2 + 𝑀𝑥5 = 0
Eq: 1 𝑥1 + 𝑥3 =4 Eq: 3 × −𝑀 − 3𝑀𝑥1 − 2𝑀𝑥2 − 𝑀𝑥5 = −18𝑀
Eq: 2 2𝑥2 + 𝑥4 = 12 ---------------------------------------------------------------------
Eq: 3 3𝑥1 + 2𝑥2 + 𝑥5 = 18 New Eq:(0) 𝑍 + −3𝑀 − 3 𝑥1 + −2𝑀 − 5 𝑥2 = −18𝑀
Pivot Data
Tubular Form
Basic Coefficient of Right
Iteration Eq: Ratio
Variable Sides
𝑍 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5
𝑍 (0) 1 -3M-3 -2M-5 0 0 0 -18M
𝑥3 (1) 0 1 0 1 0 0 4 4
0
𝑥4 (2) 0 0 2 0 1 0 12 -
𝑥5 (3) 0 3 2 0 0 1 18 6
Presented by Dr Yee Yee Htun CM- 401 12
Coefficient of Pivot Data
Basic Right
Iteration Eq: Ratio
Variable Sides
𝑍 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5
𝑍 (0) 1 0 -2M-5 3M+3 0 0 -6M+12
𝑥1 (1) 0 1 0 1 0 0 4 -
1
𝑥4 (2) 0 0 2 0 1 0 12 6
𝑥5 (3) 0 0 2 -3 0 1 6 3
Pivot Data
𝑍 (0) 1 0 0 -9/2 0 M+5/2 27
𝑥1 (1) 0 1 0 1 0 0 4 4
2
𝑥4 (2) 0 0 0 3 1 -1 6 2
𝑥2 (3) 0 0 1 -3/2 0 1/2 3 -
𝑍 (0) 1 0 0 0 3/2 M+1 36
𝑥1 (1) 0 1 0 0 -1/3 1/3 2
3
𝑥3 (2) 0 0 0 1 1/3 -1/3 2
𝑥2 (3) 0 0 1 0 1/2 0 6
The optimal solution 𝑍 = 36 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 with (𝑥1 , 𝑥2, 𝑥3 , 𝑥4 , 𝑥5 ) = (2,6,2,0,0).
Presented by Dr Yee Yee Htun CM- 401 13
Minimize Case
Example 𝑀𝑖𝑛: 𝑍 = 0.4𝑥1 + 0.5𝑥2
Subject to 0.3𝑥1 + 0.1𝑥2 ≤ 2.7
0.5𝑥1 + 0.5𝑥2 = 6
0.6𝑥1 + 0.4𝑥2 ≥ 6
and 𝑥1 ≥ 0, 𝑥2 ≥ 0
Solution Artificial Problem
𝑀𝑖𝑛: 𝑍 = 0.4𝑥1 + 0.5𝑥2 + 𝑀𝑥4 + 𝑀𝑥6
Subject to 0.3𝑥1 + 0.1𝑥2 + 𝑥3 = 2.7
0.5𝑥1 + 0.5𝑥2 + 𝑥4 = 6
0.6𝑥1 + 0.4𝑥2 −𝑥5 +𝑥6 = 6
and 𝑥1 , 𝑥2, 𝑥3 , 𝑥4 , 𝑥5 , 𝑥6 ≥ 0
Presented by Dr Yee Yee Htun CM- 401 14
𝑀𝑎𝑥: −𝑍 = −0.4𝑥1 − 0.5𝑥2 − 𝑀𝑥4 − 𝑀𝑥6
Subject to 0.3𝑥1 + 0.1𝑥2 + 𝑥3 = 2.7
0.5𝑥1 + 0.5𝑥2 + 𝑥4 = 6
0.6𝑥1 + 0.4𝑥2 −𝑥5 +𝑥6 = 6
and 𝑥1 , 𝑥2, 𝑥3 , 𝑥4 , 𝑥5 , 𝑥6 ≥ 0
Iteration 0
Eq: 0 − 𝑍 + 0.4𝑥1 + 0.5𝑥2 + 𝑀𝑥4 + 𝑥6 = 0
Eq: 1 0.3𝑥1 + 0.1𝑥2 + 𝑥3 = 2.7
Eq: 2 0.5𝑥1 + 0.5𝑥2 + 𝑥4 =6
Eq: 3 0.6𝑥1 + 0.4𝑥2 −𝑥5 + 𝑥6 = 6
Presented by Dr Yee Yee Htun CM- 401 15
Eq: 0 − 𝑍 + 0.4𝑥1 + 0.5𝑥2 + 𝑀𝑥4 + 𝑀𝑥6 = 0
Eq: 2 × −𝑀 −0.5𝑀𝑥1 − 0.5𝑀𝑥2 − 𝑀 𝑥4 = −6𝑀
Eq: 3 × −𝑀 − 0.6𝑀𝑥1 − 0.4𝑀𝑥2 +𝑀𝑥5 −𝑀𝑥6 = −6𝑀
-----------------------------------------------------------------------------------
New Eq:( 0) − 𝑍 + −1.1𝑀 + 0.4 𝑥1 + −0.9𝑀 + 0.5 𝑥2 +𝑀𝑥5 = −12𝑀
Pivot Data
Tubular Form
Basic Coefficient of Right
Iteration Eq: Ratio
Variable Sides
𝑍 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑥6
𝑍 (0) -1 -1.1M+0.4 -0.9M+0.5 0 0 M 0 -12M
𝑥3 (1) 0 0.3 0.1 1 0 0 0 2.7 9
0
𝑥4 (2) 0 0.5 0.5 0 1 0 0 6 12
𝑥6 (3) 0 0.6 0.4 0 0 -1 1 6 10
Presented by Dr Yee Yee Htun CM- 401 16
Pivot Data Pivot Data
Basic Coefficient of Right
Iteration Eq: Ratio
Variable Sides
𝑍 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑥6
𝑍 (0) -1 0 -8/15 M+11/30 11/3 M - 4/3 0 M 0 -2.1 M - 3.6
𝑥1 (1) 0 1 1/3 10/3 0 0 0 9 27
1
𝑥4 (2) 0 0 1/3 -5/3 1 0 0 3/2 4.5
𝑥6 (3) 0 0 1/5 -2 0 -1 1 3/5 3
𝑍 (0) -1 0 0 -5/3 M + 7/3 0 -5/3 M + 11/6 8/3 M - 11/6 -1/2 M - 4.7
𝑥1 (1) 0 1 0 20/3 0 5/3 -5/3 -5/3 4.8
2
𝑥4 (2) 0 0 0 5/3 1 5/3 -5/3 -5/3 0.3
𝑥2 (3) 0 0 1 -10 0 -5 5 5 -
𝑍 (0) -1 0 0 1/2 M - 11/10 0 M -5.25
𝑥1 (1) 0 1 0 5 -1 0 0 15/2
3
𝑥5 (2) 0 0 0 1 3/5 1 -1 3/10
𝑥2 (3) 0 0 1 -5 3 0 0 9/2
The optimal solution 𝑍 = −5.25 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 /𝑧 = 5.25 𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑤𝑖𝑡ℎ (𝑥1 , 𝑥2, 𝑥3 , 𝑥4 , 𝑥5 , 𝑥6 ) = (15/2,9/2,0,0,3/10,0).
Presented by Dr Yee Yee Htun CM- 401 17
Two- Phase Method
Example 𝑀𝑖𝑛: 𝑍 = 0.4𝑥1 + 0.5𝑥2
Subject to 0.3𝑥1 + 0.1𝑥2 ≤ 2.7
0.5𝑥1 + 0.5𝑥2 = 6
0.6𝑥1 + 0.4𝑥2 ≥ 6
and 𝑥1 ≥ 0, 𝑥2 ≥ 0
Solution Phase I
𝑀𝑖𝑛: 𝑍 = 𝑥4 + 𝑥6 Max: −𝑍 = −𝑥4 − 𝑥6
Subject to 0.3𝑥1 + 0.1𝑥2 + 𝑥3 = 2.7
0.5𝑥1 + 0.5𝑥2 + 𝑥4 =6
0.6𝑥1 + 0.4𝑥2 − 𝑥5 + 𝑥6 = 6
and 𝑥1 , 𝑥2, 𝑥3 , 𝑥4 , 𝑥5 , 𝑥6 ≥ 0
Presented by Dr Yee Yee Htun CM- 401 18
Iteration 0
Eq: 0 − 𝑍 + 𝑥4 + 𝑥6 = 0
Eq: 1 0.3𝑥1 + 0.1𝑥2 + 𝑥3 = 2.7
Eq: 2 0.5𝑥1 + 0.5𝑥2 + 𝑥4 =6
Eq: 3 0.6𝑥1 + 0.4𝑥2 − 𝑥5 + 𝑥6 = 6
Pivot Data
Tubular Form
Basic Coefficient of Right
Iteration Eq: Ratio
Variable Sides
𝑍 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑥6
𝑍 (0) -1 -1.1 -0.9 0 0 1 0 -12
𝑥3 (1) 0 0.3 0.1 1 0 0 0 2.7 9
0
𝑥4 (2) 0 0.5 0.5 0 1 0 0 6 12
𝑥6 (3) 0 0.6 0.4 0 0 -1 1 6 10
Presented by Dr Yee Yee Htun CM- 401 19
Basic Coefficient of Right
Iteration Eq: Ratio Pivot Data
Variable 𝑍 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑥6 Sides
𝑍 (0) -1 0 -8/15 11/3 0 1 0 -21/10
𝑥1 (1) 0 1 1/3 10/3 0 0 0 9 27
1
𝑥4 (2) 0 0 1/3 -5/3 1 0 0 3/2 4.5
𝑥6 (3) 0 0 1/5 -2 0 -1 1 3/5 3 Pivot Data
𝑍 (0) -1 0 0 -5/3 0 -5/3 8/3 -1/2
𝑥1 (1) 0 1 0 20/3 0 5/3 -5/3 8 1.2
2
𝑥4 (2) 0 0 0 5/3 1 5/3 -5/3 1/2 0.3
𝑥2 (3) 0 0 1 -10 0 -5 5 3
𝑍 (0) -1 0 0 0 1 0 1 0
𝑥1 (1) 0 1 0 0 -4 -5 5 6
3
𝑥3 (2) 0 0 0 1 3/5 1 -1 3/10
𝑥2 (3) 0 0 1 0 6 -5 -5 6
N0 Minus Value in iteration 3 and 𝑍 = 0. So 𝐏𝐡𝐚𝐬𝐞 ( 𝐈 )𝐭𝐞𝐫𝐦𝐢𝐧𝐚𝐭𝐞.
Presented by Dr Yee Yee Htun CM- 401 20
Phase II
𝑀𝑖𝑛: 𝑍 = 0.4𝑥1 + 0.5𝑥2
𝑀𝑎𝑥: −𝑍 = −0.4𝑥1 − 0.5𝑥2
Equation
Eq: 0 − 𝑍 + 0.4𝑥1 + 0.5𝑥2 = 0
Eq: 1 0.3𝑥1 + 0.1𝑥2 + 𝑥3 = 2.7
Eq: 2 0.5𝑥1 + 0.5𝑥2 =6
Eq: 3 0.6𝑥1 + 0.4𝑥2 − 𝑥5 = 6
𝑧 𝑥1 𝑥2 𝑥3 𝑥5
-1 0.4 0.5 0 0 =0
0 - 0.4 0 0 2 = -2.4
0 0 -0.5 0 -2.5 = -3
New E𝐪: 𝟎 -1 0 0 0 -0.5 = -5.4
Presented by Dr Yee Yee Htun CM- 401 21
Iteration Basic Coefficient of Right
Eq: Ratio Pivot Data
0 Variable 𝑍 𝑥1 𝑥2 𝑥3 𝑥5 Sides
𝑍 (0) -1 0 0 0 -0.5 -5.4
𝑥1 (1) 0 1 0 0 -5 6
0
𝑥3 (2) 0 0 0 1 1 0.3 0.3
𝑥2 (3) 0 0 1 0 5 6 1.2
𝑍 (0) -1 0 0 0.5 0 -5.25
𝑥1 (1) 0 1 0 5 0 7.5
1 𝑥3 (2) 0 0 0 1 1 0.3
𝑥2 (3) 0 0 1 -5 0 4.5
The basic feasible solution is Max: Z = -5.25
Min: Z = 5.25 With 𝑥1 = 7.5, 𝑥2 = 4.5, 𝑥3 = 0.3
Presented by Dr Yee Yee Htun CM- 401 22
Problems
No Page Problems No No Page Problems No
1 173 4.1.6 8 176 4.4.6
2 174 4.3.4 9 176 4.4.8
3 174 4.3.5 10 176 4.4.10
4 175 4.3.6 11 177 4.6.1
5 175 4.3.7 12 178 4.6.2
6 175 4.4.4 13 178 4.6.3
7 176 4.4.5 14 178 4.6.4
15 178 4.6.6
Presented by Dr Yee Yee Htun CM- 401 23