Only a little over a decade has passed since George Dantzig formulated the general linear programming problem and developed the simplex method for its solution. In this period, the growth of interest in, and the use of, linear programming has been remarkable. Rarely indeed has a new mathematical technique found such a wide range of practical applications, and simultaneously received so thorough a theoretical development in such a short period of time. The extensive interest in linear programming which has arisen has brought with it the need for texts at different levels of difficulty, suitable for readers of widely varying backgrounds and mathematical maturity. The present work is intended for those who desire to study the subject in some depth and detail. It attempts to provide a fairly rigorous and complete development of the theoretical and computational aspects of linear programming as well as a discussion of a number of practical applications.
Chapter 1 introduces the general linear programming problem and exhibits a series of graphical examples. Chapter 2 covers the mathematical background needed. In Chapter 3 the fundamental theoretical results required for the simplex method are derived. Chapter 4 provides a detailed development of the computational procedure of the simplex method. The two-phase technique is introduced in Chapter 5, which also includes a discussion of the solutions and requirements spaces. Chapter 6 presents Charnes' perturbation technique and the generalized simplex method for resolving the degeneracy problem. The revised simplex method is covered in Chapter 7. Chapter 8 is devoted to duality; included in this chapter are the dual simplex algorithm and the primal-dual algorithm. The solution of transportation problems is the concern of Chapter 9. A novel approach is used to derive the transportation algorithm from the simplex method. Generalized transportation problems are also covered in this chapter. Chapter 10 discusses network flow problems, the primal-dual algorithm for transportation problems, assignment problems, and the transhipment problem. Chapter 11 treats a number of special topics, such as sensitivity analysis, treatment of upper bounds for the general linear programming problem, the primal-dual algorithm for capacitated transportation problems, the decomposition principle, and the relationships between linear programming and zero-sum two-person games. The application of linear programming to practical problems in industry is discussed in Chapter 12, and applications to economic theory are considered in Chapter 13.
The level of presentation in this book assumes that the reader has a familiarity with certain elementary topics in linear algebra (including . . .