10.8 Linear Programming and the Simplex Method 431 and simultaneously subject to M=m1+m2+m3 additional constraints,mi of them of the form ai1x1+a2r2+·+aNxN≤b: (b:≥0)i=1,,m1 (10.8.3) m2 of them of the form aj1x1+aj22+.+aNxW≥bj≥0j=m1+1,.,m1+m2(10.8.4) and ma of them of the form 三 ak1T1+ak2x2+·+OkNTN=bk≥0 (10.8.5) k=m1+m2+1,.,m1+m2+m3 The various ai's can have either sign,or be zero.The fact that the b's must all be nonnegative(as indicated by the final inequality in the above three equations)is a matter of convention only,since you can multiply any contrary inequality by-1. There is no particular significance in the number of constraints M being less than, 2 equal to,or greater than the number of unknowns N. A set of values 1...N that satisfies the constraints (10.8.2)-(10.8.5)is called a feasible vector.The function that we are trying to maximize is called the objective fimnction.The feasible vector that maximizes the objective function is called the optimal feasible vector.An optimal feasible vector can fail to exist for two distinct reasons:(i)there are no feasible vectors,i.e.,the given constraints are incompatible, 6君是 or(ii)there is no maximum,i.e.,there is a direction in N space where one or more of the variables can be taken to infinity while still satisfying the constraints,giving SCIENTIFIC( an unbounded value for the objective function. 6 As you see,the subject of linear programming is surrounded by notational and terminological thickets.Both of these thorny defenses are lovingly cultivated by a coterie of stern acolytes who have devoted themselves to the field.Actually,the basic ideas of linear programming are quite simple.Avoiding the shrubbery,we want to teach you the basics by means of a couple of specific examples;it should then be quite obvious how to generalize. Why is linear programming so important?(i)Because "nonnegativity"is the Numerica 10621 usual constraint on any variable zi that represents the tangible amount of some 431 physical commodity,like guns,butter,dollars,units of vitamin E,food calories, Recipes kilowatt hours,mass,etc.Hence equation (10.8.2).(ii)Because one is often interested in additive (linear)limitations or bounds imposed by man or nature minimum nutritional requirement,maximum affordable cost,maximum on available North labor or capital,minimum tolerable level of voter approval,etc.Hence equations (10.8.3)(10.8.5).(iii)Because the function that one wants to optimize may be linear,or else may at least be approximated by a linear function-since that is the problem that linear programming can solve.Hence equation(10.8.1).For a short, semipopular survey of linear programming applications,see Bland [11. Here is a specific example of a problem in linear programming,which has N=4,m1 2,m2 m3 1,hence M=4: Maximize z=1+2+3x3-4 (10.8.6)10.8 Linear Programming and the Simplex Method 431 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). and simultaneously subject to M = m1 + m2 + m3 additional constraints, m1 of them of the form ai1x1 + ai2x2 + ··· + aiN xN ≤ bi (bi ≥ 0) i = 1,...,m1 (10.8.3) m2 of them of the form aj1x1 + aj2x2 + ··· + ajN xN ≥ bj ≥ 0 j = m1 + 1,...,m1 + m2 (10.8.4) and m3 of them of the form ak1x1 + ak2x2 + ··· + akN xN = bk ≥ 0 k = m1 + m2 + 1,...,m1 + m2 + m3 (10.8.5) The various aij ’s can have either sign, or be zero. The fact that the b’s must all be nonnegative (as indicated by the final inequality in the above three equations) is a matter of convention only, since you can multiply any contrary inequality by −1. There is no particular significance in the number of constraints M being less than, equal to, or greater than the number of unknowns N. A set of values x1 ...xN that satisfies the constraints (10.8.2)–(10.8.5) is called a feasible vector. The function that we are trying to maximize is called the objective function. The feasible vector that maximizes the objective function is called the optimal feasible vector. An optimal feasible vector can fail to exist for two distinct reasons: (i) there are no feasible vectors, i.e., the given constraints are incompatible, or (ii) there is no maximum, i.e., there is a direction in N space where one or more of the variables can be taken to infinity while still satisfying the constraints, giving an unbounded value for the objective function. As you see, the subject of linear programming is surrounded by notational and terminological thickets. Both of these thorny defenses are lovingly cultivated by a coterie of stern acolytes who have devoted themselves to the field. Actually, the basic ideas of linear programming are quite simple. Avoiding the shrubbery, we want to teach you the basics by means of a couple of specific examples; it should then be quite obvious how to generalize. Why is linear programming so important? (i) Because “nonnegativity” is the usual constraint on any variable xi that represents the tangible amount of some physical commodity, like guns, butter, dollars, units of vitamin E, food calories, kilowatt hours, mass, etc. Hence equation (10.8.2). (ii) Because one is often interested in additive (linear) limitations or bounds imposed by man or nature: minimum nutritional requirement, maximum affordable cost, maximum on available labor or capital, minimum tolerable level of voter approval, etc. Hence equations (10.8.3)–(10.8.5). (iii) Because the function that one wants to optimize may be linear, or else may at least be approximated by a linear function — since that is the problem that linear programming can solve. Hence equation (10.8.1). For a short, semipopular survey of linear programming applications, see Bland [1]. Here is a specific example of a problem in linear programming, which has N = 4, m1 = 2, m2 = m3 = 1, hence M = 4: Maximize z = x1 + x2 + 3x3 − 1 2x4 (10.8.6)