cprograme.txt

原始单纯型算法求解优化问题

#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(); /* 单纯型算法 */ 
}




实验报告： 
****************计算机系2000级软件班1000432 彭小聪************************ 
***********运筹学单纯形法解线性规划问题（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.00   -0.40    0.60    6.00 
Rj     0.00    0.00    0.20    1.20   36.00 
 (    6.00    4.00    0.00    0.00 )  Zmax=36.000000 
The Maximum :36.000000 
从而可知：MAX Z=36,此时X(1)=6,X(2)=4. 
实验成功。