CHAPTER 3: SIMPLEX METHOD

Introduction:

 In the simplex method, the model is put into the form of table,

& then a number of mathematical steps are performed on the

table (simplex tableau).

 The simplex method moves from one better solution to another

until the best one is found, & then it stops.

 Example of simplex method:

Max Z = 40 X1 + 50X2

s.t X1 + 2X2 ≤ 40 (labor)

4X1 + 3X2 ≤ 120 (clay)

X1, X2 ≥0

1
 Initial tableau:

Basic Quantity 40 50 0 0
Cj Variables (Zj) X1 X2 S1 S2
0 S1 40 1 2 1 0
0 S2 120 4 3 0 1
Zj 0 0 0 0 0
Cj - Z j 40 50 0 0

Basic Quantity 40 50 0 0
Cj Variables (Zj) X1 X2 S1 S2
50 X2 20 0.5 1 0.5 0
0 S2 60 2.5 0 -1.5 1
Zj 1000 25 50 25 0
Cj - Z j 15 0 -25 0

Optimal tableau:

Basic Quantity 40 50 0 0
Cj Variables (Zj) X1 X2 S1 S2
50 X2 8 0 1 0.8 -0.2
40 X1 24 1 0 -0.6 0.4
Zj 1360 40 50 16 6
Cj - Z j 0 0 -16 -6

Solution:

X1 = 24, X2 = 8

S1 = 0, S2 = 0

Z = 1360

2
 Steps:

1. Transform the LP model into standard form.

2. Set up the initial tableau for the basic feasible solution at

the origin & compute the zj & cj – zj (max) @ zj – cj (min)

value.

3. Determine the pivot column by selecting the column with

the highest positive value in the cj – zj @ zj – cj row.

4. Determine the pivot row by dividing the quantity column

values by the pivot column values & select the row with

the minimum nonnegative quotient.

5. Compute the new pivot row values using the formula:

old tableau pivot row values

new tableau pivot row values = pivot number

6. Compute all other row values using the formula:

New = Old Corresponding X Corresponding
tableau tableau coefficient in new tableau in
row row pivot column pivot row
values values value

7. Compute the new zj & cj – zj @ zj – cj row.

3
 8. Determine whether the new solution is optimal by

checking the cj – zj @ zj – cj row. If all the values are 0 or

negative, the solution is optimal. If not, return to step 3 &

repeat the simplex steps.

Converting the Model into Standard Form

 Standard form requires that all constraints be in the form of

equations rather than inequalities.

 A set of rules for transforming all 3 types of model constraints:

Constraint Adjustment Objective function coefficient

Maximization Minimization
≤ (+) a slack 0 0
variable

= (+) an artificial -M M
variable

≥ (-) a surplus 0 0
variable
(+) an artificial -M M
variable

4
 Artificial variable (Ai) does not have a meaning as slack variable

or surplus variable does.

 It is inserted into the equation simply to give a positive solution

at the origin.

 M is a very large positive number.

 Example 1: Maximize Z = 400x1 + 200x2

s.t x1 + x2 = 30

2x1 + 8x2 ≥ 80

x1 ≤ 20

x1, x2 ≥0

Standard form:

5
 Example 2: Minimize Z = 400x1 + 200x2

s.t x1 + x2 = 30

2x1 + 8x2 ≥ 80

x1 ≤ - 20

x1, x2 ≥0

Standard form:

6
 Example 3:

Z = 3X1 + 5X2 + 10X3 + 0S1 + 0S2 – MA1 – MA2

s.t X1 – X3 + A1 = 50

6X2 + S1 = 380

- 40X2 + 60X3 – S2 + A2 = 300

X1, X2, X3, S1, S2, A1, A2 ≥ 0

LP model:

7
Exercises 1:

Transform the following LP model into standard form model.

1. Max Z = 3X1 + 6X2 + 5X3

s.t 3X1 + 2X2 ≤ 18

