2对偶理论运筹学西南交通大学经济管理学院

1、运筹学Operations Research对偶理论西南交通大学管理学院西南交通大学管理学院§1单纯形法的矩阵描述max z = CX + 0 × X Smax z = CX AX £ bX ³ 0引入松弛变量AX + IX S= b³ 0)TX ³ 0 , Xn + mSmax z = CB X B + CN X N + 0 × X SBX+ NX+ IX S = bBN³ 0SX B= B -1b - B -1NX- B -1 X SNZ = CB B -1b + (C N- C B B -1N ) X N-

2、CB B -1 X S西南交通大学管理学院B#I与初等变换一致B-1I#西南交通大学管理学院基变量非基变量右侧常数XBXNXSCBXBIB-1 NB-1B-1 bg0CN - CBB-1N-CBB-1-CBB-1b初始非基变量初始基变量右侧常数XBXNXS0XSBNIbgCBCN00BiB1=B1-1=IB2AjbIB2-1AjB2-1B2-1bBi-1Bi-1bBiAj-1I西南交通大学管理学院§2线性的对偶理论一、对偶问题的提出周长一定，面积最大的四边形面积一定，周长最小的四边形 正方形 车辆数一定，如何安排使货运量最多货运量一定，如何安排使所用车辆最少一对对应问题表示了一个问题

3、的两个侧面，是对一个研究对象从两个角度提出极值问题，两类极值问题具有相同的目标函数值。对偶问题西南交通大学管理学院例1某工厂在计划期内要安排生产,两种，已知所需的设备台时及A，B两种原材料的消获利能力如下表所示。问如何安排生产使该生产耗，及工厂获利最多？西南交通大学管理学院III限量设备128 台时原材料A4016 Kg原材料B0412 Kg单件利润2 元3 元解根据上一章的知识，设x1，x2分别表示在计划期内，的产量，得线性模型max z=2x1+3x2 x1+2x284x1164x212x1, x20例2对例1，假设该工厂的决策者决定不生产，而将其所有出租或外售。这时工厂的决策者如何给出每

4、种的定价？解同理，设y1 ,y2 ,y3分别表示出租设备台时的原材料A，B的附加额。和出让思路：出售生产一件I的的收入应不低于生产I的利润，有一件y1+ 4y2 2西南交通大学管理学院 原问题max z=2x1+3x2 x1+2x28依次类推，得线性模型min w=8y1+16y2+12y3y1+4y2 24x1614x 122y1+4y3162y1, y2, y30x , x201(1)(2)(3)(4)系数互为转置约束条件的常数项变为目标函数系数一个为max问题，一个为min问题约束条件一个为，一个为西南交通大学管理学院这样并存的两个线性问题互为对偶，一个为原问题，另一个为对偶问题定义 1

5、.设有线性问题（）max z=CX AXb X0式中X=(x1, , xn)T，C=(c1, , cn)，b=(b1, , bm)T，a11 a21am1a12 a22am2a1n a2namnA=设另一个线性问题（）为min w=YbYACY0式中Y=(y1, , ym)，则称问题（）是问题（）的对偶问题，式（）称为原问题。两者合在一起称为一对对称的对偶线性问题。西南交通大学管理学院原问题与对偶问题的关系z =+ c 2+ "+ "x 2 + " + c n x nmaxc 1 x 1x 1 +x 1 +x n£ b 1x n£ b 2a 1

6、1a 21a 12a 22xa 1 na 2 n2x 2" " " "x 1 +x 2 + " +x n£ bma m 1a ma mn2x³ 0=+jy 1 b11 , 2 , " , njw =+ "+miny 2 b 2ym bm³ c1³ c 2y 1+y 1+ "+ "+a 11a 12a 21a 22y 2y 2a m 1a m 2y my m" " " "y 1+y i³+ "+³

7、c na 1 na 2 n0y 2a mny mi = 1, 2 , " , m西南交通大学管理学院原问题与对偶问题的关系西南交通大学管理学院0x1x2xny1 y2yma11a12a1na21a22a2nam1am2amnb1 b2bmc1c2cnmin max现考虑标准形式的线性（ ）max z=CX AX b- AX - bX0对偶变量UVmax z=CX AX = bX0等价写成对偶问题为min w = Ub -Vbmin w = Yb YA ³ CY为自由变量令Y = U - VUA -VA ³ CU ³ 0,V ³ 0西南交通大学管

