#include<iomanip.h> #include <fstream.h>ifstream fin("a.txt");ofstream fout("b.txt");#define Min -99999#define Max 99999int main(){float a[100][100];//方程的系数float check[100];//检验数float Csum;//Cj-Zj的和float z[100];//目标函数int m,n;//分别为变量数和方程个数int XB[100];//基变量int mark[100];//标记某个基是否是基变量int in,out;//换入和换出基的位置float inN,outN;//换入和换出基的值float result;//最优值int i,j;int sum;int posx,posy;float temp,temp2;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];//下面是找基的过程for(i=0;i<100;i++)XB[i]=mark[i]=0;//先来找容易看出来的基for(i=0;i<m;i++){posy=0;sum=0;for(j=0;j<n;j++)if(a[j][i]!=0){if(sum==0) posy=j;sum++;}if(sum==1 && mark[i]==0) //第i个变量只有第j个方程有系数且不是基{temp=a[posy][i];for(j=0;j<=m;j++)//把它化为基a[posy][j]/=temp;XB[posy]=i;mark[i]=1;}} posy=0;while(posy<n){if(XB[posy]==0)//表示第posy个方程还没有找出基{posx=0;while(mark[posx]==1 || a[posy][posx]==0)//对应的变量是基或等于0,换下一个变量posx++;temp=a[posy][posx];for(i=0;i<=m;i++)//化为1a[posy][i]/=temp;for(i=0;i<n;i++)//其它的行化为0{ if(i!=posy) { temp2=a[i][posx]; for(j=0;j<=m;j++) a[i][j]=a[i][j]-a[posy][j]*temp2; }}XB[posy]=posx;mark[posx]=1;}posy++;} //把基全找出来了,放到了XB数组中,后面进行换基迭代 //算检验数for(i=0;i<m;i++){Csum=0;for(j=0;j<n;j++)Csum+=z[XB[j]]*a[j][i];check[i]=z[i]-Csum;}//列出第1个表/*fout<<"CB XB b ";for(i=0;i<m;i++)fout<<"X"<<i+1<<" ";fout<<endl;*/for(i=0;i<n;i++){fout<<z[XB[i]]<<" ";fout<<"X"<<XB[i]+1<<" ";fout.setf(ios::fixed);fout<<setprecision(3)<<a[i][m]<<" ";//fout<<a[i][m]<<"  ";for(j=0;j<m;j++)fout<<a[i][j]<<"  ";fout<<endl;}fout<<"Cj-Zj ";for(i=0;i<m;i++)fout<<check[i]<<" ";fout<<endl;   //看一下b中是否有负数，要用对偶单纯形法while(1){ out=-1; outN=Max; for(i=0;i<n;i++) if(a[i][m]<outN) {  out=i;  outN=a[i][m]; } if(outN>0) break;//b全部大于0 in=-1; inN=Max; for(i=0;i<m;i++) if(a[out][i]<0 && check[i]<0) {  if(check[i]/a[out][i]<inN)  {   in=i;   inN=check[i]/a[out][i];  } } if(inN==Max) {fout<<"\n无界解\n";break;}temp=a[out][in]; for(i=0;i<=m;i++)  a[out][i]=a[out][i]/temp; for(i=0;i<n ;i++) if(i!=out) { temp=a[i][in]; for(j=0;j<=m;j++)  a[i][j]=a[i][j]-a[out][j]*temp; } temp=check[in]; for(i=0;i<m;i++)  check[i]=check[i]-a[out][i]*temp;fout<<"入X"<<in+1<<" 出X"<<XB[out]+1<<endl;for(i=0;i<n;i++){fout<<z[XB[i]]<<" ";fout<<"X"<<XB[i]+1<<" ";fout<<a[i][m]<<"  ";for(j=0;j<m;j++)fout<<a[i][j]<<"  ";fout<<endl;}fout<<"  Cj-Zj  ";for(i=0;i<m;i++)fout<<check[i]<<" ";fout<<endl;XB[out]=in;}   while(1){//经验是否达到最优in=-1;inN=Min;for(i=0;i<m;i++)if(check[i]>inN)//找最大的作为换入基{in=i;inN=check[i];}if(inN<=0) break;//检验全比0小,达到最优.退出//找换出基out=-1;outN=Max;for(i=0;i<n;i++){ if(a[i][in]>0) {  if(a[i][m]/a[i][in]<outN)  {  outN=a[i][m]/a[i][in];  out=i;  } }}if(outN==Max) {fout<<"\n无界解\n";break;}//没有换出基,无解.退出temp=a[out][in]; for(i=0;i<=m;i++)  a[out][i]=a[out][i]/temp; for(i=0;i<n ;i++) if(i!=out) { temp=a[i][in]; for(j=0;j<=m;j++)  a[i][j]=a[i][j]-a[out][j]*temp; } temp=check[in]; for(i=0;i<m;i++)  check[i]=check[i]-a[out][i]*temp;fout<<"入X"<<in+1<<" 出X"<<XB[out]+1<<endl;for(i=0;i<n;i++){fout<<z[XB[i]]<<" ";fout<<"X"<<XB[i]+1<<" ";fout<<a[i][m]<<"  ";for(j=0;j<m;j++)fout<<a[i][j]<<"  ";fout<<endl;}fout<<"  Cj-Zj  ";for(i=0;i<m;i++)fout<<check[i]<<" ";fout<<endl;XB[out]=in;}result=0;for(i=0;i<n;i++){//fout<<a[i][m]<<" "<<z[XB[i]]<<" ";result+=a[i][m]*z[XB[i]];}float c[100];for(i=0;i<m;i++)c[i]=0;for(i=0;i<n;i++)c[XB[i]]=a[i][m];for(i=0;i<m;i++)fout<<"X"<<i+1<<"="<<c[i]<<" ";fout<<"\n result="<<result<<endl;}

评论