lingo tutorial教学-菜鸟资源分享lingo相关optimization modeling with lingo

1、Optimization Modeling withLINGOSixth EditionLINDO Systems, Inc.1415 North Dayton Street, Chicago, Illinois 60622 Phone: (312)988-7422 Fax: (312)988-9065E-mail: TRADEMARKSWhatsBest! and LINDO are registered trademarks and LINGO is a trademark of LINDO Systems, Inc. Other product and comp

2、any names mentioned herein are the property of their respectiveowners.Copyright 2006 by LINDO Systems Inc All rights reserved. First edition 1998 Sixth edition, April 2006Printed in the United States of America First printing 2003ISBN: 1-893355-00-4Published by1415 North Dayton Street Chicago, Illin

3、ois 60622Technical Support: (312) 988-9421 e-mail: ContentsPrefacexiiiAcknowledgmentsxiii1 What Is Optimization?11.1 Introduction11.2 A Simple Product Mix Problem11.2.1 Graphical Analysis21.3 Linearity51.4 Analysis of LP Solutions61.5 Sensitivity Analysis, Reduced Cos

4、ts, and Dual Prices81.5.1 Reduced Costs81.5.2 Dual Prices81.6 Unbounded Formulations91.7 Infeasible Formulations101.8 Multiple Optimal Solutions and Degeneracy111.8.1 The “Snake Eyes” Condition131.8.2 Degeneracy and Redundant Constraints161.9 Nonlinear Models and Global Optimization171.10 Problems18

5、2 Solving Math Programs with LINGO232.1 Introduction232.2 LINGO for Windows232.2.1 File Menu232.2.2 Edit Menu252.2.3 LINGO Menu272.2.4 Windows Menu282.2.5 Help Menu292.2.6 Summary292.3 Getting Started on a Small Problem292.4 Integer Programming with LINGO302.4.1 Warning for Integer Programs322.5 Sol

6、ving an Optimization Model322.6 Problems333 Analyzing Solutions353.1 Economic Analysis of Solution Reports353.2 Economic Relationship Between Dual Prices and Reduced Costs353.2.1 The Costing Out Operation: An Illustration363.2.2 Dual Prices, LaGrange Multipliers, KKT Conditions, and Activity Costing

7、373.3 Range of Validity of Reduced Costs and Dual Prices383.3.1 Predicting the Effect of Simultaneous Changes in ParametersThe 100% Rule . 43 3.4 Sensitivity Analysis of the Constraint Coefficients44iiiivTable of Contents3.5 The Dual LP Problem, or the Landlord and the Renter453.6 Problems474 The Mo

8、del Formulation Process534.1 The Overall Process534.2 Approaches to Model Formulation544.3 The Template Approach544.3.1 Product Mix Problems544.3.2 Covering, Staffing, and Cutting Stock Problems544.3.3 Blending Problems544.3.4 Multiperiod Planning Problems554.3.5 Network, Distribution, and PERT/CPM

9、Models554.3.6 Multiperiod Planning Problems with Random Elements554.3.7 Financial Portfolio Models554.3.8 Game Theory Models564.4 Constructive Approach to Model Formulation564.4.1 Example574.4.2 Formulating Our Example Problem574.5 Choosing Costs Correctly584.5.1 Sunk vs. Variable Costs584.5.2 Joint

10、 Products604.5.3 Book Value vs. Market Value614.6 Common Errors in Formulating Models634.7 The Nonsimultaneity Error654.8 Problems665 The Sets View of the World695.1 Introduction695.1.1 Why Use Sets?695.1.2 What Are Sets?695.1.3 Types of Sets705.2 The SETS Section of a Model705.2.1 Defining Primitiv

11、e Sets705.2.2 Defining Derived Sets715.2.3 Summary725.3 The DATA Section735.4 Set Looping Functions755.4.1 SUM Set Looping Function765.4.2 MIN and MAX Set Looping Functions775.4.3 FOR Set Looping Function785.4.4 Nested Set Looping Functions795.5 Set Based Modeling Examples795.5.1 Primitive Set Examp

12、le805.5.2 Dense Derived Set Example835.5.3 Sparse Derived Set Example - Explicit List855.5.4 A Sparse Derived Set Using a Membership Filter905.6 Domain Functions for Variables94Table of Contentsv5.7 Spreadsheets and LINGO945.8 Summary985.9 Problems986 Product Mix Problems996.1 Introduction996.2 Exam

13、ple1006.3 Process Selection Product Mix Problems1036.4 Problems1087 Covering, Staffing & Cutting Stock Models1117.1 Introduction1117.1.1 Staffing Problems1127.1.2 Example: Northeast Tollway Staffing Problems1127.1.3 Additional Staff Scheduling Features1147.2 Cutting Stock and Pattern Selection1157.2

