Chapter (3) Linear Programming Models Graphical Method.pptx

cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc

1. Quantitative Analysis for Management Fourteenth Edition Chapter 3 Linear Programming Models: Graphical Method Copyright © 2024, 2018, 2015 Pearson Education, Inc. All Rights Reserved

2. Learning Objectives After completing this chapter, students will be able to: 7.1 Identify the basic assumptions and properties of linear programming (L P). 7.2 Formulate a linear programming problem algebraically. 7.3 Graphically solve any L P problem that has only two variables by both the corner point and i s o profit line methods. 7.4 Understand the difference between minimization and maximization objective functions. 7.5 Understand special issues in L P such as infeasibility, unboundedness, redundancy, and alternative optimal solutions .

3. Requirements of a Linear Programming Problem Linear programming (L P) Mathematical modeling technique Resource allocation—product mix Four properties in common Maximize or minimize some quantity (the objective function ) Restrictions or constraints are present Alternative courses of action are available Linear equations or inequalities

4. L P Properties and Assumptions Table 7.1 L P Properties and Assumptions of Linear Programs Properties of Linear Programs One objective function One or more constraints Alternative courses of action Objective function and constraints are linear—proportionality and divisibility Certainty Divisibility Nonnegative variables

5. Formulating L P Problems Steps in formulating a L P problem Identify the objective and the constraints Define the decision variables Write mathematical expressions for the objective function and the constraints in terms of the decision variables

6. Flair Furniture Company (1 of 2) Product mix problem Maximize profit based on combination of two products Limited resources available Table 7.2 Flair Furniture Company Data Department Hours Required to Produce 1 Unit Tables ( T ) Hours Required to Produce 1 Unit Chairs ( C ) Available Hours this Week Carpentry 4 3 240 Painting and varnishing 2 1 100 Profit per unit $70 $50 Blank

7. Flair Furniture Company (2 of 2) Create objective function in terms of T and C Maximize profit = $70 T + $50 C Develop mathematical relationships for the two constraints For carpentry, total time used is (hours of carpentry time available) For painting and varnishing (hours painting and varnishing time) Values for T and C must be nonnegative

8. Graphical Representation of Constraints (1 of 7) Figure 7.1 Quadrant Containing All Positive Values Works with just two decision variables Provides valuable insight into how other approaches work

9. Graphical Representation of Constraints (2 of 7) Plot each constraint equation on a graph Graph the equality portion of the constraint equations 4 T + 3 C = 240 Easiest way to plot 4 T + 3 C = 240 is to set T = 0 and solve for C ; then set C = 0 and solve for T . Then connect these two points with a straight line. C = 80 when T = 0 T = 60 when C = 0

10. Graphical Representation of Constraints (3 of 7) Figure 7.2 Graph of Carpentry Constraint Equation 4 T + 3 C = 240

11. Graphical Representation of Constraints (4 of 7) Figure 7.3 Region That Satisfies the Carpentry Constraint Any point on or below the constraint plot will not violate the restriction Any point above the plot will violate the restriction

12. Graphical Representation of Constraints (5 of 7) Figure 7.4 Region That Satisfies the Painting and Varnishing Constraint

13. Graphical Representation of Constraints (6 of 7) 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

14. Graphical Representation of Constraints (7 of 7) Figure 7.5 Feasible Solution Region for the Flair Furniture Company Problem Test these combinations: T = 30, C = 20 T = 70, C = 40 T = 50, C = 5

15. I s o profit Line Solution Method (1 of 5) Find the optimal solution from the many possible solutions Speediest method is to use the i s o profit 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

16. I s o profit Line Solution Method (2 of 5) Choose a profit of $2,100 The objective function is $2,100 = 70 T + 50 C 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 i s o profit line passes through the point (30, 40)

17. I s o profit Line Solution Method (3 of 5) Figure 7.6 Profit Line of $2,100 Plotted for the Flair Furniture Company

18. I s o profit Line Solution Method (4 of 5) Figure 7.7 Four I s o profit Lines Plotted for the Flair Furniture Company

19. I s o profit Line Solution Method (5 of 5) Figure 7.8 Optimal Solution to the Flair Furniture Problem

20. Corner Point Solution Method (1 of 3) 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 and add it to the first equation

