《哈工大运筹学大作业对偶单纯形法对比.docx》由会员分享，可在线阅读，更多相关《哈工大运筹学大作业对偶单纯形法对比.docx（9页珍藏版）》请在三一文库上搜索。
1、运筹学课程运筹学对偶单h 牛E中简i 卢Jl1B -sS_S ii:! IIlndn i ri= yz纯形法与单纯形法对比分析大作业哈尔滨工业大学工业工程系学生姓名：学号：指导教师：成绩：评语：运筹学对偶单纯形法与单纯形法对比分析摘要：这篇论文主要介绍了对偶单纯形法的实质、原理、流程和适用条件 等。将对偶单纯形法与单纯形法的基本思想进行对比分析，从而说明对偶单纯 形法的优点和适用范围。关键词：对偶单纯形法；对偶理论；单纯形法；基本思想在线性规划早期发展阶段的众多重要发现中，对偶的概念及其分支是其中 最重要的内容之一。这个发现指出，对于任何一个线性规划问题都具有对应的 称为对偶问题的线性规划问题
2、。对偶问题与原问题的关系在众多领域都非常有 用。（一）教学目标：通过对偶单纯形法的学习，加深对对偶问题的理解。掌握对偶单纯形法的 解题过程，理解对偶理论的其原理，了解对偶单纯形法的作用和应用范围（二）教学内容：1）对偶单纯形法的思想来源2）对偶单纯形法原理3）对偶理论的实质4）单纯形法和对偶单纯形法的比较（三）教学进程：一、对偶单纯形法的思想来源所谓对偶单纯形法，就是将单纯形法应用于对偶问题的计算，该方法是由 美国数学家C.莱姆基于1954年提出的，它并不是求解对偶问题解的方法，而 是利用对偶理论求解原问题的解的方法。二、对偶问题的实质下面是原问题的标准形式以及其对应的对偶问题：原问题对偶问题
3、nmMaXZ = CXjMin W= biyirj=1rj=1nnSL t. jXi bji = 1,2, ?, mSLtL jyi C j = 12,?,nj=1j=1Xj 0 j = 1,2,?,nyi 0 i = 1,2,?,m从而可以发现如下规律：1. 原问题目标函数系数是对偶问题约束方程的右端项。2. 原问题约束方程的右端项是对偶问题目标函数的系数。3. 原 问 题 一个 变 量在 所 有约 束方 程中 的 系数 是对 偶 问题 一 个 约束 方 程 中 的所有系数。三、对偶单纯形法原理对偶单纯形法是通过寻找原问题的对偶问题的可行解来求解原问题的最 优解的 方法，它 的应 用包 括影
4、 子价 格和 灵敏 度 分析 等。为了 理 解对 偶单纯 形法 为什么 能够解出 原 方程 的最 优解 ，我们 需要 对对偶 理 论的 几个基本 原理有 所了 解。1. 弱 对偶 性如果?(j = 1,?,n)是原冋题的可行解，?(i = 1,?, m)是其对偶冋题的可行解， 则恒有nm cj?xj biy?i j= 1i= 1证 明： 由于对 偶 方程中 原 冋 题的 约束 条 件是 各行 的 aijxj 之和 小于 等于 yi 的系数bi ,而对偶问题的约束条件是各行的ajy之和小于等于Xj的系数Cj,故 将n=ICjXj和m 1 byi分别和m 1 X ay比较，可得上述结论。2. 最优
5、性如果Xj(j= 1,?, n)是原问题的可行解，yi= 1,?,m)是其对偶问题的可行解，且 有nm Cj X?j = biy?ij= 1i= 1则?(j = 1,?,n)是原问题的最优解，yi(i = 1,?, m)是其对偶问题的最优解证明：由nm cj?xj biy?ij= 1i= 1可得nmncj ?xj bi?yi =cjx?jj=1i=1j=1mnmbi?yi cj x?j =bi?yii=1j=1i=1故可知?(j = 1,?,n)是原问题的最优解，y(i = 1,?,m)是其对偶问题的最优解。3. 强对偶性如 果 原 问 题 有 最 优 解 ， 那 么 其 对 偶 问 题 也
6、有 最 优 解 ， 且 有 maxz=minw.1证 明 ：设 B 为 原 问 题 式 (1) 的 最 优 基 ，那 么 当 基 为 B 时 的 检 验 数 为 C CBB A， 其 中 CB 为 由基 变 量 的 价 值 系 数 组 成 的 价 值 向 量 。既 然 B 为 原 问 题 式 (1)的 最 优 基 ， 那 么 有 C CBB 1A 0 。11令 Y CBB 1 ， 那 么 有 C YA 0 YA C ， 从 而 Y CBB 1 是 对 偶 问 题 式 (2) 的 可 行 解。11这样一来，Y CBB是对偶问题的可行解，XB B b是原问题的最优基可行 解。11由 于 CX CB
7、 X B CN XN CBB b ， 而 Yb CBB b ， 从 而 有 CX Yb 。 根 据 最 优 性 ， 命题得证。4. 线 性 规 划 的 问 题 原 问 题 及 对 偶 问 题 之 间 存 在 一 对 互 补 的 基 解 ，其 中 原 问 题 的 松 弛 变 量 对 应 对 偶 问 题 的 变 量 ， 对 偶 问 题 的 剩 余 变 量 对 应 原 问 题 的 变 量 ； 这 些 相 互 对 应 的 变 量 如 果 在 一 个 问 题 中 是 基 变 量 ，则 在 另 一 问 题 中 是 非 基 变 量 ；将这对互补的基解分别代入原问题和对偶问题的目标函数有Z=W四、对偶单纯形算
8、法流程在上述的理论基础上，可知用单纯形法求解线性规划问题时，在得到原问 题的一个基可行解问题同时，在检验数行得到对偶问题的一个基解。单纯形法 的基本思想是保持原问题为可行解的基础上，通过迭代增大目标函数，当其对 偶问题也为可行解时，就达到了目标函数的最优值。而对偶单纯形法的基本思想则是保持对偶问题为可行解的前提下（即单纯 性表最后一行检验数都小于零），通过迭代减小目标函数，当原问题也是可行 解时，就得到了目标函数的最优解。故我们可以得到对偶单纯形法求解过程如下：1. 将原问题化为标准型，找到一个检验数都小于等于零的对偶问题的初始 可行基。2. 确定换出基的变量对于小于零的bi，找到最小的一个b
9、r，其对应的Xr为换出基的变量3. 确定换入基的变量（1）为了使迭代后表中的第r行基变量为正值，因而只有对应aj小于零 的非基变量才可以作为换入基的变量；（2）为了使迭代后表中对偶问题仍为可行解，令A minq - ZCS- ZS= j -r=W称ars为主元素，XS为换入基的变量。4. 用换入变量替换换出变量，得到一个新的基。再次检查是否所有的bi大于等于零。如果是，则找到了最优解，如果否，则再次进行变换对偶单纯形法的算法流程图找出一个对偶问题的初始可行基 Bo,确定换出和换入的基变量：换出最小的“算右端验数，列所对应的基变量;已找到最优解二T五、对偶单纯形法例题下面用一个例子来说明对偶单纯
10、形法的解题过程Min z=5x +2x 2+4x33x1 + x2+ 2x3 4s.t. 6x1 + 3x2+ 5x3 10x1,x2,x3 01. 化为标准型MaX Z ' =-5x 1-2x2-4x3+0x 4+Ox 5-3x1- x2- 2x3+ x4 = - 4s.t. - 6x1- 3x2- 5x3+ x5 = - 10 x1,x2,x3, x4,x5 02.列出原始单纯形表Cj -5-2-400CB基bXiX2X3X4X50X4-4-3-1-2100X5-10-6卜3-501Cj-Zj-5-2-4003.找出最小的bi,即b5=-10.选择x5作为换出变量a22min C
11、- Zj2j 盲由0 = 3故选择a22为主元素，x2为换入变量，得到新的单纯形表：Cj -5-2-400CB基bX1X2X3X4X50X4-2/3-10-1/31-1/3-2 X210/3215/30-1/3Cj-Zj-10-2/30-2/3再次换入换出：Cj -5-2-400CB基bX1X2X3X4X5-5 X12/3101/3-11/3-2X220112-1Cj-Zj00-1/3-1-1/34. 所有的bi都大于零，说明找到了最优解X= （ 2/3,2,0）TMaX Z ' =-10/3-4=-22/3Min Z= 22/3.但是，对偶单纯形法并不是一种普遍算法，它有一定的局限性
12、，不是任何 线性规划问题都能用对偶单纯形法计算的。当线性规划问题具备下面条件时， 可以用对偶单纯形法求解： 问题标准化后，价值系数全非正； 所有约束全是不等式。六、对偶单纯形法的应用1.从上面的例题可以看出，原问题是求最小值，并且目标函数各项系数都 不小于 零。所以 在转 化成 标准 型后 各项 系数 不 大于 零，从 而以 松弛 变 量为基列 出的单 纯形表满 足 检验 数都 不大 于零 ，是其 对 偶问题 的 一个可行 解。如果 原问 题的标 准形式中 各 项系 数不 都小 于零 ，则不 容易找 到 对偶 问题的一 个初始 可行 解，就不适合使用对偶单纯形法求解。所以对偶单纯形法适用于不易
13、找到原方程的可行解而容易找到其对偶问 题的可行解的线性规划问题。2. 我们知道，约 束方程的数量对单纯形法的 计算过程 要远远大于变量个数 的影响 。如果 m>n ，那 么对偶问 题有 n 个约 束方 程， 而原 问题 有 m 个约束方 程，所 以对 偶问 题有 更少 的约 束方 程数 量，那 么 通过 对偶单 纯 形法 的运用 比起 直接只用单纯形法将会显着的减少计算量。3. 弱对偶性和强对偶性是对偶理论的关键原理。对 偶 问题可以 用来对原问 题的计 划方案进 行 评价 。我们 可以 用一 个对 偶问题 的 可行 解和目前 原问题 的计 划方案 进行比较 ，如 果两 个目 标函 数值
14、 相等 或 比较 接近 ，则可以说 明原问 题的 计划方案已经是可以看做最优了。4. 对偶理论在灵敏度分析和影子价格计算中有着重要的作用。七、单纯形法和对偶单纯形法的基本思想比较通 过 以 上 的 分 析 可 知 ，对 偶 单 纯 形 法 其 实 相 当 于 单 纯 形 法 的 一 种 变 形 ，只 不过在 运用对偶 单 纯形 法解 线性 规划 时需 要将 单纯 形表 旋转 一下 。单纯形 表中 的b列实际上是对偶问题的非基变量的检验数，而原单纯形表的检验数为对偶 问 题的 基解, 这样可以理解为通过旋转 90°运 用单纯形法求解线性规划。从求解思路上来说，单纯形法是首先保证基解是原问题的基可行解（bi 不小于零）， 然后通过变量的换入换出增大目标函数值， 直到其同时成为对偶 问 题的 可行解，根据强对偶性原理，可 知这个解就是最优解。而对偶单纯形法 则是首先保证基 解是对偶问 题的 可行解（ 检验数都不大于零）， 然后逐步减小 对偶标准化的目标函数值，使其成为原问 题的 可行解。两种方法殊途同归，其本质是一样的