Lesson 3: Simplex Method

Objectives:

After reading and studying this lesson, the students will be able to:

• Differentiate the simplex method from the graphical method

• Use the simplex method in solving linear programming problems
• Distinguish the optimum tables of the simplex maximization process from those of the
simple minimization process
• Apply the iterative process used in the simplex method

Introduction

The simplex algorithm/method from solving linear programming problems, a repetitive

optimizing technique, was developed around 50 years ago be George Dantzig of Stanford University. It
is a method/process that can be used to maximized or minimized the value of problems, especially when
many variables or constraints are present.

Simplex Method for Solving Maximum Problems in Standard form

A linear programming problem that aims to maximize values is referred to as a maximum linear
programming problem. The standard form specifies that the following conditions are met:

Condition 1. All the variables are non-negative.

Condition 2. All other constraints are written as linear expressions that is less than or equal
to a positive constant.

To apply the simplex method to a maximum problem, two steps are followed:

1. Introduce a slack variable .

2. Construct an initial simplex tableau.

A slack variable is a non-negative variable representing the difference between the left and the
right sides of the inequality. It also signifies the unused quantity of the constraint.

In constructing an initial simplex tableau, a table containing the symbols of the variables in each
column must first be made. The objective function and the constraints mut be placed together with
their corresponding coefficients. The first row in the table represents the objective function and its
coefficient. The remaining rows represent the constraints and their coefficients. The objective row is
separated from the constraint by horizontal line. A variable that contains a numerical coefficient of 1
and 0 is called a basic variable and denoted by BV. The number to the right-hand side of the objective
function and the constraint is also denoted as RHS.

Once the initial simplex tableau is constructed, a pivoting operation must be performed. To
pivot a matrix about a given element, called the pivot element, the row operation is applied so that the
pivot elements are replaced by 1 and all other entries in the same column becomes 0’s.

To clearly illustrate, the general procedure for solving maximum linear programming in standard
form using simplex method can be outlined as:

Step 1. State the objective function and constraints as:

Maximize: 𝑃 = 𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛

Subject to: (constraints)

𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 ≤ 𝑏1

𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 ≤ 𝑏2

. . . .
. . . .
. . . .

𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 ≤ 𝑏𝑚

𝑥1 ≥ 0; 𝑥2 ≥ 0; … ; 𝑥𝑛 ≥ 0

In which 𝑏1 ≥ 0; 𝑏2 ≥ 0; … ; 𝑏𝑚 ≥ 0

Step 2. Introduce the slack variables so that the constraints take the form of equalities

𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 + 𝑆1 = 𝑏1

𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 + 𝑆2 = 𝑏2

. . . .
. . . .
. . . .

𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 + 𝑆𝑚 = 𝑏𝑚

𝑥1 ≥ 0; 𝑥2 ≥ 0; … ; 𝑥𝑛 ≥ 0

𝑆1 ≥ 0; 𝑆2 ≥ 0; … ; 𝑆𝑚 ≥ 0
 Step 3. Write the objective function into the form of:

𝑃 − 𝑐1 𝑥1 ± 𝑐2 𝑥2 ± ⋯ ± 𝑐𝑛 𝑥𝑛 = 0

Step 4. Construct the initial simplex tableau:

BV P X1 X2 … Xn S1 S2 … Sm RHS
P 1 -C1 -C2 … -Cn 0 0 … 0 0
S1 0 A11 A12 … A1n 1 0 … 0 B1
S2 0 A21 A22 … A2n 0 1 … 0 B2
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
Sm 0 Am1 Am2 … Amn 0 0 … 1 BM

Step 5. Pivot until:

1. All entries in the objective function row are non-negative. It means that it is a final
tableau from which a solution can be read; or until;
2. The selection of the pivot column is a column whose entries are negative or zero. If
that is the case, it is unbounded and there is no solution.

Example 1. The XYZ Appliance makes two products – tables and chairs – which must be processed
through their assembly and finishing departments. The assembly department is available for 60 hours in
every production period while the finishing department is available or 48 hours of work. Manufacturing
1 table requires 4 hours in the assembly and 2 hours in finishing departments. A chair takes 2 hours to
assemble and 4 hours in finish. A table is worth $80 while a chair is $60. Determine the number of
tables and chairs to maximize the profit per production process.

