运筹学第三章对偶理论

1、第第3章章 线性规划对偶理论线性规划对偶理论及其应用及其应用例例1 穗羊公司的例子穗羊公司的例子III每周可使用量每周可使用量A（千克）（千克）125B（吨）（吨）214C（百工时）（百工时）439单位产品利润（万元）单位产品利润（万元）323.1 线性规划的对偶问题线性规划的对偶问题穗家公司由于订单较多，希望收购穗羊公司的各种穗家公司由于订单较多，希望收购穗羊公司的各种资源以扩大自己的生产能力，那么穗羊公司的资源资源以扩大自己的生产能力，那么穗羊公司的资源该如何定价呢？该如何定价呢？0,934425223max2121212121xxxxxxxxs.t.xxz生产计划问题（生产计划问题（LP

2、1）资源定价问题（资源定价问题（LP2）原料原料A原料原料B工时工时CY1Y2Y3产品产品1产品产品2原料原料A原料原料B工时工时C产品产品1产品产品2方程对变量，变量对方程方程对变量，变量对方程 min w = 5y1+4y2+9y3 y1+ 2 y2 + 4y332 y1 + y2 + 3y32y1 , y2 , y3 03.1.2 规范形式线性规划的对偶问题规范形式线性规划的对偶问题0. .maxXbAXtsCXz0. .minYCYAtsYbw原问题（LP1）对偶问题（LP2） 原问题（LP1） 对偶问题 （LP2） 目标目标max型型 目标目标min型型 有有n个变量（非负）个变量（

3、非负） 有有n个约束（大于等于）个约束（大于等于） 有有m个约束个约束 （小于等于）（小于等于） 有有m个变量（非负）个变量（非负） 价值价值系数系数 资源系数资源系数 资源资源系数系数 价值价值系数系数 技术系数矩阵技术系数矩阵 技术系数矩阵的转置技术系数矩阵的转置(AB)=AB(AB)= BA(A)=A 矩阵转置 max. .(3.1)0zCXAXbstXmin. .(3.2)0wb YA YCstY12nyyYy3.1.3 非规范形式线性规划的对偶问题非规范形式线性规划的对偶问题1 变量取值范围不符合非负要求的情况变量取值范围不符合非负要求的情况0,22122111.min2122112

4、12211yycyycyytsybybw0,22211211.max212211212211xxbxxbxxtsxcxcz0, 022211211. .max212211212211xxbxxbxxtsxcxcz0,22122111. .min212211212211yycyycyytsybybw将其约束方程第二行将其约束方程第二行左右同乘左右同乘-1： 0,22211211. .max212211212211xxbxxbxxtsxcxcz令令 022xx0,22122111. .min212211212211yycyycyytsybybw无约束212211212211, 022211211.

5、 .maxxxbxxbxxtsxcxcz0,22122111. .min212211212211yycyycyytsybybw解解:令令2 约束方程不是约束方程不是“”的情况的情况 0, 022211211. .max212211212211xxbxxbxxtsxcxcz解：约束方程第二解：约束方程第二行左右同乘行左右同乘1：其对偶规划为：其对偶规划为：令 得到原问题的对偶问题为： 0, 022211211. .max212211212211xxbxxbxxtsxcxcz无约束212211212211, 022122111. .minyycyycyytsybybw解解: :约束方程第二行的约束

6、方程第二行的等式拆为两个不等式等式拆为两个不等式: :其对偶规划为：其对偶规划为：令 得到原问题的对偶问题为： 3.1.4 总结总结方程对变量，变量对方程；方程对变量，变量对方程；正常对正常，不正常对不正常；正常对正常，不正常对不正常；变量正常是非负，方程正常看目标变量正常是非负，方程正常看目标(max ，min )。 max =7y1+4y2-2y3 2y1+ y2 - y3 3 y1 +3y3 2-4y1+ 2y2 -6 y1 - y2 - y3 0 3y1 + y3 1 y10, y20, y3无约束无约束 =min z=3x1+2x2-6x3+x5 2x1+ x2- 4x3+x4+3x

