mysimplex.cpp

单纯形法：为求解线性规划问题的通用方法。一般在数学建模课上老师要求实现

#include"mySimplex.h"
MySimplex::MySimplex()
{
	//非数组成员初始化
	indexe = 0;//剩余变量个数
	indexl = 0;//人工变量个数
	indexg = 0;//人工变量个数
	indexe2 = 0;//割平面法迭代时的新增剩余变量个数
	selectinput = -1;
	//数组成员初始化
	//matrix,x,code,b,a
	int i = 0;
	int j = 0;
	for (i = 0; i < BOUND; i++)
	{
		code[i] = 0;
		b[i] = 0;
		a[i] = 0;
		for (j = 0; j <	BOUND; j++)
		{
			matrix[i][j] = 0;
		}
	}

}

/////////////////////////////////
void MySimplex::printMatrix(void)
{
	cout<<"现在的规划模型的矩阵为："<<endl;
	for(int line = 0; line < s+1; line++)
		cout<<"--";
	cout<<endl;
	for(int i = 0; i <= n; i++)
	{
		for(int j = 0; j <= s; j++)
		{
			cout<<matrix[i][j]<<',';//输出所有方程的所有系数
		}		
		cout<<endl;
	}
	for(int line2 = 0; line2 < s+1; line2++)
		cout<<"--";
	cout<<endl;
}
//////////////////////////////////////////
void MySimplex::jckxj()//基础可行解
{//获取方程的基础可行解到x[i]中
	int i,j;
	for(i=0;i<n;i++)
	{//选取第i行限制方程的基础解变量
		for(j=0;j<s;j++)
		{
			if(matrix[i][j]==1&&a[j]==1)
			{//扫描第i个方程的第j列如果系数为1并且是本行(新)特征的基础解变量
				//把第j个解向量设置为矩阵的最后一列也就是常数项
				x[j]=matrix[i][s];
				//j=s;//结束本行的循环
				break;//取代j = s自己改
			}
		}
		//b[i]=matrix[i][s];//////调试
	}
	for(j=0;j<s;j++)
	{
		if(a[j]==0)
			x[j]=0;//s不是基础变量的解设置为0
	}
	cout<<"在基础可行解函数内部最后获得的基础可行解是："<<endl;
	cout<<"【";
	for(j = 0; j<s; j++)
	{
		cout<<x[j]<<',';
	}
	cout<<'\b'<<"】"<<endl;	
}
/////////////////////////////////////////////////
int MySimplex::rj()//规划模型的系数是否没有负数
{//规划模型（即非约束条件等式）的系数是否没有负数，是则返回1，否则返回0
int i;
for(i=0;i<s;i++)
	if(fabs(matrix[n][i])>=0.000001)
		if(matrix[n][i]<0)//如果规划模型第i个位置的系数绝对值非0并且是负数
			return 0;
return 1;//规划模型没有负数的系数的情况
}
////////////////////////////////////////////
int MySimplex::Min()
{//求规划模型中最小（负）的系数，用于作为换入变量，返回它的位置列下标
int i,temp=0;
double min=matrix[n][0];
//double min=0;//因为取得是最小负数，所以初始min为0，自己改写原来的matrix[n][0]为0
for(i=1;i<s;i++)
{
	if(min>matrix[n][i])
	{
		min=matrix[n][i];
		temp=i;
	}
}

return temp;
}
/////////////////////////////////
int MySimplex::JustArtificial()//检查人工变量是否有正，确定原问题有无最优解
{//当寻找换入变量的时候系数若全部非负，则查看人工变量是否有正值，有则表示无解返回1，无则获取最优解。
	int i;
	for(i=m+indexe+indexl;i<s;i++)
	{
		if(fabs(x[i])>=0.000001)
		{//如果有一个人工变量大于0就可以断定没有最优的结果
			cout<<"没有最优解!\n";//无解
			return 1;
		}
	}
	return 0;
}
/////////////////////
int MySimplex::Check(int in)//选取出基变量之前的检验
{//入基变量列数in,选取出基变量之前，如果选取换出变量的时候没有非负比值则函数无上界，无解返回1
	int i;
	double maxl=-1;//最大的负整数
	for(i=0;i<n;i++)
	{
		//每个方程常数项与非0的入基位置的系数之比比较选取最大是否比maxl（一个最大的负整数）大
		if(fabs(matrix[i][in])>=0.000001&&maxl<matrix[i][s]/matrix[i][in])
			maxl=matrix[i][s]/matrix[i][in];//因为maxl最大负整数，如果有一个使得maxl改变则说明有正的
	}
	if(maxl<0)
		return 1;//如果比较之后全负的结果则函数无上界，返回
	return 0;//如果比较之后有正数的结果则可以选取换出变量
}
///////////////////////////////////////////
int MySimplex::SearchOut(int *temp,int in)//出基变量
{//输入入基变量所在的列,然后再通过选举得出基变量的行数存到temp,返回列数
	int i;
	double min=10000;
	for(i=0;i<n;i++)
	{
		if(fabs(matrix[i][in])>=0.000001&&(matrix[i][s]/matrix[i][in]>=0)
			&&min>matrix[i][s]/matrix[i][in])
		{
			min=matrix[i][s]/matrix[i][in];
			*temp=i;//取得最小比值的位置 （行数）
		}
	}
	for(i=0;i<s;i++)
	{
		if(a[i]==1&&matrix[*temp][i]==1)
		{//得到最小比值位置的出基变量并返回列数原先是a[i]=1,现在改成a[i]==1
			return i;
		}
	}
	return -1;

}
/////////////////////////////////
void MySimplex::Mto(int in,int temp)
{//in是入基变量列数，temp是出基变量的方程行数,把这个方程进行初等变换使入基变量的对应系数为1
int i;
for(i=0;i<=s;i++)
{
	if(i!=in)
	{
		//如果不是入基变量的位置则把这个方程的其他除以那个入基变量
		matrix[temp][i]=matrix[temp][i]/matrix[temp][in];
		if(i==s)
		{
			b[temp] = matrix[temp][in];//为了割平面法，自己添加////////调试
		}
	}
}
matrix[temp][in]=1;//入基变量的位置处的系数置为1
}
/////////////////////////////
void MySimplex::Be(int temp,int in)//初等变换。出基变量的行数temp,入基变量的列数in
{//把所有的方程初等变换,可以消去非主元方程的入基变量
int i,j;
double c;
for(i=0;i<=n;i++)
{
	c=matrix[i][in]/matrix[temp][in];
	if(i!=temp)
	{
		for(j=0;j<=s;j++)
		{
			if(fabs(matrix[i][j]-matrix[temp][j]*c)<=0.000001)
            {//防止浮点数出现特别小的数不表示为0，而表示为2.2×10E-16 
               matrix[i][j] = 0;
            }
            else
            {
            matrix[i][j]=(matrix[i][j]-matrix[temp][j]*c);
            }
            if(j==s)
			{
				b[i] = matrix[i][j]/1;//为了割平面法，自己添加////////调试
			}
		}
	}
}
}
//////////////////////////
void MySimplex::Achange(int in,int out)//出基入基转换in--入基列数，out--出基列数
{//a是表示基础变量，把入基的变成基础变量，而淘汰出基
//int temp=a[in];
//a[in]=a[out];
//a[out]=temp;

//以下是自己改写的，原来是上面的。
a[in] = 1;
a[out] = 0;
}