8、理学院构造对偶的规则1、若目标函数为min，把原问题中的约束条件统一为“”或“=”；若目标函数为max，把原问题中的约束条件统一为“” 或“=”。2、原问题的一个约束对应于一个对偶变量 yi ，如果第i个约yi ³ 0；如果第i个约束是等式，则 yi束是不等式，则限制。3、原问题每个变量 x j 对应于一个对偶问题的约束，如果 x j ³ 0 ，则对偶约束为不等式；如果 x约束为等式。4、如果原问题目标函数为min ，则对偶问题为max；如果原问题目标函数为max ，则对偶问题为min。，则对偶j西南交通大学管理学院例3 写出下述线性min z=问题的对偶问题5 +x+x

9、5 ³4£6=23 ³04无x符号限制0³)令mz i=n解- 24+ x-+³-x³542446=3 ³0无x 约束4西南交通大学管理学院设对应于约束条件(1)、(2)、(3)的对偶变量分别 为 y1 、y2 、y3=-+ 6 y 3max-y-y yw5 y 14 y 2£- 5约束西南交通大学管理学院二、对偶定理max z=CXmin w=YbYA CY0(LP)AXbX0(LD)定理1(弱对偶定理) 若X和Y分别是（LP)和(LD)的任一可行解，则有CX Yb推论1 若X为原问题LP的任一可行解，则CX为其

10、对偶问题LD的一个下界；若Y为LD的任一可行解，则Yb为LP的一个上界。推论2 若LP有可行解，LD无可行解，则LP无上界；同理，若LD有可行解，LP无可行解，则LD无下界。推论3 若LP有可行解，但其目标函数值无上界，则LD无可行解；同理，若LD有可行解，但其目标函数值无下界，则LP无可行解。推论4 若X*与Y*分别是LP与LD的可行解，且CX* =Y*b，则X*与Y*分别是LP和LD的最优解。推论5 LP与LD同时有最优解的充要条件是：LP与LD同时有可行解。西南交通大学管理学院例4：考虑下列线性问题，假定（1）和（2）都有可行解，证明若其中一个有最优解，则另一个也有最优解；若其中一个，；

11、在都有最优解的条件下，若 X 和 U 分别则另一个也CX ³ CU为（1）和（2）的可行解，则（1） min z1 = CX AX ³ b证明：（1）和（2）线性max z2 = CU AU £ b的对偶问题分别为（2）=maxz '1YA = CbYmin z1 = CX AX ³ bmax z2 = CU（3）（1）³Y0=minz '2bV（2）（4）VA= CV³ 0管理学院AU £ b西南交通大学问题1 （1）和（2）都有可行解，假设（1）有最优解，证明（2）也有最优解由于（1）有最优解，则（3）有

12、可行解，（3）与（4）约束同，则（4）也有可行解。由于（2）和（4）互为对偶且都有可行解，根据推论1知，（2）和（4）都有最优解。问题得证。问题2 （1）和（2）都有可行解，假设（1）（2）也，证明由于（1）有可行解但，据推论4则其对偶问题（3）无可行解。（3）和（4）约束相同，则（4）也无可行解。（2）和（4）互为对偶，（2）有可行解，（4）无可行解，据推论5知（2）。问题得证。西南交通大学管理学院U分别为（1）X 和问题3 （1）和（2）都有最优解，则若CX ³ CU和（2）的可行解，证明由问题1的证明过程可知，（1）（2）都有可行解，且（3）和（4）也都有可行解，设Y 为（3）

