Scribd
Upload
9 views4 pages

Chapter4 Part3 DONE

The document outlines the steps of solving a standard maximization problem using the Simplex method, including converting inequalities to equalities, creating an initial tableau, performing row operations, and determining the optimal solution. It provides examples of linear programming problems and their solutions using the Simplex method. Additionally, it includes practice problems for the reader to solve using the same method.

Uploaded by

Lena A. Rahim
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
9 views4 pages

Chapter4 Part3 DONE

The document outlines the steps of solving a standard maximization problem using the Simplex method, including converting inequalities to equalities, creating an initial tableau, performing row operations, and determining the optimal solution. It provides examples of linear programming problems and their solutions using the Simplex method. Additionally, it includes practice problems for the reader to solve using the same method.

Uploaded by

Lena A. Rahim
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

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

You might also like