运筹学教程课件二 对偶理论与灵敏度分析

1、1第二章第二章对偶理论与灵敏度分析对偶理论与灵敏度分析 窗含西岭千秋雪，门泊东吴万里船窗含西岭千秋雪，门泊东吴万里船 对偶是一种普遍现象对偶是一种普遍现象22.1 线性规划问题的对偶问题及其变换线性规划问题的对偶问题及其变换2.1.1 线性规划对偶问题的提出及其经济意义线性规划对偶问题的提出及其经济意义 任何线性规划问题都有其对偶问题任何线性规划问题都有其对偶问题 对偶问题有其明显的经济含义对偶问题有其明显的经济含义 假设有商人要向厂方购买资源假设有商人要向厂方购买资源A A和和B B，问他们谈判原料，问他们谈判原料价格的模型是怎样的？价格的模型是怎样的？ 0,B 1522A 25322. .

2、433)(max4321432143214321xxxxxxxxxxxxt sxxxxxf资源资源例例 2.1.13 例例2.1.1设设A A、B B资源的出售价格分别为资源的出售价格分别为 y y1 1 和和 y y2 2显然商人希望总的收购价越小越好显然商人希望总的收购价越小越好工厂希望出售资源后所得不应比生产产品所得少工厂希望出售资源后所得不应比生产产品所得少 0, 4 423 3 32 2 32 1 121525)( 212121212121yyyyyyyyyyyyygMin的所得产品的所得产品的所得产品的所得产品 0,B 1522A 25322.433)(max43214321432

3、14321xxxxxxxxxxxxtsxxxxxf资源资源4 2.1.2 原问题与对偶问题的表达形式原问题与对偶问题的表达形式0XbAXtsCXxf. .)(max :原原问问题题0YCYAtsYbyg.)(min :对偶问题对偶问题TmnmTnbbbbcccCyyyYxxxX),(),(),(),(21212121上两式中上两式中mnmmnnaaaaaaaaaA2122221112115 2.1.12原问题与对偶问题的表达形式原问题与对偶问题的表达形式0,.)(min21221122222112112211112211mnmmnnnmmmmmmyyycyayayacyayayacyayaya

4、tsybybybyg把对偶问题展开把对偶问题展开0YCYAYbYTTTTTtsg. .)(min :对偶问题习惯写为6 一、一、标准标准(max,(max, ) )型的对偶变换型的对偶变换 目标函数由目标函数由 max max 型变为型变为 min min 型型 对应原问题每个约束行有一个对偶变量对应原问题每个约束行有一个对偶变量 y yi i，i i=1,2,=1,2,m m 对偶问题约束为对偶问题约束为 型，有型，有 n n 行行 原问题的价值系数原问题的价值系数 C C 变换为对偶问题的右端项变换为对偶问题的右端项 原问题的右端项原问题的右端项 b b 变换为对偶问题的价值系数变换为对偶

5、问题的价值系数 原问题的技术系数矩阵原问题的技术系数矩阵 A A 转置后成为对偶问题的技术转置后成为对偶问题的技术系数矩阵系数矩阵 原问题与对偶问题互为对偶原问题与对偶问题互为对偶对偶问题可能比原问题容易求解对偶问题可能比原问题容易求解对偶问题还有很多理论和实际应用的意义对偶问题还有很多理论和实际应用的意义 二、二、非非标准标准型的对偶变换型的对偶变换0,510342023.54)(max 2 . 1 . 2 1221212121xxxxxxxxtsxxxf不限不限原线性规划问题原线性规划问题例例 0, 551033420223.554)(max)(max, 22122122122122122

6、1xxxxxxxxxxxxxxxtsxxxxf型标准问题型标准问题化为化为0,532532443.551020)(min 43214321432143214321wwwwwwwwwwwwwwwwtswwwwwh则则应应用用标标准准型型对对偶偶变变换换规规不限经整理得令yyyyyyyyytsyyyygwwywywy,. .)(min:, 8三、三、原问题和其线性规划对偶问题的相互关系表原问题和其线性规划对偶问题的相互关系表 约束条件的类型与非负条件对偶约束条件的类型与非负条件对偶 非标准的约束条件类型对应非正常的非负条件非标准的约束条件类型对应非正常的非负条件 对偶变换是一一对应的对偶变换是一一

7、对应的9在使用在使用上上表规则写出某一线性规划的对偶规划时，要注意如下表规则写出某一线性规划的对偶规划时，要注意如下一些问题：一些问题：1）要看清原问题目标函数是）要看清原问题目标函数是max问题还是问题还是min问题。如果原问问题。如果原问题目标函数是题目标函数是max，在写其对偶问题时，应该利用，在写其对偶问题时，应该利用上上表左侧规表左侧规则向右侧规则变换；而如果原问题目标函数是则向右侧规则变换；而如果原问题目标函数是min，在写其对，在写其对偶问题时，则应该利用偶问题时，则应该利用上上表右侧规则向左侧规则变换；表右侧规则向左侧规则变换；2）如果原问题的约束条件不符合）如果原问题的约束条

8、件不符合上上表的规范要求，应该利用表的规范要求，应该利用等价变换规则，将约束条件变换成符合等价变换规则，将约束条件变换成符合上上表的规范要求。表的规范要求。例例 2.1.4 写出如下线性规划的对偶规划写出如下线性规划的对偶规划正负不限43243214321143214321, 0, 010543215653 12 425324 . .4643)(infxxxxxxxxxxxxxxxxtsxxxxxM1）第一）第一、二、二约束方程可用两个约约束方程可用两个约束方程等价表示；束方程等价表示；2) 没有给出没有给出x1 变量的约束条件，但变量的约束条件，但根据第二约束方程可推得，根据第二约束方程可推

