danchunxing.cpp

单纯形算法

//主要函数文件
//函数说明
/******************************************************
	函数功能:
		 利用单纯形法计算,以化为标准行的 线性规划问题
	注意:此函数只解决求最大值问题,线性规划问题的变量的下标
		 是从0开始的,与书上的从1开始有一点点差别
	参数说明:
		 C [IN]为指向价值系数的指针
		 A [IN]为约束条件的系数矩阵
		 b [IN]为约束条件的限额系数
		 Xb [IN OUT]传入初始基对应的变量,返回最优解对应变量
		 n [IN]为变量个数
		 m [IN]为约束条件个数
*******************************************************/
float DanChunXing(float *C,float A[MAX_G][MAX_G],float *b,int *Xb,int n,int m)
{
	float *jys=new float[n];//检验数
	float *Cb=new float[m];	//基变量价值系数
	float *st=new float[m];	//θ检验
	float OptValue=0,sum=0,min,max,mz,temp,tmp;
	int i,j,h,l;
	while(1)
	{	
		for(i=0;i<m;i++)//计算基对应的价值系数
			*(Cb+i)=(*(C+*(Xb+i)));
		for(i=0;i<n;i++)//计算检验数
		{
			sum=0;
			for(j=0;j<m;j++)
				sum+=*(Cb+j)*A[j][i];
			*(jys+i)=*(C+i)-sum;
		}
		//求检验数中的最大值
		max=*jys;
		h=0;
		for(i=1;i<n;i++)
			if(max<*(jys+i))
				{	
					max=*(jys+i);
					h=i;//存入换入变量的下标
				}
		if(max<=0)//判断检验数 若全非正
		{
			for(j=0;j<m;j++)
				OptValue+=*(Cb+j)*(*(b+j));//计算最优值
			return OptValue;
		}
		else		//若不全非负 继续求解
		{
			mz=A[0][h];//求P列中最大值是否为负
			for(i=1;i<m;i++)
				if(mz<A[i][h])
					mz=A[i][h];
			if(mz<0)	//如果为负有无界解 返回0
				return 0;
			else		//对约束条件矩阵做变换
			{
				for(i=0;i<m;i++)//选取换出变量
					if(A[i][h]>0)
						*(st+i)=*(b+i)/A[i][h];
					else
						*(st+i)=9999999;
				min=*st;
				l=0;
				for(i=1;i<m;i++)
					if(min>*(st+i))
					{	
						min=*(st+i);
						l=i;//存入换出变量的下标
					}
				*(Xb+l)=h;
				temp=A[l][h];//开始矩阵变换
				*(b+l)=*(b+l)/temp;
				for(i=0;i<n;i++)
					A[l][i]=A[l][i]/temp;
				for(j=0;j<m;j++)
				{	
					if(j!=l)
					{	
						tmp=A[j][h];
						for(i=0;i<n;i++)
							A[j][i]=A[j][i]-A[l][i]*tmp;
						*(b+j)=*(b+j)-*(b+l)*tmp;
					}
				}//结束矩阵变换
			}
		}
	}
}