Introduction to Linear Programming: Applications and Extensions

Cover......Page 1
Half Title......Page 2
Series Page......Page 4
Title Page......Page 10
Copyright Page......Page 11
Dedication......Page 12
Preface......Page 14
Table of Contents......Page 18
 1.1 Linear Systems......Page 24
 1.2 Row Echelon Algorithm......Page 27
 1.3 Row Reduction......Page 29
 1.4 Matrix Operations......Page 32
 1.6 Identity and Inverse Matrices......Page 36
 1.7 Linear Independence......Page 39
 1.8 Rearrangement......Page 42
 1.9 Solutions to Linear Systems......Page 43
 Exercises......Page 44
Chapter 2. Introduction to Linear Programming......Page 47
 2.1 Example 2.1: A Production Problem......Page 49
 2.2 Example 2.2: A Diet Problem......Page 57
 2.3 Example 2.3: A Transportation Problem......Page 59
 2.4 Duality......Page 61
 Exercises......Page 67
 3.1 Basic Properties......Page 87
 3.2 Basic Feasible Solutions......Page 92
 3.3 The Fundamental Theorem of Linear Programming......Page 95
 Exercises......Page 96
 4.1 Notation......Page 103
 4.2 Pertinent Algebra......Page 104
 4.3 The Simplex Tableau......Page 105
 4.4 Reduced Costs......Page 106
 4.5 Conditions for Optimality......Page 107
 4.6 The Objective Function......Page 109
 4.7 Simplex Method Pivoting......Page 112
 4.8 When No Optimal Solution Exists......Page 117
 4.9 Multiple Solutions......Page 119
 4.10 Degeneracy......Page 120
 4.11 Phase 1......Page 122
 4.12 The Revised Simplex Method......Page 124
 Exercises......Page 127
Chapter 5. Topics in LP and Extensions......Page 137
 5.1 Examples that Fit into LP Format......Page 138
 5.2 Infeasibility......Page 141
 5.3 Multiperiod Problems......Page 142
 5.4 More Objectives......Page 145
 5.5 Integer Variables......Page 149
 5.6 Transportation Problems......Page 153
 5.7 Introduction to Networks......Page 154
 5.8 Introduction to Dynamic Programming......Page 170
 5.9 Stability and Sensitivity......Page 179
 Exercises......Page 188
 6.1 The Duality Theorem of Linear Programming......Page 225
 6.2 Complementary Slackness......Page 226
 6.3 Kuhn-Tucker Conditions......Page 228
 Exercises......Page 230
Chapter 7. Quadratic Programming......Page 231
 7.1 Quadratic Functions......Page 232
 7.2 Convex Quadratic Functions......Page 240
 7.3 Kuhn–Tucker Conditions for Convex Quadratic Programs......Page 241
 7.4 Linear Complementarity Formulation of Kuhn–Tucker Conditions......Page 242
 7.5 Investment Application......Page 244
 Exercises......Page 247
Chapter 8. Minimizing a Quadratic Function......Page 249
 8.1 Eigenvalue Conditions for Positive (Semi)definiteness......Page 250
 8.2 Newton's Method......Page 251
 8.3 Steepest Descent......Page 253
 8.4 Conjugate Directions......Page 259
 8.5 Conjugate Gradient Method......Page 262
 8.6 Conjugate Gradient Algorithm......Page 266
 Exercises......Page 267
Chapter 9. Network Algorithms......Page 269
 9.2 Project Planning......Page 270
 9.3 Longest Path Algorithm......Page 271
 9.4 Shortest Path Algorithm......Page 274
 9.5 Minimum Spanning Tree Algorithm......Page 278
 9.6 Maximum (Simple) Path Flow Algorithm......Page 279
 9.7 Residual Digraph......Page 281
 9.8 Maximum Flow Algorithm......Page 282
 9.9 Minimum Cost–Maximum Flows: Transportation and Assignment Problems......Page 287
 9.10 Minimum Cost–Maximum Flow Algorithm......Page 292
 Exercises......Page 293
Appendix 1. Forms of LPs......Page 296
Appendix 2. Solutions Supplement for Chapter 2......Page 301
Appendix 3. Solutions Supplement for Chapter 5......Page 338
Reading List......Page 369
Index......Page 371