Management Science Linear Programming IV
Linear Programming IV
Bumho Son
College of Business Administration, CAU
Management Science Linear Programming IV
Simplex Method
2
Management Science Linear Programming IV
Simplex Method
▪ Created by U.S. mathematician George Dantzig in 1947
▪ Iterative technique that begins with a basic feasible solution as a
starting point
▪ Through algebraic manipulation, the solution is improved until no
further improvement(optimal solution)
▪ Investigates only BFSs(Basic Feasible Solutions)
▪ Feasible solution
▪ Basic Feasible solution
3
Management Science Linear Programming IV
Example Problem
Maximize Z = 60 x1 + 50 x2
subject to
4 x1 + 10 x2 100
2 x1 + x2 22
3 x1 + 3 x2 39
x1 , x2 0
4
Management Science Linear Programming IV
Slack Variable
▪ Simplex method requires all constraints to be equality(=) for
introducing the slack variables
Maximize Z = 60 x1 + 50 x2
subject to
4 x1 + 10 x2 + s1 = 100
2 x1 + x2 + s2 = 22
3 x1 + 3 x2 + s3 = 39
All variables 0
5
Management Science Linear Programming IV
General Notation
▪ Notation used in the simplex tableau:
▪ Comparison of Server Model and General Simplex Notation
6
Management Science Linear Programming IV
Number of Constraints and Variables
▪ These constraints are 𝟑 × 𝟓
▪ 3 constraints, 5 variables (including slack variables)
▪ We say that the problem is 𝑀 × 𝑁. (Here, M=3, N=5)
▪ Typically, M<N
• What does occur if M=N?
• What does occur if M>N?
• (Hint) Number of feasible solutions
7
Management Science Linear Programming IV
Feasible Solutions
▪ Corner points: solutions with only 3 variables
▪ Because there are 3 equations
▪ The other 2 variables are set to be 0
5
▪ There are 3
= 10 corner points
4 x1 + 10 x2 + s1 = 100
2 x1 + x2 + s2 = 22
3x1 + 3x2 + s3 = 39
8
Management Science Linear Programming IV
Basis (Basic Variable)
▪ When the problem is M×N, a feasible solution which consists of M
variables is called BFS(Basic Feasible Solution), and the M variables
are called Basis.
▪ Basic variables are >0
▪ Non-basic variables are set to be 0.
▪ Example: Construct a BFS with
▪ s1, s2, s3
• Feasible? Maximize Z = 60 x1 + 50 x2
• Obj value? subject to
▪ x1, s1, s3
4 x1 + 10 x2 + s1 = 100
• Feasible?
• Obj value? 2 x1 + x2 + s2 = 22
3 x1 + 3 x2 + s3 = 39
All variables 0
9
Management Science Linear Programming IV
All Possible Combinations
▪ Some of them are infeasible
▪ 1,2,3 : (x1,x2,s1)=(9,4,24) (s2,s3)=(0,0)
▪ 1,2,4 : (x1,x2,s2)=(5,8,4) (s1,s3)=(0,0)
▪ 1,2,5 : (x1,x2,s3)=(7.5,7,-4,5) (s1,s2)=(0,0)
▪ 1,3,4 : (x1,s1,s2)=(13,48,-4) (x2,s3)=(0,0)
▪ 1,3,5 : (x1,s1,s3)=(11,56,6) (x2,s2)=(0,0)
▪ 1,4,5 : (x1,s2,s3)=(25,-28,-36) (x2,s1)=(0,0)
▪ 2,3,4 : (x2,s1,s2)=(13,-30,9) (x1,s3)=(0,0)
▪ 2,3,5 : (x2,s1,s3)=(22,-120,-27) (x1,s2)=(0,0)
▪ 2,4,5 : (x2,s2,s3)=(10,12,9) (x1,s1)=(0,0)
▪ 3,4,5 : (s1,s2,s3) = (100,22,39) (x1,x2)=(0,0)
10
Management Science Linear Programming IV
Convert into the Matrix Form
4 x1 + 10 x2 + s1 = 100
2 x1 + x2 + s2 = 22 AX=b
3x1 + 3x2 + s3 = 39
x1
4 10 1 0 0 x2 100
2 1 0 1 0 s1 = 22
3 3 0 0 1 s 39
2
s
3
11
Management Science Linear Programming IV
Step 1. Draw Simplex Table
𝒄𝒋 60 50 0 0 0
𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝒔𝟏 0 4 10 1 0 0 100
𝒔𝟐 0 2 1 0 1 0 22
𝒔𝟑 0 3 3 0 0 1 39
𝒁𝒋 0 0 0 0 0 0
𝒁𝒋 − 𝒄𝒋 -60 -50 0 0 0
(0, 0, 0) * (4, 2, 3) = 0*4+0*2+0*3=0
Initialization: Choose (x1,x2) = (0,0) to be the initial Corner-Point Feasible solution (CPF)
Is it optimal? Since increasing non-basic variable can increase Z, it’s not optimal.
Then move to the edging line on either x1 or x2.
Should we increase x1 or x2?
12
Management Science Linear Programming IV
Step 2. Select Basic Variable
𝒄𝒋 60 50 0 0 0
𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝒔𝟏 0 4 10 1 0 0 100 25
𝒔𝟐 0 2 1 0 1 0 22 11
𝒔𝟑 0 3 3 0 0 1 39 13
𝒁𝒋 0 0 0 0 0 0
𝒁𝒋 − 𝒄𝒋 -60 -50 0 0 0
1. Select the smallest 𝑍𝑗 − 𝑐𝑗 → 𝑥1 (−60)
2. Select the smallest ratio (𝑅𝐻𝑆/𝑥1 ) → 𝑠2 (11)
3. Therefore, 𝑠2 will become the basic variable
13
Management Science Linear Programming IV
Step 3. Row Operation
𝒄𝒋 60 50 0 0 0
𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝒔𝟏 0 4 10 1 0 0 100 25
𝒔𝟐 0 2 1 0 1 0 22 11
𝒔𝟑 0 3 3 0 0 1 39 13
𝒁𝒋 0 0 0 0 0 0
𝒁𝒋 − 𝒄𝒋 -60 -50 0 0 0
Now, we will make 𝑥1 column as 0 by using 𝑠2 row
14
Management Science Linear Programming IV
Step 3. Row Operation
𝒄𝒋 60 50 0 0 0
𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝒔𝟏 0 4 10 1 0 0 100
𝒔𝟐 0 1 1/2 0 1/2 0 11
𝒔𝟑 0 3 3 0 0 1 39
𝒁𝒋
𝒁𝒋 − 𝒄𝒋
1. Make (𝑠2 , 𝑥1 ) value as 1 (How? Divide 𝑠2 row by 2)
15
Management Science Linear Programming IV
Step 3. Row Operation
𝒄𝒋 60 50 0 0 0
𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝒔𝟏 0 0 8 1 -2 0 56
𝒔𝟐 0 1 1/2 0 1/2 0 11
𝒔𝟑 0 0 3/2 0 -3/2 1 6
𝒁𝒋
𝒁𝒋 − 𝒄𝒋
2. Make all other values in 𝑥1 column by doing row-wise calculation using 𝑠2 row
16
Management Science Linear Programming IV
Step 3. Row Operation
𝒄𝒋 60 50 0 0 0
𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝒔𝟏 0 0 8 1 -2 0 56
𝒙𝟏 60 1 1/2 0 1/2 0 11
𝒔𝟑 0 0 3/2 0 -3/2 1 6
𝒁𝒋 60 40 0 30 0 660
𝒁𝒋 − 𝒄𝒋 0 -10 0 30 0
3. Replace 𝑠2 → 𝑥1
4. Calculate 𝑍𝑗 and 𝑍𝑗 − 𝑐𝑗
17
Management Science Linear Programming IV
Step 3. Row Operation
𝒄𝒋 60 50 0 0 0
𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝒔𝟏 0 0 8 1 -2 0 56
𝒙𝟏 60 1 1/2 0 1/2 0 11
𝒔𝟑 0 0 3/2 0 -3/2 1 6
𝒁𝒋 60 40 0 30 0 660
𝒁𝒋 − 𝒄𝒋 0 -10 0 30 0
Currently, this Simplex table is saying that solution is (𝑥1 = 11, 𝑥2 = 0, 𝑠1 = 56, 𝑠2 = 0, 𝑠3 =
5). Is this optimal?
No.
How can we know that?
See 𝑍𝑗 − 𝑐𝑗 . There still exists negative value (-10). It means that we can get the better
solution by increasing 𝑥2 .
18
Management Science Linear Programming IV
Step 4. Repeat Step 2,3
𝒄𝒋 60 50 0 0 0
𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝒔𝟏 0 0 8 1 -2 0 56 7
𝒙𝟏 60 1 1/2 0 1/2 0 11 22
𝒔𝟑 0 0 3/2 0 -3/2 1 6 4
𝒁𝒋 60 40 0 30 0 660
𝒁𝒋 − 𝒄𝒋 0 -10 0 30 0
1. Select the smallest 𝑍𝑗 − 𝑐𝑗 → 𝑥2 (−10)
2. Select the smallest ratio (𝑅𝐻𝑆/𝑥2 ) → 𝑠3 (4)
3. Therefore, 𝑠3 will becomes the basic variable
19
Management Science Linear Programming IV
Step 4. Repeat Step 2,3
𝒄𝒋 60 50 0 0 0
𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝒔𝟏 0 0 8 1 -2 0 56 7
𝒙𝟏 60 1 1/2 0 1/2 0 11 22
𝒔𝟑 0 0 3/2 0 -3/2 1 6 4
𝒁𝒋 60 40 0 30 0 660
𝒁𝒋 − 𝒄𝒋 0 -10 0 30 0
Now, we will make 𝑥2 column as 0 by using 𝑠3 row
20
Management Science Linear Programming IV
Step 4. Repeat Step 2,3
𝒄𝒋 60 50 0 0 0
𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝒔𝟏 0 0 8 1 -2 0 56
𝒙𝟏 60 1 1/2 0 1/2 0 11
𝒔𝟑 0 0 1 0 -1 2/3 4
𝒁𝒋
𝒁𝒋 − 𝒄𝒋
1. Make (𝑠3 , 𝑥2 ) value as 1 (How? Divide 𝑠3 row by 3/2)
21
Management Science Linear Programming IV
Step 4. Repeat Step 2,3
𝒄𝒋 60 50 0 0 0
𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝒔𝟏 0 0 0 1 6 -16/3 24
𝒙𝟏 60 1 0 0 1 -1/3 9
𝒔𝟑 0 0 1 0 -1 2/3 4
𝒁𝒋
𝒁𝒋 − 𝒄𝒋
2. Make all other values in 𝑥2 column by doing row-wise calculation using 𝑠3 row
22
Management Science Linear Programming IV
Step 4. Repeat Step 2,3
𝒄𝒋 60 50 0 0 0
𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝒔𝟏 0 0 0 1 6 -16/3 24
𝒙𝟏 60 1 0 0 1 -1/3 9
𝒙𝟐 50 0 1 0 -1 2/3 4
𝒁𝒋 60 50 0 10 40/3 740
𝒁𝒋 − 𝒄𝒋 0 0 0 10 40/3
3. Replace 𝑠3 → 𝑥2
4. Calculate 𝑍𝑗 and 𝑍𝑗 − 𝑐𝑗
23
Management Science Linear Programming IV
Step 4. Repeat Step 2,3
𝒄𝒋 60 50 0 0 0
𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 RHS Ratio
𝒔𝟏 0 0 0 1 6 -16/3 24
𝒙𝟏 60 1 0 0 1 -1/3 9
𝒙𝟐 50 0 1 0 -1 2/3 4
𝒁𝒋 60 50 0 10 40/3 740
𝒁𝒋 − 𝒄𝒋 0 0 0 10 40/3
Currently, this Simplex table is saying that solution is (𝑥1 = 9, 𝑥2 = 4, 𝑠1 = 24, 𝑠2 = 0, 𝑠3 = 0).
Is this optimal?
Yes.
How can we know that?
See 𝑍𝑗 − 𝑐𝑗 . There still exists no negative value.
The optimal 𝑍 = 740
24
Management Science Linear Programming IV
Example
▪ Solve following maximization problem with Simplex Method
Maximize Z = $40x1 + $50x2
subject to: 1x1 + 2x2 40
4x2 + 3x2 120
x1, x2 0
▪ (Remind) Answer is 𝑥1 = 24, 𝑥2 = 8
25
Management Science Linear Programming IV
Q&A
26