9、得，x1 变量变量的约束条件为的约束条件为x10。因此，上述线性规划等价于如下线因此，上述线性规划等价于如下线性规划：性规划：10正负不限43214321432111432143214321,0,0,010543215653 12 ,42532425324 .4643)(infxxxxxxxxxxxxxxxxxxxxxxtsxxxxxM正负不限654321652165216521654321654321,0,0,0,0,045633645224344323 .10151242525)(yyyyyyyyyyyyyyyyyyyyyyyytsyyyyyyyMaxg11112.2 2.2 线性规划的对

10、偶定理线性规划的对偶定理1 1、弱弱对偶定理对偶定理定理定理1 1 对偶问题对偶问题(min)(min)的任何可行解的任何可行解Y Y0 0，其目标函数值总其目标函数值总是不小于原问题是不小于原问题(max)(max)任何可行解任何可行解X X0 0的目标函数值的目标函数值 为了便于讨论，下面不妨总是假设为了便于讨论，下面不妨总是假设0XbAXCX. .)(max :tsxf原问题0YCYAtsYbyg.)(min :对偶问题对偶问题(2) (1) , :0000CAYbAXYX故有题的可行解分别为原问题和对偶问由于证将将(1)式左乘式左乘Y0，将，将(2)式右乘式右乘X0，立刻可得，立刻可得

11、Y0b Y0AX0 CX0，证毕。，证毕。1212 弱弱对偶定理推论对偶定理推论 maxmax问题的任何可行解目标函数值是其对偶问题的任何可行解目标函数值是其对偶minmin问题目问题目标函数值的下限；标函数值的下限； minmin问题的任何可行解目标函数值问题的任何可行解目标函数值是其对偶是其对偶maxmax问题目标函数值的上限问题目标函数值的上限 如果原如果原max(min)max(min)问题为无界解，则其对偶问题为无界解，则其对偶 min (max)min (max)问题无可行解问题无可行解 如果原如果原max(min)max(min)问题有可行解，其对偶问题有可行解，其对偶 min

12、(max)min (max)问问题无可行解，则原问题为无界解题无可行解，则原问题为无界解 注注：存在原问题和对偶问题同时无可行解的情况：存在原问题和对偶问题同时无可行解的情况13例例 2.2.1 设有如下线性规划原问题设有如下线性规划原问题 0,70276503232032. .252)(max43214321432143214321xxxxxxxxxxxxxxxxt sxxxxxf 0,223523272163. .705020)(min321321321321321321yyyyyyyyyyyyyyytsyyyyg令令 X0=(x01，x02，x03，x04)T= (1，1，1，1)T，Y

13、0=（y01，y02，y03）=（1，1，1），则显然），则显然X0和和Y0分别为原分别为原问题和对偶问题的可行解。它们对应的目标函数值分别为问题和对偶问题的可行解。它们对应的目标函数值分别为f(X0)=C X0=10，即其对偶问题目标函数值的下限不会小于，即其对偶问题目标函数值的下限不会小于10；g(Y0)= Y0 b=140，即其原问题目标函数值的上限不会大于，即其原问题目标函数值的上限不会大于140；这一结果验证了弱对偶定理这一结果验证了弱对偶定理C X0 Y0 b。14例例 2.2.2 设有如下线性规划原问题设有如下线性规划原问题0,501002 .)(max21212121xxxxx

14、xtsxxxf 0,112 . .50100)(min21212121yyyyyytsyyyg令令 X0=(x01，x02)T= (1，1)T，则显然，则显然X0为原问题的可行解，为原问题的可行解，即线性规划原问题有可行解；但将对偶问题的两个约束方即线性规划原问题有可行解；但将对偶问题的两个约束方程相加后可得程相加后可得 - y1 2，这显然与非负约束矛盾，所以对偶，这显然与非负约束矛盾，所以对偶问题无可行解。根据弱对偶定理推论问题无可行解。根据弱对偶定理推论3可以判断原问题为无可以判断原问题为无界解。事实上，利用单纯形法求解原问题（见第一章界解。事实上，利用单纯形法求解原问题（见第一章例例1

15、.10）可得，原问题的确为无界解，根据弱对偶定理推论）可得，原问题的确为无界解，根据弱对偶定理推论2可以判断对偶问题无可行解可以判断对偶问题无可行解15152 2、最优解判别、最优解判别定理定理定理定理2 2 若原问题的某个可行解若原问题的某个可行解X X0 0的目标函数值与对偶问题某个的目标函数值与对偶问题某个可行解可行解Y Y0 0的目标函数值相等，则的目标函数值相等，则X X0 0, , Y Y0 0分别是相应问题的分别是相应问题的最优解最优解 证证：由弱对偶定理推论由弱对偶定理推论1， 有有 CX0 = Y0b CX, 即即X0是原问题的最优解；是原问题的最优解； 另有另有Y0b =

16、CX0 Yb，即，即Y0是对偶问题的最优解；证毕。是对偶问题的最优解；证毕。3 3、主对偶主对偶定理定理定理定理3 3 如果原问题和对偶问题都有可行解，则它们都有最优如果原问题和对偶问题都有可行解，则它们都有最优解，且它们的最优解的目标函数值相等。解，且它们的最优解的目标函数值相等。证证：由弱对偶定理推论：由弱对偶定理推论1 1可知，原问题和对偶问题的目标函可知，原问题和对偶问题的目标函数有界，故一定存在最优解。数有界，故一定存在最优解。 现证明定理的后一句话。现证明定理的后一句话。 1616 主对偶主对偶定理的证明定理的证明 证证：现证明定理的后一句话，采用反证法。：现证明定理的后一句话，采

17、用反证法。 设设 X X0 0 ， Y Y0 0分别为原问题和对偶问题的最优解，且分别为原问题和对偶问题的最优解，且 Y Y0 0b CXb CX0 0 根据最优性检验条件，非基变量的检验数满足根据最优性检验条件，非基变量的检验数满足C CN N C CB BB B 1 1N N 0 0，而，而基变量的检验数为基变量的检验数为0 0，可写成，可写成C CB B C CB BB B 1 1B B = 0= 0，所以，包括基变量在内的所有变量的，所以，包括基变量在内的所有变量的检验数满足检验数满足 C C C CB BB B 1 1A A 0 0。令令 Y=Y= C CB BB B 1 1，则有，

18、则有 Y Y A A C C。 另外，对应于松驰变量，有另外，对应于松驰变量，有 C CB BB B 1 1I I 0 0，即，即 Y=Y= C CB BB B 1 1 0 0，故，故 Y Y为对偶问题的可行解。为对偶问题的可行解。 对偶问题可行解对偶问题可行解Y的目标函数值为的目标函数值为 g(Y)=Yb = CBB 1b Y0b 原问题最优解原问题最优解X0的目标函数值为的目标函数值为 f(X0)=CX0= CBB 1b=Yb 所以有所以有CX00，根据互补松弛定理可得u01=0；2、因为y02=0.20，根据互补松弛定理可得u02=0；3、因为y01+ 2y02=1.61，根据对偶规划(

19、2.13)的第1个约束方程 可得v010，然后根据互补松弛定理可得x01=0；4、因为2y01+ y02=2.62，根据对偶规划(2.13)的第2个约束方程 可得v020，然后根据互补松弛定理可得x02=0；5、根据上述4个步骤的结论及原线性规划的约束方程可得如下线性方程组 2023203204030403xxxx解得，x03=x04=4。X0 = (x01，x02，x03，x04)T=(0，0，4，4)T2020 2.3 2.3原问题检验数与对偶问题的解原问题检验数与对偶问题的解 在主对偶定理的证明中我们有：对偶在主对偶定理的证明中我们有：对偶(min(min型型) )变量的最优解变量的最优

20、解等于原问题松弛变量的机会成本，或者说原问题松弛变量检等于原问题松弛变量的机会成本，或者说原问题松弛变量检验数的绝对值验数的绝对值 可以证明，对偶问题最优解的剩余变量解值等于原问题对可以证明，对偶问题最优解的剩余变量解值等于原问题对应变量的检验数的绝对值应变量的检验数的绝对值 由于原问题和对偶问题是相互对偶的，因此对偶问题的检验由于原问题和对偶问题是相互对偶的，因此对偶问题的检验数与原问题的解也有类似上述关系。数与原问题的解也有类似上述关系。 更一般地讲，可以证明，不管原问题是否标准，在最优解的更一般地讲，可以证明，不管原问题是否标准，在最优解的单纯型表中，都有原问题虚变量单纯型表中，都有原问

21、题虚变量(松弛、剩余或人工变量松弛、剩余或人工变量) 的的机会成本的绝对值等于其对偶问题实变量机会成本的绝对值等于其对偶问题实变量 (对偶变量对偶变量)的最优的最优解的绝对值，原问题实变量解的绝对值，原问题实变量(决策变量决策变量)的检验数的绝对值等的检验数的绝对值等于其对偶问题虚变量于其对偶问题虚变量 (松弛或剩余变量松弛或剩余变量)的最优解的绝对值。的最优解的绝对值。因此，原问题或对偶问题只需求解其中之一就可以了。因此，原问题或对偶问题只需求解其中之一就可以了。21 例例2.2.3 原问题检验数与对偶问题的解原问题检验数与对偶问题的解不不限限原原问问题题321321321321321, 0

22、,101632182.635)(max :xxxxxxxxxxxxtsxxxxf不限不限对偶问题对偶问题321321321321321, 0,633252.101618)(min :yyyyyyyyyyyytsyyyyg22Cj 536-600 MCBXBbx1x2x 3x 3x4x5x60 x41 8121 11000 x51 621(3 ) 3010 Mx61 0111 1001O B J = 1 0 M M M MM00 Mcj - zj5 + M3 + M6 + M-6 -M0000 x43 8 /31 /35 /3001 1 /306x 31 6 /32 /31 /31 101 /3

23、0 Mx61 4 /31 /3(2 /3 )000 1 /31O B J =3 2 -1 4 M /34 -M /32 -2 M /36 602 + M /3 Mcj - zj1 + M /31 + 2 M /3000-2 -M /300 x41 1 /200011 /2 5 /26x 33(1 /2 )01 101 /2 3 /23x271 /21000 1 /23 /2O B J =3 99 /236 603 /23 /2cj - zj1 /20000 3 /2-M -3 /20 x44001 111 35x16102 201 13x2401 1(1 )0 12O B J =4 2537

24、702 1cj - zj00 110 2-M + 10 x48010010 15x11 412000 13 6x 3401 110 12O B J =4 6546 6013cj - zj0 1000 1-M 3对对 偶偶 问问 题题 最最 优优 解解 ：y4= 0y5= 1y6= 0y1= 0y2= 1y3= 3原原 问问 题题 最最 优优 解解 ： x1= 1 4 , x2= 0 , x3= -4 , x4= 8 , x5= 0 , x6= 0 , O B J = 4 623Cj 18161000MCBYBby1y2y3y4y5y60y4-5-1-2-11000y5-3-2-1-1010My

25、6613(1)001OBJ=6MM3MM00Mcj - zj18-M16-3M10-M0000y410(1)01010y53-12001110y36131001OBJ=601030100010cj - zj8-14000M-1016y210101010y51-300-21-110y33101-30-2OBJ=46101610-140-4cj - zj800140M 4原原问问题题最最优优解解：x4=8x5=0 x6=0 x1=14x2=0 x3= 4对对偶偶问问题题最最优优解解：y1=0, y2=1, y3=3, y4=0, y5=1, y6=0, OBJ=4624242.42.4对偶单纯型法

26、对偶单纯型法2.4.1 2.4.1 基本思路基本思路1 1、原单纯型迭代要求每步都是基础可行解、原单纯型迭代要求每步都是基础可行解2 2、达到最优解时，检验数、达到最优解时，检验数 c cj jz zj j 0 (max)0 (max)3 3、对于、对于(min, (min, ) )型所加的剩余变量无法构成初始基础可行解型所加的剩余变量无法构成初始基础可行解4 4、因此通过加人工变量来解决、因此通过加人工变量来解决, ,但大但大M M法和二阶段法较繁法和二阶段法较繁5、对偶单纯形法基本思路：对偶单纯形法基本思路： 从原问题的某一个满足最优检验条件的基本解出发，判断从原问题的某一个满足最优检验条

27、件的基本解出发，判断该基本解是否满足可行性条件，若是，则已得最优解，若该基本解是否满足可行性条件，若是，则已得最优解，若否，则通过迭代得到另一个满足最优检验条件且更接近可否，则通过迭代得到另一个满足最优检验条件且更接近可行解的基本解。如此循环，直到找到满足最优检验条件且行解的基本解。如此循环，直到找到满足最优检验条件且可行解的基本解（即最优解）为止。可行解的基本解（即最优解）为止。2525 2.4.2对偶单纯形法的步骤对偶单纯形法的步骤1、求一个满足最优检验条件的初始、求一个满足最优检验条件的初始基础基础解，列出初始单纯形表；解，列出初始单纯形表；2、可行性检验、可行性检验 若所有的右端系数均

28、大于等于若所有的右端系数均大于等于0，即，即 bi 0，i=1,2,.,m则已得最优解，停止运算。否则，转步骤则已得最优解，停止运算。否则，转步骤3；3、求另一个满足最优检验条件且更接近可行解的、求另一个满足最优检验条件且更接近可行解的基础基础解解1）确定出变量）确定出变量 找非可行解中分量最小者，即找非可行解中分量最小者，即 min bi | bi 0，不会破坏最优解，不会破坏最优解 若若 aij 0，必须保证，必须保证 cj zj 041ijijjijjiijiijjjNjjiijjNjijijmkkkjjjaqzcqizcqaqazczcqazzaaqazx 所所以以型型行行约约束束为为

29、对对于于第第即即则则有有变变动动设设则则有有为为非非基基变变量量设设 , 0 , 0, , 0001042x1, x3为非基变量， q1= 0, q2= 0.25, q3= 1, 故有 333123211311175. 275. 2125. 325. 325. 075. 21125. 025. 313 aaaaaa x2, x4为基变量，x5=100, b1有剩余， 故有5 .020010011001001412aa x1x2x3x4x5x6x7CBXBb15340000 x51001/40-13/4011/4-14x420020-2101-15x2100-3/4111/400-3/41130

30、04.2555.75400.251cj-zj-3.250-2.7500-0.25-143 2.5.5 新增决策变量的分析新增决策变量的分析 例例2.4.2中，若新增产品中，若新增产品 x8，问是否生产？，问是否生产？ 已知已知 c8=9, a18=5, a28=4, a38=3 计算计算 x8 的检验数可知生产是否有利的检验数可知生产是否有利05) 1325. 0405(9318888iiiaqczc结论：生产x8有利。将B1P8加入最优单纯型表中，以x8为入变量进行迭代44 2.5.6 新增约束条件的分析新增约束条件的分析1、将最优解代入新的约束条件，若满足，则最优解不变、将最优解代入新的约

31、束条件，若满足，则最优解不变2、若不满足，则当前最优解要发生变化；将新增约束条、若不满足，则当前最优解要发生变化；将新增约束条件加入最优单纯型表，并变换为标准型件加入最优单纯型表，并变换为标准型3、利用对偶单纯型法继续迭代、利用对偶单纯型法继续迭代 为什么可以利用对偶单纯型法为什么可以利用对偶单纯型法x1x2x3x4x5x6x7x8CBXBb153400000 x51001/40-13/4011/4-104x420020-2101-105x2100-3/4(1)11/400-3/4100 x865012330001例2.4.2 第2步45x1x2x3x4x5x6x7x8CBXBb1534000

32、00 x51001/40-13/4011/4-104x420020-2101-105x2100-3/4(1)11/400-3/4100 x8650123300010 x51001/40-13/4011/4-104x420020-2(1)01-105x2100-3/4111/400-3/4100 x84505/20-5/2301.5-210 x51001/40-13/4011/4-104x420020-2101-105x2100-3/4111/400-3/4100 x8-150-7/207/200-1.51146x1x2x3x4x5x6x7x8CBXBb153400000 x51001/40-1

33、3/4011/4-104x420020-2101-105x2100-3/4111/400-3/4100 x8-150-7/207/200(-1.5)111300 4.2555.75400.2510cj-zj-3.250-2.7500-0.25-100 x575-0.330-2.67010-0.83 0.174x4100-0.3300.33100-0.33 0.675x21751110000.5-0.50 x61002.330-2.33001-0.67 -0.671275 3.6756.334001.170.17cj-zj-2.670-3.33000-1.17 -0.17注意：最优解的目标函数减

34、少了25个单位47 2.5.7 灵敏度分析举例灵敏度分析举例产产量量 组组别别单单位位售售价价 品品种种I II III IV V(元元)A 产产品品数数量量3244010B 产产品品数数量量612145C 产产品品数数量量265184耗耗费费 组组别别 资资源源I II III IV V资资源源限限制制工工人人工工时时(小小时时)0461280小小时时/天天机机器器工工时时(小小时时)1121150小小时时/天天每每组组生生产产费费用用(元元)481930407例例2.4.3 某工厂生产三种产品某工厂生产三种产品 A, B, C，有五种生产组合方案。，有五种生产组合方案。下两表给出有关数据。规定每天供应下两表给出有关数据。规定每天供应 A产品至少产品至少110 个，求收个，求收益最大的生产方案。益最大的生产方案。48 例例2.13解解：设设xj为已选定各种组合方案的组数为已选定各种组合方案的组数(j=1,2,5)， x6为为A产品产品的剩余变