## Linear Programming"This comprehensive treatment of the fundamental ideas and principles of linear programming covers basic theory, selected applications, network flow problems, and advanced techniques. Using specific examples to illuminate practical and theoretical aspects of the subject, the author clearly reveals the structures of fully detailed proofs. The presentation is geared toward modern efficient implementations of the simplex method and appropriate data structures for network flow problems. Completely self-contained, it develops even elementary facts on linear equations and matrices from the beginning."--Back cover. |

### Contents

Introduction | 3 |

How the Simplex Method Works | 13 |

Pitfalls and How to Avoid Them | 27 |

How Fast Is the Simplex Method? | 45 |

The Duality Theorem | 54 |

Gaussian Elimination and Matrices | 71 |

The Revised Simplex Method | 97 |

Solutions by the Simplex Method | 118 |

Approximating Data by Linear Functions | 213 |

Matrix Games | 228 |

Systems of Linear Inequalities | 240 |

Finding All Vertices of a Polyhedron | 271 |

The Network Simplex Method | 291 |

Applications of the Network Simplex Method | 320 |

UpperBounded Transshipment Problems | 353 |

Maximum Flows Through Networks | 367 |

Theorems on Duality and Infeasibility | 137 |

Sensitivity Analysis | 148 |

Selected Applications | 169 |

Efficient Allocation of Scarce Resources | 171 |

Scheduling Production and Inventory | 188 |

The CuttingStock Problem | 195 |

The PrimalDual Method | 390 |

Updating a Triangular Factorization of the Basis | 405 |

The DantzigWolfe Decomposition Principle | 425 |

The Ellipsoid Method | 443 |

Solutions to Selected Problems | 465 |

### Other editions - View all

### Common terms and phrases

algorithm amounts applied arc ij basic feasible solution basis begin called changes Chapter choice choose column components computing consider consists constraints corresponding course defined demand described dictionary direction dual easy elimination entering entries equals equations example fact feasible solution Figure finals flow function Hence holds illustration increase inequalities initial instance integer iteration least leaving linear programming LP problems matrix maximize subject minimize node nonbasic nonzero Note objective observe obtain optimal optimal solution original particular path pivot positive precisely present problem procedure production profit proof Prove referred remaining replace represents resulting revised simplex method rule satisfies side simplex method solving Solving the system Step strategy Theorem tree triangular units update upper bound variables vector x₁ zero