Linear Programming:

Simplex Method
Chapter
03
Guide questions in learning the topic:

1. What is the advantage of simplex method from graphical method?

2. What is slack variable, surplus variable and artificial variable?

3. What are the steps in solving a problem using linear programing – simplex method in
maximization problem?

4. What are the steps in solving a problem using linear programing – simplex method in
minimization problem?

5. What are the different elements of the simplex method tableau?

6. How to interpret solutions in simplex method?

SIMPLEX METHOD

The problems to be solved using simplex method is almost the same with those solved using graphical
method but you can solve more unknown variable is simplex method. Remember that the number of
unknown variables that can be represented and solved using graphical method is only two because
of the limitation in the cartesian coordinate plane where you can only have two variables. If the
number of unknown of variables that needs to be represented and solved exceeds by two (i.e., three
or more), then simplex method should be used.

All the constraints in simplex method are expressed as equation. The inequality constraints in the
graphical method will be converted to equations or in the standard form of linear programming
problem. Simplex method is a technique which begins with a feasible solution that is not yet optimal
and is improved until there is no further possible improvement.

Steps in solving maximization problems using Linear Programming – Simplex Method

1. Understand the problem and determine the objective of the problem and the decision that you
must make.
2. Assign decision variables and determine the constraints.
3. Formulate the objective function and constraint function by transcribing the information to
mathematical form.
4. Convert the objective function and constraint functions to equations in standard form.
5. Enter the coefficient of objective function and constraint functions in the initial simplex method
tableau solution.
6. Compute for Cj – Zj, if there is a positive value in the Cj – Zj row, do Step 7.
7. Improve the simplex method tableau:
a. Determine the pivot column
b. Determine the pivot row
c. Create the improved simplex method tableau
i. Improve the pivot row
ii. Improve the remaining row
iii. Compute for Cj – Zj
8. Repeat Step No. 7 if there is still a column with a positive value in the Cj – Zj. If there is no positive
value in the Cj – Zj, the optimal solution is obtained.
Illustration 01:
A tailor has 18 m2 of cotton, 20 m 2 of silk and 5 m2 of wool available. She can’t decide yet what kind
of dress to produce, a gown or a suit. Each gown requires 3 m2 of cotton, 2 m2 of silk and 1 m2 of wool
while each suit requires 2 m2 of cotton and 4 m2 of silk. If the selling price of a gown and a suit are
P1,200 and 1,600 respectively, haw many of each dress should the tailor produce to obtain the
maximum amount of sales?

Discussion:
1. Understand the problem and determine the objective of the problem and the decision that you
must make. In this problem, our objective to maximize the sales by getting the number of gown
and suit that should be produced and sold.

2. Assign decision variables and determine the constraints.

Since we do not know yet the number of units that we will sell, we can use some variable first to
represent the unknown amounts.

Let x1 as the number of gowns to be produced and sold

X2 as the number of suits to be produced and sold.

The constraints are the limitations presented in the problem that must be taken into
consideration. In this problem, the constraints are as follows:
a. The maximum number of available cottons is 18 m2
b. The maximum number of available silks is 20 m2
c. The maximum number of available wools is 5 m2
d. The number of gowns and suits to be produced and sold must not be less than 0 (non-
negativity constraint, which is also an implicit constraint that restricts all variables to be zero
or any positive amount only at all times).

3. Formulate the objective function and constraint function by transcribing the information to
mathematical form.

The objection function will be:

Maximize P = 1,200x1 + 1,600x2

Constraints:
3x1 + 2x2 ≤ 18 Cotton
2x1 + 4x2 ≤ 20 Silk
x1 ≤ 5 Wool
x1, x2 ≥ 0 Non-negativity

4. Convert the objective function and constraint functions to equations in standard form.

In the standard for of equation, all the terms with variables are on the left side of the equation
while all the constants are on the right side. Also, slack variables should be added to each
constraint inequalities with less-than-or-equal-to (≤) sign. Usually, the constraint for
maximization problems is the limitation on the scarce resources. The maximum amount of
available resources is being given and a ≤ inequality sign is used to represent the resources to be
used and the maximum amount of resources that can be used. The slack variable (si) represents
the amount of resources that will not be used in obtaining the optimal solution which should be
added to left-hand-side of the constraint function and we can now change the inequality sign to
equal sign. (i.e., the resources to be used in optimal solution plus the slack resources is equal to
the maximum amount of available resources). Slack variables which has a numerical coefficient
of zero is added also to the objective function to show that those variables are being used in the
solution.

