第6章单纯形法的灵敏度与对偶

1、中华管理学习网 1 第六章第六章 单纯形法的灵敏度分析与对偶单纯形法的灵敏度分析与对偶 1 1单纯形表的灵敏度分析单纯形表的灵敏度分析 2 2线性规划的对偶问题线性规划的对偶问题 3 3对偶规划的基本性质对偶规划的基本性质 4 4对偶单纯形法对偶单纯形法 中华管理学习网 2 1 1单纯形表的灵敏度分析单纯形表的灵敏度分析 一、目标函数中变量Ck系数灵敏度分析 1.在最终的单纯形表里，X k是非基变量 由于约束方程系数增广矩阵在迭代中只是其本身的行的初等变换与Ck没有任何关系， 所以当Ck变成Ck+ Ck时，在最终单纯形表中其系数的增广矩阵不变，又因为Xk是非 基变量，所以基变量的目标函数的系数

2、不变，即CB不变，可知Zk也不变，只是Ck变 成了Ck+ Ck。这时 K= Ck-Zk就变成了Ck+ Ck- Zk= K+ Ck。要使原来的最优解 仍为最优解，只要 K+ Ck0即可，也就是Ck的增量 Ck- K。 2.在最终的单纯形表中， X k是基变量 当Ck变成Ck+ Ck时，最终单纯形表中约束方程的增广矩阵不变，但是基变量的目 标函数的系数CB变了，则ZJ(J=1,2,.,N)一般也变了，不妨设CB=(CB1, CB2。, Ck, ， CBm),当CB变成=(CB1, CB2。,Ck+ Ck,CBm),则： ZJ=(CB1, CB2。, Ck,，CBm)(a1j , a2j , aKj

3、 , amj) ZJ=(CB1, CB2。, Ck+ Ck,，CBm)(a1j , a2j , aKj , amj) = ZJ + Ck aKj T T 中华管理学习网 3 1 1单纯形表的灵敏度分析单纯形表的灵敏度分析 根据上式可知 检验数 J (J=1,2,.,M)变成了 J,有 J=CJ-ZJ= J+ CK aKj 。要使最优解不变，只要当J K时， J 0，就可求出 的取值范围，也就是使得第K个约束条件的对偶价格不变的 bk的变化范围。 ， -1-1-1 B XB .(bb)BbBb 。 k b mkk 3kk 2kk 1kk 1-2 1 k db . db db db bB, . D

4、则 mk k k d d d mkk 2kk 1kk 2 1 BB db . db db . XX Bm B B X X X 有新的最优解为 中华管理学习网 12 1 1单纯形表的灵敏度分析单纯形表的灵敏度分析 下面我们仍以第二章例1在最终单纯形表上对bj 进行灵敏度分析。 最终单纯形表如下所示： Bk k X00b Max|0bMin|0 BiBi ikik ikik xx dd dd 要使也就是各个分量均不小于 ，用一个数学式子来表示 的 允许变化范围是 迭代次数基变量CB X1 X2 S1 S2 S3 b 50 100 0 0 0 2 X1501 0 1 0 -150 S200 0 -2

5、 1 150 X21000 1 0 0 1250 ZJ 50 100 50 0 5027500 CJ -ZJ0 0 -50 0 -50 中华管理学习网 13 1 1单纯形表的灵敏度分析单纯形表的灵敏度分析 我们对b1进行灵敏度分析，因为在第一个约束方程中含有松弛变量S1, 实际意义可以描述为：当设备台时数的对偶价格不变，都为每设备台 时数在250与325之间变化，则设备台时数的对偶价格不变，都为每台设备 台时50元。 的第一列。就是），纯形表中的系数列（所以松弛变量在最终单 -1T B021 变。约束条件的对偶价格不 第一个即故有当而 可以因为 325bb250,25b50,250|Min 5

