| 520 |
3 |
|
|a 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, and urban planning fields, among others. The popularity of linear programming can be attributed to many factors including its ability to model large and complex problems, and the ability of the users to solve large problems in a reasonable amount of time by the use of the simplex method and computers. During and after World War II it became evident that planning and coordination among various projects and the efficient utilization of scarce resources were essential. Intensive work by the U. S. Air Force team SCOOP (Scientific Computation of Optimum Programs) began in June 1947. As a result, the simplex method was developed by George B. Dantzig by the end of summer 1947. Interest in linear programming spread quickly among economists, mathematicians, statisticians, and government institutions. In the summer of 1949 a conference on linear programming was held under the sponsorship of the Cowles Commission for Research in Economics. The papers presented at that conference were later collected in 1951 by T. C. Koopmans into the book Activiy Analysis of Production and Allocation. Since the development of the simplex method many people have contributed to the growth of linear programming by developing its mathematical theory, devising efficient computational methods and codes, exploring new applications, and by their use of linear programming as an aiding tool for solving more complex problems, for instance, discrete programs, nonlinear programs, combinatorial problems, stochastic programming problems, and problems of optimal control. This book addresses the subjects of linear programming and network flows. The simplex method represents the backbone of most of the techniques presented in the book. Whenever possible, the simplex method is specialized to take advantage of problem structure. Throughout we have attempted first to present the techniques, to illustrate them by numerical examples, and then to provide detailed mathematical analysis and an argument showing convergence to an optimal solution. Rigorous proofs of the results are given without the theorem proof format. Even though this may bother some readers, we believe that the format and mathematical level adopted in this book will provide an adequate and smooth study for those who wish to learn the techniques and the know-how to use them, and for those who wish to study the algorithms at a more rigorous level. The book can be used both as a reference and as a textbook for advanced undergraduate students and first-year graduate students in the fields of industrial engineering, management, operations research, computer science, mathematics, and other engineering disciplines that deal with the subjects of linear programming and network flows. Even though the book's material requires some mathematical maturity, the only prerequisite is linear algebra. For convenience of the reader, pertinent results from linear algebra and Convex analysis are summarized in Chapter two, In a few places in the book, the notion of differentiation would be helpful. These, however, can be omitted without loss of understanding or continuity. This book can be used in several ways. It can be used in a two-course sequence on linear programming and network flows, in which case all of its material could be easily covered. The book can also be utilized in a one-semester course on linear programming and network flows. The instructor may have to omit some topics at his discretion. The book can also be used as a text for a course on either linear programming or network flows. Following the introductory first chapter and the second chapter on linear algebra and convex analysis, the book is organized into two parts: linear programming and networks flows. The linear programming part consists of Chapters three to seven. In Chapter three the simplex method is developed in detail, and in Chapter four the initiation of the simplex method by the use of artificial variables and the problem of degeneracy are discussed. Chapter five deals with some specializations of the simplex method and the development of optimality criteria in linear programming. In Chapter six we consider the dual problem, develop several computational procedures based on duality, and discuss sensitivity and parametric analysis. Chapter seven introduces the reader to the decomposition principle and to large-scale programming. The part on network flows consists of Chapters eight to eleven. Many of the procedures in this part are presented as a direct simplification of the simplex method. In Chapter eight the transportation problem and the assignment problem are both examined. Chapter nine considers the minimal cost network flow problem from the simplex method point of view. In Chapter ten we present the out-of-kilter algorithm for solving the same problem. Finally, Chapter eleven covers the special topics of the maximal flow problem, the shortest path problem, and the multicommodity minimal cost flow problem. We thank the graduate students at the School of Industrial and Systems Engineering at the Georgia Institute of Technology who suffered through two earlier drafts of this manuscript and who offered many constructive criticisms. We express our appreciation to Gene Ramsay, Dr. Jeff Kennington, Dr. Michael Todd, and Dr. Ron Rardin for their many fine suggestions. We are especially grateful to Süleyman Tüfekçi for preparing the solutions manual and to Carl H. Wohlers for preparing the bibliography. We also thank Dr. Robert N. Lehrer, director of the School of Industrial and Systems Engineering at the Georgia Institute of Technology, for his support during all phases of the preparation of the manuscript. Special thanks are due to Mrs. Alice Jarvis, who typed the first and third drafts of the manuscript; and to Mrs. Carolyn Piersma, Mrs. Amelia Williams, and Miss Kaye Watkins, who typed portions of the second draft. Mokhtar S. Bazaraa, John J. Jarvis.
|