10.8 Linear Programming and the Simplex Method 439 Routine Implementing the Simplex Method The following routine is based algorithmically on the implementation of Kuenzi, Tzschach,and Zehnder [4].Aside from input values of M,N,m1,m2,m3,the principal input to the routine is a two-dimensional array a containing the portion of the tableau(10.8.18)that is contained between the double lines.This input occupies the M+1 rows and N+1 columns of a[1..m+1][1..n+1].Note,however,that reference is made internally to row M+2 of a (used for the auxiliary objective function,just as in 10.8.18).Therefore the variable declared as float **a,must point to allocated memory allowing references in the subrange a[i订[k],i=1..m+2,k=1..n+1 (10.8.20 菲 You will suffer endless agonies if you fail to understand this simple point.Also do 三 not neglect to order the rows of a in the same order as equations(10.8.1),(10.8.3), (10.8.4),and (10.8.5),that is,objective function,<-constraints,>-constraints, =-constraints. RECIPES On output,the tableau a is indexed by two returned arrays of integers.iposv [j] contains,for j=1...M,the number i whose original variable i is now represented 9 by row j+1 of a.These are thus the left-hand variables in the solution.(The first row of a is of course the z-row.)A valuei>N indicates that the variable is a yi rather than an i,N+y Likewise,izrov [j]contains,for j=1...N,the number i whose original variable x;is now a right-hand variable,represented by column j+1 of a.These variables are all zero in the solution.The meaning ofi>N is the same 三星是g口0 as above,except that i N +m+m2 denotes an artificial or slack variable which was used only internally and should now be entirely ignored. The flag icase is set to zero if a finite solution is found,+1 if the objective function is unbounded,-1 if no solution satisfies the given constraints. The routine treats the case of degenerate feasible vectors,so don't worry about them.You may also wish to admire the fact that the routine does not require storage for the columns of the tableau (10.8.18)that are to the right of the double line:it keeps track of slack variables by more efficient bookkeeping. 巴>空。P 61 Please note that,as given,the routine is only "semi-sophisticated"in its tests Numerica 10621 for convergence.While the routine properly implements tests for inequality with zero as tests against some small parameter EPS,it does not adjust this parameter to reflect the scale of the input data.This is adequate for many problems,where the a蓝3 input data do not differ from unity by too many orders of magnitude.If,however, you encounter endless cycling,then you should modify EPS in the routines simplx and simp2.Permuting your variables can also help.Finally,consult [51. #include "nrutil.h" #define EPS 1.0e-6 Here EPS is the absolute precision,which should be adjusted to the scale of your variables. #define FREEALL free_ivector(13,1,m);free_ivector(11,1,n+1); void simplx(float **a,int m,int n,int mi,int m2,int m3,int *icase, int izrov[],int iposv]) Simplex method for linear programming.Input parameters a,m,n,mp,np,m1,m2,and m3, and output parameters a,icase,izrov,and iposv are described above. void simp1(float **a,int mm,int 11[],int nll,int iabf,int *kp,10.8 Linear Programming and the Simplex Method 439 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). Routine Implementing the Simplex Method The following routine is based algorithmically on the implementation of Kuenzi, Tzschach, and Zehnder [4]. Aside from input values of M, N, m1, m2, m3, the principal input to the routine is a two-dimensional array a containing the portion of the tableau (10.8.18) that is contained between the double lines. This input occupies the M + 1 rows and N + 1 columns of a[1..m+1][1..n+1]. Note, however, that reference is made internally to row M + 2 of a (used for the auxiliary objective function, just as in 10.8.18). Therefore the variable declared as float **a, must point to allocated memory allowing references in the subrange a[i][k], i = 1 ... m+2, k = 1 ... n+1 (10.8.20) You will suffer endless agonies if you fail to understand this simple point. Also do not neglect to order the rows of a in the same order as equations (10.8.1), (10.8.3), (10.8.4), and (10.8.5), that is, objective function, ≤-constraints, ≥-constraints, =-constraints. On output, the tableau a is indexed by two returned arrays of integers. iposv[j] contains, for j= 1 ...M, the number i whose original variable xi is now represented by row j+1 of a. These are thus the left-hand variables in the solution. (The first row of a is of course the z-row.) A value i>N indicates that the variable is a yi rather than an xi, xN+j ≡ yj . Likewise, izrov[j] contains, for j= 1 ...N, the number i whose original variable xi is now a right-hand variable, represented by column j+1 of a. These variables are all zero in the solution. The meaning of i>N is the same as above, except that i>N + m1 + m2 denotes an artificial or slack variable which was used only internally and should now be entirely ignored. The flag icase is set to zero if a finite solution is found, +1 if the objective function is unbounded, −1 if no solution satisfies the given constraints. The routine treats the case of degenerate feasible vectors, so don’t worry about them. You may also wish to admire the fact that the routine does not require storage for the columns of the tableau (10.8.18) that are to the right of the double line; it keeps track of slack variables by more efficient bookkeeping. Please note that, as given, the routine is only “semi-sophisticated” in its tests for convergence. While the routine properly implements tests for inequality with zero as tests against some small parameter EPS, it does not adjust this parameter to reflect the scale of the input data. This is adequate for many problems, where the input data do not differ from unity by too many orders of magnitude. If, however, you encounter endless cycling, then you should modify EPS in the routines simplx and simp2. Permuting your variables can also help. Finally, consult [5]. #include "nrutil.h" #define EPS 1.0e-6 Here EPS is the absolute precision, which should be adjusted to the scale of your variables. #define FREEALL free_ivector(l3,1,m);free_ivector(l1,1,n+1); void simplx(float **a, int m, int n, int m1, int m2, int m3, int *icase, int izrov[], int iposv[]) Simplex method for linear programming. Input parameters a, m, n, mp, np, m1, m2, and m3, and output parameters a, icase, izrov, and iposv are described above. { void simp1(float **a, int mm, int ll[], int nll, int iabf, int *kp