Ch03: Linear Programming: Simplex Method 24

 Objective Function: P = 1,200x1 + 1,600x2
= 1,200 x1 + 1,600x2 + 0s1 + 0s2 + 0s3

Constraints:
3x1 + 2x2 ≤ 18 2x1 + 4x2 ≤ 20 x1 ≤ 5
3x1 + 2x2 + s1 = 18 2x1 + 4x2 + s2 = 20 x1 + s3 = 5

5. Create the initial simplex method tableau solution.

Simplex Method Tableau

Tableau 1

variables
Objective
Basic Cj 1,200 1,600 0 0 0
CB Function
Variables RHS x1 x2 s1 s2 s3
Constraint 0 s1 18 3 2 1 0 0
0 s2 20 2 4 0 1 0
Function
0 s3 5 1 0 0 0 1
Zj
Cj – Z j

6. Compute for the value Zj of each column by getting the sum of products of the coefficient in C j and
the coefficient in that column
Zj = (0)(18, 3, 2, 1, 0, 0) + (0)(20, 2, 4, 0, 1, 0) + (0)(5, 1, 0, 0, 0, 1)
= (0, 0, 0, 0, 0, 0) + (0, 0, 0, 0, 0, 0) + (0, 0, 0, 0, 0, 0)
= (0, 0, 0, 0, 0, 0)

Compute for the value of Cj – Zj.

Cj – Zj = (1,200, 1,600, 0, 0, 0) – (0, 0, 0, 0, 0)
= (1,200, 1,600, 0, 0, 0)

Tableau 1
Basic Cj 1,200 1,600 0 0 0
CB
Variables RHS x1 x2 s1 s2 s3
0 s1 18 3 2 1 0 0
0 s2 20 2 4 0 1 0
0 s3 5 1 0 0 0 1
Zj 0 0 0 0 0 0
Cj – Z j 1,200 1,600 0 0 0

7. Improve the simplex method tableau:

a. Determine the pivot column – The pivot column is the column with the largest positive
value of Cj – Zj.

By looking in the initial tableau above, we can say that the pivot column is column of
variable x2.

b. Determine the pivot row – The pivot row is the row with the lowest answer when the
value of RHS column is divided by the value in the pivot column.

R1 = 18 ÷ 2 = 9
R2 = 20 ÷ 4 = 5 The pivot row is R2
R3 = 5 ÷ 0 = Undefined

Ch03: Linear Programming: Simplex Method 25

 Tableau 1 Entering variable
Basic Cj 1,200 1,600 0 0 0
CB
Variables RHS x1 x2 s1 s2 s3
0 s1 18 3 2 1 0 0
Pivot Row 0 s2 20 2 4 0 1 0
0 s3 5 1 0 0 0 1
Zj 0 0 0 0 0 0
Cj – Z j 1,200 1,600 0 0 0
Leaving variable Pivot Column Pivot
Other important parts of the Simplex Method Tableau are the entering variable and
leaving variable. The entering variable is the variable of the pivot column which will
replace the leaving variable (the variable of the pivot row) during the improvement
process of the tableau.

c. Create the improved simplex method tableau

i. Improve the pivot row – Improvement of pivot row is done by dividing each
coefficient in the row with the coefficient in that row that intersects with the pivot
column.
Improved Row (Pivot) = Old Row Coefficient ÷ Pivot

To improve R2, each coefficient in the pivot row should be divided by 2

Improved Row (Pivot) = (20, 2, 4, 0, 1, 0) ÷ 4
= (5, ½, 1, 0, ¼, 0)

Tableau 2
Basic Cj 1,200 1,600 0 0 0
CB
Variables RHS x1 x2 s1 s2 s3
s1 R1
1,600 x2 5 ½ 1 0 ¼ 0 R2
s3 R3
Zj
Cj – Z j
The entering variable already replaced the leaving variable

ii. Improve the remaining row – Improvement of other rows is computed by

subtracting from each coefficient of the row in the previous table the product of
the coefficient of the row in the previous table that intersects the pivot column
and the improved pivot row coefficients.

Improved Row (Other) = Old Row Coefficient – Intersectional Coefficient x Improved Pivot Row
Coefficient

Improved R1 = (18, 3, 2, 1, 0, 0) – 2 (5, ½, 1, 0, ¼, 0)

