mysimplex.cpp

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

	int i;
	cout<<"当前可行解向量为：(";
	for(i=0;i<s;i++)
	{
		cout<<x[i]<<',';
	}
	cout<<'\b'<<")"<<endl;
	if(type==1)
		cout<<"Zmax="<<matrix[n][s];
	else 
		cout<<"Zmin="<<-matrix[n][s];
	cout<<endl;
}
//////////////////////
void MySimplex::PrintResult()
{//打印最后的最优最大最小值
	cout<<"得到最优解，"<<endl;
	int i = 0;
	cout<<"可行解向量为：【";
	for(i=0;i<s;i++)
	{
		cout<<x[i]<<',';
	}
	cout<<'\b'<<"】"<<endl;
	if(type==0)
	{
		cout<<"最小值为:"<<-matrix[n][s]<<endl;//自己改，认为最小值应该是取相反数
	}
	else 
		cout<<"最大值为:"<<matrix[n][s]<<endl;
}
////////////////////////////////
//合并，把后添加的三种变量分矩阵和常数项加入原方程矩阵,以便形成可以使用单纯型法的矩阵
void MySimplex::Merge(double nget[][BOUND],double nlet[][BOUND],double net[][BOUND],double b[])
{//nget--剩余变量的矩阵分量;nlet--松弛变量的对应矩阵分量;net--人工变量的对应矩阵分量，b--常数项的分量;
	int i,j;
	for(i=0;i<n;i++)
	{
		//if(index2 == 0)
	//	{
			for(j=m /*+ indexe - indexe2*/;j<m+indexe;j++)//剩余变量填入限制方程的系数矩阵-1
			{
				if(nget[i][j-m]!=-1)matrix[i][j]=0;
				else matrix[i][j]=-1;
			}
	//	}
		/*else
		{
			for(j=m;j<m+indexe;j++)//剩余变量填入限制方程的系数矩阵-1
			{
				if(nget[i][j-m]!=-1)matrix[i][j]=0;
				else matrix[i][j]=-1;
			}
		}*/
		for(j=m+indexe;j<m+indexe+indexl;j++)//松弛变量填入限制方程的系数矩阵1
		{
			if(nlet[i][j-m-indexe]!=1)matrix[i][j]=0;
			else matrix[i][j]=1;
		}
		for(j=m+indexe+indexl;j<s;j++)
		{
			if(net[i][j-m-indexe-indexl]!=1)matrix[i][j]=0;//人工变量填入限制方程的系数矩阵1
			else matrix[i][j]=1;
		}
		matrix[i][s] = b[i];//自己添加的，把常数项分量加入到矩阵当中
	}
	for(i=m;i<m+indexe+indexl;i++)
	{
		matrix[n][i]=0;
	}
	for(i=m+indexe+indexl;i<s;i++)
	{
		matrix[n][i]=100;//人工变量的位置在规划模型当中的调整
	}
	matrix[n][s]=0;
}

///////////////////////////
void MySimplex::ProcessA()//初始a[]
{//a[s]中的前m个为0以后为1
	int i;
	for(i=0;i<m+indexe;i++)
	{//原变量和剩余变量的都是非基础变量
		a[i]=0;
	}
	for(i=m+indexe;i<s;i++)
		a[i]=1;
}

