Optimization Methods The Simplex Method

Optimization Method 1 Outline Slide 1 Reduced Costs Optimality conditions Improving the cost Unboundness The Simplex algorithm The Simplex algorithm on degenerate problems 2 Matrix View x = (xB
xN ) Slide 2 cx Ax = b x
0 min s:t: 0 xB basic variables xN non-basic variables A = B
N ] Ax = b ) 1 B  xB +1N  xN = b ) xB + B N xN = B b ) xB = B 1b ; B 1N xN ; ; ; ; 2.1 Reduced Costs z = cB xB + cN xN = cB (B 1 b ; B 1 N xN ) + cN xN = cB B 1 b + (cN ; cB B 1N )xN 0 0 0 0 ; ; ; 0 cj = cj ; cB B 0 1 ; Slide 3 0 0 ; Aj reduced cost 2.2 Optimality Conditions Theorem: x BFS associated with basis B c reduced costs Then If c
0 ) x optimal x optimal and non-degenerate ) c
0 1 Slide 4 2.3 Proof y arbitrary feasible solution d = y ; x ) Ax = Ay = b ) Ad = 0 P Ad =0 ) BdB + i i iP N ) dB = ; B 1Aidi i N P cd ) c d = cB dB + i i i N P P = (ci ; cB B 1Ai )di = cidi Slide 5 2 ; 2 0 0 2 0 i2N Slide 6 ; i2N Since y 0 and xi = 0
i 2 N , then di = yi ; xi
0
i 2 N c d = c (y ; x)
0 ) c y
c x ) x optimal (b) in BT, Theorem 3.1  0 0 0 0 3 Improving the Cost Slide 7 Suppose cj = cj ; cB B 1Aj < 0 Can we improve the cost? Let dB = ;B 1 Aj dj = 1
di = 0
i 6= B(1)
: : :
B (m)
j . Let y = x +   d
 > 0 scalar 0 ; ; c y;c x = c d =   (cB dB + cj dj ) =   (cj ; cB B 1 Aj ) 0 Slide 8 0 0 0 0 Thus, if cj < 0 cost will decrease. ; =   cj 4 Unboundness Is y = x +   d feasible? Since Ad = 0 ) Ay = Ax = b y
0? If d
0 ) x +   d
0 8 
0 ) objective unbounded. 2 Slide 9 5 Improvement If di < 0, then xi + di
0 )   ; xdi i
x i )  = imin d <0 ) = i=1
:::
m mind <0 Bi  f j i ; g f j di ( ) 5.1 Example xB(i)
; dB(i) g min x1+ 5x2 s:t: x1+ x2+ x1 x1
2 66 4 1 0 0 3 1 0 1 1 1 0 0 0 0 1 0 0 Slide 11 ;2x3 x3 4 2 3 6
0 x3 3x2+ x3 x2
x3 A1 A2 A3 A4 A5 A6 A7 1 1 0 0 Slide 10 0 0 1 0 0 0 0 1 B = A1
A3
A6
A7] BFS: x = (2
0
2
0
0
1
4) 3 77 5 0x BB x12 BB x3 BB x4 BB x5 @ x6 x7 1 C 0 1 CCC B 24 C CC = B@ 3 CA CC 6 A Slide 12 Slide 13 Slide 14 0 3 21 1 0 03 2 0 B = 664 10 01 01 00 775
B 1 = 664 ;11 0 1 0 1 0 1 ;1 d1 B C = ;B d3 C d5 = 1
d2 = d4 = 0
B @d A 1 ;1 1 1 3 0 0 0 0 77 c = (0
7
0
2
;3
0
0) 1 05 0 01 1 ;1 B 1C 1 A 5=B @ ;1 CA 6 ;1 d7 y = x + d = (2 ; 
0
2 + 
0

1 ; 
4 ; ) What happens as  increases?  = min i=1
:::
m dB i < ; xBdi i = min ; ( 21)
; ( 11)
; ( 41) = 1: l = 6 (A6 exits the basis). New solution y = (1
0
3
0
1
0
3) New basis2B = (A1
A3
3A5
A7) 2 3 1 1 0 0 1 0 ;1 0 B = 664 10 01 10 00 757
B 1 = 664 ;01 01 11 00 775 0 1 0 1 0 0 ;1 1 1 c = c ; cB B A = (0
4
0
;1
0
3
0) Need to continue, column A4 enters the basis. ; ; 0  j f ; ; ( ) 0g ; 0 ; 0 0 0 Slide 15 0 0 ( ) 0 ; 4 Slide 16 Slide 17 6 Correctness ; xB(l) = min dB(l) i=1
:::
m
d Bi< ( ) 0 ; xB(i)
dB(i) =  Slide 18  Theorem B = fAB i
i=l
Aj g basis y = x +  d is a BFS associated with basis B. ( ) 6  7 The Simplex Algorithm 1. Start with basis B = AB(1)
: : :
AB(m) ] and a BFS x. 2. Compute cj = cj ; cB B 1Aj If cj
0 x optimal stop. Else select j : cj < 0. Slide 19 ; 0 3. Compute u = ;d = B 1Aj . If u  0 ) cost unbounded stop Else xB(i) uB(l) = u 4.  = 1 i min m
u >0 u Slide 20 ;  i i   l 5. Form a new basis by replacing AB(l) with Aj . 6. yj =  yB(i) = xB(i) ;  ui   7.1 Finite Convergence Slide 21 Theorem: P = fx j Ax = b
x
0g = 6 Every BFS non-degenerate Then Simplex method terminates after a nite number of iterations At termination, we have optimal basis B or we have a direction d : Ad = 0
d
0
c d < 0 and optimal cost is ;1. 0 5 7.2 Degenerate problems 6 B.  can equal zero (why?) ) y = x, although B = Even if  > 0, there might be a tie xB(i) min 1 i m
ui>0 ui ) next BFS degenerate. Finite termination not guaranteed cycling is possible.  Slide 22    7.3 Avoiding Cycling Cycling can be avoided by carefully selecting which variables enter and exit the basis. Example: among all variables cj < 0, pick the smallest subscript among all variables eligible to exit the basis, pick the one with the smallest subscript. 6 Slide 23