Linear Programming Models: Graphical and Computer Methods PDF

7 Linear Programming Models: Graphical and...

7 Linear Programming Models: Graphical and Computer To accompany Methods Quantitative Analysis for Management, Twelfth Edition, by Render, Stair, Hanna and Hale Power Point slides created by Jeff Heyl Copyright ©2015 Pearson Education, Inc.  LEARNING OBJECTIVES After completing this chapter, students will be able to: 1. Understand the basic assumptions and properties of linear programming (LP). 2. Graphically solve any LP problem that has only two variables by both the corner point and isoprofit line methods. 3. Understand special issues in LP such as infeasibility, unboundedness, redundancy, and alternative optimal solutions. 4. Understand the role of sensitivity analysis. 5. Use Excel spreadsheets to solve LP problems. Copyright ©2015 Pearson Education, Inc. 7–2  CHAPTER OUTLINE 7.1 Introduction 7.2 Requirements of a Linear Programming Problem 7.3 Formulating LP Problems 7.4 Graphical Solution to an LP Problem 7.5 Solving Flair Furniture’s LP Problem using QM for Windows, Excel 2013, and Excel QM 7.6 Solving Minimization Problems 7.7 Four Special Cases in LP 7.8 Sensitivity Analysis Copyright ©2015 Pearson Education, Inc. 7–3  Introduction Many management decisions involve making the most effective use of limited resources Linear programming (LP) – Widely used mathematical modeling technique – Planning and decision making relative to resource allocation Broader field of mathematical programming – Here programming refers to modeling and solving a problem mathematically Copyright ©2015 Pearson Education, Inc. 7–4  Requirements of a Linear Programming Problem Four properties in common – Seek to maximize or minimize some quantity (the objective function) – Restrictions or constraints are present – Alternative courses of action are available – Linear equations or inequalities Copyright ©2015 Pearson Education, Inc. 7–5  LP Properties and Assumptions TABLE 7.1 PROPERTIES OF LINEAR PROGRAMS 1. One objective function 2. One or more constraints 3. Alternative courses of action 4. Objective function and constraints are linear – proportionality and divisibility 5. Certainty 6. Divisibility 7. Nonnegative variables Copyright ©2015 Pearson Education, Inc. 7–6  Formulating LP Problems Developing a mathematical model to represent the managerial problem Steps in formulating a LP problem 1. Completely understand the managerial problem being faced 2. Identify the objective and the constraints 3. Define the decision variables 4. Use the decision variables to write mathematical expressions for the objective function and the constraints Copyright ©2015 Pearson Education, Inc. 7–7  Formulating LP Problems Common LP application – product mix problem Two or more products are produced using limited resources Maximize profit based on the profit contribution per unit of each product Determine how many units of each product to produce Copyright ©2015 Pearson Education, Inc. 7–8  Flair Furniture Company Flair Furniture produces inexpensive tables and chairs Processes are similar, both require carpentry work and painting and varnishing – Each table takes 4 hours of carpentry and 2 hours of painting and varnishing – Each chair requires 3 of carpentry and 1 hour of painting and varnishing – There are 240 hours of carpentry time available and 100 hours of painting and varnishing – Each table yields a profit of $70 and each chair a profit of $50 Copyright ©2015 Pearson Education, Inc. 7–9  Flair Furniture Company The company wants to determine the best combination of tables and chairs to produce to reach the maximum profit TABLE 7.2 HOURS REQUIRED TO PRODUCE 1 UNIT (C) AVAILABLE HOURS DEPARTMENT (T) TABLES CHAIRS THIS WEEK Carpentry 4 3 240 Painting and varnishing 2 1 100 Profit per unit $70 $50 Copyright ©2015 Pearson Education, Inc. 7 – 10  Flair Furniture Company The objective is Maximize profit The constraints are – The hours of carpentry time used cannot exceed 240 hours per week – The hours of painting and varnishing time used cannot exceed 100 hours per week The decision variables are T = number of tables to be produced per week C = number of chairs to be produced per week Copyright ©2015 Pearson Education, Inc. 7 – 11  Flair Furniture Company Create objective function in terms of T and C Maximize profit = $70T + $50C Develop mathematical relationships for the two constraints – For carpentry, total time used is (4 hours per table)(Number of tables produced) + (3 hours per chair)(Number of chairs produced) – First constraint is Carpentry time used ≤ Carpentry time available 4T + 3C ≤ 240 (hours of carpentry time) Copyright ©2015 Pearson Education, Inc. 7 – 12  Flair Furniture Company Similarly Painting and varnishing time used ≤ Painting and varnishing time available 2 T + 1C ≤ 100 (hours of painting and varnishing time) This means that each table produced requires two hours of painting and varnishing time – Both of these constraints restrict production capacity and affect total profit Copyright ©2015 Pearson Education, Inc. 7 – 13  Flair Furniture Company The values for T and C must be nonnegative T ≥ 0 (number of tables produced is greater than or equal to 0) C ≥ 0 (number of chairs produced is greater than or equal to 0) The complete problem stated mathematically Maximize profit = $70T + $50C subject to 4T + 3C ≤240 (carpentry constraint) 2T + 1C ≤100 (painting and varnishing constraint) T, C ≥ 0 (nonnegativity constraint) Copyright ©2015 Pearson Education, Inc. 7 – 14  Graphical Solution to an LP Problem Easiest way to solve a small LP problems is graphically Only works when there are just two decision variables – Not possible to plot a solution for more than two variables Provides valuable insight into how other approaches work Nonnegativity constraints mean that we are always working in the first (or northeast) quadrant of a graph Copyright ©2015 Pearson Education, Inc. 7 – 15  Graphical Representation of Constraints FIGURE 7.1 – Quadrant Containing All Positive Values C 100 – – This Axis Represents the Constraint T ≥ 0 80 – Number of Chairs – 60 – – 40 – This Axis Represents the Constraint C ≥ 0 – 20 – – | | | | | | | | | | | | 0 20 40 60 80 100 T Number of Tables Copyright ©2015 Pearson Education, Inc. 7 – 16  Graphical Representation of Constraints The first step is to identify a set or region of feasible solutions Plot each constraint equation on a graph Graph the equality portion of the constraint equations 4T + 3C = 240 Solve for the axis intercepts and draw the line Copyright ©2015 Pearson Education, Inc. 7 – 17  Graphical Representation of Constraints When Flair produces no tables, the carpentry constraint is: 4(0) + 3C = 240 3C = 240 C = 80 Similarly for no chairs: 4T + 3(0) = 240 4T = 240 T = 60 – This line is shown on the following graph Copyright ©2015 Pearson Education, Inc. 7 – 18  Graphical Representation of Constraints FIGURE 7.2 – Graph of Carpentry Constraint Equation C 100 – – 80 – (T = 0, C = 80) Number of Chairs – 60 – – 40 – – (T = 60, C = 0) 20 – – | | | | | | | | | | | | 0 20 40 60 80 100 T Number of Tables Copyright ©2015 Pearson Education, Inc. 7 – 19  Graphical Representation of Constraints FIGURE 7.3 – Region that Satisfies the Carpentry Constraint C Any point on or below the constraint plot will not 100 – violate the restriction – Any point above the plot will 80 – violate the restriction Number of Chairs – 60 – – (30, 40) (70, 40) 40 – – 20 – – (30, 20) | | | | | | | | | | | | 0 20 40 60 80 100 T Number of Tables Copyright ©2015 Pearson Education, Inc. 7 – 20  Graphical Representation of Constraints The point (30, 40) lies on the line and exactly satisfies the constraint 4(30) + 3(40) = 240 The point (30, 20) lies below the line and satisfies the constraint 4(30) + 3(20) = 180 The point (70, 40) lies above the line and does not satisfy the constraint 4(70) + 3(40) = 400 Copyright ©2015 Pearson Education, Inc. 7 – 21  Graphical Representation of Constraints FIGURE 7.4 – Region that Satisfies the Painting and Varnishing Constraint C 100 – (T = 0, C = 100) – 80 – Number of Chairs – 60 – – 40 – – (T = 50, C = 0) 20 – – | | | | | | | | | | | | 0 20 40 60 80 100 T Number of Tables Copyright ©2015 Pearson Education, Inc. 7 – 22  Graphical Representation of Constraints To produce tables and chairs, both departments must be used Find a solution that satisfies both constraints simultaneously A new graph shows both constraint plots The feasible region is where all constraints are satisfied – Any point inside this region is a feasible solution – Any point outside the region is an infeasible solution Copyright ©2015 Pearson Education, Inc. 7 – 23  Graphical Representation of Constraints FIGURE 7.5 – Feasible Solution Region C 100 – – 80 – Painting/Varnishing Constraint Number of Chairs – 60 – – 40 – – Feasible Carpentry Constraint 20 – Region – | | | | | | | | | | | | 0 20 40 60 80 100 T Number of Tables Copyright ©2015 Pearson Education, Inc. 7 – 24  Graphical Representation of Constraints For the point (30, 20) Carpentry 4T + 3C ≤ 240 hours available constraint (4)(30) + (3)(20) = 180 hours used  Painting 2T + 1C ≤ 100 hours available constraint (2)(30) + (1)(20) = 80 hours used  For the point (70, 40) Carpentry 4T + 3C ≤ 240 hours available constraint (4)(70) + (3)(40) = 400 hours used  Painting 2T + 1C ≤ 100 hours available constraint (2)(70) + (1)(40) = 180 hours used  Copyright ©2015 Pearson Education, Inc. 7 – 25  Graphical Representation of Constraints For the point (50, 5) Carpentry 4T + 3C ≤ 240 hours available constraint (4)(50) + (3)(5) = 215 hours used  Painting 2T + 1C ≤ 100 hours available constraint (2)(50) + (1)(5) = 105 hours used  Copyright ©2015 Pearson Education, Inc. 7 – 26  Isoprofit Line Solution Method Find the optimal solution from the many possible solutions Speediest method is to use the isoprofit line Starting with a small possible profit value, graph the objective function Move the objective function line in the direction of increasing profit while maintaining the slope The last point it touches in the feasible region is the optimal solution Copyright ©2015 Pearson Education, Inc. 7 – 27  Isoprofit Line Solution Method Choose a profit of $2,100 The objective function is $2,100 = 70T + 50C Solving for the axis intercepts, draw the graph Obviously not the best possible solution Further graphs can be created using larger profits – The further we move from the origin, the larger the profit The highest profit ($4,100) will be generated when the isoprofit line passes through the point (30, 40) Copyright ©2015 Pearson Education, Inc. 7 – 28  Isoprofit Line Solution Method FIGURE 7.6 – Profit line of $2,100 C 100 – – 80 – Number of Chairs – 60 – – $2,100 = $70T + $50C 40 – – (30, 0) 20 – – | | | | | | | | | | | | 0 20 40 60 80 100 T Number of Tables Copyright ©2015 Pearson Education, Inc. 7 – 29  Isoprofit Line Solution Method FIGURE 7.7 – Four Isoprofit Lines C 100 – – $3,500 = $70T + $50C 80 – Number of Chairs – $2,800 = $70T + $50C 60 – – $2,100 = $70T + $50C 40 – – $4,200 = $70T + $50C 20 – – | | | | | | | | | | | | 0 20 40 60 80 100 T Number of Tables Copyright ©2015 Pearson Education, Inc. 7 – 30  Isoprofit Line Solution Method FIGURE 7.8 – Optimal Solution C 100 – – 80 – Number of Chairs Maximum Profit Line – 60 – Optimal Solution Point – (T = 30, C = 40) 40 – – $4,100 = $70T + $50C 20 – – | | | | | | | | | | | | 0 20 40 60 80 100 T Number of Tables Copyright ©2015 Pearson Education, Inc. 7 – 31  Corner Point Solution Method The corner point method for solving LP problems Look at the profit at every corner point of the feasible region Mathematical theory is that an optimal solution must lie at one of the corner points or extreme points Copyright ©2015 Pearson Education, Inc. 7 – 32  Corner Point Solution Method FIGURE 7.9 – Four Corner Points of the Feasible Region C 100 – – (0, 80) 80 – Number of Chairs – 60 – – (?) 40 – – 20 – – (50, 0) | | | | | | | | | | | | (0, 0) 0 20 40 60 80 100 T Number of Tables Copyright ©2015 Pearson Education, Inc. 7 – 33  Corner Point Solution Method Solve for the intersection of the two constraint lines Using the elimination method to solve simultaneous equations method, select a variable to be eliminated Eliminate T by multiplying the second equation by –2 and add it to the first equation – 2(2T + 1C = 100) = – 4T – 2C = –200 4T + 3C = 240 (carpentry) – 4T – 2C = –200 (painting) C = 40 Copyright ©2015 Pearson Education, Inc. 7 – 34  Corner Point Solution Method Substitute C = 40 into either equation to solve for T 4T + 3(40) = 240 Thus the 4T + 120 = 240 corner point 4T = 120 is (30, 40) T = 30 TABLE 7.3 – Feasible Corner Points and Profits NUMBER OF NUMBER OF PROFIT = $70T + TABLES (T) CHAIRS (C) $50C 0 0 $0 50 0 $3,500 0 80 $4,000 30 40 $4,100 Copyright ©2015 Pearson Education, Inc. Highest profit – Optimal Solution 7 – 35  Slack and Surplus Slack is the amount of a resource that is not used – For a less-than-or-equal constraint Slack = (Amount of resource available) – (Amount of resource used) – Flair decides to produce 20 tables and 25 chairs 4(20) + 3(25) = 155 (carpentry time used) 240 = (carpentry time available) 240 – 155 = 85 (Slack time in carpentry) Copyright ©2015 Pearson Education, Inc. 7 – 36  Slack and Surplus At the optimal solution, slack is 0 as all 240 Slack is the amount of a resource that is not hours are used used – For a less-than-or-equal constraint Slack = (Amount of resource available) – (Amount of resource used) – Flair decides to produce 20 tables and 25 chairs 4(20) + 3(25) = 155 (carpentry time used) 240 = (carpentry time available) 240 – 155 = 85 (Slack time in carpentry) Copyright ©2015 Pearson Education, Inc. 7 – 37  Slack and Surplus Surplus is used with a greater-than-or-equal- to constraint to indicate the amount by which the right-hand side of the constraint is exceeded Surplus = (Actual amount) – (Minimum amount) – New constraint T + C ≥ 42 – If T = 20 and C = 25, then 20 + 25 = 45 Surplus = 45 – 42 = 3 Copyright ©2015 Pearson Education, Inc. 7 – 38  Summaries of Graphical Solution Methods TABLE 7.4 ISOPROFIT METHOD 1. Graph all constraints and find the feasible region. 2. Select a specific profit (or cost) line and graph it to find the slope. 3. Move the objective function line in the direction of increasing profit (or decreasing cost) while maintaining the slope. The last point it touches in the feasible region is the optimal solution. 4. Find the values of the decision variables at this last point and compute the profit (or cost). CORNER POINT METHOD 1. Graph all constraints and find the feasible region. 2. Find the corner points of the feasible reason. 3. Compute the profit (or cost) at each of the feasible corner points. 4. Select the corner point with the best value of the objective function found in Step 3. This is the optimal solution. Copyright ©2015 Pearson Education, Inc. 7 – 39  Solving Flair Furniture’s LP Problem Most organizations have access to software to solve big LP problems There are differences between software implementations, the approach is basically the same With experience with computerized LP algorithms, it is easy to adjust to minor changes Copyright ©2015 Pearson Education, Inc. 7 – 40  Using QM for Windows Select the Linear Programming module Specify the number of constraints (non- negativity is assumed) Specify the number of decision variables Specify whether the objective is to be maximized or minimized For Flair Furniture there are two constraints, two decision variables, and the objective is to maximize profit Copyright ©2015 Pearson Education, Inc. 7 – 41  Using QM for Windows PROGRAM 7.1A – QM for Windows Linear Programming Computer Input Screen Copyright ©2015 Pearson Education, Inc. 7 – 42  Using QM for Windows PROGRAM 7.1B – QM for Windows Data Input Copyright ©2015 Pearson Education, Inc. 7 – 43  Using QM for Windows PROGRAM 7.1C – QM for Windows Output and Graph Copyright ©2015 Pearson Education, Inc. 7 – 44  Using Excel’s Solver The Solver tool in Excel can be used to find solutions to – LP problems – Integer programming problems – Noninteger programming problems – Solver is limited to 200 variables and, in some situations, 100 constraints Copyright ©2015 Pearson Education, Inc. 7 – 45  Using Solver Recall the model for Flair Furniture is Maximize profit = $70T + $50C Subject to 4T + 3C ≤ 240 2T + 1C ≤ 100 To use Solver, it is necessary to enter data and formulas Copyright ©2015 Pearson Education, Inc. 7 – 46  Using Solver 1. Enter problem data – Variable names, coefficients for the objective function and constraints, RHS values for each constraint 2. Designate specific cells for the values of the decision variables 3. Write a formula to calculate the value of the objective function 4. Write a formula to compute the left-hand sides of each of the constraints Copyright ©2015 Pearson Education, Inc. 7 – 47  Using Solver PROGRAM 7.2A – Excel Data Input Copyright ©2015 Pearson Education, Inc. 7 – 48  Using Solver PROGRAM 7.2B – Formulas Copyright ©2015 Pearson Education, Inc. 7 – 49  Using Solver PROGRAM 7.2C – Excel Spreadsheet Copyright ©2015 Pearson Education, Inc. 7 – 50  Using Solver PROGRAM 7.2D – Starting Solver Copyright ©2015 Pearson Education, Inc. 7 – 51  Using Solver PROGRAM 7.2E – Solver Parameters Dialog Box Copyright ©2015 Pearson Education, Inc. 7 – 52  Using Solver PROGRAM 7.2F – Solver Add Constraint Dialog Box Copyright ©2015 Pearson Education, Inc. 7 – 53  Using Solver PROGRAM 7.2G – Solver Results Dialog Box Copyright ©2015 Pearson Education, Inc. 7 – 54  Using Solver PROGRAM 7.2H – Solution Copyright ©2015 Pearson Education, Inc. 7 – 55  Using Excel QM PROGRAM 7.3A – Excel QM in Excel 2013 Copyright ©2015 Pearson Education, Inc. 7 – 56  Using Excel QM PROGRAM 7.3B – Excel QM Input Data Copyright ©2015 Pearson Education, Inc. 7 – 57  Using Excel QM PROGRAM 7.3C – Excel QM Output Copyright ©2015 Pearson Education, Inc. 7 – 58  Solving Minimization Problems Many LP problems involve minimizing an objective such as cost Minimization problems can be solved graphically – Set up the feasible solution region – Use either the corner point method or an isocost line approach – Find the values of the decision variables (e.g., X1 and X2) that yield the minimum cost Copyright ©2015 Pearson Education, Inc. 7 – 59  Holiday Meal Turkey Ranch The Holiday Meal Turkey Ranch is considering buying two different brands of turkey feed and blending them to provide a good, low-cost diet for its turkeys TABLE 7.5 – Holiday Meal Turkey Ranch data COMPOSITION OF EACH POUND OF FEED (OZ.) MINIMUM MONTHLY REQUIREMENT PER INGREDIENT BRAND 1 FEED BRAND 2 FEED TURKEY (OZ.) A 5 10 90 B 4 3 48 C 0.5 0 1.5 Cost per pound 2 cents 3 cents Copyright ©2015 Pearson Education, Inc. 7 – 60  Holiday Meal Turkey Ranch Let X1 = number of pounds of brand 1 feed purchased X2 = number of pounds of brand 2 feed purchased Minimize cost (in cents) = 2X1 + 3X2 subject to: 5X1 + 10X2 ≥ 90 ounces (ingredient A constraint) 4X1 + 3X2 ≥ 48 ounces (ingredient B constraint) 0.5X1 ≥ 1.5 ounces (ingredient C constraint) X1 ≥ 0 (nonnegativity constraint) X2 ≥ 0 (nonnegativity constraint) Copyright ©2015 Pearson Education, Inc. 7 – 61  Holiday Meal Turkey Ranch FIGURE 7.10 – Feasible Region X2 – 20 – Ingredient C Constraint Pounds of Brand 2 15 – Feasible Region a 10 – Ingredient B Constraint 5– b Ingredient A Constraint | | | | c | | 0– 5 10 15 20 25 X1 Pounds of Brand 1 Copyright ©2015 Pearson Education, Inc. 7 – 62  Holiday Meal Turkey Ranch Solve for the values of the three corner points – Point a is the intersection of ingredient constraints C and B 4X1 + 3X2 = 48 X1 = 3 – Substituting 3 in the first equation, we find X2 = 12 – Solving for point b we find X1 = 8.4 and X2 = 4.8 – Solving for point c we find X1 = 18 and X2 = 0 Copyright ©2015 Pearson Education, Inc. 7 – 63  Holiday Meal Turkey Ranch Substituting these values back into the objective function we find Cost = 2X1 + 3X2 Cost at point a = 2(3) + 3(12) = 42 Cost at point b = 2(8.4) + 3(4.8) = 31.2 Cost at point c = 2(18) + 3(0) = 36 – The lowest cost solution is to purchase 8.4 pounds of brand 1 feed and 4.8 pounds of brand 2 feed for a total cost of 31.2 cents per turkey Copyright ©2015 Pearson Education, Inc. 7 – 64  Holiday Meal Turkey Ranch Solving using an isocost line Move the isocost line toward the lower left The last point touched in the feasible region will be the optimal solution Copyright ©2015 Pearson Education, Inc. 7 – 65  Holiday Meal Turkey Ranch FIGURE 7.11 – Graphical Solution Using the Isocost Approach X2 – Feasible Region 20 – Pounds of Brand 2 15 – 54 ¢ =2 Di X 1 + re cti on 3X 10 – 3 ofD 2 Is oc 1.2 ec os ¢= rea tL 2X s ing ine 5– 1 + Co 3X st 2 (X1 = 8.4, X2 = 4.8) | | | | | | 0– 5 10 15 20 25 X1 Pounds of Brand 1 Copyright ©2015 Pearson Education, Inc. 7 – 66  Holiday Meal Turkey Ranch PROGRAM 7.4 – Solution in QM for Windows Copyright ©2015 Pearson Education, Inc. 7 – 67  Holiday Meal Turkey Ranch PROGRAM 7.5A – Excel 2013 Solution Copyright ©2015 Pearson Education, Inc. 7 – 68  Holiday Meal Turkey Ranch PROGRAM 7.5B – Excel 2013 Formulas Copyright ©2015 Pearson Education, Inc. 7 – 69  Four Special Cases in LP Four special cases and difficulties arise at times when using the graphical approach 1. No feasible solution 2. Unboundedness 3. Redundancy 4. Alternate Optimal Solutions Copyright ©2015 Pearson Education, Inc. 7 – 70  No Feasible Solution No solution to the problem that satisfies all the constraint equations No feasible solution region exists A common occurrence in the real world Generally one or more constraints are relaxed until a solution is found Consider the following three constraints Copyright ©2015 Pearson Education, Inc. 7 – 71  No Feasible Solution FIGURE 7.12 – A problem with no feasible solution X2 8– – 6– – Region Satisfying 4– Third Constraint – 2– – 0– | | | | | | | | | | 2 4 6 8 X1 Region Satisfying First Two Constraints Copyright ©2015 Pearson Education, Inc. 7 – 72  Unboundedness Sometimes a linear program will not have a finite solution In a maximization problem – One or more solution variables, and the profit, can be made infinitely large without violating any constraints In a graphical solution, the feasible region will be open ended Usually means the problem has been formulated improperly Copyright ©2015 Pearson Education, Inc. 7 – 73  Unboundedness FIGURE 7.13 – A Feasible Region That Is Unbounded to the Right Maximize profit = $3X1 + $5X2 subject to X1 ≥5 X2 X2 ≤ 10 X1 + 2X2 ≥ 10 X1 ≥ 5 X1, X2 ≥ 0 15 – X2 ≤ 10 10 – Feasible Region 5– X1 + 2X2 ≥ 10 | | | | | 0– 5 10 15 X1 Copyright ©2015 Pearson Education, Inc. 7 – 74  Redundancy A redundant constraint is one that does not affect the feasible solution region One or more constraints may be binding This is a very common occurrence in the real world Causes no particular problems, but eliminating redundant constraints simplifies the model Maximize profit = $1X1 + $2X2 subject to X1 + X2 ≤ 20 2X1 + X2 ≤ 30 X1 ≤ 25 X1, X2 ≥0 Copyright ©2015 Pearson Education, Inc. 7 – 75  Redundancy FIGURE 7.14 – Problem Maximize profit = $1X1 + $2X2 with a Redundant Constraint subject to X1 + X2 ≤ 20 X2 2X1 + X2 ≤ 30 X1 ≤ 25 30 – X1, X2 ≥ 0 25 – 2X1 + X2 ≤ 30 20 – Redundant Constraint 15 – X1 ≤ 25 10 – X1 + X2 ≤ 20 Feasible 5– Region | | | | | | 0– 5 10 15 20 25 30 X1 Copyright ©2015 Pearson Education, Inc. 7 – 76  Alternate Optimal Solutions Occasionally two or more optimal solutions may exist Graphically this occurs when the objective function’s isoprofit or isocost line runs perfectly parallel to one of the constraints Allows management great flexibility in deciding which combination to select as the profit is the same at each alternate solution Maximize profit = $3X1 + $2X2 subject to 6X1 + 4X2 ≤ 24 X1 ≤3 X1, X2 ≥ 0 Copyright ©2015 Pearson Education, Inc. 7 – 77  Alternate Optimal Solutions FIGURE 7.15 – Example of Alternate Optimal Solutions Maximize profit = $3X1 + $2X2 X2 subject to 6X1 + 4X2 ≤ 24 X1 ≤3 8– X1, X2 ≥ 0 7– A 6– Optimal Solution Consists of All Combinations of X1 and X2 Along the 5– AB Segment 4– 3– Isoprofit Line for $8 2– B Isoprofit Line for $12 1 – Feasible Overlays Line Segment AB Region | | | | | | | | 0– 1 2 3 4 5 6 7 8 X1 Copyright ©2015 Pearson Education, Inc. 7 – 78  Sensitivity Analysis Optimal solutions to LP problems thus far have been found under deterministic assumptions – We assume complete certainty in the data and relationships of a problem Real world conditions are dynamic Analyze how sensitive a deterministic solution is to changes in the assumptions of the model This is called sensitivity analysis, postoptimality analysis, parametric programming, or optimality analysis Copyright ©2015 Pearson Education, Inc. 7 – 79  Sensitivity Analysis Involves a series of what-if? questions concerning constraints, variable coefficients, and the objective function Trial-and-error method – Values are changed and the entire model is resolved Preferred way is to use an analytic postoptimality analysis – After a problem has been solved, we determine a range of changes in problem parameters that will not affect the optimal solution or change the variables in the solution Copyright ©2015 Pearson Education, Inc. 7 – 80  High Note Sound Company The company manufactures quality speakers and stereo receivers Products require a certain amount of skilled artisanship which is in limited supply Product mix LP model Maximize profit = $50X1 + $120X2 subject to 2X1 + 4X2 ≤ 80 (hours of electricians’ time available) 3X1 + 1X2 ≤ 60 (hours of audio technicians’ time available) X1, X2 ≥ 0 Copyright ©2015 Pearson Education, Inc. 7 – 81  High Note Sound Company FIGURE 7.16 – The High Note Sound Company Graphical Solution X2 (Receivers) 60 – Optimal Solution at Point a – X1 = 0 Speakers 40 – X2 = 20 Receivers Profits = $2,400 a = (0, 20)– b = (16, 12) 20 – Isoprofit Line: $2,400 = 50X1 + 120X2 10 – | | | | | | 0– 10 20 30 40 50 60 X1 c = (20, 0) (Speakers) Copyright ©2015 Pearson Education, Inc. 7 – 82  High Note Sound Company Electrician hours used are 2X1 + 4X2 = 2(0) + 4(20) = 80 – All hours are utilized so slack = 0 – Additional units of a binding constraint will generally increase profits Technician hours used are 3X1 + 1X2 = 3(0) + 1(20) = 20 – Available hours = 60 so slack = 60 – 20 = 40 – Additional units of a nonbinding constraint will only increase slack Copyright ©2015 Pearson Education, Inc. 7 – 83  Changes in the Objective Function Coefficient Contribution rates in the objective functions fluctuate – The feasible solution region remains exactly the same – The slope of the isoprofit or isocost line changes Modest increases or decreases in objective function coefficients may not change the current optimal corner point Know how much an objective function coefficient can change before the optimal solution would be at a different corner point Copyright ©2015 Pearson Education, Inc. 7 – 84  Changes in the Objective Function Coefficient FIGURE 7.17 – Changes in the Receiver Contribution Coefficients X2 40 – Profit Line for 50X1 + 80X2 (Passes through Point b) 30 – Old Profit Line for 50X1 + 120X2 (Passes through Point a) 20 – b a Profit Line for 50X1 + 150X2 (Passes through Point a) 10 – c | | | | | | 0– 10 20 30 40 50 60 X1 Copyright ©2015 Pearson Education, Inc. 7 – 85  QM for Windows PROGRAM 7.6A – Input to QM for Windows High Note Sound Copyright ©2015 Pearson Education, Inc. 7 – 86  QM for Windows PROGRAM 7.6B – High Note Sound Sensitivity Analysis Copyright ©2015 Pearson Education, Inc. 7 – 87  Excel Solver PROGRAM 7.7A – Excel Spreadsheet for High Note Sound Copyright ©2015 Pearson Education, Inc. 7 – 88  Excel Solver PROGRAM 7.7B – Excel 2013 Solution and Solver Results Copyright ©2015 Pearson Education, Inc. 7 – 89  Excel Solver PROGRAM 7.7C – Excel 2013 Sensitivity Report Copyright ©2015 Pearson Education, Inc. 7 – 90  Changes in the Technological Coefficients Changes in the technological coefficients often reflect changes in the state of technology If the amount of resources needed to produce a product changes, coefficients in the constraint equations will change Objective function does not change May produce significant change in the shape of the feasible region May cause a change in the optimal solution Copyright ©2015 Pearson Education, Inc. 7 – 91  Changes in the Technological Coefficients FIGURE 7.18 – Change in the Technological Coefficients (a) Original Problem (b) Change in Circled (c) Change in Circled Coefficient Coefficient X2 X2 X2 60 – 60 – 60 – Stereo Receivers 3X1 + 1X2 ≤ 60 2 X1 + 1X2 ≤ 60 3X1 + 1X2 ≤ 60 40 – 40 – 40 – Optimal Still Optimal a Solution a Optimal Solution 20 – 20 – d 20 – f b 2X1 + 4X2 ≤ 80 2X1 + 4X2 ≤ 80 16 g 2X1 + 5 X2 ≤ 80 |c | | | e | | | |c | | 0 20 40 X1 0 20 30 40 X1 0 20 40 X1 CD Players Copyright ©2015 Pearson Education, Inc. 7 – 92  Changes in Resources or Right-Hand-Side Values Right-hand-side values of the constraints often represent resources available to the firm Additional resources may lead to higher total profit Sensitivity analysis about resources helps answer questions about – How much should be paid for additional resources – How much more of a resource would be useful Copyright ©2015 Pearson Education, Inc. 7 – 93  Changes in Resources or Right-Hand-Side Values Changing the RHS will change the feasible region, unless the constraint is redundant Often changes the optimal solution The dual price or dual value – The amount of change in the objective function value that results from a unit change in one of the resources – The dual price for a constraint is the improvement in the objective function value that results from a one-unit increase in the right-hand side of the constraint Copyright ©2015 Pearson Education, Inc. 7 – 94  Changes in Resources or Right-Hand-Side Values The amount of possible increase in the RHS is limited If the RHS is increased beyond the upper bound, then the objective function would no longer increase by the dual price There would be excess (slack) resources or the objective function may change by an amount different from the dual price The dual price is relevant only within limits Copyright ©2015 Pearson Education, Inc. 7 – 95  Changes in the Electricians’ Time Resource FIGURE 7.19 X2 (a) 60 – Constraint Representing 60 Hours of 40 – Audio Technician’s Time Resource a 25 – b Changed Constraint Representing 100 Hours of 20 – Electrician’s Time Resource | c | | | 0 20 40 50 60 X1 Copyright ©2015 Pearson Education, Inc. 7 – 96  Changes in the Electricians’ Time Resource FIGURE 7.19 X2 (b) 60 – Constraint Representing 60 Hours of 40 – Audio Technician’s Time Resource 25 – Changed Constraint Representing 60 Hours of 20 – a Electrician’s Time Resource b c | | | | 0 20 40 50 60 X1 Copyright ©2015 Pearson Education, Inc. 7 – 97  Changes in the Electricians’ Time Resource FIGURE 7.19 X2 (c) 60 – Changed Constraint Representing 240 Hours of Electrician’s Time Resource 40 – Constraint 25 – Representing 60 Hours of Audio 20 – Technician’s Time Resource | | | | | | 0 20 40 60 80 100 120 X1 Copyright ©2015 Pearson Education, Inc. 7 – 98  QM for Windows PROGRAM 7.6B – High Note Sound Sensitivity Analysis Copyright ©2015 Pearson Education, Inc. 7 – 99  Excel Solver PROGRAM 7.7C – Excel 2013 Sensitivity Report Copyright ©2015 Pearson Education, Inc. 7 – 100  Copyright All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the prior written permission of the publisher. Printed in the United States of America. Copyright ©2015 Pearson Education, Inc.