#include<iomanip.h>
#include <fstream.h>
#define Min -99999
#define Max 99999
int 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();
}

评论