440 Chapter 10.Minimization or Maximization of Functions float *bmax); void simp2(float **a,int m,int n,int *ip,int kp); void simp3(float **a,int i1,int k1,int ip,int kp); int i,ip,is,k,kh,kp,nl1; 1nt*11,*13; float q1,bmax; if (m !(m1+m2+m3))nrerror("Bad input constraint counts in simplx"); 11=1 vector(1,n+1); 13=ivector(1,m); n11=n; for (k=1;k<=n;k++)11[k]=izrov[k]=k; Initialize index list of columns admissible for exchange,and make all variables initially right-hand. for(1=1;1<=m;i++){ 83 if (a[i+1][1]0.0)nrerror("Bad input tableau in simplx"); 鱼 nted for Constants bi must be nonnegative. iposv[i]=n+i; 1.800 Initial left-hand variables.m1 type constraints are represented by having their slack variable initially left-hand,with no artificial variable.m2 type constraints have their slack variable initially left-hand,with a minus sign,and their artificial variable handled from NUMERICAL RECIPES I 18881892 implicitly during their first exchange.m3 type constraints have their artificial variable initially left-hand. 6 server if(m2+m3){ (Nort Origin is not a feasible starting so- for(1=1;1<=m2:1+)13[1]=1: lution:we must do phase one. Initialize list of m2 constraints whose slack variables have never been exchanged out Americ computer of the initial basis. ART for(k=1;k<a(n+1);k++)[ Compute the auxiliary objective func- 91=0.0; tion. for(1=m1+1;1<=m;1++)q1+=a[1+1][k]; 9 Programs a[m+2][k]=-q1; for(;;){ simp1(a,m+1,11,nl1,0,&kp,&bmax); Find max.coeff.of auxiliary objec- if (bmax <EPS&&a[m+2][1]-EPS){tive fn. *1case=-1: Auxiliary objective function is still negative and can't be improved,hence no feasible solution exists FREEALL return; else if (bmax <EPS&&a[m+2][1]<EPS){ 包 1920 SCIENTIFIC COMPUTING(ISBN Auxiliary objective function is zero and can't be improved;we have a feasible starting vector.Clean out the artificial variables corresponding to any remaining 10-621 equality constraints by goto one and then move on to phase two. for (ip=m1+m2+1;ip<=m;ip++) if (iposv[ip]==(iptn)){ Found an artificial variable for an Numerical Recipes -43108 simp1(a,ip,11,nl1,1,&kp,&bmax); equality constraint. if (bmax EPS) Exchange with column correspond- goto one; ing to maximum pivot element (outside in row North Software. for(1=m1+1;i<=m1+m2;1++) Change sign of row for any m2 con- 1f(13[i-m1]==1) straints still present from the ini- for(k=1;k<=n+1;k+) tial basis. a[i+1][k]=-a[i+1]]; break; Go to phase two. simp2(a,m,n,&ip,kp); Locate a pivot element (phase one). if(1p==0)【 Maximum of auxiliary objective func- *icase =-1; tion is unbounded,so no feasi- FREEALL return; ble solution exists. one: simp3(a,m+1,n,ip,kp); Exchange a left-and a right-hand variable (phase one),then update lists440 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). float *bmax); void simp2(float **a, int m, int n, int *ip, int kp); void simp3(float **a, int i1, int k1, int ip, int kp); int i,ip,is,k,kh,kp,nl1; int *l1,*l3; float q1,bmax; if (m != (m1+m2+m3)) nrerror("Bad input constraint counts in simplx"); l1=ivector(1,n+1); l3=ivector(1,m); nl1=n; for (k=1;k<=n;k++) l1[k]=izrov[k]=k; Initialize index list of columns admissible for exchange, and make all variables initially right-hand. for (i=1;i<=m;i++) { if (a[i+1][1] < 0.0) nrerror("Bad input tableau in simplx"); Constants bi must be nonnegative. iposv[i]=n+i; Initial left-hand variables. m1 type constraints are represented by having their slack variable initially left-hand, with no artificial variable. m2 type constraints have their slack variable initially left-hand, with a minus sign, and their artificial variable handled implicitly during their first exchange. m3 type constraints have their artificial variable initially left-hand. } if (m2+m3) { Origin is not a feasible starting so￾for (i=1;i<=m2;i++) l3[i]=1; lution: we must do phase one. Initialize list of m2 constraints whose slack variables have never been exchanged out of the initial basis. for (k=1;k<=(n+1);k++) { Compute the auxiliary objective func￾q1=0.0; tion. for (i=m1+1;i<=m;i++) q1 += a[i+1][k]; a[m+2][k] = -q1; } for (;;) { simp1(a,m+1,l1,nl1,0,&kp,&bmax); Find max. coeff. of auxiliary objec￾if (bmax <= EPS && a[m+2][1] < -EPS) { tive fn. *icase = -1; Auxiliary objective function is still negative and can’t be improved, hence no feasible solution exists. FREEALL return; } else if (bmax <= EPS && a[m+2][1] <= EPS) { Auxiliary objective function is zero and can’t be improved; we have a feasible starting vector. Clean out the artificial variables corresponding to any remaining equality constraints by goto one and then move on to phase two. for (ip=m1+m2+1;ip<=m;ip++) { if (iposv[ip] == (ip+n)) { Found an artificial variable for an simp1(a,ip,l1,nl1,1,&kp,&bmax); equality constraint. if (bmax > EPS) Exchange with column correspond￾ing to maximum pivot element in row. goto one; } } for (i=m1+1;i<=m1+m2;i++) Change sign of row for any m2 con￾straints still present from the ini￾tial basis. if (l3[i-m1] == 1) for (k=1;k<=n+1;k++) a[i+1][k] = -a[i+1][k]; break; Go to phase two. } simp2(a,m,n,&ip,kp); Locate a pivot element (phase one). if (ip == 0) { Maximum of auxiliary objective func￾tion is unbounded, so no feasi￾ble solution exists. *icase = -1; FREEALL return; } one: simp3(a,m+1,n,ip,kp); Exchange a left- and a right-hand variable (phase one), then update lists