1、 第3节 对偶与灵敏度分析2一、一、 线性规划的对偶关系线性规划的对偶关系二、二、 线性规划的对偶性质线性规划的对偶性质三、灵敏度分析三、灵敏度分析四、对偶关系的经济解释四、对偶关系的经济解释第第3节节 对偶与灵敏度分析对偶与灵敏度分析 灵敏度分析灵敏度分析以前讨论线性规划问题时，假定ij，bi,cj都是常数。但实际上这些系数往往是估计值和预测值。如市场条件一变，cj值就会变化；ij往往是因工艺条件的改变而改变；bi是根据资源投入后的经济效果决定的一种决策选择。显然，当线性规划问题中某一个或几个系数发生变化后，原来已得结果一般会发生变化。因此，所谓灵敏度分析灵敏度分析，是指当线性规划问题中的参
2、数发生变化后，引起最优解如何改变的分析。灵敏度分析灵敏度分析 灵敏度分析是要在求得最优解以后，解决以下几方面灵敏度分析是要在求得最优解以后，解决以下几方面的问题：的问题：（1）线性规划问题中的）线性规划问题中的各系数各系数在什么范围内变化，在什么范围内变化，不会影响已获得的最优基。不会影响已获得的最优基。（2）如果）如果系数的变化超过以上范围系数的变化超过以上范围，如何在原来最，如何在原来最优解的基础上求得新的最优解。优解的基础上求得新的最优解。（3）当线性规划问题）当线性规划问题增加一个新的变量或新的约束增加一个新的变量或新的约束，如何在原来最优解的基础上获得新的最优解。如何在原来最优解的基
3、础上获得新的最优解。 1.1.目目标函数系数标函数系数C C的变化范围的变化范围目标函数系数变化目标函数系数变化，只会影响最优，只会影响最优解解中中检验数行，检验数行，不会影响不会影响基变量的基变量的取取值。值。即即C中元素的变化只会影响中元素的变化只会影响最优解的对偶可行性而不会影响原最优解的对偶可行性而不会影响原始可行性始可行性。 m个基变量xBr（r=1,2,m）在目标函数中的系数为：001011BrBmBrBBrBrBBrBrcccccpczBCn-m个非基变量xj在目标函数中的系数为：jjBjjcpcz1BC因此，当非基变量xk的系数ck 变化成为ck=ck+ 时，基变量基变量的检验
4、数仍为的检验数仍为0。在在最优解中只会影响这个非最优解中只会影响这个非基变量基变量XK的的检检验数，验数，其他非基变量的检验数不会变化。其他非基变量的检验数不会变化。 针对目标函数极大化的线性规划问题针对目标函数极大化的线性规划问题：如如果变化后的果变化后的xk的检验数仍然为非负，则原来的检验数仍然为非负，则原来的最优基仍保持为最优基。的最优基仍保持为最优基。如如果变化后的果变化后的xk的检验数为负数，则原来的最的检验数为负数，则原来的最优基不再是最优基，新的最优基可以通过将优基不再是最优基，新的最优基可以通过将xk进进基，并进行后续的单纯形迭代，得到新的最优基基，并进行后续的单纯形迭代，得到
5、新的最优基和最优解。和最优解。 minz=-2x1+x2-x3s.t.x1+x2+x36-x1+2x24x1,x2,x30目标函数目标函数约束条件：约束条件：求求c2在什么范围内变化，原来的最优基保持不变；在什么范围内变化，原来的最优基保持不变；当当c2=-3时，最优基是否变化，如果变化，求新的时，最优基是否变化，如果变化，求新的最优基和最优解。最优基和最优解。 线性规划问题线性规划问题例题例题例例1 首先用单纯形法得到原问题的最优单纯形表，C-21-100zx1x2x3x4x5RHSz10-3-1-20-12x1-2111106x50031111002) 3012()(22222512122
6、cccycyccz22c由于由于x2在最优单纯形表中是非基变量，因此只影响它本身的检验数在最优单纯形表中是非基变量，因此只影响它本身的检验数 得到 C-2c2-100zx1x2x3x4x5RHSCBz10-2-c2-1-20-12-2x101111060 x500311110由于最优解由于最优解XB=B-1b以及最优解的目标函数值以及最优解的目标函数值z=CBB-1b与非基变量在目标函数中的系数与非基变量在目标函数中的系数CN无无关，关，其他其他变量在目标函数中的系数都不变变量在目标函数中的系数都不变。x2在在目标函数中的系数从原来的值目标函数中的系数从原来的值1减少到减少到 -2时，时，最最
7、优基保持不变优基保持不变。相应相应的单纯形表如下：的单纯形表如下： 当当c2=-3时，已经超出保持最优基不变的范围，因此单纯形时，已经超出保持最优基不变的范围，因此单纯形表不再是最优单纯形表。将表不再是最优单纯形表。将c2=-3代入单纯形表，得到以下代入单纯形表，得到以下单纯形表：单纯形表：zx1x2x3x4x5RHSz101-1-20-12x1-2111106x500311110 x2进基X5离基 得到新的最优解：得到新的最优解：x1=8/3，x2=10/3，x3=0，x4=0，x5=0，min z=-46/3zx1x2x3x4x5RHSz100-4/3-7/3-1/3-46/3x1-210
8、2/32/3-1/38/3x2-3011/31/31/310/3得到最终单纯形表：得到最终单纯形表： 例例2：在下面线性规划问题中，分析在下面线性规划问题中，分析c1在什么范围内在什么范围内变化时，原问题的最优基不变。变化时，原问题的最优基不变。maxz=2x1+x2s.t.5x2156x1+2x224X1+x25x1,x2,0 首首先得到以上问题的最优单纯形表：先得到以上问题的最优单纯形表：C21000zx1x2x3x4x5RHSz10001/41/217/2x300015/4-15/215/2x121001/4-1/27/2x21010-1/43/23/2当当c1=c1+ 时，相时，相应的
9、单纯形表为应的单纯形表为：C2+ 1000Zx1x2x3x4x5RHSz10001/4+ /41/2- /217/2+7 /2x300015/4-15/215/2x12+ 1001/4-1/27/2x21010-1/43/23/2 C2+ 1000Zx1x2x3x4x5RHSz10001/4+ /41/2- /217/2+7 /2x300015/4-15/215/2x12+ 1001/4-1/27/2x21010-1/43/23/2为了表中解为最优为了表中解为最优，应有应有，因此因此 -1 1，即当，即当1 c1 3时，最优基保持不变。时，最优基保持不变。当当c1的变化超出以上范围时，至少会使
10、一个检验数的变化超出以上范围时，至少会使一个检验数zj-cj0，用单纯形法继续运行，就可以得到新的最优基和最优解。用单纯形法继续运行，就可以得到新的最优基和最优解。 2 2、常数项的灵敏度分析、常数项的灵敏度分析当右边常数向量当右边常数向量b发生变化，成为发生变化，成为b时，对变量的检时，对变量的检验数验数jjTBjjcpcz1BC没有影响，而单纯形表中的右边常数将变成没有影响，而单纯形表中的右边常数将变成 1 bBb。 即右边常数向量的变化只会影响最优基的原始可行即右边常数向量的变化只会影响最优基的原始可行性而不会影响其对偶可行性。性而不会影响其对偶可行性。当变化以后的当变化以后的0bBb
11、1 例例3对以下线性规划问题中第一个约束对以下线性规划问题中第一个约束右边常数右边常数b1=9进行灵敏度分析。进行灵敏度分析。maxz=-x1-x2+4x3s.t.x1+x2+2x39x1+x2-x32-x1+x2+x34x1,x2,x30zx1x2x3x4x5x6RHSz104010217x1-11-1/301/30-2/31/3x500200116x3402/311/301/313/3先求得最优单纯形表：先求得最优单纯形表： 由于初始单纯形表中，约束矩阵中松弛变量由于初始单纯形表中，约束矩阵中松弛变量x4，x5，x6的系数构成一个的系数构成一个，因此最优单纯形表中松弛变量在约束矩阵中的系数
12、就是最优基，因此最优单纯形表中松弛变量在约束矩阵中的系数就是最优基的的逆矩阵逆矩阵。即。即3/103/11103/203/11B3/1363/14293/103/11103/203/11bBb当当b1=b1+ =9+ 时，时，最后一张单纯形表中最后一张单纯形表中的右边常数将成为的右边常数将成为 3/ 13/1363/ 13/ 14293/ 103/ 11103/ 203/ 1 1 bBb这时，最后单纯形表这时，最后单纯形表中目标函数的值也将中目标函数的值也将发生变化，成为：发生变化，成为： 17429201 1 bBCBz 单纯形表成单纯形表成为为:c-1-14000zx1x2x3x4x5x6
13、RHSZ104010217+x1-11-1/301/30-2/31/3+1/3x500200116x3402/311/301/313/3+1/3由此可以看出，当第一个约束的右边常数由此可以看出，当第一个约束的右边常数b1变化变化 时，时，新的单纯形表的新的单纯形表的RHS列就是原来最优单纯形表的列就是原来最优单纯形表的RHS列加上第一个松弛变量列加上第一个松弛变量x4在原来单纯形表中对在原来单纯形表中对应的列与应的列与 的乘积。的乘积。 根据这个规则，容易得到第二个约束的右边常数根据这个规则，容易得到第二个约束的右边常数b2=2变为变为b2=2+ 时的单纯形表：时的单纯形表：zx1x2x3x4
14、x5x6RHSz104010217x1-11-1/301/30-2/31/3x500200116+x3402/311/301/313/3以及第三个约束的右边常数以及第三个约束的右边常数b3=4变为变为b3=4+ 时的单纯形表：时的单纯形表：zx1x2x3x4x5x6RHSZ104010217+2 X1-11-1/301/30-2/31/3-2/3 X500200116+ X3402/311/301/313/3+1/3 c-1-14000zx1x2x3x4x5x6RHSZ104010217+2X1-11-1/301/30-2/31/3-2/3X500200116+X3402/311/301/31
15、3/3+1/3这样就可以分别求出在保持原来最优基原始可行性条件下，这样就可以分别求出在保持原来最优基原始可行性条件下，b1=9，b2=2，b3=4的变化范围。的变化范围。对于对于b1=9+ ，由第一张单纯形表约束条件的原始可行条件，由第一张单纯形表约束条件的原始可行条件可以得到，当可以得到，当03/13/1303/13/1，推出，推出 113即即-1，b1=b1+8时，原来的最优基仍为原始可行基。时，原来的最优基仍为原始可行基。 当当b1的变化超过以上范围，例如的变化超过以上范围，例如b1=7，即，即 =b1-b1=7-9=-2时，单纯形表成为：时，单纯形表成为：-1-14000zx1x2x3
16、x4x5x6RHSz104010215x1-11-1/301/30-2/3-1/3x500200116x3402/311/301/311/3x6进基X1离基zx1x2x3x4x5x6RHSz133020014x60-3/21/20-1/2011/2x503/23/201/21011/2x341/21/211/2007/2得到新的最优解为：得到新的最优解为：（x1,x2,x3,x4,x5,x6）=（0,0,7/2,0,11/2,1/2）max z=14。 3 3、增加一个新的变量、增加一个新的变量当前最优基是当前最优基是B。设新增加的变量。设新增加的变量xj在目标函数中的系数为在目标函数中的系数
17、为cj，在约束中的系数向量是，在约束中的系数向量是aj，计算，计算jjp1 BYjjBjjcpcz1BC，在原单纯形表中增加一个新的变量以及新的一列，将以在原单纯形表中增加一个新的变量以及新的一列，将以上系数置于原单纯形表中，构成新的单纯形表上系数置于原单纯形表中，构成新的单纯形表。若若新变量的检验数新变量的检验数zj-cj0，则原来的基仍为最优基，原，则原来的基仍为最优基，原来的基变量以及基变量的值保持不变，新的变量来的基变量以及基变量的值保持不变，新的变量xj=0是是非基变量。否则非基变量。否则xj进基，用单纯形法继续运行，直至获进基，用单纯形法继续运行，直至获得新的最优基和最优解。得新的
18、最优基和最优解。 maxz=2x1-x2+x3s.t.x1+x2+x36-x1+2x24x1,x2,x30在在上上面的线性规划模型中面的线性规划模型中，增加一个新的变量，增加一个新的变量x6，它在目标函数中的系数它在目标函数中的系数c6=1，在约束条件中的系，在约束条件中的系数向量为数向量为 216p，求新的最优基和最优解，求新的最优基和最优解。例例4 列出原问题的最优单纯形表：列出原问题的最优单纯形表：c2-1100zx1x2x3x4x5RHSz10312012x12111106x500311110从中可以看出，从中可以看出， 1101,02151BCccB3121)0 , 2(66166c
19、pczBBC 11211101616pBY 新的单纯形表为：新的单纯形表为：2-11000zx1x2x3x4x5x6RHSz103120-312x1211110-16x5003111110 x6进基进基x5离基，得到下一个单纯形离基，得到下一个单纯形表表:zx1x2x3x4x5x6RHSz1012453042x1214221016x6103111110得到新的最优解得到新的最优解为为:(x1,x2,x3,x4,x5,x6)T=（16,0,0,0,0,10）T，max z=42。 4 4、增加一个新的约束、增加一个新的约束增加一个新的约束以后，如果原来的最优解满足新的约束，则增加一个新的约束以后
20、，如果原来的最优解满足新的约束，则原来的最优解仍是新问题的最优解，否则，最优解将发生变化。原来的最优解仍是新问题的最优解，否则，最优解将发生变化。例例5maxz=2x1-x2+x3s.t.x1+x2+x36-x1+2x24x1,x2,x30最优单纯形表最优单纯形表为为:Zx1x2x3x4x5RHSz10312012x12111106x500311110现现在，在，增增加一个约束加一个约束-x1+2x32，试分析最优解的变化。，试分析最优解的变化。 先将原问题最优解变量值代入，因有先将原问题最优解变量值代入，因有-6+20=-6 2 0=-60可以断定这种设备能力没有剩余，即 也就是xn+i=0
21、，从而同样满足互补松弛条件xn+iyi=0。in1jjijbxa 对偶问题约束的左边 表示生产每单位j产品（j=1,2,n）所耗用的各种设备能力应能产生的利润，称为j种产品的机会成本。 若某种产品的机会成本高于这种产品的利润，即), 2 , 1(1njyamiiij), 2 , 1(1njcyajmiiij互补松弛条件的经济解释互补松弛条件的经济解释 则在最优解中这种产品一定不会安排生产，即xj=0，从而满足互补松弛条件xjym+j=0 如果在最优解中第j种产品投入生产，即xj0，这种产品的机会成本和利润必定相等即 因而互补松弛条件xjym+j=0成立。), 2 , 1(01njcyayjmi
22、iijjm弱对偶性的经济解释弱对偶性的经济解释 对于最大利润问题，由弱对偶性可知 CXYAXYb 左边：是由于某些产品的利润率和机会成本不相等引起的，即CYA。当取得最优解时，由于互补松弛条件的作用，凡机会成本和利润率不相等的产品都将不安排生产，因而使得不等式成为等式。 右边：是由于某些设备的实际耗用小于设备的实际能力引起的，即AXb同样由于互补松弛条件，实际耗用和能力不等的这些设备，影子价格都等于零，从而使右边的不等式也成为等式。 当原始和对偶问题都取得最优解时 CX=YAX=Yb对偶关系的经济解释案例对偶关系的经济解释案例 例2-34 生产计划问题 某工厂拥有A、B、C三种类型的设备，生产
23、甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如表2-1所示，试用线性规划制订使总利润最大的生产计划。产品甲产品甲 产品乙产品乙 产品丙产品丙 产品丁产品丁1.51.01.52000 8000 5000设备设备A 设备设备B 设备设备C单位产品消单位产品消耗的机时数耗的机时数产品产品设备能力设备能力（小时）（小时）利润利润（元（元/ /件）件） 5.24 7.30 8.34 4.181.05.03.02.41.03.51.03.51.0对偶关系的经济解释案例对偶关系的经济解释案例 设变量xi为第i种产品的生产件数（i1，2，3，4）
24、，目标函数z为相应的生产计划可以获得的总利润。06.1273782.584, 03,15002,12.29410,50000 . 15 . 30 . 35 . 180005 . 30 . 10 . 50 . 120000 . 14 . 20 . 15 . 1. .18. 434. 830. 724. 5max43214321432143214321zxxxxxxxxxxxxxxxxxxxxtsxxxxz 分析最优解中利润率最高的产品丙不安排生产的原因： 求解该问题的对偶问题得到三种设备的影子价格分别为： y1=1.9535，y2=0.2423，y3=1.3792 这说明三种设备在最优生产计划下
25、，能力都没有剩余，并且第一种设备能力最为紧缺。对偶关系的经济解释案例对偶关系的经济解释案例 分别计算四种产品的机会成本，得到： 产品甲： 1.5y1+1.0y2+1.5y3=5.24=C1 产品乙：7.30=C2 产品丙：9.75C3 产品丁：4.18=C4311iiiya对偶关系的经济解释案例对偶关系的经济解释案例 例2-35设利润最大问题如表所示：甲产品乙产品加工能力A设备2212B设备128C设备4016D设备0412利润（千元/件）23对偶关系的经济解释案例对偶关系的经济解释案例 利润最大问题的线性规划模型为 xxz2132max jx x x xx xxtsj2 , 10124164
26、821222. .212121对偶关系的经济解释案例对偶关系的经济解释案例 引入的松弛变量表示资源的剩余量，即设备未消耗的工时数。 求得以上问题的最优生产计划为： x1=4（件），x2=2（件） ，最大利润z=14（千元），A、B、C、D四种设备的剩余工时数：x3=0, x4=0，x5=0，x6=4对偶关系的经济解释案例对偶关系的经济解释案例 由对偶问题进一步分析甲产品 乙产品设备最大工时数工时剩余影子价格（万元/吨）A设备221200B设备12803/2C设备401601/8D设备0412 40利润(千元/件)23机会成本(千元/件)23 机会成本利润(千元/件) 00 产品产量(件)42由此可以清楚地看出，资源剩余量和影子价格之间以及“机会成本利润率”和产品产量之间的互补松弛关系（表中箭头表示“一个变量大于零，导致另一个变量等于零”的互补松弛关系）。对偶关系的经济解释案例对偶关系的经济解释案例