X1 + X2 ≥ 5

X1 + X3 ≤ 10

X1, X2, X3 ≥ 0

2. Max Z = 8X1 + 7X2

s.t 10X1 + 8X2 = 40

6X1 + 14X2 ≤ 48

X2/X1 ≥ 7/8

X1, X2 ≥ 0

3. Min Z = 4X1 + 8X2

s.t -6X1 + 5X2 ≥ -16

7X1 + 15X2 ≥ 18

X1, X2 ≥ 0

8
Exercises 2:

Transform the following standard form model into LP model.

1. Z = 70X1 + 50X2 + 0S1 + MA1 + MA2 + MA3

s.t 5X1 + 3X2 + A1 = 300

4X1 – S1 + A2 = 40

7X2 + A3 = 500

X1, X2, S1, A1, A2, A3 ≥ 0

2. Z = 150X1 + 200X2 + 180X3 + 0S1 + 0S2 + MA1

s.t X1 + S1 = 40

-7X1 – 3X2 + 5X3 + A1 = 350

X2 + X3 + S2 = 100

X1, X2, X3, S1, S2, A1 ≥ 0

3. Z = 4X1 + 8X2 + 0S1 + 0S2 – MA1 – MA2

s.t -6X1 + 5X2 – S1 + A1 = 16

7X1 + 15X2 – S2 + A2 = 18

X1, X2, S1, S2, A1, A1 ≥ 0

9
Simplex Method For ≤ Constraints

Example:

Max Z = 5X1 + 10X2 + 15X3

s.t X1 + X2 ≤ 7

X2 + X3 ≤ 10

2X1 + 2X2 + 2X3 ≤ 30

X1, X2, X3 ≥ 0

Standard form:

10
Initial tableau:

Cj Basic Quantity
Var.

Zj

Cj Basic Quantity
Var.

Zj

11
Cj Basic Quantity
Var.

Zj

12
 Corresponding New tableau
Old row - Coefficient in X Pivot = New tableau
Column Value Pivot column Row value Row value

Corresponding New tableau

Old row - Coefficient in X Pivot = New tableau
Column Value Pivot column Row value Row value

13
 Corresponding New tableau
Old row - Coefficient in X Pivot = New tableau
Column Value Pivot column Row value Row value

Corresponding New tableau

Old row - Coefficient in X Pivot = New tableau
Column Value Pivot column Row value Row value

14
Simplex Method For ≥ Constraints

Example:

Min Z = 6X1 + 3X2

s.t 2X1 + 4X2 ≥ 16

4X1 + 3X2 ≥ 24

X1, X2 ≥ 0

Standard form:

15
Initial tableau:

Cj Basic Quantity
Var.

Zj

Cj Basic Quantity
Var.

Zj

16
Cj Basic Quantity
Var.

Zj

Cj Basic Quantity
Var.

Zj

17
 Corresponding New tableau
Old row - Coefficient in X Pivot = New tableau
Column Value Pivot column Row value Row value

Corresponding New tableau

Old row - Coefficient in X Pivot = New tableau
Column Value Pivot column Row value Row value

18
 Corresponding New tableau
Old row - Coefficient in X Pivot = New tableau
Column Value Pivot column Row value Row value

19
Simplex Method For Mixed Constraints ( ≥, =, ≤ )

Example:

Max Z = 400X1 + 200X2

s.t X1 + X2 = 30

2X1 + 8X2 ≥ 80

X1 ≤ 20

X1, X2 ≥ 0

Standard form:

20
Initial tableau:

Cj Basic Quantity
Var.

Zj

Cj Basic Quantity
Var.

Zj

21
Cj Basic Quantity
Var.

Zj

Cj Basic Quantity
Var.

Zj

22
 Corresponding New tableau
Old row - Coefficient in X Pivot = New tableau
Column Value Pivot column Row value Row value

Corresponding New tableau

