《系统优算法设计与实现》运筹学课设

1、课程设计（论文）课程设计（论文）课程名称： 系统优算法设计与实现 题 目：线性规划灵敏度分析算法设计与实现院 （系）： 专业班级： 姓 名： 学 号： 指导教师： 2014 年 7 月 18 日西安建筑科技大学课程设计（论文）任务书专业班级： 信管1302 学生姓名： 黄小青 指导教师（签名）： 一、课程设计（论文）题目一、课程设计（论文）题目线性规划灵敏度设计算法与实现二、本次课程设计（论文）应达到的目的二、本次课程设计（论文）应达到的目的系统优算法设计与实现课程设计是实践教学环节的重要组成部分，其目的是通过课程设计加深学生对系统优算法设计与实现基本知识掌握和基本编程技能的培养，提高综合运用

2、知识解决实际问题的能力；本次要求学生通过掌握系统优算法设计与实现的程序设计方法，以提高学生独立分析问题、解决问题的能力，逐步增强实际工程训练。 三、本次课程设计（论文）任务的主要内容和要求三、本次课程设计（论文）任务的主要内容和要求设计内容：设计内容：本程序在已知初始单纯形表和最终单纯形表的情况下，对目标函数系数进行灵敏度分析，要实现三个个目标。其一：在输入初始单纯形表和最终单纯形表后，将单纯形表进行矩阵的分离，然后输入改变后的目标函数，利用单纯形法的矩阵描述进行计算，计算出调整后的结果，反映到最终形表中，检验是否最优。其二：若检验结果不是最优，设计单纯形法，用单纯形法进行计算，直到最优解。其

3、三：在初始单纯形表条件下，其他条件不变，对目标函数系数进行调整，在最优解不变的情况下，确定目标函数系数的变化范围。要求：要求： 1提交正确的和完整的程序设计代码。 2提交设计说明书。 3. 接受现场检验。四、应收集的资料及主要参考文献：四、应收集的资料及主要参考文献：应收集的资料：本次设计应该收集和题目背景的有关资料。主要参考文献：1.胡运权. .运筹学.清华大学出版社，20122.谭浩强.C 程序设计（第四版） .清华大学出版社，20103.谭浩强.C+程序设计（第二版） .清华大学出版社，20115 5、审核批准意见审核批准意见教研室主任（签字）教研室主任（签字） 设计总说明分析线性规划灵

4、敏度分析算法这个问题。把解决问题所需条件、原始数据、输入输出信息等搞清楚。对较大问题（单纯形法的计算和线性规划的矩阵描述）的用文字和流程图描述。分析完后问题后建立数学模型，把问题数学化公式化，此算法中有矩阵的乘法运算，矩阵的分离与合并（比如将矩阵 A 分为 BN，即A=BN） ，单纯形法，求最大最小值，设计 X 变化范围的计算公式之后绘制程序流程图，可用文字概述为以下六步。第一步：从文件读入数据。第二步：根据要求分离矩阵。第三步：输入目标函数，检验最优性。第四步：若不是最优，设计单纯形表算法，进行计算，检验最优性。重复第四步，直到最优。第五步：输出改变目标函数后最终单纯形表。第六步：输入要计算

5、变化范围的 X，利用公式计算，然后输出。编制程序，画完流程图后，就可以进行编程了。根据流程图编程，为防止最后检查时错误过多无从下手，对程序进行分模块编程，把一些小的算法先编程调试成功，再带入主程序。编写主程序的时候，每写完一小部分，要进行调试，检查是否有逻辑或语法错误。在编程中，还要对定义的变量和编写的语句进行解释，让程序更易理解。如果还未编程等待编程的语句和可插入其他功能程序的地方也要进行解释说明，这样，对后续的程序修改和优化也有帮助。编写完毕，对程序进行调试运行。关键字：线性规划，灵敏度，程序设计，C 语言第 0 页 共 25 页目 录1 1 绪论绪论.1 11.1 内容简介 .11.2

