430 Chapter 10.Minimization or Maximization of Functions Quasi-Newton methods like dfpmin work well with the approximate line minimization done by Insrch.The routines powell(810.5)and frprmn($10.6), however,need more accurate line minimization,which is carried out by the routine linmin Advanced Implementations of Variable Metric Methods Although rare,it can conceivably happen that roundoff errors cause the matrix Hi to become nearly singular or non-positive-definite.This can be serious,because the supposed search directions might then not lead downhill,and because nearly singular Hi's tend to give subsequent Hi's that are also nearly singular. There is a simple fix for this rare problem,the same as was mentioned in 810.4:In case of any doubt,you should restart the algorithm at the claimed minimum point,and see if it goes anywhere.Simple,but not very elegant.Modern implementations of variable metric methods deal with the problem in a more sophisticated way. Instead of building up an approximation to A,it is possible to build up an approximation of A itself.Then,instead of calculating the left-hand side of (10.7.4)directly,one solves the set of linear equations 华 A·(x-x)=-7fx) (10.7.11) 2 At first glance this seems like a bad idea,since solving (10.7.11)is a process of order N3-and anyway,how does this help the roundoff problem?The trick is not to store A but rather a triangular decomposition of A,its Cholesky decomposition (cf.$2.9).The updating Press. formula used for the Cholesky decomposition of A is of order N2 and can be arranged to guarantee that the matrix remains positive definite and nonsingular,even in the presence of finite roundoff.This method is due to Gill and Murray [1,2]. CITED REFERENCES AND FURTHER READING: OF SCIENTIFIC( Dennis,J.E.,and Schnabel,R.B.1983.Numerica/Methods for Unconstrained Optimization and Nonlinear Equations (Englewood Cliffs,NJ:Prentice-Hall).[1] 6 Jacobs,D.A.H.(ed.)1977,The State of the Art in Numerical Analysis(London:Academic Press), Chapter Ill.1,883-6 (by K.W.Brodlie).[2] Polak,E.1971,Computational Methods in Optimization (New York:Academic Press),pp.56ff.[3] 最 Acton,F.S.1970,Numerica/Methods That Work,1990,corrected edition (Washington:Mathe- matical Association of America),pp.467-468. Fuunrgroirion Numerical Recipes 10-621 43106 10.8 Linear Programming and the Simplex (outside Method North Software. The subject of linear programming,sometimes called linear optimization, Ame concerns itself with the following problem:For N independent variables1,...,N, maximize the function 2=a01E1+a02r2+···+a0NxN (10.8.1) subject to the primary constraints x1≥0,2≥0，.xN≥0 (10.8.2)
430 Chapter 10. Minimization or Maximization of Functions 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 machinereadable 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). Quasi-Newton methods like dfpmin work well with the approximate line minimization done by lnsrch. The routines powell (§10.5) and frprmn (§10.6), however, need more accurate line minimization, which is carried out by the routine linmin. Advanced Implementations of Variable Metric Methods Although rare, it can conceivably happen that roundoff errors cause the matrix Hi to become nearly singular or non-positive-definite. This can be serious, because the supposed search directions might then not lead downhill, and because nearly singular Hi’s tend to give subsequent Hi’s that are also nearly singular. There is a simple fix for this rare problem, the same as was mentioned in §10.4: In case of any doubt, you should restart the algorithm at the claimed minimum point, and see if it goes anywhere. Simple, but not very elegant. Modern implementations of variable metric methods deal with the problem in a more sophisticated way. Instead of building up an approximation to A−1, it is possible to build up an approximation of A itself. Then, instead of calculating the left-hand side of (10.7.4) directly, one solves the set of linear equations A · (x − xi) = −∇f(xi) (10.7.11) At first glance this seems like a bad idea, since solving (10.7.11) is a process of order N3 — and anyway, how does this help the roundoff problem? The trick is not to store A but rather a triangular decomposition of A, its Cholesky decomposition (cf. §2.9). The updating formula used for the Cholesky decomposition of A is of order N2 and can be arranged to guarantee that the matrix remains positive definite and nonsingular, even in the presence of finite roundoff. This method is due to Gill and Murray [1,2]. CITED REFERENCES AND FURTHER READING: Dennis, J.E., and Schnabel, R.B. 1983, Numerical Methods for Unconstrained Optimization and Nonlinear Equations (Englewood Cliffs, NJ: Prentice-Hall). [1] Jacobs, D.A.H. (ed.) 1977, The State of the Art in Numerical Analysis (London: Academic Press), Chapter III.1, §§3–6 (by K. W. Brodlie). [2] Polak, E. 1971, Computational Methods in Optimization (New York: Academic Press), pp. 56ff. [3] Acton, F.S. 1970, Numerical Methods That Work; 1990, corrected edition (Washington: Mathematical Association of America), pp. 467–468. 10.8 Linear Programming and the Simplex Method The subject of linear programming, sometimes called linear optimization, concerns itself with the following problem: For N independent variables x1,...,xN , maximize the function z = a01x1 + a02x2 + ··· + a0N xN (10.8.1) subject to the primary constraints x1 ≥ 0, x2 ≥ 0, ... xN ≥ 0 (10.8.2)
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 machinereadable 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)
432 Chapter 10. Minimization or Maximization of Functions a feasible basic vector (not optimal) additional con additional constraint(equality) aint 个 (inequal http://www.nr. Permission is readable files some feasible vectors granted fori the optimal feasible vector inequality） (including this one) additional constraint =3.1 .com or call 1-800-872- primary constraint =2.9 from NUMERICAL RECIPES IN X2 2=2.8 2=2.7 2=2.6 (North America to any server computer, tusers to make one paper 1988-1992 by Cambridge University Press. THE 2=2.5 ART 2=2.4 是 Programs copy for their Figure 10.8.1.Basic concepts of linear programming. The case of only two independent variables, strictly prohibited c1,2,is shown.The linear function z,to be maximized,is represented by its contour lines.Primary constraints require c1 and r2 to be positive.Additional constraints may restrict the solution to regions (inequality constraints)or to surfaces of lower dimensionality (equality constraints).Feasible vectors to dir satisfy all constraints.Feasible basic vectors also lie on the boundary of the allowed region.The simplex method steps among feasible basic vectors until the optimal feasible vector is found. OF SCIENTIFIC COMPUTING (ISBN with all the z's nonnegative and also with 1788-1982 x1+2x3≤740 10-621 2x2-7x4≤0 .Further reproduction, 43108 (10.8.7) Numerical Recipes x2-x3+2x4≥ E1十r2+x3+E4=9 (outside North Software. The answer turns out to be (to 2 decimals)1=0,x2 =3.33,x3 =4.73,x4 =0.95. In the rest of this section we will learn how this answer is obtained.Figure 10.8.1 Ame summarizes some of the terminology thus far. visit website machine Fundamental Theorem of Linear Optimization Imagine that we start with a full N-dimensional space of candidate vectors.Then (in mind's eye,at least)we carve away the regions that are eliminated in turn by each imposed constraint.Since the constraints are linear,every boundary introduced by this process is a plane,or rather hyperplane.Equality constraints of the form(10.8.5)
432 Chapter 10. Minimization or Maximization of Functions 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 machinereadable 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). additional constraint (inequality) additional constraint (inequality) the optimal feasible vector some feasible vectors x1 primary constraint x2 a feasible basic vector (not optimal) primary constraint additional constraint (equality) z = 3.1 z = 2.9 z = 2.8 z = 2.7 z = 2.6 z = 2.5 z = 2.4 z = 3.0 Figure 10.8.1. Basic concepts of linear programming. The case of only two independent variables, x1, x2, is shown. The linear function z, to be maximized, is represented by its contour lines. Primary constraints require x1 and x2 to be positive. Additional constraints may restrict the solution to regions (inequality constraints) or to surfaces of lower dimensionality (equality constraints). Feasible vectors satisfy all constraints. Feasible basic vectors also lie on the boundary of the allowed region. The simplex method steps among feasible basic vectors until the optimal feasible vector is found. with all the x’s nonnegative and also with x1 + 2x3 ≤ 740 2x2 − 7x4 ≤ 0 x2 − x3 + 2x4 ≥ 1 2 x1 + x2 + x3 + x4 = 9 (10.8.7) The answer turns out to be (to 2 decimals) x1 = 0, x2 = 3.33, x3 = 4.73, x4 = 0.95. In the rest of this section we will learn how this answer is obtained. Figure 10.8.1 summarizes some of the terminology thus far. Fundamental Theorem of Linear Optimization Imagine that we start with a full N-dimensional space of candidate vectors. Then (in mind’s eye, at least) we carve away the regions that are eliminated in turn by each imposed constraint. Since the constraints are linear, every boundary introduced by this process is a plane, or rather hyperplane. Equality constraints of the form (10.8.5)
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 machinereadable 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)
434 Chapter 10.Minimization or Maximization of Functions For our purposes it will be useful to consider an even more restricted set of cases, 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 appears uniquely in that one constraint only.We can then choose one such variable in each constraint equation,and solve that constraint equation for it.The variables thus chosen 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 or nonbasic variables.Obviously this restricted normal form can be achieved only in the case M N,so that is the case that we will consider. 三 You may be thinking that our restricted normal form is so specialized that it 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 be transformed into restricted normal form.Therefore bear with us and learn how to apply the simplex method to a restricted normal form. 之 Here is an example of a problem in restricted normal form: Maximize z=2x2-4x3 (10.8.8) with z1,x2,z3,and x4 all nonnegative and also with 、三%&、今H 9 x1=2-6x2+T3 (10.8.9) x4=8+3r2-4x3 0學总 9 This example has N=4,M=2;the left-hand variables are 1 and 4;the right-hand variables are 2 and x3.The objective function(10.8.8)is written so as to depend only on right-hand variables;note,however,that this is not an actual restriction on objective functions in restricted normal form,since any left-hand variables appearing in the objective function could be eliminated algebraically by use of (10.8.9)or its analogs For any problem in restricted normal form,we can instantly read off a feasible basic vector(although not necessarily the optimal feasible basic vector).Simply set all right-hand variables equal to zero,and equation(10.8.9)then gives the values of 10621 the left-hand variables for which the constraints are satisfied.The idea of the simplex Numerica method is to proceed by a series of exchanges.In each exchange,a right-hand 431 variable and a left-hand variable change places.At each stage we maintain a problem Recipes in restricted normal form that is equivalent to the original problem. (outside 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: North T2 T3 0 -4 T1 2 -6 1 工4 8 3 -4 (10.8.10) You should study (10.8.10)to be sure that you understand where each entry comes from,and how to translate back and forth between the tableau and equation formats of a problem in restricted normal form
434 Chapter 10. Minimization or Maximization of Functions 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 machinereadable 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). For our purposes it will be useful to consider an even more restricted set of cases, 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 appears uniquely in that one constraint only. We can then choose one such variable in each constraint equation, and solve that constraint equation for it. The variables thus chosen 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 or nonbasic variables. Obviously this restricted normal form can be achieved only in the case M ≤ N, so that is the case that we will consider. You may be thinking that our restricted normal form is so specialized that it 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 be transformed into restricted normal form. Therefore bear with us and learn how to apply the simplex method to a restricted normal form. Here is an example of a problem in restricted normal form: Maximize z = 2x2 − 4x3 (10.8.8) with x1, x2, x3, and x4 all nonnegative and also with x1 = 2 − 6x2 + x3 x4 =8+3x2 − 4x3 (10.8.9) This example has N = 4, M = 2; the left-hand variables are x1 and x4; the right-hand variables are x2 and x3. The objective function (10.8.8) is written so as to depend only on right-hand variables; note, however, that this is not an actual restriction on objective functions in restricted normal form, since any left-hand variables appearing in the objective function could be eliminated algebraically by use of (10.8.9) or its analogs. For any problem in restricted normal form, we can instantly read off a feasible basic vector (although not necessarily the optimal feasible basic vector). Simply set all right-hand variables equal to zero, and equation (10.8.9) then gives the values of the left-hand variables for which the constraints are satisfied. The idea of the simplex method is to proceed by a series of exchanges. In each exchange, a right-hand variable and a left-hand variable change places. At each stage we maintain a problem in 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: x2 x3 z 0 2 −4 x1 2 −6 1 x4 8 3 −4 (10.8.10) You should study (10.8.10) to be sure that you understand where each entry comes from, and how to translate back and forth between the tableau and equation formats of a problem in restricted normal form