Report

Readings Readings Chapter 2 An Introduction to Linear Programming BA 452 Lesson A.3 Unsolvable Linear Programs 1 Overview Overview BA 452 Lesson A.3 Unsolvable Linear Programs 2 Overview Blending Problems are Linear Programming Profit Maximization problems when additional inputs may be bought. Blending Problems thus help blend resources to maximize profit or to minimize cost. Non-Unique Optimal Solutions of a linear program mean there are either alternative optimal solutions, no solutions because it is infeasible, or no solutions because the objective can be infinite. Blending with Mixed Constraints help blend resources (grass seeds, desserts, horse food, …) when constraints restrict permissible blends by a mixture of minimal and maximal characteristics. BA 452 Lesson A.3 Unsolvable Linear Programs 3 Blending Blending BA 452 Lesson A.3 Unsolvable Linear Programs 4 Blending Overview Blending Problems are Linear Programming Profit Maximization problems when additional inputs may be bought. Blending Problems thus help production managers blend resources (grass seeds, desserts, horse food, …) to produce goods either to maximize profit or to minimize cost. Constraints restrict permissible blends by product characteristics (shade tolerance, calories, vitamin content, …). BA 452 Lesson A.3 Unsolvable Linear Programs 5 Blending Question: The Sanders Garden Shop blends two types of grass seed. Each type has been rated (per pound) according to its shade tolerance, ability to stand up to traffic, and drought resistance, as shown in the table: Type A Type B Shade tolerance 2 5 Traffic resistance 4 -1 Drought resistance 1 1 For example, if 1 pound of Type A is the blend, then that blend scores 2 points of Shade tolerence; if 2 pounds of Type A, then 4 points. (The points could measure how many blades of green grass survive being in the shade.) For another example, if 1 pound of Type B is the blend, then that blend scores -1 points of Traffic resistance. (The points could measure the number of blades of green grass minus blades of dead grass when there is traffic on the grass. A negative score means there is more dead grass.) BA 452 Lesson A.3 Unsolvable Linear Programs 6 Blending Type A seed costs $5 and Type B seed costs $2. Suppose the blend needs to score at least 10 points for shade tolerance, at least 12 points for traffic resistance, and at least 4 points for drought resistance. How many pounds of each seed should be in the blend? Which targets will be exceeded? How much will the blend cost? BA 452 Lesson A.3 Unsolvable Linear Programs 7 Blending Answer: First, formulate the problem as a linear program: Objective: minimize cost of blending x1 pounds of Type A seed with x2 pounds of Type B seed Min s.t. 5x1 + 2x2 2x1 + 5x2 > 10 4x1 - x2 > 12 x1 + x2 > 4 x 1, x 2 > 0 Constraint 1: Shade tolerance Constraint 2: Traffic resistance Constraint 3: Drought resistance Non-negativity constraints BA 452 Lesson A.3 Unsolvable Linear Programs 8 Blending Constraint 1: 2x1+5x2 > 10. Binding edge: 2x1+5x2 = 10. On the edge, when x1 = 0, then x2 = 2; when x2 = 0, then x1 = 5. Connect (5,0) and (0,2) for the binding edge of the constraint plus non-negativity. The feasible ">" side is above the binding edge. Min 5x1 + 2x2 s.t. 2x1 + 5x2 > 10 4x1 - x2 > 12 x1 + x2 > 4 x1, x2 > 0 Feasible side Binding edge BA 452 Lesson A.3 Unsolvable Linear Programs 9 Blending Constraint 2: 4x1-x2 > 12. Binding edge: 4x1-x2 = 12. On the edge, when x2 = 0, then x1 = 3. But setting x1 to 0 yields x2 = -12, which violates non-negativity. Thus, to get a second point on the binding edge, set x1 to any number larger than 3 and solve for x2: when x1 = 4, then x2 = 4. Pass a line through (3,0) and (4,4) for the binding edge of the constraint. The feasible ">" side is to the right. Min 5x1 + 2x2 s.t. 2x1 + 5x2 > 10 4x1 - x2 > 12 x1 + x2 > 4 x1, x2 > 0 Feasible side Binding edge BA 452 Lesson A.3 Unsolvable Linear Programs 10 Blending Constraint 3: x1 + x2 > 4. Binding edge: x1 + x2 = 4. On the edge, When x1 = 0, then x2 = 4; when x2 = 0, then x1 = 4. Connect (4,0) and (0,4) for the binding edge of the constraint. The feasible ">" side is above that line. Min 5x1 + 2x2 s.t. 2x1 + 5x2 > 10 4x1 - x2 > 12 x1 + x2 > 4 x1, x2 > 0 Feasible side Binding edge BA 452 Lesson A.3 Unsolvable Linear Programs 11 Blending Min 5x1 + 2x2 s.t. 2x1 + 5x2 > 10 4x1 - x2 > 12 x1 + x2 > 4 x1, x2 > 0 Feasible region 4x1 - x2 > 12 x1 + x2 > 4 2x1 + 5x2 > 10 BA 452 Lesson A.3 Unsolvable Linear Programs 12 Blending Min 5x1 + 2x2 s.t. 2x1 + 5x2 > 10 4x1 - x2 > 12 x1 + x2 > 4 x1, x2 > 0 Min 5x1 + 2x2 Set the objective function equal to an arbitrary constant (say, 20) and graph it. For 5x1 + 2x2 = 20, when x1 = 0, then x2 = 10; when x2= 0, then x1 = 4. Connect (4,0) and (0,10). Move the objective function line in the direction that lowers its value (down), since we are minimizing, until it touches the last point of the feasible region, determined in Example 2 by the first two constraints 4x1 - x2 > 12 x1 + x2 > 4 2x1 + 5x2 > 10 BA 452 Lesson A.3 Unsolvable Linear Programs 13 Blending Min 5x1 + 2x2 s.t. 2x1 + 5x2 > 10 4x1 - x2 > 12 x1 + x2 > 4 x1, x2 > 0 Min 5x1 + 2x2 Binding at optimum: 4x1 - x2 = 12 Binding at optimum: x1 + x2 = 4 BA 452 Lesson A.3 Unsolvable Linear Programs 14 Blending Min 5x1 + 2x2 s.t. 2x1 + 5x2 > 10 4x1 - x2 > 12 x1 + x2 > 4 x1, x2 > 0 The optimal solution (x1 = 5, x2 = 3) is where the second and third constraints bind: 4x1 - x2 = 12 and x1 + x2 = 4 Solve those equalities using linear algebra, matricies, determinates (det), and Cramer’s rule: 4x1 - x2 = 12 x 1 + x2 = 4 4 1 4 12 -1 x1 = det 4 1 / det 1 -1 1 4 -1 x2 = det 4 12 1 4 / det 1 -1 1 x1 x2 = 12 4 = (12x1+1x4)/(4x1+1x1) = 16/5 = (4x4-12x1)/(4x1+1x1) = 4/5 1 BA 452 Lesson A.3 Unsolvable Linear Programs 15 Blending Min 5x1 + 2x2 s.t. 2x1 + 5x2 > 10 4x1 - x2 > 12 x1 + x2 > 4 x1, x2 > 0 How many pounds of each seed should be in the blend? 16/5 pounds of Type A seed; 4/5 pounds of Type B seed. Which targets will be exceeded? The traffic resistance and draught resistance constraints are binding at the optimum, but the shade tolerance target is exceeded (the constraint is slack). How much will the blend cost? 5x1 + 2x2 = 5(16/5) + 2(4/5) = 88/5 = 17.6 dollars. BA 452 Lesson A.3 Unsolvable Linear Programs 16 Blending Graph the feasible solutions for each of the constraints. Determine the feasible region that satisfies all the constraints simultaneously. Graph an objective function line. Move parallel objective function lines toward smaller objective function values without entirely leaving the feasible region. Any feasible solution on the objective function line with the smallest value is an optimal solution. BA 452 Lesson A.3 Unsolvable Linear Programs 17 Blending Min 5x1 + 2x2 s.t. 2x1 + 5x2 > 10 4x1 - x2 > 12 x1 + x2 > 4 x1, x2 > 0 Min 5x1 + 2x2 + 0s1 + 0s2 + 0s3 s.t. 2x1 + 5x2 - s1 = 10 4x1 - x2 - s2 = 12 x1 + x 2 - s3 = 4 x 1, x 2, s 1, s 2, s 3 > 0 s1 , s2 , and s3 are surplus variables BA 452 Lesson A.3 Unsolvable Linear Programs 18 Blending Min 5x1 + 2x2 s.t. 2x1 + 5x2 > 10 4x1 - x2 > 12 x1 + x2 > 4 x1, x2 > 0 BA 452 Lesson A.3 Unsolvable Linear Programs 19 Blending Min 5x1 + 2x2 s.t. 2x1 + 5x2 > 10 4x1 - x2 > 12 x1 + x2 > 4 x1, x2 > 0 Optimal Solution: Minimized cost = 17.6 Optimal x1 = 3.2, x2 = 0.8 0.4 surplus in the first constraint BA 452 Lesson A.3 Unsolvable Linear Programs 20 Non-Unique Optimal Solutions Non-Unique Optimal Solutions BA 452 Lesson A.3 Unsolvable Linear Programs 21 Non-Unique Optimal Solutions Overview Non-Unique Optimal Solutions of a linear program mean there are either alternative optimal solutions, no solutions because it is infeasible, or no solutions because the objective function can be feasibly improved without bound. BA 452 Lesson A.3 Unsolvable Linear Programs 22 Non-Unique Optimal Solutions The feasible region for a two-variable LP problem can be empty (nonexistent), a single point, a line, a polygon, or an unbounded area. Any linear program falls in one of four categories: • has a unique optimal solution • has alternative optimal solutions • has no solution because it is infeasible • has no solution because the objective function can be feasibly improved without bound A feasible region may be unbounded and yet there may be optimal solutions. This is common in practical minimization problems and sometimes occurs in practical maximization problems. BA 452 Lesson A.3 Unsolvable Linear Programs 23 Non-Unique Optimal Solutions Alternative optimal solutions In the graphical method, if the objective function line is parallel to a boundary constraint in the direction of optimization, there are alternate optimal solutions, with all points on this line segment being optimal. For example, consider the following LP problem: Max s.t. 4x1 + 6x2 x1 < 6 2x1 + 3x2 < 18 x1 + x2 < 7 x1 > 0 and x2 > 0 BA 452 Lesson A.3 Unsolvable Linear Programs 24 Non-Unique Optimal Solutions Graph of alternative optimal solutions The binding edge of constraint 2x1 + 3x2 < 18 is parallel to all objective-function lines of 4x1 + 6x2 All points on segment A – B are optimal solutions. x2 x1 + x 2 < 7 7 6 5 A B 4 x1 < 6 2x1 + 3x2 < 18 3 2 1 1 2 3 4 5 6 7 8 9 x1 10 BA 452 Lesson A.3 Unsolvable Linear Programs 25 Non-Unique Optimal Solutions Conditions for infeasibility Infeasibility means no solution to the LP problem satisfies all the constraints, including the nonnegativity conditions. Graphically, this means the feasible region is empty (does not exist). Causes include: • A formulation error has been made. • Management’s expectations are too high. • Too many restrictions have been placed on the problem (that is, the problem is over-constrained). BA 452 Lesson A.3 Unsolvable Linear Programs 26 Non-Unique Optimal Solutions Graph of infeasibility There are no points that satisfy both constraints of the problem, so the feasible region is empty (there are no feasible solutions). x2 10 2x1 + x2 > 8 8 6 4x1 + 3x2 < 12 4 2 2 4 6 8 Max 2x1 + 6x2 s.t. 2x1 + x2 > 8 4x1 + 3x2 < 12 x1, x2 > 0 x1 10 BA 452 Lesson A.3 Unsolvable Linear Programs 27 Non-Unique Optimal Solutions Unbounded objective-function values The value of the solution to a maximization LP problem is unbounded if the value of the solution may be made indefinitely large without violating any of the constraints. For practical problems, this is the result of improper formulation. Most often, a constraint has been inadvertently omitted. Here is an example: Max 4x + 5x 1 s.t. 2 3x1 + x2 > 8 x1 + x2 > 5 x1, x2 > 0 BA 452 Lesson A.3 Unsolvable Linear Programs 28 Non-Unique Optimal Solutions Graph of unbounded function values The feasible region is unbounded and the objective function line can be moved outward from the origin without bound, infinitely increasing the objective function. x2 10 3x1 + x2 > 8 8 6 Max 4x1 + 5x2 4 s.t. 3x1 + x2 > 8 x1 + x2 > 5 x1, x2 > 0 x1 + x 2 > 5 2 2 4 6 8 x1 10 BA 452 Lesson A.3 Unsolvable Linear Programs 29 Blending with Mixed Constraints Blending with Mixed Constraints BA 452 Lesson A.3 Unsolvable Linear Programs 30 Blending with Mixed Constraints Overview Blending with Mixed Constraints help production managers blend resources (grass seeds, desserts, horse food, …) when constraints restrict permissible blends by a mixture of minimal and maximal product characteristics (shade tolerance, calories, vitamin content, …). For example, a blend of desserts should have at least a minimal weight to be satisfying and at most a maximal number of calories and fat to be healthful. BA 452 Lesson A.3 Unsolvable Linear Programs 31 Blending with Mixed Constraints Question: Maggie Stewart loves twinkies and ho ho’s, but due to weight and cholesterol concerns she has decided she must plan her desserts carefully. Maggie allows herself no more then 450 calories and 25 grams of fat in her daily desserts. She requires at least 120 grams of desserts a day. Each dessert also has a “taste index”: 37 for each twinkie gram, 65 for each ho ho gram. Plan her daily desserts to stay within her constraints and maximize the total taste index? What further information do you need for your answer? BA 452 Lesson A.3 Unsolvable Linear Programs 32 Blending with Mixed Constraints Answer: First, formulate the linear program: Step 1. Identify decision variables: x1 = daily servings of Twinkies, x2 = daily servings of Ho Ho’s. Step 2. Identify remaining information needed: • Each Twinkie serving has 150 calories, has 4.5 grams of fat, weighs 1.5 ounces. • 1.5 ounces = 42.5243 grams (since 1 ounce = 28.3495 grams). BA 452 Lesson A.3 Unsolvable Linear Programs 33 Blending with Mixed Constraints • • Each Ho Ho serving has 380 calories, has 17 grams of fat, weighs 3 ounces. 3 ounces = 85.0485 grams (since 1 ounce = 28.3495 grams). BA 452 Lesson A.3 Unsolvable Linear Programs 34 Blending with Mixed Constraints Adding the non-negativity of consumption completes the formulation. Max s.t. 37(42.5243)x1 + 65(85.0485)x2 150x1 + 380x2 < 450 4.5x1 + 17x2 < 25 42.5243x1 + 85.0485x2 > 120 x1 > 0 and x2 > 0 Taste index Calorie constraint Fat constraint Weight constraint Non-negativity constraints BA 452 Lesson A.3 Unsolvable Linear Programs 35 Blending with Mixed Constraints Max s.t. 37(42.5243)x1 + 65(85.0485)x2 150x1 + 380x2 < 450 4.5x1 + 17x2 < 25 42.5243x1 + 85.0485x2 > 120 x1 > 0 and x2 > 0 2.1541 servings of Twinkies each day. 0.3339 servings of Ho Ho’s each day. BA 452 Lesson A.3 Unsolvable Linear Programs 36 BA 452 Quantitative Analysis End of Lesson I.3 BA 452 Lesson A.3 Unsolvable Linear Programs 37