课程设计论文-王丹娜150404112

《课程设计论文-王丹娜150404112》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、02/康甲找女皆课程设计（论文）课程名称：系统优化算法设计与实现题目：求解线性规划的两阶段法设计与实现院（系）：管理学院专业班级：信管1501姓名：王丹娜学号：150404112指导教师：黄光球2014年7月18日血妥建疑科技丈曇课程设计（论文）任务书专业班级：信管1501学生姓名：王丹娜指导教师（签名）:「二「谏理丧淙「逐文j遍旨求解线性规划的两阶段法设计与实现二、本次课程设计（论文）应达到的目的《系统优算法设计与实现》课程设计是实践教学环节的重要组成部分，其目的是通过课程设计加深学生对系统优算法设计与实现基本知识掌握和基本编程技能的培养，提高综合运用

2、知识解决实际问题的能力；本次要求学生通过掌握系统优算法设计与实现的程序设计方法，以提高学生独立分析问题、解决问题的能力，逐步增强实际工程训练。三、本次课程设计（论文）任务的主要内容和要求设计内容：一般线性规划问题具有线性方程组的变量数大于方程个数，这时有不定的解。第一阶段：不考虑原问题是否存在基可行解；给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数和要求实现最小化。第二阶段：将第一阶段计算得到的最终表，除去人工变量。将目标函数行的系数,换原问题的li标函数系数，作为第二阶段计算的初始表，再进行一次单纯形法求解，若检验数符合条件时，非基变量的检

3、验数小于0,则判断为无界解，若非基变量的检验数为0,则判断为存在无穷多最优解，否则这次求解得到最优解。要求：1.提交正确的和完整的程序设计代码。2.提交设计说明书。3.接受现场检验。四、应收集的资料及主要参考文献：应收集的资料：本次设计应该收集和题目背景的有关资料。主要参考文献：1.胡运权.《运筹学》.清华大学出版社，2012五、审核批准意见教研室主任（签字）设计总说明常用的解线性规划问题的方法有图解法，单纯形法，对偶单纯形法，解乘数法，椭球法等。而木论文即主要阐述的是从属于单纯形法的两阶段法。两阶段法第一阶段是先求解一个目标函数中只包含人工变量的线性规

4、划问题，当第一阶段求解结果表明问题有可行解时，第二阶段是从第一阶段的最终单纯形表出发，去掉人工变量，并按问题原来的目标函数，继续寻找问题的最优解，即是一种为使人工变量被替换出成为非基变量的方法。与大M法同时被广为使用，但相较于大M法，两阶段法能够求的更准确地结果。关键字：线性规划，单纯形法，两阶段法，大M法1绪论11.1内容简介11.2本次课设目的11.3课设内容22求解线性规划的两阶段法设计与实现设计说明32.1程序设计过程详述32.2编程实现过程详述52.4原代码73实验研究小结223.1使用说明详述223.1.1本部分功能操作注意事项223.1.2

5、本部分功能与其他系统的关系223.2测试案例详述23参考文献281绪论1.1内容简介在各种优化算法中，两阶段法（Twostagemethod）是非常重要的一种。即如果线性规划模型中的约束条件系数矩阵不存在单位向量组，阶梯式应先加入人工变量，人工构成一个单位向量组，其只起过渡作用，不应影响决策变量的取值，两阶段法即可控制人工变量取值。寻找线性规划问题初始基可行解的一种方法.把增加人工变量的线性规划问题分为两个阶段去求解.第一阶段是构造一个辅助的人工目标函数。若原问题有可行解，则在本阶段的最终单纯形表屮使人工变量均为非基变量。此时，划去人工变量所在的列与人工

6、目标函数所在的行，就得到原问题的初始可行基对应的单纯形表，进入第二阶段。1.2本次课设目的（1）通过C语言求解线性规划的两阶段法设计与实现（2）熟悉运用开发环境，基于VC++6.0的软件开发环境；（3）完成课程设计基本任务的设计及编码；（4）熟练掌握VC++6.0上的基本的调试方法。1.3课设内容两阶段法第一阶段是先求解一个目标函数中只包含人工变量的线性规划问题，即令目标函数中其变量的系数取0,人工变量的系数取某个止的常数，（一般取1）,在保持原问题约束条件不变的情况下求这个目标函数极小化的解。显然在第一阶段中，当人工变量取值为0的时候，目标函数值也为0

7、。这时候的最优解就是原线性规划问题的一个可行解，。如果第一阶段求解结果最优解的目标函数值不为0,也即最优解的基变量中含有人工基变量，表明原线性规划问题无可行解。当第一阶段求解结果表明问题有可行解时，第二阶段是从第一阶段的最终单纯性表出发，去掉人工变量，并按问题原来的目标函数，继续寻找问题的最优解。2求解线性规划的两阶段法设计与实现设计说明2.1程序设计过程详述第一步：求出线性规划的初始基可行解，列出初始单纯形表。第二步：进行最优性检验。第三步;从一个基可行解转换到另一个FI标函数值更大的基可行解，列出新的单纯形表。⑴确定换入基变量。只要检验数5>0,对应

8、的变量勺就可作为换入基的变量，当有一个以上检验数大于零时，一般从中找出最大的一个