Linear Programming - Pearson Education
HEIZMX0B 013185755X.QXD5/4/052:39 PMPage 691Quantitative ModuleLinear ProgrammingBModule OutlineREQUIREMENTS OF A LINEARPROGRAMMING PROBLEMDiet Problem ExampleFORMULATING LINEARPROGRAMMING PROBLEMSLabor Scheduling ExampleShader Electronics ExampleGRAPHICAL SOLUTION TO A LINEARPROGRAMMING PROBLEMGraphical Representation of ConstraintsIso-Profit Line Solution MethodCorner-Point Solution MethodSENSITIVITY ANALYSISSensitivity ReportChanges in the Resourcesor Right-Hand-Side ValuesChanges in the Objective FunctionCoefficientSOLVING MINIMIZATION PROBLEMSLINEAR PROGRAMMING APPLICATIONSProduction-Mix ExampleProduction Scheduling ExampleTHE SIMPLEX METHOD OF LPSUMMARYKEY TERMSUSING SOFTWARE TO SOLVE LP PROBLEMSSOLVED PROBLEMSINTERNET AND STUDENT CD-ROM EXERCISESL EARNING O BJECTIVESWhen you complete this module youshould be able toDISCUSSION QUESTIONSACTIVE MODEL EXERCISEPROBLEMSINTERNET HOMEWORK PROBLEMSIDENTIFY OR DEFINE:Objective functionCASE STUDY: GOLDING LANDSCAPING AND PLANTS, INC.ConstraintsADDITIONAL CASE STUDIESFeasible regionBIBLIOGRAPHYIso-profit/iso-cost methodsCorner-point solutionShadow priceDESCRIBE OR EXPLAIN:How to formulate linear modelsGraphical method of linear programmingHow to interpret sensitivity analysis
HEIZMX0B 013185755X.QXD6925/4/05MODULE B2:40 PMPage 692L I N E A R P RO G R A M M I N GThe storm front closed in quickly on Chicago’s O’Hare Airport, shutting it down without warning. The heavythunderstorms, lightning, and poor visibility sent American Airlines passengers and ground crew scurrying.Because American Airlines uses linear programming (LP) to schedule flights, hotels, crews, and refueling, LP has adirect impact on profitability. As the president of AA’s Decision Technology Group says, “Finding fast solutions toLP problems is essential. If we get a major weather disruption at one of the hubs, such as Dallas or Chicago, then alot of flights may get canceled, which means we have a lot of crews and airplanes in the wrong places. What weneed is a way to put that whole operation back together again.” LP is the tool that helps airlines such as Americanunsnarl and cope with this weather mess.Linear Programming(LP)A mathematicaltechnique designed tohelp operations managersplan and make decisionsrelative to the trade-offsnecessary to allocateresources.Many operations management decisions involve trying to make the most effective use of an organization’s resources. Resources typically include machinery (such as planes, in the case of an airline),labor (such as pilots), money, time, and raw materials (such as jet fuel). These resources may beused to produce products (such as machines, furniture, food, or clothing) or services (such as airlineschedules, advertising policies, or investment decisions). Linear programming (LP) is a widelyused mathematical technique designed to help operations managers plan and make the decisionsnecessary to allocate resources.A few examples of problems in which LP has been successfully applied in operations management are1.2.3.4.5.6.7.8.Scheduling school buses to minimize the total distance traveled when carrying students.Allocating police patrol units to high crime areas to minimize response time to 911calls.Scheduling tellers at banks so that needs are met during each hour of the day whileminimizing the total cost of labor.Selecting the product mix in a factory to make best use of machine- and labor-hours available while maximizing the firm’s profit.Picking blends of raw materials in feed mills to produce finished feed combinations atminimum cost.Determining the distribution system that will minimize total shipping cost from severalwarehouses to various market locations.Developing a production schedule that will satisfy future demands for a firm’s product andat the same time minimize total production and inventory costs.Allocating space for a tenant mix in a new shopping mall so as to maximize revenues to theleasing company. (See the OM in Action box “Using LP to Select Tenants in a ShoppingMall.”)
HEIZMX0B 013185755X.QXD5/4/052:40 PMPage 693F O R M U L AT I N GLINEARP RO G R A M M I N G P RO B L E M S693OM IN ACTIONUsing LP to Select Tenantsin a Shopping MallHomart Development Company is one of the largestshopping-center developers in the U.S. When starting anew center, Homart produces a tentative floor plan, or“footprint,” for the mall. This plan outlines sizes, shapes,and spaces for large department stores. Leasing agreements are reached with the two or three major department stores that will become anchor stores in the mall.The anchor stores are able to negotiate highly favorableoccupancy agreements. Homart’s profits come primarilyfrom the rent paid by the nonanchor tenants—the smallerstores that lease space along the aisles of the mall. Thedecision as to allocating space to potential tenants is,therefore, crucial to the success of the investment.The tenant mix describes the desired stores in the mallby their size, general location, and type of merchandiseor service provided. For example, the mix might specifytwo small jewelry stores in a central section of the malland a medium-size shoe store and a large restaurant inone of the side aisles. In the past, Homart developed aplan for tenant mix using “rules of thumb” developedover years of experience in mall development.Now, to improve its bottom line in an increasinglycompetitive marketplace, Homart treats the tenant-mixproblem as an LP model. First, the model assumes thattenants can be classified into categories according tothe type of merchandise or service they provide.Second, the model assumes that for each store type,store sizes can be estimated by distinct category. Forexample, a small jewelry store is said to contain about700 square feet and a large one about 2,200 squarefeet. The tenant-mix model is a powerful tool for enhancing Homart’s mall planning and leasing activities.Sources: Chain Store Age (March 2000): 191–192; Business World (March18, 2002): 1; and Interfaces (March–April 1988): 1–9.REQUIREMENTS OF A LINEAR PROGRAMMING PROBLEMAll LP problems have four properties in common:1.Objective functionA mathematicalexpression in linearprogramming thatmaximizes or minimizessome quantity (oftenprofit or cost, but anygoal may be used).ConstraintsRestrictions that limitthe degree to whicha manager can pursuean objective.LP problems seek to maximize or minimize some quantity (usually profit or cost). We referto this property as the objective function of an LP problem. The major objective of a typical firm is to maximize dollar profits in the long run. In the case of a trucking or airline distribution system, the objective might be to minimize shipping costs.2. The presence of restrictions, or constraints, limits the degree to which we can pursue ourobjective. For example, deciding how many units of each product in a firm’s product line tomanufacture is restricted by available labor and machinery. We want, therefore, to maximizeor minimize a quantity (the objective function) subject to limited resources (the constraints).3. There must be alternative courses of action to choose from. For example, if a companyproduces three different products, management may use LP to decide how to allocateamong them its limited production resources (of labor, machinery, and so on). If there wereno alternatives to select from, we would not need LP.4. The objective and constraints in linear programming problems must be expressed in termsof linear equations or inequalities.FORMULATING LINEAR PROGRAMMING PROBLEMSOne of the most common linear programming applications is the product-mix problem. Two or moreproducts are usually produced using limited resources. The company would like to determine howmany units of each product it should produce to maximize overall profit given its limited resources.Let’s look at an example.Active Model B.1This example is furtherillustrated in Activemodel B.1 on theCD-ROM and in theexercise on page 713.Shader Electronics ExampleThe Shader Electronics Company produces two products: (1) the Shader Walkman, a portableCD/DVD player, and (2) the Shader Watch-TV, a wristwatch-size internet-connected color television. The production process for each product is similar in that both require a certain number ofhours of electronic work and a certain number of labor-hours in the assembly department. EachWalkman takes 4 hours of electronic work and 2 hours in the assembly shop. Each Watch-TVrequires 3 hours in electronics and 1 hour in assembly. During the current production period, 240
HEIZMX0B 013185755X.QXD6945/4/05MODULE B2:40 PMPage 694L I N E A R P RO G R A M M I N Ghours of electronic time are available, and 100 hours of assembly department time are available.Each Walkman sold yields a profit of 7; each Watch-TV produced may be sold for a 5 profit.Shader’s problem is to determine the best possible combination of Walkmans and Watch-TVs tomanufacture to reach the maximum profit. This product-mix situation can be formulated as a linearprogramming problem.TABLE B.1 Shader ElectronicsCompany ProblemDataDEPARTMENTElectronicAssemblyProfit per unitHOURS REQUIRED TO PRODUCE 1 UNITWALKMANSWATCH-TVS(X1)(X2)42 7AVAILABLE HOURS THIS WEEK31 5240100We begin by summarizing the information needed to formulate and solve this problem (seeTable B.1). Further, let’s introduce some simple notation for use in the objective function and constraints. LetWe name the decisionvariables X1 and X2 herebut point out that anynotation (such as WM andWT) would be fine as well.X1 number of Walkmans to be producedX2 number of Watch-TVs to be producedNow we can create the LP objective function in terms of X1 and X2:Maximize profit 7X1 5X2Our next step is to develop mathematical relationships to describe the two constraints in this problem. One general relationship is that the amount of a resource used is to be less than or equal to ( )the amount of resource available.First constraint: Electronic time used is Electronic time available.4X1 3X2 240 (hours of electronic time)Second constraint: Assembly time used is Assembly time available.2X1 1X2 100 (hours of assembly time)Both these constraints represent production capacity restrictions and, of course, affect the totalprofit. For example, Shader Electronics cannot produce 70 Walkmans during the production periodbecause if X1 70, both constraints will be violated. It also cannot make X1 50 Walkmans andX2 10 Watch-TVs. This constraint brings out another important aspect of linear programming; thatis, certain interactions will exist between variables. The more units of one product that a firm produces, the fewer it can make of other products.GRAPHICAL SOLUTION TO A LINEARPROGRAMMING PROBLEMGraphical solutionapproachA means of plotting asolution to a two-variableproblem on a graph.The easiest way to solve a small LP problem such as that of the Shader Electronics Company is thegraphical solution approach. The graphical procedure can be used only when there are twodecision variables (such as number of Walkmans to produce, X1, and number of Watch-TVs to produce, X2). When there are more than two variables, it is not possible to plot the solution on a twodimensional graph; we then must turn to more complex approaches described later in this module.Graphical Representation of ConstraintsDecision variablesChoices available to adecision maker.To find the optimal solution to a linear programming problem, we must first identify a set, orregion, of feasible solutions. The first step in doing so is to plot the problem’s constraints on agraph.
HEIZMX0B 013185755X.QXD5/4/052:40 PMPage 695GRAPHICAL SOLUTIONTO AL I N E A R P RO G R A M M I N G P RO B L E M695The variable X1 (Walkmans, in our example) is usually plotted as the horizontal axis of the graph, andthe variable X2 (Watch-TVs) is plotted as the vertical axis. The complete problem may be restated as:Maximize profit 7X1 5X2Subject to the constraints4 X1 3 X2 240 (electronics constraint )2 X1 1X2 100 ( assembly constraint )These two constraints arealso called thenonnegativity constraints.X1 0 (number of Walkmans produced is greater than or equal to 0)X2 0 (number of Watch-TVs produced is greater than or equal to 0)The first step in graphing the constraints of the problem is to convert the constraint inequalities intoequalities (or equations).Feasible regionThe set of all feasiblecombinations of decisionvariables.Constraint A:4X1 3X2 240Constraint B:2X1 1X2 100The equation for constraint A is plotted in Figure B.1 and for constraint B in Figure B.2.To plot the line in Figure B.1, all we need to do is to find the points at which the line 4X1 3X2 240intersects the X1 and X2 axes. When X1 0 (the location where the line touches the X2 axis), it impliesthat 3X2 240 and that X2 80. Likewise, when X2 0, we see that 4X1 240 and that X1 60. Thus,constraint A is bounded by the line running from (X1 0, X2 80) to (X1 60, X2 0). The shaded arearepresents all points that satisfy the original inequality.Constraint B is illustrated similarly in Figure B.2. When X1 0, then X2 100; and when X2 0,then X1 50. Constraint B, then, is bounded by the line between (X1 0, X2 100) and (X1 50,X2 0). The shaded area represents the original inequality.Figure B.3 shows both constraints together. The shaded region is the part that satisfies bothrestrictions. The shaded region in Figure B.3 is called the area of feasible solutions, or simplythe feasible region. This region must satisfy all conditions specified by the program’s constraints and is thus the region where all constraints overlap. Any point in the region would be afeasible solution to the Shader Electronics Company problem. Any point outside the shaded areawould represent an infeasible solution. Hence, it would be feasible to manufacture 30 WalkmansX2X2100100( X1 0, X2 100)Number of Watch-TVsNumber of Watch-TVs( X1 0, X2 80)8060Constraint A4020( X1 60, X2 0)020406080Number of WalkmansFIGURE B.1 Constraint A100X18060Constraint B4020( X1 50, X2 0)020406080Number of WalkmansFIGURE B.2 Constraint B100X1
HEIZMX0B 013185755X.QXD6965/4/05MODULE B2:40 PMPage 696L I N E A R P RO G R A M M I N GFIGURE B.3 X2Feasible Solution Regionfor the Shader ElectronicsCompany Problem100Number of Watch-TVs80Assembly (constraint B)6040Electronics (constraint A)Feasibleregion20020406080Number of Walkmans100X1and 20 Watch-TVs (X1 30, X2 20), but it would violate the constraints to produce 70 Walkmansand 40 Watch-TVs. This can be seen by plotting these points on the graph of Figure B.3.Iso-Profit Line Solution MethodIso-profit line methodAn approach to solvinga linear programmingmaximization problemgraphically.Now that the feasible region has been graphed, we can proceed to find the optimal solution to the problem. The optimal solution is the point lying in the feasible region that produces the highest profit.Once the feasible region has been established, several approaches can be taken in solving for theoptimal solution. The speediest one to apply is called the iso-profit line method.1We start by letting profits equal some arbitrary but small dollar amount. For the ShaderElectronics problem, we may choose a profit of 210. This is a profit level that can easily beobtained without violating either of the two constraints. The objective function can be written as 210 7X1 5X2.This expression is just the equation of a line; we call it an iso-profit line. It represents all combinations (of X1, X2) that will yield a total profit of 210. To plot the profit line, we proceed exactly as wedid to plot a constraint line. First, let X1 0 and solve for the point at which the line crosses the X2 axis: 210 7(0) 5 X2X2 42 Watch-TVsThen let X2 0 and solve for X1: 210 7 X1 5(0)X1 30 WalkmansWe can now connect these two points with a straight line. This profit line is illustrated in Figure B.4.All points on the line represent feasible solutions that produce a profit of 210.We see, however, that the iso-profit line for 210 does not produce the highest possible profit tothe firm. In Figure B.5, we try graphing two more lines, each yielding a higher profit. The middleequation, 280 7X1 5X2, was plotted in the same fashion as the lower line. When X1 0, 280 7(0) 5 X2X2 56 Watch-TVs1Isomeans “equal” or “similar.” Thus, an iso-profit line represents a line with all profits the same, in this case 210.
HEIZMX0B 013185755X.QXD5/4/052:40 PMPage 697GRAPHICAL SOLUTIONTO AL I N E A R P RO G R A M M I N G P RO B L E MX21001008080Number of Watch-TVsNumber of Watch-TVsX260(0, 42)40 210 7X1 5X 26020608040Number of Walkmans 350 7X1 5X 2 280 7X1 5X 240 210 7X1 5X 2(30, 0)20069720100X1 420 7X1 5X 20608040Number of Walkmans20100X1FIGURE B.4 A Profit Line of 210 Plotted for the ShaderFIGURE B.5 Four Iso-Profit Lines Plotted for the ShaderElectronics CompanyElectronics CompanyWhen X2 0, 280 7 X1 5(0)X1 40 WalkmansAgain, any combination of Walkmans (X1) and Watch-TVs (X2) on this iso-profit line will producea total profit of 280.Note that the third line generates a profit of 350, even more of an improvement. The farther wemove from the 0 origin, the higher our profit will be. Another important point to note is that theseiso-profit lines are parallel. We now have two clues as to how to find the optimal solution to the original problem. We can draw a series of parallel profit lines (by carefully moving our ruler in a planeparallel to the first profit line). The highest profit line that still touches some point of the feasibleregion will pinpoint the optimal solution. Notice that the fourth line ( 420) is too high to countbecause it does not touch the feasible region.The highest possible iso-profit line is illustrated in Figure B.6. It touches the tip of the feasibleregion at the corner point (X1 30, X2 40) and yields a profit of 410.FIGURE B.6 X2Optimal Solution for theShader Electronics Problem100Number of Watch-TVs80Maximum profit line60Optimal solution point( X1 30, X2 40)4020 410 7X1 5X 2020406080Number of Walkmans100X1
HEIZMX0B 013185755X.QXD6985/4/05MODULE B2:40 PMPage 698L I N E A R P RO G R A M M I N GCorner-Point Solution MethodA method for solvinggraphical linearprogramming problems.A second approach to solving linear programming problems employs the corner-point method.This technique is simpler in concept than the iso-profit line approach, but it involves looking at theprofit at every corner point of the feasible region.The mathematical theory behind linear programming states that an optimal solution to any problem (that is, the values of X1, X2 that yield the maximum profit) will lie at a corner point, or extremepoint, of the feasible region. Hence, it is necessary to find only the values of the variables at eachcorner; the maximum profit or optimal solution will lie at one (or more) of them.Once again we can see (in Figure B.7) that the feasible region for the Shader Electronics Companyproblem is a four-sided polygon with four corner, or extreme, points. These points are labeled , , and on the graph. To find the (X1, X2) values producing the maximum profit, we find out whatthe coordinates of each corner point are, then determine and compare their profit levels.Point :Point :Point :(X1 0, X2 0)(X1 0, X2 80)(X1 50, X2 0)Profit 7(0) 5(0) 0Profit 7(0) 5(80) 400Profit 7(50) 5(0) 350We skipped corner point momentarily because to find its coordinates accurately, we will have tosolve for the intersection of the two constraint lines. As you may recall from algebra, we can applythe method of simultaneous equations to the two constraint equations:4 X1 3 X2 240(electronics time)2 X1 1X2 100( assembly time)To solve these equations simultaneously, we multiply the second equation by 2: 2(2X1 1X2
4. The objective and constraints in linear programming problems must be expressed in terms of linear equations or inequalities. FORMULATING LINEAR PROGRAMMING PROBLEMS One of the most common linear programming applications is the product-mix problem. Two or more products are usually produced using limited resources.
Pearson Education LTD. Pearson Education Australia PTY, Limited. Pearson Education Singapore, Pte. Ltd. Pearson Education North Asia, Ltd. Pearson Education Canada, Ltd. Pearson Educatión de Mexico, S.A. de C.V. Pearson Education—Japan Pearson Education Malaysia, Pte. Ltd. Library of Co
Pearson Education LTD. Pearson Education Australia PTY, Limited. Pearson Education Singapore, Pte. Ltd. Pearson Education North Asia, Ltd. Pearson Education Canada, Ltd. Pearson Educación de Mexico, S.A. de C.V. Pearson Education—Japan Pearson Education Malaysia, Pte. Ltd. The Libra
Linear Programming CISC5835, Algorithms for Big Data CIS, Fordham Univ. Instructor: X. Zhang Linear Programming In a linear programming problem, there is a set of variables, and we want to assign real values to them so as to satisfy a set of linear equations
Pearson (UK) 80 Strand, London WC2R 0RL, UK T 44 (0)20 7010 2000 F 44 (0)20 7010 6060 firstname.lastname@pearson.com www.pearson.com Pearson (US) 1330 Avenue of the Americas, New York City, NY 10019, USA T 1 212 641 2400 F 1 212 641 2500 firstname.lastname@pearson-inc.com www.pearson.com Pearson Education One Lake Street, Upper Saddle River,
Pearson Education Canada, Inc. Pearson Education Malaysia, Pte. Ltd. Pearson Education-Japan Pearson Education Upper Saddle River, New Jersey Pearson Education Australia PTY, Limited PEARSON 10 9 8 7 6 5 4 ISBN-13: 17Ö-D-13-S0M507-7 ISBN-ID: G-13-5tmsa7-X . For Diane Perin Hock and Caroline Mei Perin Hock . CONTENTS PREFACE xi CHAPTER I BIOLOGY AND HUMAN BEHAVIOR 1 READING 1: ONE BRAIN OR TWO .
Brief History of Linear Programming 2 The goal of linear programming is to determine the values of decision variables that maximize or minimize a linear objective function, where the decision variables are subject to linear constraints. A linear programming problem is a special case of a general constra
SKF Linear Motion linear rail INA Linear SKF Linear Motion Star Linear Thomson Linear linear sysTems Bishop-Wisecarver INA Linear Pacific Bearing Thomson Linear mecHanical acTuaTors Duff-Norton Joyce/Dayton Nook Industries Precision mecHanical comPonenTs PIC Design Stock Drive Product
published by the American Petroleum Institute (API, 1984, 1991) are generally not consistent with the physical processes that dictate actual pile capacity. For example, the experimental observa- tion of a gradual reduction in the rate of increase of pile capacity with embedment depth is allowed for by imposing limiting values of end-bearing and shaft friction beyond some critical depth .