6、本次课设目的 .11.3 课设内容 .12.2. 线性规划灵敏度分析算法设计说明线性规划灵敏度分析算法设计说明.3 32.1 程序设计过程详述 .32.2 编程实现过程详述 .32.4 原代码 .43 3 实验研究小结实验研究小结.18183.1 使用说明详述 .183.1.1 本部分功能操作注意事项 .183.1.2 本部分功能与其他系统的关系 .183.2 测试案例详述 .18参考文献参考文献.2020第 0 页 共 25 页1 绪论1.1 内容简介在线性规划问题中的参数往往是一些估计和预测的数字，随着环境的变化（如市场条件变化，工艺技术条件的变化） ，其最优解也会随之变化。当这些参数中的

7、一个或多个发生改变是，问题的最优解会有什么变化，或者这些参数在什么范围变化时，问题的最优解或最优基不变。 为解决线性规划的目标函数的这些问题，本程序中对此进行灵敏度分析。1.2 本次课设目的 本程序中对线性规划的目标函数做出灵敏度分析，以书（胡运权. .运筹学.清华大学出版社，2012，P64）中例五为例，分析市场条件变化后利润的变化，导致目标函数改变，分析这些变化对结果的影响，以及目标函数在什么范围变化是，问题的最优解不变。1.3 课设内容一：调整目标函数系数，将参数的改变反映到最终单纯形表中，判断是否最优，若不是，继续计算二：设计单纯形法算法三：确定目标函数系数可变化的范围 第 1 页 共

8、 25 页2. 线性规划灵敏度分析算法设计说明2.1 程序设计过程详述1分析问题，了解问题要求和目的。2程序分块和建立数学模型，用公式和文字把题目中涉及到的算法一步步分解成小模块，依次解决。 其中包括：文件的读入，矩阵的乘法运算，矩阵的分离与合并（比如将矩阵 A分为 BN，即 A=BN） ，单纯形法，求最大最小值，设计 X 变化范围的计算公式等三建立流程图，把二中的算法按照步骤组合起来。第一步：从文件读入数据。第二步：根据要求分离矩阵。第三步：输入目标函数，检验最优性。第四步：若不是最优，设计单纯形表算法，进行计算，检验最优性。重复第四步，直到最优。第五步：输出改变目标函数后最终单纯形表。第六

9、步：输入要计算变化范围的 X，利用公式计算，然后输出。四对各个小模块进行编程，调试成功后，再根据流程图编写主程序，顺便把要用到小模块加进去，然后进行调试。2.2 编程实现过程详述第一步：从文件读入数据。第二步：根据要求分离矩阵。第三步：输入目标函数，检验最优性。第四步：若不是最优，设计单纯形表算法，进行计算，检验最优性。重复第四步，直到最优。第五步：输出改变目标函数后最终单纯形表。第六步：输入要计算变化范围的 X，利用公式计算，然后输出。第 2 页 共 25 页2.4 原代码#includestdio.h #includemath.h #includestring.h #includestdl

10、ib.h#includedos.hint main()double F1010,b1050,C5010;int J1050;/初始矩阵：F 是 AX+IX=b的 AIb。C 是 max z=CX+0X 的 C0 。J 是基 double FF1010,bb1050,CC5010,BB1010;int JJ1050;/最终单纯形表：BB 是 B 的逆矩阵 double R501020;int i,j,k;int r,l;/r 为约束条件矩阵的行。l 为约束条件矩阵的列 printf(输入约束矩阵的行 r 和列 l：);scanf(%d%d,&r,&l) ;printf(n); /

