Unformatted text preview:

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

MIT 6 251J - The Simplex Method II

Download The Simplex Method II
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view The Simplex Method II and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view The Simplex Method II 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?