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.

2 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.

3 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.

4 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. 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.

5 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.

6 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.

7 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. 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.

8 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. 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.

9 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. Healthy believesit can sell as much of each dog food as it can make.

10 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.