Old row - Coefficient in X Pivot = New tableau
Column Value Pivot column Row value Row value

23
 Corresponding New tableau
Old row - Coefficient in X Pivot = New tableau
Column Value Pivot column Row value Row value

Corresponding New tableau

Old row - Coefficient in X Pivot = New tableau
Column Value Pivot column Row value Row value

24
 Corresponding New tableau
Old row - Coefficient in X Pivot = New tableau
Column Value Pivot column Row value Row value

Corresponding New tableau

Old row - Coefficient in X Pivot = New tableau
Column Value Pivot column Row value Row value

25
 The basic feasible solution in the initial simplex tableau is the

origin where all the decision variables equal zero.

 The quantity column values are the solution values for the

variables in the basic feasible solution.

 The cj values are the contribution to profit (or cost) for each

variable.

 The zj row values are computed by multiplying the cj column

values by the variable column values and summing.

 The variable with the largest positive cj – zj @ zj – cj value is the

entering variable (pivot column).

 The leaving variable is determined by dividing the quantity

values by the pivot column values & selecting the minimum

possible value or zero (pivot row).

26
 The pivot number is the number at the intersection of the pivot

column & row.

 The solution is optimal when all cj – zj @ zj – cj ≤ 0.

 Artificial variables are assigned a large cost in the objective

function to eliminate them from the final solution.

 Once an artificial variable is selected as the leaving variable, it

will never reenter the tableau, so it can be eliminated.

27
Irregular types of LP Problems

1. Multiple Optimal Solutions

 Alternate optimal solutions have the same Z value but

different variables values.

 Example:

Max Z=40 X 1 +30 X 2

s .t :

X 1 +2 X 2≤40
4 X 1+3 X 2≤120
X 1 , X 2≥0

The optimal tableau for this problem is as follows:

Basic Quantity 40 30 0 0
Cj Variables (Zj) X1 X2 S1 S2
0 S1 10 0 5/4 1 -1/4
40 X1 30 1 ¾ 0 ¼
Zj 1200 40 30 0 10
Cj - Zj 0 0 0 -10

To get the alternate solution, proceed the tableau i.e. X2 enter

the tableau and X1 leave.

28
2. An Infeasible Problem

 An infeasible problem has an artificial variable in the final

simplex tableau.

 Example:

Basic Quantity 5 3 0 0 0 -M -M
Cj Var. X1 X2 S1 S2 S3 A1 A2
3 X2 4 2 1 ½ 0 0 0 0
-M A1 4 1 0 0 -1 0 1 0
-M A2 2 -2 0 -1/2 0 -1 0 1
Zj 12-6M 6+M 3 3/2 M M -M -M
+
M/2
Cj – Zj -1-M 0 -3/2 -M -M 0 0
–
M/2

3. An Unbounded Problem

 A pivot row cannot be selected for an unbounded problem.

Basic 4 2 0 0 M
Cj Variable Quantity X1 X2 S1 S2 A1
s
M A1 4 1 0 -1 0 1
0 S2 2 0 1 0 1 0
Zj 4M M 0 -M 0 M
Cj – Zj 4-M 2 M 0 0

29
4. Tie For the Pivot Column

 Sometimes when selecting the pivot column, the greatest

positive cj – zj (or zj – cj) row values are the same.

5. Tie For the Pivot Row

 Example:

Basic Quantity 4 6 0 0 0
Cj Var. X1 X2 S1 S2 S3
0 S1 12 6 0 1 -4 0
6 X2 3 0 1 0 1 0
0 S3 10 5 0 0 -10 1
Zj 18 0 6 0 6 0
Cj – Zj 4 0 0 -6 0

6. Negative Quantity Values

 Standard form for simplex solution requires positive (right-

hand-side) RHS values.

 Example:

-6x1 + 2x2 ≥ -30

(-1) (-6x1 + 2x2 ≥ -30)

6x1 - 2x2 ≤ 30

30