Instructional Goals:
At the end of the lesson, the students must
be able to:
• Discuss the logic of simplex method;
• Create a simplex table and describe its
components; and
• Solve problems using the simplex method.
What is Simplex
Method?
Simplex Method
• First developed in 1947 by Dr. George B.
Dantzig together with US Department of
the Airforce members.
• It is an iterative technique for solving
more unknown variables that are
geometrically difficult to plot in a graph.
Simplex Method
• Search of solution starts at the corner
where all the unknowns are in zeros
and then goes around the area from
one corner to another.
Set up the Initial Tableau.
Negative values in the last row? Solution is optimal. End
Identify the pivot column.
Positive values in the test No finite solution is
End
ratios? possible
Identify the pivotal row.
Prepare new tableau.
Steps in Linear Programming Model
Simplex Method
1. Set the LP problem by determining the unknown
variables, objective function and constraints.
2. Add the necessary slack variables.
3. Prepare the initial Tableau.
4. Assess the tableau if the solution is already maximal.
Otherwise, proceed to step 5.
5. Calculate another simplex tableau: choose the pivot
columns and find the pivot row and pivot entry.
6. Proceed to step 4.
Terms to remember:
• Iteration – refers to sequence of steps or row
operations in order to move one feasible solution to
another.
• Simplex Tableau – a table that keeps track of the
calculations for the simplex method.
• Right-hand-side (RHS) – is at the rightmost column of a
simplex tableau that indicates the capacities or
requirements.
• Basic Variables – variables considered in a basic
solution.
Terms to remember:
• Pivot column – in a maximization problem it should
have the lowest negative value in the last row
• Pivot row – a row in the simplex tableau that contains
the basic variable that will ho out of the solution.
• Intersectional Elements (IE) – elements in the pivot
column.
• Test Ratio – calculated by dividing the RHS by the IE. It
always yield a positive
Terms to remember:
• Pivot – is the element in the simplex tableau located in
the pivot row and pivot column.
• Pivoting – is the process of moving from one simplex
tableau to the next.
• Slack variables – these are variables used to represent
the amount which the decision variables fall short
A pottery company employs skilled artisans to produce clay
bowls and mugs with authentic design and colors. The two
primary resources used by the company are special pottery
clay and skilled labor. Given these limited resources, the
company desires to know how many bowls and mugs to
produce each day in order to maximize profit. The two
products have the following resource requirements for
production and profit per item produced.
RESOURCE REQUIREMENT
There are 40 hours of
PRODUCT Labor (Hr/ unit) Clay (lb/ unit) Profit
labor and 120 pounds
Bowl 1 4 40
of clay available each
Mug 2 3 50
day for production.
Step 1. Identify the objective function and constraints.
Maximize P = 40 x + 50y
Subject to: (Constraints)
1x + 2y ≤ 40 (hours of labor constraint)
4x + 3y ≤ 120 (available clay constraint)
x ≥ 0 (non – negativity constraint)
y ≥ 0 (non – negativity constraint)
Step 2. Covert the LP problem to linear equations.
To make the listed constraints into an equation, add
Sn as the slack variables:
1x + 2y + S1 = 40 1st constraint
4x + 3y + S2 = 120 2nd constraint
-40x – 50y + P = 0 Objective Function
Step 3. Setup the initial tableau.
• Get the numerical coefficients of the equations identified
in step 2.
BV x y S1 S2 P RHS
S1 1 2 1 0 0 40 1st Constraint
S2 4 3 0 1 0 120 2nd Constraint
P -40 -50 0 0 1 0 Objective Function
Step 4. Select the pivot column that has the most negative
entry at the bottom row.
BV x y S1 S2 P RHS
S1 1 2 1 0 0 40 1st Constraint
S2 4 3 0 1 0 120 2nd Constraint
P -40 -50 0 0 1 0 Objective Function
PIVOT COLUMN
Step 5. Apply the test ration (RHS ÷ IE). The row with the
smallest positive quotient is the pivot row.
BV x y S1 S2 P RHS Test Ratio
S1 1 2 1 0 0 40 40 ÷ 2 = 20
S2 4 3 0 1 0 120 120 ÷ 3 = 40
P -40 -50 0 0 1 0
PIVOT COLUMN
Step 5. Apply the test ration (RHS ÷ IE). The row with the
smallest positive quotient is the pivot row.
BV x y S1 S2 P RHS Test Ratio
S1 1 2 1 0 0 40 40 ÷ 2 = 20
S2 4 3 0 1 0 120 120 ÷ 3 = 40
P -40 -50 0 0 1 0
PIVOT PIVOT COLUMN PIVOT ROW
LEAVING VARIABLE ENTERING VARIABLE
BV x y S1 S2 P RHS
S1 1 2 1 0 0 40
S2 4 3 0 1 0 120
P -40 -50 0 0 1 0
INTERSECTIONAL ELEMENTS
Step 6. Compute the entries in the replacing rows by
dividing all the values by the pivot.
BV x y S1 S2 P RHS
S1 1÷2 2÷2 1÷2 0÷2 0÷2 40÷2
S2 4 3 0 1 0 120
P -40 -50 0 0 1 0
Step 6. Compute the entries in the replacing rows by
dividing all the values by the pivot.
BV x y S1 S2 P RHS
y 0.5 1 0.5 0 0 20
S2 4 3 0 1 0 120
P -40 -50 0 0 1 0
Step 7. Compute the new entries for the rest of the rows.
Remaining row = Previous row – (IE x Replacing rows)
BV x y S1 S2 P RHS
y 0.5 1 0.5 0 0 20
S2 4 - 3(0.5) 3 – 3(1) 0 - 3(0.5) 1 – 3(0) 0 – 3(0) 120 –
3(20)
P -40 + -50 + 0+ 0 + 50(0) 1 + 50(0) 0+
50(0.5) 50(1) 50(0.5) 50(20)
Step 7. Compute the new entries for the rest of the rows.
Remaining row = Previous row – (IE x Replacing rows)
BV x y S1 S2 P RHS
y 0.5 1 0.5 0 0 20
S2 2.5 0 -1.5 1 0 60
P -15 0 25 0 1 1000
Since there is a negative value in the last row, this means that the process has to return to step 4.
Step 4 – 5.
BV x y S1 S2 P RHS Test Ratio
y 0.5 1 0.5 0 0 20 20÷0.5
S2 2.5 0 -1.5 1 0 60 60÷2.5
P -15 0 25 0 1 1000
Step 4 – 5.
BV x y S1 S2 P RHS Test Ratio
y 0.5 1 0.5 0 0 20 40
S2 2.5 0 -1.5 1 0 60 24
P -15 0 25 0 1 1000
Step 6 – 7.
BV x y S1 S2 P RHS
y 0.5 1 0.5 0 0 20
S2 2.5÷2.5 0÷2.5 -1.5÷2.5 1÷2.5 0÷2.5 60÷2.5
P -15 0 25 0 1 1000
Step 6 – 7.
BV x y S1 S2 P RHS
y 0.5 1 0.5 0 0 20
x 1 0 -0.6 0.4 0 24
P -15 0 25 0 1 1000
Step 6 – 7.
BV x y S1 S2 P RHS
y 0.5 – 1– 0.5 – 0– 0– 20 –
0.5(1) 0.5(0) 0.5(-0.6) 0.5(0.4) 0.5(0) 0.5(24)
x 1 0 -0.6 0.4 0 24
P -15 + 0 + 15(0) 25 + 15(- 0+ 1 + 15(0) 1000 +
15(1) 0.6) 15(0.4) 15(24)
Step 6 – 7.
BV x y S1 S2 P RHS
y 0 1 0.8 0.2 0 8
x 1 0 -0.6 0.4 0 24
P 0 0 16 6 1 1, 360
Since there is no negative elements, the last row is the solution.
Thus, we need to produce 24 bowls and 8 mugs to get a maximize profit of Php 1 360.
Take note:
For Minimization problem,
instead of getting the lowest
negative, we take the highest
positive element.
Activity:
The same problem in the
previous activity, answer it
using the Simplex Method.
