Linear Programming: An Introduction to Finite Improvement Algorithms

Title Page......Page 2
Copyright Page......Page 3
Contents......Page 5
Introduction to the Dover Edition......Page 9
Preface......Page 12
Acknowledgments......Page 16
Chapter 1. Problem Formulation......Page 17
1.1. What is a Linear Programming Problem?......Page 19
1.2. How to Formulate an LP......Page 28
1.3. Advanced Problem Formulation......Page 39
1.4. The Development of Linear Programming......Page 47
Discussion......Page 49
References......Page 50
Chapter 2. Geometric Motivation......Page 51
2.1. A Normal Example......Page 53
2.2. Finite Improvement Algorithms......Page 63
2.3. An Infeasible Example......Page 67
2.4. An Unbounded Example......Page 71
2.5. The Geometry of an LP Having Three Variables......Page 75
Discussion......Page 81
References......Page 82
Chapter 3. Proof Techniques......Page 83
3.1. The Truth of It All......Page 85
3.2. The Forward-Backward Method......Page 87
3.3. Definitions and Mathematical Terminology......Page 94
3.4. Quantifiers I: The Construction Method......Page 99
3.5. Quantifiers II: The Choose Method......Page 102
3.6. Quantifiers III: Induction......Page 106
3.7. Quantifiers IV: Specialization......Page 111
3.8. The Contradiction Method......Page 114
3.9. The Contrapositive Method......Page 118
3.10. Nots of Nots Lead to Knots......Page 122
3.11. Special Proof Techniques......Page 125
3.12. Summary......Page 131
Discussion......Page 136
References......Page 137
Chapter 4. Linear Algebra......Page 138
4.1. Vectors......Page 140
4.2. Matrices......Page 148
4.3. Solving Linear Equations with Matrices I......Page 155
4.4. Solving Linear Equations with Matrices II......Page 166
4.5. Linear Algebra in Linear Programming......Page 177
4.6. Converting an LP to Standard Form......Page 190
Discussion......Page 200
References......Page 201
Chapter 5. The Simplex Algorithm......Page 202
5.1. Basic Feasible Solutions......Page 204
5.2. The Test for Optimality......Page 218
5.3. Determining a Direction of Movement......Page 223
5.4. Determining the Amount of Movement......Page 229
5.5. Moving: The Pivot Operation......Page 239
5.6. A Summary of the Simplex Algorithm......Page 249
5.7. Degeneracy......Page 263
Discussion......Page 276
References......Page 277
Chapter 6. Phase 1......Page 278
6.1. The Phase 1 Problem......Page 280
6.2. Solving the Phase 1 Problem......Page 285
6.3. Initiating Phase 2......Page 293
Discussion......Page 309
References......Page 310
Chapter 7. Computational Implementation......Page 311
7.1. Computational Considerations......Page 313
7.2. The Revised Simplex Algorithm......Page 318
7.3. Advanced Basis Handling Techniques......Page 328
7.4. Matrix Inversion......Page 343
7.5. Special Structure......Page 352
7.6. Computational Improvements in Phase 1......Page 354
Discussion......Page 364
References......Page 366
Chapter 8. Duality Theory......Page 368
8.1. The Dual Linear Programming Problem......Page 370
8.2. Economic Interpretation of the Dual......Page 379
8.3. Weak Duality......Page 383
8.4. Strong Duality......Page 392
8.5. The Dual Simplex Algorithm......Page 401
Discussion......Page 410
References......Page 411
Chapter 9. Sensitivity and Parametric Analysis......Page 412
9.1. Changes in the c Vector......Page 414
9.2. Changes in the b Vector......Page 427
9.3. Changes in the A Matrix......Page 436
9.4. The Addition of a New Variable or Constraint......Page 440
Discussion......Page 447
References......Page 448
Chapter 10. Techniques for Handling Bound Constraints......Page 449
10.1. Finite Bounds......Page 451
10.2. Handling Nonbasic Values Between Their Bounds......Page 461
10.3. Generalized Upper Bounding......Page 471
Discussion......Page 485
References......Page 486
Chapter 11. Network Flow Problems......Page 487
11.1 The Network LP and Its Properties......Page 489
11.2. The Simplex Algorithm for Network Flow Problems......Page 494
11.3. The Phase 1 Procedure for Network Flow Problems......Page 508
Discussion......Page 516
References......Page 518
Appendix A. The Tableau Method......Page 520
Appendix B. How Efficiently Can We Solve LP Problems?......Page 531
Appendix C. Spreadsheet Modeling Using Excel......Page 548
Index......Page 577