438 Chapter 10. Minimization or Maximization of Functions to be solved is as posed in equations(10.8.6)(10.8.7). T2 T3 1 2 0 1 1 3 - 0 0 0 21 740 -1 0 -2 0 -1 0 0 22 0 -2 0 7 0 0 23 0 1 -2 0 0 24 9 -1 1 0 0 0 83 3 -749号 2 4 1 -1 (10.8.18) 李二gOM 鱼 100 This is not as daunting as it may,at first sight,appear.The table entries inside from NUMERICAL RECIPES I 18881892 the box of double lines are no more than the coefficients of the original problem (10.8.6)(10.8.7)organized into a tabular form.In fact,these entries,along with the values of N,M,m1,m2,and m3,are the only input that is needed by the simplex method routine below.The columns under the slack variables yi simply e≥e8N America THE record whether each of the M constraints is of the form≤，≥，or=,this is redundant information with the values m1,m2,m3,as long as we are sure to enter the rows of ART the tableau in the correct respective order.The coefficients of the auxiliary objective function (bottom row)are just the negatives of the column sums of the rows above. Progra so these are easily calculated automatically. The output from a simplex routine will be (i)a flag telling whether a finite solution,no solution,or an unbounded solution was found,and (ii)an updated tableau. The output tableau that derives from(10.8.18),given to two significant figures,is T1 y2 y3 1881892 OF SCIENTIFIC COMPUTING (ISBN 17.03 -.95 -.05 -1.05 3.33 -.35 -.15 .35 v@cam 72 …… 10-6211 T3 4.73 -.55 .05 -.45 工4 .95 -.10 .10 .10 gegegh% Numerical Recipes 43198-5 1 730.55 .10 -.10 90 (10.8.19) (outside North Software. A little counting of the zi's and yi's will convince you that there are M+1 rows (including the z-row)in both the input and the output tableaux,but that only N+1-m3 columns of the output tableau(including the constant column)contain any useful information,the other columns belonging to now-discarded artificial variables.In the output,the first numerical column contains the solution vector. along with the maximum value of the objective function.Where a slack variable(y) appears on the left,the corresponding value is the amount by which its inequality is safely satisfied.Variables that are not left-hand variables in the output tableau have zero values.Slack variables with zero values represent constraints that are satisfied as equalities.438 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). to be solved is as posed in equations (10.8.6)–(10.8.7). x1 x2 x3 x4 y1 y2 y3 z 0 1 1 3 −1 2 0 0 0 z1 740 −1 0 −2 0 −1 0 0 z2 0 0 −2 0 7 0 −1 0 z3 1 2 0 −1 1 −2 0 0 1 z4 9 −1 −1 −1 −1 0 0 0 z
−749 1 2 2 4 2 −4 1 1 −1 (10.8.18) This is not as daunting as it may, at first sight, appear. The table entries inside the box of double lines are no more than the coefficients of the original problem (10.8.6)–(10.8.7) organized into a tabular form. In fact, these entries, along with the values of N, M, m1, m2, and m3, are the only input that is needed by the simplex method routine below. The columns under the slack variables y i simply record whether each of the M constraints is of the form ≤, ≥, or =; this is redundant information with the values m1, m2, m3, as long as we are sure to enter the rows of the tableau in the correct respective order. The coefficients of the auxiliary objective function (bottom row) are just the negatives of the column sums of the rows above, so these are easily calculated automatically. The output from a simplex routine will be (i) a flag telling whether a finite solution, no solution, or an unbounded solution was found,and (ii) an updated tableau. The output tableau that derives from (10.8.18), given to two significant figures, is x1 y2 y3 ··· z 17.03 −.95 −.05 −1.05 ··· x2 3.33 −.35 −.15 .35 ··· x3 4.73 −.55 .05 −.45 ··· x4 .95 −.10 .10 .10 ··· y1 730.55 .10 −.10 .90 ··· (10.8.19) A little counting of the xi’s and yi’s will convince you that there are M + 1 rows (including the z-row) in both the input and the output tableaux, but that only N + 1 − m3 columns of the output tableau (including the constant column) contain any useful information, the other columns belonging to now-discarded artificial variables. In the output, the first numerical column contains the solution vector, along with the maximum value of the objective function. Where a slack variable (y i) appears on the left, the corresponding value is the amount by which its inequality is safely satisfied. Variables that are not left-hand variables in the output tableau have zero values. Slack variables with zero values represent constraints that are satisfied as equalities