## Linear Programming and Network FlowsLinear Programming and Network Flows, now in its third edition, addresses the problem of minimizing or maximizing a linear function in the presence of linear equality or inequility constraints. This book: * Provides methods for modeling complex problems via effective algorithms on modern computers. * Presents the general theory and characteristics of optimization problems, along with effective solution algorithms. * Explores linear programming (LP) and network flows, employing polynomial-time algorithms and various specializations of the simplex method. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

ONE INTRODUCTION | 1 |

TWO LINEAR ALGEBRA CONVEX ANALYSIS AND POLYHEDRAL SETS | 45 |

THREE THE SIMPLEX METHOD | 91 |

FOUR STARTING SOLUTION AND CONVERGENCE | 151 |

FIVE SPECIAL SIMPLEX IMPLEMENTATIONS AND OPTIMALITY CONDITIONS | 201 |

SIX DUALITY AND SENSITIVITY ANALYSIS | 259 |

SEVEN THE DECOMPOSITION PRINCIPLE | 339 |

EIGHT COMPLEXITY OF THE SIMPLEX ALGORITHM AND POLYNOMIALTIME ALGORITHMS | 393 |

NINE MINIMALCOST NETWORK FLOWS | 453 |

TEN THE TRANSPORTATION AND ASSIGNMENT PROBLEMS | 513 |

ELEVEN THE OUTOFKILTER ALGORITHM | 567 |

TWELVE MAXIMAL FLOW SHORTEST PATH MULTICOMMODITY FLOW AND NETWORK SYNTHESIS PROBLEMS | 607 |

681 | |

733 | |

### Common terms and phrases

arcs artiﬁcial variables assignment problem basic feasible solution basic variables column compute Consider the following constraints convex convex combination convex set corresponding cycle decomposition deﬁned deﬁnition degenerate denote dual feasible dual problem dual variables enter the basis Equation example Exercise extreme directions extreme point feasible region Figure ﬁnd ﬁrst flow following problem foregoing given graph Hence hyperplanes integer iteration kilter leaves the basis linear programming problem linearly independent matrix maximal ﬂow Minimize cx subject minimum negative cost network ﬂow problem nonbasic variables nonnegative Note objective function obtain optimal objective value optimal solution path from node Phase pivot polyhedral set polynomial primal and dual procedure right—hand—side satisﬁes Section shortest path problem Show simplex algorithm simplex method simplex tableau slack variables Solve the following speciﬁed step subject to Ax subproblem Suppose Theorem transportation problem unbounded updated upper bounds vector zero