IE 507

Mathematical Programming Ι

Chapter 3
The Simplex Method
(Part III)
1

Criteria for Entering & Leaving

(1) Entering:
If zk - ck 0, xk may enter the basis.

(2) Leaving:
br b
 

If Min  i : yik 0 , xBr may leave the basis.
yrk 1
i m

yik 


2
 Termination of the Algorithm
Z Z 0 - ( z j - c j ) x j
jR

1. If z j - c j 0, j R  an optimal BFS is obtained

(a) If z j - c j 0, j R
 the current optimal BFS is unique

(b) If z j - c j 0, j R , but at least one NB variable with

z j - c j 0
 Infinite number of alternative optimal solutions.
3

x2

2
Example 3.6 
3

5

Min - 3 x1 + x2 
3


0
s.t. x1 2 x2 x3 4 
1


4
- x1 + x2 x4 = 1 
0

Unique
C optimum
x1
x1 , x2 , x3 , x4 0 
0

0


Figure 3.9 (a)

4
 x2

2
Example 3.6 (cont) 
3

5


3

Min - 2 x1 - 4x2 
0

1


x1

0 
4
 
0
0
 

Termination of the Algorithm (cont)

2. Unboundedness
A BFS with z k - ck 0 for some NB variable xk & yk 0,
then the optimum is unbounded with the objective value of -.
X  B -1b 
 vertex of the ray is the current BFS, X  B  
X N   0 
- yk 
0 
 

& the direction of the ray is d  ,
1 

 
0 
 
that is, cd (C B , C N ) d -C B yk ck - z k ck 0
6
 Note:
k l
P' : Min c  f 
j 1
j j
i 1
i i

k
s.t.  1
j 1
j

j 0, i 0

Fact 1: for any fi cdi 0, the obj  -

 necessary & sufficient conditions for unboundedness.

Optimal objective
Example 3.7 x2
value is unbounded
along this way
Increase x1
Min - x1 - 3 x2 (unblocked)

0

s.t. x1 - 2 x2 4 


3

- x1  x2 3
x2 0

0
x1 , 
0
 
4
x1

0

C = (-1,-3)
Figure 3.10

8
 Procedure of the Simplex Method
Initialization (choose an initial BFS with the basis B)
Loop
(1) Solve the system with X B B -1b b, X N 0 & Z CB X B

(2) Calculate z j - c j CB B -1a j - c j j R

& zk - ck Max z j - c j 
jR

If zk - ck 0  Stop with the optimal BFS;

If zk - ck 0  xk is the entering variable, go to (3)
9

Procedure of the Simplex Method (cont)

(3) Calculate yk B -1ak
If yk 0  Stop with unboundedness;
If yk 0  go to (4)

(4) Calculate the mininum ratio test

br b 
Min  i : yik 0 
yrk 1
i m
yik 
 xBr leaves the basis & xk enters the basis
 Update B & R, then go to (1) 10
The Simplex Method in Tableau Format

M in C X Min Z
s .t. A X b s.t. Z - CB X B - CN X N 0
X 0 BX B NX N b
X B , X N 0
X 
X  B 
X N  BX B NX N b
C 
CB ,CN   X B B -1 NX N B -1b
A 
B, N   CB X B CB B -1 NX N CB B -1b

X B 
Z 0  CB B -1 N - C N X N CB B -1b

11

The Simplex Method in Tableau Format (cont)

X B 
Z 0  CB B -1 N - CN X N CB B -1b

X B B -1 NX N B -1b

Initial Tableau
Z XB XN RHS

Z 1 0 CBB-1N - CN CBB-1b

XB 0 I B -1 N B -1 b

12
AX b  AX IS b S : slack variables
 S b - AX
Z CX  Z - CX 0 
S 0
 Z - CX - 0 
( b - AX ) 0 (1)
B -1 AX B -1 IS B -1b
 B -1 AX B -1 S B -1b ( Row 2)
 C B B -1 AX C B B -1 S C B B -1b (2)

(1) (2 )  Z ( C B B -1 A - C ) X C B B -1 S C B B -1b (Row 1 )

Z X S RHS

Z 1 CBB-1A - C C B B -1 CB B-1b

XB 0 B -1A B -1 B -1 b 13

Min CX Min Z
s.t. AX b s.t. Z (CB B-1 A - C) X CB B-1S CB B-1b
X 0 B-1 AX  B-1S B-1b

Z X S RHS
Z 1 CBB-1A - C C B B -1 CBB-1b

XB 0 B-1A B -1 B -1 b

14
Example 3.9
Min x1 x2 - 4 x3 0 x4 0 x5 0 x6
s.t. x1 x2 2 x3 x4 9
x1 x2 x3 x5 2
- x1 x2 x3 x6 4
x1 , x2 , x3 , x4 , x5 , x6 0

15

Example 3.9 –Iteration 2

z x1 x2 x3 x4 x5 x6 RHS
z 1 3 -5 0 0 0 -4 -16
x4 0 3 -1 0 1 0 -2 1
x5 0 0 2 0 0 1 1 6
x3 0 -1 1 1 0 0 1 4

16
 Interpretation of Entries in the
Simplex Tableau

From row Z C B B -1b - (C B B -1 N - C N ) X N

= C B B -1b - ( z j - c j )x j = C B B -1b ( c j - z j )x j
j R j R

X B B -1b - B -1 NX N
B -1b (- y j ) x j ( y j B -1 a j )
j R

1. X N v.s. Z :
the rate of change of Z is a function of NB variable x j
Z
 c j - z j
x j
17

Interpretation of Entries in the

Simplex Tableau (cont)
2. b v.s. Z :
the rate of change of Z is a function of the RHS vector b
i.e. the availability of the resources.
Z
 CB B -1
b

3. X N v.s. X B :
the rate of change of X B is a function of x j

XB
 - y j
xj
18
 Interpretation of Entries in the
Simplex Tableau (cont)
4. b v.s. X B :
the rate of change of X B is a function of b
 X Bi
 is the ith row of B -1
 b


X B  X B is the j th column of B -1

 B -1 (matrix)  b j
b 

 X Bi
 is the (i , j ) entry o f B -1
 b j

 19

Example 3.10
z x1 x2 x3 x4 x5 x6 RHS
z 1 3 -5 0 0 0 -4 -16
x4 0 3 -1 0 1 0 -2 1
x5 0 0 2 0 0 1 1 6
x3 0 -1 1 1 0 0 1 4

20
Example 3.10 (cont)

21