Lecture 3: The Simplex Method

15.093 Optimization Methods Lecture 3: The Simplex Method 1 Outline � � � � � � Reduced Costs Optimality conditions Improving the cost Unboundness The Simplex algorithm The Simplex algorithm on degenerate problems 2 Matrix View x � (xB ; xN ) min s:t: c0 x Ax � b x�0 Slide 1 Slide 2 xB basic variables xN non-basic variables A � [B; N ] Ax � b ) � B � xB +� N � xN � b ) xB + B NxN � B b ) xB � B � b � B � NxN 1 1 1 1 2.1 Reduced Costs z � c0B xB + c0N xN � c0B (B �1 b � B �1 N xN ) + c0N xN � c0B B �1 b + (c0N � c0B B �1N )xN Slide 3 cj � cj � c0B B �1Aj 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 ) BdB + P Aidi � 0 i2N ) dB � � P B �1 Ai di i2N ) c0 d � c0B dB + P cidi P i2N P � (ci � c0B B �1Ai )di � cidi i2N Slide 5 Slide 6 i2N � Since y � 0 and xi � 0; i 2 N, then di � yi � xi � 0; i 2 N � c0 d � c0 (y � x) � 0 ) c0 y � c0 x ) x optimal (b) in BT, Theorem 3.1 3 Improving the Cost Slide 7 � Suppose cj � cj � c0B 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 c0y � c0x � � � c d0 � � � (cB dB + cj dj ) � � � (cj � c0B B � Aj ) Slide 8 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 1 Slide 9 x3 (0,0,3) (1,0,3) (2,0,2) (0,1,3) x1 (0,2,0) (2,2,0) x2 5 Improvement If di � 0, then xi + �di � 0 ) � � � xdi i � x� ) �� � fijmin � di di < g i 0 ) �� � min fi�1;:::;mjdB(i) <0g 5.1 Example � xB i � � ( ) dB(i) 1 2 1 0 0 3 3 1 0 1 1 4 1 0 0 0 5 0 1 0 0 �4 �2 �3 �6 �0 x3 x3 3x2+ x3 x2; x3 A A A A A A A 1 1 0 0 Slide 11 �2x3 min x1+ 5x2 s:t: x1+ x2+ x1 x1; 2 66 4 Slide 10 7 6 0 0 1 0 0 0 0 1 B � [A1 ; A3; A6; A7] BFS: x � (2; 0; 2; 0; 0;1;4)0 3 77 5 0x BB x BB x BB x BB x @x 1 2 3 4 5 6 x7 1 CC 0 4 1 CC B 2 C CC � B@ 3 CA CC 6 A Slide 12 Slide 13 Slide 14 3 x3 (0,0,3) (1,0,3) (2,0,2) (0,1,3) x1 (0,2,0) (2,2,0) x2 21 1 0 03 2 0 1 B � 664 10 01 01 00 775 ; B� � 664 �11 �11 0 1 0 1 0 1 �1 1 d B d C d � 1; d � d � 0; B @ d CA � �B� A 1 1 5 2 3 4 1 6 d7 5 3 77 c0 � (0; 7; 0; 2; �3; 0;0) 5 1 �1 B 1 CC �B @ �1 A 0 0 0 0 1 0 0 01 �1 Slide 15 y0 � x0 + �d0 � (2 � �; 0; 2 + �; 0; �; 1 � �; 4 � �) What happens as � increases� � � �� � minfi�1;:::;mjdB i < g � xBdi i � � � min � (�21) ; � (�11) ; � (�41) � 1: l � 6 (A6 exits the basis). New solution y � (1; 0; 3; 0; 1; 0;3)0 New basis2B � (A1 ; A3 ;3A5; A7) 2 1 1 0 0 1 0 �1 66 1 0 1 0 77 �1 66 0 0 1 B � 4 0 1 0 0 5 ; B � 4 �1 1 1 0 1 0 1 0 0 �1 c0 � c0 � c0B B�1A � (0; 4; 0; �1; 0; 3; 0) Need to continue, column A4 enters the basis. ( ) ( ) 0 4 0 0 0 1 3 77 5 Slide 16 Slide 17 6 Correctness � xdB(l) � i�1;:::;m;d min B(l) � xB i � � � �� Slide 18 ( ) B(i)<0 dB(i) Theorem � B � fAB i ;i�6 l ; Aj g basis � y � x + �� d is a BFS associated with basis B . ( ) 7 The Simplex Algorithm 1. Start with basis B � [AB(1) ; : : :; AB(m) ] and a BFS x. 2. Compute cj � cj � c0B B �1Aj � If cj � 0; x optimal; stop. � Else select j : cj � 0. 3. Compute u � �d � B �1Aj . � If u � 0 ) cost unbounded; stop � Else xB(i) uB(l) 4. �� � 1�i�min � u m;u >0 u i i Slide 19 Slide 20 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; c0d � 0 and optimal cost is �1. 5 7.2 Degenerate problems � �� can equal zero (why�) ) y � x, although B 6� B . � Even if �� � 0, there might be a tie Slide 22 xB(i) min 1�i�m;ui >0 ui ) next BFS degenerate. � Finite termination not guaranteed; cycling is possible. 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