7、57 x1+ 2x3 -x4 4 -x1+3x2 -x4+ x5 = -2 x1,x2,x30; x4 0;x5无约束无约束 例例 求解下面线性规划的对偶规划求解下面线性规划的对偶规划0, 0, 04422923532. .532max43214321432143214321xxxxxxxxxxxxxxxxtsxxxxz无约束，无约束321321321321321321, 0, 053423122223. .495minyyyyyyyyyyyyyyytsyyywLP2: min w = 5y1+4y2+9y3 y1+ 2 y2 + 4y33 st. 2 y1 + y2 + 3y32 y1 ,

8、y2 , y3 0 x1 + 2x2 5 2x1+ x2 4 4x1+3x2 9 x1 ,x2 0LP1: max z=3x1+2x2st. .对偶变量对偶变量y1y2y3对偶变量对偶变量x1x2 x x1 1+ +2x2 +x3 = 52x1+ x2 +x4 = 44x1+3x2 +x5 = 9 x1 ,x2 ,x3 ,x4 , x50 y1 + 2y2 + 4y3 y4 = 32y1 + y2 + 3y3 y5 = 2 y1 , y2 , y3 , y4 , y5 0原原问题变量问题变量原问题松弛变量原问题松弛变量CBXBx1x2x3x4x5b032x3x1x20100011005/23/

9、2-2-3/2-1/213/23/21- -j j0001/21/213/2原问题松弛变量原问题松弛变量原原问题变量问题变量x3 x4x5x1x2对偶问题剩余变量对偶问题剩余变量对偶问题变量对偶问题变量y4 y5y1y2y3对偶问题变量对偶问题变量对偶问题剩余变量对偶问题剩余变量CBXBy1y2y3y4y5b49y2y3-5/415/21001-1/41/21/4-3/21/21/2j j3/2003/2113/232000CBXBx1x2x3x4x5b000 x3x4x5124213100010001549320000030 x3x1x50103/21/21100-1/21/2-200132

10、101/20-3/206032x3x1x20100011005/23/2-2-3/2-1/213/23/21000-1/2-1/213/2max z = CX + 0XS st. AX +I XS = b ( I式式 ) X, XS0I 式式经过若干迭代，经过若干迭代，基矩阵为基矩阵为B，则则上式上式等价与等价与：max z = CBXB + CNXN + 0XS st. BXB + NXN+ I XS = b XB, XN, XS0max z = CX st. AX b X0LP:max Z = CB B -1b+（CN-CB B -1N）XN - CB B -1XS st. XB + B

11、-1N XN + B -1XS = B -1b XB ，XN，XS 0 单纯形算法的矩阵表示单纯形算法的矩阵表示基基解解 XB XN XSXSb B N I j CB CN 0基基解解 XB XN XSXBB -1b I B -1N B -1 j 0 CN - CB B 1N - CB B -1初始单纯形表初始单纯形表基为基为B时单纯形表时单纯形表单纯形算法的矩阵表示单纯形算法的矩阵表示Cj23 500bCBXBx1x2 x3x4x50 x42/3 1/3 4/31011/60 x52/3 4/3 10/30110/3j j23 50000 CN-CBB-1N-CBB-1CBB-1bCB CN

12、 00例例: max z = 2x1+3x2+5x3 2/3 x1+ 1/3 x2 + 4/3x311/6 st. 2/3 x1 + 4/3x2 + 10/3x310/3 x1 , x2 , x3 0BINB-1NIB-1Cj23 50 0bCBXBx1x2 x3x4 x52x11 0 12-1/223x20 1 2-1 13/2j j00 -3-1 -217/2初初始始表表最最终终表表3max z = 2x1+3x2+5x3 2/3 x1+ 1/3 x2 + 4/3x3 + x4= 11/6 st. 2/3 x1 + 4/3x2 + 10/3x3 + x5= 10/3 x1 , x2 , x

13、3 ，x4 , x5 0基基解解 XB XN XSXBB -1b I B -1N B -1 j 0 CN - CB B 1N - CB B -1基为基为B时单纯形表时单纯形表若若B为最优基，则为最优基，则 CB CBB 1B = 0CN CBB 1N 0 - CBB -1 0则则 AY C Y0= Yb = CBB1 b= z* 令令 Y = CBB1，Y = S S = CBB1YS = = C CBB1AC CBB 1A 0- CBB 10例：下表为例：下表为“max，”型线性规划问题加入松弛变量型线性规划问题加入松弛变量后的最优解单纯形表后的最优解单纯形表BV.x1x2x3x4x5bx1