= (18, 3, 2, 1, 0, 0) – (10, 1, 2, 0, ½, 0)
= (8, 2, 0, 1, -½, 0)

Improved R3 = (5, 1, 0, 0, 0, 1) – 0 (5, ½, 1, 0, ¼, 0)

= (5, 1, 0, 0, 0, 1) – (0, 0, 0, 0, 0, 0)
= (5, 1, 0, 0, 0, 1)

Tableau 2
Basic Cj 1,200 1,600 0 0 0
CB
Variables RHS x1 x2 s1 s2 s3
0 s1 8 2 0 1 -½ 0 R1
1,600 x2 5 ½ 1 0 ¼ 0 R2
0 s3 5 1 0 0 0 1 R3
Zj
Cj – Z j

Ch03: Linear Programming: Simplex Method 26

 iii. Compute for Zj and Cj – Zj
Zj = (0)(8, 2, 0, 1, -½, 0) + (1,600)(5, ½, 1, 0, ¼, 0) + (0)(5, 1, 0, 0, 0, 1)
= (0, 0, 0, 0, 0, 0) + (8,000, 800, 1,600, 0, 400, 0) + (0, 0, 0, 0, 0, 0)
= (8,000, 800, 1,600, 0, 400, 0)

Compute for the value of Cj – Zj.

Cj – Zj = (1,200, 1,600, 0, 0, 0) – (800, 1,600, 0, 400, 0)
= (400, 0, 0, -400, 0)

Tableau 2
Basic Cj 1,200 1,600 0 0 0
CB
Variables RHS x1 x2 s1 s2 s3
0 s1 8 2 0 1 -½ 0 R1
1,600 x2 5 ½ 1 0 ¼ 0 R2
0 s3 5 1 0 0 0 1 R3
Zj 8,000 800 1,600 0 400 0
Cj – Z j 400 0 0 -400 0

Since there is still a positive coefficient in the improved tableau (Tableau 2), let’s
do Step 7 again.

Improvement to Tableau 3
a. Determine the pivot column – By looking in the initial tableau above, we can say that the
pivot column is column of variable x1.

b. Determine the pivot row

R1 = 8 ÷ 2 = 4 The pivot row is R1
R2 = 5 ÷ ½ = 10
R3 = 5 ÷ 1 = 5

c. Create the improved simplex method tableau

i. Improve the pivot row
Improved Row (Pivot) = (8, 2, 0, 1, -½, 0) ÷ 2
= (4, 1, 0, ½, -¼, 0)
Table 2
Basic Cj 1,200 1,600 0 0 0
CB
Variables RHS x1 x2 s1 s2 s3
1,200 x1 4 1 0 ½ -¼ 0 R1
1,600 x2 R2
s3 R3
Zj
Cj – Z j

ii. Improve the remaining row

Improved R2 = (5, ½, 1, 0, ¼, 0) – ½ (4, 1, 0, ½, -¼, 0)
= (5, ½, 1, 0, ¼, 0) – (2, ½, 0, ¼, -1⁄8 , 0)
= (3, 0, 1, -¼, 3⁄8 , 0)

Improved R3 = (5, 1, 0, 0, 0, 1) – 1 (4, 1, 0, ½, -¼, 0)

= (5, 1, 0, 0, 0, 1) – (4, 1, 0, ½, -¼, 0)
= (1, 0, 0, -½, ¼, 1)

Also, the entering variable (1,200 and x1) should replace the leaving variable (0,
s1).

Ch03: Linear Programming: Simplex Method 27

 Tableau 3
Basic Cj 1,200 1,600 0 0 0
CB
Variables RHS x1 x2 s1 s2 s3
1,200 x1 4 1 0 ½ -¼ 0 R1
3⁄
1,600 x2 3 0 1 -¼ 8 0 R2
0 s3 1 0 0 -½ ¼ 1 R3
Zj
Cj – Z j

iii. Compute for Zj and Cj – Zj

Zj = (1,200) (4, 1, 0, ½, -¼, 0) + (1,600)(3, 0, 1, -¼, 3⁄8 , 0)+ (0)(1, 0, 0, -½, ¼, 1)
= (4,800, 1,200, 0, 600, -300, 0)+(4,800, 0, 1,600, -400, 600, 0)+(0,0,0,0,0,0)
= (9,600, 1,200, 1,600, 200, 300, 0)

