10.8 Linear Programming and the Simplex Method 441 if (iposv[ip]>(n+m1+m2+1)){ Exchanged out an artificial variable for (k=1;k<=nl1;k++) for an equality constraint.Make if (11[k]=kp)break; sure it stays out by removing it -n11; from the 11 list. for(is=k;1s<=n11;1s++)11[1s]=11[is+1]; else kh=iposv[ip]-m1-n; 1f(kh>=113[kh])[ Exchanged out an m2 type constraint 13[kh]=0; for the first time.Correct the ++a[m+2][kp+1]; pivot column for the minus sign for(1=1;1<=m+2;1++) and the implicit artificial vari- a[i][kp+1]=-a[i]p+1]; able. is=izrov [kp]; Update lists of left-and right-hand 83 izrov [kp]=iposv[ip]; variables. 鱼 18881892 iposv [ip]=is; Still in phase one,go back to the 1800 for(;;) End of phase one code for finding an initial feasible solution.Now,in phase two,optimize it. O州fro for(;;){ simp1(a,0,11,nl1,0,&kp,&bmax); Test the z-row for doneness. if (bmax <EPS){ Done.Solution found.Return with (Nort server *icase=0; the good news. 9 FREEALL return; computer Ameri simp2(a,m,n,&ip,kp); Locate a pivot element (phase two). ART 1f(1p==0)[ Objective function is unbounded.Re- *icase=1; port and return. FREEALL return; Program simp3(a,m,n,ip,kp); Exchange a left-and a right-hand is=izrov[kp]; variable (phase two). izrov [kp]=iposv [ip]; iposv[ip]=is; to dir and return for another iteration. 188 OF SCIENTIFIC COMPUTING(ISBN 1920 The preceding routine makes use of the following utility functions. Numerical Recipes 0621 -43108 #include <math.h> void simp1(float **a,int mm,int 11[],int nll,int iabf,int *kp, (outside float *bmax) Software. Determines the maximum of those elements whose index is contained in the supplied list 11, either with or without taking the absolute value,as flagged by iabf. Ame int k; float test; if(n11<=0) No eligible columns 米bmax=0.0; else *kp=11[1]; *bmax=a [mm+1][*kp+1]; for(k=2;k<=nl1;k++)[ if (iabf ==0) test=a[mm+1][11[k]+1]-(*bmax);10.8 Linear Programming and the Simplex Method 441 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). if (iposv[ip] >= (n+m1+m2+1)) { Exchanged out an artificial variable for an equality constraint. Make sure it stays out by removing it from the l1 list. for (k=1;k<=nl1;k++) if (l1[k] == kp) break; --nl1; for (is=k;is<=nl1;is++) l1[is]=l1[is+1]; } else { kh=iposv[ip]-m1-n; if (kh >= 1 && l3[kh]) { Exchanged out an m2 type constraint for the first time. Correct the pivot column for the minus sign and the implicit artificial vari￾able. l3[kh]=0; ++a[m+2][kp+1]; for (i=1;i<=m+2;i++) a[i][kp+1] = -a[i][kp+1]; } } is=izrov[kp]; Update lists of left- and right-hand izrov[kp]=iposv[ip]; variables. iposv[ip]=is; } Still in phase one, go back to the } for(;;). End of phase one code for finding an initial feasible solution. Now, in phase two, optimize it. for (;;) { simp1(a,0,l1,nl1,0,&kp,&bmax); Test the z-row for doneness. if (bmax <= EPS) { Done. Solution found. Return with *icase=0; the good news. FREEALL return; } simp2(a,m,n,&ip,kp); Locate a pivot element (phase two). if (ip == 0) { Objective function is unbounded. Re- *icase=1; port and return. FREEALL return; } simp3(a,m,n,ip,kp); Exchange a left- and a right-hand is=izrov[kp]; variable (phase two), izrov[kp]=iposv[ip]; iposv[ip]=is; } and return for another iteration. } The preceding routine makes use of the following utility functions. #include <math.h> void simp1(float **a, int mm, int ll[], int nll, int iabf, int *kp, float *bmax) Determines the maximum of those elements whose index is contained in the supplied list ll, either with or without taking the absolute value, as flagged by iabf. { int k; float test; if (nll <= 0) No eligible columns. *bmax=0.0; else { *kp=ll[1]; *bmax=a[mm+1][*kp+1]; for (k=2;k<=nll;k++) { if (iabf == 0) test=a[mm+1][ll[k]+1]-(*bmax);