14、100105x500-1/21/211x2011/2-1/20200-3/2-1/20（1 1）问题中有几个约束方程、几个决策变量、几）问题中有几个约束方程、几个决策变量、几个松弛变量？个松弛变量？（2 2）此线性规划问题的最优解）此线性规划问题的最优解x x* *=?=?（3 3）对偶问题的最优解）对偶问题的最优解y y* *=? =? 3.2 对偶规划的基本性质对偶规划的基本性质3.2.1 对称性定理对称性定理：线性规划的对偶问题的对偶问题：线性规划的对偶问题的对偶问题是原问题是原问题证明：证明： 对偶的定义对偶的定义对偶的定义对偶的定义max z=CXs.t. AXb X 0min w=

15、bYs.t. AYCY 0min z = - CXs.t. -AX -bX 0max w = -bYs.t. -AY-CY 0 以下定理以下定理3.2.2-3.2.5，假定原问题是，假定原问题是(3.1)，对，对偶问题是偶问题是(3.2)。 max. .(3.1)0zCXAXbstXmin. .(3.2)0wb YA YCstY3.2.2 弱对偶性定理弱对偶性定理：如果：如果X、Y分别是原问题和对分别是原问题和对偶问题的一个可行解，则其对应的原问题的目偶问题的一个可行解，则其对应的原问题的目标函数值不大于对偶问题的目标函数值，也即标函数值不大于对偶问题的目标函数值，也即YbCX0XbAX0YC

