Linear programming and network flows /
Preface, I linear Programming deals with the problem of minimizing or maximizing a linear function in the presence of linear finequalities. Since the development of the simplex method by George B. Dantzig in 1947, linear programming has been extensively used in the military, industrial, governmental...
| Formato: | Libro |
|---|---|
| Lenguaje: | Spanish |
| Publicado: |
United States of America :
Jhon Wiley & Sons,
©1977
|
Tabla de Contenidos:
- 1. Introduction. 1.1 The linear programming problem.
- 1.2 Examples of linear problems.
- 1.3 Geometric solution.
- 1.4 The requirement space.
- 1.5 Notation.
- Exercises.
- Notes and references.
- 2. Results from linear algebra and convex analysis. 2.1 Vectors.
- 2.2 Matrices.
- 2.3 Simultaneous linear equations.
- 2.4 Convex sets and convex functions.
- 2.5 Polyhedral sets and polyhedral cones.
- 2.6 Representation of polyhedral sets.
- 2.7 Farka´s theorem.
- Exercises.
- Notes and references.
- 3. The simplex method. 3.1 Extreme points and optimality.
- 3.2 Basic feasible solutions.
- 3.3 Improving a basic feasible solution.
- 3.4 Termination: Optimality and Unboundedness.
- 3.5 The simplex method.
- 3.6 The simplex method in tableau format.
- 3.7 Block pivoting.
- Exercises.
- Notes and References.
- 4. Starting solution and convergence. 4.1 The initial basic feasible solution.
- 4.2 The two-phase method.
- 4.3 The big-M method.
- 4.4 The single artificial variable technique.
- 4.5 Degeneracy and cycling.
- 4.6 Lexicographic validation of cycling prevention.
- Exercises.
- Notes and references.
- 5. Special simplex forms anf ofimality conditions. 5.1 The revised simplex method.
- 5.2 The simplex method for bounded variables.
- 5.3 The Kuhn-Tucker conditions and the simplex method.
- Exercises.
- Notes and references.
- 6. Duality and sensitivity. 6.1 Formulation.
- 6.2 Primal-dual relationships.
- 6.3. Economic interpretation of the dual.
- 6.4 The dual simplex method.
- 6.5 The primal-dual method.
- 6.6 Finding an initial dual feasible solution: The artificial Constraint technique.
- 6.7 Sensivity analysis.
- 6.8 Parametric analysis.
- Exercises.
- Notes and references.
- 7. The decomposition principle. 7.1 The decomposition algorithm.
- 7.2 Numerical example.
- 7.3 Gettong started.
- 7.4 The case of unbounded region X.
- 7.5 Block diagonal structure.
- Exercises.
- Notes and references.
- 8. The transportation and assignment problems. 8.1 Definition of the transportation problem.
- 8.2 Properties of the A matrix.
- 8.3 Representation of a Nonbasic vector in terms of the basic vectors.
- 8.4 The simplex method for transportation problems.
- 8.5 An example of the transportation algorithm.
- 8.6 Degeneracy in the transportation problem.
- 8.7 The simplex tableau associated with a transportation tableau.
- 8.8 The assigment problem.
- 8.9 The transshipment problem.
- Exercises.
- Notes and references.
- 9. Minimal cost network flows. 9.1 The minimal cost network flow problem.
- 9.2 Properties of the A matrix.
- 9.3 Representation of a nonbasic vector in terms of the basic vectors.
- 9.4 The simplex method for network flow problems.
- 9.5 An example of the the network simplex method.
- 9.6 Finding an initial basic reasible solution.
- 9.7 Network flows with lower and upper bounds.
- 9.8 The simplex tableau associated with a network flow problem.
- Exercises.
- Notes and references.
- 10. The out-of-kilter algorithm. 10.1 The out-of-kilter formulation of a minimal cost network flow problem.
- 10.2 Strategy of the out-of-kilter algortihm.
- 10.3 Summary of the out-of-kilter algorithm.
- 10.4 An example of the out-of-kilter algortihm.
- Exercises.
- Notes and references.
- 11. Maximal flow, shortest path, and multicommodity flow problems. 11.1 The maximal flow problem.
- 11.2 The shortest path problem.
- 11.3 Multicommodity flows.
- 11.4 Characterization of a basic for the multicommodity minimal caost flow problem.
- Exercises.
- Notes and references.
- Appendix: Proof of the representation theorem.