BUST 252 QUANTITATIVE

BUSINESS ANALYSIS

Chapter 5– Extra Examples for Simplex Method, Big M

Method, Special Cases

© 2003 ThomsonTM/South-Western Slide 1

 5th Week
Examples for Simplex Method and Big M
Method
 Extra Examples for Simplex Method
 Big M Method
 When do we need Big M Method?
 Special Cases for Optimal Solutions of Simplex
Method

© 2003 ThomsonTM/South-Western Slide 2

 Overview of the Simplex Method

 Steps Leading to the Simplex Method

Put In
Formulate Put In Execute
Tableau
Problem Standard Simplex
(Canonical)
as LP Form Method
Form

© 2003 ThomsonTM/South-Western Slide 3

 Example 2
Max z = 2x1 + 6x2 + 5x3
s.t. x1 + x2 + x3 < 40
x1 + 2x2 < 20
x1, x2, x3 > 0

Initial (the first) Tableau [1st Stage]

© 2003 ThomsonTM/South-Western Slide 4

 Example 2
Initial (the first) Tableau [1st Stage]

Iteration 1 [ 2nd Stage ]

© 2003 ThomsonTM/South-Western Slide 5

 Example 2
Iteration 1 [ 2nd Stage ]

Iteration 2 [ 3rd Stage ]

© 2003 ThomsonTM/South-Western Slide 6

 Example 2

 Iteration 2 (continued) – Final Tableau

x1 s2 s1 x3 x2

Basic cB 2 0 0 5 6
x3 5 1/2 -1/2 1 1 0 30
x2 6 1/2 1/2 0 0 1 10

zj 5.5 .5 5
cj - zj -3.5 -.5 -5

© 2003 ThomsonTM/South-Western Slide 7

 Extra Note : How to find the next table using
Elementary row operations (an alternative method)
 Elementary row operations consist of three basic
operations performed on the rows of a matrix, which
simplify the matrix without changing its properties.

 These operations are especially used in linear algebra

and solving methods. The operations are as follows:

•Multiplying a row by a scalar

•Adding (or subtracting) one row to/from another
•Interchanging two rows

© 2003 ThomsonTM/South-Western Slide 8

 Elementary row operations (an alternative
method) for the initial Simplex table of Example 2

 Let's write this table as a system of linear equations

𝑥1 + 𝑥2 + 𝑥3 + 𝑆1 = 40
𝑥1 + 2𝑥2 + 𝑆2 = 20

If we recall, at this stage, the entering and leaving variables are 𝑥2 and 𝑆2 ,
respectively.
In other words, in the second equation, 𝑥2 will be the basic variable instead of
𝑆2 .
© 2003 ThomsonTM/South-Western Slide 9
 𝑥2 will be the basic variable instead of 𝑆2 .
 This means that 𝑥2 should not appear in the first equation (in other
words, the coefficient of 𝑥2 in the first equation has to be zero)
and should appear with a coefficient of 1 in the second equation.
 To do this, some elementary row operations must be performed.
• For example, firstly, add -1/2 times the second equation to the
first equation (to make zero the coefficient of 𝑥2 in the first
equation).

𝑥1 + 𝑥2 + 𝑥3 + 𝑆1 = 40
𝑥1 + 2𝑥2 + 𝑆2 = 20 -1/2

1 1
𝑥 + 𝑥3 + 𝑆1 − 𝑆2 = 30
2 1 2
𝑥1 + 2𝑥2 + 𝑆2 = 20

© 2003 ThomsonTM/South-Western Slide 10

 •Then, multiply the second equation by 1/2. (to make
one the coefficient of 𝑥2 in the second equation).

1 1
𝑥1 + 𝑥3 + 𝑆1 − 𝑆2 = 30
2 2
𝑥1 + 2𝑥2 + 𝑆2 = 20 1/2

