//用单纯形法求解线性规划问题
//求解max z=2*x(1)+3*x(2)
//       2*x(1)+2*(x2)<=12
//       4*x(1)<=16
//       5*x(2)<=15
//       x(1),x(2)>=0
//Matrix.dat文件中存放的是x的系数
//        x1  x2  x3  x4  x5
//        a11 a12 a13 a14 a15
//        a21 a22 a23 a24 a25
//        a31 a32 a33 a34 a35
//Cb.dat文件中存放的数据是Cb和B中的数据
//        Cb1  B1
//        Cb2  B2
//        Cb3  B3
//Check.dat文件中存放的数据是检验数Check中的数据
//        Check1  Check2  Check3  Check4  Check5
#include<iostream>
#include<fstream>
#include<string>
using namespace std;
int main()
{
	double *Cj;        //目标函数各个系数所组成的数组
    double *Cb;       //松弛变量系数数组
	double *B;       //  标准式中的常数
    double *Check;   //检验数
	double **Matrix; //矩阵
	int Row=0;        //行数
	int Column=0;     //列数
	int *BasicOrder;//基序列，用来表示x1,x2,x3……
	double Aim=0;  //目标函数值
	string s;
	double dd;    //缓存用
	char c;
	ifstream Ma("Matrix.dat");
	while(getline(Ma,s))     //统计行数
	{
		Row++;
	}
	Ma.close();    //关闭文件
	Ma.open("Matrix.dat");
	while(1)       //统计列数
	{
		Ma>>dd;
		Column++;
		c=Ma.peek();
		if('
'==c)
			break;
	}
	Ma.close();
	Cj=new double[Column];
	Cb=new double[Row];
	B=new double[Row];
	Check=new double[Column];
	Matrix=(double **)new double*[Row];   //为矩阵Matrix分配空间
	for(int i=0;i!=Row;i++)
	{
		Matrix[i]=new double[Column];
	}
	Ma.open("Matrix.dat");
	while(!Ma.eof())    //读取矩阵
	{
		for(int i=0;i!=Row;i++)
		{
			for(int j=0;j!=Column;j++)
			{
				Ma>>Matrix[i][j];
			}
		}
	}
	Ma.close();
	ifstream CB("Cb.dat");   //其中Cb和B的数据在同一文件中，第一行为Cb第二行为B
	int temI=0;
	while(!CB.eof()) //读取Cb
	{
	     CB>>Cb[temI]>>B[temI];
		 temI++;
	}
	CB.close();
	ifstream CH("Check.dat");
	while(!CH.eof()) //读取Check
	{
		for(int i=0;i!=Column;i++)
		{
			CH>>Cj[i];
			Check[i]=Cj[i];
		}
	}
	CH.close();
	//接下来是一个大while循环
	while(1)
	{
	   for(int i=0;i!=1;i++)     
	   {
		  cout<<Cb[i]<<"  "<<B[i]<<"  ";    //输出Cb和B
		  for(int j=0;j!=Column;j++)
		  {
			 cout<<Matrix[i][j]<<"  ";//输出矩阵Matrix
		  }
		  cout<<endl;
	   }
		int MaxCheck; //最大检验数所在的列数
		double TemMin;       //缓存最小值
		double *TemArray;
		int TemI;      //确定需要换出的基所在的行数
		TemArray=new double[Row];
		MaxCheck=0;   //默认最大检验数为第一个检验数
		TemI=0;     //缓存最小值所在的行
		for(int i=0;i!=Column;i++)      //
	    {
          if(Check[MaxCheck]<Check[i])
		  {
			 MaxCheck=i;
		  } 
	    }
		if(Check[MaxCheck]>0)       //如果检验数的最大值大于0则进行换出基操作
	    {
			for(int j=0;j!=Row;j++)    //计算除法所得的值
			{
               if(Matrix[j][MaxCheck]==0)     //如果除数为0
			   {
				  TemArray[j]=10000;  //代表无穷大
			   }
			   else
			   {
				  TemArray[j]=B[j]/Matrix[j][MaxCheck];
			   }
			}
			TemMin=TemArray[0];
			for(int j=1;j!=Row;j++)     //找出最小值
			{
                if(TemMin>TemArray[j])
				{
				   	TemMin=TemArray[j];
					TemI=j;
				}
			}
			Cb[TemI]=Cj[MaxCheck];          //将Cb中的值更换
			double TemElem=Matrix[TemI][MaxCheck];    //将定位好的值缓存
			for(int j=0;j!=Column;j++)        //将此行中的对应换入基的数变为1，并对相应的值更改
			{
		        Matrix[TemI][j]/=TemElem;
			}
			B[TemI]/=TemElem;    //将B中的元素更改
			for(int j=0;j!=Row;j++)      //将Matrix中的定位的值的上下方的元素变为0
			{
			    if(j!=TemI)   //将变为1的数字所在的行排除
				{
					TemElem=-Matrix[j][MaxCheck];    //1的上面的值要想变为0，则它的值加上它的相反数
					for(int k=0;k!=Column;k++)
					{
					    Matrix[j][k]+=Matrix[TemI][k]*TemElem; //更改当前行的元素
					}
					B[j]+=B[TemI]*TemElem;  //更改当前行的B元素
				}
			}
			double TemCheck=-Check[MaxCheck];     //检验数也要改
			for(int j=0;j!=Column;j++)
			{
			    Check[j]+=Matrix[TemI][j]*TemCheck; //更改检验和
			}
	    }
		else
		{
			for(int i=0;i!=Row;i++)
			{
				Aim+=Cb[i]*B[i];
			}
			for(int i=0;i!=Row;i++)     
			{
				cout<<Cb[i]<<"  "<<B[i]<<"  ";    //输出Cb和B
				for(int j=0;j!=Column;j++)
				{
					cout<<Matrix[i][j]<<"  ";//输出矩阵Matrix
				}
				cout<<endl;
			}
			for(int i=0;i!=Column;i++)
			{
				cout<<Check[i]<<"  ";        //输出检验数
			}
			cout<<endl;
			cout<<"目标函数值为"<<Aim<<endl;
			break;
		}
	}
	system("pause");
	return 0;
}