10.8 Linear Programming and the Simplex Method 433 force the feasible region onto hyperplanes of smaller dimension,while inequalities simply divide the then-feasible region into allowed and nonallowed pieces. When all the constraints are imposed,either we are left with some feasible region or else there are no feasible vectors.Since the feasible region is bounded by hyperplanes,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 its interior,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 that we could always increase the objective function by running up the gradient until we 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 we reach an edge of that wall.We can then run up that edge,and so on,down through whatever number of dimensions,until we finally arrive at a point,a vertex of the original simplex.Since this point has all N of its coordinates defined,it must be the solution of N simultaneous egualities drawn from the original set of equalities and inequalities (10.8.2)-(10.8.5). Points that are feasible vectors and that satisfy N of the original constraints as equalities,are termed feasible basic vectors.If N M,then a feasible basic 9 vector has at least N-M of its components equal to zero,since at least that many of the constraints(10.8.2)will be needed to make up the total of N.Put the other way,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 the last three constraints of(10.8.7)and the constraint>0,for the required total of 4. 三色%D9 9 Put together the two preceding paragraphs and you have the Fundamental OF SCIENTIFIC Theorem of Linear Optimization:If an optimal feasible vector exists,then there is a feasible basic vector that is optimal.(Didn't we warn you about the terminological 6 thicket?) The importance of the fundamental theorem is that it reduces the optimization problem 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 optimal feasible vector.We have only to keep trying different combinations,and computing the objective function for each trial,until we find the best. Numerica 10621 Doing this blindly would take halfway to forever.The simplex method,first 43106 published by Dantzig in 1948(see [21),is a way of organizing the procedure so that (i)a series of combinations is tried for which the objective function increases at each Recipes step,and(ii)the optimal feasible vector is reached after a number of iterations that is almost always no larger than of order M or N,whichever is larger.An interesting Software. g mathematical sidelight is that this second property,although known empirically ever since the simplex method was devised,was not proved to be true until the 1982 work of Stephen Smale.(For a contemporary account,see [3].) Simplex Method for a Restricted Normal Form A linear programming problem is said to be in normal form if it has no constraints in the form(10.8.3)or(10.8.4),but rather only equality constraints of the form (10.8.5)and nonnegativity constraints of the form (10.8.2).10.8 Linear Programming and the Simplex Method 433 Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machine￾readable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). force the feasible region onto hyperplanes of smaller dimension, while inequalities simply divide the then-feasible region into allowed and nonallowed pieces. When all the constraints are imposed, either we are left with some feasible region or else there are no feasible vectors. Since the feasible region is bounded by hyperplanes, 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 its interior, 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 that we could always increase the objective function by running up the gradient until we 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 we reach an edge of that wall. We can then run up that edge, and so on, down through whatever number of dimensions, until we finally arrive at a point, a vertex of the original simplex. Since this point has all N of its coordinates defined, it must be the solution of N simultaneous equalities drawn from the original set of equalities and inequalities (10.8.2)–(10.8.5). Points that are feasible vectors and that satisfy N of the original constraints as equalities, are termed feasible basic vectors. If N>M, then a feasible basic vector has at least N − M of its components equal to zero, since at least that many of the constraints (10.8.2) will be needed to make up the total of N. Put the other way, 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 the last 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 Fundamental Theorem of Linear Optimization: If an optimal feasible vector exists, then there is a feasible basic vector that is optimal. (Didn’t we warn you about the terminological thicket?) The importance of the fundamental theorem is that it reduces the optimization problem 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 optimal feasible vector. We have only to keep trying different combinations, and computing the objective function for each trial, until we find the best. Doing this blindly would take halfway to forever. The simplex method, first published 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 each step, and (ii) the optimal feasible vector is reached after a number of iterations that is almost always no larger than of order M or N, whichever is larger. An interesting mathematical sidelight is that this second property, although known empirically ever since the simplex method was devised, was not proved to be true until the 1982 work of Stephen Smale. (For a contemporary account, see [3].) Simplex Method for a Restricted Normal Form A linear programming problem is said to be in normal form if it has no constraints in the form (10.8.3) or (10.8.4), but rather only equality constraints of the form (10.8.5) and nonnegativity constraints of the form (10.8.2)