dcx.cpp

单纯型法程序算法

#include<iostream.h>
#include<stdlib.h>
#define p(i,j)  p[(i)*(n+m+1)+j]
void shuchu(float p[],int m,int n,float s,int ci,int k,int t,int *a)
{ int i,j;
cout<<"No."<<ci<<endl;
if(k!=-1) {cout<<"diao ru ji:"<<k<<endl;
cout<<"diao chu ji:"<<t<<endl;}  
  for(i=-1;i<m+1;++i)
  {     for(j=0;j<m+n+1;++j)
  { if(i==-1&&j<m+n) { cout<<"x"<<j+1<<"          ";continue;}
        if(i==-1&&j==m+n) {cout<<"b"; continue;}
      if(!(i==m&&j==m+n))
	  cout.setf(ios::left);
      cout.setf(ios::fixed);
      cout.width(10);
      cout.precision(4);
		  cout<<p(i,j)<<"  ";
  }   
	  cout<<endl;
  }
  cout<<"ji bian liang is:";
  for(i=n;i<m+n;++i)
	  cout<<"x"<<a[i]+1<<"  ";
  cout<<"\nmax jianyanshu is s:"<<s<<endl;
  cout<<endl;
}
void jianyanshu(float *p,int m,int n)
{ int i,j;
  float s;
  for(j=0;j<m+n;++j)
  {   s=p(m+1,j);
	  for(i=0;i<m;++i)
      s-=p(i,j)*p(m+1,n+i);
	  p(m,j)=s;
  }
}
void main()
{ int m,n,i,j,k1=0,k2=0,*a,k=0,r;//m n分别纪录A行与列k记录迭代次数
  cout<<"intput m n:(AX1+IX2=b,A(m*n))";
  cin>>m>>n;
  float *p,s=0;
  p=new float[(m+2)*(n+m+1)];
  a=new int[m+n];
  cout<<"input A["<<m<<"]["<<n<<"]:"<<endl;
  for(i=0;i<m;++i)
  for(j=0;j<n;++j)
  cin>>p(i,j);
  for(i=0;i<m;++i)
  for(j=n;j<n+m;++j)
  if(j==i+n)  p(i,j)=1;
    else  p(i,j)=0;
  cout<<"input b("<<1<<"....."<<m<<"):"<<endl;
  for(j=0;j<m;++j)
  cin>>p(j,m+n);//最后一列m+n纪录b
  cout<<"input c(c"<<1<<".....c"<<n<<")"<<endl;
  for(j=0;j<n;++j)
  cin>>p(m+1,j);//m+1行纪录c 完成输入
  for(j=n;j<m+n;++j)
	  p(m+1,j)=0;
  for(j=0;j<m+n;++j)
  a[j]=j;//a录变量序号 1->(m-1)列为非基变量 n->(n+m-1)列为基变量
  cout<<"input the number of ren gong bian liang:";
  cin>>r;
  int *rz;
     rz=new int[r];
  if(r!=0)//添加人工变量系数
  {  cout<<"input the xu hao ("<<1<<"->"<<n+m<<")"<<endl;
	 for(i=0;i<r;++i)
		 cin>>rz[i];
	 for(i=0;i<r;++i)
		 if(rz[i]-1>=n) p(m+1,rz[i]-1)=-10000;
  }
  jianyanshu(p,m,n);
  p(m,n+m)=0;p(m+1,n+m)=0;
  s=p(m,a[0]);k1=0;
  for(j=1;j<n;++j)
  if(s<p(m,a[j])) { s=p(m,a[j]);k1=j;}//k1记录换入基a[j]
  shuchu(p,m,n,s,k,-1,-1,a);
  while(s>0)//s记录最大检验数 记在m行
  { if(k>7) {cout<<"N0."<<k<<">20"<<endl;exit(1);}
	  k++;
	  i=0;
	  while(p(i,a[k1])<=0&&i<m) i++;
       if(i==m) { cout<<"it have infinity value";exit(1);}
	   s=p(i,m+n)/p(i,a[k1]);k2=i;//K2+n换出       
	   for(i=i+1;i<m;++i)
       if(p(i,a[k1])>0) if(s>=p(i,m+n)/p(i,a[k1])) 
		   if(s==p(i,m+n)/p(i,a[k1]))  {if(a[k2+n]<n&&a[i+n]>=n)  ;else   {s=p(i,m+n)/p(i,a[k1]);k2=i;}}
	      else   {s=p(i,m+n)/p(i,a[k1]);k2=i;}
       i=a[k1];a[k1]=a[k2+n];a[k2+n]=i;//互换完毕 开始消元
       for(j=0;j<m+n+1;++j)
       {if(j==0) s=p(k2,a[k2+n]);p(k2,j)=p(k2,j)/s;}
	   for(i=0;i<m+1;++i)
	   { if(i==k2) continue;
	     for(j=0;j<m+n+1;++j)
		 { if(j==0) s=p(i,a[k2+n]);p(i,j)-=p(k2,j)*s;}
	   }//消元完毕
       s=p(m,a[0]);
	   for(j=0;j<n;++j)
          if(s<p(m,a[j]))  s=p(m,a[j]);
	   shuchu(p,m,n,s,k,a[k2+n]+1,a[k1]+1,a);
	   s=p(m,a[0]);k1=0;
	   for(j=0;j<n;++j)
          if(s<p(m,a[j])) { s=p(m,a[j]);k1=j;}
   }
   if(r!=0)
  for(i=n;i<m+n;++i)//检验基变量中是否有人工变量
  { k=0;
    for(j=0;j<r;++j)
		if(rz[j]==a[i]+1) k++;
		if(k!=0) {cout<<"wu ke xing jie\n"; exit(1);}
  }
  if(s==0) {cout<<"wu qiong duo zui you jie\n";}
  for(i=n;i<m+n;++i)
   cout<<"x"<<a[i]+1<<"="<<p(i-n,m+n)<<endl;
  s=0;//解的输出
  for(j=n;j<m+n;++j)
	  s+=p(m+1,a[j])*p(j-n,m+n);
  cout<<"max z="<<s<<endl;
}