Compute for the value of Cj – Zj.

Cj – Zj = (1,200, 1,600, 0, 0, 0) – (1,200, 1,600, 200, 300, 0)
= (0, 0, -200, -300, 0)

Tableau 3
Basic Cj 1,200 1,600 0 0 0
CB
Variables RHS x1 x2 s1 s2 s3
1,200 x1 4 1 0 ½ -¼ 0 R1
3⁄
1,600 x2 3 0 1 -¼ 8 0 R2
0 s3 1 0 0 -½ ¼ 1 R3
Zj 9,600 1,200 1,600 200 300 0
Cj – Z j 0 0 -200 -300 0

After improving Tableau 2 and coming up with Tableau 3, there are no more
positive coefficients in the Cj – Zj, thus, the simplex method tableau 3 is already
the optimal solution.

The solution for the linear programming solution is found in the RHS column.

Decision:
x1 = 4 gowns
x2 = 3 suits
P = P9,600.00

Let us check for the maximum amount of profit that can be obtained by the optimal solution
Objective Function: P = 1,200x1 + 1,600x2
= 1,200(4) + 1,600(3)
= 4,800 + 4,800
= 9,600

Also, let us check if there are any slack resources.

Cotton Silk Wool
Total available resources 18 20 5
Allotted for gown
4x3 (12)
4x2 ( 8)
4x1 (4)
Allotted for suit
3x2 ( 6)
3x4 (12)
Slack resources 0 0 1
Same with the table 3, only s3 has a slack value which is 1. All other slack variables is zero.

Ch03: Linear Programming: Simplex Method 28

Steps in solving maximization/minimization problems using Linear Programming – Simplex Method
(Minimization Problem)

The steps in minimization problems are just the same with maximization. There is additional rule in
converting the objective function and constraint functions in standard form.

The following rules are to be observed:

In converting inequality constraints with greater-than-or-equal-to (≥) sign, a surplus variable should
be subtracted, and an artificial variable should be added. The surplus variable represents the
additional resources used in production that exceeds the minimum possible amount which should be
subtracted to the left-hand-side of the constraint function so we can change the inequality sign to
equal sign (I.e., the resources to be used in optimal solution less the surplus resources is equal to the
minimum amount of resources to be used).

Also, whenever an artificial variable is used, the same artificial variable should be included to the
objective function as well. The coefficient of which should be +M if it is a minimization problem and
-M if it is a maximization problem. “M” is a very large value of number.

Artificial variables and rules for M are also added to constraint functions with equal (=) sign.

In determining if the simplex method tableau already contains the optimal solution, the C j – Zj. must
be greater-than-or-equal-to zero (Cj – Zj ≥ 0). It means that the simplex method tableau must still be
improved if there is still a negative value on it

Illustration 2:
A leading soap manufacturing company produces two variants of soap. It uses three kinds of
chemicals in its production. The total unit cost is P80 and P50 for Soap#1 and Soap#2, respectively.
The production of the soaps depends on the availability of the chemicals used producing the soap.
The mixture in producing the soaps are shown below:
Resource Requirement Minimum
Chemicals
Soap#1 Soap#2 requirement
Chemical 1 3g 1g 6g
Chemical 2 1g 1g 4g
Chemical 3 2g 6g 12 g

The company wants to know the number of Soap#1 and Soap#2 that must be produced that will also
attain the minimum cost possible,

Discussion:
1. Understand the problem and determine the objective of the problem and the decision that you
must make. In this problem, our objective to minimize the cost by getting the number of soap#1
and soap#2 that should be produced.

2. Assign decision variables and determine the constraints.

Since we do not know yet the number of units that we will produce, we can use some variable
first to represent the unknown amounts.

Let x1 as the number of soap#1 to be produced and sold

X2 as the number of soap#2 to be produced and sold.

The constraints are the limitations presented in the problem that must be taken into
consideration. In this problem, the constraints are as follows:
a. The minimum number of chemical 1 to be used is 6 g.
b. The minimum number of chemical 2 to be used is 4 g.
c. The minimum number of chemical 3 to be used is 12 g.
d. The number of soap#1 and soap#2 to be produced and sold must not be less than 0 (non-
negativity constraint, which is also an implicit constraint that restricts all variables to be zero
or any positive amount only at all times).

Ch03: Linear Programming: Simplex Method 29

3. Formulate the objective function and constraint function by transcribing the information to
mathematical form.