13、和（4）的可行解，则由定理1可得 CX ³ Yb 和 Yb ³ CU ，因此CX ³ CU问题得证西南交通大学管理学院例5用弱对偶定理，证明下述线性min z=x1x2+x3问题无下界x1x3 4x1x2 +2x33x1, x2 , x3 0证：其对偶问题为max w=4y1+3y2y1+y21y2 1y1+2y21y1, y20原问题有可行解，如X=(4,0,0)T。但对偶问题第一个约束加上第三个约束，得3y22。第二个约束两边同乘以（-1），得y2 1，故对偶问题无可行解。由推论5，原问题无下界。西南交通大学管理学院定理2 （最优性定理）若原和对偶都有可行解，

14、则它们都有有限最优解，而且其最优目标函数值相等，即max CX=min Yb定理3（对偶定理）若（LP）和（LD）中有一个有最优解，则另一个也有最优解，且目标函数值相等。原问题关系对偶问题有有限最优解有可行解，目标函数无可行解有有限最优解有可行解，目标函数无可行解西南交通大学管理学院定理 4 （互补松弛定理） 若X*与Y*分别是（LP）与（LD） 的可行解，则X*和Y*为最优解的充要条件是Ys*X*=0Y*Xs*=0等价于等价于*x *=0ysjj*=0yi xsij=1,2,ni=1,2,m如果最优解使某个约束取等号，则称这个约束是紧的，否则称为松的。原问题对偶问题y*x* > 0=

15、0某个变量对应变量约束为等式sjjy*> 0x*= 0约束为严格不等式sjjx*> 0y*= 0约束为严格不等式对应变量某个变量siiy* > 0x*= 0约束为等式isi西南交通大学管理学院例6对例1，已知其最优解为(4,2)T ，试根据对偶理论，直接求出其对偶问题例2的最优解。解：首先将（LP）及（LD）化为max z=2x1+3x2x1+2x2+xs1=84x1+ xs2=164x2+ xs3=12(LP)x1, x20xs1, xs2 , xs3 0min w=8y1+16y2+12y3y1+4y2 ys1=22y1+4y3 ys2=3(LD)y1, y2, y30

16、ys1, ys2 0西南交通大学管理学院再将(4,2)T代入（LP）的约束，得xs1=0, xs2=0 , xs3=4由定理4（互补松弛定理）知*=0yi xsiy3=0i=1,2,3得*=0由ysj xjj=1,2ys1= ys2=0得代入（LD）的约束，得y1+4y2 =22y1=3解得 y1*=3/2, y2*=1/8Y*=(3/2,1/8,0,0,0)西南交通大学从而有管理学院定理6LP的检验数对应对偶问题的一个解原问题达到最优时，单纯形表中检验数的负值，就等于其对偶问题的最优解西南交通大学管理学院原问题CBCN0XBXNXS初始表BNI最终表IB-1 NB-1检验数0CN - CBB

17、-1N-CBB-1对应的对偶变量-ys1-ys2-y举例：ma3x1 + 2x2min w = 90 y1 + 200 y2 + 210 y32£ 90£ 2003 y1 + 4 y22 y1 + 6 y2³ 7+ 7 y3 ³ 54x + 6x127x2 £ 210x1 ³ 0 , x2 ³ 0y1 , y2 , y3 ³ 0min w = 90 y1+ 200 y 2 + 210 y 33 y1 + 4 y2 - y4 + y6 = 72 y1 + 6 y2y i³ 0+ 7 y3 - y5 + y7

18、= 5i = 1," ,7西南交通大学管理学院y3y4y5y1y22x3x4x5x1x2管理学院西南交通大学cj9020021000MMbCBXBy1y2y3y4y5y6y79000y1 y210-14/5 -3/5-2/53/5-2/50121/101/5 -3/10 -1/53/1011/51/10gj00421424M-14 M- 24-218cj75000bCBXBx1x2x3x4x5750x1 x2 x5103/5-1/5001-2/53/1000014/5-21/101142442gj00-11/5-1/100三、对偶问题的意义B-1b = y*b + y*b +&quo

