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.
(1, 3) in our example. Both these solutions are feasible, and both yield an objective value of 10. Hence, the weak duality theorem says that these solutions are optimal. 4. The Strong Duality Theorem The fact that for linear programming there is never a gap between the primal and the dual optimal objective values is usually referred to as the Strong Duality Theorem: THEOREM 5.2. If the primal problem has an optimal solution, x∗ = (x∗1 , x∗2 , . . . , x∗n ), then the dual also has an optimal
this problem involves a production facility that can take a variety of raw materials (enumerated i = 1, 2, . . . , m) and turn them into a variety of final products (enumerated j = 1, 2, . . . , n). We assume as before that the current market value of a unit of the ith raw material is ρi , that the current market price for a unit of the jth product is σj , that producing one unit of product j requires aij units of raw material i, and that at the current moment in time the facility has on hand bi
forward and, after the first couple, a clear pattern should emerge which will make the subsequent pivots easy. Clearly indicate the range of μ values for which each dictionary is optimal. Notes Parametric analysis has its roots in Gass and Saaty (1955). G.B. Dantzig’s classic book (Dantzig 1963) describes the self-dual simplex method under the name of the self-dual parametric simplex method. It is a special case of “Lemke’s algorithm” for the linear complementarity problem (Lemke 1965) (see
explain, let us consider an example: ⎡ ⎤ 2 4 −2 ⎢ 3 1 ⎥ 1 ⎢ ⎥ ⎢ −1 −2 ⎥ B = ⎢ −1 ⎥. ⎣ −1 −6 ⎦ 1 4 (Note that, to emphasize the importance of sparsity, zero entries are simply left blank.) In Gaussian elimination, one begins by subtracting appropriate multiples of the first row from each subsequent row to get zeros in the first column below the diagonal. For our specific example, we subtract 3/2 times the first row from the second row and we subtract −1/2 times the first row from the third row.
constraints; that is, there are at most m + 1 variables that are nonzero. Hence, this basic feasible solution corresponds to a convex combination of just m + 1 of the original n points. (See Exercise 10.5.) It is easy to see that the number m + 1 is the best possible. For example, the point (1/(m + 1), 1/(m + 1), . . . , 1/(m + 1)) in Rm belongs to the convex hull of the m + 1 points e1 , e2 , . . . , em , 0 but is not a convex combination of any subset of them. 3. The Separation Theorem We shall