Linear programming: mathematics, theory and algorithms
The purpose of this book is to present to the students the salient features of the theory and computational aspects of linear programming. Linear programming is one of the most versatile and powerful mathematical programming techniques that can be employed for efficiently solving a stylized class of decision problems of the form \[ \max f(X)=C'X\quad\text{subject to } AX\leq b,\quad X\geq 0, \] where \(C\), \(X\in \mathbb{R}^p\), \(b\in\mathbb{R}^m\), \(A\) is a matrix of order \((m\times n)\), and a prime denotes transposition. The book has 14 chapters: Chapter 1: Introduction and overview; Chapter 2: Preliminary mathematics; Chapter 3: Introduction to linear programming; Chapter 4: Duality theory; Chapter 5: The theory of linear programming; Chapter 6: Duality theory revisited; Chapter 7: Computational aspects of linear programming; Chapter 8: One-phase, two-phase, and composite methods of linear programming; Chapter 9: Computational aspects of linear programming: selected transformation; Chapter 10: The dual simplex, primal-dual, and complementary pivot methods; Chapter 11: Postoptimality analysis I; Chapter 12: Postoptimality analysis II; Chapter 13: Interior point methods; Chapter 14: Interior point algorithms for solving linear complementarity problems. The bibliography contains 155 items. Chapter 2 reviews the mathematical tools needed to study linear programming. Chapter 3 presents the canonical and standard forms of a linear programming problem and the concepts of feasibility and optimality. In chapter 4, the fundamental theorems of linear programming, namely the weak duality theorem, the strong duality theorem, the existence theorem, and weak and strong complementary slackness theorems are discussed. Chapter 5 presents the primal simplex method for solving linear programming problems. In chapter 6, duality theory revisited (the geometry of duality and optimality and Lagrangean saddle-points) is discussed. Chapter 7 deals with the computational aspepts of linear programming. Chapter 8 presents the one-phase, two-phase, and composite methods of linear programming. Chapter 9 presents an assortment of specialized transformations for solving problems involving departures from the general form. Chapter 10 deals with three important variants of the simplex method, namely the dual simplex method, primal-dual method and complementary pivot method. Chapters 11 and 12 deal with the postoptimality analysis: sensitivity analysis (chapter 11) and parametric analysis (chapter 12). Chapter 13 presents interior point methods for solving linear programming problems. Chapter 14 extends some interior point techniques to solution of linear complementarily problems. The book is written for students in the areas of mathematics, economics, engineering and management science and can be recommended. It is carefully written and is a very useful source of information for all students and researchers that work in the field of optimization theory.
scientific article; zbMATH DE number 920117
scientific article