19、t;+ y* b= w* = Cz*B1122mm¶z=y *i¶biyi*变量位的意义是在其它条件不变的情况下，单的变化所引起的目标函数的最优值的变化。在完全市场条件下，价格对市场有调节作用当的市场价低于价格时，企业应买进该用于扩大生产当的市场价高于价格时，企业应把已有卖掉西南交通大学管理学院例7对例1，原问题最优点B(4,2),最优值Z*=14/8)89(1)设备台时数由8增到9，则可行域界线从移到了，最优点变为E,*y目标值由14增加到31/2，增加了3/2，等于对偶问题的1(2)原材料A若增加1千克，可行域边界由移到，最优点变为F，最优值y*增加1/8，等于对偶问题

20、的2(3)原材料B若增加1千克，可行域由移到了，最优点不变，最优值不变，y*所以对偶问题的等于03西南交通大学管理学院§对偶单纯形法一、对偶单纯形法的基本思想LP的最优解必须满足三个条件(1)基本解B -1b ³ 0C - CBB-1A £ 0 ÞYA³ C(2)可行性(对偶问题可行)(3)最优性LD可行性LP最优性西南交通大学管理学院逐步减少>0的检验数个数保持LP解可行g£ 0( 最优 )另一基解LP的基解j使LD解的不可行性逐步消除LD解可行 对偶单纯形法 保持LD解可行LP的基解逐步消除LD解的不可行性LD解可行( 最优

21、 )另一基解单纯形法：(1) (2)(1) (2) (3)对偶单纯形法：(1)(3)(1) (2) (3)西南交通大学管理学院对偶可行解可行性基可行解最优性单纯形法二、对偶单纯形法的解题步骤（1）假定已给一对偶可行基（即它对应的对偶问题的解可行）单位阵B ，相应的基解为XB=B-1b。若它的各个分量均非负，则这个解就是最优解，停止迭代。（2）如果XB有分量xBi<0，且xi所在行的所有系数aij0，则（LP） 无可行解，停止迭代；否则转（3）。（3）确定换出变量，若minbi| bi <0 =bli则对应的xl为换出变量；计算的值，若ìï gQ = min

22、52;ïa< 0=g kjíýljïî aljalkïþj则选择xk为换入变量，alk为主元。（4）以alk为主元，进行系数变换，得一新的正则解，转（2）。西南交通大学管理学院例1用对偶单纯形法解线性min z=3x1+2x2+x3+4x4问题2x1+4x2+5x3 +x4 03x1x2 +7x3 2 x4 25x1+2x2+x3+6x4 10x1, x2, x3, x4 0解引入剩余变量x5, x6, x7, 化所给max z= 3x1 2x2 x3 4x4为2x14x25x3x4+x53x1 + x2 7x3 +2

23、 x4+ x6=0= 25x12x2 x36x4x1, , x7 0+ x7= 10西南交通大学管理学院其初始单纯形表为当前解为正则解，但不可行（存在负分量）根据min0, 2, 10= 10,以x7为换出变量,由ì -3 , -2 , - 1 , -4 ü3Q = min=í -6 ý5-2- 1-5îþ以为x1为换入变量，以a31= 换，得新单纯形表西南交通大学5为主元进行系数变管理学院cj3 2 1 4000biCBXBx1x2x3x4x5x6x7000x5 x6 x72 4 5 110031 720105 2 1 600102

24、10rj32 1 40000由此得正则解X=(2,0,0,0,4,4,0)T,及相应目标函数值。因为bi0,所以X为最优解, 相应目标函数值6。西南交通大学管理学院cj3214000biCBXBx1x2x3x4x5x6x7003x5 x6 x10 16/5 23/57/510 2/5011/532/5 28/501 3/512/51/56/500 1/5442rj0 4/5 2/5 2/500 3/5-6§3灵敏度分析对于标准形式的线性来说max z = CX AX = bX ³ 0一旦其系数矩阵A，约束条件右侧向量b和价值系数向量C给定之后，这个线性系数是可能发生变化的。

25、问题也就确定了但是，这些研究线性模型某些系数或限制量的变化对最优解的影响极其程度的分析就称之为灵敏度分析。西南交通大学管理学院对解的影响主要有：1、最优解保持不变，即基变量和它们的取值没有变化2、基变量保持不变，但它们的值改变了3、基解完全变了因此，我们最终要回答下面两个问题：1、这些系数在什么范围内变化时，原先求出的线性规 划问题的最优解不变。2、如果系数的变化超出了上述范围，如何用最简便的 方法求出新的最优解。西南交通大学管理学院一价值系数变化B是原问题的最优基，xr ® c' = c + DcrrrXB = B-1bg = C - CBB-1A与c无关与c有关价值系数变