Solution:

Total to Process in Total to Process in

Profit
Assembly Finishing
Let X1 be the number of tables 4X1 2X1 80X1
Let X2 be the number of chairs 2X2 4X2 60X2

Step 1. State the objective function.

Maximize: P = 80X1 + 60X2
Subject to: (constraints)
4𝑥1 + 2𝑥2 ≤ 60 𝑜𝑟 2𝑥1 + 𝑥2 ≤ 30

2𝑥1 + 4𝑥2 ≤ 48 𝑜𝑟 𝑥1 + 2𝑥2 ≤ 24

𝑥1 ≥ 0; 𝑥2 ≥ 0
Step 2. Introduce slack variables (S1 and S2 since there are only two constraints) and write the
constraints in equation form.

2𝑥1 + 𝑥2 + 𝑆1 = 30

𝑥1 + 2𝑥2 + 𝑆2 = 24

𝑥1 ≥ 0; 𝑥2 ≥ 0; 𝑆1 ≥ 0; 𝑆2 ≥ 0

Step 3. Write the objective function in the equation form.

𝑃 − 80𝑋1 − 60𝑋2 = 0

Step 4. Construct an initial simplex tableau

BV P X1 X2 S1 S2 RHS
P 1 -80 -60 0 0 0
S1 0 2 1 1 0 30
S2 0 1 2 0 1 24
(Tableau 1)

Step 5. Perform pivoting operations

The first step is to find the pivot element. Find the smallest value in the objective row. The column it
belongs to is the pivot column. Divide the values in the RHS by the corresponding value in the pivot
column. Whichever value gives the smallest quotient is the pivot element. In the example given, the
smallest value in the objective row is -80, so the column X1 , is the pivot column. The quotient of RHS and
the positive entries in the pivot column are 30 ÷ 2 = 15 and 24 ÷ 1 = 24. The smallest among the two is
15; then, the pivot row is S1, and the pivot element is 2.

1
Next is taking the pivot row (R2) and transforming the pivot element into 1 using 𝑅2 = 2 𝑅2

1 1 1
𝑅2 = [0 2 1 1 0 30] = [0 1 0 15]
2 2 2

Next is to pivot R1 and R3 to make the values in the pivot column 0’s. For R3, R3 = R3 – R2 is use. Thus,

R3 0 1 2 0 1 24
1 1
R2 0 1 2 2
0 15

3 1
R3 0 0 2
−2 1 9
For R1, the operation is R1 = R1 + 80 R1. Then,

R1 1 -80 -60 0 0 0
+ 80R2 80(0) 80(1) 80(2)
1
80(2)
1
80(0) 80(15)

R3 1 0 -20 40 0 1200

Replacing all previous rows with the derived ones results in:

BV P X1 X2 S1 S2 RHS
P 1 0 -20 40 0 1200
X1 0 1 1 1 0 15
2 2
X2 0 0 3 1 1 9
−
2 2
(Tableau 2)

Pivoting in the first constraints is now done. Since there is still a negative value in the objective row on
the tableau, continue pivoting until the values in the objective row are all non – negative. In table 2, the
3
pivot column is X2, the pivot row X2 and the pivot element is . Applying the row operation once
2
2
again for R3 = 3R3, gives the following:

2 3 1 1 2
𝑅3 = [0 0 − 1 9] = [0 0 1 − 6]
3 2 2 3 3
1
For R2, the operation is R2 = R2 - 2 R3

1 1
R2 0 1 2 2
0 15

1 1 1 1 1 1 1 2 1
2
R3 2
(0) 2
(0) 2
(1) (- )
2 3
( )
2 3 2
(6)

2 1
R2 0 1 0 3
−3 12

For R1, the operation is R1 = R1 + 20R3, then:

R1 1 0 -20 40 0 1200

+ 20 R3 20(0) 20(0) 20(1)

1
20(− 3) 20(3)
2
20(6)

100 40
R1 1 0 0 3 3
1320
 BV P X1 X2 S1 S2 RHS
P 1 0 0 100 40 1320
3 3
X1 0 1 0 2 1 12
−
3 3
X2 0 0 1 1 2 6
−
3 3

(tableau 3)

Since the objective row in tableau 3 is composed of non – negative numbers, then the tableau is final.