The objection function will be: Constraints:

Minimize C = 80x1 + 50x2 3x1 + x2 ≥ 6 Chemical 1
x1 + x2 ≥ 4 Chemical 2
2x1 + 6x2 ≥ 12 Chemical 3
x1, x2 ≥ 0 Non-negativity

4. Convert the objective function and constraint functions to equations in standard form.

Objective Function: C = 80x1 + 50x2

= 80x1 + 50x2 + 0s1 + 0s2 + 0s3 + Ma1 + Ma2 + Ma3

Constraints:
3x1 + x2 ≥ 6 x1 + x 2 ≥ 4 2x1 + 6x2 ≥ 12
3x1 + x2 – s1 + a1 = 6 x 1 + x 2 – s 2 + a2 = 4 2x1 + 6x2 – s3 + a3 = 12

5. Create the initial simplex method tableau solution.

Simplex Method Tableau
Tableau 1
Basic Cj 80 50 0 0 0 M M M
CB
Variables RHS x1 x2 s1 s2 s3 a1 a2 a3
M a1 6 3 1 -1 0 0 1 0 0
M a2 4 1 1 0 -1 0 0 1 0
M a3 12 2 6 0 0 -1 0 0 1
Zj 22M 6M 8M -M -M -M M M M
Cj – Zj 80-6M 50-8M M M M 0 0 0

6. Compute for the value Zj of each column by getting the sum of products of the coefficient in C j and
the coefficient in that column
Zj = (M)(6, 3, 1, -1, 0, 0, 1, 0, 0) + (M)(4, 1, 1, 0, -1, 0, 0, 1, 0)
+(M)(12, 2, 6, 0, 0, -1, 0, 0, 1)
Zj = (6M, 3M, M, -M, 0, 0, M, 0, 0) + (4M, M, M, 0, -M, 0, 0, M, 0)
+ (12M, 2M, 6M, 0, 0, -M, 0, 0, M)
Zj = (22M, 6M, 8M, -M, -M, -M, M, M, M)

Compute for the value of Cj – Zj.

Cj – Zj = (80, 50, 0, 0, 0, M, M, M) – (6M, 8M, -M, -M, -M, M, M, M)
= (80-6M, 50-8M, M, M, M, 0, 0, 0)

7. Improve the simplex method tableau:

a. Determine the pivot column – The pivot column is the column with the most negative
value of Cj – Zj.

Since M is a very large number, let us assume a number which we will substitute in Cj – Zj
to know which column has te most negative value.

Let M be equal to 1,000

x, x2
Cj – Zj = 80 – 6M Cj – Zj = 50 – 8M
= 80 – 6(1,000) = 50 – 8(1,000)
= 80 – 6,000 = 50 – 8,000
= - 5,920 = - 7,950

we can say that the pivot column is column of variable x2.

Ch03: Linear Programming: Simplex Method 30

b. Determine the pivot row
R1 = 6 ÷ 1 = 6
R2 = 4 ÷ 1 = 4
R3 = 12 ÷ 6 = 2 The pivot row is R3

NOTE: If the leaving value is an artificial variable, the column of that artificial variable will
be removed in the next improvement. Thus, A3 is not included in the improved Tableau 2.

c. Create the improved simplex method tableau

i. Improve the pivot row
Improved Row (Pivot) = (12, 2, 6, 0, 0, -1, 0, 0) ÷ 6
= (2, 1/3, 1, 0, 0, -1/6, 0, 0)

Tableau 2
Basic Cj 80 50 0 0 0 M M
CB
Variables RHS x1 x2 s1 s2 s3 a1 a2
M a1
M a2
50 x2 2 1/3 1 0 0 -1/6 0 0
Zj
Cj – Z j
The entering variable already replaced the leaving variable

ii. Improve the remaining row

Improved R1 = (6, 3, 1, -1, 0, 0, 1, 0) – (1) (2, 1/3, 1, 0, 0, -1/6, 0, 0)
= (6, 3, 1, -1, 0, 0, 1, 0) – (2, 1/3, 1, 0, 0, -1/6, 0, 0)
= (4, 8/3, 0, -1, 0, 1/6, 1, 0)

Improved R2 = (4, 1, 1, 0, -1, 0, 0, 1) – (1) (2, 1/3, 1, 0, 0, -1/6, 0, 0)