26、化不影响基的可行性，只影响基的最优性。1、xr 为非基变量cr 的变化只影响其本身的检验数gr,只要gr =< 0,最优解B-1 A不变.既对该c ,只需满足 g ' = C ' - C£ 0,否则可将rrrBrxr作为引入变量, 进行单纯形迭代求解.西南交通大学管理学院2、xr为基变量= Cr - CB B-1Ar虽然cr的变化不影响基B的可行性，但由 g r,而cB=(c1 , cr , cm)，故这种变化对所有变量的检验数都将产B-1 Ar生影响。只有 g '= Cr - C '£ 0（r=m+1, , n）时，最优解Br才不变。

27、否则，取最大检验数作单纯形迭代求解。西南交通大学管理学院例1 考虑线性问题max z=x1+2x2 x3x1+2x2+x38x1+x22x3 4x1, x2, x30当x1在目标函数中系数由1变为2时，进行灵敏度分析。解：该线性问题的原始单纯形表如下所示（表1）西南交通大学管理学院cj12100biCBXBx1x2x3x4x500x4 x5121101120184rj12100经一步迭代得最终单纯形表如下所示（表2）当x1的价值系数由1变为2时，注意到在最终表中为非基变量，故只须计算其新检验数，由于é 1 / 2ùg = C - C BA2（21B1-1ú = 1

28、 > 00）êë- 3 / 2û最优解发生变化，故需在最终表的基础上进一步求解。一步迭代得下表（表3），得以重新寻优西南交通大学管理学院cj12100biCBXBx1x2x3x4x520x2 X51/211/21/203/205/21/2140rj00210西南交通大学管理学院cj22100biCBXBx1x2x3x4x520x2 X51/211/21/203/205/21/2140rj10210cj22100biCBXBx1x2x3x4x520x1 X51211003111812rj02320二、右侧常数变化不影响最优性，只影响可行性XB = B-1bg

29、= C - CBB-1Agr =Cr -CBB-1Ar和X=B-1b知b的变化对检验数没由有影响，故不 影响B的最优性，但有可能对B的可行性产生影响。只要X=B-1b ³0，最优基就仍可B行。否则用对偶单纯形法迭代求解。西南交通大学管理学院例2对例1中的线性问题，当第一个约束方程的右侧常数由8变为10时，进行灵敏度分析。max z=x1+2x2 x3x1+2x2+x310x1+x22x3 4x1, x2, x30-1 é 1 / 20ùé10ùé 5 ù解X B = Bb = ê- 1 / 21ú

30、4; 4 ú = ê- 1úëûëûëû显然，最优解的可行性遭到破坏，以最终表为基础进一步求解。 得到表4西南交通大学管理学院西南交通大学管理学院cj12100biCBXBx1x2x3x4x520x2 X51/211/21/203/2 0 5/21/2151rj00210cj12100biCBXBx1x2x3x4x521x2 x1011/31/31/3105/31/32/314/32/3rj00210三、约束条件系数矩阵A的变化非基变量的系数列向量Aj变化XB = B-1bg = C - CBB-1A对于

