15.081J/6.251J Introduction to Mathematical Programming Lecture 5: The Simplex Method I1 Outline Slide 1 • Reduced Costs • Optimality conditions • Improving the cost • Unbo undness • The Simplex algorithm • The Simplex algorithm on degenerate problems 2 Matrix View Slide 2 ′ min c x s.t. Ax = b x ≥ 0 x = (xB , xN ) xB basic variables xN non-basic variables A = [B, N ] Ax = b ⇒ B · xB + N · xN = b ⇒ xB + B−1N xN = B−1b ⇒ xB = B−1b − B−1N xN 2.1 Reduced Costs Slide 3 ′ ′ z = cB xB + cN xN = c ′ B (B−1b − B−1NxN ) + c ′ N xN = c ′ B−1b + (c ′ − c ′ B−1N )xNB N B cj = cj − c ′ B B−1Aj reduced cost 2.2 Optimality Conditions Slide 4 Recall Theorem: • x BFS associated with basis B • c re duced costs Then • If c ≥ 0 ⇒ x optimal • x optimal and non-degenerate ⇒ c ≥ 0 1� � � � 3 Improving the Cost Slide 5 • Suppose cj = cj − cB ′ B−1Aj < 0 Can we improve the cost? • Let dB = −B−1Aj dj = 1, di = 0, i � B(1), . . . , B(m), j. = • Let y = x + θ · d, θ > 0 scalar Slide 6 ′ ′ c y − c x = θ · c ′ d ′ = θ · (cB dB + cj dj ) = θ · (cj − c ′ B−1Aj )B = θ · cj Thus, if cj < 0 cost will decrease. 4 Unboundness Slide 7 • Is y = x + θ · d feasible? Since Ad = 0 ⇒ Ay = Ax = b • y ≥ 0 ? If d ≥ 0 ⇒ x + θ · d ≥ 0 ∀ θ ≥ 0 ⇒ objective unbounded. 5 Improvement Slide 8 If di < 0, then xi xi + θdi ≥ 0 ⇒ θ ≤ − di ⇒ θ ∗ = min − xi {i|di<0} di ⇒ θ ∗ = min − xB(i) {i=1,...,m|dB(i) <0} dB(i) 5.1 Example Slide 9 min x1+ 5x2 −2x3 s.t. x1+ x2+ x3 ≤ 4 x1 ≤ 2 x3 ≤ 3 3x2+ x3 ≤ 6 x1, x2, x3 ≥ 0 2� � � � x3 x1 (0,0,3) (1,0,3) (2,0,2) (2,2,0) (0,2,0) (0,1,3) Slide 10 Ax1 2 A2 A3 A4 A5 A6 A7 x1 Slide 11   x2    1 1 1 1 0 0 0 4  x3   1 0 0 0 1 0 0    2     x4  =   0 0 1 0 0 1 0  3   x5  0 3 1 0 0 0 1 6  x6  x7 B = [A1, A3, A6, A7] BFS: x = (2, 0, 2, 0, 0, 1, 4) ′ Slide 12     1 1 0 0 0 1 0 0 ′ B =  1 0 0 0  , B−1 =  1 −1 0 0  c = (0, 7, 0, 2, −3, 0, 0)  0 1 1 0   −1 1 1 0  0 1 0 1 −1 1 0 1     d1 −1     d5 = 1, d2 = d4 = 0,  d3  = −B−1A5 =  1  Slide 13  d6   −1  d7 −1 ′ ′ y = x + θ d ′ = (2 − θ, 0, 2 + θ, 0, θ, 1 − θ, 4 − θ) What happe ns as θ increases? θ ∗ = min{i=1,...,m|dB(i)<0} −xBdi (i) = min −(−21) , −(−11) , −(−41) = 1. l = 6 (A6 exits the basis). New solution y = (1, 0, 3, 0, 1, 0, 3) ′ Slide 14 New basis B = (A1, A3, A5, A7) Slide 15 3� � x3 x1 (0,0,3) (1,0,3) (2,0,2) (2,2,0) (0,2,0) (0,1,3)  1 1 0 0   1 0 −1 0   x21 0 1 0  −1  0 0 1 0   B =  , B =   0 1 0 0  −1 1 1 0  0 1 0 1 0 0 −1 1 ′ ′ ′−1 c = c − c B A = (0, 4, 0, −1, 0, 3, 0) B Need to c ontinue, column A4 enters the basis. 6 Correctness Slide 16 − xB(l) = min − xB(i) = θ ∗ dB(l) i=1,...,m,dB(i)<0 dB(i) Theorem • B = {AB(i) ,i�=l, Aj } basis • y = x + θ ∗d is a BFS associated with basis B. 7 The Simplex Algorithm Slide 17 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. 4Slide 18 3. Compute u = −d = B−1Aj . • If u ≤ 0 ⇒ cost unbounded; stop • Else 4. θ ∗ = min xB(i) = uB(l) 1≤i≤m,ui >0 ui ul 5. Form a new basis by replacing AB(l) with Aj . 6. yj = θ ∗ yB(i) = xB(i) − θ ∗ ui 7.1 Finite Convergence Slide 19 Theorem: • P = {x | Ax = b, x ≥ 0} � ∅= • Every BFS non-degenerate Then • Simplex method terminates after a finite 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 −∞. 7.2 Degenerate problems Slide 20 • θ ∗ can equal zero (why?) ⇒ y = x, although B �= B. • Even if θ ∗ > 0, there might b e a tie xB(i) min ⇒ 1≤i≤m,ui >0 ui next BFS degenerate. • Finite termination not guaranteed; cycling is possible. Slide 21 -x y f g h g .x2=0 x3=0x4=0 x5=0 x6=0 x1=0 c 57.3 Pivot Selection Slide 22 • Choices for the entering column: (a) Choose a column Aj , with cj < 0, whose reduced cost is the most negative. (b) Choose a column with cj < 0 for which the corresponding cost de- crease θ ∗|cj | is largest. • Choices for the exiting column: smallest subscript rule: out o f all variables eligible to exit the basis , choo se one with the smallest subscript. 7.4 Avoiding Cycling Slide 23 • Cycling can be avoided by carefully selecting which var iables 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. 6MIT OpenCourseWarehttp://ocw.mit.edu 6.251J / 15.081J Introduction to Mathematical Programming Fall 2009 For information about citing these materials or our Terms of Use, visit: