Linear Programming: Foundations and Extensions (International Series in Operations Research & Management Science)
Robert J Vanderbei
Format: PDF / Kindle (mobi) / ePub
This Third Edition introduces the latest theory and applications in optimization. It emphasizes constrained optimization, beginning with linear programming and then proceeding to convex analysis, network flows, integer programming, quadratic programming, and convex optimization. You’ll discover a host of practical business applications as well as non-business applications. With its focus on solving practical problems, the book features free C programs to implement the major algorithms covered. The book’s accompanying website includes the C programs, JAVA tools, and new online instructional tools and exercises.
and Firdevs Ulus for carefully reviewing and commenting on this new material. Princeton, NJ, USA Robert J. Vanderbei xv Contents Preface vii Preface to 2nd Edition xi Preface to 3rd Edition xiii Preface to 4th Edition xv Part 1. Basic Theory: The Simplex Method and Duality 1 Chapter 1. Introduction 1. Managing a Production Facility 2. The Linear Programming Problem Exercises Notes 3 3 5 7 9 Chapter 2. The Simplex Method 1. An Example 2. The Simplex Method 3. Initialization 4.
SIMPLEX METHOD IN MATRIX NOTATION Hence, the largest t for which all of the inequalities hold is given by t= max i∈B Δxi x∗i −1 . As always, the correct convention for 0/0 is to set such ratios to zero. Also, if the maximum is less than or equal to zero, we can stop here—the primal is unbounded. Step 5. Select Leaving Variable. The leaving variable is chosen as any variable xi , i ∈ B, for which the maximum in the calculation of t is obtained. Step 6. Compute Dual Step Direction ΔzN .
c , where the notation y + denotes the componentwise positive part of y, etc. This problem is an example from the class of problems called piecewise linear programs. Usually, piecewise linear programs are solved by converting them into linear programs. Here, however, we wish to go in the other direction. We shall present an algorithm for (9.4) that will serve as an algorithm for (9.2). We will call this algorithm the dual simplex method for problems in general form. To economize on the
j=1 tj = 1. If any of the tj ’s vanish, then z is really just a convex combination of two points and so belongs to C. Hence, suppose that each of the tj ’s is strictly positive. Rewrite z as follows: t1 t2 z1 + z2 + t 3 z3 1 − t3 1 − t3 t1 t2 = (1 − t3 ) z1 + z2 + t 3 z3 . t1 + t2 t1 + t2 Since C contains all convex combinations of pairs of points, it follows that t1 t2 z1 + z2 ∈ C. t1 + t2 t1 + t2 z = (1 − t3 ) 1 2 Now, since z is a convex combination of the two points t1t+t z1 + t1t+t z2 and
not constrained to be nonnegative. Therefore, there is no reason for it to be nonbasic. Let us do an arbitrary pivot with v as the entering variable and any basic variable as the leaving variable (well, not exactly any—we must make sure that it causes no division by 0, so therefore x3 is not a candidate). Picking x4 to leave, we get ξ = −2 + 2x1 + 3x2 − x4 v = −2 + 2x1 + 3x2 − x4 x5 = 6 − 9x1 − 7x2 + x4 x6 = 2 + 3x1 − 9x2 + x4 x3 = 1 − x1 − x2 . 4. POKER 157 Since v is free of sign