资源描述：
《哈工大运筹学大作业-对偶单纯形法对比》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、运筹学课程运筹学对偶单纯形法与单纯形法对比分析大作业哈尔滨工业大学工业工程系学生姓名:学号：11208401指导教师：成绩：评语：8运筹学对偶单纯形法与单纯形法对比分析摘要：这篇论文主要介绍了对偶单纯形法的实质、原理、流程和适用条件等。将对偶单纯形法与单纯形法的基本思想进行对比分析，从而说明对偶单纯形法的优点和适用范围。关键词：对偶单纯形法；对偶理论；单纯形法；基本思想在线性规划早期发展阶段的众多重要发现中，对偶的概念及其分支是其中最重要的内容之一。这个发现指出，对于任何一个线性规划问题都具有对应的称为对偶问题的线性规划问题。对偶问题与原问题的关系在众多领域都非常
2、有用。（一）教学目标：通过对偶单纯形法的学习，加深对对偶问题的理解。掌握对偶单纯形法的解题过程，理解对偶理论的其原理，了解对偶单纯形法的作用和应用范围（二）教学内容：1）对偶单纯形法的思想来源2）对偶单纯形法原理3）对偶理论的实质4）单纯形法和对偶单纯形法的比较（三）教学进程：一、对偶单纯形法的思想来源所谓对偶单纯形法，就是将单纯形法应用于对偶问题的计算，该方法是由美国数学家C.莱姆基于1954年提出的，它并不是求解对偶问题解的方法，而是利用对偶理论求解原问题的解的方法。8二、对偶问题的实质下面是原问题的标准形式以及其对应的对偶问题：原问题对偶问题MaxZ=j=1
3、ncjxjs.t.j=1naijxj≤bii=1,2,⋯,mxj≥0j=1,2,⋯,nMinW=j=1mbiyis.t.j=1naijyi≥cjj=1,2,⋯,nyi≥0i=1,2,⋯,m从而可以发现如下规律：1.原问题目标函数系数是对偶问题约束方程的右端项。2.原问题约束方程的右端项是对偶问题目标函数的系数。3.原问题一个变量在所有约束方程中的系数是对偶问题一个约束方程中的所有系数。三、对偶单纯形法原理对偶单纯形法是通过寻找原问题的对偶问题的可行解来求解原问题的最优解的方法，它的应用包括影子价格和灵敏度分析等。为了理解对偶单纯形法为什么能够解出原方程的最优解，我
4、们需要对对偶理论的几个基本原理有所了解。1.弱对偶性如果xj(j=1,⋯,n)是原问题的可行解，yi(i=1,⋯,m)是其对偶问题的可行解，则恒有j=1ncjxj≤i=1mbiyi证明：由于对偶方程中原问题的约束条件是各行的aijxj之和小于等于yi的系数bi，而对偶问题的约束条件是各行的aijyi之和小于等于xj的系数cj，故将j=1ncjxj和i=1mbiyi分别和i=1mj=1nxjaijyi比较，可得上述结论。82.最优性如果xj(j=1,⋯,n)是原问题的可行解，yi(i=1,⋯,m)是其对偶问题的可行解，且有j=1ncjxj=i=1mbiyi则xj(j
5、=1,⋯,n)是原问题的最优解，yi(i=1,⋯,m)是其对偶问题的最优解。证明：由j=1ncjxj≤i=1mbiyi可得j=1ncjxj≤i=1mbiyi=j=1ncjxji=1mbiyi≥j=1ncjxj=i=1mbiyi故可知xj(j=1,⋯,n)是原问题的最优解，yi(i=1,⋯,m)是其对偶问题的最优解。3.强对偶性如果原问题有最优解，那么其对偶问题也有最优解，且有maxz=minw.证明：设B为原问题式(1)的最优基，那么当基为B时的检验数为，其中为由基变量的价值系数组成的价值向量。既然B为原问题式(1)的最优基，那么有。令，那么有，从而是对偶问题式(
6、2)的可行解。这样一来，是对偶问题的可行解，是原问题的最优基可行解。由于，而，从而有。根据最优性，命题得证。84.线性规划的问题原问题及对偶问题之间存在一对互补的基解，其中原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些相互对应的变量如果在一个问题中是基变量，则在另一问题中是非基变量；将这对互补的基解分别代入原问题和对偶问题的目标函数有z=w。四、对偶单纯形算法流程在上述的理论基础上，可知用单纯形法求解线性规划问题时，在得到原问题的一个基可行解问题同时，在检验数行得到对偶问题的一个基解。单纯形法的基本思想是保持原问题为可行解的基础上，通
7、过迭代增大目标函数，当其对偶问题也为可行解时，就达到了目标函数的最优值。而对偶单纯形法的基本思想则是保持对偶问题为可行解的前提下（即单纯性表最后一行检验数都小于零），通过迭代减小目标函数，当原问题也是可行解时，就得到了目标函数的最优解。故我们可以得到对偶单纯形法求解过程如下：1.将原问题化为标准型，找到一个检验数都小于等于零的对偶问题的初始可行基。2.确定换出基的变量对于小于零的bi，找到最小的一个br，其对应的xr为换出基的变量3.确定换入基的变量（1）为了使迭代后表中的第r行基变量为正值，因而只有对应aij小于零的非基变量才可以作为换入基的变量；（2）为了使迭
8、代后表中对