= (4, 1, 1, 0, -1, 0, 0, 1) – (2, 1/3, 1, 0, 0, -1/6, 0, 0)
= (2, 2/3, 0, 0, -1, 1/6, 0, 1)

Tableau 2
Basic Cj 80 50 0 0 0 M M
CB
Variables RHS x1 x2 s1 s2 s3 a1 a2
M a1 4 8/3 0 -1 0 1/6 1 0
M a2 2 2/3 0 0 -1 1/6 0 1
50 x2 2 1/3 1 0 0 -1/6 0 0
Zj
Cj – Z j

iii. Compute for Zj and Cj – Zj

Zj = (M) (4, 8/3, 0, -1, 0, 1/6, 1, 0)+(M) (2, 2/3, 0, 0, -1, 1/6, 0, 1)
+ (50) (2, 1/3, 1, 0, 0, -1/6, 0, 0)
= (4M, 8M/3, 0, -M, 0, M/6, M, 0)+(2M, 2M/3, 0, 0, -M, M/6, 0, M)
+ (100, 50/3, 50, 0, 0, -25/3, 0, 0)
50+10𝑀 𝑀−25
= (100+6M, , 50, -M, -M, , M, M)
3 3

Compute for the value of Cj – Zj.

50+10𝑀 𝑀−25
Cj – Zj = (80, 50, 0, 0, 0, M, M) – ( , 50, -M, -M, , M, M)
3 3
190−10𝑀 25−𝑀
=( , 0, M, M, , 0, 0)
3 3

Ch03: Linear Programming: Simplex Method 31

 Tableau 2
Basic Cj 80 50 0 0 0 M M
CB
Variables RHS x1 x2 s1 s2 s3 a1 a2
M a1 4 8/3 0 -1 0 1/6 1 0
M a2 2 2/3 0 0 -1 1/6 0 1
50 x2 2 1/3 1 0 0 -1/6 0 0
50 + 10𝑀 𝑀 − 25
Zj 100+6M 50 -M -M M M
3 3
190 − 10𝑀 25 − 𝑀
Cj – Z j 0 M M -M -M
3 3

Since there are still negative coefficients in the improved tableau (Tableau 2), let’s do
Step 7 again.

Improvement to Tableau 3
a. Determine the pivot column
Let M be equal to 1,000
x, s3
190 − 10𝑀 25 − 𝑀
Cj – Z j = Cj – Z j =
3 3
190 − 10(1,000) 25 − 1,000
= =
3 3
190 − 10,000 − 975
= =
3 3
− 9,810
=
3

We can say that the pivot column is column of variable x1.

b. Determine the pivot row

R1 = 4 ÷ 8/3 = 3/2 The pivot row is R1
R2 = 2 ÷ 2/3 = 3
R3 = 2 ÷ 1/3 = 6

NOTE: Since the leaving value is an artificial variable, the column of that artificial variable will
be removed in the next improvement. Thus, A1 is not included in the improved Tableau 3.

c. Create the improved simplex method tableau

i. Improve the pivot row
Improved Row (Pivot) = (4, 8/3, 0, -1, 0, 1/6, 0) ÷ 8/3
= (3/2, 1, 0, -3/8, 0, 1/16, 0)

Tableau 3
Basic Cj 80 50 0 0 0 M
CB
Variables RHS x1 x2 s1 s2 s3 a2
80 x1 3/2 1 0 -3/8 0 1/16 0
M a2
50 x2
Zj
Cj – Z j
The entering variable already replaced the leaving variable.

ii. Improve the remaining row

Improved R2 = (2, 2/3, 0, 0, -1, 1/6, 1) – (2/3) (3/2, 1, 0, -3/8, 0, 1/16, 0)
= (2, 2/3, 0, 0, -1, 1/6, 1) – (1, 2/3, 0, -1/4, 0, 1/24, 0)
= (1, 0, 0, ¼, -1, 1/8, 1)

Improved R3 = (2, 1/3, 1, 0, 0, -1/6, 0, 0) – (1/3) (3/2, 1, 0, -3/8, 0, 1/16, 0)

= (2, 1/3, 1, 0, 0, -1/6, 0) – (1/2, 1/3, 0, -1/8, 0, 1/48, 0)
= (3/2, 0, 1, 1/8, 0, -3/16, 0)

Ch03: Linear Programming: Simplex Method 32

 Tableau 3
