#include<iostream>
#include<cmath>
using namespace std;
#define M 100000
//全局變量
float **kernel;//核心矩陣表
int m=0,n=0,t=0;//m:結(jié)構(gòu)向量的個(gè)數(shù)
                 //n:約束不等式個(gè)數(shù)
                 //t:目標(biāo)函數(shù)類型：－1代表求最小值，1代表求最大值
void newspace()   //動(dòng)態(tài)開辟數(shù)組
{	
	kernel=new float*[n+2];
	if (kernel==NULL)
	{
		cout<<"對不起，開辟數(shù)組不成功！程序結(jié)束！"<<endl;
		return ;
	}
	int i;
	for (i=0;i<n+2;i++)
	{
		kernel[i]=new float[m+2*n+1];
		if(kernel[i]==NULL)
		{
			cout<<"對不起，開辟數(shù)組不成功！程序結(jié)束！"<<endl;
			return ;
		}
	}
}
void delspace()  //釋放數(shù)組空間
{
	int i;
	for(i=0;i<n+2;i++)
		delete []kernel[i];
	delete []kernel;
}
//輸入接口函數(shù)
void input()
{
	//讀入所求問題的基本條件
	cout<<"－－－－－－－－－－參 數(shù) 輸 入－－－－－－－－－－－"<<endl;
	cout<<"請按提示輸入下列參數(shù)："<<endl<<endl;
	cout<<"  變量個(gè)數(shù)m:  "<<"   m=  ";
	cin>>m;
	cout<<endl<<"  約束不等式數(shù)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<<"  約束方程矩陣的系數(shù)及不等式方向（1代表<=,-1代表>=,2表示=）:"<<endl<<endl<<"          ";
	for (i=1;i<=m;i++)
		cout<<"   x"<<i;
		cout<<"  不等式方向 "<<" 常數(shù)項(xiàng)"<<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;
	}
	//讀入目標(biāo)條件
	cout<<endl<<endl<<" 目標(biāo)函數(shù)的系數(shù)及類型（求最大值:1；求最小值:-1）:"<<endl<<endl<<"                ";
	for(i=1;i<=m;i++)
		cout<<"x"<<i<<"   ";
	cout<<"類型"<<endl<<"  ";
	cout<<"  目標(biāo)函數(shù):   ";
	for (i=1;i<=m;i++)
		cin>>kernel [0][i];
		cin>>t;
	//矩陣調(diào)整
	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<<"對不起，開辟數(shù)組不成功！程序結(jié)束！"<<endl;
		return ;
	}
}
//算法函數(shù)
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<<"對不起，開辟數(shù)組不成功！程序結(jié)束！"<<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<<"對不起，開辟數(shù)組不成功！程序結(jié)束！"<<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;
	}

	 //循環(huán)求解
	do{ 
		cout<<"  "<<" 檢驗(yàn)數(shù) "; 
		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;
					}
	         }
			//輸出結(jié)果
			cout<<endl<<endl;
			cout<<"－－－－－－－－－－－－結(jié) 果 輸 出－－－－－－－－－－－－"<<endl<<endl;
			if(temp1==1)
			{ 
				cout<<" 此線性規(guī)劃的最優(yōu)解存在!"<<endl<<endl<<"  最優(yōu)解為："<<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<<"整數(shù)解已達(dá)到!"<<endl;
					return;
				}
				if(flag==-1)
				{
					for(j=0;j<=n;j++)
						kernel[j][i]=0;

				}
				cout<<" ;"<<endl<<endl<<"     最優(yōu)目標(biāo)函數(shù)值f= "<<f<<endl<<endl;
				return ;
			}
			else 
			{   
				cout<<" 此線性規(guī)劃無解"<<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<<"此線性規(guī)劃無約束"<<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 ;
}
//主函數(shù)
void main()
{ cout<<"-------------------單純形法算法程序----------------------"<<endl<<endl;
  input();
  comput();
 }