SIMPLEX METHOD
- Is appropriate when numerous variables and
constraints are presented.
- It involves repetitive process of finding the optimal
solution to a problem, either maximize profit or
minimize cost.
Developed by George B. Dantzig of Stanford
University in 1947 while on assignment with the U.S.
Department of the air force.
Basic Steps in Simplex Method
1. Construct the Objective function
2. Convert explicit constraints from inequality to an
equality
3. Prepare the simplex tableau and compute for the
values of Cj, Zj, and Cj-Zj
4. Check if the simplex tableau needs to be improved
5. Determine the incoming column and the outgoing
row.
6. Improve the table and repeat step 3
contribution per unit of a product.
Zj are the amount of profit that will be
reduced if
one unit of any variable is added to
the mix.
Cj – Zj is the difference between the
contribution margin and the expected
reduction of one unit of a variable
Slack variable - is a mathematical
representation of surplus resources.
- it represent the unused resources
needed to fill the gap between the left
and the right element of the inequalities.
Artificial variable – prevent the slack
variable from becoming a zero and
prevent an equality constraint from
resulting in a constant zero.
The coefficient value is equal to the
power of 10, raised to the highest
coefficient of the variables in the objective
function or constraints
Maximization Problem:
To convert the constraints to
equations, the procedures are:
1. Add a slack variable if the symbol used
is ≤.
2. Add a slack variable if the symbol used
is =.
3. Multiply the equation by negative 1 and
add a slack variable if the symbol sign is
≥.
Minimization Problem:
To convert the constraints to
equations, the procedures are:
1. Add a slack variable if the symbol used
is ≤.
2. Add an artificial variable if the symbol
used is =.
3. Subtract a slack variable and add an
artificial variable if the symbol sign is ≥.
≥ 80 Minimization Problem:
5x + 5y ≤ Example:
200 Min Cost : 100x + 40y
x + y = 20 Constraint: 10x + 20y ≥ 80
5x + 5y ≤ 200
convert into: x + y = 20
Max Profit :
100x+40y+S1+S2+S3 Convert into:
Constraint: Min Cost: 100x+40y-
-10x – 20y + S1 = - S1+S2+10A1 +10A2
80 Constraint:
5x + 5y + S2 = 10x + 20y - S1 + A1 = 80
200 5x + 5y + S2 = 200
x + y + S3 = 20 x + y + A2 = 20
Izzy Furniture Shop manufactures tables and
chairs. All of its tables and chairs pass through
two departments, namely Department 1 and
Department 2. In one production period, Dept. 1
and Dept. 2 have total available hours of 120
and 96, respectively. The production of one table
requires 3 hours in Dept.1 and 6 hours in Dept.
2. Similarly producing one chair requires 6 hours
in Dept. 1 and 3 hours in Dept. 2. The
contribution margin or profit of one table is
P30.00 and that of a chair is P24.00.
Required: Using simplex method, determine
the optimal solution.
Solution:
Step 2
Step 1
Improved:
Max Profit: 30x + 24y
Max Profit: 30x + 24y + S1 + S2
Subject to: 3x + 6y ≤ 120
6x + 3y ≤ 96 Subject to: 3x + 6y + S1 = 120
x, y > 0 6x + 3y + S2 = 196
Solution: Step 3 Prepare the simplex tableau and compute for the values of Cj, Zj, and Cj-Zj
Cj 30 24 0 0
Solution
Product quantity x y S1 S2
0 S1 120 3 6 1 0
0 S2 96 6 3 0 1
Zj 0 0 0 0
Cj - Z j 30 24 0 0
optimum column/incoming
column
Step 4 Check if the simplex tableau needs to be improved
Step 5 Determine the incoming column and the outgoing row
Solution:
The optimum Column/incoming column is the column
that has the highest positive value in the Cj - Zj row.
Pivot value is the intersectional element in the incoming
column and the corresponding row.
Outgoing row shall then be determine by dividing the
value in the quantity column with the pivot value in the
incoming column. Outgoing variable is the variable with
the lowest value.
Solution: Step 5 Determine the incoming column and the outgoing row
Product Solution quantity Pivot Value Quotient
S1 120 / 3 = 40
S2 96 / 6 = 16
outgoing variable
Old Value of the Pivot Value of Values of
outgoing variable Outgoing Variable Incoming Variable
96 / 6 = 16
6 / 6 = 1
3 / 6 = 0.5
0 / 6 = 0
1 / 6 = 0.16667
Solution: Step 5 Determine the incoming column and the outgoing row
Old value Pivot Value New Values New Values
of of of of
Retained Retained Incoming Retained
Variable Variable Variable Product Variable
120 - 3 x 16 = 48 72
3 - 3 x 1 = 3 0
6 - 3 x 0.5 = 1.5 4.5
1 - 3 x 0 = 0 1
0 - 3 x 0.1667 = 0.5001 -0.5001
Solution: Step 6 Improve the table and repeat step 3
Cj 30 24 0 0
Solution
Product quantity x y S1 S2
30 x 16 1 .5 0 .1667
0 S2 72 0 4.5 1 .5
Zj 480 30 15 0 5
Cj - Z j 0 9 0 -5
optimum column/incoming
column
Step 4 Check if the simplex tableau needs to be improved
Step 5 Determine the incoming column and the outgoing row
Solution: Step 5 Determine the incoming column and the outgoing row
Product Solution quantity Pivot Value Quotient
x 16 / .5 = 32
S2 72 / 4.5 = 16
outgoing variable
Old Value of the Pivot Value of Values of
outgoing variable Outgoing Variable Incoming Variable
72 / 4.5 = 16
0 / 4.5 = 0
4.5 / 4.5 = 1
1 / 4.5 = 0.2222
.5 / 4.5 = 0.1111
Solution: Step 5 Determine the incoming column and the outgoing row
Old value Pivot Value New Values New Values
of of of of
Retained Retained Incoming Retained
Variable Variable Variable Product Variable
16 - .5 x 16 = 8 8
1 - .5 x 0 = 0 1
.5 - .5 x 1 = 0.5 0
0 - .5 x 0.2222 = 0.1111 -0.111
0.1667 - .5 x 0.1111 = 0.0555 0.111
Solution: Step 6 Improve the table and repeat step 3 if needed
Cj 30 24 0 0
Solution
Product quantity x y S1 S2
30 x 8 1 0 -.1111 .111
24 y 16 0 1 .2222 .111
Zj 624 30 24 2 5.997
Cj - Z j 0 0 -2 -5.997