/////////////////////////////////////
//把>=方程取反
void MySimplex::JustUpper()
{
	int i = 0;
	int j = 0;
	for(i = 0; i < n; i++)
	{
		if(code[i] == 2)
		{
			for(j = 0; j <= s; j++)
			{
				matrix[i][j] = -matrix[i][j];
			}
			code[i] =0;
			b[i] = -b[i];
		}
	}
}
/////////////////////////////////////
//把负常数方程取反
void MySimplex::JudgeNegative()
{
	int i = 0;
	int j = 0;
	for(i = 0; i < n; i++)
	{
		if(b[i] < -0.000001)
		{
			for(j = 0; j <= s; j++)
			{
				matrix[i][j] = -matrix[i][j];
			}
			if(code[i] == 0)
			{
				code[i] = 2;
			}
			if(code[i] == 2)
			{
				code[i] =0;
			}
			b[i] = -b[i];
		}
	}
}
/////////////////////////////////////
void MySimplex::ChangeForm(void)
{//把方程标准化为常数正或全<=，并写道fileout.txt
	int i = 0;
	int j = 0;
	ofstream fout("fileout.txt");//自己改写的输出调整后的文件
	JudgeNegative();//转为常数项全正
	JustUpper();//转为小于号
	fout.setf(ios::left,ios::adjustfield);
	fout<<m<<endl;//
    fout<<n<<endl;//
    for(i=0;i<n;i++)
	{
		//cout<<"第"<<i<<"行：\n----------------"<<endl;
		//cout<<"请输入限制条件矩阵第"<<i<<"行的系数\n";
		for(j=0;j<m;j++)
		{
			
			fout<<setw(5)<<matrix[i][j];//输入限制方程的系数
		}
		//cout<<"第"<<i<<"行的系数部分已经确定"<<endl;
		//cout<<"请输入限制条件矩阵的第"<<i<<"行的条件的类型：0表示<=，1表示=，2表示>=\n";
		fout<<setw(5)<<code[i];
		//cout<<"请输入限制条件矩阵的第"<<i<<"行的常量部分\n";
		fout<<setw(5)<<b[i];
		fout<<endl;
		//cout<<"第"<<i<<"行的常数部分和不等式类型已经确定\n----------------"<<endl;
	}	
	for(i=0;i<m;i++)//////改i=0为j=0
		fout<<setw(5)<<matrix[n][i];//输入规划模型的方程,此时要注意要把所有的系数移到z的同侧
	fout.setf(ios::right,ios::adjustfield);
	
}
////////////////////////
//void Print()
//{//打印所有方程的所有系数，并且如果含有基础界变量的方程就也输出它的号码
//	int i,j,k,temp=0;
//	for(i=0;i<n;i++)
//	{//处理第i个方程
//		for(k=temp;k<s;k++)
//			if(a[k]==1)
//			{//当k处1时终止本循环并记录下次进入循环的开始点
//				cout<<k;//??当它是含有基础解变量的方程的时候输出含有基础解变量方程的号数??位置??
//				temp=k+1;
//				k=s;
//			}
//		for(j=0;j<=s;j++)
//			cout<<matrix[i][j];//输出所有方程的所有系数
//		cout<<"\n";
//	}
//	cout<<"Rj";
//	for(j=0;j<=s;j++)
//		cout<<matrix[n][j];//输出规划模型的方程的系数
//	cout<<"\n";

////////////////////////
//void InitPrint()
//{
//	int i;
//	cout<<"X";
//	for(i=0;i<s;i++)
//		cout<<i;
//	cout<<"b\n";
//	cout<<" ";
//	cout<<"\n";

//////////////////
void MySimplex::Result()
{//打印解当前的向量结果和最大/最小值