毕业论文123ER3.doc

2011年度本科生毕业论文（设计）一种改进的求解线性规划问题的单纯形法院 系： 专 业： 年 级： 学生姓名： 学 号： 导师及职称： 2011年6月2011 annual graduation thesis (project) of the college undergraduate an improved simplex method for solving linear programming problemdepartment: major: grade: students name: student no.: tutor: june 2010毕业论文（设计）原创性声明本人所呈交的毕业论文（设计）是我在导师的指导下进行的研究工作及取得的研究成果。据我所知，除文中已经注明引用的内容外，本论文（设计）不包含其他个人已经发表或撰写过的研究成果。对本论文（设计）的研究做出重要贡献的个人和集体，均已在文中作了明确说明并表示谢意。 作者签名： 日期： 毕业论文（设计）授权使用说明本论文（设计）作者完全了解红河学院有关保留、使用毕业论文（设计）的规定，学校有权保留论文（设计）并向相关部门送交论文（设计）的电子版和纸质版。有权将论文（设计）用于非赢利目的的少量复制并允许论文（设计）进入学校图书馆被查阅。学校可以公布论文（设计）的全部或部分内容。保密的论文（设计）在解密后适用本规定。 作者签名： 指导教师签名：日期： 日期： 毕业论文（设计）答辩委员会(答辩小组)成员单姓名职称单位备注数学学院组长数学学院数学学院 红河学院本科毕业论文（设计）摘要 通过对单纯形法的分析和研究, 针对无第一可行基的情况, 利用单位资源所获得的增量由大到小规定进基顺序, 从而得到线性规划问题的一个基. 该单纯形法可有效简化求解过程, 同时, 不再引入人工变量, 为解决线性规划问题提供了一个有效的方法.关键词: 线性规划; 单纯形法; 最大增量abstract through analysing and studying the simplex method, in the absence of the first feasible base , uses unit resources obtained by big incremental stipulated to small incremental stipulated into base sequence, can get a base of linear programming problems. the simplex method can implify the solution process effectively, at the same time, we neednt to introduce artificial variables, it is an effective method for solving the linear programming problems. key words: linear programming; simplex method; biggest incremental 目录第一章 引言1第二章 相关定理与预备知识2第三章 算法步骤4第四章 实例74.1 本文算法求解74.2 原两阶段法求解9第五章 结束语12参考文献13致谢15第一章 引言单纯形法是求解线性规划问题的通用方法, 也是目前为止最为成熟有效的解法. 在具有第一可行基的情况下, 用单纯形法求解比较简单, 只涉及到矩阵及其初等变换理论; 在无第一可行基的情况下, 需要引入人工变量, 借助“大m法”或“两阶段法”求解. 两种方法确实为没有现成初始可行基的线性规划问题提供了一种解决途径, 但其缺点1也是众所周知的. 计算机求解时, 由于每一台计算机都有一定字长的限制, 于是只能用很大的数来代替充分大数, 这样就可能造成计算上的错误; 采用两阶段法, 要把原线性规划问题化为两个线性规划问题来求解, 这势必会使得计算过程繁琐、冗长, 并且计算机的存储量也随之增加.为解决这一问题, 文献2-10做了一些尝试, 为求解线性规划问题初始基本可行解提供了很多有效的解法, 在其计算上, 与传统的大法或两阶段法相比, 确实体现出了它们的优点, 但有的计算量还是很大, 且计算过程容易出错, 计算方法也不太容易掌握.事实上, 只要对标准形式约束条件的增广矩阵有选择的作初等行变换就可以在系数矩阵中得到单位矩阵, 从而得到基本解, 若在初等行变换后常数项非负, 就可以得到线性规划问题的一个比较接近该问题最优解的初始基本可行解; 若在初等行变换后常数项为负, 根据定理2.3进行换基迭代便可得到基本可行解 或判断原问题无解.得到了一个基本可行解以后, 我们要确定它是不是最优解, 在单纯形法解线性规划问题中, 由解的判别准则及最优性检验来确定得到的基本可行解是否为最优解. 如果检验基本可行解不是最优解, 那么求新的基本可行解的方法为: 首先从非基变量中选择一个入基变量, 一般的方法是选择检验数大于零的最大者(对最小化问题, 选择检验数小于零的最小者)作为入基变量, 再通过最小比值测试确定主元行, 使用初等行变换的方法, 迭代运算后得到新的基本可行解, 重复此过程直到求得最优解.11 第二章 相关定理与预备知识设线性规划最大化问题的标准形式为:（lp）定理 2.111 对线性规划问题（lp）, 若存在第行有且对有所有为负数（为正数）则称该行为矛盾行, 此时线性规划问题无解.定理 2.2 对线性规划问题（lp）, 若存在第行与第行有 （2-1）则称线性规划问题存在多余行.设, （2-2）,（2-3）定理 2.311 在具有典式的线性规划问题对应的单纯形表中, 若则以为主元, 若, 则以为主元, 对单纯形表进行初等行变换, 则新的基解中小于的项至少减少一个, 重复上述过程, 可以得到该单纯形问题的可行解.注: 当以为主元若, 时, 对单纯形表进行初等行变换, 新的基解中小于0的项有可能不会减少, 重复上述过程后出现矛盾行.推论 2.3.111 在具有典式的线性规划问题的单纯形表中, 若设=, （2-4）则以为主元, 对单纯形表进行初等行变换, 得到的新基必定为可行基.推论 2.3.211 在具有典式的线性规划问题的单纯形表中, 若设 = , （2-5）则以主元, 对单纯形表进行初等行变换, 得到的新基必为可行基.定理 2.512 可行比: 某列比值的最小值, 称为该列的可行比. （2-6）定理 2.612 增量: 各列可行比与该列对应的目标函数的系数的积, 叫做该列的增量.第三章 算法步骤具体步骤:step 1 将所给线性规划问题化为标准形;step 2 判断约束矩阵中有无矛盾行, 若有, 则该线性规划问题无解, 停止运算; 否则转下一步;step 3 判断约束矩阵中有无多余行, 若有, 则任意留下其中一行, 删除另一行;step 4 建立如下初始表格（表3-1）, ; （3-1）表3-1 改进的单纯形法初始表 step 513 若表 3-1中对所有的, 恒有, 且, 则原问题无可行解, 停止计算; 若且, 则原问题只有唯一的可行解=0, 亦停止计算; 否则转下一步;step 6 确定入基变量, 考察目标函数的决策变量, 计算出各列所获得的增量. 从大到小依次为入基变量, 以及相应的入基顺序. 最大增量对应的变量为第一进基变量, 根据从大到小的顺序, 确定其他变量的入基顺序. 若有多个相等的增量, 则选取下标最小者优先入基;step 713 根据入基的先后顺序依次将该列化为（1位于行, 为第个进基的变量）, 每化出一个基变量在表表3-2中和下方分别附上和, 并计算一次及, 其中, （3-2）即已经产生了基变量的行不再累加到与中, 若而或者而, 则原问题无解, 停止运算; 若则原问题有唯一最优解=0, 亦停止运算; 否则转下一步;表3-2 改进单纯形法计算表 step 8 若某一列不能化成（1位于行，为第个进基的变量）, 则选该进基变量后面一个进基变量替代该进基变量进基;step 9 根据算出的结果: 若在初等行变换后常数项非负, 则该解为可行解, 转入传统的单纯形表迭代便可以求出原问题的最优解; 若在初等行变换后常数项存在负数, 选取第列进基（是为负的对应系数矩阵中，负分量最多的列）; 若存在多个, 则选取下标最小者进基, 求出 以及, 根据定理 2.3进行换基迭代便可以求出原问题的一个可行解（或判断原问题无解）. 转入传统单纯形表迭代便可求出原问题的最优解.第四章 实例分别用现在提出的新算法和两阶段法来求解下面线性规划问题4.1 本文算法求解表4-1-1 改进的单纯形法初始表 =（10, 10, 12，-10）, 因此入基顺序依次为, , , 表4-1-2 改进的单纯形法第一次迭代表 续表4-1-2 表4-1-3 改进的单纯形法第二次迭代表310 表4-1-4 改进的单纯形法第三次迭代表由, 所以为原问题的可行解表4-1-5 转入传统单纯形迭代表检验数, 所以该问题有最优解, 即 =，=15 4.2 原两阶段法求解表4-2-1 第一阶段初始表表4-2-2 第一阶段第一次迭代表3104续表4-2-206表4-2-3 第一阶段第二次迭代表0表4-2-4 第二阶段迭代表 续表4-2-4 1检验数, 所以该问题有最优解, 即=，=15 第五章 结束语第五章 结束语本文提出的算法, 从以上实例可以看出, 该算法在不用引入人工变量的情况下, 求出初始基本可行解, 避免了求解辅助问题的过程, 在求解过程中减少了计算量, 使计算变得更加简单, 且在计算过程中也不容易出错. 以上论述及求解实例说明该方法是行之有效的, 是求解线性规划问题最优解的一种有效方法.参考文献 1 刘满凤, 陶长琪, 柳键等. 运筹学教程m. 北京: 清华大学出版社, 2010: 46-82.2 张卫国. 一种求线性规划问题的初始基本可行解的新算法j. 西安科技学院学报, 2002, 22(3): 321-324.3 金涛, 刘三阳, 孙小军. 一种线性规划问题单纯形法的改进算法j. 宝鸡文理学院学报(自然科学版) , 2007, 27(4): 268-278.4 展丙军. 单纯形法的改进及其应用j. 大庆师范学院学报, 2007, 27(2): 5-7.5 范国兵. 一种求线性规划问题的初始基本可行解的方法j. 华北科技学院学报, 2007, 4(2): 95-96.6 马烁, 赵天玉. 线性规划两阶段法的简易算法j. 太原师范学院学报(自然科学版) , 2007, 6(4): 23-26.7 陶凤玲, 宛士春. 利用“准最优基”简化单纯形法求解过程j. 武汉大学学报(工学版) , 2004, 37(1): 68-71. 8 范国兵. 一种求线性规划问题的初始基本可行解的方法j. 重庆工商大学学报(自然科学版) , 2007, 24(3): 234-236.9 梁平, 张相斌, 王海娇, 阎楠. 避免引入人工变量求线性规划可行基的一个新方法j. 数学的实践与认识, 2009,39(10): 136-139.10 吕为, 赵佳因. 线性规划数学模型的一种新解法j. 北京市经济管理干部学院学报, 2000 , 15(1): 41-44. 11 董兵, 梁俊. 一种改进的单纯形最优化方法j. 重庆师范大学学报(自然科学版) , 2010 , 27(4): 9-11.12 石岩涛. 用最大增量法解线性规划问题j. 丹东纺专学报, 2002, 9(3): 55-56.13 范国兵. 线性规划问题的一种改进的单纯形法j. 海南大学学报(自然科学版) , 2007, 25(3): 243-247.14 范国兵. 线性规划两阶段法的改进j. 长江大学学报(自然版)理工卷, 14 2007, 4(2): 134-135.15 江道琪, 何建坤, 陈华松. 实用线性规划方法及其支持系统m. 北京: 清华大学出版社, 2006: 9-33.16 牛映武, 杨文鹏, 郭鹏等. 运筹学(第2版)m. 西安: 西安交通大学出版社, 2006: 16-33.致谢 走的最快的总是时间, 来不及感叹, 大学生活已接近尾声. 四年的学习生活即将结束, 回顾四年的学习生活, 感受颇深, 收获丰厚.在论文的写作过程中,有很多困难, 无论是在理论学习阶段, 还是在论文的选题、资料查询、开题、研究和撰写的每一个环节, 无不得到导师的悉心指导和帮助.借此机会我向导师表示衷心的感谢! 同时, 我要感谢红河学院授课的各位老师, 正是由于他们的传道、授业、解惑, 让我学到了专业知识, 并从他们身上学到了如何求知治学、如何为人处事.同时我也要感谢我的同学给予我的帮助,为我撰写论文提供了不少建议和帮助.我要感谢,非常感谢我的导师曹香莲老师.她为人随和热情, 治学严谨细心.在闲聊中她总是能像知心朋友一样鼓励我,在论文的写作和措辞等方面她也总会以“专业标准”严格要求我,从选题、定题开始,一直到最后论文的反复修改、润色,曹老师始终认真负责地给予我深刻而细致地指导,帮助我开拓研究思路,精心点拨、热忱鼓励.正是曹老师的无私帮助与热忱鼓励,我的毕业论文才能够得以顺利完成,谢谢曹老师! 还要感谢和我同一设计小组的几位同学, 是你们在我平时设计中和我一起探讨问题, 并指出我设计上的误区, 使我能及时的发现问题把设计