单纯形法c++编程，可用于线性规划问题的研究解决优化问题.zip

#include<stdio.h> #include<math.h> #include<iostream.h> float matrix[100][100],x[100]; /* 记录总方程的数组,解的数组 */ int a[100]; /* 记录基础,非基础的解的情况,0:非基础,1:基础 */ int m,n,s,type; /* 方程变量,约束数,求最大最小值的类型,0:最小 1:最大 */ int indexe,indexl,indexg; /* 剩余变量,松弛变量,人工变量 */ void Jckxj() { int i,j; for(i=0;i<n;i++) for(j=0;j<s;j++) if(matrix[i][j]==1&&a[j]==1){ x[j]=matrix[i][s]; j=s; } for(i=0;i<s;i++) if(a[i]==0) x[i]=0; } int Rj() { int i; for(i=0;i<s;i++) if(fabs(matrix[n][i])>=0.000001) if(matrix[n][i]<0) return 0; return 1; } int Min() { int i,temp=0; float min=matrix[n][0]; for(i=1;i<s;i++) if(min>matrix[n][i]){ min=matrix[n][i]; temp=i; } return temp; } void JustArtificial() { int i; for(i=m+indexe+indexl;i<s;i++) if(fabs(x[i])>=0.000001){ printf("No Answer\n"); return; } } int Check(int in) { int i; float max1=-1; for(i=0;i<n;i++) if(fabs(matrix[i][in])>=0.000001&&max1<matrix[i][s]/matrix[i][in]) max1=matrix[i][s]/matrix[i][in]; if(max1<0) return 1; return 0; } int SearchOut(int *temp,int in) { int i; float 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) return i; } void Mto(int in,int temp) { int i; for(i=0;i<=s;i++) if(i!=in) matrix[temp][i]=matrix[temp][i]/matrix[temp][in]; matrix[temp][in]=1; } void Be(int temp,int in) { int i,j; float c; for(i=0;i<=n;i++){ c=matrix[i][in]/matrix[temp][in]; if(i!=temp) for(j=0;j<=s;j++) matrix[i][j]=matrix[i][j]-matrix[temp][j]*c; } } void Achange(int in,int out) { int temp=a[in]; a[in]=a[out]; a[out]=temp; } void Print() { int i,j,k,temp=0; for(i=0;i<n;i++){ for(k=temp;k<s;k++) if(a[k]==1){ printf("X%d ",k); temp=k+1; k=s; } for(j=0;j<=s;j++) printf("%8.2f",matrix[i][j]); printf("\n"); } printf("Rj "); for(j=0;j<=s;j++) printf("%8.2f",matrix[n][j]); printf("\n"); } void InitPrint() { int i; printf("X"); for(i=0;i<s;i++) printf(" a%d",i); printf(" b\n"); Print(); printf("\n"); } void Result() { int i; printf(" ("); for(i=0;i<s;i++) printf("%8.2f",x[i]); printf(" ) "); if(type==1) printf(" Zmax=%f\n\n",matrix[n][s]); else printf(" Zmin=%f\n\n",matrix[n][s]); } void PrintResult() { if(type==0) printf("The Minimal :%f\n",-matrix[n][s]); else printf("The Maximum :%f\n",matrix[n][s]); } void Merge(float nget[][100],float nlet[][100],float net[][100],float b[]) { int i,j; for(i=0;i<n;i++){ for(j=m;j<m+indexe;j++) if(nget[i][j-m]!=-1) matrix[i][j]=0; else matrix[i][j]=-1; for(j=m+indexe;j<m+indexe+indexl;j++) 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; 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 ProcessA() { int i; for(i=0;i<m+indexe;i++) a[i]=0; for(i=m+indexe;i<s;i++) a[i]=1; } void Input(float b[],int code[]) { int i=0,j=0; printf("The equator Variable and Restrictor\n"); /* 输入方程变量和约束数 */ cin>>m>>n; for(i=0;i<n;i++){ printf("Input b[] and Restrictor code 0:<= 1:= 2:>=\n"); /* 输入方程右边的值,code的值 */ cin>>b[i]>>code[i]; printf("The XiShu\n"); for(j=0;j<m;j++) cin>>matrix[i][j]; /* 输入方程 */ } printf("The Type 0:Min 1:Max \n"); /* 输入求最大值还是最小值 */ do{ cin>>type; if(type!=0&&type!=1) printf("Error,ReInput\n"); }while(type!=0&&type!=1); printf("The Z\n"); /* 输入z */ for(i=0;i<m;i++) cin>>matrix[n][i]; if(type==1) for(i=0;i<m;i++) matrix[n][i]=-matrix[n][i]; } void 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){ for(k=0;k<=s;k++) matrix[n][k]=matrix[n][k]-matrix[j][k]*100; j=n; } } } } void Process(float c[][100],int row,int vol) { int i; for(i=0;i<n;i++) if(i!=row) c[i][vol]=0; } void Sstart(float b[],int code[]) { int i; float nget[100][100],nlet[100][100],net[100][100]; /* 剩余变量数组,松弛变量数组,人工变量数组 */ indexe=indexl=indexg=0; for(i=0;i<n;i++){ if(code[i]==0){nlet[i][indexl++]=1; Process(nlet,i,indexl-1);} if(code[i]==1){ net[i][indexg++]=1; Process(net,i,indexg-1); } if(code[i]==2){ net[i][indexg++]=1; nget[i][indexe++]=-1; Process(net,i,indexg-1); Process(nget,i,indexe-1); } } s=indexe+indexl+indexg+m; Merge(nget,nlet,net,b); /* 合并 */ ProcessA(); /* 初始化a[] */ InitPrint(); /* 初始化打印 */ Xartificial(); /* 消去人工变量 */ } void Simplix() /* 单纯型算法 */ { int in,out,temp=0; while(1){ Jckxj(); /* 基础可行解 */ Print(); /* 打印 */ Result(); /* 打印结果 */ if(!Rj()) in=Min(); /* 求换入基 */ else { if(indexg!=0) JustArtificial(); /* 判断人工变量 */ PrintResult(); /* 打印最后结果 */ return; } if(Check(in)){ /* 判断无界情况 */ printf("No Delimition\n"); return; } out=SearchOut(&temp,in); /* 求换出基 */ Mto(in,temp); /* 主元化1 */ Be(temp,in); /* 初等变换 */ Achange(in,out); /* 改变a[]的值 */ } } void main() { int code[100]; /* 输入符号标记 */ float b[100]; /* 方程右值 */ Input(b,code); /* 初始化 */ Sstart(b,code); /* 化标准型 */ Simplix(); /* 单纯型算法 */ } 实验报告： *************************************************************************************** *********************************运筹学单纯形法解线性规划问题（C＋＋实现,VC6.0中通过）********************************** 函数列表： Jckxj Rj Min JustArtificial Check SearchOut Mto Be Achange Print InitPrint Result PrintResult Merge ProcessA Input Xartificial Process Sstart Simplix while main 变量： float matrix[100][100],x[100] 记录总方程的数组,解的数组 int a[100] 记录基础,非基础的解的情况,0:非基础,1:基础 int m,n,type 方程变量,约束数,求最大最小值的类型,0:最小 1:最大 int indexe,indexl,indexg 剩余变量,松弛变量,人工变量 输入提示： equator Variable 变量个数； Restrictor 约束条件个数；（注：这里程序默认X(i)>0；否则对每个X(i)我们均要添加一个约束条件X(i)>0） b[] 约束条件右端项； Restrictor code 约束条件不等式符号编码;(0表示<=；1表示=；2表示>=) The XiShu 各约束条件中X(i)对应的系数 The Type Z的最优方向（0表示MIN;1表示MAX） The Z 目标函数的系数 输入例子： MAX Z=4X(1)+3X(2) S.T. 2X(1)+3X(2)<=24 3X(1)+2X(2)<=26 X(1),X(2)>=0 运行1000432.exe The equator Variable and Restrictor: 2 2 Input b[] and Restrictor code 0:<= 1:= 2:>= 24 0 The XiShu 2 3 Input b[] and Restrictor code 0:<= 1:= 2:>= 26 0 The XiShu 3 2 The Type 0:Min 1:Max 1 The Z 4 3 结果输出： X a0 a1 a2 a3 b X2 2.00 3.00 1.00 0.00 24.00 X3 3.00 2.00 0.00 1.00 26.00 Rj -4.00 -3.00 0.00 0.00 0.00 X2 2.00 3.00 1.00 0.00 24.00 X3 3.00 2.00 0.00 1.00 26.00 Rj -4.00 -3.00 0.00 0.00 0.00 ( 0.00 0.00 24.00 26.00 ) Zmax=0.000000 X0 0.00 1.67 1.00 -0.67 6.67 X2 1.00 0.67 0.00 0.33 8.67 Rj 0.00 -0.33 0.00 1.33 34.67 ( 8.67 0.00 6.67 0.00 ) Zmax=34.666668 X0 0.00 1.00 0.60 -0.40 4.00 X1 1.00 0.