14、.1 Example: Cooldot Cutting Stock Problem1167.2.2 Formulation and Solution of Cooldot1177.2.3 Generalizations of the Cutting Stock Problem1217.2.4 Two-Dimensional Cutting Stock Problems1237.3 Crew Scheduling Problems1237.3.1 Example: Sayre-Priors Crew Scheduling1247.3.2 Solving the Sayre/Priors Crew

15、 Scheduling Problem1267.3.3 Additional Practical Details1287.4 A Generic Covering/Partitioning/Packing Model1297.5 Problems1318 Networks, Distribution and PERT/CPM1418.1 Whats Special About Network Models1418.1.1 Special Cases1448.2 PERT/CPM Networks and LP1448.3 Activity-on-Arc vs. Activity-on-Node

16、 Network Diagrams1498.4 Crashing of Project Networks1508.4.1 The Cost and Value of Crashing1518.4.2 The Cost of Crashing an Activity1518.4.3 The Value of Crashing a Project1518.4.4 Formulation of the Crashing Problem1528.5 Resource Constraints in Project Scheduling1558.6 Path Formulations1578.6.1 Ex

17、ample1588.7 Path Formulations of Undirected Networks1598.7.1 Example1608.8 Double Entry Bookkeeping: A Network Model of the Firm1628.9 Extensions of Network LP Models1638.9.1 Multicommodity Network Flows1648.9.2 Reducing the Size of Multicommodity Problems1658.9.3 Multicommodity Flow Example165viTab

18、le of Contents8.9.4 Fleet Routing and Assignment1688.9.5 Fleet Assignment1718.9.6 Leontief Flow Models1768.9.7 Activity/Resource Diagrams1788.9.8 Spanning Trees1808.9.9 Steiner Trees1828.10 Nonlinear Networks1868.11 Problems1889 Multi-period Planning Problems1979.1 Introduction1979.2 A Dynamic Produ

19、ction Problem1999.2.1 Formulation1999.2.2 Constraints2009.2.3 Representing Absolute Values2029.3 Multi-period Financial Models2039.3.1 Example: Cash Flow Matching2039.4 Financial Planning Models with Tax Considerations2079.4.1 Formulation and Solution of the WSDM Problem2089.4.2 Interpretation of th

20、e Dual Prices2099.5 Present Value vs. LP Analysis2109.6 Accounting for Income Taxes2119.7 Dynamic or Multi-period Networks2149.8 End Effects2169.8.1 Perishability/Shelf Life Constraints2179.8.2 Startup and Shutdown Costs2179.9 Non-optimality of Cyclic Solutions to Cyclic Problems2179.10 Problems2231

21、0 Blending of Input Materials22710.1 Introduction22710.2 The Structure of Blending Problems22810.2.1 Example: The Pittsburgh Steel Company Blending Problem22910.2.2 Formulation and Solution of the Pittsburgh Steel Blending Problem23010.3 A Blending Problem within a Product Mix Problem23210.3.1 Formu

22、lation23310.3.2 Representing Two-sided Constraints23410.4 Proper Choice of Alternate Interpretations of Quality Requirements23710.5 How to Compute Blended Quality23910.5.1 Example24010.5.2 Generalized Mean24010.6 Interpretation of Dual Prices for Blending Constraints24210.7 Fractional or Hyperbolic

23、Programming24210.8 Multi-Level Blending: Pooling Problems24310.9 Problems248Table of Contents vii11 Formulating and Solving Integer Programs26111.1 Introduction26111.1.1 Types of Variables26111.2 Exploiting the IP Capability: Standard Applications26211.2.1 Binary Representation of General Integer Va

24、riables26211.2.2 Minimum Batch Size Constraints26211.2.3 Fixed Charge Problems26311.2.4 The Simple Plant Location Problem26311.2.5 The Capacitated Plant Location Problem (CPL)26511.2.6 Modeling Alternatives with the Scenario Approach26711.2.7 Linearizing a Piecewise Linear Function26811.2.8 Converti

25、ng to Separable Functions27111.3 Outline of Integer Programming Methods27211.4 Computational Difficulty of Integer Programs27411.4.1 NP-Complete Problems27511.5 Problems with Naturally Integer Solutions and the Prayer Algorithm27511.5.1 Network LPs Revisited27611.5.2 Integral Leontief Constraints276

26、11.5.3 Example: A One-Period MRP Problem27711.5.4 Transformations to Naturally Integer Formulations27911.6 The Assignment Problem and Related Sequencing and Routing Problems28111.6.1 Example: The Assignment Problem28111.6.2 The Traveling Salesperson Problem28311.6.3 Capacitated Multiple TSP/Vehicle