6、00|Max,50X,50X, 02d, 01d 11 1 1 1 212111 i i Bi i i Bi d d x d d x 中华管理学习网 14 1 1单纯形表的灵敏度分析单纯形表的灵敏度分析 三、约束方程系数矩阵A灵敏度分析 下面分两种情况讨论 1.在初始单纯形表上的变量Xk的系数列Pk改变为Pk经过迭代后，在最终单 纯形表上Xk是非基变量。由于单纯形表的迭代是约束方程的增广矩阵的行变 换，Pk变成Pk仅仅影响最终单纯形表上第k列数据，包括Xk的系数列、Zk以 及 k，这时最终单纯形表上的Xk的系数列就变成了B-1Pj,而Zk就变成CBB-1Pk， 新的检验数 k=Ck-CBB-1

7、Pk。若 k0，则原最优解仍然为最优解。若 k 0， 则继续进行迭代以求出最优。 例例 以第二章例1为基础，设该厂除了生产，种产品外，现在试制成一个新产 品，已知生产产品,每件需要设备2台时，并消耗A原料0.5公斤。B原料 1.5公斤，获利150元，问该厂应该生产该产品多少？ 解：这是一个增加新变量的问题。我们可以把它认为是一个改变变量X3在初始 表上的系数列的问题， 中华管理学习网 15 1 1单纯形表的灵敏度分析单纯形表的灵敏度分析 接上页 ., 0, 25,150255 . 11005 . 050, 5 . 1 2 5 . 0 5 . 1 5 . 0 2 1 1 1 0 1 0 0 2

8、1 PB ）1.5，0.5，2（ ）1.5，0.5，2（）0，0，0（ 6 66666 1 - 33 3 TT 见表题的最优解可知原最优解就是新问这时新变量如下表所示 这时 就变成了上是非基变量，在最终表之后的第六列上，显然把它放在 的一列，上添上新的一列变量，。这样在原来的最终表变成从 ZCZ XS X 迭代次数基变量CBX1 X2 S1 S2 S3 X3 b 50 100 0 0 0 150 X1501 0 1 0 -1 0.550 S200 0 -2 1 1 -250 X21000 1 0 0 1 1.5250 ZJ50 100 50 0 50 17527500 CJ -ZJ0 0 -5

9、0 0 -50 -25 中华管理学习网 16 1 1单纯形表的灵敏度分析单纯形表的灵敏度分析 例 假设上例题中产品的工艺结构有了改进，这时生产1件产品需要 使用1.5台设备 ，消耗原料A为2千克，原料B为1千克，每件产品的 利润为160元，问该厂的生产计划是否要修改。 解：首先求出X3在最终表上的系数列 6 1P B 填入下表,35 ,125 1 0 0.5 (50,0,100), 1 0 5 . 0 1 2 5 . 1 1 1 1 0 1 0 0 2 1 PB 66 66 1 ZC z j 迭代 次数 基变量CBX1 X2 S1 S2 S3 X3 b 50 100 0 0 0 150 2 X

10、1501 0 1 0 -1 0.55050/0.5 S200 0 -2 1 1 050 X21000 1 0 0 1 1250250/1 ZJ50 100 50 0 50 12527500 CJ -ZJ0 0 -50 0 -50 35 中华管理学习网 17 1 1单纯形表的灵敏度分析单纯形表的灵敏度分析 接下来又可以有新的迭代S3进基， 63 1 0,3,X X 由于可知此解不是最优解 我们要进行第 次迭代 选为入基变量， 为出基变量 迭代 次数 基变量CBX1 X2 S1 S2 S3 X3 b 50 100 0 0 0 150 3 X31602 0 2 0 -2 1100- S200 0 -

11、2 1 1 05050/1 X2100-20 1 -2 0 3 0150250/3 ZJ120 100 120 0 -20 16031000 CJ -ZJ-70 0 -120 0 20 0 中华管理学习网 18 1 1单纯形表的灵敏度分析单纯形表的灵敏度分析 接上页 可知此规模的最优解X1=0, X2=0, S1=0, S2=0, S3=50, X3=200,此时， 最大目标函数为32000元。也就是说，该厂的新的生产计划为不生产、 产品，生产产品200件, 可获得最大利润32000元。 迭代 次数 基变量CBX1 X2 S1 S2 S3 X3 b 50 100 0 0 0 150 4 X31

