改进单纯形法3.cpp

单纯行法实现线性规划的优化问题求解

//改进单纯形法源程序
#include<iostream.h>
#include<iomanip.h>
void main()
{
	const int M=100;
	float min;
	float max;
	int count,count1,count2,count3,J,J1,J2;//标志变量
	int i,j,m,n,z,z1,z2,temp,s,d;
	int d1[M],d2[M],d3[M];
	float A[M][M],N[M][M],B[M][M],B1[M][M],B2[M][M];
	float C[M],Cb[M],Cn[M],p[M],E[M],b[M],b1[M],X[M],E1[M][M],T3[M],T4[M],T1[M],T2[M],Q[M],z3;
	cout<<"首先化为标准型:（如是松弛变量或是剩余变量系数为零，若是人工变量则系数必须取小于等于-10000的数!）"<<endl;
	do
	{
		cout<<"请输入资源向量b的个数："<<endl;
		cin>>m;
	}while(!(m>0&&m<=100));
	do
	{
		cout<<"请输入价值向量c的个数:"<<endl;
		cin>>n;
	}while(!(n>0&&n<=100&&n>=m));
	cout<<"请输入资源向量b:"<<endl;
	for(i=1;i<=m;i++)
	{
		cin>>b[i];
	   b1[i]=b[i];
	}
	cout<<"请输入价值向量的系数:"<<endl;
	for(i=1;i<=n;i++)
	{
		cin>>C[i];
	}
	cout<<"请输入约束方程系数:"<<endl;
	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++)
			cin>>A[i][j];
	cout<<"请指出初始基变量的下标:"<<endl;
	    for(i=1;i<=m;i++)
			cin>>d1[i];//初始基变量的下标值
	    cout<<"请输入初始非基变量的下标值:"<<endl;
	    for(i=1;i<=n-m;i++)
			cin>>d2[i];//初始非基变量的下标值
		do
		{
			cout<<"请输入人工变量的个数:"<<endl;
			cin>>d;
		}while(!(d<=m));
    cout<<"请输入人工变量的下标值"<<endl;
	    for(i=1;i<=d;i++)
	          cin>>d3[i];//人工变量的下标
		cout<<"初始基B为:"<<endl;
		for(i=1;i<=m;i++)
			for(j=1;j<=m;j++)
			{
				if(i==j)
					B[i][j]=1;
				else
					B[i][j]=0;
			}
			for(i=1;i<=m;i++)
			{
				for(j=1;j<=m;j++)
				{
					cout<<setw(4)<<B[i][j];
				    B1[i][j]=B[i][j];
				}
				cout<<endl;
			}


	  for(int k=0;k>-2;k++)//整个过程的循环
	  {
		   max=-1;
		   min=123456;
		    count=0;
		    cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;
			cout<<"基变量Xb"<<k<<"=(";
			for(i=1;i<=m;i++)
			{
				if(i!=m)
					cout<<"X"<<d1[i]<<",";
				else
					cout<<"X"<<d1[i]<<")"<<endl;
			}
			cout<<"其对应的系数为Cb"<<k<<": (";
				for(i=1;i<=m;i++)
				{
					Cb[i]=C[d1[i]];
					if(i!=m)
						cout<<C[d1[i]]<<",";
					else
						cout<<C[d1[i]]<<")"<<endl;
				}
			cout<<"非基变量Xn"<<k<<"=(";
			for(i=1;i<=n-m;i++)
			{
				if(i!=n-m)
					cout<<"X"<<d2[i]<<",";
				else
					cout<<"X"<<d2[i]<<")"<<endl;
			}
			cout<<"其对应的系数为Cn"<<k<<"=(";
				for(i=1;i<=n-m;i++)
				{
					Cn[i]=C[d2[i]];
					if(i!=n-m)
						cout<<C[d2[i]]<<",";
					else
						cout<<C[d2[i]]<<")"<<endl;
				}
			cout<<"基B"<<k<<"="<<endl;
			for(i=1;i<=m;i++)
			{
				for(j=1;j<=m;j++)
					cout<<setw(10)<<B[i][j];
				cout<<endl;
			}
				for(i=1;i<=n-m;i++)
					for(j=1;j<=m;j++)
						N[j][i]=A[j][d2[i]];//非基变量的系数矩阵,可伴随每次循环更新
				//计算非基变量的检验数，确定换入变量。
					for(i=1;i<=m;i++)
					{
					    T1[i]=0;
						for(j=1;j<=m;j++)
							T1[i]+=Cb[j]*B[j][i];
					}
					for(i=1;i<=n-m;i++)
					{
						    T2[i]=0;
							for(j=1;j<=m;j++)
								T2[i]+=T1[j]*N[j][i];
					}
					for(i=1;i<=n-m;i++)//判断
					{
						X[i]=Cn[i]-T2[i];//检验数
						if(X[i]<=0)
							count++;
						else if(X[i]>0)
						{
							count1=0;
							count2=0;
							for(j=1;j<=m;j++)
							{
								T3[j]=0;
								T4[j]=0;
								for(s=1;s<=m;s++)
								{
									T3[j]+=B[j][s]*b1[s];
									T4[j]+=B[j][s]*A[s][d2[i]];
								}
							}
							for(j=1;j<=m;j++)
							{
								if(T3[j]/T4[j]<=0&&T4[j]!=0)
									count2++;//检验不符合条件的个数
								else if(T4[j]==0)
									count2++;//检验不符合条件的个数
							}
							for(j=1;j<=m;j++)
							{
								if(T4[j]<=0||count2==m)
									count1++;
							}
							if(count1==m)//检验数大于零，但所对应的系数列向量小于等于零
							{
								cout<<"该线性规划问题为无界解！"<<endl;
							    J=1;
							}
						}//else if
					}//for
					if(J==1)
						break;//该问题为无界解,退出循环 
					cout<<"检验数X[i]=(";
					for(i=1;i<=n-m;i++)
					{
						if(i!=n-m)
							cout<<X[i]<<",";
						else
							cout<<X[i]<<")"<<endl;
					}//输出检验数
				if(count!=n-m)
				{
				
					for(i=1;i<=n-m;i++)
					{
						if(X[i]>0&&X[i]>max)//求检验数中的最大值的下标
						{
							max=X[i];
							z=i;
						}
					}
                    cout<<"可确定X"<<d2[z]<<"为换入变量"<<endl;
					//计算机变量$的值，确定换出变量
					for(i=1;i<=m;i++)
					{
						 T3[i]=0;
						 T4[i]=0;
						for(j=1;j<=m;j++)
						{
							T3[i]+=B[i][j]*b1[j];
						    T4[i]+=B[i][j]*A[j][d2[z]];
						}
					}
					cout<<"$值为:(";
					for(i=1;i<=m;i++)
					{
						if(i!=m)
						{
							if(T4[i]>0&&T3[i]/T4[i]>0)
								cout<<T3[i]/T4[i]<<",";
						    else
							     cout<<"-"<<",";
						}
						else
						{
							if(T4[i]>0&&T3[i]/T4[i]>0)
								cout<<T3[i]/T4[i]<<")"<<endl;
						    else
							     cout<<"-"<<")"<<endl;
						}
					}
					for(i=1;i<=m;i++)
					{
						if(T4[i]>0&&T3[i]/T4[i]>0&&T3[i]/T4[i]<min)//求$值中大于零的最小者的下标
						{
							min=T3[i]/T4[i];
							z1=i;
						}
						z2=z1;
					}
					cout<<"可确定X"<<d1[z2]<<"为换出变量!"<<endl;
					for(i=1;i<=m;i++)
					{
						p[i]=0;
						for(j=1;j<=m;j++)
						{
						  p[i]+=B[i][j]*A[j][d2[z]];//列向量
						}
					}
                    float t2=p[z2];
					for(i=1;i<=m;i++)
					{
						if(i==z2)
							E[i]=1/t2;
						else
							E[i]=-p[i]/t2;
					}
					for(j=1;j<=m;j++)
						for(i=1;i<=m;i++)
						{
							if(j==z2)
								E1[i][j]=E[i];
							else
								E1[i][j]=B1[i][j];
						}
					for(i=1;i<=m;i++)
					{
						for( s=1;s<=m;s++)
						{
						   float t3=0;
                           for(j=1;j<=m;j++)
							   t3+=E1[i][j]*B[j][s];
						    B2[i][s]=t3;
						}
					}
					for(i=1;i<=m;i++)
						for(j=1;j<=m;j++)
							B[i][j]=B2[i][j];//更新基B
					temp=d1[z2];//交换换入换出变量的下标值
					d1[z2]=d2[z];
					d2[z]=temp;
				}
				else if(count==n-m)//所有非基变量的检验数小于等于零
				{	
					for(i=1;i<=m;i++)//更新资源向量b
					{
						Q[i]=0;
						for(j=1;j<=m;j++)
							Q[i]+=B[i][j]*b1[j];
					}
					for(i=1;i<=n-m;i++)
					{
						if(X[i]==0)//