表上作業(yè)法的源代碼

1、/* 表上作業(yè)法的源代碼 */#include "stdio.h"#include "alloc.h"#include "math.h"/* #define debug */#define a(j) (*(C+(M-1)*N+j) /*銷量數(shù)組*/#define b(i) (*(C+i*N+N-1) /*產(chǎn)量數(shù)組*/#define c(i,j) (*(C+i*N+j) /*運(yùn)價數(shù)組*/#define x(i,j) (*(X+i*(N-1)+j) /*運(yùn)量數(shù)組 */*(<1.0E15:基本解,>=1.0E15:運(yùn)量為0) *

2、/#define s(i,j) (*(S+i*(N-1)+j) /*檢驗數(shù)數(shù)組Sij */#define u(i) (*(U+i) /*位勢數(shù)組Ui*/#define v(i) (*(V+i) /*位勢數(shù)組Vi*/#define cpi(k) (CP+k)->i) /*閉回路點(diǎn)i標(biāo)*/#define cpj(k) (CP+k)->j) /*閉回路點(diǎn)i標(biāo)*/#define cpf(k) (CP+k)->f) /*閉回路點(diǎn)i標(biāo)*/* f=0:j+; f=2:j-; f=1;i-; f=3:i+; */*void TP(int M,int N,double *C,double *X

3、); */ 10 6 30 0 20 30 40 50 60 12 7 14 16 9 10 9 13 8 14 183 185 119 162 137 102 179 118 114 189 107 169 161 179 169 140 135 112 184 149 128 106 165 178 199 183 194 127 184 173 124 125 151 127 178 160 162 105 150 185 179 153 174 121 142 108 163 157 138 189 171 114 131 165 150 159 131 155 135 165 124

