#include<iomanip.h>#include <fstream.h>#define Min -99999#define Max 99999int main(){ float a[100][100],b[100],z[100],c[100]; int XB[100]; int m,n; int in,out; float inN,outN; float sum; int pos; float temp,temp2,temp3; int i,j; float result; ifstream fin("in.txt"); ofstream fout("out.txt"); fin>>m>>n; for(i=0;i<m;i++) fin>>z[i]; for(i=0;i<n;i++) { for(j=0;j<m;j++) fin>>a[i][j]; fin>>b[i]; } for(i=0;i<n;i++) XB[i]=i+m; for(i=0;i<n;i++) for(j=0;j<n;j++) a[i][m+j]=0; for(i=0;i<n;i++) a[i][m+i]=1; //第一阶段 for(i=0;i<m;i++) c[i]=0; for(i=0;i<n;i++) c[i+m]=-1; for(i=0;i<m+n;i++) { sum=0.0; for(j=0;j<n;j++) sum-=a[j][i]; a[n][i]=c[i]-sum; } //for(i=0;i<n;i++) //a[n][i+m]=-1; fout<<"第1阶段 \n"; while(1) { for(i=0;i<n;i++) { fout<<"X"<<XB[i]+1<<" "; fout.setf(ios::fixed); fout<<setprecision(3)<<b[i]<<" "; //fout<<b[i]<<" "; for(j=0;j<m+n;j++) fout<<a[i][j]<<" "; fout<<"\n"; } fout<<" Cj-Zj "; for(j=0;j<m+n;j++) { fout.setf(ios::fixed); fout<<setprecision(3)<<a[n][j]<<" "; //fout<<a[n][j]<<" "; } in=-1; inN=Min; for(i=0;i<m;i++) if(a[n][i]>inN) { in=i; inN=a[n][i]; } if(inN<=0) break;//end out=-1; outN=Max; for(i=0;i<n;i++) if(a[i][in]>0) { if(b[i]/a[i][in]<outN) { out=i; outN=b[i]/a[i][in]; //fout<<outN<<" "; } } if(outN==Max) break;//无界解 fout<<"\n换出变量:X"<<XB[out]+1<<" 换入变量:X"<<in+1<<endl; fout<<"\n\n"; XB[out]=in; temp=a[out][in]; for(i=0;i<m+n;i++) a[out][i]=a[out][i]/temp; temp3=b[out]; b[out]=b[out]/temp; for(i=0;i<n+1;i++) if(i!=out) { temp2=a[i][in]; for(j=0;j<m+n;j++) a[i][j]=a[i][j]-a[out][j]*temp2; b[i]=b[i]-b[out]*temp2; } //for(i=0;i<n;i++) //{ //if(i!=out) //b[i]=b[i]-b[out]*temp2; //} } //第2阶段 fout<<"\n\n第2阶段 \n"; for(i=0;i<m;i++) c[i]=z[i]; //for(j=0;j<n;j++) // fout<<XB[j]<<" "; for(i=0;i<m;i++) { sum=0.0; for(j=0;j<n;j++) { sum=sum+c[XB[j]]*a[j][i]; //fout<<sum<<" "<<c[XB[j]]<<" "<<a[j][i]<<endl; } a[n][i]=c[i]-sum; } while(1) { for(i=0;i<n;i++) { fout<<"X"<<XB[i]+1<<" "; fout.setf(ios::fixed); fout<<setprecision(3)<<b[i]<<" "; //fout<<b[i]<<" "; for(j=0;j<m;j++) fout<<a[i][j]<<" "; fout<<"\n"; } fout<<" Cj-Zj "; for(j=0;j<m;j++) { fout.setf(ios::fixed); fout<<setprecision(3)<<a[n][j]<<" "; //fout<<a[n][j]<<" "; } in=-1; inN=Min; for(i=0;i<m;i++) if(a[n][i]>inN) { in=i; inN=a[n][i]; } if(inN<=0) break;//end out=-1; outN=Max; for(i=0;i<n;i++) if(a[i][in]>0) { if(b[i]/a[i][in]<outN) { out=i; outN=b[i]/a[i][in]; //fout<<outN<<" "; } } if(outN==Max) break;//无界解 fout<<"\n换出变量:X"<<XB[out]+1<<" 换入变量:X"<<in+1<<endl; fout<<"\n\n"; XB[out]=in; temp=a[out][in]; for(i=0;i<m;i++) a[out][i]=a[out][i]/temp; temp3=b[out]; b[out]=b[out]/temp; for(i=0;i<n+1;i++) if(i!=out) { temp2=a[i][in]; for(j=0;j<m+n;j++) a[i][j]=a[i][j]-a[out][j]*temp2; b[i]=b[i]-b[out]*temp2; } //for(i=0;i<n;i++) //{ //if(i!=out) //b[i]=b[i]-b[out]*temp2; //} } fout<<"\n\n"; for(i=0;i<m;i++) c[i]=0; for(i=0;i<n;i++) c[XB[i]]=b[i]; for(i=0;i<m;i++) fout<<"X"<<i+1<<"="<<c[i]<<" "; fout<<endl; result=0.0; for(i=0;i<n;i++) result+=b[i]*z[XB[i]]; fout<<"结果是："<<result; fout.close();}
评论