Decision

The value of X1 is 12 and X2 is 6. Therefore, the maximum profit per production is $1320.

Example 2. Consider the previous example on Shampoo. The data are given in the table below:

Product
Process Number of Minutes per Case
Available Minutes per Day
Men’s Shampoo Women’s Shampoo
Mixing 5x 10y ≤ 100
Bottling 7x 7y ≤ 84
Packing 9x 5y ≤ 90
Profit per case in Php 60x 80y = Maximize

Solve the problem using Simplex Method.

Solution: Step 1. Setup the objective function:

Maximize: 𝑃 = 60𝑥 + 80𝑦

Subject to: (constraints)
5𝑥 + 10𝑦 ≤ 100
7𝑥 + 7𝑦 ≤ 84
9𝑥 + 5𝑦 ≤ 90
𝑥 ≥ 0, 𝑦 ≥ 0

Step 2. Introduce slack variables S1 ,S2 ,and S3 since there are three constraints. (The number of slack
variables depends on the number of constraints). Write the inequalities in equation forms. Thus,
5𝑥 + 10𝑦 + 𝑆1 = 100
7𝑥 + 7𝑦 + 𝑆2 = 84
9𝑥 + 5𝑦 + 𝑆3 = 90
𝑥 ≥ 0; 𝑦 ≥ 0; 𝑆1 ≥ 0; 𝑆2 ≥ 0; 𝑆3 ≥ 0
 Step 3. Write the Objective function in the equation form.
𝑃 − 60𝑥 − 80𝑦 = 0

Step 4. Construct the initial Simplex Tableau

BV P X Y S1 S2 S3 RHS
P 1 -60 -80 0 0 0 0
S1 0 5 10 1 0 0 100
S2 0 7 7 0 1 0 84
S3 0 9 5 0 0 1 90
(TABLEAU 1)

Step 5. Perform the pivot operation.

From the tableau, the most negative in the objective row is -80 and y is the pivot column.
Solving the pivot row, the quotient of 100/10 is 10, 84/7 is 12 and 90/5 is 18. The lowest among them is
our pivot row is at S1. The pivot element, therefore, is 10. Applying the row operation in S1, which is
S1=R2 results in:
1 1 1
𝑅2 = 10 [0 5 10 1 0 0 100] = [0 2
1
10
0 0 10]

For row operation of S2 = R3, use R3=R3 - 7R2 shows:

R3 0 7 7 0 1 0 84
1 1
7R2 7(0) 7(2) 7(1) 7(10) 7(0) 7(0) 7(10)

7 7
R3 0 0 − 1 0 14
2 10

For row operation of S3 = R4, use R4 = R4 – 5R2, thus:

R4 0 9 5 0 0 1 90
1 1
5R2 5(0) 5(2) 5(1) 5(10) 5(0) 5(0) 5(10)

13 1
R4 0 2
0 −2 0 1 40

For row operation of P = R1, then R1 = R1 + 80R2

R1 1 -60 -80 0 0 0 0
1 1
+ 80R2 80(0) 80(2) 80(1) 80(10) 80(0) 80(0) 80(10)
R1 1 -20 0 8 0 0 800
 The New Tableau is:

BV P X Y S1 S2 S3 RHS
P 1 -20 0 8 0 0 800
Y 0 1 1 1 0 0 10
2 10
S2 0 7 0 7 1 0 14
−
2 10
S3 0 13 0 1 0 1 40
−
2 2
(TABLEAU 2)

Since there still a negative value on the objective function, another pivoting process must be done. In
7
the tableau above, the pivotal column is in X, and the pivotal row at S2 and the pivot element is 2.

2
Performing row operations in S2, use R3 = 7R3 shows:
2 7 7 1 2
𝑅3 = 7 [0 0 − 10 1 0 14] = [0 1 0 − 0 4]
2 5 7

1
For R2, the row operation is R2 = R2 - 2R3

1 1
R2 0 2
1 10
0 0 10
1 1 1 1 1 1 1 2 1 1
2
R3 2
(0) 2
(1) 2
(0) 2
(− 5) ( )
2 7 2
(0) 2
(4)

1 1
R2 0 0 1 − 0 8
5 7