4、 167 107 109 107 149 175 162 108 182 135 181 106 136 183 134 179 188 136 131 189 166 158 159 180 162 104 116 159 111void main()int M,N,i,j;double *C; /*存儲運(yùn)價,產(chǎn)量及銷量 */double *X; /*存儲運(yùn)量分配方案 */float z;FILE *fp;char fn80;double sum;void TP(int M,int N,double *C,double *X);printf("please input the da

5、ta file name: ");scanf("%s",fn);if(fp=fopen(fn,"r")=NULL) printf("Cannot open the data file!"); getch(); exit(0); fscanf(fp,"%d%d",&M,&N);M+; N+;X=(double *)malloc(sizeof(double)*(M-1)*(N-1);C=(double *)malloc(sizeof(double)*M*N);/* 把運(yùn)價,供應(yīng)量和需求量的數(shù)據(jù)

6、讀入到數(shù)組c(i,j); */ /*-高太光：這里可以直接定義固定的數(shù)組c(i,j),也可以從文件讀取for(i=0;i<M;i+) for(j=0;j<N;j+) fscanf(fp,"%f",&z); c(i,j)=z; printf("n"); fclose(fp);/* output c(i,j); */printf("n=Data File=n");for(i=0;i<M;i+) for(j=0;j<N;j+) printf("%10.3f",c(i,j); printf(

7、"n"); getch();TP(M,N,C,X);/* 輸出產(chǎn)銷分配方案; */printf("n=Best Solution=n");sum=0;for(i=0;i<M-1;i+) for(j=0;j<N-1;j+) if(x(i,j)>=1.0e15) printf("%10s","*"); else printf("%10.3f",x(i,j); sum+=(x(i,j)*c(i,j); printf("n"); printf("nntTh

8、e min Cost is: %-10.4fn",sum); getch(); free(X); free(C);struct PATH int i,j,f; ; /*記錄閉回路點(diǎn)結(jié)構(gòu)*/void TP(int M,int N, double *C,double *X)double *U,*V,*S;int MN1,m,n;struct PATH *CP;int k,i,j,l,k1,l1,ip;double Cmin,sum;int I0,J0,Imin,Jmin;int fi,fj,fc,f;MN1=(M-1)+(N-1)-1;m=M-1;n=N-1;S=(double *)ma

9、lloc(sizeof(double)*(M-1)*(N-1);U=(double *)malloc(sizeof(double)*M);V=(double *)malloc(sizeof(double)*N);CP=(struct PATH *)malloc(sizeof(struct PATH)*(MN1+1);#ifdef debugprintf("nM=%d,N=%d,m=%d,n=%dn",M,N,m,n);printf("nb(i)is following:n");for(i=0;i<m;i+) printf("%8.4ft&

10、quot;,b(i);printf("na(j)is folowing:n");for(j=0;j<n;j+) printf("%8.4ft",a(j);printf("n");getch();#endif/*解初始化Xij=1.0e15; */for(i=0;i<m;i+) for(j=0;j<n;j+) x(i,j)=1.0e15;/*最小元素法求初始可行解 */for(k=0;k<MN1;k+) Cmin=1.0e15; for(i=0;i<m;i+) fi=0; for(l=0;l<k;l+

11、) /* 去除已經(jīng)用過的行; */ if(i=cpi(l)fi=1;break; if(fi=1)continue; for(j=0;j<n;j+) fj=0; for(l=0;l<k;l+) /* 去除已經(jīng)用過的列; */ if(j=cpj(l)fj=1;break; if(fj=1) continue; if(Cmin>c(i,j) Cmin=c(i,j);I0=i;J0=j; #ifdef debug printf("n now c(i,j)=%8.4fn",c(i,j); #endif /*end for j */ /* end for i */

12、/*得到了未劃去的最小運(yùn)價所在格的坐標(biāo)(I0,J0)和最小運(yùn)價Cmin */ if(k>0) if(Cmin=1.0e15&&cpi(k-1)=0) for(l1=0;l1<m;l1+) if(x(l1,cpj(k-1)=1.0e15) x(l1,cpj(k-1)=0; else if(Cmin=1.0e15&&cpi(k-1)!=0) for(l1=0;l1<n;l1+) if(x(cpi(k-1),l1)=1.0e15) x(cpi(k-1),l1)=0; if(b(I0)<a(J0) cpi(k)=I0;cpj(k)=-1; x(I

13、0,J0)=b(I0); #ifdef debug printf("I0=%d,J0=%d,x(I0,J0)=%8.4f,k=%d,cpi(k)=%d,cpj(k)=%dn",I0,J0,x(I0,J0),k,cpi(k),cpj(k); #endif a(J0)-=b(I0); b(I0)=0; else cpi(k)=-1;cpj(k)=J0; x(I0,J0)=a(J0); #ifdef debug printf("I0=%d,J0=%d,x(I0,J0)=%8.4f,k=%d,cpi(k)=%d,cpj(k)=%dn",I0,J0,x(I0,J0

14、),k,cpi(k),cpj(k); #endif b(I0)-=a(J0); a(J0)=0; /*END FOR K 用最小元素法求得了初使可行解*/ /*輸出初始可行解*/printf("n=init Solution=n");sum=0;for(i=0;i<M-1;i+) for(j=0;j<N-1;j+) if(x(i,j)>=1.0e15) printf("%10s","*"); else printf("%10.3f",x(i,j); sum+=(x(i,j)*c(i,j); pri

15、ntf("n"); printf("nntThe Cost is: %-10.4fn",sum); getch(); /*循環(huán)換入換出,直到檢驗數(shù)為非負(fù)數(shù)*/*循環(huán)決定換入變量 */while(1) /*位勢置初值Ui,Vi=1.0e15 */ for(i=0;i<m;i+) u(i)=1.0e15; for(j=0;j<n;j+) v(j)=1.0e15; /*求位勢*/ l=0;u(0)=0; for(i=0;i<m;i+) for(j=0;j<n;j+) if(u(i)>=1.0e15&&v(j)>

16、;=1.0e15&&x(i,j)<1.0e15) cpi(l)=i;cpj(l)=j;l+; /*記錄未求過位勢的位置*/ else if(x(i,j)<1.0e15&&u(i)<1.0e15) v(j)=c(i,j)-u(i); else if(x(i,j)<1.0e15&&v(j)<1.0e15) u(i)=c(i,j)-v(j); /*end for j */ /*end for i */ /*按記錄位置求其余位勢*/ if(l>0) while(1) ip=0; for(k=0;k<l;k+) i

17、=cpi(k);j=cpj(k); if(u(i)>=1.0e15)&&(v(j)>=1.0e15)&&(x(i,j)<1.0e15) cpi(ip)=i;cpj(ip)=j;ip+; /*記錄未求過位勢的位置*/ else if(x(i,j)<1.0e15&&u(i)<1.0e15) v(j)=c(i,j)-u(i); else if(x(i,j)<1.0e15&&v(j)<1.0e15) u(i)=c(i,j)-v(j); /*end for k */ if(ip=0)break; l

18、=ip; /*end for while */ /*end if l */#ifdef debugprintf("nU(i):");for(i=0;i<m;i+) printf("%10.2f",u(i); printf("nV(j):");for(j=0;j<n;j+) printf("%10.2f",v(j); printf("n");#endif/*求檢驗數(shù)*/for(i=0;i<m;i+) for(j=0;j<n;j+) s(i,j)=1.0e15; if(x(i

19、,j)>=1.0e15) s(i,j)=c(i,j)-u(i)-v(j); /*求最小檢驗數(shù)*/Cmin=1.0e15;for(i=0;i<m;i+) for(j=0;j<n;j+) if(Cmin>s(i,j) Cmin=s(i,j);I0=i;J0=j; #ifdef debug printf("ncheck number:n"); for(i=0;i<m;i+) for(j=0;j<n;j+) printf("s(%d,%d)=%-10.2fn",i,j,s(i,j); printf("n")

20、; printf("Smin=%-10.2f",Cmin); getch(); #endifif(Cmin>=0) return; /*已經(jīng)得到最優(yōu)解,返回主程序*/*此時找到了入基變量X(I0,J0) */*求閉回路*/for(k=0;k<MN1;k+) cpf(k)=-1; /*end for k */cpi(0)=I0;cpj(0)=J0;k=0;while(1) f=cpf(k); /*設(shè)置閉回路搜索方向*/ while(1) i=cpi(k);j=cpj(k); fc=0; f+; cpf(k)=f; if(f>=4)break; /*避免反向搜

21、索*/ if(k>0) if(f=0&&cpf(k-1)=2) continue; else if(f=1&&cpf(k-1)=3)continue; else if(f=2&&cpf(k-1)=0)continue; else if(f=3&&cpf(k-1)=1)continue; if(f=0) /*沿J+方向搜索*/ while(1) j+; if(j>=n)fc=2;break; if(i=I0)&&(j=J0) fc=1;break; if(s(i,j)>=1.0e15) fc=3;b

22、reak; /*end j+ */ else if(f=1) /*沿i-方向搜索*/ while(1) i-; if(i<0)fc=2;break; if(i=I0)&&(j=J0)fc=1;break; if(s(i,j)>=1.0e15)fc=3;break; /*end if=1 */ else if(f=2) /*沿J-方向搜索*/ while(1) j-; if(j<0)fc=2;break; if(i=I0)&&(j=J0)fc=1;break; if(s(i,j)>=1.0e15)fc=3;break; /*end f=2

23、*/ else if(f=3) /*沿I+方向搜索*/ while(1) i+; if(i>=m)fc=2;break; if(i=I0)&&(j=J0)fc=1;break; if(s(i,j)>=1.0e15)fc=3;break; /*end f=3 */ if(fc=1)|(fc=3)break;/*end while flag 2 */if(fc=0) /*沿些方向搜索失敗,退回回到前一點(diǎn)*/ k-; else if(fc=1)break; /*搜索完成*/ else if(fc=3) /*沿此方向搜索成功,前進(jìn)一點(diǎn)*/ k+; cpi(k)=i;cpj(k)=j; #ifdef debug p