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
TableofContentsvii.26111Formulatingand Solving Integer Programs..26111.1Introduction....11.1.1TypesofVariables..261.26211.2ExploitingtheIPCapability:StandardApplications.26211.2.1BinaryRepresentationof General IntegerVariables.26211.2.2MinimumBatchSizeConstraints...26311.2.3FixedChargeProblems.26311.2.4TheSimplePlantLocationProblem.26511.2.5TheCapacitatedPlantLocationProblem(CPL)11.2.6ModelingAlternativeswiththeScenarioApproach.267..26811.2.7LinearizingaPiecewiseLinearFunction11.2.8ConvertingtoSeparableFunctions.27111.3OutlineofIntegerProgrammingMethods..272.27411.4ComputationalDifficultyofIntegerPrograms....27511.4.1NP-CompleteProblems...11.5ProblemswithNaturallyIntegerSolutionsandthePrayerAlgorithm.275.27611.5.1NetworkLPsRevisited....27611.5.2Integral Leontief Constraints.27711.5.3Example:AOne-PeriodMRPProblem....27911.5.4TransformationstoNaturallyIntegerFormulations28111.6TheAssignmentProblemandRelatedSequencingandRoutingProblems.28111.6.1Example:TheAssignmentProblem...28311.6.2TheTravelingSalespersonProblem.28911.6.3CapacitatedMultipleTSPNehicleRoutingProblems..29311.6.4MinimumSpanningTree...29311.6.5TheLinearOrderingProblem..29611.6.6QuadraticAssignmentProblem....29911.7 Problems of Grouping,Matching,Covering,Partitioning,and Packing.30011.7.1FormulationasanAssignmentProblem.....30111.7.2Matching Problems, Groups of Size Two ....30311.7.3GroupswithMoreThanTwoMembers..30711.7.4GroupswithaVariableNumberofMembers,AssignmentVersion..30811.7.5GroupswithAVariableNumberofMembers,PackingVersion.31111.7.6GroupswithAVariableNumberofMembers,CuttingStockProblem..31511.7.7GroupswithAVariableNumberof Members,VehicleRouting.11.8LinearizingProductsof Variables..320.32011.8.1Example:BundlingofProducts...32311.9RepresentingLogicalConditions..32411.10Problems....33512Decision making UnderUncertainty and Stochastic Programs...33512.1Introduction...33512.2 Identifying Sources of Uncertainty..33612.3TheScenarioApproach......33812.4AMore Complicated Two-Period Planning Problem...34012.4.1TheWarm WinterSolution...12.4.2TheColdWinterSolution.340
Table of Contents vii 11 Formulating and Solving Integer Programs.261 11.1 Introduction.261 11.1.1 Types of Variables .261 11.2 Exploiting the IP Capability: Standard Applications.262 11.2.1 Binary Representation of General Integer Variables .262 11.2.2 Minimum Batch Size Constraints.262 11.2.3 Fixed Charge Problems .263 11.2.4 The Simple Plant Location Problem .263 11.2.5 The Capacitated Plant Location Problem (CPL).265 11.2.6 Modeling Alternatives with the Scenario Approach .267 11.2.7 Linearizing a Piecewise Linear Function .268 11.2.8 Converting to Separable Functions .271 11.3 Outline of Integer Programming Methods .272 11.4 Computational Difficulty of Integer Programs.274 11.4.1 NP-Complete Problems .275 11.5 Problems with Naturally Integer Solutions and the Prayer Algorithm.275 11.5.1 Network LPs Revisited.276 11.5.2 Integral Leontief Constraints.276 11.5.3 Example: A One-Period MRP Problem.277 11.5.4 Transformations to Naturally Integer Formulations .279 11.6 The Assignment Problem and Related Sequencing and Routing Problems.281 11.6.1 Example: The Assignment Problem .281 11.6.2 The Traveling Salesperson Problem .283 11.6.3 Capacitated Multiple TSP/Vehicle Routing Problems.289 11.6.4 Minimum Spanning Tree.293 11.6.5 The Linear Ordering Problem .293 11.6.6 Quadratic Assignment Problem .296 11.7 Problems of Grouping, Matching, Covering, Partitioning, and Packing .299 11.7.1 Formulation as an Assignment Problem.300 11.7.2 Matching Problems, Groups of Size Two .301 11.7.3 Groups with More Than Two Members .303 11.7.4 Groups with a Variable Number of Members, Assignment Version .307 11.7.5 Groups with A Variable Number of Members, Packing Version.308 11.7.6 Groups with A Variable Number of Members, Cutting Stock Problem .311 11.7.7 Groups with A Variable Number of Members, Vehicle Routing.315 11.8 Linearizing Products of Variables.320 11.8.1 Example: Bundling of Products.320 11.9 Representing Logical Conditions.323 11.10 Problems.324 12 Decision making Under Uncertainty and Stochastic Programs.335 12.1 Introduction.335 12.2 Identifying Sources of Uncertainty.335 12.3 The Scenario Approach.336 12.4 A More Complicated Two-Period Planning Problem.338 12.4.1 The Warm Winter Solution.340 12.4.2 The Cold Winter Solution.340
vili Table of Contents12.4.3TheUnconditionalSolution...341.34412.5ExpectedValueofPerfectInformation(EVPI).34512.6ExpectedValueofModelingUncertainty.34512.6.1CertaintyEquivalence....12.7RiskAversion...34612.7.1DownsideRisk.34712.7.2Example....348.35012.8ChoosingScenarios..35112.8.1MatchingScenarioStatisticstoTargets...35212.8.2GeneratingScenarioswithaSpecifiedCovarianceStructure.35312.8.3 Generating a Suitable Z Matrix ....12.8.4Example.....35435512.8.5ConvertingMulti-StageProblemstoTwo-StageProblems12.9 Decisions Under Uncertainty with More thanTwo Periods355..35612.9.1DynamicProgrammingandFinancialOptionModels...35712.9.2BinomialTreeModelsof InterestRates..36112.9.3BinomialTreeModelsofForeignExchangeRates..12.10DecisionsUnderUncertaintywithanInfiniteNumberofPeriods363..36512.10.1Example:CashBalanceManagement....12.11Chance-ConstrainedPrograms..368..36912..12Problems........37113PortfolioOptimization....37113.1Introduction...37113.2TheMarkowitzMean/VariancePortfolioModel.13.2.1Example....37237513.3DualingObjectives:EfficientFrontierandParametricAnalysis37513.3.1PortfolioswithaRisk-FreeAsset...37813.3.2TheSharpeRatio......37913.4Important Variationsof thePortfolioModel...38013.4.1PortfolioswithTransactionCosts.38013.4.2Example...38213.4.3PortfolioswithTaxes....38413.4.4FactorsModelforSimplifyingtheCovarianceStructure.38513.4.5Exampleof theFactorModel....13.4.6ScenarioModel forRepresenting Uncertainty.386.38713.4.7Example:ScenarioModelforRepresentingUncertainty13.5Measures of Risk other than Variance ....389.39013.5.1MaximizingtheMinimumReturn.39113.5.2ValueatRisk..39213.5.3ExampleofVAR.39313.6ScenarioModelandMinimizingDownsideRisk...39413.6.1Semi-varianceandDownsideRisk..39613.6.2DownsideRiskandMAD.13.6.3ScenariosBasedDirectlyUponaCovarianceMatrix.396..39813.7Hedging,MatchingandProgramTrading.39813.7.1PortfolioHedging
viii Table of Contents 12.4.3 The Unconditional Solution.341 12.5 Expected Value of Perfect Information (EVPI) .344 12.6 Expected Value of Modeling Uncertainty .345 12.6.1 Certainty Equivalence.345 12.7 Risk Aversion.346 12.7.1 Downside Risk .347 12.7.2 Example .348 12.8 Choosing Scenarios .350 12.8.1 Matching Scenario Statistics to Targets .351 12.8.2 Generating Scenarios with a Specified Covariance Structure.352 12.8.3 Generating a Suitable Z Matrix .353 12.8.4 Example .354 12.8.5 Converting Multi-Stage Problems to Two-Stage Problems .355 12.9 Decisions Under Uncertainty with More than Two Periods .355 12.9.1 Dynamic Programming and Financial Option Models .356 12.9.2 Binomial Tree Models of Interest Rates.357 12.9.3 Binomial Tree Models of Foreign Exchange Rates .361 12.10 Decisions Under Uncertainty with an Infinite Number of Periods.363 12.10.1 Example: Cash Balance Management .365 12.11 Chance-Constrained Programs.368 12.12 Problems.369 13 Portfolio Optimization.371 13.1 Introduction.371 13.2 The Markowitz Mean/Variance Portfolio Model.371 13.2.1 Example .372 13.3 Dualing Objectives: Efficient Frontier and Parametric Analysis .375 13.3.1 Portfolios with a Risk-Free Asset.375 13.3.2 The Sharpe Ratio.378 13.4 Important Variations of the Portfolio Model .379 13.4.1 Portfolios with Transaction Costs .380 13.4.2 Example .380 13.4.3 Portfolios with Taxes.382 13.4.4 Factors Model for Simplifying the Covariance Structure .384 13.4.5 Example of the Factor Model.385 13.4.6 Scenario Model for Representing Uncertainty.386 13.4.7 Example: Scenario Model for Representing Uncertainty.387 13.5 Measures of Risk other than Variance .389 13.5.1 Maximizing the Minimum Return .390 13.5.2 Value at Risk.391 13.5.3 Example of VAR.392 13.6 Scenario Model and Minimizing Downside Risk.393 13.6.1 Semi-variance and Downside Risk .394 13.6.2 Downside Risk and MAD .396 13.6.3 Scenarios Based Directly Upon a Covariance Matrix.396 13.7 Hedging, Matching and Program Trading .398 13.7.1 Portfolio Hedging .398
Tableof Contentsix.39813.7.2 Portfolio Matching, Tracking, and Program Trading ...39913.8MethodsforConstructingBenchmarkPortfolios.....40213.8.1ScenarioApproachtoBenchmarkPortfolios.13.8.2EfficientBenchmarkPortfolios...40413.8.3EfficientFormulationofPortfolioProblems40513.9CholeskyFactorizationforQuadraticPrograms..407..40913.10Problems.....41114MultipleCriteriaandGoal Programming..41114.1Introduction...41214.1.1AlternateOptima andMulticriteria.14.2ApproachestoMulti-criteriaProblems.412.41214.2.1ParetoOptimalSolutionsandMultipleCriteria..14.2.2UtilityFunctionApproach....412.41314.2.3Trade-offCurves.14.2.4Example:AdLibMarketing.41314.3Goal Programming and Soft Constraints....416.41714.3.1Example:SecondaryCriteriontoChooseAmongAlternateOptima..41914.3.2Preemptive/LexicoGoalProgramming.....14.4Minimizing theMaximumHurt,orUnordered LexicoMinimization422.42314.4.1Example....14.4.2 Finding a Unique Solution Minimizing the Maximum.42342814.5IdentifyingPointsontheEfficientFrontier...42814.5.1EfficientPoints,More-is-BetterCase...43014.5.2EfficientPoints,Less-is-BetterCase...43214.5.3EfficientPoints,theMixedCase.....43314.6ComparingPerformancewithData EnvelopmentAnalysis....43814.7Problems......44115Economic Equilibriaand Pricing.....44115.1WhatisanEquilibrium?..44215.2ASimpleSimultaneousPrice/ProductionDecision..44315.3RepresentingSupply&DemandCurvesinLPs...44715.4AuctionsasEconomicEguilibria...45115.5Multi-ProductPricingProblems.......45515.6GeneralEquilibriumModelsofAnEconomy...45715.7Transportation Equilibria........46115.7.1UserEquilibriumvs.SocialOptimum.46315.8EquilibriainNetworksasOptimizationProblems15.8.1EguilibriumNetworkFlows..46515.9Problems..46716GameTheoryandCostAllocation.471.47116.1Introduction.16.2Two-PersonGames.471..47216.2.1TheMinimaxStrategy16.3Two-PersonNon-ConstantSumGames.474
Table of Contents ix 13.7.2 Portfolio Matching, Tracking, and Program Trading .398 13.8 Methods for Constructing Benchmark Portfolios.399 13.8.1 Scenario Approach to Benchmark Portfolios.402 13.8.2 Efficient Benchmark Portfolios.404 13.8.3 Efficient Formulation of Portfolio Problems.405 13.9 Cholesky Factorization for Quadratic Programs.407 13.10 Problems.409 14 Multiple Criteria and Goal Programming .411 14.1 Introduction.411 14.1.1 Alternate Optima and Multicriteria .412 14.2 Approaches to Multi-criteria Problems .412 14.2.1 Pareto Optimal Solutions and Multiple Criteria.412 14.2.2 Utility Function Approach.412 14.2.3 Trade-off Curves .413 14.2.4 Example: Ad Lib Marketing.413 14.3 Goal Programming and Soft Constraints.416 14.3.1 Example: Secondary Criterion to Choose Among Alternate Optima.417 14.3.2 Preemptive/Lexico Goal Programming.419 14.4 Minimizing the Maximum Hurt, or Unordered Lexico Minimization .422 14.4.1 Example .423 14.4.2 Finding a Unique Solution Minimizing the Maximum.423 14.5 Identifying Points on the Efficient Frontier.428 14.5.1 Efficient Points, More-is-Better Case.428 14.5.2 Efficient Points, Less-is-Better Case .430 14.5.3 Efficient Points, the Mixed Case .432 14.6 Comparing Performance with Data Envelopment Analysis.433 14.7 Problems.438 15 Economic Equilibria and Pricing.441 15.1 What is an Equilibrium?.441 15.2 A Simple Simultaneous Price/Production Decision.442 15.3 Representing Supply & Demand Curves in LPs.443 15.4 Auctions as Economic Equilibria .447 15.5 Multi-Product Pricing Problems .451 15.6 General Equilibrium Models of An Economy.455 15.7 Transportation Equilibria.457 15.7.1 User Equilibrium vs. Social Optimum .461 15.8 Equilibria in Networks as Optimization Problems.463 15.8.1 Equilibrium Network Flows.465 15.9 Problems.467 16 Game Theory and Cost Allocation .471 16.1 Introduction.471 16.2 Two-Person Games.471 16.2.1 The Minimax Strategy.472 16.3 Two-Person Non-Constant Sum Games.474
TableofContents+16.3.1Prisoner'sDilemma...475...47616.3.2ChoosingaStrategy....47916.3.3BimatrixGameswithSeveralSolutions.16.4 Nonconstant-Sum Games Involving Two or More Players.48116.4.1ShapleyValue...483..48316.5TheStableMarriagelAssignmentProblem.48716.5.1TheStableRoom-mateMatchingProblem.49016.6Problems....49317Inventory,Production,andSupplyChainManagement....49317.1 Introduction....17.2OnePeriodNewsVendorProblem.493..49417.2.1Analysis of the Decision....49617.3Multi-StageNewsVendor....49917.3.1OrderingwithaBackupOption..50117.3.2SafetyLotsize...50217.3.3MultiproductInventorieswithSubstitution.50617.4EconomicOrderQuantity......50717.5TheQ,rModel......50717.5.1DistributionofLeadTimeDemand.50717.5.2CostAnalysisofQ.r.........51217.6BaseStockInventoryPolicy..51317.6.1BaseStock—PeriodicReview.51317.6.2 Policy...51317.6.3Analysis..51517.6.4BaseStock—ContinuousReview.51517.7Multi-EchelonBaseStock,theMETRICModel.51917.8DCWithHoldbackInventory/Capacity...52117.9Multiproduct,ConstrainedDynamicLotSizeProblems52217.9.1 Input Data...52317.9.2Example....52817.9.3Extensions....52917.10Problems....53118Design&ImplementationofServiceandQueuingSystems-18.1Introduction..531..53118.2ForecastingDemandforServices...53218.3WaitingLineorQueuingTheory..53318.3.1ArrivalProcess..18.3.2QueueDiscipline..534.53418.3.3ServiceProcess.53418.3.4PerformanceMeasuresforServiceSystems53518.3.5Stationarity.....53518.3.6AHandyLittleFormula.53518.3.7Example.....53618.4SolvedQueuingModels53718.4.1NumberofOutboundWATSlinesviaErlangLossModel
x Table of Contents 16.3.1 Prisoner’s Dilemma.475 16.3.2 Choosing a Strategy .476 16.3.3 Bimatrix Games with Several Solutions.479 16.4 Nonconstant-Sum Games Involving Two or More Players .481 16.4.1 Shapley Value.483 16.5 The Stable Marriage/Assignment Problem.483 16.5.1 The Stable Room-mate Matching Problem.487 16.6 Problems.490 17 Inventory, Production, and Supply Chain Management .493 17.1 Introduction.493 17.2 One Period News Vendor Problem .493 17.2.1 Analysis of the Decision.494 17.3 Multi-Stage News Vendor.496 17.3.1 Ordering with a Backup Option.499 17.3.2 Safety Lotsize .501 17.3.3 Multiproduct Inventories with Substitution .502 17.4 Economic Order Quantity .506 17.5 The Q,r Model.507 17.5.1 Distribution of Lead Time Demand .507 17.5.2 Cost Analysis of Q,r .507 17.6 Base Stock Inventory Policy.512 17.6.1 Base Stock — Periodic Review .513 17.6.2 Policy.513 17.6.3 Analysis.513 17.6.4 Base Stock — Continuous Review .515 17.7 Multi-Echelon Base Stock, the METRIC Model.515 17.8 DC With Holdback Inventory/Capacity .519 17.9 Multiproduct, Constrained Dynamic Lot Size Problems .521 17.9.1 Input Data.522 17.9.2 Example .523 17.9.3 Extensions.528 17.10 Problems.529 18 Design & Implementation of Service and Queuing Systems.531 18.1 Introduction.531 18.2 Forecasting Demand for Services .531 18.3 Waiting Line or Queuing Theory.532 18.3.1 Arrival Process.533 18.3.2 Queue Discipline.534 18.3.3 Service Process .534 18.3.4 Performance Measures for Service Systems .534 18.3.5 Stationarity .535 18.3.6 A Handy Little Formula .535 18.3.7 Example .535 18.4 Solved Queuing Models .536 18.4.1 Number of Outbound WATS lines via Erlang Loss Model.537
Table of Contentsxi.53818.4.2EvaluatingServiceCentralizationviatheErlangCModel.53918.4.3AMixedService/lnventorySystemviatheM/G/ooModel.54018.4.4OptimalNumberofRepairmenviatheFiniteSourceModel..54118.4.5 Selection of a Processor Type via the M/G/1 Model .54318.4.6MultipleServerSystemswithGeneralDistribution,M/G/c&G/G/c.54518.5CriticalAssumptionsandTheirValidity.......18.6NetworksofQueues....545.54718.7DesignerQueues..18.7.1Example:PositivebutFiniteWaitingSpaceSystem547.55018.7.2ConstantServiceTime.InfiniteSource.NoLimitonLineLength.55018.7.3ExampleEffectofServiceTimeDistribution...55318.8Problems..19Design&ImplementationofOptimization-BasedDecisionSupportSystems...55555519.1GeneralStructureoftheModelingProcess55619.1.1DevelopingtheModel:DetailandMaintenance.55619.2Verificationand Validation.55619.2.1AppropriateLevelofDetailandValidation.55719.2.2WhenYour Model&the RW Disagree, Bet on the RW.19.2.3ShouldWeBehaveNon-Optimally?558.55819.3SeparationofDataandSystemStructure19.3.1SystemStructure55919.4Marketing theModel....559.55919.4.1Reports..56319.4.2ReportGenerationinLINGO.56519.5ReducingModelSize.....56619.5.1ReductionbyAggregation...56919.5.2ReducingtheNumberofNonzeroes.....56919.5.3ReducingtheNumberofNonzeroesinCoveringProblems.19.6On-the-FlyColumnGeneration.....571..57219.6.1ExampleofColumnGenerationAppliedtoaCuttingStockProblem.57619.6.2ColumnGenerationandIntegerProgramming...19.6.3RowGeneration...57619.7Problems..577.579ReferencesINDEX589
Table of Contents xi 18.4.2 Evaluating Service Centralization via the Erlang C Model .538 18.4.3 A Mixed Service/Inventory System via the M/G/f Model .539 18.4.4 Optimal Number of Repairmen via the Finite Source Model. .540 18.4.5 Selection of a Processor Type via the M/G/1 Model .541 18.4.6 Multiple Server Systems with General Distribution, M/G/c & G/G/c .543 18.5 Critical Assumptions and Their Validity .545 18.6 Networks of Queues .545 18.7 Designer Queues.547 18.7.1 Example: Positive but Finite Waiting Space System .547 18.7.2 Constant Service Time. Infinite Source. No Limit on Line Length .550 18.7.3 Example Effect of Service Time Distribution.550 18.8 Problems.553 19 Design & Implementation of Optimization-Based Decision Support Systems.555 19.1 General Structure of the Modeling Process .555 19.1.1 Developing the Model: Detail and Maintenance .556 19.2 Verification and Validation.556 19.2.1 Appropriate Level of Detail and Validation.556 19.2.2 When Your Model & the RW Disagree, Bet on the RW.557 19.2.3 Should We Behave Non-Optimally? .558 19.3 Separation of Data and System Structure.558 19.3.1 System Structure .559 19.4 Marketing the Model.559 19.4.1 Reports.559 19.4.2 Report Generation in LINGO .563 19.5 Reducing Model Size.565 19.5.1 Reduction by Aggregation.566 19.5.2 Reducing the Number of Nonzeroes .569 19.5.3 Reducing the Number of Nonzeroes in Covering Problems.569 19.6 On-the-Fly Column Generation .571 19.6.1 Example of Column Generation Applied to a Cutting Stock Problem .572 19.6.2 Column Generation and Integer Programming.576 19.6.3 Row Generation .576 19.7 Problems.577 References.579 INDEX .589