13
For R4, the row operation is R4 = R4 - 2
R3 , Solving for R4:
13 1
R4 0 2
0 −2 0 1 40
13 13 13 13 13 1 13 2 13 13
2
R3 2
(0) 2
(1) 2
(0) 2
(− 5) 2 (7) 2
(0) 2
(4)

4 13
R4 0 0 0 5
− 7
1 14

For the row operation of the first row, R1 = R1 + 20R3, then:

R1 1 -20 0 8 0 0 800
+ 20R3 20(0) 20(1) 20(0)
1
20(− 5)
2
20(7) 20(0) 20(4)

40
R1 1 0 0 4 0 880
7
Summarizing the results, the new tableau:

BV P X Y S1 S2 S3 RHS
P 1 0 0 4 40 0 880
7
Y 0 0 1 1 1 0 8
−
5 7
X 0 1 0 1 2 0 4
−
5 7
S3 0 0 0 4 13 1 14
−
5 7
(TABLEAU 3)

Decision
The production manager should decide to produce 4 cases of Men’s Shampoo and 8 cases of
Women’s Shampoo per day at a maximum profit of Php 880, with 14 minutes of unused packing
capacity.

Simplex Method for Solving Minimum Problems in Standard Form

A linear programming problem that aims to minimize values is called minimum linear
programming problem. Such problem is said to be in standard form if the following conditions we wet:

1. All variables are non-negative

2. All other constraints are written as a linear expression which is expressed as greater than or
equal to a constant.
3. The objective function must be expressed as a linear expression with non – negative
coefficient.

The technique for solving a minimum problem in standard form was developed by John von
Neumann and others in 1928. This is based on the duality principle which states that:

"The optimum solution, if it exists, of a minimum linear programming problem in Standard form
has the same value as the optimal solution of the dual problem, a maximum problem in
standard form"
 In other words, a minimum problem can be solved in terms of a maximum problem. The
following are the steps in solving a minimum problem in standard form:

Step 1. Formulate the dual (maximum) problem by doing the succeeding steps:
a) Write the minimum problem in standard form.
b) Construct the matrix that represents the constraints and the objective function
c) Interchange the rows and columns to form the matrix of the dual problem.
d) Translate this matrix into a maximum problem in standard form.

Step 2. Solve the maximum problem using the simplex method.

Step 3. Get the optimal solution for the maximum problem from the objective row of the final
simplex tableau.

Step 4. The minimum value of the objective function will appear in the upper right corner of the
final tableau. It is equal to the maximum value of the dual objective function

Example: Objective Function:

Minimize: 𝐶 = 6𝑥1 + 8𝑥2 + 𝑥3
Subject to: 3𝑥1 + 5𝑥2 + 3𝑥3 ≥ 20
𝑥1 + 3𝑥2 + 2𝑥3 ≥ 9
6𝑥1 + 2𝑥2 + 5𝑥3 ≥ 30
𝑥1 ≥ 0; 𝑥2 ≥ 0; 𝑥3 ≥ 0

Solution:
Write the dual problem. The minimum problem is in the standard form. The matrix
representing the problem is shown in the left table below. Inter-change rows and columns to get the
table on the right. (also known as Matrix Transpose)

3 5 3 20 3 1 6 6
1 3 2 9 5 3 2 8
6 2 5 30 3 2 5 1
6 8 1 0 20 9 30 0

The dual problem is:

Maximize: 𝑃 = 20𝑦1 + 9𝑦2 + 30𝑦3
Subject to: 3𝑦1 + 𝑦2 + 6𝑦3 ≤ 6
5𝑦1 + 3𝑦2 + 2𝑦3 ≤ 8
3𝑦1 + 2𝑦2 + 5𝑦3 ≤ 1
𝑦1 ≥ 0; 𝑦2 ≥ 0; 𝑦3 ≥ 0
 Applying the maximum simplex method and introducing slack variables, the initial simplex tableau is:
BV P Y1 Y2 Y3 S1 S2 S3 RHS
P 1 -20 -9 -30 0 0 0 0
S1 0 3 1 6 1 0 0 6
S2 0 5 3 2 0 1 0 8
S3 0 3 2 5 0 0 1 1
(TABLEAU 1)
From the first tableau, the pivotal element can be found. The pivot column is Y3 , the pivot row is S3, and
the pivot element is 5. Applying row operation on R4, thus:
1 3 2 1 1
𝑅4 = 5 [0 3 2 5 0 0 1 1] = [0 5 5
1 0 0 5 5
]

