No label defined (Q3694971)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3920182
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3920182

      Statements

      0 references
      0 references
      1985
      0 references
      FORTRAN codes
      0 references
      implementation
      0 references
      text book
      0 references
      elementary level
      0 references
      Simplex Method
      0 references
      Parametric Linear Programming
      0 references
      In the words of the authors ''...(the) presentation is new in that it is based on a direct generalization of this geometric notion.'' The geometric notion is: if an extreme point of the feasible region is not optimal, then we can move along an edge of the feasible region to an adjacent extreme point with a better value of the objective function. The presentation of the authors is refreshing from several points of view. The orientation of the material is toward a realistic implementation of the algorithms. It does not rely on the usual hand manipulation of simplex tableaus. In fact, the simplex method is not discussed in detail until Chapter 4 and then it is introduced in the revised simplex form. The text provides FORTRAN codes for all of the algorithms. During the period of the review, I did not have time to test the codes. The book is suitable as an introduction to linear programming at either the undergraduate or graduate level. It requires knowledge of linear and matrix algebra, and relies almost exclusively on matrix algebra notation for the presentation of results. On the negative side, the chapter on Applications could have been done in a more complete fashion. While it presents some interesting applications, it does not give an idea of the wide range of problems or the size of problems that can be handled. The codes are given in FORTRAN 77; particularly in the microcomputing area, PASCAL may have been more appropriate. The more sophisticated the student, the more useful the presentation. Each chapter concludes with plenty of exercises, ranging from computational to theoretical. The book focuses on LP and does not include closely related topics such as networks and decomposition. The text is certainly recommended for anyone wanting to study linear programming from a realistic implementation point of view. The contents of the book are: Ch. 1: Geometric Examples - An introduction to the geometric interpretation of extreme points, cones, edges, and how these come together in solving linear programs. Ch. 2: Basic LP Solution Algorithms - The basic algorithm is defined. It is based on the result that a point \(x^*\) is optimal if -c lies in a certain cone. Ch. 3: Theory - Formulates this condition for a general problem and proves that it is necessary and sufficient for optimality. This chapter also introduces duality, alternate optimal solutions, and sensitivity analysis. Ch. 4: The Simplex Method - Introduces the simplex method of linear programming using the revised simplex form. This introduction incorporates Bland's anti-cycling rules. Also the authors show the equivalence of the algorithms of Ch. 2 and 3 with the revised simplex algorithm. The chapter concludes with a section which compares the computational aspects of these approaches. Ch. 5: Parametric Linear Programming - This chapter presents the parametric program ''minimize \(\{(c+tq)^ Tx:\) \(Ax\leq (b+tp)\}''\) from the point of view of the approach of Ch. 2. Ch. 6: Dual Methods - Presents the dual approach, including dual simplex. Ch. 7: Upper Bounding Techniques - Presents a modified revised simplex method for problems with bounded variables and with generalized upper bounds. Ch. 8: Applications - Presents five applications of linear programming: the diet problem, engineering design, pattern recognition, graduation of actuarial data, and input-output models. Appendices: The text concludes with FORTRAN 77 listings of all of the algorithms presented in the text.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references