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

课程设计（论文）课程名称：系统优算法设计与实现题目：线性规划灵敏度分析算法设计与实现院（系）：专业班级：姓名：学号：指导教师：2014年7月18日西安建筑科技大学课程设计（论文）任务书专业班级：信管1302学生姓名：黄小青指导教师（签名）：一、课程设计（论文）题目线性规划灵敏度设计算法与实现二、本次课程设计（论文）应达到的目的《系统优算法设计与实现》课程设计是实践教学环节的重要组成部分，其目的是通过课程设计加深学生对系统优算法设计与实现基本知识掌握和基本编程技能的培养，提高综合运用知识解决实际问题的能力；本次要求学生通过掌握系统优算法设计与实现的程序设计方法，以提高学生独立分析问题、解决问题的能力，逐步增强实际工程训练。三、本次课程设计（论文）任务的主要内容和要求设计内容：本程序在已知初始单纯形表和最终单纯形表的情况下，对目标函数系数进行灵敏度分析，要实现三个个目标。其一：在输入初始单纯形表和最终单纯形表后，将单纯形表进行矩阵的分离，然后输入改变后的目标函数，利用单纯形法的矩阵描述进行计算，计算出调整后的结果，反映到最终形表中，检验是否最优。其二：若检验结果不是最优，设计单纯形法，用单纯形法进行计算，直到最优解。其三：在初始单纯形表条件下，其他条件不变，对目标函数系数进行调整，在最优解不变的情况下，确定目标函数系数的变化范围。要求：1．提交正确的和完整的程序设计代码。2．提交设计说明书。3.接受现场检验。四、应收集的资料及主要参考文献：应收集的资料：本次设计应该收集和题目背景的有关资料。主要参考文献：1.胡运权.《运筹学》.清华大学出版社，20122.谭浩强.《C程序设计（第四版）》.清华大学出版社，20103.谭浩强.《C++程序设计（第二版）》.清华大学出版社，2011五、审核批准意见教研室主任（签字）设计总说明分析线性规划灵敏度分析算法这个问题。把解决问题所需条件、原始数据、输入输出信息等搞清楚。对较大问题（单纯形法的计算和线性规划的矩阵描述）的用文字和流程图描述。分析完后问题后建立数学模型，把问题数学化公式化，此算法中有矩阵的乘法运算，矩阵的分离与合并（比如将矩阵A分为BN，即A=BN），单纯形法，求最大最小值，设计X变化范围的计算公式之后绘制程序流程图，可用文字概述为以下六步。第一步：从文件读入数据。第二步：根据要求分离矩阵。第三步：输入目标函数，检验最优性。第四步：若不是最优，设计单纯形表算法，进行计算，检验最优性。重复第四步，直到最优。第五步：输出改变目标函数后最终单纯形表。第六步：输入要计算变化范围的X，利用公式计算，然后输出。编制程序，画完流程图后，就可以进行编程了。根据流程图编程，为防止最后检查时错误过多无从下手，对程序进行分模块编程，把一些小的算法先编程调试成功，再带入主程序。编写主程序的时候，每写完一小部分，要进行调试，检查是否有逻辑或语法错误。在编程中，还要对定义的变量和编写的语句进行解释，让程序更易理解。如果还未编程等待编程的语句和可插入其他功能程序的地方也要进行解释说明，这样，对后续的程序修改和优化也有帮助。编写完毕，对程序进行调试运行。关键字：线性规划，灵敏度，程序设计，C语言第1页共24页目录1绪论......................................................11.1内容简介................................................11.2本次课设目的............................................11.3课设内容................................................12.线性规划灵敏度分析算法设计说明...........................22.1程序设计过程详述........................................22.2编程实现过程详述........................................22.4原代码..................................................33实验研究小结.............................................163.1使用说明详述...........................................163.1.1本部分功能操作注意事项.............................163.1.2本部分功能与其他系统的关系.........................163.2测试案例详述..........................................16参考文献...................................................19第1页共24页1绪论1.1内容简介在线性规划问题中的参数往往是一些估计和预测的数字，随着环境的变化（如市场条件变化，工艺技术条件的变化），其最优解也会随之变化。当这些参数中的一个或多个发生改变是，问题的最优解会有什么变化，或者这些参数在什么范围变化时，问题的最优解或最优基不变。为解决线性规划的目标函数的这些问题，本程序中对此进行灵敏度分析。1.2本次课设目的本程序中对线性规划的目标函数做出灵敏度分析，以书（胡运权.《运筹学》.清华大学出版社，2012，P64）中例五为例，分析市场条件变化后利润的变化，导致目标函数改变，分析这些变化对结果的影响，以及目标函数在什么范围变化是，问题的最优解不变。1.3课设内容一：调整目标函数系数，将参数的改变反映到最终单纯形表中，判断是否最优，若不是，继续计算二：设计单纯形法算法三：确定目标函数系数可变化的范围第2页共24页2.线性规划灵敏度分析算法设计说明2.1程序设计过程详述一．分析问题，了解问题要求和目的。二．程序分块和建立数学模型，用公式和文字把题目中涉及到的算法一步步分解成小模块，依次解决。其中包括：文件的读入，矩阵的乘法运算，矩阵的分离与合并（比如将矩阵A分为BN，即A=BN），单纯形法，求最大最小值，设计X变化范围的计算公式等三．建立流程图，把二中的算法按照步骤组合起来。第一步：从文件读入数据。第二步：根据要求分离矩阵。第三步：输入目标函数，检验最优性。第四步：若不是最优，设计单纯形表算法，进行计算，检验最优性。重复第四步，直到最优。第五步：输出改变目标函数后最终单纯形表。第六步：输入要计算变化范围的X，利用公式计算，然后输出。四．对各个小模块进行编程，调试成功后，再根据流程图编写主程序，顺便把要用到小模块加进去，然后进行调试。2.2编程实现过程详述第一步：从文件读入数据。第二步：根据要求分离矩阵。第三步：输入目标函数，检验最优性。第四步：若不是最优，设计单纯形表算法，进行计算，检验最优性。重复第四步，直到最优。第五步：输出改变目标函数后最终单纯形表。第六步：输入要计算变化范围的X，利用公式计算，然后输出。第3页共24页2.4原代码#includestdio.h#includemath.h#includestring.h#includestdlib.h#includedos.hintmain(){doubleF[10][10],b[10][50],C[50][10];intJ[10][50];//初始矩阵：F是AX+IX=b的AIb。C是maxz=CX+0X的C0。J是基doubleFF[10][10],bb[10][50],CC[50][10],BB[10][10];intJJ[10][50];//最终单纯形表：BB是B的逆矩阵doubleR[50][10][20];inti,j,k;intr,l;//r为约束条件矩阵的行。l为约束条件矩阵的列printf(输入约束矩阵的行r和列l：);scanf(%d%d,&r,&l);printf(\n);//---------------------输入初始单纯形表和最终单纯形表-----------------------------FILE*fp=fopen(D:\\A.txt,r);//输入F[3][6]if(!fp)return0;i=0;j=0;while(!feof(fp)){fscanf(fp,%lf,&F[i][j]);j++;if(j==6){i++;j=0;}}fclose(fp);FILE*fp1=fopen(D:\\B.txt,r);//输入C[0][5]if(!fp1)return0;第4页共24页i=0;while(!feof(fp1)){fscanf(fp1,%lf,&C[0][i]);i++;}fclose(fp1);FILE*fp2=fopen(D:\\C.txt,r);//输入基j[3][0]if(!fp2)return0;i=0;while(!feof(fp2)){fscanf(fp2,%d,&J[i][0]);i++;}fclose(fp2);FILE*fpd=fopen(D:\\D.txt,r);//输入FF[3][6]if(!fpd)return0;i=0;j=0;while(!feof(fpd)){fscanf(fpd,%lf,&FF[i][j]);j++;if(j==6){i++;j=0;}}fclose(fpd);FILE*fpe=fopen(D:\\E.txt,r);//输入CCif(!fpe)return0;第5页共24页i=0;while(!feof(fpe)){fscanf(fpe,%lf,&CC[0][i]);i++;}fclose(fpe);FILE*fpf=fopen(D:\\F.txt,r);//输入基if(!fpf)return0;i=0;while(!feof(fpf)){fscanf(fpf,%d,&JJ[i][0]);i++;}fclose(fpf);//--------------------输出初始单纯形表和最终单纯形表-------------------------------------printf(线性规划的初始单纯形表为：\n);//输出初始单纯形表printf(Cj);for(i=0;il-1;i++){printf(%lf,C[0][i]);}printf(\n);printf(基);printf(b);for(i=0;il-1;i++){printf(X%d,i);}printf(\n);k=0;for(i=0;ir;i++){printf(X%d,J[i][0]);for(j=0;jl;j++)第6页共24页{printf(%lf,F[i][j]);k++;if(k==6){printf(\n);k=0;}}}printf(\n\n);printf(最终单纯形表为：\n);//输出最终单纯形表printf(Cj-Zj);for(i=0;il-1;i++){printf(%lf,CC[0][i]);}printf(\n);printf(基);printf(b);for(i=0;il-1;i++){printf(X%d,i);}printf(\n);k=0;for(i=0;ir;i++){printf(X%d,JJ[i][0]);for(j=0;jl;j++){printf(%lf,FF[i][j]);k++;if(k==6){printf(\n);k=0;}}}//--------------------------分离出b[r][0]，bb[r][0]，BB[r][r]（B的逆）----------------------第7页共24页for(i=0;ir;i++){b[i][0]=F[i][l-1];}for(i=0;ir;i++){bb[i][0]=FF[i][l-1];}for(i=0;ir;i++){k=0;for(j=l-r-