simplix.cpp

线性约束方程组,单纯形人工变量法(用类写的)用文件输入输出的

// Simplix.cpp: implementation of the CSimplix class.
//
//////////////////////////////////////////////////////////////////////

#include "Simplix.h"
#include<iostream.h>
#include<math.h>
#include<fstream.h>
#include<iomanip.h>
#define MAX 1000000
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
void CSimplix::Input()
{
 ifstream fin("in.txt",ios::nocreate);
 //...
  if(fin.fail())
  {
   cerr<<"error opening file myname";
   return;
  }
//结构向量数m: 约束不等式数n:
   fin>>m>>n;  
//读入约束方程矩阵的系数及不等式方向（最后一个参数1代表<=,-1代表>=,0代表＝）:
    //不等式
   for (int i=1;i<=n;i++) 
	{   
	  for (int j=1;j<=m+2;j++) 	
		  fin>>List[i][j];
	}     
//读入目标函数的系数及类型（求最小值:1；求最大值:-1）
  for (i=1;i<=m;i++)
	 fin>>List[0][i];
     fin>>type;
     InitMatrix();
}
void CSimplix::InitMatrix()
{ //假定每一个变量都是大于0的
   double temp;
   int i,j,t,t1;
//添加松弛变量，找出人工变量
   for (i=1;i<=n;i++)
   { 
	   temp=List[i][m+2];       
	   List[i][0]=List[i][m+1];
       List [i][m+1]=0;
	   List [i][m+2]=0;
	   if (List[i][0]<0)
         for (j=0;j<=m;j++) List[i][j]=List[i][j]*(-1);
	
	  if (temp==-1)
			{		   
		     indexAdd++;
		     t=m+indexAdd;	   
             List[i][t]=1;
			 base[i]=t;
			}
       if (temp==1)
			{
		        indexAdd++;
                 t=m+indexAdd;           
                List[i][t]=-1;
	           indexManu++;
		         manu[indexManu]=i;                 
			}   
      if (temp==0)
			{
	           indexManu++;
	            manu[indexManu]=i;
			}
   } 
   index=m+indexAdd+indexManu;
 //添加人工变量
   for (i=1;i<=indexManu;i++)
   {
	 t1=manu[i];
	 t=m+indexAdd+i;
	 List[t1][t]=1;
	 List[n+1][t]=1;
     base[t1]=t;
   }
//修正目标函数
  if (type==1)
    for(i=1;i<=m;i++) 
      List[0][i]=(-1)*List[0][i];

}
void CSimplix::Write(double f)
{
     if (fabs(f-(long)f)<1e-8) 
	 {   
		cout<<setiosflags(ios::fixed);
		cout<<setw(5)<<setprecision(0)<<f<<" ";}
	 else
	 {  cout<<setiosflags(ios::fixed);
	    cout<<setw(5)<<setprecision(2)<<f<<" ";
	 }
}
void CSimplix::ShowList()
{
 cout<<"--------------------showlist----------------------"<<endl;
 for (int i=1;i<=n+1;i++)
  {	 
  for (int j=1;j<=index;j++) Write(List[i][j]);	  
  Write(List[i][0]);
  cout<<endl;
  }

}
void CSimplix::Comput()
{
//阶段1 使T最小
  while(!CheckBest())
  {   
	  
	  ShowList();
	  ModifyBase();   
  }
//阶段2 使目标函数最小
  for (int i=1;i<=index;i++)
  {
  List[n+1][i]=List[0][i];
  index=m+indexAdd;//去处人工变量
  }
  while(!CheckBest())
  {
	  ModifyBase();   
  }  
}
void CSimplix::ModifyBase()
{
double min=0,temp;
int t=0,j,i,l;
 for (j=1;j<=index;j++)
	 if (List[n+1][j]<min) { min=List[n+1][j];t=j;}
 min=MAX;l=0;
 for (i=1;i<=m;i++) 
  if (List[i][t]>0)
  {
	  check[i]=List[i][0]/List[i][t];
     if (check[i]<min)
	 { min=check[i];l=i;} 
  }
  cout<<t<<"  "<<l<<endl;
  if (List[t][l]!=0)
  {  
	  temp=List[t][l];
    for (j=0;j<=index;j++) 
       List[t][j]=List[t][j]/temp;
    for (i=1;i<=m;i++)
	  if (i!=t) 
	  {   
          temp=List[i][l];
		  for (j=0;j<=index;j++) List[i][j]-=temp*List[t][j];	  
	  }       
  }
  base[l]=t;
   ShowList();

}
bool CSimplix::CheckBest()
{
int i,j,t;
double temp,min;
 for (i=1;i<=m;i++) 
 {
	 t=base[i];
	 temp=List[n+1][t];
	 if (fabs(temp)>1e-8)
	 {
	 for (j=0;j<=index;j++) 
		 List[n+1][j]-=temp*List[i][j];
	 }
 }
 min=0;t=0;
 for (j=1;j<=index;j++)
	 if (List[n+1][j]<min) { min=List[n+1][j];t=j;}
  if (min==0) 
	return true;
   else 
	return false;

}