Geometry of Linear Programming

z The Geometry of Linear Programs – the geometry of LPs illustrated on DTC Announcement: please turn in homework solutions now • with a cover sheet 1 Goal of this Lecture z 3 mathematical intuitions – Algebraic/computational – Geometric – Economic z In this lecture, we focus on 2-dimensional geometry to guide intuition and develop a deeper understanding of linear programs. z Use DTC as a running example 2 Data for the DTC Problem Slingshot Kits Stone Shields Resources Stone Gathering time 2 hours 3 hours 100 hours Stone Smoothing 1 hour 2 hours 60 hours Delivery time 1 hour 1 hour 50 hours Demand 40 30 3 shekels 5 shekels Profit The DTC problem has two variables. We can learn a lot from its 2 dimensional geometry. 3 Formulating the DTC Problem K = number of slingshot kits manufactured S = number of stone shields manufactured Maximize Profit z = 3 K + 5 S 2 K + 3 S ≤ 100 Smoothing time: K + 2 S ≤ 60 Delivery time: K + S ≤ 50 Slingshot demand: K ≤ 40 Gathering time: Shield demand: S ≤ Non-negativity: K,S ≥ 0 30 4 Reformulation K = number of slingshot kits manufactured (in 10s) S = number of stone shields manufactured (in 10s) Maximize Profit z = 3 K + 5 S (in 10s) 2 K + 3 S ≤ 10 Smoothing time: K + 2 S ≤ 6 Delivery time: K + S ≤ 5 Slingshot demand: K ≤ 4 Gathering time: Shield demand: S ≤ Non-negativity: K,S ≥ 0 3 5 Finding an optimal solution z Introduce yourself to your partner z Try to find an optimal solution to the linear program, without looking ahead. 6 Graphing the Feasible Region We will construct and shade the feasible region one or two constraints at a time. 5 4 3 2 1 1 2 3 4 5 6 7 Graph the Constraints: 2 K + 3 S ≤ 10 K ≥ 0 , S ≥ 0. S 5 4 3 2 K + 3 S = 10 2 1 1 2 3 4 5 6 K 8 Add the Constraint: K + 2 S ≤ 6 S 5 4 3 2 K + 2 S = 6 1 1 2 3 4 5 6 K 9 Add the Constraint: K + S ≤ 5 S 5 K + S = 5 4 3 2 1 1 2 3 4 5 6 K 10 Add the Constraints: K ≤ 4; S ≤ 3 S 5 We have now graphed the feasible region. 4 3 2 1 1 2 3 4 5 6 K 11 How do we maximize 3K + 5S ? S 5 4 3 2 1 1 2 3 4 5 6 K 12 S How do we maximize 3K + 5S ? Isoprofit line: the set of solutions to 3K + 5S = a 3 2 3K + 5S = 16 1 3K + 5S = 7.5 3K + 5S = 12 1 2 3 4 K 13 Isoprofit line: the set of solutions to 3K + 5S = a. S Adjust parameter a until the isoprofit line is tangent to the feasible region. 3 An optimal solution occurs at a corner point. 2 3K + 5S = 16 1 3K + 5S = 7.5 3K + 5S = 12 1 2 3 4 K 14 S If we had maximized 2K + 4S, we would have gotten a line segment of optimal solutions. 3 Here an optimal solution occurs at two corner points. 2 2K + 4S = 12 1 2K + 4S = 4 2K + 4S = 8 1 2 3 4 K 15 An Unbounded Feasible Region Maximize z = 3 x - 5 y x - y ≥ -2 x - 2y ≤ 2 y x ≥ 0, y ≥ 0, 5 4 3 2 Either an optimal solution occurs at a corner point, or else the objective is unbounded from above. 1 1 2 3 4 5 6 x 16 An Unbounded Feasible Region Maximize y z = x - 3y Maximize The optimum solution is x = 2, y = 0. z = 3 x - 5 y The objective value is unbounded from above. 5 3x - 5y = 0 4 3 x - 3y = 0 2 1 1 2 3 4 5 6 x 17 What the geometry reveals z If the feasible region is bounded, it is polyhedral. That is, it can be enclosed by lines. It is a convex polyhedron. convex not convex Not a linear program 18 3 dimensional geometry zIf the feasible region is bounded, it is polyhedral. in 3D it is enclosed by planes. It is still convex. 19 What the geometry reveals z If there is an optimal solution, there is an optimal solution that is a corner point. If two points are optimal, then every solution on the line segment joining those points is optimal. 20 Review Questions on Geometry z Which of the following can be feasible regions for linear programs? A B C D 21 Questions on Geometry If exactly one of these points is optimal for an LP, which point(s) can it be? B C A E D If point E is optimum, is it true that all points must be optimum? Is it true that the objective is minimize 0x + 0y? 22 More on corner points in 2 dimensions Maximize z = 3 K + 5 S 2 K + 3 S ≤ 10 K + 2 S ≤ 6 S plus other constraints 5 4 A constraint is said to be binding if it holds with equality at the optimum solution. 3 Other constraints are non-binding 2 1 1 2 3 4 5 6 K 23 Evaluating the optimal solution In two dimensions, a corner point is the intersection of 2 lines. S Maximize z = 3 K + 5 S 5 2 K + 3 S = 10 K + 2 S = 6 4 Solution: 3 2 K + 4 S = 12 K = 2; 2 S = 2 z = 16 1 1 2 3 4 5 6 K 24 Next: A Preview of the Simplex Algorithm z In n dimensions, one cannot evaluate the solution value of every corner (or extreme) point efficiently. (There are too many.) – Consider: 0 ≤ xj ≤ 1 for j = 1 to n. – There are 2n different corner points. n=1 n=2 n=3 •The simplex method finds the best solution by a neighborhood search technique. •Two feasible corner points are said to be “adjacent” if they have one binding constraint in common. 25 Neighborhood Search Algorithms – – – – Start with a feasible solution x Define a neighborhood of x Identify an improved neighbor y Replace x by y and repeat xx x x xx xx x xx x x x x x x x x xx x x x xxx xx x x xx x x xx x xx x x xx x x x x x x xx x xx xx xxx x x xx x x x x x x x xx x x x xxxx xx x x x x x x x xx x x x x xx x x xx x x x x x x x x x x x x …………….. xx x x x x x x x x x x x x x x x x x x x x x xx x x xx x x x x x x x x x 26 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 27 Using Geometry for Sensitivity Analysis Models often are built on data that may or may not be accurate. Dij ≥ γ L Dij ≤ γ U for ( i , j ) ∈ T for ( i , j ) ∈ C From model for radiotherapy Sensitivity analysis: vary the data and see the impact on the solutions. Special sensitivity analyses for linear programming. •Vary the RHS in a linear manner. •Vary the cost in a linear manner. 28 Data for the DTC Problem Slingshot Kits Stone Shields Resources Stone Gathering time 2 hours 3 hours 100 hours Stone Smoothing 1 hour 2 hours 60 hours Delivery time 1 hour 1 hour 50 hours Demand 40 30 3 shekels 5 shekels Profit Sensitivity analysis. Suppose that one of the town’s children volunteers for stone gathering. What is the extra profit (ignoring wages)? Suppose the profit for stone shields is reduced to 4.5. 29 Sensitivity Analysis in 2D S Suppose the gathering time is increased to 10 + ∆. What is the impact on the optimal solution value? 5 The shadow price of a constraint is the unit increase in the optimal objective value per unit increase in the RHS of the constraint. 4 3 2 1 1 2 3 4 5 6 K 30 Sensitivity Analysis in 2D S z = 3 K + 5 S 2 K + 3 S = 10 + ∆ K + 2 S = 6 Solve for the corner point solution as a function of ∆. Solution: 5 2 K + 4 S = 12 S = 2 - ∆ K = 2 + 2∆; 4 z = 16 + ∆ 3 So, the shadow price of “gathering time” is 1. If we increase gather time by an hour is it worth 1 shekel? (Be careful of units) 2 1 1 2 3 4 5 6 K 31 Sensitivity Analysis z Key insights: – Optimal solutions occur at corner points. – Optimal solutions typically stay optimal for small changes in data z We will use these insights to answer several questions on sensitivity analysis. 32 Exercise with Partner (4 minutes) z The objective value in the “transformed” model increases by 1 if we increase gathering time from 10 to 11. What is the impact in the original model of increasing gathering time from 100 to 101? z What is the impact on the optimal objective value of increasing smoothing time from 6 to 7? z What happens if we decrease it from 6 to 4? 33 2-Dimensional Sensitivity Analysis z = 3 K + 5 S 2 K + 3 S = 10 K + 2 S = 6 + S ∆ Solution: 5 2 K + 4 S = 12 S = 2 + ? K = 2 + ? 4 z = 16 + ? 3 2 1 1 2 3 4 5 6 K 34 2-Dimensional Sensitivity Analysis z = 3 K + 5 S 2 K + 3 S = 10 + ∆ K + 2 S = 6 S Solution: 5 2 K + 4 S = 12 S = 2 - ∆ K = 2 + 2∆; 4 z = 16 + ∆ 3 The shadow price is 1. It is valid in an interval. 2 1 1 2 3 4 5 6 K 35 35 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. 36 Sensitivity Analysis: determining the interval K =2+2∆; Maximize Profit S= 2-∆ Solver z = 3 K + 5 S (in 10s) 2 K + 3 S ≤ Smoothing time: K + 2 S ≤ 6 6 ≤ 6 Delivery time: K + S ≤ 5 4+∆ ≤ 5 Slingshot demand: K ≤ 4 2 + 2∆ ≤ 4 3 2-∆ ≤ 3 Gathering time: Shield demand: S ≤ Non-negativity: K,S ≥ 0 10 + ∆ z = 16 + ∆ 10 + ∆ ≤ 10 + ∆ 2 + 2∆ ≥ 0 2- ∆ ≥ 0 So, -1 ≤ ∆ ≤ 1 37 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. z If there are three binding constraints, then choose two of these to get the two equations to solve, and the technique still works. (But the shadow prices and ranges depends on which two constraints are chosen.) 38 Bounds on Cost coefficients in Sensitivity Analysis z Recall that the optimum solution is a corner point, – in 2D: 2 binding equations in 2 variables – in 2D: it has two neighboring corner points z Cost sensitivity: how much can you change the cost coefficient of a variable so that the current corner point solution stays optimal? 39 Determining Bounds on Cost Coefficients S 5 Suppose the objective function is changed to z = 3 K + (5 + ∆) S If ∆ = 1, the objective is parallel to K + 2 S = 6 If ∆ = -.5, the objective is parallel to 2 K + 3 S = 10 So (2, 2) remains optimal if -.5 ≤ ∆ ≤ 1. 4 3 2 K + 3 S = 10 2 K + 2 S = 6 1 1 2 3 4 5 6 K 40 Determining Bounds on Cost Coefficients 5 Suppose the objective function is changed to z = (3 + ∆) K + 5 S Take two minutes to determine upper and lower bounds on what value d can take so that (2, 2) remains optimal. 4 Solver S 3 2 K + 3 S = 10 2 K + 2 S = 6 1 1 2 3 4 5 6 K 41 Summary: 2D Geometry helps guide the intuition z The Geometry of the Feasible Region – Graphing the constraints z Finding an optimal solution – Graphical method – Searching all the extreme points – Simplex Method z Sensitivity Analysis – Changing the RHS – Changing the Cost Coefficients 42