15.081J/6.251J Introduction to Mathematical Programming Lecture 6: The Simplex Method II1 Outline Slide 1 • Revised Simplex method • The full tableau implementatio n • Anticycling 2 Revised Simplex Slide 2 Initial data: A, b, c 1. Start with basis B = [AB(1), . . . , AB(m)] and B−1 . 2. Compute p ′ = c ′ BB−1 cj = cj − p ′ Aj • If cj ≥ 0; x optimal; stop. • Else select j : cj < 0. Slide 3 3. Compute u = 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 B by replacing AB(l) with Aj. 6. yj = θ∗ , yB(i) = xB(i) − θ∗ ui Slide 4 7. Form [B−1|u] 8. Add to each one of its rows a multiple of the lth row in order to make the last column equal to the unit vector el. −1 The first m columns is B . 2.1 Example Slide 5 min x1+ 5x2 −2x3 s.t. x1+ x2+ x3 ≤ 4 x1 ≤ 2 x3 ≤ 3 3x2+ x3 ≤ 6 x1, x2, x3 ≥ 0 Slide 6 1� � B = {A1, A3, A6, A7}, BFS: x = (2, 0, 2, 0, 0, 1, 4) ′ ′ c = (0, 7, 0, 2, −3, 0, 0) 1 1 0 0 0 1 0 0 1 0 0 0 B−1 1 −1 0 0 B = , = 0 1 1 0 −1 1 1 0 0 1 0 1 −1 1 0 1 (u1, u3, u6, u7) ′ = B−1A5 = (1, −1, 1, 1) ′ θ∗ = min 21 , 11 , 41 = 1, l = 6 l = 6 (A6 exits the basis ). Slide 7 0 1 0 0 1 [B−1|u] = 1 −1 0 0 −1 −1 1 1 0 1 −1 1 0 1 1 1 0 −1 0 −1 0 0 1 0 ⇒ B = −1 1 1 0 0 0 −1 1 2.2 Practical issues Slide 8 • Numerical Stability B−1 needs to be computed from scratch o nce in a while, as errors accu-mulate • Sparsity B−1 is represented in terms of sparse triangular matrices 3 Full tableau implementation Slide 9 −c ′ B−1b c ′ − c ′ B−1AB B B−1b B−1A or, in more detail, ′ −cBxB xB(1) . . . xB(m) c1 . . . cn | | B−1A1 . . . B−1An | | 23.1 Example min −10x1 − 12x2 − 12x3 s.t. x1 + 2x2 + 2x3 ≤ 20 2x1 + x2 + 2x3 ≤ 20 2x1 + 2x2 + x3 ≤ 20 x1, x2, x3 ≥ 0 min −10x1 − 12x2 − 12x3 s.t. x1 + 2x2 + 2x3 + x4 = 20 2x1 + x2 + 2x3 + x5 = 20 2x1 + 2x2 + x3 + x6 = 20 x1, . . . , x6 ≥ 0 BFS: x = (0, 0, 0, 20, 20, 20) ′ B=[A4, A5, A6] x1 x2 x3 x4 x5 x6 0 −10 −12 −12 0 0 0 x4 = 20 1 2 2 1 0 0 x5 = 20 2* 1 2 0 1 0 x6 = 20 2 2 1 0 0 1 Slide 10 Slide 11 c ′ = c ′ − cB ′ B−1A = c ′ = (−10, −12, −12, 0, 0, 0) Slide 12 x1 x2 x3 x4 x5 x6 0 −7 −2 0 5 0 0 1.5 1* 1 −0.5 0 1 0.5 1 0 0.5 0 0 1 −1 0 −1 1 100 10 10 x4 = x1 = x6 = 0 Slide 13 x1 x2 x3 x4 x5 x6 120 0 −4 0 2 4 0 x3 = 10 0 1.5 1 1 −0.5 0 x1 = 0 1 −1 0 −1 1 0 x6 = 10 0 2.5* 0 1 −1.5 1 Slide 14 3� � x1 x2 x3 x4 x5 x6 136 0 0 0 3.6 1.6 1.6 x3 = 4 0 0 1 0.4 0.4 −0.6 x1 = 4 1 0 0 −0.6 0.4 0 .4 x2 = 4 0 1 0 0.4 −0.6 0 .4 Slide 15 A = (0,0,0) B = (0,0,10) E = (4,4,4) . ... . x3 C = (0,10,0) D = (10,0,0) x1 x2 4 Comparison of implementations Slide 16 Full tableau Memory O(mn) Worst-case time O(mn) Best-case time O(mn) Revised simplex O(m2) O(mn) O(m2) 5 Anticycling 5.1 Degeneracy in Practice Slide 17 Does degeneracy really happen in practice? n xij = 1 j=1 n xij = 1 i=1 xij ≥ 0 4n! vertices: For each vertex ∃ 2n−1nn−2 different ba ses (n = 8) for each vertex ∃ 33, 554, 432 bases. 5.2 Perturbations Slide 18 ′ ′(P ) min c x (Pǫ) min c x ǫ ǫ2 s.t. Ax = b s.t. Ax = b + . . . ǫm x ≥ 0 x ≥ 0. 5.2.1 Theorem Slide 19 ∃ ǫ1 > 0: for all 0 < ǫ < ǫ1 ǫ . Ax = b + .. ǫm x ≥ 0 is non-dege nerate. 5.2.2 Proof Slide 20 Let B1, . . . , Br be a ll the bases. r ǫb1 + Br · · · + Br ǫm 11ǫ + 1m B−1 . . . r b + .. = . ǫm b r + Br m1ǫ + · · · + Br ǫm m mm where: r Br Br · · · b11 1m 1 B−1 .. , B−1 . r = . . . . r b = . . Br Br r · · · m1 mm bm Slide 21 r • + Br + · · · + Br is a polynomial in θbi i1θ im θm • Roots θi,r 1, θi,r 2, . . . , θr i,m r • If ǫ = θi,r 1, . . . , θr + Bir 1ǫ + · · · + Br ǫm = 0. � i,m ⇒ bi im � • Let ǫ1 the smallest pos itive roo t ⇒ 0 < ǫ < ǫ1 all RHS are � 0 ⇒ = non-degenera c y. 55.3 Lexicography Slide 22 L • u is lexicographically larger than v, u > v, if u � v and the first = nonzero component of u − v is positive. • Example: L (0, 2, 3, 0) > (0, 2, 1, 4), L (0, 4, 5, 0) < (1, 2, 1, 2). 5.4 Lexicography-Pertubation 5.4.1 Theorem Slide 23 Let B be a basis of Ax = b, x ≥ 0. Then B is feasible for Ax = b + ′ (ǫ, . . . , ǫm) , x ≥ 0 for sufficiently …
View Full Document