////////////////////////////////
void MySimplex::InputFile()
{//从文件读取数据
int i;
int j;
char filename[256];
cout<<"请输入文件名称(含扩展名):"<<endl;
cin>>filename;
ifstream fin(filename);
while(!fin)
{
	cout<<"文件不存在！请重新输入！"<<endl;
	cin>>filename;
	fin.clear();
	fin.open(filename);	
}
//调试
//ofstream fout("fileout.txt");//自己改写的输出调整后的文件
//ifstream fin(filename);
    fin>>m;//
    fin>>n;//
    for(i=0;i<n;i++)
	{
		//cout<<"第"<<i<<"行：\n----------------"<<endl;
		//cout<<"请输入限制条件矩阵第"<<i<<"行的系数\n";
		for(j=0;j<m;j++)
			fin>>matrix[i][j];//输入限制方程的系数
		//cout<<"第"<<i<<"行的系数部分已经确定"<<endl;
		//cout<<"请输入限制条件矩阵的第"<<i<<"行的条件的类型：0表示<=，1表示=，2表示>=\n";
		fin>>code[i];
		//cout<<"请输入限制条件矩阵的第"<<i<<"行的常量部分\n";
		fin>>b[i];
		//cout<<"第"<<i<<"行的常数部分和不等式类型已经确定\n----------------"<<endl;
	}
	cout<<"请输入类型 0:最小值 1:最大值\n";
	do{
		cin>>type;
		if(type!=0&&type!=1)
			cout<<"error,ReInput!\n";
	}while(type!=0&&type!=1);
	//cout<<"请输入规划模型方程的系数：\n";
	for(i=0;i<m;i++)//////改i=0为j=0
		fin>>matrix[n][i];//输入规划模型的方程,此时要注意要把所有的系数移到z的同侧
	if(type==0)//自己改，当原规划模型求的是最小值的时候（不是最大值）把它们的系数取反即可
		for(i=0;i<m;i++)
			matrix[n][i]=-matrix[n][i];
	s=m;
	ChangeForm();
	//调试
	printMatrix(); 
}
////////////////////////////////
void MySimplex::Input(double b[],int code[])
{//输入数据
	int i=0;int j=0;
	cout<<"请输入原规划模型变量个数：\n";
	cin>>m;
	cout<<"请输入限制条件方程个数：\n";
	cin>>n;
	cout<<"----------------"<<endl;
	for(i=0;i<n;i++)
	{
		cout<<"第"<<i<<"行：\n----------------"<<endl;
		cout<<"请输入限制条件矩阵第"<<i<<"行的系数\n";
		for(j=0;j<m;j++)
			cin>>matrix[i][j];//输入限制方程的系数
		cout<<"第"<<i<<"行的系数部分已经确定"<<endl;
		cout<<"请输入限制条件矩阵的第"<<i<<"行的条件的类型：0表示<=，1表示=，2表示>=\n";
		cin>>code[i];
		cout<<"请输入限制条件矩阵的第"<<i<<"行的常量部分\n";
		cin>>b[i];
		cout<<"第"<<i<<"行的常数部分和不等式类型已经确定\n----------------"<<endl;
	}
	cout<<"请输入类型 0:最小值 1:最大值\n";
	do{
		cin>>type;
		if(type!=0&&type!=1)
			cout<<"error,ReInput!\n";
	}while(type!=0&&type!=1);
	cout<<"请输入规划模型方程的系数：\n";
	for(i=0;i<m;i++)//////改i=0为j=0
		cin>>matrix[n][i];//输入规划模型的方程,此时要注意要把所有的系数移到z的同侧
	if(type==0)//自己改，当原规划模型求的是最小值的时候（不是最大值）把它们的系数取反即可
		for(i=0;i<m;i++)
			matrix[n][i]=-matrix[n][i];
	s=m;
	printMatrix();
} 


////////////////// 
void MySimplex::Xartificial()//消去人工变量
{//这样之后可以满足单纯型法的条件，进而使用单纯型法
	int i,j,k;
	if(indexg!=0)
	{//如果存在人工变量就开始为规划模型消除人工变量
		for(i=m+indexe+indexl;i<s;i++)
		{
			for(j=0;j<n;j++)
				if(matrix[j][i]==1)
				{//如果第j个方程中的第i个变量位置是人工变量
					for(k=0;k<=s;k++)
					{
						matrix[n][k]=matrix[n][k]-matrix[j][k]*100;//在非约束方程中消去相应第j个方程的人工变量。
						if(k == s)
						{
							b[n] = matrix[n][k];////////////调试
						}
					}
					j=n;//消去之后终止循环开始下一方程的人工变量消除
				}
		}
	}
}

////////////////////////////////////////////////
void MySimplex::Process(double c[][BOUND],int row,int vol)
{//除了第row个方程之外的所有限制方程的第vol列的系数都置为0
	int i;
	for(i=0;i<n;i++)
		if(i!=row)c[i][vol]=0;
}

