×

Linear programming. Textbook. (Linejnoe programmirovanie. Uchebnoe posobie). (Russian) Zbl 0578.90049

Moskva: “Nauka”. Glavnaya Redaktsiya Fiziko-Matematicheskoj Literatury. 304 p. R. 0.70 (1981).
The book consists of eight chapters and an appendix. Chapter 1, ”Linear Models”, is introductory; it presents several problems which can be formulated as problems of linear programming, and describes possible types of such problems. Chapter 2, ”Convex Polyhedrons and Linear Inequalities”, presents a detailed study of basic properties of convex polyhedral sets, including fundamental concepts such as that of a separating hyperplane, supporting hyperplane, convex cone and its dual, convex hull of a set, etc. The last section deals with linear inequalities; the results include Farkas’ Lemma and some of its consequences. Chapter 3 contains a detailed study of duality in linear programming, including also the differential properties of the optimum value of the objective function as a function of the availabilities. Chapter 4, ”Applications of Duality Theory”, contains sections dealing with the theory of games, properties of nonnegative matrices, substitution effects in a generalized Leontieff model, a dynamic model of planning, and the maximum principle for discrete linear problems of optimal control. Chapters 5 and 6 are devoted to the simplex method and to the dual simplex method, respectively. Chapter 7, ”Special Problems of Linear Programming”, deals mainly with the transportation problem and with linear programming in integers. The last section, ”Block Programming”, deals with linear programming problems having a special structure and presents the Dantzig-Wolfe decomposition principle. Chapter 8, ”A Method of Regularization of Unstable Linear Programming Problems”, is devoted to the study of stability of linear programming problems; in the last section, a regularization method for unstable linear programming problems is presented. Khachyan’s method of ellipsoids is described in the appendix. Some exercises are given at the ends of Chapters 2, 3, 4 and 5; solutions are provided at the end of the book.
Reviewer: J.Abrham

MSC:

90C05 Linear programming
90-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming
52Bxx Polytopes and polyhedra
91B62 Economic growth models
90C10 Integer programming
91A05 2-person games
91B66 Multisectoral models in economics
90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
90C06 Large-scale problems in mathematical programming
90C31 Sensitivity, stability, parametric optimization