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 form434 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 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). 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