31、不在基B中的元素akr发生变化时，注意到A的第r列Ar,amr)，而 g = C - CBB-1A ，显然只也变为Ar=(a1r,akr对xr对 应的检验数gr产生影响（不影响可行性，只影响最优性）。若满足=c -C B-1A' £0g 'rrBr则B仍为最优基。否则按一般单纯形法在原有的基础上重新寻优。对于基B中元素发生变化，情况比较复杂，这里就不再讨论。西南交通大学管理学院x3例3对例1中的线性问题，当第二个约束中的系数由-2变为-1时，作相应的灵敏度分析。解 注意到0 é 1 / 20ùé 1 ù = -2 < 0g

32、 1（2）êúêú3ë- 1 / 21ûë- 1û故最优解不变。西南交通大学管理学院四、增加或删去一个变量1、增加一个变量在原问题的最优单纯形表中增加一列，对应变量xn+1及B-1An+1，gB-1 A= c- C,不难看出， 原最优基仍是新问题的一检验数n+1n+1n+1B个可行基， xn+1为非基变量。（1）g n+1£ 0> 0,满足最优性条件，原B是新问题的最优基（2）gB -1 A£ 0 新问题，否则继续迭代。n+1n+12、删去一个变量若为非基变量，删去不影响最优基可行解和最优

33、目标函数值。若为基变量，可将其基（实施对偶单纯形法迭代，或以M为价值系数将其迭代出基），一旦出基即可删除。西南交通大学管理学院例4对例1中的线性问题，增加一变量，价值系数为2，约束系数矩阵列向量为(1,2)T，作相应的灵敏度分析。解：注意到æ0öæ 1 ö1 / 2= 2 - (20)çg÷ç÷ = 1 > 0ç - 1 / 21 ÷ç 2÷6èøèøæ0öæ 1 öæ 1 / 2

34、 ö1 / 2A6 = BA6 = ç-1÷ç÷ = ç÷1è - 1 / 21 øè 2øè 3 / 2ø将x6 引入，作单纯形迭代，得表5。西南交通大学管理学院西南交通大学管理学院cj121002biCBXBx1x2x3x4x5x620x2 X51/211/21/201/23/205/21/213/240rj002101cj121002biCBXBx1x2x3x4x5x622x2 X6114/32/ 31/30105/31/32/3140rj101/32/32/

35、30cj121002biCBXBx1x2x3x4x5x612x1 X6114/32/ 31/30011/31/31/3144rj0 15/34/31/30五、增加或删去一个约束条件1、增加一个约束条件x2=7 x+ 5 xmaxz123x +2x =903 x 1 +4 x 1 +2 x 2£ 9012£j =6 x 22001, "7x2=210C³x0, 5jDEB4x1+6x2=200z = 7 x 1+ 5 x 2max3 x 1 +4 x 1 +2 x 2£ 90£o6 x 2200x1Ax³ 0j = 1, &q

36、uot; ,5jR' Í R增加一个约束后，可行域的变化为西南交通大学管理学院7 x 2 £ 210分三种情况：R'R'= f新问题无可行解= R新问题最优解不变R' Ì R首先将原问题最优解代入束，如满足束，则最优解不变，否则在表中添加一个新变量为第n+1列，新约束为m+1行，但基变量所在列不是向量，用行初等变换将其化。2、删除一个约束条件若这个约束条件对来说是不起作用约束，即松弛变量，剩余变量不为零，则去掉这个约束条件对最优解无影响。反之，则使最优解发生变化，将松弛变量或剩余变量或人 工变量转为基变量即可。西南交通大学管理学院问

37、题，增加一个约束，x 2+x 3£ 3例5 对例1中的线性作灵敏度分析。解：显然原最优解不满足束，采用上述加行加列的方法对新问题的最初单纯形表（对偶单纯形法）迭代，依次得表，得以重新寻优。西南交通大学管理学院cj121000biCBXBx1x2x3x4x5x6200x2 X5 X61/211/21/2003/205/21/210011001403rj002101西南交通大学管理学院cj121000biCBXBx1x2x3x4x5x6200x2 X5 X41/211/21/2003/205/21/2101/2 01/21/201401rj002100cj121000biCBXBx1x2

38、x3x4x5x6201x2 X5 X1011001004113101102332rj002100= -5mazx例-2£0£1290³0, T 5,c =12,-=0A1()A6(1)b 变为95(5)的系数变为2T,c10=(=x ，系数为35)(2)b 变为45(6)增加一个变量61(3) c3变为8(4) c2变为66(7)增加一个约束250(8)第二个约束1变0 为100解,T=2010)z*=100æ 10ö-1= ç -4÷1øBè西南交通大学管理学院cj-551300b(CBXBx1x2x3x4x550x2 x5-11310160-2-412010gj00-2-50解(1)最优性不变，影响可行性= æçö÷1B