2023年运筹学大作业单纯性法与对偶单纯性法的比较.docx
对偶单纯形法与单纯形法对比分析1 .教学目的：通过对偶单纯形法的学习，加深对对偶问题的理解.教学内容：1）对偶单纯形法的思想来源2）对偶单纯形法原理2 .教学进程：1）讲述对偶单纯形法解法的来源：所谓对偶单纯形法，就是将单纯形法应用于对偶问题的计算，该方法是由美 国数学家C.莱姆基于1954年提出的，它并不是求解对偶问题解的方法，而是运用 对偶理论求解原问题的解的方法。2）为什么要引入对偶单纯形法：单纯形法是解线性规划的重要方法，对偶单纯形法则提高了求解线性规划 问题的效率，由于它具有以下优点：（1）初始基解可以是非可行解，当检查数都为负值时，就可以进行基的变换, 不需加入人工变量，从而简化计算；（2）对于变量多于约束条件的线性规划问题,用对偶单纯形法可以减少计算量, 在灵敏度分析及求解整数规划的割平面法中，有时适宜用对偶规划单纯形法。由对偶问题的基本性质可以知道，线性规划的原问题及其对偶问题之间存在 一组互补的基解,其中原问题的松弛变量相应对偶问题的变量,对偶问题的剩余 变量相应原问题的变量；这些互相相应的变量假如在一个问题的解中是基变量， 则在另一问题的解中是非基变量；将这对互补的基解分别代入原问题和对偶问题 的目的函数有z二w。据此可知，用单纯形法求解线性规划问题时，在得到原问题的 一个基可行解的同时，在检查数行得到对偶问题的一个基解，并且将两个解分别算量要多于对偶单纯形法。一般情况下，假如问题可以用对偶单纯形法计算,计算量会少于单纯形法。但是，对偶单纯形法并不是一种普遍算法,它有一 定的局限性，不是任何线性规划问题都能用对偶单纯形法计算的。当线性规划问题具有下面条件时,可以用对偶单纯形法求解：问题标准化后，价值系数全非正；所有约束全是不等式。总结上面的分析过程可知，对偶单纯形法本质上就是单纯形法，只但是在 运用对偶单纯形法解线性规划时需要将单纯形表旋转一下。单纯形表中的b列事实上是对偶问题的非基变量丫出的检查数，而原单纯形表的检查数为对偶问题的（负的）基解， 这样可以理解为通过旋转900运用单纯形法求解 线性规划。代入各自的目的函数时其值相等。我们知道,单纯形法计算的基本思绪是保持原问题为可行解（这时一般其对 偶问题为非可行解）的基础上，通过迭代，增大目的函数，当其对偶问题的解也 为可行解时，就达成了目的函数的最优值。那么对偶单纯形法的基本思想可以理 解为保持对偶问题为可行解（这时一般原问题为非可行解）的基础上，通过迭代, 减小目的函数，当原问题也达成可行解时，即达成了目的函数的最优值。其实对 偶单纯形法木质上就是单纯形法，只但是在运用时需要将单纯形表旋转一下而 己。一.单纯形法和对偶单纯性法单纯形法是求解线性规划的重要方法，单纯形表则是单纯形法和对偶单纯形法的运算工具。设线性规划问题为Max Z = £c.x.j=is.t.<将其化为标准形式，得Max Z= CXs.t.s.t.Ax + Xi x，XF。Xb ,则其相应的线Xn其中 C=（Cb，CJ , Cv=0=（°，°，°），a =（b,n）,性约束转换为Xs+3Xn+RXl。，XB = B'b-B“XN+B'X，代入目的函数得 z = Cs B%+（C.，v- Cb B> Xn-Cb B' Xs，' j-XB = B'b，XL。，Xs=°。显然，若B%N。，且（Cn-CEn）no,-C,B"Xs2°，则基解4为该线性规划的最优解，此时检查数均大 于零，见表1。表1线性规划单纯形法QCxCsXbbXbX、XsXrB-'bIir 1n/r'验数CB- Cfi-'BCs- Cffl-'N-点L通过上面的分析，我们知道单纯形表的检查数事实上是目的函数中基变 量、非基变量的价值系数,又由对偶理论知道它们是相应对偶问题的一个（加一 个负号）基解。那么表中b列的数字仅仅表达的是Xs的取值吗？我们可以猜想B” 很也许是对偶问题的检查数。这里一方面给出问题（1）的对偶问题的一 般形式1=1y > 0(/=1,./«)Min卬= ?=i s. t-Ys = c Mi（3）-Ys = c Mis. t将问题（3）化为标准形式,得 Min w=YB由C =（C/pCn），A = （8,N）, Ys为松弛变量，心相应分解为丫山、y、N，其中乙，得:YN»n = Cn(6)由式得到通过令y、8=o,由式(5)得对偶问题的基解y = c,BT，代入式(6)得 YxCbBn-Cv，将式 对偶问题的目的函数得卬=CbB 'b+Y.bB b 0 显然若目的函数达成最小，非基变量y、4的价值系数规定大于等于零,单纯形表 b列B"bNO,即8%之0事实上是对偶问题的非基变量检查数。二.对偶单纯形法的算法环节(1)拟定换出基的变量设原问题为(1),对偶问题为(3)。由A = (3,N)C =(Cs，Cv),不等式E42C则 可分解为YBNCbJNNCn进一步添加松弛变量有等式(5)、(6),对等式(5)两端同时左乘有y-Y'bB' = CbBT(9)将移至等式右端得¥ = YsbB' + CbB'(10) 由不等式(8)得(11) Cn-ynwo(12) 将式(10)代入不等式(11)、( 12)得Cyb=CCB'b-Y、bB"wo(13)Cn-yn=CCbB 'n-y'bB Mo （14）将（13 ）、（14 ）合并得（Cb，Cn）-Y（B，N） =（Cb，Cn）TCbB' + YsbB7）（B,N）£0 （15） 整理得（1 6）其中c-C/"a是单纯形表中x变量的检查数，记。-0“牙 =（6）,（j = 1,2,.，n） ,成U矩阵,显然，若Y为基可行解，而若8-%（），则对偶问题的目的函数w=cb%+y、jB%未取得最小值，取 ming %）： I（B %），°=（夕”，拟定单纯形表的换出基变量为，即（在单纯形 表中的）对偶问题相应的换入基变量y,w，令丫阴其余分量为零，即 YsB =（%/%，»,”）=（°，。，乂“0） 也许取大，使对偶问题的目的 函数值下降，由丫为基可行解，则规定满足式（16）,即对于任意的j,均有6一儿.74之°，得以+min 91G士。，“产。=乌"，从而拟定单纯形表中换入基变量工用，同时拟定对偶问题（在单纯形表中）换出基变量y这与单纯形法拟定换出基变量的规则是完全同样的。3）例题讲解下面举例说明对偶单纯形法的算法环节：【例题】用对偶单纯形法求解线性规划问题：mi n卬=15y+ 24y, + 5y.6%+y?2sj.< 5 y + 2 y2 + )2 1解：1)将问题改写为：min w = 15y + 24j + 5y56 is +) > 2-* J5M + 2y2 +.% > 1J-omin w = 15必 + 24y2 + 5y3 + 0y4 + 0y56y2+8一乂=2, 5必+28+%- = 1Z> 0(/= 1,2,3,4,5)2)算法环节第一步:建立一个初始单纯形表，使表中检查行的色值所有大于或等于零,即对其对偶问题而言是一基本可行解。约束条件两端乘-L得：min w = 15M + 24 乃 + 5 K + 0y4 + 0y5-6匕一乃+以=-2< -5y, -2% 一% + = - 1,1* Z 33乂 2 0。= 1,234,5)min vr = 15M + 24j + 5y. + 0v4 +0y5_6%一乃+居=-2-5 必-2 为-%+为=-1Z> 0(7 = 1,2,3,4,5)15 24 5 0yi y2 y3 y4 ys*3Y4 20 -6 -1 1 oys T-5 -2 -1 0 hO15 24 5 0 0根据原问题和对偶问题之间的对称关系，这时单纯形表中原基变量列数字相称于对偶问题解的非基变量的检查数。第二步：由于对偶问题的求解是使目的函数达成最小值，所以最优判别准则是当所有检查数大于或等于零时为最优（也即这时原问题是可行解）。假如不满足这个条件,找出绝对值最大的负检查数，设为,其相应 的原问题的基变量无即为对偶问题的换入变量。第三步：将b,行数字与表中第/行相应的数字对比，令。二mim | G | “. < 0，= G, q伏即为主元素，项为对偶问题的换出 dijCllk变量。第四步:用换入变量替换对偶问题中的换出变量（在单纯形表中反映为用替原问题的基变量），得到一个新的单纯形表。表中数字计算同用单纯形法时完全同样。新表中对偶问题仍保持基可行解，原问题基变量列数字列数字相称于对偶问题的检查数。15 2450yiY2Y3Y4ys*3丫420-6-11ys-5-2-10q0+152450yz 1/3O11/6-1/6Oys T/3-5O -2/3-1/3 1qCj -815O 14O,Y2 1/4-5/41 O-1/4 1/4.Y3 1/215/2 O 11/2 -3/2Cj -17/2015/2 O O7/2 3/22据此可以完毕对这个对偶问题的求解。4 .总结o1）对比单纯形法&对偶单纯形法单纯性法基本思想2）对偶单纯形法优点这里我们需要对单纯形法和对偶单纯形法做一个具体的对比：1,单纯形法中的b相应于对偶单纯形法中的2,单纯形法中的。作为检查数,时偶单纯形法中的b作为检查数；3,单纯形法中的之（），对偶单纯形法中的4,单纯形法中当<7<0时得到最优解,对偶单纯形法中当b>0时得到最优 解；5,单纯形法的可行解为x=B%，对偶单纯形法的可行解为y； （由于松弛变量X、相应的检查数为-c/"，由于X,与丫相应，又由于 可得 y=c/°）。对于单纯形法和对偶单纯形法，我们建立了使用单纯形法解决线性规划问题的依据：1 ,表中有单位矩阵/ ,当b 2 0时用单纯形法；2,表中有单位矩阵/,当。40时用单纯形法；3,两者都不满足时，使用人工变量法或两阶段法。接下来需要说明在哪些场合下使用对偶单纯形法解决线性规划问题较为便 捷，我将通过下面的例子来说明：min Z = 12X1 + 8X2 + 16X3 + 12X2X + %2 + 4%3-2s2 冗+ 2% + 4%/3Z = -z,则问题可变为max Z = n xrs X2-6 xr2 X4-2xrx2-4X3+X5 = -2s i2无_2%_4乂 + 乂 = _3Xj N 0( z = 1 6)取B = (R,p)为初始基，易见所有检查数0产0,从而建立单纯形表,计算结果如下：C-12816 -120 0J4,b% % / % % %0 04 %2<24-4010. ”r -L-2. K-4220-401O-128 -16 -12 000-12网23 4-2-1 -40101/21/20104/4K-2O-4 -2 -1600 38-12% %2 -1/421 W 0 -10 l-2, K-l"0-211Z2 .1/4 最O2°£0 -2-3 X=l/2.8-12“X,I 1/201.441琮l】。41/2勺4=0.O0°0 T 7 -2 mi 应=14本例假如用单纯形法计算，拟定初始基可行解时需引入两个人工变量，计
