c10-8 (Numerical Recipes in C), страница 2

Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).addanequnt (iainstral cotionx110.8 Linear Programming and the Simplex Method433Simplex Method for a Restricted Normal FormA linear programming problem is said to be in normal form if it has noconstraints in the form (10.8.3) or (10.8.4), but rather only equality constraints of theform (10.8.5) and nonnegativity constraints of the form (10.8.2).Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.

Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).force the feasible region onto hyperplanes of smaller dimension, while inequalitiessimply divide the then-feasible region into allowed and nonallowed pieces.When all the constraints are imposed, either we are left with some feasibleregion or else there are no feasible vectors. Since the feasible region is bounded byhyperplanes, it is geometrically a kind of convex polyhedron or simplex (cf.

§10.4).If there is a feasible region, can the optimal feasible vector be somewhere in itsinterior, away from the boundaries? No, because the objective function is linear.This means that it always has a nonzero vector gradient. This, in turn, means thatwe could always increase the objective function by running up the gradient untilwe hit a boundary wall.The boundary of any geometrical region has one less dimension than its interior.Therefore, we can now run up the gradient projected into the boundary wall until wereach an edge of that wall. We can then run up that edge, and so on, down throughwhatever number of dimensions, until we finally arrive at a point, a vertex of theoriginal simplex. Since this point has all N of its coordinates defined, it must bethe solution of N simultaneous equalities drawn from the original set of equalitiesand inequalities (10.8.2)–(10.8.5).Points that are feasible vectors and that satisfy N of the original constraintsas equalities, are termed feasible basic vectors.

If N > M , then a feasible basicvector has at least N − M of its components equal to zero, since at least that manyof the constraints (10.8.2) will be needed to make up the total of N . Put the otherway, at most M components of a feasible basic vector are nonzero. In the example(10.8.6)–(10.8.7), you can check that the solution as given satisfies as equalities thelast three constraints of (10.8.7) and the constraint x1 ≥ 0, for the required total of 4.Put together the two preceding paragraphs and you have the FundamentalTheorem of Linear Optimization: If an optimal feasible vector exists, then there is afeasible basic vector that is optimal. (Didn’t we warn you about the terminologicalthicket?)The importance of the fundamental theorem is that it reduces the optimizationproblem to a “combinatorial” problem, that of determining which N constraints(out of the M + N constraints in 10.8.2–10.8.5) should be satisfied by the optimalfeasible vector. We have only to keep trying different combinations, and computingthe objective function for each trial, until we find the best.Doing this blindly would take halfway to forever.

The simplex method, firstpublished by Dantzig in 1948 (see [2]), is a way of organizing the procedure so that(i) a series of combinations is tried for which the objective function increases at eachstep, and (ii) the optimal feasible vector is reached after a number of iterations thatis almost always no larger than of order M or N , whichever is larger. An interestingmathematical sidelight is that this second property, although known empirically eversince the simplex method was devised, was not proved to be true until the 1982 workof Stephen Smale.

(For a contemporary account, see [3].)434Chapter 10.Minimization or Maximization of FunctionsMaximize z = 2x2 − 4x3(10.8.8)with x1 , x2 , x3 , and x4 all nonnegative and also withx1 = 2 − 6x2 + x3(10.8.9)x4 = 8 + 3x2 − 4x3This example has N = 4, M = 2; the left-hand variables are x1 and x4 ; theright-hand variables are x2 and x3 . The objective function (10.8.8) is written soas to depend only on right-hand variables; note, however, that this is not an actualrestriction on objective functions in restricted normal form, since any left-handvariables appearing in the objective function could be eliminated algebraically byuse of (10.8.9) or its analogs.For any problem in restricted normal form, we can instantly read off a feasiblebasic vector (although not necessarily the optimal feasible basic vector).

Simply setall right-hand variables equal to zero, and equation (10.8.9) then gives the values ofthe left-hand variables for which the constraints are satisfied. The idea of the simplexmethod is to proceed by a series of exchanges. In each exchange, a right-handvariable and a left-hand variable change places. At each stage we maintain a problemin restricted normal form that is equivalent to the original problem.It is notationally convenient to record the information content of equations(10.8.8) and (10.8.9) in a so-called tableau, as follows:zx1x4028x2x32−63−41−4(10.8.10)You should study (10.8.10) to be sure that you understand where each entry comesfrom, and how to translate back and forth between the tableau and equation formatsof a problem in restricted normal form.Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.

Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).For our purposes it will be useful to consider an even more restricted set ofcases, with this additional property: Each equality constraint of the form (10.8.5)must have at least one variable that has a positive coefficient and that appearsuniquely in that one constraint only. We can then choose one such variable in eachconstraint equation, and solve that constraint equation for it.

The variables thuschosen are called left-hand variables or basic variables, and there are exactly M(= m3 ) of them. The remaining N − M variables are called right-hand variables ornonbasic variables. Obviously this restricted normal form can be achieved only inthe case M ≤ N , so that is the case that we will consider.You may be thinking that our restricted normal form is so specialized thatit is unlikely to include the linear programming problem that you wish to solve.Not at all! We will presently show how any linear programming problem can betransformed into restricted normal form.

Therefore bear with us and learn how toapply the simplex method to a restricted normal form.Here is an example of a problem in restricted normal form:43510.8 Linear Programming and the Simplex Methodx1 = 2 − 6x2 + x3→x2 =13− 16 x1 + 16 x3(10.8.11)We then substitute this into the old z-row,z = 2x2 − 4x3 = 213− 16 x1 + 16 x3 − 4x3 =23− 13 x1 −11x3 3(10.8.12)and into all other left-variable rows, in this case only x4 ,x4 = 8 + 313− 16 x1 + 16 x3 − 4x3 = 9 − 12 x1 − 72 x3(10.8.13)Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.

Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).The first step in the simplex method is to examine the top row of the tableau,which we will call the “z-row.” Look at the entries in columns labeled by right-handvariables (we will call these “right-columns”).

We want to imagine in turn the effectof increasing each right-hand variable from its present value of zero, while leavingall the other right-hand variables at zero. Will the objective function increase ordecrease? The answer is given by the sign of the entry in the z-row. Since we wantto increase the objective function, only right columns having positive z-row entriesare of interest.

In (10.8.10) there is only one such column, whose z-row entry is 2.The second step is to examine the column entries below each z-row entrythat was selected by step one. We want to ask how much we can increase theright-hand variable before one of the left-hand variables is driven negative, which isnot allowed. If the tableau element at the intersection of the right-hand column andthe left-hand variable’s row is positive, then it poses no restriction: the correspondingleft-hand variable will just be driven more and more positive.