simplex.cpp

用单纯性法求解线性规划问题

#include<iostream>
#include<cmath>
using namespace std;
#define M 100000
//全局变量
float **kernel;//核心矩阵表
int m=0,n=0,t=0;//m:结构向量的个数
                 //n:约束不等式个数
                 //t:目标函数类型：－1代表求最小值，1代表求最大值
void newspace()   //动态开辟数组
{	
	kernel=new float*[n+2];
	if (kernel==NULL)
	{
		cout<<"对不起，开辟数组不成功！程序结束！"<<endl;
		return ;
	}
	int i;
	for (i=0;i<n+2;i++)
	{
		kernel[i]=new float[m+2*n+1];
		if(kernel[i]==NULL)
		{
			cout<<"对不起，开辟数组不成功！程序结束！"<<endl;
			return ;
		}
	}
}
void delspace()  //释放数组空间
{
	int i;
	for(i=0;i<n+2;i++)
		delete []kernel[i];
	delete []kernel;
}
//输入接口函数
void input()
{
	//读入所求问题的基本条件
	cout<<"－－－－－－－－－－参 数 输 入－－－－－－－－－－－"<<endl;
	cout<<"请按提示输入下列参数："<<endl<<endl;
	cout<<"  变量个数m:  "<<"   m=  ";
	cin>>m;
	cout<<endl<<"  约束不等式数n:"<<"   n=  ";
	cin>>n;
	newspace();
	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代表>=,2表示=）:"<<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++) 
		if(kernel [i][0]<0)
			for(j=0;j<=m+2;j++)
			kernel [i][j]=(-1)*kernel [i][j];	
	for(i=1;i<=n;i++)
	{ 
		kernel [i][m+i]=kernel [i][m+1];
		if(i!=1)
			kernel [i][m+1]=0;
	}
	///*========================
	cout<<"\nkerne矩阵:\n";
	for(i=0;i<n+2;i++)
	{
		for(j=0;j<m+2*n+1;j++)
			cout<<kernel[i][j]<<"\t";
		cout<<endl;
	}
	cout<<"************************"<<endl;
	//========================*/
}
void newellor(float* p)//开辟空间失败处理
{
	if (p==NULL)
	{
		cout<<"对不起，开辟数组不成功！程序结束！"<<endl;
		return ;
	}
}
//算法函数
void comput()
{
	int i,j,flag,temp0,temp1,temp2,h,k=0,*temp3,*is,nl=0;
	float a,*b,temp,*temp4,*temp5,*xb[2],f=0,aa,d,c,q=2;
	cout.precision (4);
	temp3=new int[n+1];
	if (temp3==NULL)
	{
		cout<<"对不起，开辟数组不成功！程序结束！"<<endl;
		return ;
	}
	for(i=0;i<2;i++)
	{
		xb[i]=new float(n);
		newellor(xb[i]);
	}
	temp4=new float[n+2];
	newellor(temp4);
	temp5=new float[n+2];
	newellor(temp5);
	b=new float[n+2];
	newellor(b);
	is=new int[n+1];
	if (is==NULL)
	{
		cout<<"对不起，开辟数组不成功！程序结束！"<<endl;
		return ;
	}
	//初始化
	for(i=1;i<=n;i++)
	{
		temp3[i]=0;
		is[i]=0;
	}
	for(i=0;i<n+2;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;
			nl=nl+1;
		}
		else
		{
			temp3[i]=m+i;
			if(abs(kernel [i][m+i])==2)
			{
				kernel [i][m+i]=1;
				kernel [0][m+i]=-M;
				is[i]=m+i;
			}
		}
	}
    for(i=1;i<=n;i++)
		  temp4[i]=kernel [0][temp3[i]];
	//初始单纯形表
	cout<<endl<<endl;
	cout<<"－－－－－－－－－－单纯形表求解过程－－－－－－－－－－－－"<<endl;
	cout<<"序 "<<"      c    ";
	for(j=1;j<=m+n+nl;j++)
	{
		if(j<=m) cout<<"\t"<<kernel [0][j];
		else if(j<=m+n)	
		{
			if(kernel [0][j]==-M) cout<<"\t-M";
			else cout<<"\t"<<kernel[0][j];
		}
		else 
			cout<<"\t-M"<<"  ";	
	}
	cout<<"\n号 "<<"   cB   xB ";
	for(j=1;j<=m+n+nl;j++) cout<<"\tx"<<j;
	cout<<"\tb"<<"\n-----------------------------------------------------------\n";
	a=0;c=0;temp0=0;
	for(i=1;i<=n;i++)
	{
		if(i==n/2+1) cout<<" 1";
		else cout<<"  ";
		for(j=m+1;j<=m+n+nl;j++)
		if(kernel [i][j]==1)
		{
			if(temp4[i]==-M) 
			cout<<"    -M   x"<<j+temp0;
			else 
			cout<<"    "<<temp4[i]<<"   x"<<j+temp0;
			xb[0][i]=temp4[i];xb[1][i]=j+temp0;
			break;
		}
		else if(kernel [i][j]==-1)
		{
			if(temp4[i]==-M)
			cout<<"    -M   x"<<j+1;
			else 
			cout<<"    "<<temp4[i]<<"   x"<<j+1;
			xb[0][i]=temp4[i];xb[1][i]=j+1;
			temp0=temp0+1;
			break;
		}
		for(j=1;j<=m+n+nl;j++)
		{
			if(j<=m) cout<<"\t"<<kernel [i][j];
			else if(kernel [i][j]==-1) 
			{
				cout<<"\t"<<kernel [i][j]<<"\t"<<kernel [i][m+n+i];
				for(a=j+2;a<=m+n+nl;a++) cout<<"\t"<<0;
				a=j+1;
				c=c+1;				
				break;
			}
			else if(j==a) 
			{
				for(d=1;d<=c;d++) cout<<"\t"<<0;
				cout<<"\t"<<kernel [i][j];
				for(d=j+3;d<=m+n+nl;d++) cout<<"\t"<<0;
				break;
			}
		    else cout<<"\t"<<kernel [i][j];
		}
		cout<<"\t"<<kernel [i][0]<<endl;
	}

	 //循环求解
	do{ 
		cout<<"  "<<" 检验数 "; 
		for(i=0;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+nl;i++)
		{  
			cout<<"\t"<<kernel[n+1][i];
		}
		cout<<"\t"<<kernel[n+1][0];
		cout<<"\n-----------------------------------------------------------\n";
	//=======================
	cout<<"\nkerne矩阵:\n";
	for(i=0;i<n+2;i++)
	{
		for(j=0;j<m+2*n+1;j++)
			cout<<kernel[i][j]<<"\t";
		cout<<endl;
	}
	cout<<"************************"<<endl;
	//=======================
		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&&kernel[0][temp3[i]]!=is[i]) 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<<"， ";
				}
				for(i=1;i<=m;i++)
				{
					if(temp5[i]==0||temp5[i]==1)
						flag=1;
					else
					{
						flag=-1;
						break;
					}
				}
				if(flag==1)
				{
                    cout<<"整数解已达到!"<<endl;
					return;
				}
				if(flag==-1)
				{
					for(j=0;j<=n;j++)
						kernel[j][i]=0;

				}
				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<<"此线性规划无约束"<<endl;
			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;
				}
			}
			xb[1][k]=h;
			xb[0][k]=kernel[0][h];
			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]; 
			}
			a=0;c=0;temp0=0;
			for(i=1;i<=n;i++)
			{
				if(i==n/2+1) cout<<" "<<q;
				else cout<<"  ";
				if(xb[0][i]==-M) cout<<"    -M   x"<<xb[1][i];
				else cout<<"    "<<xb[0][i]<<"   x"<<xb[1][i];
				for(j=1;j<=m+n+nl;j++)
				{
					if(j<=m) cout<<"\t"<<kernel [i][j];
					else if(kernel [i][j]==-1) 
					{
						cout<<"\t"<<kernel [i][j]<<"\t"<<kernel [i][m+n+i];
						for(a=j+2;a<=m+n+nl;a++) cout<<"\t"<<0;
						a=j+1;
						c=c+1;				
						break;
					}
					else if(j==a) 
					{
						for(d=1;d<=c;d++) cout<<"\t"<<0;
						cout<<"\t"<<kernel [i][j];
						for(d=j+3;d<=m+n+nl;d++) cout<<"\t"<<0;
						break;
					}
					else cout<<"\t"<<kernel [i][j];
				}
				cout<<"\t"<<kernel [i][0]<<endl;
			}
			q=q+1;
		}
		
	}
while(1);
delspace();
delete []temp3;
delete []temp4;
delete []temp5;
delete []is;
delete []xb[0];
delete []xb[1];
delete []b;
return ;
}
//主函数
void main()
{ cout<<"-------------------单纯形法算法程序----------------------"<<endl<<endl;
  input();
  comput();
 }