Linear Programming

1 The Role of Mathematical Models in OperationsDecision Making B2 Constrained Optimization Models B2 Advantages and Disadvantages of Using Optimiza-tion Models B5 Assumptions of Linear Programming Models B6 Formulating Linear Programs B7 The Geometry of Linear Programs B14 The Graphical Solution Approach B15 The Simplex Algorithm B17 Using Artificial Variables B26 Computer Solutions of Linear Programs B29 Using Linear Programming Models for DecisionMaking B32 Before studying this supplement you should know or, if necessary, review1. Competitive priorities, Chapter 22. Capacity management concepts, Chapter 93. Aggregate planning, Chapter 134. Developing a master schedule, Chapter 14 Linear ProgrammingSUPPLEMENTBLEARNING OBJECTIVESA fter studying this supplement, you should be able toDescribe the role of mathematical models in operations decision constrained optimization the advantages and disadvantages ofusing optimization the assumptions of Linear Linear the geometry of Linear the graphical solution the simplex artificial computer solutions of Linear Linear Programming models for decisionmaking.

2 1 2 3 4 5 6 7 8 9 10 11 Adapted with permission from Joseph S. Martinich,Production and Operations Management: An Applied Modern Approach,Wiley, New York, OUTLINEA dvances in business and engineering research and computer technology have ex-panded managers use of mathematical models. A modelrepresents the essential fea-tures of an object, system, or problem without unimportant details. The models inthis supplement have the important aspects represented in mathematical form usingvariables, parameters, and functions. Analyzing and manipulating the model gives in-sight into how the real system behaves under various conditions. From this we deter-mine the best system design or action to models are cheaper, faster, and safer than constructing and ma-nipulating real systems.

3 Suppose we want to find the mixture of recycled scrap paperto use when producing a type of paperboard that minimizes cost. A company couldtry several different combinations, check the quality, and calculate the cost. Since allpossible combinations are not tried, the optimum combination will probably not befound. Alternatively, using a mathematical model, we evaluate all possible combina-tions to find the one that satisfies product specifications at the lowest price. Mathe-matical modeling is quicker and less expensive than using the trial-and-error location, vehicle routing and scheduling, personnel, machine and jobscheduling, product mixes, and inventory management problems are formulated asconstrained optimization optimization modelsare mathemati-cal models that find the best solution with respect to some evaluation criterion from aset of alternative solutions.

4 These solutions are defined by a set of mathematical con-straints mathematical inequalities or BLINEAR PROGRAMMINGTHE ROLE OF MATHEMATICAL MODELS IN OPERATIONS DECISION MAKINGCONSTRAINED OPTIMIZATION MODELSC onstrained optimization models have three major components: decision variables,objective function, and variablesare physical quantities controlled by the decision makerand represented by mathematical symbols. For example, the decision variablexjcan represent the number of pounds of product jthat a company will pro-duce during some month. Decision variables take on any of a set of functiondefines the criterion for evaluating the solution. It is amathematical function of the decision variables that converts a solution intoa numerical evaluation of that solution.

5 For example, the objective functionmay measure the profit or cost that occurs as a function of the amounts ofvarious products produced. The objective function also specifies a directionof optimization, either to maximize or minimize. An optimal solution for themodel is the best solution as measured by that a set of functional equalities or inequalities that representphysical, economic, technological, legal, ethical, or other restrictions on whatnumerical values can be assigned to the decision variables. For example, con-straints might ensure that no more input is used than is available. Con-straints can be definitional, defining the number of employees at the start ofa period t 1 as equal to the number of employees at the start of period t,plus those added during period tminus those leaving the organization dur-ing period t.

6 In constrained optimization models we find values for the A modelrepresents the es-sential features of an object,system, or problem withoutunimportant details. Constrained optimizationmodelsMath models that find thebest solution with respect tosome evaluation criterion. Decision variablesPhysical quantities controlledby the decision maker. Objective functionEvaluation criterion. ConstraintsPhysical, economic, techno-logical, legal, ethical, or otherlimits on what numerical val-ues can be assigned to the de-cision Healthy Pet Food Company manufactures two types of dog food: Meaties and Yum-mies. Each package of Meaties contains 2 pounds of cereal and 3 pounds of meat; eachpackage of Yummies contains 3 pounds of cereal and pounds of meat.

7 Healthy believesit can sell as much of each dog food as it can make. Meaties sell for $ per package andYummies sell for $ per package. Healthy s production is limited in several ways. First,Healthy can buy only up to 400,000 pounds of cereal each month at $ per pound. It canbuy only up to 300,000 pounds of meat per month at $ per pound. In addition, a spe-cial piece of machinery is required to make Meaties, and this machine has a capacity of90,000 packages per month. The variable cost of blending and packing the dog food is $ package for Meaties and $ per package for Yummies. This information is given inTable OPTIMIZATION MODELSB3decision variables that maximize or minimize the objective function and sat-isfy all following example shows how an operational problem can be representedand analyzed using a constrained optimization model.

8 Example The Healthy Pet Food Company Product MixTable B-1 Healthy Pet Food DataMeatiesYummiesSales price per package$ $ materials per cost blending and packing$ package$ packageResourcesProduction capacity for Meaties90,000 packages per monthCereal available per month400,000 available per month300,000 you are the manager of the Dog Food Division of the Healthy Pet Food Com-pany. Your salary is based on division profit, so you try to maximize its profit. How shouldyou operate the division to maximize its profit and your salary?Solution:The Decision Variables. We first identify those things over which we have control: the deci-sion this problem we have direct control over two quantities: the number ofpackages of Meaties to make each month, and the number of packages of Yummies to makeeach month.

9 Within the model these two quantities appear repeatedly, so we represent themin a simple fashion. We designate these variables by the symbols Mand number of packages of Meaties to make each monthY number of packages of Yummies to make each monthNote that the amount of meat used each month and the amount of cereal used eachmonth are not good choices for the variables. First, we control these only indirectly throughour choice ofMand Y. More important, using these as variables could lead to ambiguousproduction plans. Determining how much cereal and meat to use in production does not tell us how to use it how much of each dog food to make.

10 In contrast, after determiningthe values for Mand Y, we know what to produce and how much meat and cereal function. Any pair of numerical values for the variables Mand Yis a produc -tion plan. For example,M 10,000 and Y 20,000 means we make 10,000 packages ofMeaties and 20,000 packages of Yummies each month. But how do we know whether this isa good production plan? We need to specify a criterion for evaluation an objective most appropriate objective function is to maximize monthly profit. (Actually, thisis the contribution to profit: fixed costs are ignored because any plan that maximizes rev-enue minus variable costs maximizes profit as well.)