哈工大运筹学大作业-对偶单纯形法对比.docx

《哈工大运筹学大作业-对偶单纯形法对比.docx》由会员分享，可在线阅读，更多相关《哈工大运筹学大作业-对偶单纯形法对比.docx（7页珍藏版）》请在课桌文档上搜索。

1、运筹学对偶单纯形法与单纯形法对比分析摘要：这篇论文主要介绍了对偶单纯形法的实质、原理、流程和适用条件等.将对偶单纯形法与单纯形法的基本思想进行对比分析,从而说明对偶单纯形法的优点和适用范围.关键词：对偶单纯形法；对偶理论；单纯形法；基本思想在线性规划早期发展阶段的众多重要发现中,对偶的概念与其分支是其中最重要的内容之一.这个发现指出,对于任何一个线性规划问题都具有对应的称为对偶问题的线性规划问题.对偶问题与原问题的关系在众多领域都非常有用.一教学目标：通过对偶单纯形法的学习,加深对对偶问题的理解.掌握对偶单纯形法的解题过程,理解对偶理论的其原理,了解对偶单纯形法的作用和应用范围二教学内容：1）

2、 对偶单纯形法的思想来源2） 对偶单纯形法原理3） 对偶理论的实质4） 单纯形法和对偶单纯形法的比较三教学进程：一、对偶单纯形法的思想来源所谓对偶单纯形法,就是将单纯形法应用于对偶问题的计算,该方法是由美国数学家C.莱姆基于1954年提出的,它并不是求解对偶问题解的方法,而是利用对偶理论求解原问题的解的方法.二、对偶问题的实质下面是原问题的标准形式以与其对应的对偶问题：原问题对偶问题Max Z=j=1ncjxjs.t. j=1naijxjbi i=1,2,mxj0 j=1,2,nMin W=j=1mbiyis.t. j=1naijyicj j=1,2,nyi0 i=1,2,m从而可以发现如下规

3、律：1.原问题目标函数系数是对偶问题约束方程的右端项.2.原问题约束方程的右端项是对偶问题目标函数的系数.3.原问题一个变量在所有约束方程中的系数是对偶问题一个约束方程中的所有系数.三、对偶单纯形法原理对偶单纯形法是通过寻找原问题的对偶问题的可行解来求解原问题的最优解的方法,它的应用包括影子价格和灵敏度分析等.为了理解对偶单纯形法为什么能够解出原方程的最优解,我们需要对对偶理论的几个基本原理有所了解.1.弱对偶性如果xj(j=1,n)是原问题的可行解,yi(i=1,m)是其对偶问题的可行解,则恒有j=1ncjxji=1mbiyi证明：由于对偶方程中原问题的约束条件是各行的aijxj之和小于等于

4、yi的系数bi,而对偶问题的约束条件是各行的aijyi之和小于等于xj的系数cj,故将j=1ncjxj和i=1mbiyi分别和i=1mj=1nxjaijyi比较,可得上述结论.2.最优性如果xj(j=1,n)是原问题的可行解,yi(i=1,m)是其对偶问题的可行解,且有j=1ncjxj=i=1mbiyi则xj(j=1,n)是原问题的最优解,yi(i=1,m)是其对偶问题的最优解.证明：由j=1ncjxji=1mbiyi可得j=1ncjxji=1mbiyi=j=1ncjxji=1mbiyij=1ncjxj=i=1mbiyi故可知xj(j=1,n)是原问题的最优解,yi(i=1,m)是其对偶问题的

5、最优解.3.强对偶性如果原问题有最优解,那么其对偶问题也有最优解,且有maxz=minw.证明：设B为原问题式的最优基,那么当基为B时的检验数为,其中为由基变量的价值系数组成的价值向量.既然B为原问题式的最优基,那么有.令,那么有,从而是对偶问题式的可行解.这样一来,是对偶问题的可行解,是原问题的最优基可行解.由于,而,从而有.根据最优性,命题得证.4.线性规划的问题原问题与对偶问题之间存在一对互补的基解,其中原问题的松弛变量对应对偶问题的变量,对偶问题的剩余变量对应原问题的变量；这些相互对应的变量如果在一个问题中是基变量,则在另一问题中是非基变量；将这对互补的基解分别代入原问题和对偶问题的目

