Linear programming and network flows, Fourth Edition

Title Page......Page 5
CONTENTS......Page 9
Preface......Page 13
1.1 The Linear Programming Problem......Page 17
1.2 Linear Programming Modeling and Examples......Page 23
1.3 Geometric Solution......Page 34
1.4 The Requirement Space......Page 38
1.5 Notation......Page 43
Exercises......Page 45
Notes and References......Page 58
2.1 Vectors......Page 61
2.2 Matrices......Page 67
2.3 Simultaneous Linear Equations......Page 77
2.4 Convex Sets and Convex Functions......Page 80
2.5 Polyhedral Sets and Polyhedral Cones......Page 86
2.6 Extreme Points, Faces, Directions, and Extreme Directions of Polyhedral Sets: Geometric Insights......Page 87
2.7 Representation of Polyhedral Sets......Page 91
Exercises......Page 98
Notes and References......Page 106
3.1 Extreme Points and Optimality......Page 107
3.2 Basic Feasible Solutions......Page 110
3.3 Key to the Simplex Method......Page 119
3.4 Geometric Motivation of the Simplex Method......Page 120
3.5 Algebra of the Simplex Method......Page 124
3.6 Termination: Optimality and Unboundedness......Page 130
3.7 The Simplex Method......Page 136
3.8 The Simplex Method in Tableau Format......Page 141
3.9 Block Pivoting......Page 150
Exercises......Page 151
Notes and References......Page 164
4.1 The Initial Basic Feasible Solution......Page 167
4.2 The Two–Phase Method......Page 170
4.3 The Big–M Method......Page 181
4.4 How Big Should Big–M Be?......Page 188
4.5 The Single Artificial Variable Technique......Page 189
4.6 Degeneracy, Cycling, and Stalling......Page 191
4.7 Validation of Cycling Prevention Rules......Page 198
Exercises......Page 203
Notes and References......Page 214
5.1 The Revised Simplex Method......Page 217
5.2 The Simplex Method for Bounded Variables......Page 236
5.3 Farkas\' Lemma via the Simplex Method......Page 250
5.4 The Karush–Kuhn–Tucker Optimality Conditions......Page 253
Exercises......Page 259
Notes and References......Page 272
6.1 Formulation of the Dual Problem......Page 275
6.2 Primal–Dual Relationships......Page 280
6.3 Economic Interpretation of the Dual......Page 286
6.4 The Dual Simplex Method......Page 293
6.5 The Primal–Dual Method......Page 301
6.6 Finding an Initial Dual Feasible Solution: The Artificial Constraint Technique......Page 309
6.7 Sensitivity Analysis......Page 311
6.8 Parametric Analysis......Page 328
Exercises......Page 335
Notes and References......Page 352
SEVEN: THE DECOMPOSITION PRINCIPLE......Page 355
7.1 The Decomposition Algorithm......Page 356
7.2 Numerical Example......Page 361
7.3 Getting Started......Page 369
7.4 The Case of an Unbounded Region X......Page 370
7.5 Block Diagonal or Angular Structure......Page 377
7.6 Duality and Relationships with other Decomposition Procedures......Page 387
Exercises......Page 392
Notes and References......Page 407
8.1 Polynomial Complexity Issues......Page 409
8.2 Computational Complexity of the Simplex Algorithm......Page 413
8.3 Khachian\'s Ellipsoid Algorithm......Page 417
8.4 Karmarkar\'s Projective Algorithm......Page 418
8.5 Analysis of Karmarkar\'s Algorithm: Convergence, Complexity, Sliding Objective Method, and Basic Optimal Solutions......Page 433
8.6 Affine Scaling, Primal–Dual Path Following, and Predictor–Corrector Variants of Interior Point Methods......Page 444
Exercises......Page 451
Notes and References......Page 464
9.1 The Minimal Cost Network Flow Problem......Page 469
9.2 Some Basic Definitions and Terminology from Graph Theory......Page 471
9.3 Properties of the A Matrix......Page 475
9.4 Representation of a Nonbasic Vector in Terms of the Basic Vectors......Page 481
9.5 The Simplex Method for Network Flow Problems......Page 482
9.7 Finding an Initial Basic Feasible Solution......Page 491
9.8 Network Flows with Lower and Upper Bounds......Page 494
9.9 The Simplex Tableau Associated with a Network Flow Problem......Page 497
9.10 List Structures for Implementing the Network Simplex Algorithm......Page 498
9.11 Degeneracy, Cycling, and Stalling......Page 504
9.12 Generalized Network Problems......Page 510
Exercises......Page 513
Notes and References......Page 527
10.1 Definition of the Transportation Problem......Page 529
10.2 Properties of the A Matrix......Page 532
10.3 Representation of a Nonbasic Vector in Terms of the Basic Vectors......Page 536
10.4 The Simplex Method for Transportation Problems......Page 538
10.5 Illustrative Examples and a Note on Degeneracy......Page 544
10.7 The Assignment Problem: (Kuhn\'s) Hungarian Algorithm......Page 551
10.8 Alternating Path Basis Algorithm for Assignment Problems......Page 560
10.9 A Polynomial–Time Successive Shortest Path Approach for Assignment Problems......Page 562
10.10 The Transshipment Problem......Page 567
Exercises......Page 568
Notes and References......Page 580
11.1 The Out–of–Kilter Formulation of a Minimal Cost Network Flow Problem......Page 583
11.2 Strategy of the Out–of–Kilter Algorithm......Page 589
11.3 Summary of the Out–of–Kilter Algorithm......Page 602
11.4 An Example of the Out–of–Kilter Algorithm......Page 603
11.5 A Labeling Procedure for the Out–of–Kilter Algorithm......Page 605
11.6 Insight into Changes in Primal and Dual Function Values......Page 607
11.7 Relaxation Algorithms......Page 609
Exercises......Page 611
Notes and References......Page 621
12.1 The Maximal Flow Problem......Page 623
12.2 The Shortest Path Problem......Page 635
12.3 Polynomial–Time Shortest Path Algorithms for Networks Having Arbitrary Costs......Page 651
12.4 Multicommodity Flows......Page 655
12.5 Characterization of a Basis for the Multicommodity Minimal–Cost Flow Problem......Page 665
12.6 Synthesis of Multiterminal Flow Networks......Page 670
Exercises......Page 679
Notes and References......Page 694
BIBLIOGRAPHY......Page 697
INDEX......Page 749