Simplex Method 1

z Introduction to Simplex Algorithm 1 Preview of the Simplex Method Maximize z = 3 K + 5 S Start at any feasible corner point. S Move to an adjacent corner point with better objective value. 5 Continue until no adjacent corner point has a better objective value. 4 3 2 1 1 2 3 4 5 6 K 2 The simplex algorithm (for max problems) Start with a feasible corner point solution find an improved corner point solution Is it optimal? Yes quit with optimal solution No No Is the optimum unbounded from above? Yes quit with proof of unboundedness 3 Goals for this lecture Major Issues of the Simplex Algorithm 1. How does one get the LP into the correct starting form? 2. How does one recognize optimality and unboundedness? 3. How does one move to the next corner point solution? Next: getting a linear program into nearly into the starting form. 4 Linear Programs in Standard Form We say that a linear program is in standard form if the following are all true: 1. Non-negativity constraints for all variables. 2. All remaining constraints are expressed as equality constraints. 3. The right hand side vector, b, is non-negative. An LP not in Standard Form maximize z = 3x1 + 2x2 - x3 + x4 x1 + 2x2 + x3 - x4 ≤ 5 ; not equality -2x1 - 4x2 + x3 + x4 ≤ -1; not equality x1 ≥ 0, x2 ≥ 0 x3 and x4 may be negative 5 Converting Inequalities into Equalities Plus Non-negatives Before x1 + 2x2 + x3 - x4 ≤ 5 After x1 + 2x2 + x3 - x4 +s1 = 5 s1 ≥ 0 s1 is called a slack variable, which measures the amount of “unused resource.” Note that s1 = 5 - x1 - 2x2 - x3 + x4. To convert a “≤” constraint to an equality, add a slack variable. 6 Converting RHS and “≥” constraints z Consider the inequality -2x1 - 4x2 + x3 + x4 ≤ -1; z Step 1. Eliminate the negative RHS 2x1 + 4x2 - x3 - x4 ≥ 1 z Step 2. Convert to an equality 2x1 + 4x2 - x3 - x4 – s2 = 1 s2 ≥ 0 z The variable added will be called a “surplus variable.” To convert a “≥” constraint to an equality, subtract a surplus variable. 7 More Transformations How can one convert a minimization problem to a maximization problem? Example: Minimize z = 3x1 + 2x2 subject to “constraints” Has the same optimum solution(s) as Maximize v = -3x1 - 2x2 subject to “constraints” 8 The Last Transformations (for now) Transforming variables that may take on negative values. maximize subject to z = 3x1 + 4x2 + 5x3 2x1 - 5x2 + 2x3 = 7 other constraints x1 ≤ 0, x2 is unconstrained in sign, x3 ≥ 0 Transforming x1: replace x1 by y1 = -x1; y1 ≥ 0. max z = -3y1 + 4x2 +5x3 -2y1 -5x2 +2x3 =7 y1 ≥ 0, x2 is unconstrained in sign, x3 ≥ 0 One can recover x1 from y1. 9 Transforming variables that may take on negative values. max z = -3y1 + 4x2 +5x3 -2y1 -5x2 +2x3 =7 y1 ≥ 0, x2 is unconstrained in sign, x3 ≥ 0 e.g., y1 = 1, x2 = -1, x3 = 2 is feasible. Transforming x2: replace x2 by x2 = y3 - y2; y2 ≥ 0, y3 ≥ 0. max z = -3y1 + 4(y3 - y2) +5x3 -2y1 -5y3 +5y2 +2x3 =7 all vars ≥ 0 One can recover x2 from y2, y3. e.g., y1 = 1, y2 = 0, y3 = 1 x3 = 2 is feasible. 10 A Class Exercise z Exercise: transform the following to standard form (maximization): Minimize v = x1 + 3x2 Subject to 2x1 + 5x2 ≤ 12 x1 + x2 ≥ 1 x1 ≥ 0 Perform the transformation with your partner (2 minutes) 11 A 2-variable LP: our running example -3x1 + 3x2 ≤ 6 -4x1 + 2x2 ≤ max s.t 4 3 2 z= -3x1 + 2x2 -3x1 + 3x2 ≤ 6 -4x1 + 2x2 ≤ 2 x1 ≥ 0, x2 ≥ 0 2 1 1 2 3 4 12 A 2-variable LP maximize subject to z= maximize subject to z= -3x1 + 2x2 -3x1 + 3x2 -4x1 + 2x2 x1 ≥ 0, x2 ≥ 0 ≤6 ≤2 -3x1 + 2x2 -3x1 + 3x2 +x3 -4x1 + 2x2 + x4 x1, x2, x3, x4 =6 =2 ≥ 0 z x1 x2 x3 x4 1 3 -2 0 0 = 0 0 -3 3 1 0 = 6 0 -4 2 0 1 = 2 13 LP “canonical form” An LP is in “canonical form” if it is written so that it is in standard form, and such that each constraint has a variable with a coefficient “1” and such that that variable has a 0 in all other constraints. z x1 x2 x3 x4 1 3 -2 0 0 = 0 0 -3 3 1 0 = 6 0 -4 2 0 1 = 2 14 The Canonical Form and its Basic Feasible Solution (bfs) z x1 x2 x3 x4 1 3 -2 0 0 = 0 0 -3 3 1 0 = 6 0 -4 2 0 1 = 2 The basic variables are z, x3 and x4. The non-basic variables are x1 and x2. The basic feasible solution (bfs) for this basis is z = 0, x1 = 0, x2 = 0, x3 = 6, x4 = 2 (set the non-basic variables to 0, and then solve) 15 Theorem. Every basic feasible solution of a linear program in standard form is a corner point solution, and vice versa. -3x1 + 3x2 ≤ 6 -4x1 + 2x2 ≤ 2 The basic feasible solution z = 0, x1 = 0, x2 = 0, x3 = 6, x4 = 2 4 3 2 1 1 2 3 4 16 LP Canonical Form and the bfs. z x1 x2 x3 x4 1 -3 3 -2 2 0 0 = 0 0 -3 3 1 0 = 6 0 -4 2 0 1 = 2 The text treats z as a basic variable. The simplex method starts with a tableau in LP canonical form (or it creates canonical form at a preprocess step.) The first solution is the bfs for that tableau. 17 For each constraint there is a basic variable z x1 x2 x3 x4 1 -3 3 -2 2 0 0 = 0 Objective function. 0 -3 3 1 0 = 6 Constraint 1 0 -4 2 0 1 = 2 Constraint 2 The basic variable for the objective function is always z Constraint 1: basic variable is x3 Constraint 2: basic variable is x4 The basic variables are z , x3 and x4 18 The simplex algorithm (for max problems) Start with a feasible corner point solution Is it optimal? Yes No We were lucky to be able to start with a feasible bfs. We now move on to the rest of the algorithm. Next lecture: how to find a starting bfs Next: how to recognize optimality. 19 Recognizing Optimality (note that the data is different here) z x1 x2 x3 x4 1 2 4 0 0 = 8 0 -3 3 1 0 = 6 0 -4 2 0 1 = 2 z + 2x1 +4x2 = 8. And x1 ≥ 0 and x2 ≥ 0 Therefore, z ≤ 8. Important Fact. If there is no negative coefficient in the z row, the basic feasible solution is optimal! And z = 8 in the current basic feasible solution This basic feasible solution is optimal! 20 Recognizing non-optimality z x1 x2 x3 x4 1 -3 3 -2 2 0 0 = 0 0 -3 3 1 0 = 6 0 -4 2 0 1 = 2 The cost-coefficient of x2 is -2. z + 3x1 - 2x2 = 0 The current bfs can be improved if we can increase x2 and hold x1 at 0. 21 The current basic feasible solution (bfs) is not optimal! z x1 x2 x3 x4 1 -3 3 -2 2 0 0 = 0 0 -3 3 1 0 = 6 0 -4 2 0 1 = 2 Recall: z + 3x1 - 2x2 = 0 Increasing x2 and adjusting x3 and x4 and z will improve the solution. Increase x2 to ∆ > 0. Let x1 stay at 0. If there is a negative coefficient in the z row, the basis is not optimal** z = 2 ∆. x3 = 6 - 3 ∆. x4 = 2 - 2 ∆. 22 Moving along an edge of the feasible region. Let x2 = ∆. z x1 x2 x3 x4 1 -3 3 -2 0 0 = 0 0 -3 3 1 0 = 6 0 -4 2 0 1 = 2 z = 2∆. x1 = 0 x2 = ∆ x3 = 6 - 3∆. x4 = 2 - 2∆. Choose ∆ as large as it can be so that all variables remain non-negative. That is, the solution stays feasible. ∆ = 1. Fact. The resulting solution is a basic feasible solution for a different basis. 23 The two dimensional geometry -3x1 + 3x2 + x3 = 6 -4x1 + 2x2 + x4 = 2 Increasing x2 by ∆ corresponds to moving along an edge. 4 3 2 1 1 2 3 4 24 Pivoting to obtain a better solution New Solution: basic variables z, x2 and x3. Nonbasics: x1 and x4. -z z x1 x2 x3 x4 1 -1 3 -2 0 0 0 1 = 2 0 0 -3 3 3 0 1 -1.5 0 = 6 3 0 -4 -2 2 1 0 .5 1 = 2 1 z= 2 x1 = 0 x2 = 1 x3 = 3 x4 = 0 Pivot on a coefficient in the matrix. Choose the column of the basic variable that enters. Choose the row of the basic variable that leaves. If we pivot on the coefficient 2, we obtain the new basic feasible solution. 25 Summary of Simplex Algorithm z Start in canonical form with a basic feasible solution 1. Check for optimality conditions 2. If not optimal, determine a non-basic variable that should be made positive 3. Increase that non-basic variable, and perform a pivot, obtaining a new bfs 4. Continue until optimal (or unbounded). 26 z x1 x2 x3 x4 1 a 0 0 0 = 3 0 b 0 1 0 = 6 0 c 1 0 0 = 3 0 d 0 0 1 = 5 To do with your partner (2 minutes) The values a, b, c, and d are unknown 1. What are the basic variables? What is the current bfs? 2. Under what condition is the current bfs optimal? 27 z x1 x2 x3 x4 1 a 0 0 0 = 3 0 b 0 1 0 = 6 0 c 1 0 0 = 3 0 d 0 0 1 = 5 To do with your partner (3 minutes) 1. If we set x1 to ∆, what are x2, x3, and x4, all expressed in terms of ∆. 2. Assume that b > 0 and d < 0. Under what condition we will set ∆ = 3/c? 3. If ∆ = 3/c, what coefficient do we pivot on next? 28 Recognizing Unboundedness If the non-cost coefficients in the entering column are ≤ 0, then the solution is unbounded z - x1 + x4 = 2 z x1 x2 x3 x4 1 -1 0 0 1 = 2 0 -3 0 1 -1.5 = 3 0 -2 1 0 .5 = 1 z= 2+∆ x1 = ∆ x2 = 1 + 2∆ x3 = 3 + 3∆. x4 = 0 ∆ can grow to ∞, and then z goes to ∞. 29 The two dimensional geometry 4 3 2 1 1 2 3 4 30 Next: two more iterations. (Then showing the standard shortcut.) z - x1 + x4 = 2 z x1 x2 x3 x4 1 -1 0 0 1 = 2 0 3 0 1 -1.5 = 3 0 -2 1 0 .5 = 1 z= 2+∆ x1 = ∆ x2 = 1 + 2∆ x3 = 3 - 3∆. x4 = 0 The cost coefficient of x1 is negative. Set x1 = ∆ and x4 = 0. Then ∆ = 3/3. 31 Another pivot z x1 x2 x3 x4 1 -1 0 0 +1/3 0 +1/2 1 = 2 3 0 3 1 0 1/3 1 -1/2 -1.5 = 3 1 0 -2 0 1 2/3 0 -1/2 .5 = 1 3 z= 2 3+∆ x1 = 1 ∆ x2 = 3 1 + 2∆ x3 = 0 3 - 3∆. x4 = 0 The largest value of ∆ is 3/3. Variable x1 becomes basis, x3 becomes nonbasic. So, x1 becomes the basic variable for constraint 1. Pivot on the coefficient with a 3. 32 The two dimensional geometry -3x1 + 3x2 + x3 = 6 -4x1 + 2x2 + x4 = 2 4 3 2 1 1 2 3 4 33 Check for optimality z + x3/3 + x4/2 = 3 z x1 x2 x3 x4 1 0 0 +1/3 +1/2 = 3 0 1 0 1/3 -1/2 = 1 0 0 1 2/3 1/2 = 3 z 1== 3D x x12 = 1 + 2D x23 = 3 - 3D. x34 = 0 z 4== 20 + D x There is no negative coefficient in the z-row. The current basic feasible solution is optimal! 34 The two dimensional geometry -3x1 + 3x2 + x3 = 6 -4x1 + 2x2 + x4 = 2 -3x1 + 2x2 = -5 4 3 2 1 1 2 3 4 35 Two views of the simplex method z Improvement by “moving along an edge.” – Increase ∆, and increase z. – An approach used in other algorithms, and that shows what is going on. z Improvement by “moving to an adjacent corner point” – Move to an adjacent corner point and increase z – It can be viewed as a “shortcut” 36 Summary of Simplex Algorithm Again z Start in canonical form with a basic feasible solution 1. Check for optimality conditions z 2. If not optimal, determine a non-basic variable that should be made positive z 3. Choose a variable with a negative coef. in the cost row. Increase that non-basic variable, and perform a pivot, obtaining a new bfs (or unboundedness) z 4. Is there a negative coefficient in the cost row? We will review this step, and show a shortcut Continue until optimal (or unbounded). 37 The Minimum Ratio Rule for determining the leaving variable. z - 3x1 = 3 z x1 x2 x3 x4 1 -3 0 0 0 = 3 0 3 1 0 0 = 6 0 -2 0 1 0 = 1 0 2 0 0 1 = 5 z = 3 + 2∆ x1 = ∆ x2 = 6 - 3∆ x3 = 1 + 2∆ x4 = 5 - 2∆ ∆ = min (6/3, 5/2). At next iteration, pivot on the 3. ratio: RHS coefficient/ entering column coefficient s.t. entering column coefficient is positive 38 More on performing a pivot z To determine the column to pivot on, select a variable with a negative cost coefficient z To determine a row to pivot on, select a coefficient according to a minimum ratio rule z Carry out a pivot as one does in solving a system of equations. 39 Next Lecture z Review of the simplex algorithm z Formalizing the simplex algorithm z How to find an initial basic feasible solution, if one exists z A proof that the simplex algorithm is finite (assuming non-degeneracy) 40