The Simplex Method Beamer Print - Study Guide

The Simplex Method I I Stopping Criteria 1 Standard form (max) z − cT x = 0 such that Ax = b. Build initial tableau. z −cT 0 A I I 0 b Find an initial BFS. Look at Row 0 for neg coeffs: 1. Choose the column most negative coef. 2. Perform a “ratio test” by taking “RHS/Lead Coeff”. Exceptions: Ignore zeros and neg coeffs. Choose the row with the smallest ratio. 3. Pivot using the column/row we found. 4. Repeat. From Wed: Unbounded LP Stop if all Row 0 coeffs are non-negative. The current solution is optimal and unique. Example Final Tableau: z x1 x2 s1 s2 rhs 1 0 0 3 1 27 0 0 1 3 −1 3 1 2 0 1 0 −2 Maximizer: x1 = 2, x2 = 3 and s1 = s2 = 0. Notice also the top row: z = 27 − 3s1 − s2 Example 3, A Little Foreshadowing Here was the final tableau for an unbounded region and an unbounded LP: s1 x2 x3 z x1 x2 x3 s1 s2 s3 rhs 1 1 0 0 0 3 −2 50 0 4 0 0 1 −1 0 5 0 1 1 0 0 1 −2 10 0 0 0 1 0 1 −1 15 Translation: max z = 50 − x1 − 3s2 + 2s3 with     0 0  10   2       15     + s3  1  x=  5   0       0   0  0 1 max z = x1 +x2 st 2x1 +x2 ≥ 4 x1 +2x2 = 6 x1 , x2 ≥ 0 Build the initial tableau. z x1 x2 e1 rhs 1 −1 −1 0 0 0 2 1 −1 4 0 1 2 0 6 Not standard form... No initial BFS. Choosing x1 , x2 as the basic variables, we can perform the row reduction using an inverse matrix:   2 1 B= 1 2 B −1 1 [A|b] = 3   2 −1 −1 2  2 1 −1 4 1 2 0 6  1 0 −2/3 2/3 0 1 1/3 8/3  = The new tableau: Bring e1 into the set of BV (take x2 out):  z x1 x2 e1 rhs  1 0 1 0 6   0 1 2 0 6 0 0 3 1 8 Optimal? Yes.       e1 rhs z x1 x2  1 0 0 −1/3 10/3     0 1 0 −2/3 2/3  0 0 1 1/3 8/3 Back to the Example z x1 x2 e1 rhs 1 −1 −1 0 0 0 2 1 −1 4 0 1 2 0 6 What if we had chosen x2 and e1 as our basic variables?   z x1 x2 e1 rhs  1 −1/2 0 0 3     0 1/2 1 0 3  0 −3/2 0 1 −1 Conclusion? Not every choice of basic variables will be feasible! Example 4 maxx 6x1 + s.t. x1 + 3x1 + x1 , 5x2 x2 ≤ 5 2x2 ≤ 12 x2 ≥ 0 −6 −5 0 0 0 1 1 1 0 5 3 2 0 1 12 0 0 3 1 27 0 1 3 −1 3 1 0 −2 1 2 Solution is (2, 3) Slight Change: maxx 6x1 + s.t. x1 + 3x1 + x1 , We can bring in x2 with no change to z: 4x2 x2 ≤ 5 2x2 ≤ 12 x2 ≥ 0 0 0 0 2 24 0 1/3 1 −1/3 1 1 2/3 0 1/3 4 −6 −4 0 0 0 1 1 1 0 5 3 2 0 1 12 0 0 0 2 24 0 1/3 1 −1/3 1 1 2/3 0 1/3 4 ⇓ New solution is (4, 0) Alternative Optimal Solutions I 0 0 0 2 24 0 1 3 −1 3 1 0 −2 1 2 New solution is (2, 3). Any point on that line segment is also a maximizer. Example Consider the following “final” tableau: If a NBV in Row 0 is 0, and we can pivot in this column (and maintain the same value of z), then we may have alternative optimal solutions. I If two BFS are optimal, the line segment joining them is also optimal (by convexity). I There may be “stalling” behavior. That is, it may be that once we pivot into the new BV, there may be a new way to proceed (for a better value of z). z x1 x2 x3 x4 rhs 1 0 0 0 2 2 0 1 0 −1 1 2 0 0 1 −2 3 3 Interpretation? Row 0 may have a 0 for x3 , but we cannot pivot in that column. How many solutions to the optim. problem do we have? Example Write out the system of equations: Consider the following LP: max 4x1 + 3x2 st x1 − 6x2 ≤ 5 3x1 ≤ 11 x1 , x2 ≥ 0 Start as usual: −4 −3 0 0 0 1 −6 1 0 5 3 0 0 1 11 ⇒ 0 −3 0 4/3 44/3 0 −6 1 −1/3 4/3 1 0 0 1/3 11/3 What’s going on? = 44/3 +3x2 −(4/3)s2 = 1/3 −(1/3)s2 = x2 = 4/3 +6x2 +(1/3)s2 = s2 How should we maximize this? Set s2 = 0, and     1 0   1  1 0  + x2   x=   6  3 4  0 0 This increases the value of z without bound. Notice that cT d 6= 0. min z = −x1 + 2x2 st x1 − x2 ≤ 1 x1 − 2x2 ≤ 2 x1 , x2 ≥ 0 Proceed as usual: −1 2 0 0 0 1 −1 1 0 1 1 −2 0 1 2 Interpretation? max z st x1 x2 s1 s2 ⇒ 0 1 1 0 1 1 −1 1 0 1 0 −1 −1 1 1 There is an optimal solution: (1, 0) The feasible set is unbounded. Two Types of Unboundedness I The objective function is unbounded (as is the feasible region). I The feasible region is unbounded, but the objective function is not. “The LP is unbounded if there is a negative coefficient in Row 0, and all the remaining elements in the column are negative or zero”