Linear Programming: Basic Concepts and Graphical Solution

Chapter 3Linear Programming:Basic Concepts and Graphical SolutionPart 2 Introduction to Management Science and ForecastingLearning ObjectivesExplain what is meant by the terms constrained optimization and linear programming.List the components and the assumptions of linear programming and briefly explain each.Name and describe at least three successful applications of linear programming.Identify the type of problems that can be solved using linear programming.Formulate simple linear programming models.Identify LP problems that are amenable to graphical solutions.After completing this chapter, you should be able to:2Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Learning Objectives (cont’d)Explain these terms: optimal solution, feasible solution space, corner point, redundant constraint slack, and surplus.Solve two-variable LP problems graphically and interpret your answers.Identify problems that have multiple solutions, problems that have no feasible solutions, unbounded problems, and problems with redundant constraints.After completing this chapter, you should be able to:3Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Decisions and Linear ProgrammingConstrained optimizationFinding the optimal solution to a problem given that certain constraints must be satisfied by the solution.A form of decision making that involves situations in which the set of acceptable solutions is somehow restricted.Recognizes scarcity—the limitations on the availability of physical and human resources.Seeks solutions that are both efficient and feasible in the allocation of resources.4Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Linear ProgrammingLinear Programming (LP)A family of mathematical techniques (algorithms) that can be used for constrained optimization problems with linear relationships.Graphical methodSimplex methodKarmakar’s methodThe problems must involve a single objective, a linear objective function, and linear constraints and have known and constant numerical values.5Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 3–1 6Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Table 3–1 Successful Applications of Linear Programming Published in Interfaces7Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Table 3–2 Characteristics of LP Models8Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Formulating LP ModelsFormulating linear programming models involves the following steps: Define the decision variables. Determine the objective function. Identify the constraints. Determine appropriate values for parameters and determine whether an upper limit, lower limit, or equality is called for. Use this information to build a model. Validate the model.9Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 3–2 x1 = quantity of server model 1 to producex2 = quantity of server model 2 to producemaximize Z = 60x1+50x2Subject to:10Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Graphing the ModelThis method can be used only to solve problems that involve two decision variables.The graphical approach: Plot each of the constraints. Determine the region or area that contains all of the points that satisfy the entire set of constraints. Determine the optimal solution.11Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Key Terms in GraphingOptimal solutionFeasible solution spaceCorner pointRedundant constraintSlackSurplus12Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 3–1 A Graph Showing the Nonnegativity Constraints13Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 3–2 Feasible Region Based on a Plot of the First Constraint(assembly time) and the Nonnegativity Constraint14Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 3–3 A Completed Graph of the Server Problem Showing theAssembly and Inspection Constraints and the FeasibleSolution Space15Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 3–4 Completed Graph of the Server Problem Showing All of theConstraints and the Feasible Solution Space16Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Finding the Optimal SolutionThe extreme point approachInvolves finding the coordinates of each corner point that borders the feasible solution space and then determining which corner point provides the best value of the objective function.The extreme point theorem If a problem has an optimal solution at least one optimal solution will occur at a corner point of the feasible solution space.17Copyright © 2007 The McGraw-Hill Companies. All rights reserved. The Extreme Point ApproachGraph the problem and identify the feasible solution space.Determine the values of the decision variables at each corner point of the feasible solution space. Substitute the values of the decision variables at each corner point into the objective function to obtain its value at each corner point.After all corner points have been evaluated in a similar fashion, select the one with the highest value of the objective function (for a maximization problem) or lowest value (for a minimization problem) as the optimal solution.18Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 3–5 Graph of Server Problem with Extreme Points of the FeasibleSolution Space Indicated19Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Table 3–3 Extreme Point Solutions for the Server Problem20Copyright © 2007 The McGraw-Hill Companies. All rights reserved. The Objective Function (Iso-Profit Line) ApproachThis approach directly identifies the optimal corner point, so only the coordinates of the optimal point need to be determined.Accomplishes this by adding the objective function to the graph and then using it to determine which point is optimal. Avoids the need to determine the coordinates of all of the corner points of the feasible solution space.21Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 3–6 The Server Problem with Profit Lines of $300, $600, and $90022Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 3–7 Finding the Optimal Solution to the Server Problem23Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Graphing—Objective Function ApproachGraph the constraints.Identify the feasible solution space.Set the objective function equal to some amount that is divisible by each of the objective function coefficients. After identifying the optimal point, determine which two constraints intersect there.Substitute the values obtained in the previous step into the objective function to determine the value of the objective function at the optimum.24Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 3–8 A Comparison of Maximization and Minimization Problems25Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 3-3 MinimizationDetermine the values of decision variables x1 and x2 that will yield the minimum cost in the following problem. Solve using the objective function approach.26Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 3–9 Graphing the Feasible Region and Using the ObjectiveFunction to Find the Optimum for Example 3-327Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 3-428Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Table 3–3 Summary of Extreme Point Analysis for Example 3-429Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Table 3–5 Computing the Amount of Slack for the Optimal Solution tothe Server Problem30Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Some Special IssuesNo Feasible SolutionsOccurs in problems where to satisfy one of the constraints, another constraint must be violated.Unbounded ProblemsExists when the value of the objective function can be increased without limit.Redundant ConstraintsA constraint that does not form a unique boundary of the feasible solution space; its removal would not alter the feasible solution space.Multiple Optimal SolutionsProblems in which different combinations of values of the decision variables yield the same optimal value.31Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 3–10 Infeasible Solution: No Combination of x1 and x2, CanSimultaneously Satisfy Both Constraints32Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 3–11 An Unbounded Solution Space33Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 3–12 Examples of Redundant Constraints34Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 3–13 Multiple Optimal Solutions35Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 3–14 Constraints and Feasible Solution Space for Solved Problem 236Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 3–15 A Graph for Solved Problem 337Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 3–16 Graph for Solved Problem 438Copyright © 2007 The McGraw-Hill Companies. All rights reserved.