Optimization for Decision Making

Linear and Quadratic Models
1. Auflage 2010
ISBN: 978-1-4419-1291-6
Verlag: Springer-Verlag
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 482 Seiten

Linear programming (LP), modeling, and optimization are very much the fundamentals of OR, and no academic program is complete without them. No matter how highly developed one's LP skills are, however, if a fine appreciation for modeling isn't developed to make the best use of those skills, then the truly 'best solutions' are often not realized, and efforts go wasted. Katta Murty studied LP with George Dantzig, the father of linear programming, and has written the graduate-level solution to that problem. While maintaining the rigorous LP instruction required, Murty's new book is unique in his focus on developing modeling skills to support valid decision making for complex real world problems. He describes the approach as 'intelligent modeling and decision making' to emphasize the importance of employing the best expression of actual problems and then applying the most computationally effective and efficient solution technique for that model.

Autoren/Hrsg.

Inhaltsverzeichnis

1;Preface;6
2;Contents;11
3;Glossary of Symbols and Abbreviations;18
4;1 Linear Equations, Inequalities, Linear Programming: A Brief Historical Overview;24
4.1;1.1 Mathematical Modeling, Algebra, Systems of Linear Equations, and Linear Algebra;24
4.1.1;1.1.1 Elimination Method for Solving Linear Equations;25
4.2;1.2 Review of the GJ Method for Solving Linear Equations: Revised GJ Method;28
4.2.1;1.2.1 GJ Method Using the Memory Matrix to Generate the Basis Inverse;31
4.2.2;1.2.2 The Revised GJ Method with Explicit Basis Inverse;34
4.3;1.3 Lack of a Method to Solve Linear Inequalities Until Modern Times;37
4.3.1;1.3.1 The Importance of Linear Inequality Constraints and Their Relation to Linear Programs;38
4.4;1.4 Fourier Elimination Method for Linear Inequalities;40
4.5;1.5 History of the Simplex Method for LP;41
4.6;1.6 The Simplex Method for Solving LPs and Linear Inequalities Viewed as an Extension of the GJ Method;42
4.6.1;1.6.1 Generating the Phase I Problem if No Feasible Solution Available for the Original Problem;42
4.7;1.7 The Importance of LP;44
4.7.1;1.7.1 Marginal Values and Other Planning Toolsthat can be Derived from the LP Model;45
4.8;1.8 Dantzig's Contributions to Linear Algebra, Convex Polyhedra, OR, Computer Science;50
4.8.1;1.8.1 Contributions to OR;50
4.8.2;1.8.2 Contributions to Linear Algebra and Computer Science;50
4.8.3;1.8.3 Contributions to the Mathematical Study of Convex Polyhedra;51
4.9;1.9 Interior Point Methods for LP;52
4.10;1.10 Newer Methods;53
4.11;1.11 Conclusions;53
4.12;1.12 How to Be a Successful Decision Maker?;53
4.13;1.13 Exercises;54
4.14;References;60
5;2 Formulation Techniques Involving Transformationsof Variables;62
5.1;2.1 Operations Research: The Science of Better;62
5.2;2.2 Differentiable Convex and Concave Functions;63
5.2.1;2.2.1 Convex and Concave Functions;63
5.3;2.3 Piecewise Linear (PL) Functions;69
5.3.1;2.3.1 Convexity of PL Functions of a Single Variable;70
5.3.2;2.3.2 PL Convex and Concave Functions in Several Variables;71
5.4;2.4 Optimizing PL Functions Subject to Linear Constraints;76
5.4.1;2.4.1 Minimizing a Separable PL Convex Function Subject to Linear Constraints;76
5.4.2;2.4.2 Min-max, Max-min Problems;80
5.4.3;2.4.3 Minimizing Positive Linear Combinations of Absolute Values of Affine Functions;82
5.4.4;2.4.4 Minimizing the Maximum of the Absolute Values of Several Affine Functions;84
5.4.5;2.4.5 Minimizing Positive Combinationsof Excesses/Shortages;92
5.5;2.5 Multiobjective LP Models;95
5.5.1;2.5.1 Practical Approaches for Handling Multiobjective LPs in Current Use;97
5.5.2;2.5.2 Weighted Average Technique;98
5.5.3;2.5.3 The Goal Programming Approach;99
5.6;2.6 Exercises;102
5.7;References;147
6;3 Intelligent Modeling Essential to Get Good Results;149
6.1;3.1 The Need for Intelligent Modeling in Real WorldDecision Making;149
6.2;3.2 Case Studies Illustrating the Need for Intelligent Modeling;150
6.2.1;3.2.1 Case Study 1: Application in a Container Shipping Terminal;150
6.2.2;3.2.2 Case Study 2: Application in a Bus Rental Company;162
6.2.3;3.2.3 Case Study 3: Allocating Gates to Flights at an International Airport;172
6.3;3.3 Murty's Three Commandments for SuccessfulDecision Making;186
6.4;3.4 Exercises;186
6.5;References;187
7;4 Polyhedral Geometry;189
7.1;4.1 Hyperplanes, Half-Spaces, and Convex Polyhedra;189
7.1.1;4.1.1 Expressing a Linear Equation as a Pair of Inequalities;189
7.1.2;4.1.2 Straight Lines, Half-Lines, and Their Directions;191
7.1.3;4.1.3 Convex Combinations, Line Segments;192
7.2;4.2 Tight (Active)/Slack (Inactive) Constraints at a Feasible Solution ;193
7.2.1;4.2.1 What is the Importance of Classifying the Constraints in a System as Active/Inactive at a Feasible Solution?;195
7.3;4.3 Subspaces, Affine Spaces, Convex Polyhedra; Binding, Nonbinding, Redundant Inequalities; Minimal Representations;196
7.4;4.4 The Interior and the Boundary of a Convex Polyhedron;198
7.5;4.5 Supporting Hyperplanes, Faces of a Convex Polyhedron, Optimum Face for an LP;199
7.5.1;4.5.1 Supporting Hyperplanes;199
7.5.2;4.5.2 Faces of a Convex Polyhedron;200
7.6;4.6 Zero-Dimensional Faces, or Extreme Points, or Basic Feasible Solutions (BFSs);202
7.6.1;4.6.1 Nondegenerate, Degenerate BFSs for Systems in Standard Form;206
7.6.2;4.6.2 Basic Vectors and Bases for a System in Standard Form;207
7.6.3;4.6.3 BFSs for Systems in Standard Form for Bounded Variables;209
7.7;4.7 Purification Routine for Deriving a BFSs from a Feasible Solution for Systems in Standard Form;210
7.7.1;4.7.1 The Main Strategy of the Purification Routine;211
7.7.2;4.7.2 General Step in the Purification Routine;212
7.7.3;4.7.3 Purification Routine for Systems in Symmetric Form;218
7.8;4.8 Edges, One-Dimensional Faces, Adjacency of Extreme Points, Extreme Directions;226
7.8.1;4.8.1 How to Check if a Given Feasible Solution is on an Edge;227
7.9;4.9 Adjacency in a Primal Simplex Pivot Step;234
7.10;4.10 How to Obtain All Adjacent Extreme Points of a Given Extreme Point?;240
7.11;4.11 Faces of Dimension 2 of a Convex Polyhedron;243
7.11.1;4.11.1 Facets of a Convex Polyhedron;244
7.12;4.12 Optimality Criterion in the Primal Simplex Algorithm;245
7.13;4.13 Boundedness of Convex Polyhedra;248
7.14;4.14 Exercises;251
7.15;References;255
8;5 Duality Theory and Optimality Conditions for LPs;256
8.1;5.1 The Dual Problem;256
8.2;5.2 Deriving the Dual by Rational Economic Arguments;257
8.2.1;5.2.1 Dual Variables are Marginal Values;259
8.2.2;5.2.2 The Dual of the General Problem in This Form;259
8.3;5.3 Rules for Writing the Dual of a General LP ;260
8.3.1;5.3.1 Complementary Pairs in a Primal, Dual Pair of LPs;262
8.3.2;5.3.2 What Is the Importance of Complementary Pairs?;263
8.3.3;5.3.3 Complementary Pairs for LPs in Standard Form;263
8.3.4;5.3.4 Complementary Pairs for LPs in Symmetric Form;265
8.3.5;5.3.5 Complementary Pairs for LPs in Bounded Variable Standard Form;266
8.4;5.4 Duality Theory and Optimality Conditions for LP ;268
8.4.1;5.4.1 The Importance of Good Lower Bounding Strategies in Solving Optimization Problems;270
8.4.2;5.4.2 Definition of the Dual Solution Corresponding to Each Primal Basic Vector for an LP in Standard Form;272
8.4.3;5.4.3 Properties Satisfied by the Primal and Dual Basic Solutions Corresponding to a Primal Basic Vector;275
8.4.4;5.4.4 The Duality Theorem of LP;278
8.4.5;5.4.5 Optimality Conditions for LP;279
8.4.6;5.4.6 Necessary and Sufficient Optimality Conditions for LP;281
8.4.7;5.4.7 Duality Gap, a Measure of Distance from Optimality;281
8.4.8;5.4.8 Using CS Conditions to Check the Optimality of a Given Feasible Solution to an LP;282
8.5;5.5 How Various Algorithms Solve LPs;289
8.6;5.6 How to Check if an Optimum Solution is Unique;290
8.6.1;5.6.1 Primal and Dual Degeneracy of a Basic Vector for an LP in Standard Form;290
8.6.2;5.6.2 Sufficient Conditions for Checking the Uniqueness of Primal and Dual Optimum Solutions;292
8.6.3;5.6.3 Procedure to Check if the BFS Corresponding to an Optimum Basic Vector xB is the Unique Optimum Solution;293
8.6.4;5.6.4 The Optimum Face for an LP;296
8.7;5.7 Mathematical Equivalence of LP to the Problem of Finding a Feasible Solution of a System of Linear Constraints Involving Inequalities;297
8.8;5.8 Marginal Values and the Dual Optimum Solution;298
8.9;5.9 Summary of Optimality Conditions for Continuous Variable Nonlinear Programs and Their Relation to Those for LP;300
8.9.1;5.9.1 Global Minimum (Maximum), Local Minimum (Maximum), and Stationary Points;300
8.9.2;5.9.2 Relationship to Optimality Conditions for LP Discussed Earlier;305
8.10;5.10 Exercises;306
8.11;References;317
9;6 Revised Simplex Variants of the Primal and Dual Simplex Methods and Sensitivity Analysis;318
9.1;6.1 Primal Revised Simplex Algorithm Using the Explicit Basis Inverse;319
9.1.1;6.1.1 Steps in an Iteration of the Primal Simplex Algorithm When (xB, –z) is the Primal Feasible Basic Vector;320
9.1.2;6.1.2 Practical Consequences of Satisfying the Unboundedness Criterion;327
9.1.3;6.1.3 Features of the Simplex Algorithm;328
9.2;6.2 Revised Primal Simplex Method (Phase I, II) with Explicit Basis Inverse;328
9.2.1;6.2.1 Setting Up the Phase I Problem;328
9.3;6.3 How to Find a Feasible Solution to a System of Linear Constraints;335
9.4;6.4 Infeasibility Analysis;337
9.5;6.5 Practical Usefulness of the Revised Simplex Method Using Explicit Basis Inverse;339
9.6;6.6 Cycling in the Simplex Method;340
9.7;6.7 Revised Simplex Method Using the Product Form of the Inverse;341
9.7.1;6.7.1 Pivot Matrices;341
9.7.2;6.7.2 A General Iteration in the Revised Simplex Method Using the Product Form of the Inverse;342
9.7.3;6.7.3 Transition from Phase I to Phase II;343
9.7.4;6.7.4 Reinversions in the Revised Simplex Method Using PFI;344
9.8;6.8 Revised Simplex Method Using Other Factorizations of the Basis Inverse;345
9.9;6.9 Finding the Optimum Face of an LP (Alternate Optimum Solutions);345
9.10;6.10 The Dual Simplex Algorithm;347
9.10.1;6.10.1 Properties of the Dual Simplex Algorithm;355
9.11;6.11 Importance of the Dual Simplex Algorithm, How to Get New Optimum Efficiently When RHS Changes or New Constraints Are Added to the Model;358
9.11.1;6.11.1 The Dual Simplex Method;363
9.12;6.12 Marginal Analysis;363
9.12.1;6.12.1 How to Compute the Marginal Values in a General LP Model;366
9.13;6.13 Sensitivity Analysis;368
9.13.1;6.13.1 Introducing a New Nonnegative Variable;368
9.13.2;6.13.2 Ranging the Cost Coefficient or an I/O Coefficient in a Nonbasic Column Vector;370
9.13.3;6.13.3 Ranging a Basic Cost Coefficient;373
9.13.4;6.13.4 Ranging the RHS Constants;374
9.13.5;6.13.5 Features of Sensitivity Analysis Available in Commercial LP Software;375
9.13.6;6.13.6 Other Types of Sensitivity Analyses;376
9.14;6.14 Revised Primal Simplex Method for Solving Bounded Variable LP Models;376
9.14.1;6.14.1 The Bounded Variable Primal Simplex Algorithm;379
9.14.2;6.14.2 General Iteration in the Bounded Variable Primal Simplex Algorithm;380
9.14.3;6.14.3 The Bounded Variable Primal Simplex Method;383
9.15;6.15 Exercises;384
9.16;References;413
10;7 Interior Point Methods for LP;414
10.1;7.1 Boundary Point and Interior Point Methods;414
10.2;7.2 Interior Feasible Solutions;415
10.3;7.3 General Introduction to Interior Point Methods;415
10.4;7.4 Center, Analytic Center, Central Path;420
10.5;7.5 The Affine Scaling Method;422
10.6;7.6 Newton's Method for Solving Systems of Nonlinear Equations;429
10.7;7.7 Primal-Dual Path Following Methods;430
10.8;7.8 Summary of Results on the Primal-Dual IPMs;435
10.9;7.9 Exercises;436
10.10;References;437
11;8 Sphere Methods for LP;438
11.1;8.1 Introduction;438
11.2;8.2 Ball Centers: Geometric Concepts;443
11.3;8.3 Approximate Computation of Ball Centers ;446
11.3.1;8.3.1 Approximate Computation of Ball Centersof Polyhedra;446
11.3.2;8.3.2 Computing An Approximate Ball Center of K on the Current Objective Plane;451
11.3.3;8.3.3 Ball Centers of Some Simple Special Polytopes;451
11.4;8.4 Sphere Method 1;452
11.4.1;8.4.1 Summary of Computational Results on Sphere Method 1;456
11.5;8.5 Sphere Method 2;457
11.6;8.6 Improving the Performance of Sphere Methods Further;460
11.7;8.7 Some Open Theoretical Research Problems;461
11.8;8.8 Future Research Directions;463
11.9;8.9 Exercises;463
11.10;References;465
12;9 Quadratic Programming Models;466
12.1;9.1 Introduction;466
12.2;9.2 Superdiagonalization Algorithm for Checking PD and PSD;467
12.3;9.3 Classification of Quadratic Programs;472
12.4;9.4 Types of Solutions and Optimality Conditions;473
12.5;9.5 What Types of Solutions Can Be Computed Efficiently by Existing Algorithms?;475
12.6;9.6 Some Important Applications of QP;476
12.7;9.7 Unconstrained Quadratic Minimization in ClassicalMathematics;479
12.8;9.8 Summary of Some Existing Algorithms for Constrained QPs;480
12.9;9.9 The Sphere Method for QP;482
12.9.1;9.9.1 Procedure for Getting an Approximate Solution for (9.6);483
12.9.2;9.9.2 Descent Steps;485
12.9.3;9.9.3 The Algorithm;488
12.9.4;9.9.4 The Case when the Matrix D is not Positive Definite;489
12.10;9.10 Commercially Available Software;490
12.11;9.11 Exercises;491
12.12;References;496
13;Epilogue;496
14;Index;499