IEEN 5335
Principles of Optimization
Lecture 6
Dr. Joon-Yeoul Oh
Dept. of Mechanical & Industrial Engineering
Texas A&M University – Kingsville
Agenda
Simplex Algorithm
Some special cases
Big M method
Infeasible
Unbounded
Free variable
Multiple optimal solutions
2
Big M method – Windor Glass Co. problem
3
Big M method – equality constraints
Obtaining an initial BF solution
Apply the artificial-variable technique by introducing a
nonnegative artificial variable into equality constraints
For example,
3x1+2x2 = 18 3x3x1 + 2x2 + a5 = 18
Assign an overwhelming penalty to having “a5 > 0” by
changing the objective function
For example,
z = 3x1 + 5x2 z = 3x1 + 5x2 – Ma5, where M
represents a HUGE positive number.
4
Big M method – Windor Glass Co. problem
Standard form
Max z – 3x1 – 5x2 + Ma5 = 0
s.t. x1 + x3 = 4
2x2 + x4 = 12
3x1 + 2x2 + a5 = 18
all variables >= 0
New z row
z – 3x1 – 5x2 + Ma5 = 0
- M(3x1 + 2x2 + a5 = 18)
z – (3M+3)x1 – (2M+5)x2 = -18M
5
Big M method – Windor Glass Co. problem
6
Two-phase – infeasible
Consider the following problem
Min z = x1
s.t. 2x1 - x2 >= 10
x1 + 2x2 <= 4
x1, x2 >= 0
7
Two-phase – infeasible
Graphical solution
8
Two-phase – infeasible
B.V z1 z2 x1 x2 s1 s2 a1 RHS
z1 -1 0 0 0 0 0 1 0
z2 0 -1 1 0 0 0 0 0
a1 0 0 2 -1 -1 0 1 10
s2 0 0 1 2 0 1 0 4
B.V z1 z2 x1 x2 s1 s2 a1 RHS Ratio
z1 -1 0 -2 1 1 0 0 -10
z2 0 -1 1 0 0 0 0 0
a1 0 0 2 -1 -1 0 1 10 10/2
s2 0 0 1 2 0 1 0 4 4/1
9
Two-phase – infeasible
The coefficients of artificial variables in z1 row are all 0
(phase I is optimal),
but the RHS for z1 is not 0 infeasible!
B.V z1 z2 x1 x2 s1 s2 a1 RHS
z1 -1 0 0 5 1 2 0 -2
z2 0 -1 0 -2 0 -1 0 -4
a1 0 0 0 -5 -1 -2 1 2
x1 0 0 1 2 0 1 0 4
10
Two-phase – unbounded
Consider the following problem
Max z = x1
s.t. 2x1 - x2 <= 10
x1 + 2x2 >= 4
x1, x2 >= 0
11
Two-phase – unbounded
Graphical solution
12
Two-phase – unbounded
B.V z1 z2 x1 x2 s1 s2 a1 RHS
z1 -1 0 0 0 0 0 1 0
z2 0 1 -1 0 0 0 0 0
s1 0 0 2 -1 1 0 0 10
a1 0 0 1 2 0 -1 1 4
B.V z1 z2 x1 x2 s1 s2 a1 RHS Ratio
z1 -1 0 -1 -2 0 1 0 -4
z2 0 1 -1 0 0 0 0 0
s1 0 0 2 -1 1 0 0 10
a1 0 0 1 2 0 -1 1 4 4/2
13
Two-phase – unbounded
B.V z1 z2 x1 x2 s1 s2 a1 RHS
z1 -1 0 0 0 0 0 1 0
z2 0 1 -1 0 0 0 0 0
s1 0 0 2.5 0 1 -0.5 0.5 12
x2 0 0 0.5 1 0 -0.5 0.5 2
B.V z2 x1 x2 s1 s2 RHS Ratio
z2 1 -1 0 0 0 0
s1 0 2.5 0 1 -0.5 12 4.80
x2 0 0.5 1 0 -0.5 2 4.00
14
Two-phase – unbounded
B.V z2 x1 x2 s1 s2 RHS Ratio
z2 1 0 2 0 -1 4
s1 0 0 -5 1 2 2 2/2
x1 0 1 2 0 -1 4
B.V z2 x1 x2 s1 s2 RHS Ratio
z2 1 0 -0.5 0.5 0 5
s1 0 0 -2.5 0.5 1 1 ?
x1 0 1 -0.5 0.5 0 5 ?
Pivot column (entering var.) is selected, but can’t select pivot row
(leaving var.) the problem is unbounded!
15
Free variables
The term refers to variables that have no sign constraint.
In simplex method, the choice of pivot row guarantees that
correctly executed pivots keep nonnegative values for all of
the basic variables.
If we really need “free” variables, we need to adjust the
formulation to accommodate the algorithm.
16
Free variables
How to work with free variables
Replace each free variable by two nonnegative
variables: x = p – n, where p, n >= 0.
For x = -5, let’s look at several different ways to
present x = p – n.
One possible answer would be p = 5 and n = 0
Now, let’s try x = +5:
Note: p for positive and n for negative
17
Free variables - example
Consider the following problem
Min z = x2
s.t. x1 + x2 <= 4
x1 + 3x2 >= 3
x1 >= 0 and x2 is free
18
Free variables - example
Graphical solution
19
Free variables - example
Adjusting formulation
Min z = p2 – n2
s.t. x1 + p2 – n2 + s1 = 4
x1 + 3p2 – 3n2 - s2 = 3
x1, p2, n2, s1, s2 >= 0
Optimal solution:
(x1, p2, n2) = (9/2, 0, 1/2), so (x1, x2) = (9/2, -1/2)
(s1, s2) = (0, 0)
z = -1/2
20
Multiple optimal solution
At the final tableau, check Z-row.
A value in Z-row for basic variable = zero
A value in Z-row for non-basic variable = not zero
However, if a problem has multiple optimal solution,
A value in Z-row for non-basic variable = zero
It means that the variable can be a basic variable.
Select the variable for entering variable and make another
iteration.
You will see different basic variable with same
objective, Z, value.
See next slide.
21
Multiple optimal solution
22
