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

运筹学课程 运筹学对偶单纯形法与单纯形法 对比分析大作业 哈尔滨工业大学工业工程系 学 生 姓 名: 学 号： 11208401 指 导 教 师： 成 绩： 评 语：  运筹学对偶单纯形法与单纯形法对比分析 摘要：这篇论文主要介绍了对偶单纯形法的实质、原理、流程和适用条件等。将对偶单纯形法与单纯形法的基本思想进行对比分析，从而说明对偶单纯形法的优点和适用范围。 关键词：对偶单纯形法；对偶理论；单纯形法；基本思想 在线性规划早期发展阶段的众多重要发现中，对偶的概念及其分支是其中最重要的内容之一。这个发现指出，对于任何一个线性规划问题都具有对应的称为对偶问题的线性规划问题。对偶问题与原问题的关系在众多领域都非常有用。 （一）教学目标： 通过对偶单纯形法的学习，加深对对偶问题的理解。掌握对偶单纯形法的解题过程，理解对偶理论的其原理，了解对偶单纯形法的作用和应用范围 （二）教学内容： 1） 对偶单纯形法的思想来源 2） 对偶单纯形法原理 3） 对偶理论的实质 4） 单纯形法和对偶单纯形法的比较 （三）教学进程： 一、对偶单纯形法的思想来源 所谓对偶单纯形法，就是将单纯形法应用于对偶问题的计算，该方法是由美国数学家C.莱姆基于1954年提出的，它并不是求解对偶问题解的方法，而是利用对偶理论求解原问题的解的方法。 二、对偶问题的实质 下面是原问题的标准形式以及其对应的对偶问题： 原问题 对偶问题 Max Z=j=1ncjxj s.t. j=1naijxj≤bi i=1,2,⋯,m xj≥0 j=1,2,⋯,n Min W=j=1mbiyi s.t. j=1naijyi≥cj j=1,2,⋯,n yi≥0 i=1,2,⋯,m 从而可以发现如下规律： 1.原问题目标函数系数是对偶问题约束方程的右端项。 2.原问题约束方程的右端项是对偶问题目标函数的系数。 3.原问题一个变量在所有约束方程中的系数是对偶问题一个约束方程中的所有系数。 三、对偶单纯形法原理 对偶单纯形法是通过寻找原问题的对偶问题的可行解来求解原问题的最优解的方法，它的应用包括影子价格和灵敏度分析等。为了理解对偶单纯形法为什么能够解出原方程的最优解，我们需要对对偶理论的几个基本原理有所了解。 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比较，可得上述结论。 2.最优性 如果xj(j=1,⋯,n)是原问题的可行解，yi(i=1,⋯,m)是其对偶问题的可行解，且有 j=1ncjxj=i=1mbiyi 则xj(j=1,⋯,n)是原问题的最优解，yi(i=1,⋯,m)是其对偶问题的最优解。 证明：由 j=1ncjxj≤i=1mbiyi 可得 j=1ncjxj≤i=1mbiyi=j=1ncjxj i=1mbiyi≥j=1ncjxj=i=1mbiyi 故可知xj(j=1,⋯,n)是原问题的最优解，yi(i=1,⋯,m)是其对偶问题的最优解。 3.强对偶性 如果原问题有最优解，那么其对偶问题也有最优解，且有maxz=minw. 证明：设B为原问题式(1)的最优基，那么当基为B时的检验数为，其中为由基变量的价值系数组成的价值向量。 既然B为原问题式(1)的最优基，那么有。 令，那么有，从而是对偶问题式(2)的可行解。 这样一来，是对偶问题的可行解，是原问题的最优基可行解。 由于，而，从而有。根据最优性，命题得证。 4.线性规划的问题原问题及对偶问题之间存在一对互补的基解，其中原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些相互对应的变量如果在一个问题中是基变量，则在另一问题中是非基变量；将这对互补的基解分别代入原问题和对偶问题的目标函数有z=w。 四、对偶单纯形算法流程 在上述的理论基础上，可知用单纯形法求解线性规划问题时，在得到原问题的一个基可行解问题同时，在检验数行得到对偶问题的一个基解。单纯形法的基本思想是保持原问题为可行解的基础上，通过迭代增大目标函数，当其对偶问题也为可行解时，就达到了目标函数的最优值。 而对偶单纯形法的基本思想则是保持对偶问题为可行解的前提下（即单纯性表最后一行检验数都小于零），通过迭代减小目标函数，当原问题也是可行解时，就得到了目标函数的最优解。 故我们可以得到对偶单纯形法求解过程如下： 1.将原问题化为标准型，找到一个检验数都小于等于零的对偶问题的初始可行基。 2.确定换出基的变量 对于小于零的bi，找到最小的一个br，其对应的xr为换出基的变量 3.确定换入基的变量 （1）为了使迭代后表中的第r行基变量为正值，因而只有对应aij小于零的非基变量才可以作为换入基的变量； （2）为了使迭代后表中对偶问题仍为可行解，令 θ=minjcj-zjaijari<0=cs-zsars 称ars为主元素，xs为换入基的变量。 4.用换入变量替换换出变量，得到一个新的基。再次检查是否所有的bi大于等于零。如果是，则找到了最优解，如果否，则再次进行变换。 对偶单纯形法的算法流程图 开始 化原问题为标准型 找出一个对偶问题的初始可行基B0，计算非基变量检验数（全部检验数σj≤0）并列出初始单纯形表 是 bi 都≥0？ 否 确定换出和换入的基变量： 换出最小的“右端项”bi所对应的基变量； 按公式θ=min｛σj/a’ij，a’ij≤0｝=σs/a’ij计算最小比值θ，所对应的基变量为换入 计算检验数，列出新的单纯形表 已找到最优解 结束 五、对偶单纯形法例题 下面用一个例子来说明对偶单纯形法的解题过程。 Min z=5x1+2x2+4x3 s.t.3x1+x2+2x3≥46x1+3x2+5x3≥10x1,x2,x3≥0 1.化为标准型 Max z’=-5x1-2x2-4x3+0x4+0x5 s.t.-3x1-x2-2x3+x4=-4-6x1-3x2-5x3+x5=-10x1,x2,x3,x4,x5≥0 2.列出原始单纯形表 cj→ -5 -2 -4 0 0 CB 基 b x1 x2 x3 x4 x5 0 x4 -4 0 x5 -10 -3 -1 -2 1 0 -6 [-3] -5 0 1 cj-zj -5 -2 -4 0 0 3.找出最小的bi，即b5=-10.选择x5作为换出变量。 θ=minjcj-zjaijari<0=23=c2-z2a22 故选择a22为主元素，x2为换入变量，得到新的单纯形表： cj→ -5 -2 -4 0 0 CB 基 b x1 x2 x3 x4 x5 0 x4 -2/3 -2 x2 10/3 [-1] 0 -1/3 1 -1/3 2 1 5/3 0 -1/3 cj-zj -1 0 -2/3 0 -2/3 再次换入换出： cj→ -5 -2 -4 0 0 CB 基 b x1 x2 x3 x4 x5 -5 x1 2/3 -2 x2 2 1 0 1/3 -1 1/3 0 1 1 2 -1 cj-zj 0 0 -1/3 -1 -1/3 4.所有的bi都大于零，说明找到了最优解。 X=（2/3,2,0）T Max z’=-10/3-4=-22/3 Min z= 22/3. 但是，对偶单纯形法并不是一种普遍算法，它有一定的局限性，不是任何线性规划问题都能用对偶单纯形法计算的。当线性规划问题具备下面条件时，可以用对偶单纯形法求解： ①问题标准化后，价值系数全非正； ②所有约束全是不等式。 六、对偶单纯形法的应用 1.从上面的例题可以看出，原问题是求最小值，并且目标函数各项系数都不小于零。所以在转化成标准型后各项系数不大于零，从而以松弛变量为基列出的单纯形表满足检验数都不大于零，是其对偶问题的一个可行解。如果原问题的标准形式中各项系数不都小于零，则不容易找到对偶问题的一个初始可行解，就不适合使用对偶单纯形法求解。 所以对偶单纯形法适用于不易找到原方程的可行解而容易找到其对偶问题的可行解的线性规划问题。 2.我们知道，约束方程的数量对单纯形法的计算过程要远远大于变量个数的影响。如果m>n，那么对偶问题有n个约束方程，而原问题有m个约束方程，所以对偶问题有更少的约束方程数量，那么通过对偶单纯形法的运用比起直接只用单纯形法将会显著的减少计算量。 3.弱对偶性和强对偶性是对偶理论的关键原理。对偶问题可以用来对原问题的计划方案进行评价。我们可以用一个对偶问题的可行解和目前原问题的计划方案进行比较，如果两个目标函数值相等或比较接近，则可以说明原问题的计划方案已经是可以看做最优了。 4.对偶理论在灵敏度分析和影子价格计算中有着重要的作用。 七、单纯形法和对偶单纯形法的基本思想比较 通过以上的分析可知，对偶单纯形法其实相当于单纯形法的一种变形，只不过在运用对偶单纯形法解线性规划时需要将单纯形表旋转一下。单纯形表中的b列实际上是对偶问题的非基变量的检验数, 而原单纯形表的检验数为对偶问题的基解, 这样可以理解为通过旋转90运用单纯形法求解线性规划。 从求解思路上来说，单纯形法是首先保证基解是原问题的基可行解（bi不小于零），然后通过变量的换入换出增大目标函数值，直到其同时成为对偶问题的可行解，根据强对偶性原理，可知这个解就是最优解。而对偶单纯形法则是首先保证基解是对偶问题的可行解（检验数都不大于零），然后逐步减小对偶标准化的目标函数值，使其成为原问题的可行解。两种方法殊途同归，其本质是一样的。 8