Symbols ...................................................... XIII
A Linear Algebra ............................................... 1
A.1 Matrix Algebra .......................................... 1
A.2 Systems of Simultaneous Linear Equations ................ 5
A.3 Convexity .............................................. 23
B Computational Complexity .................................... 31
B.1 Algorithms and Time Complexity Functions ............... 31
B.2 Examples of Time Complexity Functions .................. 37
B.3 Classes of Problems and Their Relations ................ 41
1 Introduction ................................................ 45
1.1 A Short History of Linear Programming .................. 45
1.2 Assumptions and the Main Components of Linear
Programming Problems ................................... 48
1.3 The Modeling Process ................................... 53
1.4 The Three Phases in Optimization ....................... 57
1.5 Solving the Model and Interpreting the Printout ........ 60
2 Applications ................................................ 67
2.1 The Diet Problem ....................................... 67
2.2 Allocation Problems .................................... 71
2.3 Cutting Stock Problems ................................. 75
2.4 Employee Scheduling .................................... 80
2.5 Data Envelopment Analysis .............................. 82
2.6 Inventory Planning ..................................... 85
2.7 Blending Problems ...................................... 89
2.8 Transportation Problems ................................ 91
2.9 Assignment Problems ................................... 102
2.10 A Production - Inventory Model: A Case Study .......... 107
3 The Simplex Method ......................................... 129
3.1 Graphical Concepts .................................... 129
3.1.1 The Graphical Solution Technique ............... 129
3.1.2 Four Special Cases ............................. 138
3.2 Algebraic Concepts .................................... 143
3.2.1 The Algebraic Solution Technique ............... 143
3.2.2 Four Special Cases Revisited ................... 158
4 Duality .................................................... 167
4.1 The Fundamental Theory of Duality ..................... 167
4.2 Primal-Dual Relations ................................. 183
4.3 Interpretations of the Dual Problem ................... 198
5 Extensions of the Simplex Method ........................... 203
5.1 The Dual Simplex Method ............................... 203
5.2 The Upper Bounding Technique .......................... 212
5.3 Column Generation ..................................... 219
6 Postoptimality Analyses .................................... 225
6.1 Graphical Sensitivity Analysis ........................ 227
6.2 Changes of the Right-Hand Side Values ................. 232
6.3 Changes of the Objective Function Coefficients ........ 240
6.4 Sensitivity Analyses in the Presence of Degeneracy .... 245
6.5 Addition of a Constraint .............................. 248
6.6 Economic Analysis of an Optimal Solution .............. 252
7 Non-Simplex Based Solution Methods ......................... 261
7.1 Alternatives to the Simplex Method .................... 262
7.2 Interior Point Methods ................................ 273
8 Problem Reformulations ..................................... 295
8.1 Reformulations of Variables ........................... 295
8.1.1 Lower Bounding Constraints ..................... 295
8.1.2 Variables Unrestricted in Sign ................. 296
8.2 Reformulations of Constraints ......................... 298
8.3 Reformulations of the Objective Function .............. 301
8.3.1 Minimize the Weighted Sum of Absolute Values ... 301
8.3.2 Bottleneck Problems ............................ 306
8.3.3 Minimax and Maximin Problems ................... 313
8.3.4 Fractional (Hyperbolic) Programming ............ 320
9 Multiobjective Programming ................................. 325
9.1 Vector Optimization ................................... 327
9.2 Models with Exogenous Tradeoffs Between Objectives .... 337
9.2.1 The Weighting Method ........................... 337
9.2.2 The Constraint Method .......................... 339
9.3 Models with Exogenous Achievement Levels .............. 341
9.3.1 Reference Point Programming .................... 342
9.3.2 Fuzzy Programming .............................. 346
9.3.3 Goal Programming ............................... 351
9.4 Bilevel Programming ................................... 359
References .................................................... 363
Subject Index ................................................. 377
| 
