【文件属性】:
文件名称:Optimization Modelling A Practical Approach
文件大小:3.5MB
文件格式:PDF
更新时间:2014-04-11 16:01:32
Optimization Modelling
List of Figures...................................................................................................... xv
List of Tables ...................................................................................................... xxi
List of Mathematical Notations .................................................................... xxiv
Preface ................................................................................................................. xxv
Acknowledgments ........................................................................................... xxix
Authors............................................................................................................... xxxi
Section I Introduction to Optimization and Modelling
1 Introduction ......................................................................................................3
1.1 General Introduction .............................................................................3
1.2 History of Optimization .......................................................................4
1.3 Optimization Problems.........................................................................5
1.4 Mathematical Model..............................................................................6
1.4.1 Characteristics and Assumptions ........................................... 6
1.5 Concept of Optimization ......................................................................8
1.6 Classification of Optimization Problems .........................................11
1.7 Organization of the Book ...................................................................13
Exercises ...........................................................................................................14
References ........................................................................................................15
2 The Process of Optimization.......................................................................17
2.1 Introduction ..........................................................................................17
2.2 Decision Process...................................................................................17
2.3 Problem Identification and Clarification .........................................19
2.4 Problem Definition ..............................................................................20
2.5 Development of a Mathematical Model ..........................................21
2.5.1 Measure of Effectiveness........................................................ 23
2.6 Deriving a Solution..............................................................................25
2.7 Sensitivity Analysis .............................................................................26
2.8 Testing the Solution.............................................................................26
2.9 Implementation ....................................................................................27
v
2.10 Summary ...............................................................................................28
Exercises ...........................................................................................................29
3 Introduction to Modelling ...........................................................................31
3.1 Introduction ..........................................................................................31
3.2 Components of a Mathematical Model............................................31
3.2.1 Decision Variables................................................................... 32
3.2.2 Objective Function................................................................... 32
3.2.3 Constraints................................................................................ 32
3.3 Simple Examples..................................................................................32
3.4 Analyzing a Problem...........................................................................34
3.4.1 A Nonmathematical Programming Problem...................... 35
3.5 Modelling a Simple Problem .............................................................36
3.5.1 Defining the Variables ............................................................ 37
3.5.2 Objective Function................................................................... 37
3.5.3 Constraints................................................................................ 37
3.6 Linear Programming Model ..............................................................39
3.7 More Mathematical Models ...............................................................39
3.8 Integer Programming..........................................................................42
3.9 Multi-Objective Problem.....................................................................45
3.9.1 Objective versus Goal ............................................................. 47
3.10 Goal Programming ..............................................................................47
3.11 Nonlinear Programming.....................................................................49
3.12 Summary ...............................................................................................52
Exercises ...........................................................................................................52
Section II Modelling Techniques
4 Simple Modelling Techniques I ................................................................59
4.1 Introduction ..........................................................................................59
4.2 Use of Subscripts in Variables ...........................................................59
4.3 Simple Modelling Techniques ...........................................................60
4.3.1 Additional Work Requirement in the Formulation........... 61
4.3.2 Variables as Fractions of Other Variables ........................... 64
4.3.3 Maintaining Certain Ratios among Different Variables .... 68
4.3.4 One Constraint Is a Fraction of Another Constraint ......... 70
4.3.5 Maxi–Min or Mini–Max Objective Function....................... 75
4.3.6 Multi-Period Modelling.......................................................... 77
4.3.7 Transforming Infeasible Solutions to Satisfactory
Solutions.................................................................................... 79
4.3.8 Single to Multiple Objectives ................................................ 81
4.4 Special Types of Linear Programming.............................................82
4.4.1 Transportation Problem ......................................................... 83
4.4.2 Assignment Problem .............................................................. 86
4.4.3 Transshipment Problem ......................................................... 88
4.4.4 Project Management Problem ............................................... 91
vi
4.5 Summary ...............................................................................................98
Exercises ...........................................................................................................98
Bibliography ..................................................................................................102
5 Simple Modelling Techniques II .............................................................103
5.1 Introduction ........................................................................................103
5.2 Precedence Constraints.....................................................................103
5.3 Either–or Constraints ........................................................................104
5.4 K out of N Constraints Must Hold .................................................105
5.5 Yes-or-No Decisions ..........................................................................106
5.6 Functions with N Possible Values...................................................108
5.7 Mutually Exclusive Alternatives and Contingent Decisions......109
5.8 Linking Constraints with the Objective Function ........................111
5.9 Piecewise Linear Functions ..............................................................113
5.10 Nonlinear to Approximate Functions ............................................116
5.11 Deterministic Models with Probability Terms..............................118
5.12 Alternate Objective Functions .........................................................121
5.13 Constrained to Unconstrained Problem ........................................122
5.14 Simplifying Cross Product of Binary Variables............................124
5.15 Fractional Programming...................................................................126
5.16 Unrestricted Variables.......................................................................128
5.17 Changing Constraint and Objective Type .....................................129
5.17.1 From to¼Constraints..................................................... 129
5.17.2 From to¼Constraints..................................................... 130
5.17.3 From to Constraints.................................................... 130
5.17.4 From to Constraints.................................................... 130
5.17.5 From ¼ Constraint to and Constraints.................... 130
5.17.6 Changing Objective Type................................................... 131
5.18 Conditional Constraints....................................................................132
5.19 Dual Formulation...............................................................................133
5.20 Regression Model ..............................................................................136
5.21 Stochastic Programming...................................................................137
5.22 Constraint Programming..................................................................137
5.23 Summary .............................................................................................138
Exercises .........................................................................................................138
Bibliography ..................................................................................................142
References ......................................................................................................143
6 Modelling Large-Scale and Well-Known Problems I..........................145
6.1 Introduction ........................................................................................145
6.2 Use of the Summation (S) Sign.......................................................145
6.3 Use of the Subset (2) Sign ................................................................147
6.4 Network Flow Problems...................................................................149
6.4.1 Shortest Path Problem ........................................................ 149
6.4.2 Maximum Flow Problem ................................................... 150
6.4.3 Multi-Commodity Flow Problem ..................................... 152
vii
6.5 Knapsack Problem...............................................................................154
6.5.1 Capital Budgeting Problem................................................... 154
6.5.2 Bin Packing Problem .............................................................. 155
6.5.3 Cutting Stock Problem ........................................................... 157
6.6 Facility Location and Layout .............................................................159
6.6.1 Facility Location Problem...................................................... 159
6.6.2 Facility Layout Problem......................................................... 161
6.7 Production Planning and Scheduling ..............................................164
6.7.1 Relevant Literature ................................................................. 165
6.8 Logistics and Transportation .............................................................167
6.8.1 Airlift Problem ........................................................................ 167
6.8.2 Relevant Literature ................................................................. 168
6.9 Summary ...............................................................................................170
Exercises .........................................................................................................170
References ......................................................................................................172
7 Modelling Well-Known Problems II.......................................................177
7.1 Introduction ..........................................................................................177
7.2 Job and Machine Scheduling .............................................................177
7.2.1 Relevant Literature ................................................................. 179
7.3 Assignment and Routing....................................................................180
7.3.1 Generalized Assignment Problem ....................................... 180
7.3.2 Traveling Salesperson Problem............................................ 181
7.3.3 Relevant Literature on Traveling Salesperson
Problem..................................................................................... 184
7.3.4 Vehicle Routing Problem....................................................... 185
7.3.5 Relevant Literature on Vehicle Routing Problem ............. 188
7.4 Staff Rostering and Scheduling .........................................................189
7.4.1 Staff Scheduling: A Weekly Problem .................................. 189
7.4.2 Daily Rostering Problem ....................................................... 191
7.4.3 Relevant Literature on General Staff Scheduling .............. 192
7.4.4 Crew Planning=Scheduling Problem................................... 193
7.5 Scheduling and Timetabling Problem..............................................194
7.5.1 School Timetabling Problem................................................. 194
7.5.2 University Timetabling .......................................................... 196
7.5.3 Relevant Literature ................................................................. 197
7.6 Summary ...............................................................................................199
Exercises .........................................................................................................199
References ......................................................................................................201
8 Alternative Modelling ................................................................................205
8.1 Introduction ..........................................................................................205
8.2 Modelling under Different Assumptions ........................................205
8.2.1 A Coal Blending Problem...................................................... 205
8.2.2 First Alternative Blending Model ........................................ 207
8.2.3 Second Alternative Blending Model.................................... 209
viii
8.2.4 Comparing the Two Simple Alternative Models ........... 210
8.2.5 A Crop Planning Problem.................................................. 211
8.2.6 Crop Planning Model 1 ...................................................... 212
8.2.7 Crop Planning Model 2 ...................................................... 213
8.3 Hierarchical Modelling: An Introduction.....................................214
8.3.1 Hierarchical Modelling in a Manufacturing Context .... 215
8.3.2 Aggregate Model ................................................................. 216
8.3.3 Family Scheduling Model .................................................. 217
8.3.4 Individual Item Scheduling Model................................... 218
8.4 Summary ............................................................................................219
References ......................................................................................................220
Section III Model Solving
9 Solution Approaches: An Overview........................................................223
9.1 Introduction .......................................................................................223
9.2 Complexity and Complexity Classes ............................................223
9.2.1 Complexity of Algorithms.................................................. 223
9.2.2 Complexity Classes.............................................................. 224
9.3 Classical Optimization Techniques................................................225
9.3.1 Linear Programming............................................................ 225
9.3.2 Integer Programming: The Curse
of Dimensionality ................................................................. 227
9.3.3 Integer Linear Program: Solution Approaches ............... 228
9.3.4 Special Linear Programming Models ............................... 230
9.3.5 Goal Programming............................................................... 230
9.3.6 Nonlinear Programming..................................................... 231
9.3.7 Multi-Objective Models....................................................... 232
9.4 Heuristic Techniques........................................................................233
9.4.1 Hill Climbing ........................................................................ 233
9.4.2 Simulated Annealing ........................................................... 233
9.4.3 Tabu Search........................................................................... 234
9.4.4 Genetic Algorithms.............................................................. 234
9.4.5 Ant Colony Optimization ................................................... 235
9.4.6 Memetic Algorithms ............................................................ 236
9.4.7 Other Heuristics ................................................................... 236
9.5 Optimization Software.....................................................................236
9.5.1 LINGO=LINDO .................................................................... 237
9.5.2 MPL with OptiMax 2000, CPLEX,
and XPRESS........................................................................... 237
9.5.3 GAMS..................................................................................... 237
9.5.4 Solver and Premium Solver................................................ 238
9.5.5 Win QSB................................................................................. 238
9.5.6 MINOS ................................................................................... 238
9.6 Summary ............................................................................................239
ix
References ....................................................................................................239
Appendix-9A LINGO: An Introduction .................................................241
9A.1 Introduction.....................................................................................241
9A.2 Inputting Model in LINGO...........................................................241
9A.3 Solving the Model...........................................................................243
9A.3.1 Solver Status Window.................................................... 243
9A.3.2 LINGO Special Features ................................................ 244
9A.4 Another Example............................................................................246
9A.4.1 Objective Function .......................................................... 246
9A.4.2 Constraints ....................................................................... 247
9A.4.3 Complete LINGO Model ............................................... 248
9A.4.4 Defining the Sets ............................................................. 249
9A.4.5 Inputting the Data .......................................................... 250
9A.5 LINGO Syntax.................................................................................252
Appendix-9B MPL: An Introduction.......................................................253
9B.1 Introduction .....................................................................................253
9B.2 Use of MPL......................................................................................253
9B.3 Using Vectors and Indexes in MPL.............................................255
9B.4 A Product-Mix Model with Three Variables .............................256
Appendix-9C GAMS: An Introduction...................................................260
9C.1 Introduction.....................................................................................260
9C.2 An Example.....................................................................................260
Appendix-9D Excel Solver: An Introduction .........................................264
9D.1 Introduction.....................................................................................264
9D.2 Solving Linear Programs with Solver .........................................264
9D.2.1 Defining the Target Cell (Objective Function) ........... 266
9D.2.2 Identifying the Changing Cells
(Decision Variables) ........................................................ 266
9D.2.3 Adding Constraints ........................................................ 267
9D.2.4 Some Important Options ............................................... 269
9D.2.5 The Solution ..................................................................... 270
Appendix-9E Win QSB: An Introduction ...............................................273
9E.1 Introduction.....................................................................................273
9E.2 Problem Solving with Win QSB...................................................273
9E.3 Reference..........................................................................................275
10 Input Preparation and Model Solving ..................................................277
10.1 Introduction .....................................................................................277
10.2 Data and Data Collection ..............................................................277
10.3 Data Type.........................................................................................279
10.4 Data Preparation .............................................................................280
10.4.1 Data Requirements ......................................................... 282
10.4.2 Data Aggregation............................................................ 283
10.5 Data Preprocessing .........................................................................287
10.6 Model-Driven Data versus Data-Driven Model ........................292
x
10.7 Model Solving .................................................................................292
10.7.1 Excel Solver ....................................................................... 293
10.7.2 LINGO and MPL.............................................................. 295
10.8 Summary .........................................................................................304
Exercises .......................................................................................................304
References.....................................................................................................308
Appendix-10A Additional Problem-Solving Using LINGO ...............309
10A.1 Example 4.6 (Model 4.7) ..............................................................309
10A.1.1 LINGO Code ................................................................ 309
10A.1.2 LINGO Solution ........................................................... 310
10A.2 A Transportation Model ..............................................................310
10A.2.1 LINGO in Algebraic Form ......................................... 311
10A.2.2 LINGO Solution Report.............................................. 311
10A.2.3 LINGO Codes (Alternative)....................................... 312
10A.2.4 LINGO Solution Report (Using
Alternative Codes)....................................................... 312
10A.2.5 A Modified Transportation Model ........................... 313
10A.2.6 LINGO Solution Report (with Restricted
Path)............................................................................... 314
10A.3 Example 4.14 (Model 4.15) ..........................................................315
10A.3.1 LINGO in Algebraic Form......................................... 315
10A.3.2 LINGO Solution Report ............................................. 316
10A.3.3 LINGO Codes (Alternative Form)............................ 316
10A.3.4 LINGO Solution Report
(for Alternative Codes)............................................... 317
10A.4 Example 3.6 (Model 4.1) ..............................................................318
10A.4.1 LINGO in Algebraic Form......................................... 318
10A.4.2 LINGO Model Statistics ............................................. 318
10A.4.3 LINGO Solution........................................................... 318
10A.4.4 LINGO Codes (Alternative Form)............................ 319
10A.4.5 LINGO Solution for Alternative Codes................... 319
10A.5 Example 5.3 (Model 5.2) ..............................................................320
10A.5.1 LINGO Codes .............................................................. 320
10A.5.2 LINGO Solution Report ............................................. 321
10A.5.3 LINGO Alternative Codes ......................................... 321
10A.5.4 LINGO Solution Report (for Alternative
Codes)............................................................................ 321
10A.6 Example 5.16..................................................................................322
10A.6.1 LINGO Codes .............................................................. 322
10A.6.2 LINGO Solution Report ............................................. 322
10A.7 Example 4.11 (Model 4.12) ..........................................................323
10A.7.1 LINGO Codes .............................................................. 323
10A.7.2 LINGO Solution Report ............................................. 324
10A.8 Example 5.10 (Model 5.7) ............................................................324
10A.8.1 LINGO Codes .............................................................. 324
10A.8.2 LINGO Solution Report ............................................. 325
xi
11