6、标函数有z=w.四、对偶单纯形算法流程在上述的理论基础上,可知用单纯形法求解线性规划问题时,在得到原问题的一个基可行解问题同时,在检验数行得到对偶问题的一个基解.单纯形法的基本思想是保持原问题为可行解的基础上,通过迭代增大目标函数,当其对偶问题也为可行解时,就达到了目标函数的最优值.而对偶单纯形法的基本思想则是保持对偶问题为可行解的前提下即单纯性表最后一行检验数都小于零,通过迭代减小目标函数,当原问题也是可行解时,就得到了目标函数的最优解.故我们可以得到对偶单纯形法求解过程如下：1.将原问题化为标准型,找到一个检验数都小于等于零的对偶问题的初始可行基.2.确定换出基的变量对于小于零的bi,找到

7、最小的一个br,其对应的xr为换出基的变量3.确定换入基的变量1为了使迭代后表中的第r行基变量为正值,因而只有对应aij小于零的非基变量才可以作为换入基的变量；2为了使迭代后表中对偶问题仍为可行解,令=minjcjzjaijari0=cszsars称ars为主元素,xs为换入基的变量.4.用换入变量替换换出变量,得到一个新的基.再次检查是否所有的bi大于等于零.如果是,则找到了最优解,如果否,则再次进行变换.对偶单纯形法的算法流程图开始化原问题为标准型找出一个对偶问题的初始可行基B0,计算非基变量检验数全部检验数j0并列出初始单纯形表是bi 都0？否确定换出和换入的基变量： 换出最小的右端项b

8、i所对应的基变量； 按公式=minj/aij,aij0=s/aij计算最小比值,所对应的基变量为换入计算检验数,列出新的单纯形表已找到最优解结束五、对偶单纯形法例题下面用一个例子来说明对偶单纯形法的解题过程.Min z=5x1+2x2+4x3s.t.3x1+x2+2x346x1+3x2+5x310x1,x2,x301.化为标准型Max z=-5x1-2x2-4x3+0x4+0x5s.t.3x1x22x3+x4=46x13x25x3+x5=10x1,x2,x3,x4,x502.列出原始单纯形表cj-5-2-400CB基 bx1x2x3x4x50 x4 -40 x5-10-3-1-210-6-3-

9、501cj-zj-5-2-4003.找出最小的bi,即b5=-10.选择x5作为换出变量.=minjcjzjaijarin,那么对偶问题有n个约束方程,而原问题有m个约束方程,所以对偶问题有更少的约束方程数量,那么通过对偶单纯形法的运用比起直接只用单纯形法将会显著的减少计算量.3.弱对偶性和强对偶性是对偶理论的关键原理.对偶问题可以用来对原问题的计划方案进行评价.我们可以用一个对偶问题的可行解和目前原问题的计划方案进行比较,如果两个目标函数值相等或比较接近,则可以说明原问题的计划方案已经是可以看做最优了.4.对偶理论在灵敏度分析和影子价格计算中有着重要的作用.七、单纯形法和对偶单纯形法的基本思

10、想比较通过以上的分析可知,对偶单纯形法其实相当于单纯形法的一种变形,只不过在运用对偶单纯形法解线性规划时需要将单纯形表旋转一下.单纯形表中的b列实际上是对偶问题的非基变量的检验数, 而原单纯形表的检验数为对偶问题的基解, 这样可以理解为通过旋转90运用单纯形法求解线性规划.从求解思路上来说,单纯形法是首先保证基解是原问题的基可行解bi不小于零,然后通过变量的换入换出增大目标函数值,直到其同时成为对偶问题的可行解,根据强对偶性原理,可知这个解就是最优解.而对偶单纯形法则是首先保证基解是对偶问题的可行解检验数都不大于零,然后逐步减小对偶标准化的目标函数值,使其成为原问题的可行解.两种方法殊途同归,其本质是一样的.6 / 7