27、Routing Problems28911.6.4 Minimum Spanning Tree29311.6.5 The Linear Ordering Problem29311.6.6 Quadratic Assignment Problem29611.7 Problems of Grouping, Matching, Covering, Partitioning, and Packing29911.7.1 Formulation as an Assignment Problem30011.7.2 Matching Problems, Groups of Size Two30111.7.3

28、Groups with More Than Two Members30311.7.4 Groups with a Variable Number of Members, Assignment Version30711.7.5 Groups with A Variable Number of Members, Packing Version30811.7.6 Groups with A Variable Number of Members, Cutting Stock Problem31111.7.7 Groups with A Variable Number of Members, Vehic

29、le Routing31511.8 Linearizing Products of Variables32011.8.1 Example: Bundling of Products32011.9 Representing Logical Conditions32311.10 Problems32412 Decision making Under Uncertainty and Stochastic Programs33512.1 Introduction33512.2 Identifying Sources of Uncertainty33512.3 The Scenario Approach

30、33612.4 A More Complicated Two-Period Planning Problem33812.4.1 The Warm Winter Solution34012.4.2 The Cold Winter Solution340viii Table of Contents12.4.3 The Unconditional Solution34112.5 Expected Value of Perfect Information (EVPI)34412.6 Expected Value of Modeling Uncertainty34512.6.1 Certainty Eq

31、uivalence34512.7 Risk Aversion34612.7.1 Downside Risk34712.7.2 Example34812.8 Choosing Scenarios35012.8.1 Matching Scenario Statistics to Targets35112.8.2 Generating Scenarios with a Specified Covariance Structure35212.8.3 Generating a Suitable Z Matrix35312.8.4 Example35412.8.5 Converting Multi-Sta

32、ge Problems to Two-Stage Problems35512.9 Decisions Under Uncertainty with More than Two Periods35512.9.1 Dynamic Programming and Financial Option Models35612.9.2 Binomial Tree Models of Interest Rates35712.9.3 Binomial Tree Models of Foreign Exchange Rates36112.10 Decisions Under Uncertainty with an

33、 Infinite Number of Periods36312.10.1 Example: Cash Balance Management36512.11 Chance-Constrained Programs36812.12 Problems36913 Portfolio Optimization37113.1 Introduction37113.2 The Markowitz Mean/Variance Portfolio Model37113.2.1 Example37213.3 Dualing Objectives: Efficient Frontier and Parametric

34、 Analysis37513.3.1 Portfolios with a Risk-Free Asset37513.3.2 The Sharpe Ratio37813.4 Important Variations of the Portfolio Model37913.4.1 Portfolios with Transaction Costs38013.4.2 Example38013.4.3 Portfolios with Taxes38213.4.4 Factors Model for Simplifying the Covariance Structure38413.4.5 Exampl

35、e of the Factor Model38513.4.6 Scenario Model for Representing Uncertainty38613.4.7 Example: Scenario Model for Representing Uncertainty38713.5 Measures of Risk other than Variance38913.5.1 Maximizing the Minimum Return39013.5.2 Value at Risk39113.5.3 Example of VAR39213.6 Scenario Model and Minimiz

36、ing Downside Risk39313.6.1 Semi-variance and Downside Risk39413.6.2 Downside Risk and MAD39613.6.3 Scenarios Based Directly Upon a Covariance Matrix39613.7 Hedging, Matching and Program Trading39813.7.1 Portfolio Hedging398Table of Contents ix13.7.2 Portfolio Matching, Tracking, and Program Trading3

37、9813.8 Methods for Constructing Benchmark Portfolios39913.8.1 Scenario Approach to Benchmark Portfolios40213.8.2 Efficient Benchmark Portfolios40413.8.3 Efficient Formulation of Portfolio Problems40513.9 Cholesky Factorization for Quadratic Programs40713.10 Problems40914 Multiple Criteria and Goal P

38、rogramming41114.1 Introduction41114.1.1 Alternate Optima and Multicriteria41214.2 Approaches to Multi-criteria Problems41214.2.1 Pareto Optimal Solutions and Multiple Criteria41214.2.2 Utility Function Approach41214.2.3 Trade-off Curves41314.2.4 Example: Ad Lib Marketing41314.3 Goal Programming and

39、Soft Constraints41614.3.1 Example: Secondary Criterion to Choose Among Alternate Optima41714.3.2 Preemptive/Lexico Goal Programming41914.4 Minimizing the Maximum Hurt, or Unordered Lexico Minimization42214.4.1 Example42314.4.2 Finding a Unique Solution Minimizing the Maximum42314.5 Identifying Point

