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

1、哈工大运筹学大作业-对偶单纯 形法对比运筹学课程运筹学对偶单纯形法与单纯形法对比分析大作业哈尔滨工业大学工业工程系学生姓名：学号：11208401指导教师：成绩：语:运筹学对偶单纯形法与单纯形法对比分析摘要：这篇论文主要介绍了对偶单纯形 法的实质、原理、流程和适用条件等。将对 偶单纯形法与单纯形法的基本思想进行对 比分析，从而说明对偶单纯形法的优点和适 用范围。关键词：对偶单纯形法；对偶理论；单 纯形法；基本思想在线性规划早期发展阶段的众多重要 发现中，对偶的概念及其分支是其中最重要 的内容之一。这个发现指出）对于任何一个 线性规划问题都具有对应的称为对偶问题 的线性规划问题。对偶问题与原问题

2、的关系 在众多领域都非常有用。（一）教学目标：通过对偶单纯形法的学习，加深对对偶 问题的理解。掌握对偶单纯形法的解题过 程，理解对偶理论的其原理，了解对偶单纯 形法的作用和应用范围（二）教学内容：1）对偶单纯形法的思想来源2）对偶单纯形法原理3）对偶理论的实质4）单纯形法和对偶单纯形法的比较（三）教学进程：一、对偶单纯形法的思想来源所谓对偶单纯形法，就是将单纯形法应 用于对偶问题的计算，该方法是由美国数学 家C.莱姆基于1954年提出的，它并不是求 解对偶问题解的方法，而是利用对偶理论求 解原问题的解的方法。二、对偶问题的实质下面是原问题的标准形式以及其对应 的对偶问题：对倜衅_1MaxZ -

3、 > CjXjs. t ajjXj < bj j=iXj > 0 j =Min W = y 可达 = ££包诙访> Cj 航之。i= 1,2,，m从而可以发现如下规律：1 .原问题目标函数系数是对偶问题约 束方程的右端项。2 .原问题约束方程的右端项是对偶问 题目标函数的系数。3 .原问题一个变量在所有约束方程中的系数是对偶问题一个约束方程中的所有 系数。三、对偶单纯形法原理对偶单纯形法是通过寻找原问题的对 偶问题的可行解来求解原问题的最优解的 方法，它的应用包括影子价格和灵敏度分析 等。为了理解对偶单纯形法为什么能够解出 原方程的最优解，我们需要对

4、对偶理论的几 个基本原理有所了解。1 .弱对偶性如果Xj( = L/n)是原问题的可行解，1,/m)是其对偶问题的可行解，则恒证明： 件是各行的2 b承 1=1由于对偶方程中原问题的约束条aj Xj之和小于等于V'的系数b)而对偶问题的约束条件是各行的 小于等于Xj的系数Cj ,aj V'之和故将ZJLi 9%x；和bi%分别和£目1£11居分比较)可得上述结论。2.最优性如果=hJf，口)是原问题的可行解,%。工 草芳.啰某翻禺问题的可行解，且有j二i1=1则&是原问题的最优解，i(i =是其对偶问题的最优解。因”c b=-iyiiyiAb b c

5、m m电一 <->-可 与iyi一 b证IE .1可EKII故可知= LIH）是原问题的最优 解，yi（i = L,m）是其对偶问题的最优解。3 .强对偶性如果原问题有最优解，那么其对偶问题 也有最优解）且有maxz=minw.证明：设 B为原问题式（1）的最优基， 那么当基为 B时的检验数为C cbb1a,其中CB为 由基变量的价值系数组成的价值向量。既然B为原问题式（1）的最优基，那么有 C CBB1A 0 o令Y CbB那么有C YA 0 YA C ,从而Y OB是 对偶问题式（2）的可行解。这样一来，Y CBB1是对偶问题的可行解， Xb ”是原问题的最优基可行解。由于 C

6、X CbXb CnXn CbB 1b 而 Yb CbB 1b 从而有 CX Yb。根据最优性，命题得鬲4 .线性规划的问题原问题及对偶问题 之间存在一对互补的基解，其中原问题的松 弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些相互对应的 变量如果在一个问题中是基变量，则在另一 问题中是非基变量；将这对互补的基解分别 代入原问题和对偶问题的目标函数有Z=Wo四、对偶单纯形算法流程在上述的理论基础上，可知用单纯形法 求解线性规划问题时，在得到原问题的一个 基可行解问题同时，在检验数行得到对偶问 题的一个基解。单纯形法的基本思想是保持 原问题为可行解的基础上，通过迭代增大目 标函

7、数，当其对偶问题也为可行解时，就达 到了目标函数的最优值。而对偶单纯形法的基本思想则是保持 对偶问题为可行解的前提下(即单纯性表最 后一行检验数都小于零)，通过迭代减小目 标函数，当原问题也是可行解时，就得到了 目标函数的最优解。故我们可以得到对偶单纯形法求解过 程如下：1 .将原问题化为标准型，找到一个检验 数都小于等于零的对偶问题的初始可行基。2 .确定换出基的变量对于小于零的 bi)找到最小的一个 br) 其对应的Xr为换出基的变量3 .确定换入基的变量(1)为了使迭代后表中的第 r行基变 量为正值，因而只有对应 aj小于零的非基 变量才可以作为换入基的变量；(2)为了使迭代后表中对偶问

