SIMPLEX METHOD: Standard Maximization Problem
Step of solving linear programming problem using Simplex method:
Step 1: Step 3:
Step 2:
Convert Use elementary
Convert the Step 4:
inequality to row operation,
standard form
equality and Gauss-Jordan Determine the
above into First
insert slack Elimination to optimal solution
Initial Tableau
variable into each obtain improved
Table
constraint solution
Example 1
Use simplex method to solve the given Linear Programming problem.
Max 𝑍 = 4𝑥₁ + 6𝑥₂
Subject to −𝑥₁ + 𝑥₂ ≤ 11
𝑥₁ + 𝑥₂ ≤ 27
2𝑥₁ + 5𝑥₂ ≤ 90
𝑥1 , 𝑥2 ≥ 0
Solution:
Step 1: Convert inequality to equality and insert slack variable into each constraint
𝑍 = 4𝑥₁ + 6𝑥₂ 𝑍 − 4𝑥1 − 6𝑥2 = 0
−𝑥₁ + 𝑥₂ ≤ 11 −𝑥1 + 𝑥2 + 𝑆1 = 11
𝑥₁ + 𝑥₂ ≤ 27 𝑥1 + 𝑥2 + 𝑆2 = 27
2𝑥₁ + 5𝑥₂ ≤ 90 2 𝑥1 + 5𝑥2 + 𝑆3 = 90
Step 2: Convert the standard form above into First Initial Tableau Table
ROW OPERATION 𝑍 𝑥1 𝑥2 𝑆1 𝑆2 𝑆3 b RATIO
A 1 −4 −𝟔 0 0 0 0
B 0 −1 1 1 0 0 11 11
C 0 1 1 0 1 0 27 27
D 0 2 5 0 0 1 90 18
1- Choose the lowest negative value from Row A 𝒙𝟐 is called as PIVOT COLUMN
2- Find the RATIO for each row : Ratio = b / PIVOT COLUMN
3- Choose the lowest positive value from RATIO Row B is called as PIVOT ROW
4- The DARK BLUE with WHITE 1 is called as PIVOT CELL
5- Since the PIVOT CELL value is already 1, copy the whole row B in the new table
Step 3: Use elementary row operation, Gauss-Jordan Elimination to obtain improved solution
ROW OPERATION 𝑍 𝑥1 𝒙𝟐 𝑆1 𝑆2 𝑆3 b RATIO
A’ 6B’ + A 1 −10 0 6 0 0 66
B’ 0 −1 1 1 0 0 11 −
C’ -1B’ + C 0 2 0 −1 1 0 16 8
D’ -5B’ + D 0 7 0 −5 0 1 35 5
1- Choose the lowest negative value from Row A 𝒙𝟏 is called as PIVOT COLUMN
2- Find the RATIO for each row : Ratio = b / PIVOT COLUMN
3- Choose the lowest positive value from RATIO Row D is called as PIVOT ROW
4- The DARK BLUE with WHITE 7 is called as PIVOT CELL
5- Since the PIVOT CELL value is 7 Row D divide with 7
ROW OPERATION 𝑍 𝑥1 𝒙𝟐 𝑆1 𝑆2 𝑆3 b
8 10
A’’ 10D’’ + A’ 1 0 0 − 0 116 𝒁
7 7
2 1
B’’ 1D’’ + B’ 0 0 1 0 16 𝒙𝟐
7 7
25 2
C’’ -2D’’ + C’ 0 0 0 − 1 − 25 𝑺𝟐
7 7
5 1
D’’ D’ 7 0 1 0 − 0 5 𝒙𝟏
7 7
Step 4: Determine the optimal solution
THE OPTIMAL SOLUTION IS;
(𝒁, 𝒙𝟏 , 𝒙𝟐 , 𝑺𝟏 , 𝑺𝟐 , 𝑺𝟑 ) = (𝟏𝟏𝟔, 𝟓, 𝟏𝟔, 𝟎, 𝟐𝟓, 𝟎)
CHECK: 𝒁 = 4𝒙𝟏 + 6𝒙𝟐 = 4(5) + 6(16) = 𝟏𝟏𝟔 (PROVEN)
Example 2
Use simplex method to solve the given linear programming problem
Max 𝑧 = 2𝑥₁ − 𝑥₂ + 2𝑥₃
Subject to 2𝑥₁ + 𝑥₂ ≤ 10
𝑥₁ + 2𝑥₂ − 2𝑥₃ ≤ 20
𝑥₂ + 2𝑥₃ ≤ 5
𝑥₁ , 𝑥₂ , 𝑥₃ ≥ 0
Solution:
Step 1: Convert inequality to equality and insert slack variable into each constraint
Step 2: Convert the standard form above into First Initial Tableau Table
ROW OPERATION 𝑍 𝑥1 𝑥2 𝑥3 𝑆1 𝑆2 𝑆3 RHS RATIO
Step 3: Use elementary row operation, Gauss -Jordan Elimination to obtain improved solution
ROW OPERATION 𝑍 𝑥1 𝑥2 𝑥3 𝑆1 𝑆2 𝑆3 RHS RATIO
Step 4: Determine the optimal solution
THE OPTIMAL SOLUTION IS;
(𝒁, 𝒙𝟏 , 𝒙𝟐 , 𝑺𝟏 , 𝑺𝟐 , 𝑺𝟑 ) = ( )
CHECK: 𝒁 = 2𝒙𝟏 − 𝒙𝟐 + 2𝒙𝟑 = 2( ) − ( ) + 2( ) (PROVEN)
TEST YOURSELF
Use Simplex Method to solve the given problem:
a. A manufacturer produces three types of plastic fixtures. The time required for moulding, trimming, and
packaging is given in table below. (Times are given in hours per dozen fixtures.). How many dozen of
each type of fixture should be produced to obtain a maximum profit?
Process Type A Type B Type C Total time available
Moulding 1 2 3/2 12,000
Trimming 2/3 2/3 1 4,600
Packaging ½ 1/3 1/2 2,400
Profit (RM) 11 16 15 -
b. The advertising alternatives for a company include television, radio, and newspaper advertisements.
The costs and estimates for audience coverage are given in a table.
Television Newspaper Radio
Cost per advertisement $ 2,000 $ 600 $ 300
Audience per advertisement 100,000 40,000 18,000
The local newspaper limits the number of weekly advertisements from a single company to ten.
Moreover, in order to balance the advertising among the three types of media, no more than half of the
total number of advertisements should occur on the radio, and at least 10% should occur on television.
The weekly advertising budget is $18,200. How many advertisements should be run in each of the three
types of media to maximize the total audience?
c. Solve the given linear programming problem
Max 𝑧 = 𝑥₁ − 𝑥₂ + 2𝑥₃
Subject to 2𝑥₁ + 2𝑥₂ ≤ 8
𝑥₃ ≤ 1
x₁, x₂, x₃ ≥ 0
d. Use simplex method to solve the given linear programming problem
Max 𝑧 = 2𝑥₁ − 𝑥₂ + 3𝑥₃
Subject to 𝑥₁ + 𝑥₂ + 𝑥₃ ≤ 59
2𝑥₁ + 3𝑥₃ ≤ 75
𝑥₂ + 6𝑥₃ ≤ 54
x₁, x₂, x₃ ≥ 0