1 1
𝑥 + 𝑥3 + 𝑆1 − 𝑆2 = 30
2 1 2
1 1
𝑥 + 𝑥2 + 𝑆2 = 10
2 1 2

By doing these elemantary matrix operations, we have found the same (2nd stage
table in the Simplex Method)

© 2003 ThomsonTM/South-Western Slide 11

 Example 3
Max z = 3x1 + 6x2
s.t. 2x1 + 4x2 < 160
6x1 + 2x2 < 180
x2 < 35
x1, x2, x3 > 0

Initial (the first) Tableau [1st Stage]

© 2003 ThomsonTM/South-Western Slide 12

 Example 3
Initial (the first) Tableau [1st Stage]

Iteration 1 [ 2nd Stage ]

© 2003 ThomsonTM/South-Western Slide 13

 Example 3
Iteration 1 [ 2nd Stage ]

Iteration 2 [ 3rd Stage ]

© 2003 ThomsonTM/South-Western Slide 14

 Example 3

 Iteration 2 (continued) – Final Tableau

x1 s2 s1 x3 x2

Basic cB 2 0 0 5 6
x3 5 1/2 -1/2 1 1 0 30
x2 6 1/2 1/2 0 0 1 10

zj 5.5 .5 5
cj - zj -3.5 -.5 -5

© 2003 ThomsonTM/South-Western Slide 15

 Big-M Method
(Reminder of Some of the steps of setting up the initial tableau)
 If the problem is a minimization problem, multiply the
objective function by -1.
 If the problem formulation contains any constraints with
negative right-hand sides, multiply each constraint by -1.
 Subtract a surplus variable and add an artificial variable to
each > constraint.
 Add an artificial variable to each = constraint.
 Set each artificial variable's coefficient in the objective
function equal to -M, where M is a very large number (Big M
Method).
 Each slack and artificial variable becomes one of the basic
variables in the initial basic feasible solution.
 We need Big-M Method, if we have any artificial variable as
a basic variable in canonical (tableau) form
© 2003 ThomsonTM/South-Western Slide 16
 Example: Big-M Method

© 2003 ThomsonTM/South-Western Slide 17

 Example: Big-M Method
Max z = 3x1 + 6x2
s.t. 2x1 + 4x2 < 160
6x1 + 2x2 < 180
x2 < 35
x1, x2, x3 > 0

Initial (the first) Tableau [1st Stage]

© 2003 ThomsonTM/South-Western Slide 18

 Example: Big-M Method
Initial (the first) Tableau [1st Stage]

Iteration 1 [ 2nd Stage ]

© 2003 ThomsonTM/South-Western Slide 19

 Example: Big-M Method
Iteration 1 [ 2nd Stage ]

Iteration 2 [ 3rd Stage ]

© 2003 ThomsonTM/South-Western Slide 20

 Example: Big-M Method

 Iteration 2 (continued) – Final Tableau

x1 s2 s1 x3 x2

Basic cB 2 0 0 5 6
x3 5 1/2 -1/2 1 1 0 30
x2 6 1/2 1/2 0 0 1 10

zj 5.5 .5 5
cj - zj -3.5 -.5 -5

© 2003 ThomsonTM/South-Western Slide 21

 Special Cases

 Infeasibility
 Unboundedness
 Alternative Optimal Solution
 Degeneracy

© 2003 ThomsonTM/South-Western Slide 22

 Infeasibility

 Infeasibility is detected in the simplex method when an

artificial variable remains positive in the final tableau.

© 2003 ThomsonTM/South-Western Slide 23

 Example: Infeasibility

 LP Formulation

MAX 2x1 + 6x2

s. t. 4x1 + 3x2 < 12
2x1 + x2 > 8

x1, x2 > 0

© 2003 ThomsonTM/South-Western Slide 24

 Example: Infeasibility

 Final Tableau

