OptimizationModeling withLINGOSixthEditionLINDO Systems, Inc1415NorthDayton Street,Chicago, Ilinois 60622Phone:(312)988-7422Fax:(312)988-9065E-mail:info@lindo.com
Preliminary Edition Optimization Modeling with LINGO Sixth Edition LINDO Systems, Inc. 1415 North Dayton Street, Chicago, Illinois 60622 Phone: (312)988-7422 Fax: (312)988-9065 E-mail: info@lindo.com
ContentsPrefacexiliAcknowledgments...xili1WhatIsOptimization?.1.1 Introduction..1.2ASimpleProductMixProblem.1.2.1GraphicalAnalysis1.3 Linearity...1.4AnalysisofLPSolutions.681.5SensitivityAnalysis,ReducedCosts,andDualPrices1.5.1ReducedCosts91.5.2DualPrices...8O1.6UnboundedFormulations101.7InfeasibleFormulations...111.8Multiple Optimal Solutions and Degeneracy.131.8.1The"Snake Eyes"Condition....161.8.2DegeneracyandRedundantConstraints...1.9NonlinearModelsandGlobal Optimization.171.10Problems..18232SolvingMathProgramswithLINGO232.1 Introduction...232.2LINGOforWindowS.232.2.1 File Menu ...252.2.2EditMenu.272.2.3LINGOMenu.282.2.4WindowsMenu292.2.5 Help Menu....292.2.6Summary....292.3GettingStartedonaSmallProblem.302.4IntegerProgrammingwithLINGO322.4.1 Warning for Integer Programs..322.5Solving an Optimization Model..332.6Problems....353Analyzing Solutions...353.1EconomicAnalysisofSolutionReports...353.2EconomicRelationshipBetweenDualPricesandReducedCosts.363.2.1TheCostingOut Operation:An Illustration.....3.2.2Dual Prices, LaGrangeMultipliers, KKT Conditions, and Activity Costing ...37..383.3RangeofValidityofReducedCostsandDualPrices...3.3.1PredictingtheEffectofSimultaneousChangesinParameters-The100%Rule.433.4SensitivityAnalysisof theConstraintCoefficients...44ili
iii Contents Preface .xiii Acknowledgments.xiii 1 What Is Optimization? .1 1.1 Introduction.1 1.2 A Simple Product Mix Problem.1 1.2.1 Graphical Analysis .2 1.3 Linearity .5 1.4 Analysis of LP Solutions.6 1.5 Sensitivity Analysis, Reduced Costs, and Dual Prices.8 1.5.1 Reduced Costs .8 1.5.2 Dual Prices.8 1.6 Unbounded Formulations .9 1.7 Infeasible Formulations .10 1.8 Multiple Optimal Solutions and Degeneracy .11 1.8.1 The “Snake Eyes” Condition.13 1.8.2 Degeneracy and Redundant Constraints.16 1.9 Nonlinear Models and Global Optimization.17 1.10 Problems.18 2 Solving Math Programs with LINGO .23 2.1 Introduction.23 2.2 LINGO for Windows.23 2.2.1 File Menu .23 2.2.2 Edit Menu.25 2.2.3 LINGO Menu.27 2.2.4 Windows Menu .28 2.2.5 Help Menu.29 2.2.6 Summary.29 2.3 Getting Started on a Small Problem.29 2.4 Integer Programming with LINGO .30 2.4.1 Warning for Integer Programs.32 2.5 Solving an Optimization Model.32 2.6 Problems.33 3 Analyzing Solutions.35 3.1 Economic Analysis of Solution Reports.35 3.2 Economic Relationship Between Dual Prices and Reduced Costs.35 3.2.1 The Costing Out Operation: An Illustration.36 3.2.2 Dual Prices, LaGrange Multipliers, KKT Conditions, and Activity Costing .37 3.3 Range of Validity of Reduced Costs and Dual Prices .38 3.3.1 Predicting the Effect of Simultaneous Changes in Parameters—The 100% Rule .43 3.4 Sensitivity Analysis of the Constraint Coefficients.44
iyTableofContents3.5TheDual LPProblem,ortheLandlordand theRenter.45.473.6 Problem.....534TheModelFormulationProcess534.1TheOverallProcess544.2Approaches to Model Formulation..544.3TheTemplateApproach.544.3.1ProductMixProblems.544.3.2Covering,Staffing,andCuttingStockProblems544.3.3BlendingProblems...554.3.4MultiperiodPlanningProblems..554.3.5Network,Distribution,andPERT/CPMModels554.3.6MultiperiodPlanningProblemswithRandomElements554.3.7Financial PortfolioModels.....564.3.8GameTheoryModels.564.4ConstructiveApproachtoModelFormulation574.4.1 Example...574.4.2FormulatingOurExampleProblem584.5ChoosingCostsCorrectly...584.5.1Sunkvs.VariableCosts604.5.2Joint Products...614.5.3BookValuevs.MarketValue..634.6CommonErrorsinFormulatingModels..654.7TheNonsimultaneityError..664.8Problems......695TheSetsViewoftheWorld695.1 Introduction...695.1.1WhyUseSets?695.1.2WhatAreSets?....705.1.3Types ofSets..705.2TheSETSSectionofaModel705.2.1DefiningPrimitiveSets-5.2.2DefiningDerivedSets71725.2.3Summary...5.3TheDATASection73755.4SetLoopingFunctions....765.4.1@SUMSetLoopingFunction5.4.2@MINand@MAXSetLoopingFunctions775.4.3@FORSetLoopingFunction...785.4.4NestedSetLoopingFunctions..79795.5SetBasedModelingExamples..805.5.1PrimitiveSetExample....835.5.2DenseDerivedSetExample...855.5.3SparseDerivedSetExample-ExplicitList.905.5.4ASparseDerivedSetUsingaMembershipFilter5.6Domain Functions for Variables.94
iv Table of Contents 3.5 The Dual LP Problem, or the Landlord and the Renter.45 3.6 Problems.47 4 The Model Formulation Process.53 4.1 The Overall Process .53 4.2 Approaches to Model Formulation.54 4.3 The Template Approach.54 4.3.1 Product Mix Problems.54 4.3.2 Covering, Staffing, and Cutting Stock Problems.54 4.3.3 Blending Problems.54 4.3.4 Multiperiod Planning Problems .55 4.3.5 Network, Distribution, and PERT/CPM Models .55 4.3.6 Multiperiod Planning Problems with Random Elements.55 4.3.7 Financial Portfolio Models.55 4.3.8 Game Theory Models .56 4.4 Constructive Approach to Model Formulation .56 4.4.1 Example .57 4.4.2 Formulating Our Example Problem .57 4.5 Choosing Costs Correctly.58 4.5.1 Sunk vs. Variable Costs.58 4.5.2 Joint Products .60 4.5.3 Book Value vs. Market Value.61 4.6 Common Errors in Formulating Models.63 4.7 The Nonsimultaneity Error.65 4.8 Problems.66 5 The Sets View of the World .69 5.1 Introduction.69 5.1.1 Why Use Sets? .69 5.1.2 What Are Sets?.69 5.1.3 Types of Sets .70 5.2 The SETS Section of a Model .70 5.2.1 Defining Primitive Sets.70 5.2.2 Defining Derived Sets .71 5.2.3 Summary.72 5.3 The DATA Section.73 5.4 Set Looping Functions.75 5.4.1 @SUM Set Looping Function .76 5.4.2 @MIN and @MAX Set Looping Functions .77 5.4.3 @FOR Set Looping Function.78 5.4.4 Nested Set Looping Functions.79 5.5 Set Based Modeling Examples.79 5.5.1 Primitive Set Example.80 5.5.2 Dense Derived Set Example.83 5.5.3 Sparse Derived Set Example - Explicit List .85 5.5.4 A Sparse Derived Set Using a Membership Filter .90 5.6 Domain Functions for Variables .94
Tableof ContentsJ.945.7SpreadsheetsandLINGO.985.8Summary..985.9Problems..996ProductMixProblems.996.1Introduction...1006.2Example..6.3ProcessSelectionProductMixProblems103.1086.4Problems..7 Covering,Staffing&Cutting Stock Models....1111117.1Introduction....1127.1.1Staffing Problems.1127.1.2Example:NortheastTollwayStaffingProblems.7.1.3Additional Staff SchedulingFeatures.....1147.2 Cutting Stock and Pattern Selection.115.1167.2.1Example:CooldotCuttingStockProblem.7.2.2Formulation and Solution of Cooldot117..1217.2.3GeneralizationsoftheCuttingStockProblem.1237.2.4Two-DimensionalCuttingStockProblems.1237.3CrewSchedulingProblems....1247.3.1Example:Sayre-PriorsCrewScheduling...1267.3.2Solving theSayre/Priors CrewSchedulingProblem.1287.3.3AdditionalPracticalDetails1297.4AGenericCovering/Partitioning/PackingModel7.5Problems...1318Networks,DistributionandPERT/CPM.....1411418.1What'sSpecialAboutNetworkModels.1448.1.1SpecialCases....1448.2PERT/CPMNetworksandLP8.3Activity-on-Arc vs.Activity-on-Node Network Diagrams..1491508.4CrashingofProjectNetworks...8.4.1TheCostandValueofCrashing1511518.4.2TheCostofCrashinganActivity-1518.4.3TheValueofCrashingaProject.1528.4.4FormulationoftheCrashingProblem.8.5ResourceConstraints inProject Scheduling1551578.6PathFormulations....1588.6.1Example.1598.7PathFormulationsofUndirectedNetworks..1608.7.1Example..8.8DoubleEntryBookkeeping:ANetworkModeloftheFirm..162.1638.9ExtensionsofNetworkLPModels....8.9.1MulticommodityNetworkFlows.1641658.9.2ReducingtheSizeofMulticommodityProblems1658.9.3MulticommodityFlowExample
Table of Contents v 5.7 Spreadsheets and LINGO .94 5.8 Summary .98 5.9 Problems.98 6 Product Mix Problems .99 6.1 Introduction.99 6.2 Example.100 6.3 Process Selection Product Mix Problems .103 6.4 Problems.108 7 Covering, Staffing & Cutting Stock Models.111 7.1 Introduction.111 7.1.1 Staffing Problems.112 7.1.2 Example: Northeast Tollway Staffing Problems.112 7.1.3 Additional Staff Scheduling Features.114 7.2 Cutting Stock and Pattern Selection.115 7.2.1 Example: Cooldot Cutting Stock Problem.116 7.2.2 Formulation and Solution of Cooldot .117 7.2.3 Generalizations of the Cutting Stock Problem.121 7.2.4 Two-Dimensional Cutting Stock Problems .123 7.3 Crew Scheduling Problems .123 7.3.1 Example: Sayre-Priors Crew Scheduling.124 7.3.2 Solving the Sayre/Priors Crew Scheduling Problem .126 7.3.3 Additional Practical Details .128 7.4 A Generic Covering/Partitioning/Packing Model .129 7.5 Problems.131 8 Networks, Distribution and PERT/CPM.141 8.1 What’s Special About Network Models .141 8.1.1 Special Cases .144 8.2 PERT/CPM Networks and LP.144 8.3 Activity-on-Arc vs. Activity-on-Node Network Diagrams.149 8.4 Crashing of Project Networks.150 8.4.1 The Cost and Value of Crashing.151 8.4.2 The Cost of Crashing an Activity .151 8.4.3 The Value of Crashing a Project.151 8.4.4 Formulation of the Crashing Problem .152 8.5 Resource Constraints in Project Scheduling.155 8.6 Path Formulations .157 8.6.1 Example .158 8.7 Path Formulations of Undirected Networks.159 8.7.1 Example .160 8.8 Double Entry Bookkeeping: A Network Model of the Firm.162 8.9 Extensions of Network LP Models.163 8.9.1 Multicommodity Network Flows .164 8.9.2 Reducing the Size of Multicommodity Problems .165 8.9.3 Multicommodity Flow Example .165
viTableofContents8.9.4 Fleet Routing and Assignment...1681718.9.5FleetAssignment...1768.9.6LeontiefFlowModels.1788.9.7Activity/ResourceDiagrams.....1808.9.8SpanningTrees.8.9.9SteinerTrees.1828.10NonlinearNetworks.1868.11Problems..1889Multi-period PlanningProblems..197.1979.1Introduction...1999.2ADynamicProductionProblem..1999.2.1 Formulation..9.2.2Constraints...200.2029.2.3RepresentingAbsoluteValues.9.3Multi-periodFinancialModels203.2039.3.1Example:CashFlowMatching9.4FinancialPlanningModels withTaxConsiderations.207.2089.4.1FormulationandSolutionoftheWSDMProblem9.4.2 Interpretation of the Dual Prices.2092109.5PresentValuevs.LPAnalysis....2119.6AccountingforIncomeTaxes2149.7DynamicorMulti-periodNetworks..2169.8EndEffects.2179.8.1Perishability/ShelfLifeConstraints.9.8.2StartupandShutdownCosts...217.2179.9Non-optimalityof CyclicSolutionstoCyclicProblems...2239.10Problems......22710BlendingofInputMaterials22710.1Introduction...22810.2TheStructureofBlendingProblems22910.2.1Example:ThePittsburghSteelCompanyBlendingProblem.....23010.2.2FormulationandSolutionofthePittsburghSteelBlendingProblem.23210.3ABlendingProblemwithinaProductMixProblem.....23310.3.1Formulation....23410.3.2RepresentingTwo-sidedConstraints10.4ProperChoiceofAlternateInterpretationsofQualityRequirements.23723910.5HowtoComputeBlendedQuality.24010.5.1Example.10.5.2GeneralizedMean.240.24210.6Interpretationof DualPrices for Blending Constraints10.7FractionalorHyperbolicProgramming.....242.24310.8Multi-LevelBlending:PoolingProblems10.9Problems.....248
vi Table of Contents 8.9.4 Fleet Routing and Assignment.168 8.9.5 Fleet Assignment .171 8.9.6 Leontief Flow Models.176 8.9.7 Activity/Resource Diagrams.178 8.9.8 Spanning Trees.180 8.9.9 Steiner Trees.182 8.10 Nonlinear Networks .186 8.11 Problems.188 9 Multi-period Planning Problems.197 9.1 Introduction.197 9.2 A Dynamic Production Problem.199 9.2.1 Formulation .199 9.2.2 Constraints.200 9.2.3 Representing Absolute Values.202 9.3 Multi-period Financial Models.203 9.3.1 Example: Cash Flow Matching .203 9.4 Financial Planning Models with Tax Considerations.207 9.4.1 Formulation and Solution of the WSDM Problem.208 9.4.2 Interpretation of the Dual Prices .209 9.5 Present Value vs. LP Analysis.210 9.6 Accounting for Income Taxes.211 9.7 Dynamic or Multi-period Networks.214 9.8 End Effects .216 9.8.1 Perishability/Shelf Life Constraints .217 9.8.2 Startup and Shutdown Costs .217 9.9 Non-optimality of Cyclic Solutions to Cyclic Problems .217 9.10 Problems.223 10 Blending of Input Materials.227 10.1 Introduction.227 10.2 The Structure of Blending Problems .228 10.2.1 Example: The Pittsburgh Steel Company Blending Problem .229 10.2.2 Formulation and Solution of the Pittsburgh Steel Blending Problem.230 10.3 A Blending Problem within a Product Mix Problem.232 10.3.1 Formulation .233 10.3.2 Representing Two-sided Constraints.234 10.4 Proper Choice of Alternate Interpretations of Quality Requirements .237 10.5 How to Compute Blended Quality .239 10.5.1 Example .240 10.5.2 Generalized Mean.240 10.6 Interpretation of Dual Prices for Blending Constraints .242 10.7 Fractional or Hyperbolic Programming.242 10.8 Multi-Level Blending: Pooling Problems.243 10.9 Problems.248