Optimization: Linear Programs in Mgmt Science

z The Geometry of Linear Programs – The simplex algorithm – More properties of linear programs Pentagonal prism 1 Overview of Lecture z Review of Geometry z The Simplex Algorithm z More on convexity z RHS Sensitivity Analysis 2 Quotes of the Day Geometry is not true, it is advantageous. Jules H. Poincare I've always been passionate about geometry and the study of threedimensional forms. Erno Rubik 3 Review of Geometry y 3 2 A set S is convex if for every two points in the set, the line segment joining the points is also in the set; that is, if p1, p2 ∈ S, then so is(1-λ)p1 + λp2 for λ ∈ [0,1] Theorem. The feasible region of a linear program is convex. p1 1 p2 1 2 3 4 x 4 Corner Points z z A corner point of the feasible region is a point that is not the midpoint of two other points of the feasible region. All feasible LPs with non-negativity constraints have at least one corner point. If an LP is feasible, has nonnegativity constraints, and has an optimal solution, then there is a corner point that is optimal. 5 Solving for Corner Points z z In two dimensions, a corner point is the intersection of two equality constraints. In three dimensions, a corner point is the intersection of three constraints. (3 planes) 0≤x≤2 0≤y≤2 0≤z≤2 z x -y +z≤3 x y 6 The red corner point is the intersection of three planes x=2 z=2 x -y+z=3 The unique solution is x = 2, y = 1, z = 2. There are 3 Types of Linear Programs 3 3 2 2 1 1 1 2 3 4 Those with an optimal solution 1 2 3 4 Those with no feasible solution. 5 4 3 Those whose objective value is unbounded Isoprofit line 2 1 1 2 3 4 5 6 7 The Simplex Method in Two Dimensions Start at any feasible corner point. y 5 4 Move to an adjacent corner point with better objective value. Move along an edge of the feasible region. Continue until no adjacent corner point has a better objective value. Max z = 3 x + 5 y 3 2 3 x + 5 y = 19 1 1 2 3 4 5 6 x 8 8 The Simplex Method Again Start at any feasible corner point. x 5 4 Move to an adjacent corner point with better objective value. Move along an edge of the feasible region. Continue until no adjacent corner point has a better objective value. 3 2 1 1 2 3 4 5 6 y 9 The Simplex Method in 3 Dimensions Start at any feasible corner point. Move to an adjacent corner point with better objective value. Move along an edge of the feasible region. Continue until no adjacent corner point has a better objective value. Note: in two dimensions, the “edges” are the intersections of two constraints. The corner points are the intersection of three constraints. Pentagonal prism 10 An Example of the Simplex Method in 3 Dimensions y Maximize y y=2 The number of iterations depends upon which edge is chosen at each iteration. y=1.7 y=1.5 y=1 y=0 y=.1 x y=.3 z y=.2 In practice, the simplex method is very efficient, even on very complex large scale LPs. 11 This is a twisted cube. Notice how the simplex method starting at the origin could move to the optimum in 1 step or pivot. It is also possible for the simplex method to take 7 pivots, thus visiting each corner point. Klee and Minty developed an example that is very similar that has n variables. It is possible that the simplex method would take 2^n – 1 pivots on these examples, thus showing that the simplex method can take exponential time in the worst case. In practice, there may be many different edges that the simplex method can select at a given iteration. The speed in which the simplex method moves to the optimum depends on the choice of the edge. The Simplex Method on Unbounded LPs Maximize x y If the objective is unbounded from above, then the simplex method will move infinitely far along an edge. 5 4 3 2 1 1 2 3 4 5 6 x 12 y Interior Point Algorithms for LP 3 3x + 5y = 16 2 1 1 2 3 4 x 13 There are a variety of algorithms that move within the interior of linear programs. These algorithms typically take far fewer iterations than the simplex algorithm and far more time per iteration for large problems. Sometimes interior point algorithms obtain answers quicker than the simplex algorithm. Often they are slower. Interior point algorithms were popularized by Karmarkar in 1984, who proved that the number of iterations is bounded by a polynomial in the dimension of the problem and in the number of bits needed to describe the coefficients. Comments on Optimality Conditions z Linear programming produces both the optimal solution and the proof of optimality. (This is true for any number of variables, and even if many of the constraints are equality constraints.) – special among optimization problems – very valuable – “The Gold Standard” for optimization z For other optimization problems in the subject, we will settle for bounds from optimality – e.g., we will be happy if we can guarantee at most 10% from optimality 14 Convex Combinations Suppose that p1, p2, …, pk are all vectors (or points). Let pk +1 = λ1p1 + λ2 p2 + ... + λk pk . We say that pk+1 is a convex combination of p1, …, pk if the following are true: λ1 + λ2 + ... + λk = 1 and λi ≥ 0 for i = 1 to k . Suppose k = 2. What points are convex combinations of p1 and p2? p1 p2 15 More on Convex Combinations 5 What points can be represented as the convex combination of (0,0), (0, 4), and (3, 0)? 4 λ1 (0, 0) 3 + λ2 (0, 4) + λ3 (3, 0) 2 1 1 2 3 4 5 6 16 Convex Combinations and Convex Hulls The convex hull of points p1, …, pk is the smallest convex region containing all of the points. It is also the set of all points that can be expressed as convex combinations of p1 to pk. 5 4 Note that the convex hull of points in 2 dimensions looks like an LP feasible region. 3 2 1 1 2 3 4 5 6 17 Convex Hulls in 3 dimensions y z x 18 In Slide show mode, the figure is revealed as a cube that is partially cut off. Representation Theorem z Theorem. Every bounded polyhedra (linear programming feasible region) can be represented as a convex hull of its corner points. z Theorem. The convex hull of a set of points is a bounded linear programming feasible region. z Usually, we prefer to represent a linear program in terms of constraints. But there are times when it is useful to represent it as the convex combination of corner points. 19 Mental Break What are the odds? 20 Sensitivity Analysis z Sensitivity analysis: Determining the marginal effect on the optimal objective function if we make small changes in the data. z In LP, we focus on two types of sensitivity analysis that are very useful and very easy for an LP package to compute 21 The revised DTC example z = 3x + 5y 2x + 3y ≤ 10 Gathering time x + 2y ≤ 6 Smoothing time y ≤ 5 Delivery Time ≤ 4 Demand: kits y ≤ 3 Demand: shields x + x x, y ≥ 0 non-negativity 22 We could have used the original variable names of K and S, but it is simpler to use x and y since we usually think of the two axes as the x and y axis. The optimal solution In two dimensions, a corner point lies at the intersection of two lines. x + 2y = 6 2x + 3y = 10 smoothing time y 3 x +2y = 6 2x + 4y = 12 2x + 3y = 10 gathering time 2 2x +3y = 10 y=2 1 z = 3x + 5y 1 2 3 4 x x = 2, z = 16 23 It’s very useful that the corner point lies at the intersection of two lines. Then solving a system of equations with two variables and two equations will give the value of the corner point. Varying the RHS Suppose that we consider the problem in which gathering time is parameterized by G. y 3 Let z(G) be the optimal objective value when gathering time is G, and all other data is unchanged. smoothing time x +2y = 6 gathering time 2 2x +3y = 10 G z(10) = 16 1 1 2 3 4 x What is z’(10)? (derivative) 24 It’s very useful that the corner point lies at the intersection of two lines. Then solving a system of equations with two variables and two equations will give the value of the corner point. Computing the derivative z '(10) = limΔ→0 z(10 + Δ ) − z(10) Δ Key observation: if Δ is small, then the optimum corner point of the problem will be the intersection of the smoothing time constraint and the gathering constraint. That is, the constraints that define the corner point will not change. 25 On the new corner point y 3 The solution value changes, but the “structure” of the solution does not change. smoothing time x +2y = 6 gathering time 2 2x +3y = G 1 1 2 3 4 x 26 Computing the New Corner Point x + 2y = 6 2x + 3y = 10 + Δ y 3 smoothing time x +2y = 6 2x + 4y = 12 2x + 3y = 10 + Δ gathering time 2 2x +3y = 10 + Δ y=2-Δ 1 z = 3x + 5y 1 2 3 4 x x = 2 + 2Δ z = 16 + Δ 27 The Shadow Price z '(10) = limΔ→0 z (10 + Δ ) − z (10) Δ (16 + Δ ) − 16 z '(10) = limΔ→0 =1 Δ Note that z’(10 + Δ) is linear in Δ. This is the shadow price of the gathering constraint. Note. We only needed that the corner point was the intersection of the gathering and smoothing constraint. 28 More on Shadow Prices The shadow price of a constraint is the unit increase in the optimal objective value per unit increase in the RHS of the constraint. It is also a derivative. Let p denote the shadow price. If the RHS of gathering increases from 10 to 10 + Δ, then the objective value increases from 16 to 16 + pΔ, that is, it increases by pΔ. 29 Exercises z z(10) = 16; z’(10) = 1 (The shadow price is 1) z Fact: z(11) = 16 + 1 = 17. z What is z(10.2)? z What is z(9.7)? z What is z(0)? (trick question) 30 Computing the Shadow Price of a Constraint z Step 1. Determine the binding constraints that determine the corner point. x + 2y = 6 2x + 3y = 10 z Step 2. Add Δ to the RHS of the constraint whose shadow price we are computing. x + 2y = 6 2x + 3y = 10 + Δ z Step 3. Solve the system of equations. x = 2 + 2Δ y=2-Δ z Step 4. Compute the “increase” in z when Δ increases from 0 to 1 (i.e., compute the derivative) z(10 + Δ) = 16 + Δ Shadow price = 1. 31 Bounds on RHS coefficients in Sensitivity Analysis z Recall that the optimum solution is a corner point, which in 2 dimensions is the solution of 2 equations in 2 variables, and the equations are the binding constraints. z Compute the largest changes in the RHS coefficient so that all constraints remain satisfied. 32 What happens if the RHS changes by a lot? y 3 2 2x +3y = G 1 1 2 3 4 x 33 More Sensitivity Analysis: Determining the Interval x =2+2Δ; Maximize Profit Constraint after substitution. y= 2-Δ z = 3 x + 5 y (in 10s) 2 x + 3 y ≤ Smoothing time: x + 2 y ≤ 6 6 ≤ 6 Delivery time: x + y ≤ 5 4+Δ ≤ 5 Slingshot demand: x ≤ 4 2 + 2Δ ≤ 4 3 2-Δ ≤ 3 Gathering time: Shield demand: y ≤ Non-negativity: K,S ≥ 0 10 + Δ z = 16 + Δ 10 + Δ ≤ 10 + Δ 2 + 2Δ ≥ 0 2- Δ ≥ 0 So, -1 ≤ Δ ≤ 1 34 Summary for changes in RHS coefficients z Determine the binding constraints z Determine the change in the “corner point solution” as a function of Δ. z Compute the largest and smallest values of Δ so that the solution stays feasible. z The shadow price is valid so long as the “corner point solution” remains optimal, which is so long as it is feasible. 35 And now, it’s time for ….. 36 “Who wants a piece of candy” is not stored on the web.