x1 x2 s1 s2 a2
Basic CB 2 6 0 0 -M
x1 2 1 3/4 1/4 0 0 3
a2 -M 0 -1/2 -1/2 -1 1 2
zj 2 (1/2)M (1/2)M M -M -2M
+3/2 +1/2 +6
cj - zj 0 -(1/2)M -(1/2)M -M 0
+9/2 -1/2

© 2003 ThomsonTM/South-Western Slide 25

 Example: Infeasibility

In the previous slide we see that the tableau is the

final tableau because all cj - zj < 0. However, an
artificial
variable is still positive, so the problem is infeasible.

© 2003 ThomsonTM/South-Western Slide 26

 Unboundedness

 A linear program has an unbounded solution if all

entries in an entering column are non-positive.

© 2003 ThomsonTM/South-Western Slide 27

 Example: Unboundedness

 LP Formulation

MAX 2x1 + 6x2

s. t. 4x1 + 3x2 > 12
2x1 + x2 > 8

x1, x2 > 0

© 2003 ThomsonTM/South-Western Slide 28

 Example: Unboundedness

 Final Tableau

x1 x2 s1 s2

Basic cB 3 4 0 0
x2 4 3 1 0 -1 8
s1 0 2 0 1 -1 3
zj 12 4 0 -4 32
cj - zj -9 0 0 4

© 2003 ThomsonTM/South-Western Slide 29

 Example: Unboundedness

In the previous slide we see that c4 - z4 = 4 (is

positive), but its column is all non-positive. This
indicates that the problem is unbounded.

© 2003 ThomsonTM/South-Western Slide 30

 Alternative Optimal Solution

 A linear program has alternate optimal solutions if the

final tableau has a cj - zj value equal to 0 for a non-basic
variable.

© 2003 ThomsonTM/South-Western Slide 31

 Example: Alternative Optimal Solution

 Final Tableau

x1 x2 x3 s1 s2 s3 s4
Basic cB 2 4 6 0 0 0 0
s3 0 0 0 2 4 -2 1 0 8
x2 4 0 1 2 2 -1 0 0 6
x1 2 1 0 -1 1 2 0 0 4
s4 0 0 0 1 3 2 0 1 12
zj 2 4 6 10 0 0 0 32
cj – zj 0 0 0 -10 0 0 0

© 2003 ThomsonTM/South-Western Slide 32

 Example: Alternative Optimal Solution

 New Tableau

x1 x2 x3 s1 s2 s3 s4
Basic cB 2 4 6 0 0 0 0
s3 0 0 -1 0 2 -1 1 0 2
x3 6 0 .5 1 1 - .5 0 0 3
x1 2 1 .5 0 2 1.5 0 0 7
s4 0 0 - .5 0 2 2.5 0 1 9
zj 2 4 6 10 0 0 0 32
cj - zj 0 0 0 -10 0 0 0

© 2003 ThomsonTM/South-Western Slide 33

 Example: Alternative Optimal Solution

In the previous slide we see that the optimal

solution is:
x1 = 4, x2 = 6, x3 = 0, and z = 32
Note that x3 is non-basic and its c3 - z3 = 0. This 0
indicates that if x3 were increased, the value of the
objective function would not change.
Another optimal solution can be found by choosing
x3 as the entering variable and performing one iteration
of the simplex method. The new tableau on the next
slide shows an alternative optimal solution is:
x1 = 7, x2 = 0, x3 = 3, and z = 32

© 2003 ThomsonTM/South-Western Slide 34

 Degeneracy

 A degenerate solution to a linear program is one in

which at least one of the basic variables equals 0.
 This can occur at formulation or if there is a tie for the
minimizing value in the ratio test to determine the
leaving variable.
 When degeneracy occurs, an optimal solution may have
been attained even though some cj – zj > 0.
 Thus, the condition that cj – zj < 0 is sufficient for
optimality, but not necessary.

© 2003 ThomsonTM/South-Western Slide 35

 End of 5th Week

© 2003 ThomsonTM/South-Western Slide 36