运筹学大作业单纯性法与对偶单纯性法比较.doc

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

1、.wd对偶单纯形法与单纯形法比照分析1教学目标：通过对偶单纯形法的学习，加深对对偶问题的理解2 教学内容：1） 对偶单纯形法的思想来源2） 对偶单纯形法原理3 教学进程：1） 讲述对偶单纯形法解法的来源： 所谓对偶单纯形法，就是将单纯形法应用于对偶问题的计算，该方法是由美国数学家C.莱姆基于1954年提出的，它并不是求解对偶问题解的方法，而是利用对偶理论求解原问题的解的方法。2） 为什么要引入对偶单纯形法： 单纯形法是解线性规划的主要方法，对偶单纯形法那么提高了求解线性规划问题的效率，因为它具有以下优点：1初始基解可以是非可行解, 当检验数都为负值时, 就可以进展基的变换, 不需参加人工变量,

2、 从而简化计算；2对于变量多于约束条件的线性规划问题,用对偶单纯形法可以减少计算量,在灵敏度分析及求解整数规划的割平面法中,有时适宜用对偶规划单纯形法。 由对偶问题的根本性质可以知道，线性规划的原问题及其对偶问题之间存在一组互补的基解，其中原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基变量，那么在另一问题的解中是非基变量；将这对互补的基解分别代入原问题和对偶问题的目标函数有z=w。据此可知，用单纯形法求解线性规划问题时，在得到原问题的一个基可行解的同时，在检验数行得到对偶问题的一个基解，并且将两个解分别代入各自的目标函数时其值

3、相等。 我们知道，单纯形法计算的根本思路是保持原问题为可行解这时一般其对偶问题为非可行解的根底上，通过迭代，增大目标函数，当其对偶问题的解也为可行解时，就到达了目标函数的最优值。那么对偶单纯形法的根本思想可以理解为保持对偶问题为可行解这时一般原问题为非可行解的根底上，通过迭代，减小目标函数，当原问题也到达可行解时，即到达了目标函数的最优值。其实对偶单纯形法本质上就是单纯形法, 只不过在运用时需要将单纯形表旋转一下而已。一.单纯形法和对偶单纯性法单纯形法是求解线性规划的主要方法, 单纯形表那么是单纯形法和对偶单纯形法的运算工具。设线性规划问题为Max将其化为标准形式，得 Max Z= s.t.

4、其中，那么其对应的线性约束转换为，代入目标函数得，相应的一个基解为，。显然，假设，且，那么基解为该线性规划的最优解, 此时检验数均大于零, 见表1。通过上面的分析, 我们知道单纯形表的检验数实际上是目标函数中基变量、非基变量的价值系数,又由对偶理论知道它们是相应对偶问题的一个( 加一个负号) 基解。那么表中b列的数字仅仅表示的是的取值吗? 我们可以猜测 很可能是对偶问题的检验数。这里首先给出问题(1) 的对偶问题的一般形式 Min s.t.将问题3化为标准形式，得 Min s.t.由，为松弛变量，相应分解为、，其中，。得：由式得到通过令，由式(5)得对偶问题的基解,代入式(6)得,将式(7)对

5、偶问题的目标函数得。显然假设目标函数到达最小,非基变量的价值系数要求大于等于零,单纯形表b列, 即实际上是对偶问题的非基变量检验数。二对偶单纯形法的算法步骤 (1)确定换出基的变量设原问题为1，对偶问题为3。由，不等式那么可分解为 (8)进一步添加松弛变量有等式5、6，对等式5两端同时左乘有(9)将移至等式右端得(10)由不等式8得(11)(12)将式10代入不等式11、12得(13)(14)将13、14合并得(15)整理得(16)其中是单纯形表中X变量的检验数,记，(j=1,2,.,n),矩阵，显然，假设Y为基可行解，而假设，那么对偶问题的目标函数未取得最小值，取，确定单纯形表的换出基变量，

6、即在单纯形表中的对偶问题相应的换入基变量，令其余分量为零，即，可能取大，使对偶问题的目标函数值下降，由Y为基可行解，那么要求满足式16，即对于任意的j，均有，得，从而确定单纯形表中换入基变量，同时确定对偶问题在单纯形表中换出基变量。这与单纯形法确定换出基变量的规那么是完全一样的。3例题讲解下面举例说明对偶单纯形法的算法步骤：【例题】用对偶单纯形法求解线性规划问题：min解：1将问题改写为：2） 算法步骤 第一步：建立一个初始单纯形表，使表中检验行的值全部大于或等于零， 即对其对偶问题而言是一根本可行解。 约束条件两端乘 -1，得：根据原问题和对偶问题之间的对称关系，这时单纯形表中原基变量列数字

7、 相当于对偶问题解的非基变量的检验数。第二步：由于对偶问题的求解是使目标函数到达最小值，所以最优判别准那么是 当所有检验数大于或等于零时为最优也即这时原问题是可行解。 如果不满足这个条件，找出绝对值最大的负检验数，设为，其对应 的原问题的基变量即为对偶问题的换入变量。第三步：将行数字与表中第行对应的数字比照，令，即为主元素，为对偶问题的换出变 量。第四步：用换入变量替换对偶问题中的换出变量在单纯形表中反映为用替原问 题的基变量，得到一个新的单纯形表。 表中数字计算同用单纯形法时完全一样。新表中对偶问题仍保持根本 可行解，原问题基变量列数字列数字相当于对偶问题的检验数。据此可以完成对这个对偶问题

8、的求解。4 总结。1） 比照单纯形法&对偶单纯形法单纯性法根本思想2） 对偶单纯形法优点 这里我们需要对单纯形法和对偶单纯形法做一个详细的比照： 1，单纯形法中的b对应于对偶单纯形法中的； 2，单纯形法中的作为检验数，对偶单纯形法中的b作为检验数； 3，单纯形法中的，对偶单纯形法中的；4，单纯形法中当时得到最优解，对偶单纯形法中当时得到最优解；5，单纯形法的可行解为，对偶单纯形法的可行解为；由于松弛变量对应的检验数为，由于与对应，又由于，可得。 对于单纯形法和对偶单纯形法，我们建立了使用单纯形法解决线性规划问题 的依据： 1，表中有单位矩阵，当时用单纯形法； 2，表中有单位矩阵，当时用单纯形法

9、； 3，两者都不满足时，使用人工变量法或两阶段法。 接下来需要说明在哪些场合下使用对偶单纯形法解决线性规划问题较为便 捷，我将通过下面的例子来说明： min 令，那么问题可变为 max 取为初始基，易见所有检验数，从而建立单纯形表，计算结果如下：本例如果用单纯形法计算，确定初始基可行解时需引入两个人工变量，计算量要多于对偶单纯形法。一般情况下，如果问题能够用对偶单纯形法计算，计算量会少于单纯形法。但是，对偶单纯形法并不是一种普遍算法，它有一定的局限性，不是任何线性规划问题都能用对偶单纯形法计算的。当线性规划问题具备下面条件时，可以用对偶单纯形法求解：问题标准化后，价值系数全非正；所有约束全是不等式。 总结上面的分析过程可知，对偶单纯形法本质上就是单纯形法,只不过在运用对偶单纯形法解线性规划时需要将单纯形表旋转一下。单纯形表中的b列实际上是对偶问题的非基变量 的检验数, 而原单纯形表的检验数为对偶问题的( 负的) 基解, 这样可以理解为通过旋转90运用单纯形法求解线性规划。欢送您的光临，Word文档下载后可修改编辑.双击可删除页眉页脚.谢谢！让我们共同学习共同进步！学无止境.更上一层楼。