12、602 0 2 0 -2 1200- S300 0 -2 1 1 05050/1 X2100-2 1 4 -3 0 00250/3 ZJ120 100 80 20 0 16032000 CJ -ZJ-70 0 -80 -20 0 0 中华管理学习网 19 1 1单纯形表的灵敏度分析单纯形表的灵敏度分析 2.在初始表上的变量XK的系数PK改变为PK，经 过迭代后，在最终表上XK是基变量，在这种情况下 原最优解的可行性和最优解都可能被破坏，问题十分 复杂，一般不去修改原表而是直接计算。 中华管理学习网 20 1 1单纯形表的灵敏度分析单纯形表的灵敏度分析 四、增加一个约束条件的灵敏度分析 在原线性

13、规划中增加一个约束条件时,先将原问 题的最优解的变量值代入新增的约束条件，如满足 则说明新增的条件没有起到限制作用，故原最优解 不变，否则将新增的约束添入原最终单纯形表上进 一步求解。 下面仍以第三章例1为例来加以说明。 例：假如该工厂除了在设备台时，原材料A、B 上对该厂的生产有限制外，还有电力供应上的限制。 最高供应电量为5000度，而生产一个产品需要用 电10度，而生产一个产品需要用电30度。试分析 此时该厂获得最大利润的生产计划？ 中华管理学习网 21 1 1单纯形表的灵敏度分析单纯形表的灵敏度分析 1 x 2 x解：先将原问题的最优解=50=50，=250代入用电量的约束条件 得：1

14、050+30250=500+75005000,所以原题的最优解不是本题的最优解。 在用电量的约束条件中加入松驰变量S4后得： 124 10 x +30 x +s =5000 把这个约束条件加入到原最终单纯形表上，其中S4为基变量，得表如下： B C 1 x 2 x 1 s 2 s 3 s 4 s 1 x 2 s 2 x 4 s j z 迭代迭代 次数次数 基变量基变量b b比值比值 50501001000 00 00 00 0 50501 10 01 10 0-1-10 05050 0 00 00 0-2-21 11 10 05050 1001000 01 10 00 01 10 025025

15、0 0 0101030300 00 00 01 150005000 505010010050500 050500 027502750 0 0 0 00 0-50-500 0-50-500 0 jjj cz 12 10305000 xx 中华管理学习网 22 1 1单纯形表的灵敏度分析单纯形表的灵敏度分析 在上表中的X1，X2不是单位向量，故进行行的线性变换，得 迭代迭代 次数次数 基变量基变量C CB Bx x1 1x x2 2s s1 1s s2 2s s3 3s s4 4b b比值比值 50501001000 00 00 00 0 x x1 150501 10 01 10 0-1-10 0

16、5050 s s2 20 00 00 0-2-21 11 10 05050 x x2 21001000 01 10 00 01 10 0250250 s s4 40 00 00 0-10-100 0-20-201 1-3000-3000 z zj j505010010050500 050500 02750027500 0 00 0-50-500 0-50-500 0 把上表中的S4行的约束可以写为： 134 10203000sss 上式两边乘以（-1），再加上人工变量a1得： 1341 10203000sssa 用上式替换上表中的S4行，得下表： jjj cz 中华管理学习网 23 1 1单纯

17、形表的灵敏度分析单纯形表的灵敏度分析 迭代迭代 次数次数 基变基变 量量 x x1 1x x2 2s s1 1s s2 2s s3 3s s4 4a a1 1b b比值比值 50501001000 00 00 00 0-M-M x x1 150501 10 01 10 0-1-10 00 05050 s s2 20 00 00 0-2-21 1(1)(1)0 00 05050 x x2 21001000 01 10 00 01 10 00 0250250 s s4 4-M-M0 00 0-10-100 0-20-201 11 130003000 z zj j505010010050-10M50