21. Corner Point Solution Method (2 of 3) Figure 7.9 Four Corner Points of the Feasible Region Evaluate the objective function at every corner point of the feasible region An optimal solution must lie at one of the corner points or extreme points

22. Corner Point Solution Method (3 of 3) Substitute C = 40 into either equation to solve for T Thus, the corner point is (30, 40) Table 7.3 Feasible Corner Points and Profits for Flair Furniture

23. Slack and Surplus (1 of 2) Slack is the amount of a resource that is not used For a less-than-or-equal constraint Ex. Flair decides to produce 20 tables and 25 chairs 240 = hours carpentry time available At the optimal solution, slack is 0 as all 240 hours are used

24. Slack and Surplus (2 of 2) 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 New constraint If T = 20 and C = 25, then 20 + 25 = 45

25. Summaries of Graphical Solution Methods (1 of 2) Table 7.4 Summaries of Graphical Solution Methods I s o profit Line Method Graph all constraints and find the feasible region. Select a specific profit (or cost) line and graph it to find the slope. 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. Find the values of the decision variables at this last point and compute the profit (or cost).

26. Summaries of Graphical Solution Methods (2 of 2) Table 7.4 [continued] Corner Point Method Graph all constraints and find the feasible region. Find the corner points of the feasible region. Compute the profit (or cost) at each of the feasible corner points. Select the corner point with the best value of the objective function found in step 3. This is the optimal solution.

27. Holiday Meal Turkey Ranch (1 of 6) 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 Ingredient Composition of Each Pound of Feed (O Z.) Brand 1 Feed Composition of Each Pound of Feed (O Z.) Brand 2 Feed Minimum Monthly Requirement per Turkey (O Z.) A 5 10 90 B 4 3 48 C 0.5 1.5 Cost per pound 2 cents 3 cents Blank This is a minimization problem—low cost is the objective.

28. Holiday Meal Turkey Ranch (2 of 6) Let number of pounds of brand 1 feed purchased number of pounds of brand 2 feed purchased subject to: (ingredient A constraint) (ingredient B constraint) (ingredient C constraint) (nonnegativity constraint) (nonnegativity constraint)

29. Holiday Meal Turkey Ranch (3 of 6) Figure 7.10 Feasible Region for the Holiday Meal Turkey Ranch Problem

30. Holiday Meal Turkey Ranch (4 of 6) Solve for the values of the three corner points Point a is the intersection of ingredient constraints C and B Substituting 3 in the first equation, we find Solving for point b we find Solving for point c we find

31. Holiday Meal Turkey Ranch (5 of 6) Substituting these values back into the objective function we find 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

32. Holiday Meal Turkey Ranch (6 of 6) Figure 7.11 Graphical Solution to the Holiday Meal Turkey Ranch Problem Using the I s o cost Line Move the i s o cost line down and left. The last feasible point touched is optimal.

33. Four Special Cases in L P Four special cases and difficulties arise at times when using the graphical approach No feasible solution Unboundedness Redundancy Alternate optimal solutions

34. No Feasible Solution A common occurrence in the real world No solution satisfies all the constraints Generally, one or more constraints are relaxed Figure 7.12 A problem with no feasible solution

35. Unboundedness Sometimes a linear program will not have a finite solution In a maximization problem, the profit, can be made infinitely large without violating any constraints Usually means the problem has been formulated improperly Figure 7.13 A Feasible Region That Is Unbounded to the Right

36. Redundancy A redundant constraint is one that does not affect the feasible solution region, eliminating it simplifies the model One or more constraints may be binding Very common occurrence in the real world Figure 7.14 Example of a Redundant Constraint

37. Alternate Optimal Solutions Occasionally, two or more optimal solutions may exist Graphically, this occurs when the objective function’s i s o profit or i s o cost line runs perfectly parallel to one of the constraints Allows management great flexibility in selecting solutions Figure 7.15 Example of Alternate Optimal Solutions

38. Copyright This work is protected by United States copyright laws and is provided solely for the use of instructors in teaching their courses and assessing student learning. Dissemination or sale of any part of this work (including on the World Wide Web) will destroy the integrity of the work and is not permitted. The work and materials from it should never be made available to students except by instructors using the accompanying text in their classes. All recipients of this work are expected to abide by these restrictions and to honor the intended pedagogical purposes and the needs of other instructors who rely on these materials.