8、题仍为6可行的空叫口 |1。|二星二公J （沏J as称ars为主元素）Xs为换入基的变量。4 .用换入变量替换换出变量，得到一个新的基。再次检查是否所有的bi大于等于零。如果是，则找到了最优解，如果否，则再次进行变换。对偶单纯形法的算法流程图:开始化原问题找出一个对偶问题的 初始可行等B）,计算 一. 上bi者B确定换出和换入的基变量：7换出最小的“右端项” b计算检验已找到"结束>五、对偶单纯形法例题下面用一个例子来说明对偶单纯形法 的解题过程。Min z=5x i+2x 2+4x3（3x1 + x2 + 2x3 > 45 .t.伯门一代二一, '.） xlf

9、x2,x3 > 01.化为标准型Max z ' =-5x i-2x 2-4x 3+0x4+0x5'-3x1 逐一2x3 + x4 = -4s.t. -6x1 - 3x2 5x3 +x5 = -1Oxl,x2Tx3Tx4*TxS > 02 .列出原始单纯形表Cjf-5-2-400Cb基bXiX2X3X4X50x4-4-3-1-2100x5-10-6-3-501Cj-z j-5-2-4003 .找出最小的 bi ,即b5=-10.选择x5作为再出变量J q I% 。1=4 =Q一也J aiiJ 3a22故选择a22为主元素)x2为换入变量) 得到新的单纯形表：Cjf-5

10、-2-400Cb基bXiX2X3X4X50X4 -2/3-2X210/3-10-1/31-1/3215/30-1/3Cj-z j-10-2/30-2/3再次换人换出：Cj 一-5-2-400Cb基bXiX2X3X4X5-5Xi2/3-2X22101/3-11/30112-1Cj-z j00-1/3-1-1/34.所有的bi都大于零，说明找到了最 优解。X= (2/3,2,0) TMax z' =-10/3-4=-22/3Min z= 22/3.但是，对偶单纯形法并不是一种普遍算 法，它有一定的局限性，不是任何线性规划 问题都能用对偶单纯形法计算的。当线性规 划问题具备卜面条件时，可以用

11、对偶单纯形 法求解：问题标准化后，价值系数全非正;所有约束全是不等式。六、对偶单纯形法的应用1 .从上面的例题可以看出，原问题是求 最小值，并且目标函数各项系数都不小于 零。所以在转化成标准型后各项系数不大于 零，从而以松弛变量为基列出的单纯形表满 足检验数都不大于零，是其对偶问题的一个 可行解。如果原问题的标准形式中各项系数 不都小于零，则不容易找到对偶问题的一个 初始可行解，就不适合使用对偶单纯形法求 解。所以对偶单纯形法适用于不易找到原 方程的可行解而容易找到其对偶问题的可 行解的线性规划问题。2 .我们知道，约束方程的数量对单纯形 法的计算过程要远远大于变量个数的影响。 如果m>

12、n,那么对偶问题有 n个约束方程， 而原问题有 m个约束方程，所以对偶问题有 更少的约束方程数量，那么通过对偶单纯形 法的运用比起直接只用单纯形法将会显著 的减少计算量。3 .弱对偶性和强对偶性是对偶理论的 关键原理。对偶问题可以用来对原问题的计 划方案进行评价。我们可以用一个对偶问题 的可行解和目前原问题的计划方案进行比 较，如果两个目标函数值相等或比较接近， 则可以说明原问题的计划方案已经是可以 看做最优了。4 .对偶理论在灵敏度分析和影子价格 10计算中有着重要的作用。七、单纯形法和对偶单纯形法的基本思 想比较通过以上的分析可知，对偶单纯形法其 实相当于单纯形法的一种变形，只不过在运 用对偶单纯形法解线性规划时需要将单纯 形表旋转一下。单纯形表中的b列实际上是对偶问题的非基变量的检验数，而原单纯 形表的检验数为对偶问题的基解，这样可 以理解为通过旋转900运用单纯形