16、YAYbYAXYAXCXCX)(证明：因为证明：因为X、Y分别是原问题（分别是原问题（3.1）与对偶问题）与对偶问题（3.2）的可行解，故：）的可行解，故： 所以所以 推论一推论一：原问题任一可行解的目标函数值是其：原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值一可行解的目标函数值是其原问题目标函数值的上界。的上界。 推论二推论二：如果原问题存在无界解，则对偶问题：如果原问题存在无界解，则对偶问题一定无可行解；反之，如果对偶问题存在无界一定无可行解；反之，如果对偶问题存在无界解，原问题也一

17、定不存在可行解。解，原问题也一定不存在可行解。( (若其中一若其中一个问题为无界解，则另一个问题无可行解个问题为无界解，则另一个问题无可行解) ) 注意，该推论的逆定理并不成立。注意，该推论的逆定理并不成立。 3.2.3 最优性定理最优性定理: :如果如果 是原问题的可行解，是原问题的可行解， 是其对偶问题的可行解，且有是其对偶问题的可行解，且有 ，则：则： 是原问题和对偶问题的最优解。是原问题和对偶问题的最优解。XYYbXC YX、证明证明: 假设假设X* ,Y*分别是原问题与对偶问题的分别是原问题与对偶问题的最优解，则显然它们也是各自的可行解。最优解，则显然它们也是各自的可行解。而根据最优

18、解的定义，而根据最优解的定义， *CXXCXCYbCX *由弱对偶性定理得：由弱对偶性定理得：所以所以 *CXXC因而因而 是也原问题的最优解是也原问题的最优解 X同理，可证同理，可证 也是其对偶问题的最优解。也是其对偶问题的最优解。 Y3.2.4 强对偶性定理（对偶定理）强对偶性定理（对偶定理）如果原问题存在最优解如果原问题存在最优解X*，则其对偶问题一定具，则其对偶问题一定具有最优解有最优解Y*，且，且*YbCX则则Y*=0, 且且AY* C所以由最优性定理知所以由最优性定理知Y*为对偶问题的最优解。为对偶问题的最优解。 如果原问题存在最优解，假设其对应的基是如果原问题存在最优解，假设其对

19、应的基是B，即，即 0,*1*NBXbBX令令)(1*BCYB所以所以Y*满足对偶问题的约束条件满足对偶问题的约束条件, 是其可行解是其可行解 又因为又因为 CX* = CBB1 b= (Y*)b=b Y*3.2.5 互补松弛定理互补松弛定理线性规划问题的最优解中，线性规划问题的最优解中，)0 x (bx a,0y siin1jjiji 即即则则若若0y ),0 x (bx aisiin1jjij 则则即即若若njxmibxatsxczjinjijijjnjj,2, 1,0,2, 1,.max11线性规划问题的最优解中，线性规划问题的最优解中，0y ,cy a,0 x sjjm1iiijj 即

20、即则则若若0 x ,0y ,cy ajsjjm1iiij 则则即即若若yi xSi = 0 xj ySj = 0miynjcyatsybwijmiijimiii,2, 1,0,2, 1,.min11yi0,分为两种情况：分为两种情况： yi0，变量比较松；，变量比较松；yi=0，变量比较紧；，变量比较紧；互补松弛定理的解释互补松弛定理的解释约束方程约束方程 分为两种情况：分为两种情况： , ,约束条件比较松；约束条件比较松； , ,约束条件比较紧约束条件比较紧injjijbxa1injjijbxa1injjijbxa1变量同其对偶问题的约束方程之间至多只能够有一个取松弛的情况，当其中一个取松弛

21、的情况时，另外一个比较紧，即取严格等号 。 例例3.6 已知下面的已知下面的LP1和和LP2为一组对偶规划，且已知为一组对偶规划，且已知LP1的最优解为的最优解为X=（1.5，1）T。试运用互补松弛定理。试运用互补松弛定理求出对偶问题的最优解求出对偶问题的最优解Y。解：由解：由X=（1.5，1），得），得55 . 3221 xx01y0, 021xx232342321321yyyyyy联立求解得：联立求解得：5 . 0, 5 . 0, 0321yyy生产计划问题（生产计划问题（LP1）资源定价问题（资源定价问题（LP2） max z=3x1+2x2 x1 + 2x2 5 2x1+ x2 4 4

22、x1+3x2 9 x1 ,x2 0st. . y1+ 2 y2 + 4y33 st. 2 y1 + y2 + 3y32 y1 , y2 , y3 0 min w = 5y1+4y2+9y3 3.3 影子价格和灵敏度分析影子价格和灵敏度分析 3.3.1 影子价格影子价格 对偶变量的经济含义就是资源的定价，然而对偶变量的经济含义就是资源的定价，然而这种价格同市场价格不同，我们称之为影子价格。这种价格同市场价格不同，我们称之为影子价格。它反映了资源对于企业的紧缺程度、利润贡献程它反映了资源对于企业的紧缺程度、利润贡献程度等，并不能反映资源的生产成本，以及在外部度等，并不能反映资源的生产成本，以及在外

23、部市场的紧缺程度。市场的紧缺程度。 1 1、影子价格是边际利润、影子价格是边际利润wybYbCXzmiii1iiybw如果某种资源有剩余，则增加资源不会增加利润；如果某种资源有剩余，则增加资源不会增加利润；如果某种资源影子价格大于如果某种资源影子价格大于0 0，则资源一定没有剩余。，则资源一定没有剩余。说明资源增加说明资源增加1 1个单位，企业总利润可以增加个单位，企业总利润可以增加y yi i单位。单位。所以如果资源的市场价格低于所以如果资源的市场价格低于y yi i，就要买进。，就要买进。互补松弛定理互补松弛定理y1y2ym2、影子价格是影子价格是产品的机会成本产品的机会成本 (Oppor

24、tunity Cost)机会成本机会成本 表示减少一件产品所节省的资源可以增加的利润表示减少一件产品所节省的资源可以增加的利润mmjiijjjyayayaya2211减少一件产品可以节省的资源减少一件产品可以节省的资源0 xxxxbxaxaxaxabxaxaxaxabxaxaxaxas.t.xcxcxcxczmaxnj21mnmnjmj2m21m12n2nj2j2221211n1nj1j212111nnjj2211增加单位资源可以增加的利润增加单位资源可以增加的利润如果该产品机会成本大于利润，则该产品不生产。如果该产品机会成本大于利润，则该产品不生产。对于原有产品，如果生产的，则其机会成本等于

25、对于原有产品，如果生产的，则其机会成本等于利润。利润。0jxjmiiijcya10jxjmiiijcya1miiijya1对于原有产品对于原有产品j j，其机会成本为，其机会成本为 在利润最大化的生产计划中在利润最大化的生产计划中 （1）影子价格大于）影子价格大于0的资源没有剩余；的资源没有剩余； （2）有剩余的资源影子价格等于）有剩余的资源影子价格等于0； （3）安排生产的产品机会成本等于利润；）安排生产的产品机会成本等于利润； （4）机会成本大于利润的产品不安排生产。）机会成本大于利润的产品不安排生产。总结3.3.2 灵敏度分析灵敏度分析1、目标函数系数、目标函数系数cj变化变化例例 3.

26、7 C由由(3.2)变为变为(3,1)，请问最优生产计划如何变化？，请问最优生产计划如何变化？32000CBXBx1x2x3x4x5b000 x3x4x512421310001000154932000032000CBXBx1x2x3x4x5b032x3x1x20100011005/23/2-2-3/2-1/213/23/21000-1/2-1/211114 5初初始始表表最最优优表表z解：由原最优单纯形表得：解：由原最优单纯形表得：31000CBXBx1x2x3x4x5b031x3x1x20100011005/23/2-2-3/2-1/213/23/21000-5/21/211/2252325

27、4) 2(1300500 ( 3/2)3 ( 1/2) 1 1 1/20 所以原最优解不是新问题的最优解所以原最优解不是新问题的最优解 单纯形迭代得：单纯形迭代得：31000bCBxBx1x2x3x4x50 x30 3/21 -1/2033x11 1/20 1/2020 x50 10 -21 1 0 -1/20- 3/206所以得到新的最优生产计划为产品所以得到新的最优生产计划为产品I生产生产2件，件，产品产品II不生产，此时总利润上升为不生产，此时总利润上升为6万元。万元。例例3.8 假设产品假设产品II的价格不变，请问产品的价格不变，请问产品I的利润在什的利润在什么范围内波动时，最优生产计

28、划不变？么范围内波动时，最优生产计划不变？ 41 32 512欲使最优生产计划不变，须欲使最优生产计划不变，须02102311313解：假设解：假设c1由由3变为变为 ，则，则32000bCBxBx1x2x3x4x50 x30 0 1 5/2-3/23/23x11 0 0 3/2- 1/23/22x20 1 0 -2 1 1 0 0 0 - 1/2-1/213/2所以所以,当当-1/3,1,即即c1 8/3,4时时,最优生产计划不变最优生产计划不变最优解保持不变的最优解保持不变的C变化范围变化范围但要分两种情况讨论。只影响最优性时变为价格,ccc即可。故只要，为因只影响自己的检验数的价格系数是

29、非基变量0, (1)1jjBjjjjjPBCccxc 的范围。解得只需由jjc 0。解得公共的应由所有的数这时要影响所有的检验的价格系数是基变量jiimiiiijjcPBcccccxc0,)( (2)112、约束条件右端向量、约束条件右端向量b的变化的变化 例例3.8 b由由(5 4 9)T变为变为(5 5 9)T，最优生产计划如何变化？，最优生产计划如何变化？32000CBXBx1x2x3x4x5b000 x3x4x512421310001000154932000032000CBXBx1x2x3x4x5b032x3x1x20100011005/23/2-2-3/2-1/213/23/2100

30、0-1/2-1/213/25b1 b2 b3 z初初始始表表最最优优表表1349551202/12/302/32/511bBXB解：解：显然显然X=(3,-1,4,0,0)T不是基可行解不是基可行解XB带入原最终单纯形表得：带入原最终单纯形表得：32000bCBxBx1x2x3x4x50 x30 0 1 5/2-3/24(1)3x11 0 0 3/2- 1/23(2)2x20 1 0 -2 1 -1 (3)0 0 0 - 1/2-1/27(4)jl因为因为x2=-10，所以令其，所以令其岀岀基。基。minbi/bi0=brl检验数所在行除以出基变量所在行，商最小的列对应的检验数所在行除以出基变量所在行，商最小的列对应的元素作为主元素元素作为主元素min /arj ,arj0 。这里。这里正数和零不能正数和零不能作为主元素作为主元素 。l本题中第三行只有本题中第三行只有a34=-20，所以选为主元素，进行对偶，所以选为主元素，进行对偶迭代迭代l迭代的目标：迭代的目标：