xii Table of Contents
xii Table of Contents
PrefaceThis book shows how to use the power of optimization, sometimes known as mathematicalprogramming,to solve problems of business, industry,and government.The intended audience isstudents of business, managers, and engineers.Themajor technical skill required of the reader is to becomfortable with the idea of using a symbol to represent an unknown quantity.This book is oneof themost comprehensiveexpositionsavailable on howto applyoptimizationmodels to important business and industrial problems.If you do notfind your favoritebusinessapplication explicitly listed in thetable of contents,checkthe verycomprehensive index at theback ofthe book.There are essentially three kinds of chapters in the book:1.introduction tomodeling (chapters 1,3, 4, and 19),2.solving models with a computer (chapters 2, 5), and3.application specific illustration of modeling with LINGO (chapters 6-18)Readers completely new to optimization should read at least the first five chapters. Readersfamiliar with optimization, but unfamiliar withLINGO, should read at least chapters 2and5.Readersfamiliar with optimization and familiar with at least the concepts of a modeling language can probablyskipto chapters 6-18.One can pick and choosefrom these chapters on applications.There is no strongsequential ordering among chapters 6-18, other than that the easier topics are in the earlier chapters.Among these application chapters, chapters 11 (on integer programming), and 12 (on stochasticprogramming)areworthyof specialmention.Theycovertwocomputationallyintensivetechniquesoffairlygeneral applicability.As computers continuetogrowmorepowerful,integerprogramming andstochastic programming will become even more valuable. Chapter 19 is a concluding chapter onimplementing optimization models.It requires somefamiliarity with the details of models, asillustrated in the preceding chapters.There is a natural progression of skills needed as technology develops. For optimization, it hasbeen:Abilityto solvethemodels:1950's1)2)Ability toformulate optimization models: 1970's3)Abilitytouseturnkeyortemplatemodels:1990'sonward.This book has no material on the mathematics of solving optimization models.For users who arediscovering new applications, there is a substantial amount of material on the formulation ofoptimization models.For the modern two minute"manager,there is a big collection of“off-the-shelf',ready-to-apply template models throughout the book.Users familiar with the text Optimization Modeling with LINDO will notice much of the materialin this current book is based on material in the LINDO book.The major differences are dueto the twovery important capabilities of LINGO:the ability to solve nonlinear models, and the availability of theset or vector notation for compactly representing large models.AcknowledgmentsThis book has benefited from comments and corrections from Egon Balas, Robert Bosch, Angel G.Coca Balta, Sergio Chayet, Richard Darst, Daniel Davidson, Robert Dell, Hamilton Emmons, SaulGass, Tom Knowles, Milt Gutterman, Changpyo David Hong, Kipp Martin, Syam Menon, Raulxili
xiii Preface This book shows how to use the power of optimization, sometimes known as mathematical programming, to solve problems of business, industry, and government. The intended audience is students of business, managers, and engineers. The major technical skill required of the reader is to be comfortable with the idea of using a symbol to represent an unknown quantity. This book is one of the most comprehensive expositions available on how to apply optimization models to important business and industrial problems. If you do not find your favorite business application explicitly listed in the table of contents, check the very comprehensive index at the back of the book. There are essentially three kinds of chapters in the book: 1. introduction to modeling (chapters 1, 3, 4, and 19), 2. solving models with a computer (chapters 2, 5), and 3. application specific illustration of modeling with LINGO (chapters 6-18). Readers completely new to optimization should read at least the first five chapters. Readers familiar with optimization, but unfamiliar with LINGO, should read at least chapters 2 and 5. Readers familiar with optimization and familiar with at least the concepts of a modeling language can probably skip to chapters 6-18. One can pick and choose from these chapters on applications. There is no strong sequential ordering among chapters 6-18, other than that the easier topics are in the earlier chapters. Among these application chapters, chapters 11 (on integer programming), and 12 (on stochastic programming) are worthy of special mention. They cover two computationally intensive techniques of fairly general applicability. As computers continue to grow more powerful, integer programming and stochastic programming will become even more valuable. Chapter 19 is a concluding chapter on implementing optimization models. It requires some familiarity with the details of models, as illustrated in the preceding chapters. There is a natural progression of skills needed as technology develops. For optimization, it has been: 1) Ability to solve the models: 1950’s 2) Ability to formulate optimization models: 1970’s 3) Ability to use turnkey or template models: 1990’s onward. This book has no material on the mathematics of solving optimization models. For users who are discovering new applications, there is a substantial amount of material on the formulation of optimization models. For the modern “two minute” manager, there is a big collection of “off-the-shelf”, ready-to-apply template models throughout the book. Users familiar with the text Optimization Modeling with LINDO will notice much of the material in this current book is based on material in the LINDO book. The major differences are due to the two very important capabilities of LINGO: the ability to solve nonlinear models, and the availability of the set or vector notation for compactly representing large models. Acknowledgments This book has benefited from comments and corrections from Egon Balas, Robert Bosch, Angel G. Coca Balta, Sergio Chayet, Richard Darst, Daniel Davidson, Robert Dell, Hamilton Emmons, Saul Gass, Tom Knowles, Milt Gutterman, Changpyo David Hong, Kipp Martin, Syam Menon, Raul
xivPrefaceNegro, David Phillips, J. Pye, Fritz Raffensperger, Rick Rosenthal, James Schmidt, Paul Schweitzer,Shuichi Shinmura, Rob Stubbs, David Tulett, Richard Wendell, Mark Wiley, and Gene Woolsey andhis students.The outstanding software expertise and sage advice of Kevin Cunningham was crucial.Theproduction of this book (from editing and formatting to printing)was ably managed by SarahSnider,HanzadeIzmit, SrinnathTumuandJaneRees
xiv Preface Negro, David Phillips, J. Pye, Fritz Raffensperger, Rick Rosenthal, James Schmidt, Paul Schweitzer, Shuichi Shinmura, Rob Stubbs, David Tulett, Richard Wendell, Mark Wiley, and Gene Woolsey and his students. The outstanding software expertise and sage advice of Kevin Cunningham was crucial. The production of this book (from editing and formatting to printing) was ably managed by Sarah Snider, Hanzade Izmit, Srinnath Tumu and Jane Rees
1What Is Optimization?1.1IntroductionOptimization, or constrained optimization, or mathematical programming, is a mathematical procedurefor determining optimal allocation of scarce resources.Optimization, and its most popular specialform,LinearProgramming(LP),hasfoundpracticalapplicationinalmostallfacetsofbusiness,fromadvertisingtoproductionplanning.Transportationandaggregateproductionplanningproblems arethemosttypical objectsofLPanalysis.Thepetroleum industrywasan earlyintensiveuserofLPforsolvingfuelblendingproblemsIt is important for the reader to appreciate at the outset that the “programming" in MathematicalProgramming is of a different flavor than the“programming"in Computer Programming. In theformer case, itmeans to plan and organize (as in"Get with the program!").In thelatter case, it meanstowriteinstructions forperformingcalculations.Althoughaptitudein one suggests aptitude intheother, training in the one kind of programming has very lttle direct relevance to the other.For most optimization problems,one can think of therebeing two important classes of objects.The first of these is limited resources, such as land,plant capacity,and sales force size.The second isactivities, such as“produce low carbon steel,""produce stainless steel,"and“produce high carbonsteel."Each activity consumes or possibly contributes additional amounts of the resources.Theproblem is to determine the best combination of activity levels that does not use more resources thanareactuallyavailable.Wecanbest gaintheflavorof LPby using a simpleexample1.2ASimpleProduct MixProblemThe Enginola Television Company produces two types of TV sets, the"Astro"and the"Cosmo"Therearetwoproductionlines,oneforeachset.TheAstroproduction linehasacapacityof 60setsper day, whereas the capacity for the Cosmo production line is only 50 sets per day.The laborrequirements for the Astro set is 1 person-hour, whereas the Cosmo requires a full 2 person-hours oflabor.Presently,there is a maximum of 120 man-hours of labor per day that can be assigned toproduction of thetwo types of sets.If theprofit contributions are S20 and $30foreachAstro andCosmo set,respectively,what shouldbethedailyproduction?1
1 1 What Is Optimization? 1.1 Introduction Optimization, or constrained optimization, or mathematical programming, is a mathematical procedure for determining optimal allocation of scarce resources. Optimization, and its most popular special form, Linear Programming (LP), has found practical application in almost all facets of business, from advertising to production planning. Transportation and aggregate production planning problems are the most typical objects of LP analysis. The petroleum industry was an early intensive user of LP for solving fuel blending problems. It is important for the reader to appreciate at the outset that the “programming” in Mathematical Programming is of a different flavor than the “programming” in Computer Programming. In the former case, it means to plan and organize (as in “Get with the program!”). In the latter case, it means to write instructions for performing calculations. Although aptitude in one suggests aptitude in the other, training in the one kind of programming has very little direct relevance to the other. For most optimization problems, one can think of there being two important classes of objects. The first of these is limited resources, such as land, plant capacity, and sales force size. The second is activities, such as “produce low carbon steel,” “produce stainless steel,” and “produce high carbon steel.” Each activity consumes or possibly contributes additional amounts of the resources. The problem is to determine the best combination of activity levels that does not use more resources than are actually available. We can best gain the flavor of LP by using a simple example. 1.2 A Simple Product Mix Problem The Enginola Television Company produces two types of TV sets, the “Astro” and the “Cosmo”. There are two production lines, one for each set. The Astro production line has a capacity of 60 sets per day, whereas the capacity for the Cosmo production line is only 50 sets per day. The labor requirements for the Astro set is 1 person-hour, whereas the Cosmo requires a full 2 person-hours of labor. Presently, there is a maximum of 120 man-hours of labor per day that can be assigned to production of the two types of sets. If the profit contributions are $20 and $30 for each Astro and Cosmo set, respectively, what should be the daily production?
2Chapter1WhatisOptimization?A structured, but verbal, description ofwhat we want to do is:MaximizeProfitcontributionAstro production less-than-or-equal-to Astro capacity,subjecttoCosmoproductionless-than-or-equal-toCosmocapacity,Laborused less-than-or-equal-tolaboravailabilityUntil there is a significant improvement in artificial intelligenceexpert system software,wewillneed to be more precise if we wish to get some help in solving our problem.We can be more precise ifwe define:A = units of Astros to be produced per day,C= units of Cosmos to be produced per day.Further, we decide to measure:Profit contribution in dollarsAstro usage in units of Astros produced,Cosmo usage in units of Cosmos produced, andLabor in person-hours.Then, a precise statement of our problem is:Maximize20A +30C(Dollars)subject toA≤60(Astro capacity)C≤50(Cosmo capacity)A+2C≤120(Labor in person-hours)Thefirst line,"Maximize 20A+30C,is known as the objectivefunction.Theremaining three linesare known as constraints. Most optimization programs, sometimes called "solvers", assume allvariables are constrained tobe nonnegative, so stating the constraints A ≥0 and C≥0 is unnecessaryUsing the terminology of resources and activities, there are three resources: Astro capacity,Cosmo capacity,and labor capacity.The activities are Astro and Cosmo production.It is generally truethat,with each constraint in an optimization model, onecan associate someresource.For each decisionvariable,thereisfrequentlyacorrespondingphysical activity1.2.1GraphicalAnalysisThe Enginola problem is represented graphically in Figure 1.1. The feasible production combinationsare the points in the lowerleft enclosed by thefive solid lines.We want tofind the point in the feasibleregion that gives the highest profit.To gain some idea of where the maximum profit point lies, let's consider some possibilities. Thepoint A = C= O is feasible, but it does not help us out much with respect to profits. If we spoke withthemanager of the Cosmo line,the response mightbe:"The Cosmo is our moreprofitableproduct.Therefore, we should make as many of it as possible, namely 50, and be satisfied with the profitcontributionof30×50=$1500
2 Chapter 1 What is Optimization? A structured, but verbal, description of what we want to do is: Maximize Profit contribution subject to Astro production less-than-or-equal-to Astro capacity, Cosmo production less-than-or-equal-to Cosmo capacity, Labor used less-than-or-equal-to labor availability. Until there is a significant improvement in artificial intelligence/expert system software, we will need to be more precise if we wish to get some help in solving our problem. We can be more precise if we define: A = units of Astros to be produced per day, C = units of Cosmos to be produced per day. Further, we decide to measure: Profit contribution in dollars, Astro usage in units of Astros produced, Cosmo usage in units of Cosmos produced, and Labor in person-hours. Then, a precise statement of our problem is: Maximize 20A + 30C (Dollars) subject to A d 60 (Astro capacity) C d 50 (Cosmo capacity) A + 2C d 120 (Labor in person-hours) The first line, “Maximize 20A+30C”, is known as the objective function. The remaining three lines are known as constraints. Most optimization programs, sometimes called “solvers”, assume all variables are constrained to be nonnegative, so stating the constraints A t 0 and C t 0 is unnecessary. Using the terminology of resources and activities, there are three resources: Astro capacity, Cosmo capacity, and labor capacity. The activities are Astro and Cosmo production. It is generally true that, with each constraint in an optimization model, one can associate some resource. For each decision variable, there is frequently a corresponding physical activity. 1.2.1 Graphical Analysis The Enginola problem is represented graphically in Figure 1.1. The feasible production combinations are the points in the lower left enclosed by the five solid lines. We want to find the point in the feasible region that gives the highest profit. To gain some idea of where the maximum profit point lies, let’s consider some possibilities. The point A = C = 0 is feasible, but it does not help us out much with respect to profits. If we spoke with the manager of the Cosmo line, the response might be: “The Cosmo is our more profitable product. Therefore, we should make as many of it as possible, namely 50, and be satisfied with the profit contribution of 30 u 50 = $1500