运筹学实验-单纯形法上机报告(共29页).docx

精选优质文档-倾情为你奉上单纯形法大M法实验报告目录一、 实验目的使用目前熟悉的语言，实现所学的单纯形法之大M法，并正确运算测试结果。本组成员使用C语言实现。 二、 单纯形法及大M法1. 单纯形法（Simplex Method）（1） 单纯形法是解线性规划问题的一个重要方法。其原理的基本框架为：第一步：将LP线性规划变标准型，确定一个初始可行解（顶点）。第二步：对初始基可行解最优性判别，若最优，停止；否则转下一步。第三步：从初始基可行解向相邻的基可行解（顶点）转换，且使目标值有所改善目标函数值增加，重复第二和第三步直到找到最优解。（2） 用程序进行运算前，要将目标函数及约束方程变成标准形式。对于非标准形式须作如下变换：a) 目标函数为极小值min z=CX时，转换为max z=-CX形式；b) 在约束方程中有 “”时，在加上一个松弛变量；c) 在约束方程中有 “”时，采用减去一个松弛变量，再加上一个人工变量；d) 在约束方程中有 “=”时，加上一个人工变量；e) 所有的人工变量，松弛变量的目标函数系数置为0。（3） 对于标准形式的线性规划问题。用单纯形法计算步骤的框图（4） 在程序运算过程中，采用单纯形表显示运算过程。2. 大M法（1） 方法：在约束条件中，加入人工变量后，要求目标函数不受影响，目标函数中人工变量的系数取 M（M为系统所能表示范围内的一个非常大的值本程序取），其运算过程同单纯形法。（2） 理由：目标函数实现最大化，就必须将人工变量从基变量中换出，否则目标函数就不可能取得最大化。三、 数据结构及模块设计1. 程序中用到的数据结构：#define M 20 /最大20个变量#define N 40 /40个约束方程#define Max /大Mdouble DMN;/系数矩阵double CM;/目标函数系数double CbM;/基向量系数double BM;/约束常数double ValueN;/检验数int XbM;/基向量double X0M;/可行解int opM;/约束方程符号0-"<"、1-"="、2-">"int m,n;/矩阵行数、列数int begin_n;/初始变量数int In_BaseX=-1;/进基变量int in_n=-1;/进基列标示int out_m=-1;/出基行标示int Out_BaseX=-1;/出基变量int best;/最优函数返回值char name30;/文件名int ManX_num=0;/人工变量数目int ManX_listM;/人工变量存放数组2. 模块设计：void read();/读取方程子函数void print();/显示单纯表子函数void init_change();/初始变换子函数void compute_value();/计算检验数子函数int best_Result();/判断是否得到最优解子函数void in_base();/进基选子函数void out_base();/出基选择子函数void row_change();/行变换子函数四、 详细设计1. 文件格式定义格式：（行数/约束方程数：列数/变量数：） m n （约束矩阵： 符号：0小于，1等于，2大于 B值）D11 D12 D13 Dn1 op1 b1D21 D22 D23 Dn2 op2 b2.Dm1 D2m Dm3 Dnm opm bm（最大值/最小值：1最大，2最小）max/min目标函数的变量系数：C1C2 C3 . Cn例：32 0.60.50120000.40.10400000.406000125102. void read()读取约束矩阵、目标函数void read()FILE *fp ;/文件int i=0,j=0,k;fp=fopen(name,"r");if(fp!=NULL)/读变量数目和约束方程个数m,nfscanf(fp,"%d",&m);fscanf(fp,"%d",&n); begin_n=n;/初始（未经过标准化）变量数置为n,for(i=0;i<m;i+)/按行读取约束矩阵，约束方程符号，常数值for(j=0;j<n;j+)/读取约束矩阵if(fp!=NULL)fscanf(fp,"%lf",&Dij);elseprintf("error");if(fp!=NULL)/读约束方程符号fscanf(fp,"%d",&opi);elseprintf("error");if(fp!=NULL)/读取常数值fscanf(fp,"%lf",&Bi);elseprintf("error");if(fp!=NULL)/读取目标函数类型fscanf(fp,"%d",&Type);elseprintf("error");for(k=0;k<n;k+)/读取目标函数变量系数if(fp!=NULL)fscanf(fp,"%lf",&Ck);elseprintf("error");fclose(fp); / void read()3. void print()单纯形表显示函数void print()int i=0,j=0;void line_V(int);/竖线子函数void line_R(int);/横线子函数void ln();/换行子函数void space();/空格子函数ln();/第1条直线line_R(15+n*5);ln(); /显示第1行 “ C | C1 C2 C3 .” space(6);printf("C");space(7);line_V(1);for(i=0;i<n;i+)if(Ci=-Max)printf(" -M");elseprintf("%5.1lf",Ci);ln();/第2条直线line_R(15+n*5);ln();/显示第2行“Cb Xb B| X1 X2 X3 .”printf("Cb Xb B ");line_V(1);for(i=0;i<n;i+)printf(" X%-2d",i+1);ln();/第3条直线line_R(15+n*5);ln();/显示第3部分“Cb1 Xb1 B1| D11 D12 D13 .”/ “Cb2 Xb2 B2| D21 D22 D23 .”/“Cb3 Xb3 B3| D31 D32 D33 .”/“. ”for(i=0;i<m;i+)if(Cbi=-Max)printf("-M ");elseprintf("%-5.0lf",Cbi);printf("X%-2d",Xbi+1);printf("%5.0lf ",Bi);line_V(1);for(j=0;j<n;j+)printf("%5.1lf",Dij);ln();/第4条直线line_R(15+n*5);ln();/显示第4行 “ Value | Value1 Value2 Value3 .” space(5);printf("Value");space(4);line_V(1);for(i=0;i<n;i+)if(Valuei>Max/2)/当Value值达到M数量级时，用aM+b表示int k=(int)(Valuei/Max);double l=Valuei-k*Max;if(l>Max/2)k+;l-=Max;if(k=0)printf(" ");else if(k=1)printf(" M");elseprintf("%dM",k);if(l=0)printf(" ");else if(l>0)printf("+%-1.0lf",l);elseprintf("%-2.0lf",l);else if(Valuei<-Max/2) /当Value值达到M数量级时，用aM+b表示int k=(int)(Valuei/Max);double l=Valuei-k*Max;if(l<-Max/2)k-;l+=Max;if(k=0)printf(" ");else if(k=-1)printf(" -M");elseprintf("%dM",k);if(l=0)printf(" ");else if(l>0)printf("+%-1.0lf",l);else if(l<0)printf("%-2.0lf",l);else/正常显示printf(" %4.1lf",Valuei);ln();/第5条直线line_R(15+n*5);ln();/显示第5行 “ X(0)=( X1， X2， X3.)”space(1);printf("X(0)=(");for(i=0;i<n-1;i+)printf("%.2lf,",X0i);printf("%.1lf",X0i);printf(")");ln();line_R(15+n*5); /第6条直线ln();/*横线*void line_R(int n)int i;for(i=0;i<n;i+)printf("-");/*竖线*void line_V(int n)int i;for(i=0;i<n;i+)printf("|");/*空格*void space(int n)int i;for(i=0;i<n;i+)printf(" ");/*换行*void ln()printf("n ");4. void init_change()初始矩阵变换，加入松弛变量和人工变量void init_change()int i=0,j;int base_variable(int x);/判断是否为基变量的子函数/对 ">=" 约束方程，减去松弛变量，目标系数为0for(i=0;i<m;i+)if(opi=2)n+;Cn-1=0;for(j=0;j<m;j+)if(j=i)Djn-1=-1;elseDjn-1=0;for(i=0;i<m;i+)/对有 ">="和"=" 约束方程，加上人工变量，目标系数为Mif(opi=2|opi=1)n+;ManX_listManX_num=n-1;/将人工变量下标存入人工变量表ManX_num+;/人工变量数目加1Xbi=n-1;Cn-1=-Max;/人工变量的系数去-MCbi=Cn-1;for(j=0;j<m;j+)if(j=i)Djn-1=1;elseDjn-1=0;/对有 "<=" 约束方程，加上松弛变量，目标系数为0elsen+;Xbi=n-1;Cn-1=0;Cbi=Cn-1;for(j=0;j<m;j+)if(j=i)Djn-1=1;elseDjn-1=0;/如果是求最小值，则通过将目标函数各变量系数去相反数if(Type=2)for(i=0;i<n;i+)/读取目标函数变量系数Ci=-Ci;/初始可行解for(i=0;i<n;i+)if(j=base_variable(i)!=-1)X0i=Bj;elseX0i=0;/init_change()int base_variable(int x) /*判断是否为基变量，若是，返回下标，否则返回-1*int j;for(j=0;j<m;j+)if(x=Xbj)return j;return -1;5. void compute_value()计算检验数void compute_value()int i,j,k;int base_variable(int x);/判断是否为基变量的子函数for(i=0;i<n;i+)if(j=base_variable(i)!=-1) /基变量的检验数为0Valuei=0;else/非基变量Xi的检验数为Ci-Cb*Dmidouble sum=0;for(k=0;k<m;k+)sum+=Cbk*Dki;Valuei=Ci-sum;/compute_value()6. int best_Result()判断是否得到最优解。int best_Result()/唯一最优1，无穷多最优2，无界3，无可行5，未得到返回4int i;int less=0,more=0,equal=0;/检验数各种情况的数目小于0，大于0，等于0；int only_more=-1;/当只有一个检验数大于0时，记录进基变量的列数for(i=0;i<n;i+)/统计大于0，等于0，小于0个数if(Valuei<0)less+;else if(Valuei=0)equal+;else if(Valuei>0)more+;only_more=i; if(more=0) /无检验数大于0/若基解中有人工变量不为0，则无可行解for(i=0;i<ManX_num;i+)if(X0ManX_list1!=0)return 5;/非基变量检验数至少一个等于0，得到无穷多最优解for(i=0;i<n;i+)if(Valuei!=0&&base_variable(i)!=-1)return 2;/检验数全部小于0，得到唯一最优解else return 1;/检验数只有1个大于0，并且无出基变量，得到无界解else if(more=1)for(i=0;i<m;i+)/是否进基变量所在列的所有D值都小于0if(Dionly_more>0)return 4;/有一个大于0，不能判断return 3;/全部小于0，无出基变量，得到无界解/检验数至少有2个大于0，不能判断else return 4;/best_Result()f void in_base();/进基选子函数void out_base();/出基选择子函数void row_change();/行变换子函数7. void in_base() 进基选子函数void in_base()double max=0; int i;int max_num=-1;/初始最大的检验数下标为-1for(i=0;i<n;i+)/冒泡算法，求的最大检验数下标if(Valuei>max)max=Valuei;max_num=i;in_n=i;In_BaseX=max_num;/存到全局变量In_BaseX/in_base()8. void out_base()出基选择子函数void out_base()double tempM;int i;int in=In_BaseX;double min=Max;int min_num=-1;/初始最小B/Dij下标为-1for(i=0;i<m;i+)/计算B/Dij的值/D值为零，Dif(Diin>0)tempi=Bi/Diin;else tempi=Max;for(i=0;i<m;i+)/冒泡算法，求最小B/Dij下标if(tempi<min)min=tempi;min_num=Xbi;out_m=i;Out_BaseX=min_num;/存到全局变量Out_BaseX/out_base()9. void row_change()行变换子函数void row_change()int i,j;double temp;Xbout_m=In_BaseX;/进基变量进基/对出基行变换，包括系数矩阵和B值temp=Dout_min_n;for(j=0;j<n;j+)Dout_mj=Dout_mj/temp;Bout_m=Bout_m/temp;/对其他行变换for(i=0;i<m;i+)/不是出基行，并且其对应进基列值不为0，变换if(i!=out_m&&Diin_n!=0)double m=Diin_n;/倍数for(j=0;j<n;j+)/系数矩阵变换Dij=Dij-m*Dout_mj;Bi=Bi-m*Bout_m;/B值变换for(i=0;i<m;i+)/更新Cb的值Cbi=CXbi;for(i=0;i<n;i+)/更新当前可行解if(j=base_variable(i)!=-1) /基变量值为对应B值X0i=Bj;else/其他变量值为0X0i=0;/row_change()五、 程序测试及结果1. 第1题（1） 原题（2） 文件存储（3） 读取（4） 初始变换（5） 运算过程（6） 运算结果2. 第2题（1） 原题（2） 文件存储（3） 读取（4） 初始变换（5） 运算过程 （6） 运算结果3. 第3题（1） 原题（2） 文件存储（3） 读取（4） 初始变换（5） 运算过程（6） 运算结果4. 第2题（1） 原题（2） 文件存储（3） 读取（4） 初始变换（5） 运算过程（6） 运算结果因为，X4进基，无出基变量，故有无界解。5. 第2题（1） 原题（2） 文件存储（3） 读取（4） 初始变换（5） 运算过程（6） 运算结果因为，所有非基变量检验数小于0，并且有人工变量值不为0六、 工作分配及实验感想1. 工作分配完成程序代码及程序报告：刘光锐查找资料及相关书籍：周威，姚奇森参与对问题分析与设计：彭飞，何华刚，刘鹏飞2. 实验感想这次试验，开始认为很困难，因为对单纯形法本来就不是很熟悉，但是后来看到有很多同学都能完成任务，觉得这虽然是个难题，但如果没去做过，有些遗憾，正好老师给我们把上交期限延长到五一之前，这又给我们了机会，因为我们清楚地知道，大学的实验越来越少，能锻炼自己的机会也越来越少，所以鼓起勇气，一定要去完成。不会的地方，去问问学的好的同学，都很耐心的告诉，终于经过了1天多的时间，完成了任务，回头看看，困难真是个纸老虎，心里自然有种胜利的感觉。而且对算法有了更深的印象，在我今后的学习，工作中提供了一种思考方式。谢谢老师，谢谢运筹课。专心-专注-专业