11、-输入初始单纯形表和最终单纯形表- FILE *fp=fopen(D:A.txt,r);/输入 F 36if(!fp) return 0;i=0;j=0;while(!feof(fp)fscanf(fp,%lf,&Fij);j+;if(j=6)i+;j=0;fclose (fp);FILE *fp1=fopen(D:B.txt,r);/输入 C 05if(!fp1) return 0;第 3 页 共 25 页i=0;while(!feof(fp1)fscanf(fp1,%lf,&C0i);i+;fclose (fp1);FILE *fp2=fopen(D:C.txt,r);/输

12、入基 j30if(!fp2) return 0;i=0;while(!feof(fp2)fscanf(fp2,%d,&Ji0);i+;fclose (fp2);FILE *fpd=fopen(D:D.txt,r);/输入 FF36if(!fpd) return 0;i=0;j=0;while(!feof(fpd)fscanf(fpd,%lf,&FFij);j+;if(j=6)i+;j=0;fclose (fpd);FILE *fpe=fopen(D:E.txt,r);/输入 CCif(!fpe) return 0;第 4 页 共 25 页i=0;while(!feof(fpe)

13、fscanf(fpe,%lf,&CC0i);i+;fclose (fpe);FILE *fpf=fopen(D:F.txt,r);/输入基 if(!fpf) return 0;i=0;while(!feof(fpf)fscanf(fpf,%d,&JJi0);i+;fclose (fpf);/-输出初始单纯形表和最终单纯形表- printf(线性规划的初始单纯形表为：n);/输出初始单纯形表 printf( Cj ); for(i=0;il-1;i+) printf(%lf ,C0i); printf(n); printf(基 ); printf(b ); for(i=0;il-

14、1;i+) printf( X%d ,i); printf(n); k=0;for(i=0;ir;i+)printf(X%d ,Ji0);for(j=0;jl;j+)第 5 页 共 25 页printf(%lf ,Fij);k+;if(k=6) printf(n);k=0; printf(nn); printf(最终单纯形表为：n);/输出最终单纯形表 printf( Cj-Zj ); for(i=0;il-1;i+) printf(%lf ,CC0i); printf(n); printf(基 ); printf(b ); for(i=0;il-1;i+) printf( X%d ,i);

15、printf(n); k=0;for(i=0;ir;i+)printf(X%d ,JJi0);for(j=0;jl;j+)printf(%lf ,FFij);k+;if(k=6) printf(n);k=0; /-分离出 br0，bbr0，BBrr（B 的逆）-第 6 页 共 25 页-for(i=0;ir;i+)bi0=Fil-1;for(i=0;ir;i+)bbi0=FFil-1;for(i=0;ir;i+)k=0;for(j=l-r-1;jl-1;j+)BBik=FFij;k+; /-分离出 CB0r - double CB100r; for(i=0;ir;i+)k=JJi0;/prin

16、tf(%d ,k); CB0i=C0k-1; /-/-分析 cj 的变化-/-printf(n);printf (现在分析 Cj 的变化对最优解的影响n 请输入新的目标函数系数:);for(i=0;il-1;i+)scanf(%lf,&C1i); /-分离出 CB1r - for(i=0;ir;i+)第 7 页 共 25 页k=JJi0;CB1i=C1k-1; /-计算-CB* BB ,这边设为 E -CB1rBBrr-double E1r,H1r;double sum=0;for(i=0;i1;i+)/i 是 CB 的行 for(j=0;jr;j+)/j 是 BB 的列 for(k=

17、0;kr;k+)/k 是 CB 的列和 BB 的行 sum=sum+CBi+1k*BBkj; Eij=(-1)*sum; sum=0;j=0; for(i=l-r-1;il-1;i+) CC1i=E0j; j+; /-单纯形法-int s,m,n,p,q;/s 用来判断是否进行单纯形表的计算 double Qr;int maxl,minbi,minr;/最小列 maxl,最小行的基 minbi,最小行 minrdouble maxC,minb,t;/ 最大 maxC,minb s=0;for(i=0;i0)s=1;/如果存在检验数大于 0，不是最优，则 s=1 第 8 页 共 25 页if(s

18、=0)printf(新的目标函数对应的结果仍旧是最优解n);for(i=0;ir;i+)/将 FFrl赋值给 R0 for(j=0;jl;j+)R0ij=FFij; /-不是最优还需继续进行解单纯形表 - - if(s=1) /-找出换出和换入的基- for(k=0;s=1;k+) maxC=CCk+10;maxl=0; for(i=0;imaxC)maxC=CCk+1i; maxl=i; for(i=0;ir;i+)if(Rkimaxl=0)Qi=999999999; elseQi=bbik/Rkimaxl;第 9 页 共 25 页 minb=Q0;minbi=J0k ;minr=0;for

19、(i=0;ir;i+) /找出换出的基 /找出检验数中最小的 b 记为 minb，对应的基 Xi 记为 minbi(下标)，minr 为行，从第 0 行开始计算 if(Qiminb)minb=Qi;minbi=Jik;minr=i; t=Rkminrmaxl; for(i=0;il;i+)Rk+1minri=Rkminri/t; /-换基，计算新的单纯形表- for(i=0;ir;i+)if(i=minr)JJik+1=maxl+1;elseJJik+1=JJik; for(i=0;ir;i+) /i 是行 if(i!=minr) if(Rkimaxl=0)for(j=0;jl;j+)第 10

20、 页 共 25 页Rk+1ij=Rkij; elset=Rkimaxl;for(j=0;jl;j+)/j 是列 Rk+1ij=Rkij-t*Rk+1minrj; else; /分离出新的 bb3k+1-for(i=0;ir;i+) bbik+1=Rk+1il-1; /-计算新的目标函数-t=CCk+1maxl;if(t=0)for(i=0;il-1;i+)CCk+2i=CCk+1i; elsefor(i=0;il-1;i+)CCk+2i=CCk+1i-t*Rk+1minri;第 11 页 共 25 页/-检验是否最优 -如果最优的话 s=0，否则 s=1- s=0;for(i=0;i0)s=1

21、; /如果存在检验数大于 0，不是最优，则 m=1 printf(n); printf(改变 Cj 后的最终单纯形表为：n);/输出初始单纯形表 printf( Cj ); for(i=0;il-1;i+) printf(%lf ,CCk+1i); printf(n); printf(基 ); printf(b ); for(i=0;il-1;i+) printf( X%d ,i); printf(n); m=0;for(i=0;ir;i+)printf(X%d ,JJik);for(j=0;jl;j+)printf(%lf ,Rkij);m+;if(m=6) printf(n);m=0;第

22、12 页 共 25 页 /-/-对最优解的未知数范围进行计算-/-printf(n);m=0;n=0;double max,min; printf(在初始单纯形表的基础上，其他条件不变，n 现在对第 Xi 进行范围的确定，请输入 i：); /这表将 i 设为 q scanf(%d,&q);for(i=0;ir;i+)/找到第 q 个未知数 Xq 对应的基在第 p 行 if(q+1)=JJi0)p=i;/-调用公式求范围- for(i=0;i1;i+)/i 是 CB 的行 for(j=0;jr;j+)/j 是 BB 的列 for(k=0;kr;k+)/k 是 CB 的列和 BB 的行 s

23、um=sum+CBik*BBkj; if(BBqj0)H0n=(-1)*(sum-CBip*BBpj)/BBpj; n+; if(BBqj=0)第 13 页 共 25 页E0m=0;m+;sum=0; /-接下来找左边的最大值，和右边的最小值- max=E00;min=H00;for(i=0;i1;i+)for(j=0;jm;j+)if(maxEij)max=Eij;/最大 for(i=0;i1;i+)for(j=0;jHij)min=Hij;/最小 /-输出范围- if(m0&n0)if(maxmin)printf(无解);if(maxmin)printf(第 %d 个未知数的取值范

24、围为：%lf = X 0) printf(第 %d 个未知数的取值范围为：%lf = X ,q,max) ;elseprintf(第 %d 个未知数的取值范围为: X =%lf ,q,min) ; return 0;第 15 页 共 25 页3 实验研究小结3.1 使用说明详述3.1.1 本部分功能操作注意事项为了程序测试时输入方便简洁，本程序将输入的数据放在文件中，一个单纯形表放在 3 个文件中，这三个文件分别是：1.约束条件系数矩阵，b 放在矩阵的右边（用的是 double 形） ；2.目标函数系数矩阵（double 形） ；3.对应的基（int形） 。若是要测试其他例题，只要将其他例题中

25、的系数矩阵分为三块放在文件中即可（要注意是双精度还是整形）还有，在程序开始时，要求输入的行和列是进行变换后的行和列（其中可能有松弛变量，人工变量等）3.1.2 本部分功能与其他系统的关系在现实问题反映到线性规划问题时，环境的多变往往会导致结果的改变，那么这个原来线性规划问题就失效了。所以，这就要求计划对问题的改变做出有效的反应，因此设计了此算法，对问题进行灵敏度分析。在现实中，市场的变化会导致利润等问题改变，由此，目标函数系数也随之改变。本程序实现了目标函数的改变还能继续分析是否最优，最优解的什么，以及目标函数允许变化的范围。这就提高了线性规划问题在现实中应变能力，使之应用更为广泛3.2 测试案例详述美佳公司计划制造 I，II 两种家电产品。已知各制造一件时分别占用设备 A，设备 B 的台时、调试工序时