//////////////////////
void MySimplex::Start(double b[],int code[])
{//把原始方程化为可以进行单纯型方法的方程
	int i;
	//nget--剩余变量的对应矩阵分量;nlet--松弛变量的对应矩阵分量;net--人工变量的对应矩阵分量;
	double nget[BOUND][BOUND],nlet[BOUND][BOUND],net[BOUND][BOUND];
	//JudgeNegative();////////////自己添加调试错误
	//indexe=indexl=indexg=0;///////////去掉变为全局调试
	for(i=0;i<n;i++)
	{
		//如果第i个限制方程变量对应的是松弛变量则把松弛变量矩阵相应方程相应松弛变量的位置置1其他列位置置0
		if(code[i]==0){nlet[i][indexl++]=1;Process(nlet,i,indexl-1);code[i] = -1;}
		//如果变量对应的是人工变量则把人工变量矩阵??indexg初始值成了负数??
		if(code[i]==1){net[i][indexg++]=1;Process(net,i,indexg-1);}//改indexl++为indexg++///////
		//如果变量对应的是剩余变量则把人工变量矩阵和剩余变量矩阵??indexg初始值成了负数??
		if(code[i]==2){
			net[i][indexg++]=1;//先人工??
			nget[i][indexe++]=-1;//再剩余??
			Process(net,i,indexg-1);Process(nget,i,indexe-1);//改nlet为nget///////
		}
	}
	s=indexe+indexl+indexg+m;//s成为添加之后的全部变量的个数??
	Merge(nget,nlet,net,b);//??把三个矩阵分量加到原来的矩阵上面，实现方程可以用单纯型法
	ProcessA();//初始a[]
	//InitPrint();
	Xartificial();//消去人工变量
}

/////////////////////////////////////
int MySimplex::Simplix()//单纯形法
{//有解返回1，无解返回0
	int in,out,temp=0;//入基列位置，出基列位置， 出基行位置 
	while(1)
	{   
		jckxj();//获取基础可行解
		/////////调试 
		cout<<"单纯型法内部获取基础可行解之后的矩阵："<<endl; 
        printMatrix();
		Result();//打印当前的结果
		//如果规划模型第i个位置的系数绝对值非0并且是负数，取最负的系数变量作为换入变量系数位置存放到in变量里面
		if(!rj()) 
		{//如果规划模型的系数有负数
			in=Min();//选取最负的作为入基变量系数
		}
		else
		{//规划模型没有负数的系数的情况
			if(indexg!=0)
			{//存在人工变量
				int havePositive = JustArtificial();//如果人工变量有大于0则无解返回
				if(havePositive == 1)
					return 0;
			}
			//如果没有人工变量或者人工变量全都不是正值的时候则打印最优结果并且返回1
			PrintResult();
			return 1;
		}
		if(Check(in))
		{//如果选取出基变量的时候没有正的比值则无解无上界退出
			cout<<"函数没有上界所以没有最优解!\n";
			return 0;
		}
		out=SearchOut(&temp,in);//temp存放出基变量的行数，out存放出基变量的列数
        Mto(in,temp);//初等变换出基变量的方程使它的入基变量的位置的系数变为1
        Be(temp,in);//消去所有非出基变量方程的入基的系数（高斯/约当变换）
	    Achange(in,out);//把out出基变量的a数组与入基变量的a数组位置值对换	
	}
}
void MySimplex::initial()
{
	cout<<"准备计算，请按提示选择:"<<endl;
	cout<<"-------------------------------------"<<endl;
	do
	{
		cout<<"0.手动输入原问题模型"<<endl<<endl;
		cout<<"1.读取文件输入原问题模型"<<endl<<endl;
		cout<<"2.退出"<<endl;
		cout<<"-------------------------------------"<<endl;
		cin>>selectinput;
		if(selectinput == 0)
		{
			Input(b,code);//输入原规划模型和限制条件 
		}
		else if(selectinput == 1)
		{
			InputFile();
		}
		else if(selectinput == 2)
		{
			exit(0);
		}
		else
		{
			cout<<"选择错误，请重新输入!"<<endl;
		}
	}while((selectinput !=0) && (selectinput != 1) && (selectinput != 2));	
}
void MySimplex::compute()
{
	if(selectinput >= 0)
	{
	Start(b,code);//标准化原规划模型和限制条件使它们可以用单纯型法来做 
	cout<<endl;
	cout<<"标准化之后:"<<endl;
	printMatrix();
	cout<<"开始用单纯型法求最优解:"<<endl;
	int haveSolution = Simplix();//单纯型法解决问题/**/
	}
	else
	{
		cout<<"调用计算前前没有初始化"<<endl;
	}
	
}
MySimplex::~MySimplex()
{
}