dcxf.doc

自己编的一个运筹学中单纯形法的一个程序,界面友好,按照提示来输入参数,可以解决很多线性规划问题

//在Visual C++控制台程序中编译执行
#include<iostream.h>
#include<math.h>
#define M 10000
//全局变量
 float kernel[11][31];//核心矩阵表
 int m=0,n=0,t=0;//m:结构向量的个数
                 //n:约束不等式个数
                 //t:目标函数类型：－1代表求求最小值，1代表求最大值
//输入接口函数
void input()
{
	 //读入所求问题的基本条件
  cout<<"－－－－－－－－－－参 数 输 入－－－－－－－－－－－"<<endl;
  cout<<"请按提示输入下列参数："<<endl<<endl;
	cout<<"  结构向量数m:  "<<"   m=  ";
	cin>>m;
	cout<<endl<<"  约束不等式数n:"<<"   n=  ";
	cin>>n;
   int i,j;
   //初始化核心向量
   for (i=0;i<=n+1;i++)
    for (j=0;j<=m+n+n;j++) 
	     kernel [i][j]=0;
   //读入约束条件
   cout<<endl<<"  约束方程矩阵的系数及不等式方向（1代表<=,-1代表>=）:"<<endl<<endl<<"          ";
   for (i=1;i<=m;i++)
	   cout<<"   x"<<i;
       cout<<"  不等式方向 "<<" 常数项"<<endl;
   for (i=1;i<=n;i++) 
	{ 
	  cout<<"    不等式"<<i<<"  ";
	  for (j=1;j<=m+2;j++) 	
		  cin>>kernel [i][j];
	}

  for (i=1;i<=n;i++)
	 { 
	   kernel [i][0]=kernel [i][m+2];
	   kernel [i][m+2]=0;
	 }
  //读入目标条件
  cout<<endl<<endl<<" 目标函数的系数及类型（求最小值:1；求最大值:-1）:"<<endl<<endl<<"                ";
   for(i=1;i<=m;i++)
	    cout<<"x"<<i<<"   ";
  cout<<"类型"<<endl<<"  ";
  cout<<"  目标函数:   ";
   for (i=1;i<=m;i++)
	 cin>>kernel [0][i];
     cin>>t;
  //矩阵调整
  if(t==-1) 
	  for(i=1;i<=m;i++) 
		  kernel [0][i]=(-1)*kernel [0][i];
  for(i=1;i<=n;i++)
  { 
	  kernel [i][m+i]=kernel [i][m+1];
         if(i!=1)
			 kernel [i][m+1]=0;
  }
}

//算法函数
void comput()
{
	int i,j,flag,temp1,temp2,h,k=0,temp3[10];
	float a,b[11],temp,temp4[11],temp5[11],f=0,aa,d,c;
	//初始化
  for(i=1;i<=n;i++) 
     temp3[i]=0;
   for(i=0;i<11;i++)
   {    temp4[i]=0;
	   temp5[i]=0;
   }
    for(i=1;i<=n;i++)
  {
	 if(kernel [i][m+i]==-1)
	  {
		kernel [i][m+n+i]=1;
	    kernel [0][m+n+i]=M;
		temp3[i]=m+n+i;
	  }
     else 
		 temp3[i]=m+i;
  }
     for(i=1;i<=n;i++)
		   temp4[i]=kernel [0][temp3[i]];

	 //循环求解
do{   
    for(i=1;i<=m+n+n;i++)
	  {  
	    a=0;
	    for(j=1;j<=n;j++)
	       a+=kernel [j][i]*temp4[j];
	       kernel [n+1][i]=kernel [0][i]-a;
		}
    for(i=1;i<=m+n+n;i++)
		 {
			if(kernel [n+1][i]>=0) flag=1;
	         else 
			 {  
				 flag=-1;
			     break;
			 }
		  }
	if(flag==1)
	{     for(i=1;i<=n;i++)
	         { 
		          if(temp3[i]<=m+n) temp1=1;
                            else
							  { 
							      temp1=-1;
						          break;
							   }
	          }
	//输出结果
	cout<<endl<<endl;
	cout<<"－－－－－－－－－－结 果 输 出－－－－－－－－－－－"<<endl<<endl;
	    if(temp1==1)
		   { 
			  cout<<" 此线性规划的最优解存在!"<<endl<<endl<<"  最优解为："<<endl<<endl<<"     ";
		      for(i=1;i<=n;i++)
			     temp5[temp3[i]]=kernel [i][0];
			  for(i=1;i<=m;i++)
			     f+=t*kernel [0][i]*temp5[i];
			 
			  for(i=1;i<=m;i++) 
			  {
				 cout<<"x"<<i<<" = "<<temp5[i];
				 if(i!=m)
					 cout<<"， ";
			  }
		      cout<<" ;"<<endl<<endl<<"     最优目标函数值f= "<<f<<endl<<endl;
			  return ;
            }
		    else 
			{   
				cout<<" 此线性规划无解"<<endl<<endl;
		        return ;
			}
	  }
   if(flag==-1)
   {   
	   temp=100000;
	   for(i=1;i<=m+n+n;i++)
		  if(kernel [n+1][i]<temp)    
			{
			  temp=kernel [n+1][i];
			  h=i;                    
			}
             
	    for(i=1;i<=n;i++)
		  {	
			if(kernel [i][h]<=0) temp2=1;
		        else { 
					          temp2=-1;
				              break;
					}                       
		  }
   }
	if(temp2==1)  
	 { 
		cout<<"此线性规划无约束";
	     return  ;
	 }
   if(temp2==-1) 
   {   
	  c=100000;
	  for(i=1;i<=n;i++)
		{
		   if(kernel [i][h]!=0)  b[i]=kernel [i][0]/kernel [i][h];
		   if(kernel [i][h]==0)  b[i]=100000;
		   if(b[i]<0)     b[i]=100000;
		   if(b[i]<c) 
		   {
			   c=b[i];
			   k=i;
		   }
	  }
	     temp3[k]=h;
		 temp4[k]=kernel [0][h];
         d=kernel [k][h];
      for(i=0;i<=m+n+n;i++)
		kernel [k][i]=kernel [k][i]/d;
	  for(i=1;i<=n;i++)
	  {	 if(i==k) 
	     continue;
	     aa=kernel [i][h];
	     for(j=0;j<=m+n+n;j++)
		    kernel [i][j]=kernel [i][j]-aa*kernel [k][j]; 
	  }
   } 
   
}
while(1);
	 return ;
}

//主函数
void main()
{ cout<<"-------------------单纯形算法程序----------------------"<<endl<<endl;
  input();
  comput();
}