运筹学实验-单纯形法上机报告(共29页).docx
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《运筹学实验-单纯形法上机报告(共29页).docx》由会员分享,可在线阅读,更多相关《运筹学实验-单纯形法上机报告(共29页).docx(29页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、精选优质文档-倾情为你奉上单纯形法大M法实验报告目录一、 实验目的使用目前熟悉的语言,实现所学的单纯形法之大M法,并正确运算测试结果。本组成员使用C语言实现。 二、 单纯形法及大M法1. 单纯形法(Simplex Method)(1) 单纯形法是解线性规划问题的一个重要方法。其原理的基本框架为:第一步:将LP线性规划变标准型,确定一个初始可行解(顶点)。第二步:对初始基可行解最优性判别,若最优,停止;否则转下一步。第三步:从初始基可行解向相邻的基可行解(顶点)转换,且使目标值有所改善目标函数值增加,重复第二和第三步直到找到最优解。(2) 用程序进行运算前,要将目标函数及约束方程变成标准形式。对
2、于非标准形式须作如下变换:a) 目标函数为极小值min z=CX时,转换为max z=-CX形式;b) 在约束方程中有 “”时,在加上一个松弛变量;c) 在约束方程中有 “”时,采用减去一个松弛变量,再加上一个人工变量;d) 在约束方程中有 “=”时,加上一个人工变量;e) 所有的人工变量,松弛变量的目标函数系数置为0。(3) 对于标准形式的线性规划问题。用单纯形法计算步骤的框图(4) 在程序运算过程中,采用单纯形表显示运算过程。2. 大M法(1) 方法:在约束条件中,加入人工变量后,要求目标函数不受影响,目标函数中人工变量的系数取 M(M为系统所能表示范围内的一个非常大的值本程序取),其运算
3、过程同单纯形法。(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-int m,n;/矩阵行数、列数int begin_n;/初始变量
4、数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();/判断是否得到最优解子函数vo
5、id 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 r
6、ead()读取约束矩阵、目标函数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;im;i+)/按行读取约束矩阵,约束方程符号,常数值for(j=0;jn;j+)/读取约束矩阵if(fp!=NULL)fscanf(fp,%lf,&Dij);elseprintf(error);if(fp!=NULL)/读约束方程符号fscanf(fp,%d,
7、&opi);elseprintf(error);if(fp!=NULL)/读取常数值fscanf(fp,%lf,&Bi);elseprintf(error);if(fp!=NULL)/读取目标函数类型fscanf(fp,%d,&Type);elseprintf(error);for(k=0;kn;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)
8、;/竖线子函数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;in;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
9、(1);for(i=0;in;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;im;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;jn;j+)printf(%5.1
10、lf,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;iMax/2)/当Value值达到M数量级时,用aM+b表示int k=(int)(Valuei/Max);double l=Valuei-k*Max;if(lMax/2)k+;l-=Max;if(k=0)printf( );else if(k=1)printf( M);elseprintf(%dM,k);if(l=0)printf( )
11、;else if(l0)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(l0)printf(+%-1.0lf,l);else if(l0)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);p
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 实验 单纯 上机 报告 29
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内