Basic Cj 80 50 0 0 0 M
CB
Variables RHS x1 x2 s1 s2 s3 a2
80 x1 3/2 1 0 -3/8 0 1/16 0
M a2 1 0 0 1/4 -1 1/8 1
50 x2 3/2 0 1 1/8 0 -3/16 0
Zj
Cj – Z j

iii. Compute for Zj and Cj – Zj

Zj = (80) (3/2, 1, 0, -3/8, 0, 1/16, 0) + (M) (1, 0, 0, ¼, -1, 1/8, 1)
+ (50) (3/2, 0, 1, 1/8, 0, -3/16, 0)
= (120, 80, 0, -30, 0, 5, 0) + (M, 0, 0, M/4, -M, M/8, M)
+ (75, 0, 50, 25/4, 0, -75/8, 0)
𝑀−95 𝑀 − 35
= (195+M, 80, 50, , -M, , M)
4 8

Compute for the value of Cj – Zj.

𝑀−95 𝑀 − 35
Cj – Zj = (80, 50, 0, 0, 0, M) – (80, 50, , -M, , M)
4 8
95−𝑀 35−𝑀
= (0, 0, , M, , 0)
4 4

Tableau 3
Basic Cj 80 50 0 0 0 M
CB
Variables RHS x1 x2 s1 s2 s3 a2
80 x1 3/2 1 0 -3/8 0 1/16 0
M a2 1 0 0 1/4 -1 1/8 1
50 x2 3/2 0 1 1/8 0 -3/16 0
𝑀 − 95 𝑀 − 35
Zj 195+M 80 50 -M M
4 8
95 − 𝑀 35 − 𝑀
Cj – Z j 0 0 M 0
4 8

Since there are still negative coefficients in the improved tableau (Tableau 3), let’s do
Step 7 again.

Improvement to Tableau 4
a. Determine the pivot column
Let M be equal to 1,000
s, s3
95 − 𝑀 35 − 𝑀
Cj – Z j = Cj – Z j =
4 8
95 − 1,000 35 − 1,000
= =
4 8
−905 − 965
= =
4 8

We can say that the pivot column is column of variable s1.

b. Determine the pivot row

R1 = 3/2 ÷ -3/8 = -4
R2 = 1 ÷ 1/4 = 4 The pivot row is R2
R3 = 3/2 ÷ 1/8 = 12

NOTE: Since the leaving value is an artificial variable, the column of that artificial variable will
be removed in the next improvement. Thus, A2 is not included in the improved Tableau 4.

c. Create the improved simplex method tableau

i. Improve the pivot row
Improved Row (Pivot) = (1, 0, 0, ¼, -1, 1/8) ÷ 1/4
= (4, 0, 0, 1, -4, ½ )

Ch03: Linear Programming: Simplex Method 33

 Tableau 4
Basic Cj 80 50 0 0 0
CB
Variables RHS x1 x2 s1 s2 s3
80 x1
0 s1 4 0 0 1 -4 ½
50 x2
Zj
Cj – Zj
The entering variable already replaced the leaving variable.

ii. Improve the remaining row

Improved R1 = (3/2, 1, 0, -3/8, 0, 1/16) – (-3/8) (4, 0, 0, 1, -4, ½ )
= (3/2, 1, 0, -3/8, 0, 1/16) – (-3/2, 0, 0, -3/8, 3/2, -3/16)
= (3, 1, 0, 0, -3/2, ¼)

Improved R3 = (3/2, 0, 1, 1/8, 0, -3/16) – (1/8) (4, 0, 0, 1, -4, ½ )

= (3/2, 0, 1, 1/8, 0, -3/16) – (1/2, 0, 0 1/8, -1/2, 1/16)
= (1, 0, 1, 0, ½, -¼)

Tableau 4
Basic Cj 80 50 0 0 0
CB
Variables RHS x1 x2 s1 s2 s3
80 x1 3 1 0 0 -3/2 ¼
0 s1 4 0 0 1 -4 ½
50 x2 1 0 1 0 ½ -¼
Zj
Cj – Zj

iii. Compute for Zj and Cj – Zj

Zj = (80) (3, 1, 0, 0, -3/2, ¼) + (0) (4, 0, 0, 1, -4, ½ ) + (50) (1, 0, 1, 0, ½, -¼)
= (240, 80, 0, 0, -120, 20) + (0, 0, 0, 0, 0, 0) + (50, 0, 50, 0, 25, -25/2)
= (290, 80, 50, 0, -95, 15/2)

