15.081J/6.251J Introduction to Mathematical Programming Lecture 7: The Simplex Method III1 Outline Slide 1 • Finding an initial BFS • The complete algorithm • The column geometry • Computational efficiency • The diameter of p olyhedra and the Hirch conjecture 2 Finding an initial BFS Slide 2 • Goal: Obtain a BFS of Ax = b, x ≥ 0 or decide that LOP is infeasible. • Special case: b ≥ 0 Ax ≤ b, x ≥ 0 ⇒ Ax + s = b, x, s ≥ 0 s = b, x = 0 2.1 Artificial variables Slide 3 Ax = b, x ≥ 0 1. Multiply rows with −1 to get b ≥ 0. 2. Introduce artificial variables y, start with initial BFS y = b, x = 0, and apply simplex to auxiliary problem min y1 + y2 + . . . + ym s.t. Ax + y = b x, y ≥ 0 Slide 4 3. If cost > 0 ⇒ LOP infeasible; stop. 4. If cost = 0 a nd no artificial variable is in the basis , then a BFS was found. 5. Else, all yi ∗ = 0, but some are still in the basis. Say we have AB(1), . . . , AB(k) in basis k < m. There are m − k additional c olumns of A to form a basis. Slide 5 6. Drive artificial variables out of the basis: If lth basic variable is artifi- cial e xamine lth row of B−1A. If all elements = 0 ⇒ row redundant. Otherwise pivot with � 0 element. = 12.2 Example Slide 6 min x1 + x2 + x3 s.t. x1 + 2x2 + 3x3 = 3 −x1 + 2x2 + 6x3 = 2 4x2 + 9x3 = 5 3x3 + x4 = 1 x1, . . . , x4 ≥ 0. min x5 + x6 + x7 + x8 s.t. x1 + 2x2 + 3x3 + x5 = 3 −x1 + 2x2 + 6x3 + x6 = 2 4x2 + 9x3 + x7 = 5 3x3 + x4 + x8 = 1 x1, . . . , x8 ≥ 0. = 3 = 2 = 5 = 1 = = = = = 2 = 0 = 2 = 1/3 Slide 7 x1 x2 x3 x4 x5 x6 x7 x8 0 −8 −21 −1 0 0 0 0 1 2 3 0 1 0 0 0 −1 2 6 0 0 1 0 0 0 4 9 0 0 0 1 0 0 0 3 1* 0 0 0 1 −11 x5 x6 x7 x8 x1 x2 x3 x4 x5 x6 x7 x8 0 −8 −18 0 0 0 0 1 1 2 3 0 1 0 0 0 −1 2 6 0 0 1 0 0 0 4 9 0 0 0 1 0 0 0 3* 1 0 0 0 1 Slide 8 x1 x2 x3 x4 x5 x6 x7 x8 0 −8 0 6 0 0 0 7 1 2 0 −1 1 0 0 −1 −1 2* 0 −2 0 1 0 −2 0 4 0 −3 0 0 1 −3 0 0 1 1/3 0 0 0 1/3 2 −10 3 2 5 1 −4 x5 x6 x7 x4 x5 x6 x7 x3−4 x5 = 2 x2 = 0 x7 = 2 x3 = 1/3 0 x1 = 1 x2 = 1/2 x7 = 0 x3 = 1/3 x1 x2 x3 x4 x5 x6 x7 x8 −4 0 0 −2 0 4 0 −1 2* 0 0 1 1 −1 0 1 1 0 −1 0 1/2 0 −1 2 0 0 1 0 −2 1 1 0 0 1 1/3 0 0 0 1/3 Slide 9 −1/2 x1 x2 x3 x4 x5 x6 x7 x8 0 1 0 0 0 x1 = x2 = x3 = 0 0 0 2 2 0 1 0 0 1/2 1/2 −1/2 0 1/2 1 0 −3/4 1/4 1/4 0 −3/4 0 0 0 −1 −1 1 0 0 1 1/3 0 0 0 1/3 ∗ 1 1/2 1/3 Slide 10 x1 x2 x3 x4 ∗ ∗ ∗ ∗ 1 0 0 1/2 0 1 0 −3/4 0 0 1 1/3 3 A complete Algorithm for LO Slide 11 Phase I: 1. By multiplying so me of the constraints by −1, change the problem so that b ≥ 0. 2. Introduce y1, . . . , ym, if necessary, and apply the simplex metho d to min �mi=1 yi. 3. If cost> 0, original problem is infeasible; STOP. 4. If cost= 0, a feasible solution to the original problem has been found. 5. Drive ar tificia l variables out of the basis, potentially eliminating redundant rows. Slide 12 Phase II: 3� � 1. Let the final basis and tableau obtained from Phase I be the initial basis and tableau for Phase II. 2. Compute the reduced costs of all variables for this initial basis, us ing the cost coefficients of the original problem. 3. Apply the simplex method to the original problem. 3.1 Possible outcomes Slide 13 1. Infeasible: Detected at Phase I. 2. A has linearly dependent rows: Detected at Phase I, eliminate redundant rows. 3. Unbounded (co st= −∞): detected a t Phase II. 4. Optimal solution: Terminate at Phase II in optimality check. 4 The big-M method Slide 14 n m min cj xj + Myi j=1 i=1 s.t. Ax + y = b x, y ≥ 0 5 The Column Geometry Slide 15 min c ′ x s.t. Ax = b e ′ x = 1 x ≥ 0 � � � � � � � � x1 A1 + x2 A2 + · · · + xn An = b c1 c2 cn z Slide 16 Slide 17 6 Computational efficiency Slide 18 Exceptional practical behavior: linear in n Worst case max xn s.t. ǫ ≤ x1 ≤ 1 ǫxi−1 ≤ xi ≤ 1 − ǫxi−1, i = 2, . . . , n Slide 19 Theorem Slide 20 4z b . B D E F C G H I . . . initial basis z . b . . . . . . . . next basis optimal basis 1 23 4 5 6 7 8 (a) (b) x1 x2 x3 x1 x2 5• � � • The feasible set has 2n vertices • The vertices can be ordered so that each one is adjace nt to and has lower cost than the previous one. • There exists a pivoting rule under which the simplex method requires 2n − 1 changes of basis befor e it terminates. 7 The Diameter of polyhedra Slide 21 • Given a polyhedron P , and x, y vertices of P , the distance d(x, y) is the minimum number of jumps from one vertex to an adjacent one to reach y starting from x. • The diameter D(P ) is the maximum of d(x, y) ∀x, y. Slide 22 • Δ(n, m) as the maximum of D(P ) over all bounded polyhedra in ℜn that are represented in terms of m inequality constra ints. • Δu(n, m) is like Δ(n, m) but for possibly unbounded polyhedra. 7.1 The …