18、-10M0 050-20M50-20M0 0-M-M 0 00 010M-5010M-500 020M-5020M-500 00 0 x x1 150501 10 0-1-11 10 00 00 0100100 s s3 30 00 00 0-2-21 11 10 00 05050 x x2 21001000 01 12 2-1-10 00 00 0200200 s s4 4-M-M0 00 05050-20-200 0-1-11 120002000 z zj j5050100100150-50M150-50M20M-5020M-500 0M M-M-M 0 050M-15050M-15050

19、-20M50-20M0 0-M-M0 0 x x1 150501 10 00 03/53/50 0-1/50-1/501/501/50140140 s s3 30 00 00 00 01/51/51 1-2/50-2/502/502/50130130 x x2 21001000 01 10 0-1/5-1/50 02/502/50-2/50-2/50120120 s s4 40 00 00 01 1-2/5-2/50 0-1/50-1/501/501/504040 z zj j50501001000 010100 03 3-3-3 0 00 0-10-100 0-3-3-M+3-M+3 jjj

20、 cz jjj cz jjj cz 中华管理学习网 24 1 1单纯形表的灵敏度分析单纯形表的灵敏度分析 由上表可知，最优解为： 121231 1401200 xxsssa 即该工厂在添加了用电限量以后的最优生产计划为 产品生产140件，产品生产120件。 中华管理学习网 25 每一个线性规划问题，都存在每一个与它密切相关的线性规划的问题，我们称其为原问题， 另一个为对偶问题。 例题例题1 1 某工厂在计划期内安排、两种产品，生产单位产品所需设备A、B、C台时如表所示 该工厂每生产一单位产品 可获利50元，每生产一单位产品可获利100元，问工厂应分别 生产多少 产品和产品，才能使工厂获利最多？

21、 解：设 为产品 的计划产量， 为产品的计划产量，则有 目标函数： Max z z=50 +100 约束条件： ， 资源限量 设备 A 1 1 300 台时 设备 B 2 1 400 台时 设备 C 0 1 250 台时 1 x 2 x 300 21 xx 4002 21 xx 2 x 250 2 x 1 x 0 2 2 线性规划的对偶问题线性规划的对偶问题 中华管理学习网 26 现在我们从另一个角度来考虑这个问题。假如有另外一个工厂要求租用该厂的设备A、B、 C，那么该厂的厂长应该如何来确定合理的租金呢？ 设 分别为设备A、B、C的每台时的租金。为了叙述方便，这里把租金定义为扣 除成本后的利

22、润。作为出租者来说，把生产单位 产品所需各设备的台时各总租金不应低于 原利润50元，即 ，否则就不出租还是用于生产 产品以获利50元；同样把 生产一单位 产品所需各设备的台时的总租金也不应当低于原利润100元， 即 ，否则这些设备台时就不出租，还是用于生产 产品以获利100元。但对于租用者来说，他要 求在满足上述要求的前提下，也就是在出租者愿意出租的前提下尽量要求全部设备台时的总 租金越低越好，即min ，这样我们得到了该问题的数学模型： 目标函数： 约束条件： 这样从两个不同的角度来考虑同一个工厂的最大利润（最小租金）的问题，所建立起来 的两个线性模型就是一对对偶问题，其中一个叫做原问题原问

23、题，而另外一个叫对偶问题对偶问题。 3, 21, yyy 321 250400300minyyyf 502 21 yy 100 321 yyy 321 250400300yyy 0, 100 502 321 321 21 yyy yyy yy 2 2 线性规划的对偶问题线性规划的对偶问题 中华管理学习网 27 如果我们把求目标函数最大值的线性规划问题看成原问题，则求目标函数最小值的线性 规划问题看成对偶问题。下面来研究这两个问题在数学模型上的关系。 1 求目标函数最大值的线性规划问题中有n 个变量 m个约束条件，它的约束条件都是小于 等于不等式。而其对偶则是求目标函数为最小值的线性规划问题，有

