CHAPTER 3
THE SIMPLEX
METHOD
ASSOC. PROF. HO THANH PHONG
OBJECTIVES
AFTER COMPLETING THIS CHAPTER, STUDENTS
WILL BE ABLE TO:
• Setup a standard LP problem
• Solve LP with simplex method
• Solve LP with computer software
• Understand special cases in LP
Operations Research - Assoc. Professor Ho Thanh Phong
THE STANDARD LP PROBLEM
• All constraints are equations.
• All variables are nonnegative
• The objective function may be maximization or
minimization.
• Constraints: with the type (), add a slack
variable (subtract a surplus variable) to left side
Example:
3x1 + 2x2 25 is converted to 3x1 + 2x2 + s = 25
• Objective function: Max. Z = - Min (- Z)
Example: Max Z = 5x1 + 3x2 has the same
solution with Min (-Z) = - 5x1 - 3x2
3
Operations Research - Assoc. Professor Ho Thanh Phong
BASIC SOLUTIONS
1. Each variable is designated as either a nonbasic variable or a
basic variable.
2. The number of basic variables equals the number of
constraints.
If we have m constraints, n variables then number of nonbasic
variables = n – m, number of basic variables = m
3. The nonbasic variables are set equal to zero, basic variables
are set different with zero .
4. The values of the basic variables are obtained as the
simultaneous solution of the system of equations. The set of basic
variables is often referred to as the basis.
5. If the basic variables satisfy the nonnegativity constraints, the
basic solution is a BF solution (Basic Feasible Solution).
4
Operations Research - Assoc. Professor Ho Thanh Phong
We consider the example: After converting:
Max. profit Z = 3x1 + 5x2 Max. Z = 3x1 + 5x2
Subject to: Subject to:
x1 4
2x2 12 x1 + 1s1 =4
3x1 + 2x2 18 2x2 + 1s2 = 12
3x1 + 2x2 + 1s3 = 18
m = 3; n = 5 ➔ Number of m = 3; n = 5
nonbasic = 2, basic = 3. The final solution:
The initial solution: x1 = 2; x2 = 6; s1 = 2
x1 = x2 = 0 :non-basic s2 = s3 = 0
s1 = 4; s2 = 12; s3 = 18 : basic We have m=3 basic solutions and
(5 – 3) = 2 nonbasic solutions
5
Operations Research - Assoc. Professor Ho Thanh Phong
Simplex Method using (Cj – Zj) coefficients for Maximization
problem (Minimization)
1. Determine the new entering variable by select the largest
positive (most negative) number in the (Cj – Zj) row. The column
identified is called pivot column.
2. Determine leaving variable by dividing amount in RHS by the
corresponding number in the selected column, select smallest
ratio, take only positive number. This row is called pivot row, the
intersection called pivot number.
3. Compute the new value for pivot row: divide every number for
the pivot number.
4. Compute the new value for each remaining row: keep other
number in the pivot column ( pivot number) to be zero by
matrix elementary transformation
5. If all numbers in the (Cj – Zj) row are non-positive (non-
negative), reach optimal. If not, return to step 1 6
Operations Research - Assoc. Professor Ho Thanh Phong
Simplex Method using Cj - Zj coefficients
Max. Z = 3x1 + 5x2+0s1+0s2+0s3
Subject to:
x1 + 1s1 =4
2x2 + 1s2 = 12
3x1 + 2x2 + 1s3 = 18
SIMPLEX ITERATION 1
Cj 3 5 0 0 0
BV X1 X2 S1 S2 S3 RHS
0 S1 1 0 1 0 0 4
0 S2 0 2 0 1 12
0 S2 leaving
0 S3 3 2 0 0 18
1
Zj 0 0 0 0 0 0
Cj - Zj 3 5 0 0 0
X2 entering
This number must be This number must be
equal to 1 transformed to zero
Operations Research - Assoc. Professor Ho Thanh Phong 7
Cj 3 5 0 0 0
Solution X1 X2 S1 S2 S3 RHS
0 S1 1 0 1 0 0 4
5 X2 0 1 0 1/2 0 6
0 S3 3 2 0 0 1 18
Zj 0 0 0 0 0 0
Cj - Zj 3 5 0 0 0
This number must be
transformed to zero
SIMPLEX ITERATION 2
Cj 3 5 0 0 0
Solution X1 X2 S1 S2 S3 RHS
0 S1 1 0 1 0 0 4
5 X2 0 1 0 1/2 0 6
0 S3 3 0 0 -1 1 6 S3 leaving
Zj 0 5 0 5/2 0 30
Cj - Zj 3 0 0 - 5/2 0
X1 entering
This number must be This number must be
equal to 1 equal to 0
Operations Research - Assoc. Professor Ho Thanh Phong 8
SIMPLEX ITERATION 3
Cj 3 5 0 0 0
Solution X1 X2 S1 S2 S3 RHS
0 S1 0 0 1 1/3 - 1/3 2
5 X2 0 1 0 1/2 0 6
3 X1 1 0 0 -1/3 1/3 2
Zj 3 5 0 3/2 1 36
Cj - Zj 0 0 0 - 3/2 -1
All coefficients in (Cj-Zj) are non positive, we reach optimal solution. Values are:
We have S1 = 2, this means
X1 = 2 resource 1 have not used
X2 = 6 exhausted, something remains
Z = 36
Operations Research - Assoc. Professor Ho Thanh Phong 9
Simplex Method using Z-equation for read for fun
Maximization problem (Minimization)
1. Determine the entering variable by select the most negative
(largest positive) number in the Z-equation row. The column
identified is called pivot column.
2. Determine leaving variable by dividing amount in RHS by the
corresponding number in the selected column, select smallest
ratio, take only positive number. This row is called pivot row,
the intersection called pivot number.
3. Compute the new value for pivot row: divide every number
for the pivot number.
4. Compute the new value for each remaining row: keep other
number in the pivot column ( pivot number) to be zero by
matrix elementary transformation
5. If all numbers in the Z-equation row are non-negative (non-
positive), reach optimal. If not, return to step 1 10
Operations Research - Assoc. Professor Ho Thanh Phong
Cj 3 5 0 0 0
Z - 3x1 - 5x2-0s1-0s2-0s3 = 0 Basic X1 X2 S1 S2 S3 RHS
x1 + 1s =4 Solution
2x2 + 1s2 = 12 0 S1 1 0 1 0 0 4
0 S2 0 2 0 1 0 12
3x1 + 2x2 + 1s3 = 18 0 S3 3 2 0 0 18
1
Zj 0 0 0 0 0 0
Cj - Zj 3 5 0 0 0
Basic Z X1 X2 S1 S2 S3 RHS
Variable
Z 1 -3 -5 0 0 0 0
S1 0 1 0 1 0 0 4 Constraint
rows
S2 0 0 2 0 1 0 12
S3 0 3 2 0 0 1 18
Currently, X1 = X2 = 0; if we want to increase 1 unit of X1 so we have to
decrease S1 and S2 . Remember S1 and S2 is the available resources.
Notes: Z = 3x1 + 5x2➔ Z - 3x1 - 5x2= 0
11
Operations Research - Assoc. Professor Ho Thanh Phong
The 2nd Simplex Tableau
Basic Z X1 X2 S1 S2 S3 RHS Basic Z X1 X2 S1 S2 S3 RHS
Variable Variable
Z 1 -3 0 0 5/2 0 30 Z 1 -3 -5 0 0 0 0
S1 0 1 0 1 0 0 4 S1 0 1 0 1 0 0 4
X2 0 0 1 0 1/2 0 6 S2 0 0 1 0 1/2 0 6
S3 0 3 0 0 -1 1 6 S3 0 3 2 0 0 1 18
The 3rd Simplex Tableau is the final tableau
Basic Z X1 X2 S1 S2 S3 RHS All coefficients in Z-
Variable equation are non-negative,
Z 1 0 0 0 3/2 1 36 we reached optimal values:
S1 0 0 0 1 1/3 -1/3 2 Z = 36
X2 0 0 1 0 1/2 0 6 S1 = 2
X1 0 1 0 0 -1/3 1/3 2 X2 = 6
X1 = 2
S1 = 2 : resource corresponding still remains 2, not
finishes yet.
12
Operations Research - Assoc. Professor Ho Thanh Phong
ARTIFICIAL VARIABLES
When dealing with equality constraints, we need artificial variables
We consider the example: After converting:
Max. profit Z = 7x1 + 5x2 Max. Z = 7x1 + 5x2+ 0s1+ 0s2 -MA1 -MA2
Subject to: Subject to:
4x1 + 3x2 240 4x1 + 3x2 + 1s1 = 240
2x1 + 1x2 100 2x1 + 1x2 - 1s2 +1 A1 = 100
5x1 + 3x2 = 400 5x1 + 3x2 + A2 = 400
Note: The coefficients of surplus and slack variables in objective function are 0 whereas
the coefficients of artificial variables are very big number, M. Max (use –M), Min (use
M)
13
Operations Research - Assoc. Professor Ho Thanh Phong
Example 2 (Minimization problem)
Solve the following Min. problem:
Min. Z = 5 X1 + 6 X2 By graphical approach, we obtain:
Sub. To: X1 = 300
X1 + X2 = 1000 X2 = 700
X1 300 Cost Z = 5700
X2 150
X1, X2 0
To use Simplex method, we convert the original problem
to standard form:
Min. Z = 5X1 +6X2 + 0S1 + 0S2 + MA1 + MA2
Sub. To:
X1 + X2 + A1 = 1000 (Why we use two more variables
X1 + S1 = 300 in the last constraint ?)
X2 - S2 + A2 = 150
14
Operations Research - Assoc. Professor Ho Thanh Phong
Initial Simplex tableau
Cj 5 6 0 0 M M Quantity
Solution X1 X2 S1 S2 A1 A2
M A1 1 1 0 0 1 0 1000
0 S1 1 0 1 0 0 0 300
M A2 0 1 0 -1 0 1 150
Zj M 2M 0 -M M M 1150 M
Cj - Zj -M+5 -2M+6 0 M 0 0
Second Simplex tableau
Cj 5 6 0 0 M M Quantity
Solution X1 X2 S1 S2 A1 A2
M A1 1 0 0 1 1 -1 850
0 S1 1 0 1 0 0 0 300
6 X2 0 1 0 -1 0 1 150
Zj M 6 0 M-6 M -M+6 850M+900
Cj - Zj -M+5 0 0 - M+6 0 2M-6
15
Operations Research - Assoc. Professor Ho Thanh Phong
Student check and self develop the intermediate simplex tableau.
The final Simplex tableau
Cj 5 6 0 0 M M Quantity
Solution X1 X2 S1 S2 A1 A2
0 S2 0 0 -1 1 1 -1 550
5 X1 1 0 1 0 0 0 300
6 X2 0 1 -1 0 1 0 700
Zj 5 6 -1 0 6 0 5700
Cj - Zj 0 0 1 0 M-6 M
The optimal solution is:
X1 = 300
X2 = 700
Cost Z = 5700
(The surplus S2 = 550)
16
Operations Research - Assoc. Professor Ho Thanh Phong
HOMEWORK 1
1. Book of Hamdy Taha:
- Chapter 2: Problems 2.12, 14, 15, 17
- Chapter 3: Problems 3.22, 28, 31, 37
2. Book of Hillier & Lierberman
- Chapter 3: Problems 3.2.1, 3.2.3
- Chapter 4: Problems 4.1-7, 4.6-6, 4.6-10
Time allowance: 1 week.
Operations Research - Assoc. Professor Ho Thanh Phong 17