For R3 operation use R3=R3 – 2R4:

R3 0 5 3 2 0 1 0 8
3 2 1 1
2R4 2(0) 2(5) 2(5) 2(1) 2(0) 2(0) 2(5) 2(5)

19 11 2 38
R3 0 5 5
0 0 1 −5 5

For R2, the row operation is R2 = R2 – 6R4

R2 0 3 1 6 1 0 0 6
3 2 1 1
6R4 6(0) 6( ) 6( ) 6(1) 6(0) 6(0) 6( ) 6( )
5 5 5 5
3 7 6 24
R2 0 −5 −5 0 1 0 −5 5

For R1 row operation, R1 = R1 + 30R4

R1 1 -20 -9 -30 0 0 0 0
+ 30R4 30(0)
3
30( )
2
30( ) 30(1) 30(0) 30(0)
1
30( ) 30( )
1
5 5 5 5
R1 1 -2 3 0 0 0 6 6

The new Tableau shows:

BV P Y1 Y2 Y3 S1 S2 S3 RHS
P 1 -2 3 0 0 0 6 6
S1 0 3 7 0 1 0 6 24
− − −
5 5 5 5
S2 0 19 11 0 0 1 2 38
−
5 5 5 5
y3 0 3 2 1 0 0 1 1
5 5 5 5
(TABLEAU 2)
 3
The pivot column in the second tableau is Y1, the pivot row is Y3, and the pivot element is 5. Applying
the row operation in the tableau:
5 3 2 1 1 2 5 1 1
𝑅4 = 3 [0 1 0 0 5 5
] = [0 1 0 0 3
]
3
5 5 3 3

19
The next row operation is R3 = R3 - 5
R4
19 11 2 38
R3 0 5 5
0 0 1 −5 5
19 19 19 19 2 19 5 19 19 19 1 19 1
5
R4 5
(0) 5
(1) ( )
5 3
( )
5 3 5
(0) 5
(0) ( )
5 3
( )
5 3
1 19 5 19
R3 0 0 −3 −3 0 1 −3 3

3
Finding the row operation values of R2, use R2 = R2 + R4.
5

3 7 6 24
R2 0 −5 −5 0 1 0 −5 5
+ 3
R4
3
(0)
3
(1)
3 2
( )
3 5
( )
3
(0)
3
(0)
3 1
( )
3 1
( )
5 5 5 5 3 5 3 5 5 5 3 5 3

R2 0 0 -1 1 1 0 -1 5

In Solving R1, the row operations be, R1 = R1 + 2R4. Thus,

R1 1 -2 3 0 0 0 6 6
+ 2R4 2(0) 2(1) 2( )
2
2(3)
5
2(0) 2(0) 2(3)
1
2(3)
1
3
13 10 20 20
R1 1 0 0 0
3 3 3 3

Applying the results:

BV P Y1 Y2 Y3 S1 S2 S3 RHS
P 1 0 13 10 0 0 20 𝟐𝟎
3 3 3 𝟑
S1 0 0 -1 1 1 0 -1 5
S2 0 0 1 19 0 1 5 19
− − −
3 3 3 3
Y1 0 1 2 5 0 0 1 𝟏
3 3 3 𝟑
(TABLEAU 3)
Since all the entries in the objective row are non – negatives, then it is the final tableau. The
result is a maximum; so, it implies that:
𝟐𝟎 𝟏
Maximum Profit(P) = with Y1 = 𝟑; Y2=0; Y3=0
𝟑
The target is to minimize. Applying the principle of duality it gives:

𝑥1 = 𝑦3 ; 𝑥2 = 𝑦2 ; 𝑥3 = 𝑦1 ; and

P(Maximum) = P(Minimum), then

𝟏 𝟐𝟎
At 𝒙𝟏 = 𝟎; 𝒙𝟐 = 𝟎; 𝒙𝟑 = 𝟑 ; 𝒕𝒉𝒆 𝒎𝒊𝒏𝒊𝒎𝒖𝒎 𝒄𝒐𝒔𝒕 𝒊𝒔 𝟑