24、m个变量n个约束条件， 其约束条件都为大于等于不等式。 2 原问题的目标函数中的变量系数为对偶问题中的约束条件的右边常数项，并且原问题的 目标函数中的第i个变量的系数就等于对偶问题中的第i个约束条件的右边常数项。 3 原问题的约束条件的右边常数项为对偶问题的目标函数中的变量的系数。并且原问题的 第i个约束条件的右边常数项就等于零对偶问题的目标函数中的第i个变量的系数。 4 对偶问题的约束条件的系数矩阵A是原问题约束矩阵的转置。 设 A= 则 mnmm n aaa aaa . . . 21 11211 2 2 线性规划的对偶问题线性规划的对偶问题 mnnn m T aaa aaa A 21 12

25、111 中华管理学习网 28 如果我们用矩阵形式来表示，则有原问题： 其中A是 矩阵m*n，该问题有m个约束条件n个变量，x= ,b= , c= 对偶问题： 其中 是A的转置， 是b的转置, 是c的转置, y= 现在我们用单纯形法求对偶问题的解。 0 , ,max x bAx cxz ).,.,( 21n ccc T m bbb),.,( 21 T A T b T C T m yyy),.,( 21 0 . .min y cyA ybf TT T 2 2 线性规划的对偶问题线性规划的对偶问题 T n xxx, 21 中华管理学习网 29 加上剩余变量 和人工变量 ，把此问题化成标准型如下： 把

26、上述数据填入单纯形表计算。 21,s s 1 a 1321 500400300)max(Mayyyf 0, 100 502 121321 2321 1121 assyyy syyy asyy 2 2 线性规划的对偶问题线性规划的对偶问题 中华管理学习网 30 迭代 变量 基变量 b -300-400-25000-M 1 -M1 0 -1 0 15050/2 -250 1 1 1 0 -1 0 100100/1 -M-250-2M- 250 -250M250-M-50M-25000 M-250 2M- 150 0-M-2500 2 -4001/210-1/201/225 -2501/2011/2

27、-1-1/275 -325-400-25075250-75-28750 2500-75-250-M+75 3 -300120-10150 -2500-111-1-150 -300-350-25050250-50-27500 0-500-50-250-M+50 b c 1 y 2 y 3 y 2 s 1 s 1 a 1 a 3 y j z jj zc 2 y 3 y 2/1 75 2/1 25 j z jj zc 1 y 3 y j z jj zc 2 2 线性规划的对偶问题线性规划的对偶问题 中华管理学习网 31 由上表，最优解： =50， -f 的最大值为-27500，即目标函数f的最大值为

28、f=27500元。 从上面可知租金：A设备为50元，B设备为0元，C设备为50元。这样把工 厂的所有设备出租可共得租金27500元。对出租者来说这租金是出租者愿意出 租设备的最小费用，因为这是目 标函数的最小值。 通过比较，我们发现：对偶问题的最优解即最佳租金恰好等于原问题各种 设备的对偶价格，这在道理上也能讲得通。 对于两个有对偶关系的线性规划 的问题，我们只要求得了其中一个最优解，就可以从这个问题的对偶价格而 求得其对偶问题的最优解，知道其中一个最优值也就找到了其对偶问题的最 优值，因为这两个最优值相等。 1 y0, 0, 0,50, 0 12132 assyy 2 2 线性规划的对偶问题

29、线性规划的对偶问题 中华管理学习网 32 下面来阐述如何写出一个线性规划问题的对偶问题。为了 便于阐述，我们不妨以下面的线性规划为例，写出它的对偶 问题。 S.T. 321 643maxxxxz 0, ,20035 ,10046 ,440632 321 321 321 321 xxx xxx xxx xxx 2 2 线性规划的对偶问题线性规划的对偶问题 中华管理学习网 33 这是一个求最大值的线性规划问题，为了写出它的对偶问题，我们不 妨把它的约束条件都变换成取小于号的不等式。显然第一个约束条件已符 合要求，不要做任何变动，而第二个约束条件，我们只要两边都乘以（- 1），使不等号方向改变即可，

30、得 这样第二个约束条件也就符合要求。对于第三个约束条件，我们可以 用小于等于和大于等于两个约束条件来替代它。即有 显然，这两个约束条件与原来第三个约束条件是等价的，我们再把其 中的 两边都乘以（-1），得 10046 321 xxx 20035 20035 321 321 xxx xxx 20035 321 xxx 20035 321 xxx 2 2 线性规划的对偶问题线性规划的对偶问题 中华管理学习网 34 通过上面的一些变换，我们得到了一个和原线性规划等价的线性规划 问题： s.t. 321 643maxxxxz 0, 20035 20035 ,10046 ,440632 321 321

31、321 321 321 xxx xxx xxx xxx xxx 2 2 线性规划的对偶问题线性规划的对偶问题 中华管理学习网 35 这个求最大值的线性规划问题的约束条件都取小于等于号，我们马 上可以写出其对偶问题： s.t. 3 3 21 200200100440minyyyyf , 0, , 66 , 43343 , 35562 3 3 21 3 3 21 3 3 21 3 3 21 yyyy yyyy yyyy yyyy 2 2 线性规划的对偶问题线性规划的对偶问题 中华管理学习网 36 这里 和 一样都是不同的决策变量，为了表示这两个 决策变量都来源于原问题的第三个约束条件，记为 。 因

32、为在该对偶问题中 和 的系数只相差一个符号，我们可以把 上面的对偶问题化为： s.t. 3 3 , yy 21, y y 3 y3 y )(200100440min3 3 21 yyyyf , 0, , 6)(6 , 4)(343 , 3)(562 3 3 21 3 3 21 3 3 21 3 3 21 yyyy yyyy yyyy yyyy 2 2 线性规划的对偶问题线性规划的对偶问题 3 3 , yy 中华管理学习网 37 进一步，我们可以令 ，这时当 时， ，当 时， 。这也就是说，尽管 但 的取值可以为正，可以为0， 可以为负，即 没有非负限制。 这样我们把原规划的对偶问题化为 s.t

33、. 没有限制。 对照原线性规划问题，我们可以知道： 当原线性规划问题的第i个约束条件取等号时，则其对偶问题的 i个决策变量没有非 负限制。 如果当原线性规划问题中的第 i个决策变量 没有非负限制时，我们也可以用 进行替换，这里 ， ，用类似的方法知道其对偶问题中第 i个 约束条件取等号。 3 3 3 yyy3 3 yy 0y 3 3 yy 0 3 y, 0, 3 3 yy 3 y 3 y 321 200100440minyyyf , 0, , 66 , 4343 , 3562 21 321 321 321 yy yyy yyy yyy 3 y i x ii i xxx 0 ix0 ix 2 2

34、 线性规划的对偶问题线性规划的对偶问题 中华管理学习网 38 另外，用大于等于0的两个决策变量之差来代替无非负限制的决策变 量也是求解含有无非负限制的决策变量的线性规划问题的一种方法。 原线性规划问题为： s.t. 无非负限制。 321 493minxxxf , 0, ,24035 ,6032 ,18032 21 21 321 321 xx xx xxx xxx 3 x 2 2 线性规划的对偶问题线性规划的对偶问题 中华管理学习网 39 3 3对偶规划的基本性质对偶规划的基本性质 对偶规划的基本性质对偶规划的基本性质 1对称性对称性。即对偶问题的对偶是原问题。 2弱对偶性弱对偶性。即对于原问题

35、（）和对偶问题（）的可 行解 都有C bT 。 由弱对偶性，可得出以下推论： （1）原问题任一可行解的目标函数值是其对偶问题目标函数值的 下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数 值的上界。 （2）如原问题有可行解且目标函数值无界（或具有无界解），则 其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界， 则其原问题无可行解（注意：本点性质的逆不成立，当对偶问题无 可行解时，其原问题或具有无界解或无可行解，反之亦然）。 （3）若原问题有可行解而其对偶问题无可行解，则原问题目标函 数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问 题的目标函数值无界。 YX , X Y 中华管理学习网 40 3 3对偶规划的基本性质对偶规划的基本性质 3最优性最优性。如果 是原问题()的可行解，