40、s on the Efficient Frontier42814.5.1 Efficient Points, More-is-Better Case42814.5.2 Efficient Points, Less-is-Better Case43014.5.3 Efficient Points, the Mixed Case43214.6 Comparing Performance with Data Envelopment Analysis43314.7 Problems43815 Economic Equilibria and Pricing44115.1 What is an Equil

41、ibrium?44115.2 A Simple Simultaneous Price/Production Decision44215.3 Representing Supply & Demand Curves in LPs44315.4 Auctions as Economic Equilibria44715.5 Multi-Product Pricing Problems45115.6 General Equilibrium Models of An Economy45515.7 Transportation Equilibria45715.7.1 User Equilibrium vs.

42、 Social Optimum46115.8 Equilibria in Networks as Optimization Problems46315.8.1 Equilibrium Network Flows46515.9 Problems46716 Game Theory and Cost Allocation47116.1 Introduction47116.2 Two-Person Games47116.2.1 The Minimax Strategy47216.3 Two-Person Non-Constant Sum Games474xTable of Contents16.3.1

43、 Prisoners Dilemma47516.3.2 Choosing a Strategy47616.3.3 Bimatrix Games with Several Solutions47916.4 Nonconstant-Sum Games Involving Two or More Players48116.4.1 Shapley Value48316.5 The Stable Marriage/Assignment Problem48316.5.1 The Stable Room-mate Matching Problem48716.6 Problems49017 Inventory

44、, Production, and Supply Chain Management49317.1 Introduction49317.2 One Period News Vendor Problem49317.2.1 Analysis of the Decision49417.3 Multi-Stage News Vendor49617.3.1 Ordering with a Backup Option49917.3.2 Safety Lotsize50117.3.3 Multiproduct Inventories with Substitution50217.4 Economic Orde

45、r Quantity50617.5 The Q,r Model50717.5.1 Distribution of Lead Time Demand50717.5.2 Cost Analysis of Q,r50717.6 Base Stock Inventory Policy51217.6.1 Base Stock Periodic Review51317.6.2 Policy51317.6.3 Analysis51317.6.4 Base Stock Continuous Review51517.7 Multi-Echelon Base Stock, the METRIC Model5151

46、7.8 DC With Holdback Inventory/Capacity51917.9 Multiproduct, Constrained Dynamic Lot Size Problems52117.9.1 Input Data52217.9.2 Example52317.9.3 Extensions52817.10 Problems52918 Design & Implementation of Service and Queuing Systems53118.1 Introduction53118.2 Forecasting Demand for Services53118.3 W

47、aiting Line or Queuing Theory53218.3.1 Arrival Process53318.3.2 Queue Discipline53418.3.3 Service Process53418.3.4 Performance Measures for Service Systems53418.3.5 Stationarity53518.3.6 A Handy Little Formula53518.3.7 Example53518.4 Solved Queuing Models53618.4.1 Number of Outbound WATS lines via E

48、rlang Loss Model537Table of Contents xi18.4.2 Evaluating Service Centralization via the Erlang C Model53818.4.3 A Mixed Service/Inventory System via the M/G/f Model 53918.4.4 Optimal Number of Repairmen via the Finite Source Model54018.4.5 Selection of a Processor Type via the M/G/1 Model54118.4.6 M

49、ultiple Server Systems with General Distribution, M/G/c & G/G/c54318.5 Critical Assumptions and Their Validity54518.6 Networks of Queues54518.7 Designer Queues54718.7.1 Example: Positive but Finite Waiting Space System54718.7.2 Constant Service Time. Infinite Source. No Limit on Line Length55018.7.3

50、 Example Effect of Service Time Distribution55018.8 Problems55319 Design & Implementation of Optimization-Based Decision Support Systems55519.1 General Structure of the Modeling Process55519.1.1 Developing the Model: Detail and Maintenance55619.2 Verification and Validation55619.2.1 Appropriate Leve

51、l of Detail and Validation55619.2.2 When Your Model & the RW Disagree, Bet on the RW55719.2.3 Should We Behave Non-Optimally?55819.3 Separation of Data and System Structure55819.3.1 System Structure55919.4 Marketing the Model55919.4.1 Reports55919.4.2 Report Generation in LINGO56319.5 Reducing Model

52、 Size56519.5.1 Reduction by Aggregation56619.5.2 Reducing the Number of Nonzeroes56919.5.3 Reducing the Number of Nonzeroes in Covering Problems56919.6 On-the-Fly Column Generation57119.6.1 Example of Column Generation Applied to a Cutting Stock Problem57219.6.2 Column Generation and Integer Program

53、ming57619.6.3 Row Generation57619.7 Problems577References579INDEX589xii Table of ContentsPrefaceThis 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, m

54、anagers, 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 pro

55、blems. 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), and3. 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