Compute for the value of Cj – Zj.

Cj – Zj = (80, 50, 0, 0, 0) – (80, 50, 0, -95, 15/2)
= (0, 0, 0, 95, -15/2)

Tableau 4
Basic Cj 80 50 0 0 0
CB
Variables RHS x1 x2 s1 s2 s3
80 x1 3 1 0 0 -3/2 ¼
0 s1 4 0 0 1 -4 ½
50 x2 1 0 1 0 ½ -¼
Zj 290 80 50 0 -95 15/2
Cj – Zj 0 0 0 95 -15/2

Since there is still a negative coefficient in the improved tableau (Tableau 4), let’s do
Step 7 again.

Improvement to Tableau 5
a. Determine the pivot column – The pivot column is column of variable s3.

b. Determine the pivot row

R1 = 3 ÷ 1/4 = 12
R2 = 4 ÷ 1/2 = 8 The pivot row is R2
R3 = 1 ÷ -1/4 = -4

Ch03: Linear Programming: Simplex Method 34

c. Create the improved simplex method tableau
i. Improve the pivot row
Improved Row (Pivot) = (4, 0, 0, 1, -4, ½ ) ÷ 1/2
= (8, 0, 0, 2, -8, 1)

Tableau 5
Basic Cj 80 50 0 0 0
CB
Variables RHS x1 x2 s1 s2 s3
80 x1
0 s3 8 0 0 2 -8 1
50 x2
Zj
Cj – Zj
The entering variable already replaced the leaving variable.

ii. Improve the remaining row

Improved R1 = (3, 1, 0, 0, -3/2, ¼) – (1/4)(8, 0, 0, 2, -8, 1)
= (3, 1, 0, 0, -3/2, ¼) – (2, 0, 0, ½, -2, ¼)
= (1, 1, 0, -½, ½, 0)

Improved R3 = (1, 0, 1, 0, ½, -¼) – (-1/4)(8, 0, 0, 2, -8, 1)

= (1, 0, 1, 0, ½, -¼) – (-2, 0, 0, -½, 2, -¼)
= (3, 0, 1, ½, -3/2, 0)

Tableau 5
Basic Cj 80 50 0 0 0
CB
Variables RHS x1 x2 s1 s2 s3
80 x1 1 1 0 -½ ½ 0
0 s3 8 0 0 2 -8 1
50 x2 3 0 1 ½ -3/2 0
Zj
Cj – Zj

iii. Compute for Zj and Cj – Zj

Zj = (80) (1, 1, 0, -½, ½, 0) + (0) (8, 0, 0, 2, -8, 1) + (50) (3, 0, 1, ½, -3/2, 0)
= (80, 80, 0, -40, 40, 0) + (0, 0, 0, 0, 0, 0) + (150, 0, 50, 25, -75, 0)
= (230, 80, 50, -15, -35, 0)

Compute for the value of Cj – Zj.

Cj – Zj = (80, 50, 0, 0, 0) – (80, 50, -15, -35, 0)
= (0, 0, 15, 35, 0)

Tableau 5
Basic Cj 80 50 0 0 0
CB
Variables RHS x1 x2 s1 s2 s3
80 x1 1 1 0 -½ ½ 0
0 s1 8 0 0 2 -8 1
50 x2 3 0 1 ½ -3/2 0
Zj 230 80 50 -15 -35 0
Cj – Zj 0 0 15 35 0

Since there no negative coefficient in the improved tableau (Tableau 5) anymore, we already
have our optimal solution.

Ch03: Linear Programming: Simplex Method 35

The solution for the linear programming is found in the RHS column.

Decision:
x1 = 1 soap#1
x2 = 3 soap#2
C = P230

Let us check for the minimum amount of cost that can be obtained by the optimal solution
Objective Function: C = 80x1 + 50x2
= 80(1) + 50(3)
= 80 + 130
= 230

Also, let us check if there are any surplus resources.

Chemical 1 Chemical 2 Chemical 3
Minimum amount 6 4 12
Allotted for soap#1
1x3 (3)
1x1 (1)
1x2 (2)
Allotted for soap#2
3x1 (3)
3x1 (1)
3x6 (18)
Surplus resources 0 0 (8)

Same with the table 5, only s1 has a surplus value which is 8. All other surplus variables are
zero.

Ch03: Linear Programming: Simplex Method 36

Ch03: Linear Programming: Simplex Method 37