In-Depth Analysis of Linear Programming In-Depth Analysis of Linear Programming by FP. Vasilyev Moscow State University, Russia and A. Yu. Ivanitskiy Chuvash State University, Cheboksary, Russia Springer-Science+Business Media, B.Y. A c.l.P. Catalogue record for this book is available from the Library of Congress. ISBN 978-90-481-5851-5 ISBN 978-94-015-9759-3 (eBook) DOI 10.1007/978-94-015-9759-3 Translated from the Russian language by Irene Aleksanova. Revised and translated version of Linear Programming by EP. Vasilyev and A. Yu. Ivanitskiy, published in the Russian language by Factorial, Moscow, 1998 Printed on acid-free paper All Rights Reserved © 2001 Springer Science+Business Media Dordrecht Originally published by Kluwer Academic Publishers in 2001. Softcover reprint ofthe hardcover 1st edition 2001 No part of the material protected by this copyright notice may be reproduced or utilized in any form or by any means, e1ectronic or mechanical, including photocopying, recording or by any information storage and retrieval system, without written permission from the copyright owner. Contents Preface Vll Introduction IX Acknow ledgments Xlll 1. SIMPLEX METHOD 1 1.1. Statement of the Problem 1 1.2. Geometrical Interpretation. Extreme Points 10 1.3. The Main Scheme of the Simplex Method 19 1.4. Anticyclin 45 1.5. Search for the Initial Extreme Point. Conditions for Solvability of a Canonical Problem 58 2. THE MAIN THEOREMS OF LINEAR PROGRAMMING 79 2.1. Condition for Solvability of the General Problem 79 2.2. The Duality Theorems 82 2.3. The M-Method 94 2.4. Other Theorems 104 2.5. Evaluation of the Distance Between a Point and a Polyhedron (Hoffman Inequality) 110 3. DUAL SIMPLEX METHOD 119 3.1. Description of the Method 119 3.2. Interpreting the Method for a Dual Problem 135 3.3. Choice of the Initial Point 146 3.4. Dual Interpretation of the Main Simplex Method 161 4. CRITERION OF STABILITY 167 4.1. Examples. Definitions 167 4.2. The Necessary Condition for Stable Solvability 171 v vi CONTENTS 4.3. Criteria of Boundedness of Polyhedrons 174 4.4. Criteria of Stable Solvability 182 4.5. Equivalence of Different Concepts of Stability 192 5. REGULARIZATION METHODS 203 5.1. Stabilization Method 203 5.2. The Method of Residual 218 5.3. The Method of Quasisolutions 222 6. POLYNOMIAL METHODS IN LINEAR PROGRAMMING 229 6.1. Problem Statement 229 6.2. Khachiyan's Method 240 6.3. Karmarkar's Method 249 6.4. Nesterov's Method 266 Notation 295 References 299 Index 311 Preface Along with the traditional material concerning linear programming (the simplex method, the theory of duality, the dual simplex method) the book contains new results of research carried out by the authors. For the first time, the criteria of stability (in the geometrical and algebraic forms) of the general linear programming problem are formulated and proved (see Chapter 4). Hitherto these criteria were established only for special dasses of linear programming problems. In Chapter 5 new regularization methods based on the idea of extension of an admissible set are proposed for solving unstable (ill-posed) linear programming problems. In contrast to the well-known regularization methods, in the methods proposed in this book the initial unstable problem is replaced by a new stable auxiliary problem which is also a linear programming problem and which can be solved by standard finite methods. In addition, proceeding from the results of Chapter 4, we indicate the conditions imposed on the parameters of the auxiliary problem which guarantee its stability, and this circumstance advantageously distinguishes the regularization methods proposed in this book from the existing methods in which the stability of the auxiliary problem is usually only presupposed but is not explicitly investigated. The estimates of the rate of convergence of the proposed regularization methods are obtained, and it is established that on the dass of linear programming problems these estimates are exact with respect to the order of the parameters that appear in them. Chapter 6 is devoted to the so-called polynomial methods of linear programming which date back about 20 years. Today they are develop ing rapidly. It should be pointed out that the traditional material contained in Chapters 1-3 is expounded much simpler than it is done in the majority of books in linear programming and is more convenient for und erstand ing by the beginners. Namely, the fundamental principle of linear pro- Vll Vlll PREFACE gramming, namely, the simplex method, is strictly and completely (the degenerate case inclusive) presented already in the first chapter without resort to the cumbersome theory of polyhedral sets and subtle theorems of duality and is based only on the elementary primary concepts from linear algebra. In Chapter 2 the simplex method is used as a tool for proving mathematical theorems, and this allows us to give a simple expo sition of the theory of duality and prove a number of important theorems of linear programming (the theorem on the existence of a solution, the Farkas theorem, the Stiemke theorem, the Hoffman inequality). On the basis of the developed theory of duality we give a strict exposition of other methods oflinear programming (the M-method, the dual simplex method) and present a dual interpretation of the indicated methods. Introduction Linear programming is a division of the optimization theory which deals with problems of minimization or maximization of linear functions on sets defined by systems of linear equalities or inequalities. Linear pro gramming originated in the 30-40s of the twentieth century under the in fluence of the technical and economic problems and, thanks to the works of J. von Neumann, L.V. Kantorovich, G. Dantzig, and many other well known mathematicians, became an independent branch of mathematics and continues its development today. Many books are devoted to linear programming, and the reader has a right to ask whether the appearance of one more book in this field is justified and what distinguishes it from other similar books. The first distinguishing feature is that we give a strict exposition of the fundamentals of linear programming theory with the use of minimal mathematical apparatus, employing only the most simple concepts of linear algebra such as the matrix, the determinant, the linear dependence and independence of vectors, the rank of a matrix, the inverse matrix. In many textbooks on linear programming (see, e. g., [1, 2]) the authors begin with a very complicated theory of convex polyhedral sets, prove subtle theorems on the separability of these sets, construct the duality theory, and only then pass to the exposition and justification of the main methods of linear programming, starting from the simplex method. This scheme of exposition is fully justified in voluminous detailed monographs and is very convenient for an experienced reader but, in our opinion, is rather difficult for those who make their first steps in the study of linear programming. In our book, the fundamental principle of linear programming, the simplex method, is expounded with a detailed motivation of each element and is strictly justified, including the so-called degenerate case, already in the first chapter. We hope that after studying this chapter the reader IX x INTRODUCTION will have a clear idea that every step of the simplex method, which consists in an exhaustion of a finite number of extreme points of an admissible set with a simultaneous decrease (in minimization problems) or increase (in maximization problems) of values of the objective function at these points, is, in essence, not hing but a transition from one simplex table to another with the use of the Gauss-Jordan elimination with a special choice of the resolving (principal) element. The students are sure to be acquainted with this method from linear algebra. Only after giving a mathematically strict exposition of the fundamen tals of the simplex method we pass to the proof of theorems which serve as the basis of linear programming, namely, the proof of the existen tial theorem, the duality theorem, and some other important facts from the theory of systems of linear inequalities and equations (the Farkas theorem, the Stiemke theorem, the Hoffman inequality), the simplex method itself being used as a tool for proving some of these theorems, which simplifies the proof essentially. This material is given in the sec ond chapter, and, in order to master it, along with the elementary facts from linear algebra mentioned above, the reader must know the basic concepts of analysis. Note that many authors pointed out the possibility of using the simplex method for proving theorems and constructing the theory of linear programming; the examples of realization of this idea are given, for instance, in [2-5]. A strict exposition of other methods of linear programming, such as the M-method (Chapter 2, Sec. 2.3), the dual simplex method (Chapter 3) is given on the basis of the developed duality theory. Another distinctive feature of this book is that, for the first time, the theory of stability of linear programming problems is given so completely. This material is contained in the fourth chapter in which we formulate and prove the criteria of stability of the general linear programming problem. Note that, despite its importance, the problem of stability in linear programming remained, until recently, poorly investigated, and so the results obtained here are relatively new, they were given, in the main, in articles [6-9] and were insufficiently represented in monographs (see [1, 10-14]). Some words are due about one more specific feature of the book. In practice, the search for solutions of unstable linear programming problems is impossible without resort to special regularization methods worked out in the framework of the general theory of unstable (ill-posed) problems [13-32]. This is the first book in which the main regularization methods, namely, the stabilization method, the method of the residual, the method of quasisolutions, based on the idea of extension of a set, are given systematically and in detail [1, 6, 8, 10, 13, 14, 16, 18, 25,