对偶理论DualityTheoryppt课件

1、对对 偶偶 理理 论论(Duality Theory)对偶问题的提出对偶问题的提出线性规划的对偶实际线性规划的对偶实际对偶问题的经济解释对偶问题的经济解释-影子价钱影子价钱 对对 偶偶 单单 纯纯 形形 法法 灵灵 敏敏 度度 分分 析析 对偶性是线性规划问题的最重要的内容之一。每一个线性对偶性是线性规划问题的最重要的内容之一。每一个线性规划规划 LP 必然有与之相伴而生的另一个线性规划问题，即必然有与之相伴而生的另一个线性规划问题，即任何一个求任何一个求 maxZ 的的LP都有一个求都有一个求 minZ 的的LP。其中的一个问。其中的一个问题叫题叫“原问题，记为原问题，记为“P，另一个称为，

2、另一个称为“对偶问题，记为对偶问题，记为“D。 例一、资源的合理利用例一、资源的合理利用问题问题 知资料如表所示，问应知资料如表所示，问应如何安排消费方案使得既如何安排消费方案使得既能充分利用现有资源有使能充分利用现有资源有使总利润最大？总利润最大？1810单件利润单件利润150设备设备51C100煤炭煤炭32B170钢材钢材25A资源限制资源限制乙乙甲甲单件单件 产产 耗费耗费 品品资源资源一、问一、问 题题 的的 提提 出出 0, 1505( 10032 170251810max2121212121xxxxxxxxxxZ原原问问题题）数数学学模模型型： 下面从另一个角度来讨论这个问题：下面

3、从另一个角度来讨论这个问题： 假定：该厂的决策者不是思索本人消费甲、乙两种假定：该厂的决策者不是思索本人消费甲、乙两种产品，而是将厂里的现有资源用于接受外来加工义务，产品，而是将厂里的现有资源用于接受外来加工义务，只收取加工费。试问该决策者应制定怎样的收费规范只收取加工费。试问该决策者应制定怎样的收费规范合理的？合理的？ 分析问题：分析问题： 1 1、每种资源收回的费用不能低于本人消费时的可获、每种资源收回的费用不能低于本人消费时的可获利润；利润； 2 2、定价又不能太高，要使对方可以接受。、定价又不能太高，要使对方可以接受。Wyyyyyyyyyyyyyyy 32132132132132115

4、0100170 0, 18532 1025 , 以以表表达达：就就目目标标而而言言，用用下下式式可可有有下下式式：单单价价，所所以以分分别别为为三三种种资资源源的的收收费费设设 普通而言，普通而言，W W 越大越好，但因需双方称心，故越大越好，但因需双方称心，故321150100170minyyyW 为最好。为最好。该问题的数学模型为：该问题的数学模型为： 0,185321025150100170min321321321321yyyyyyyyyyyyW（对对偶偶问问题题） 0, 1505( 10032 170251810max2121212121xxxxxxxxxxZ原原问问题题） 0, 18

5、532 1025150100170min321321321321yyyyyyyyyyyyW（对对偶偶问问题题）模型对比：模型对比： 例二、合理配料问题，其数学模型为：例二、合理配料问题，其数学模型为： 0 min 11jmiijijnjjjxbxaxcZ 假设工厂想把这假设工厂想把这m m 种营养成分分别制成一种营养丸种营养成分分别制成一种营养丸销售，问如何定价以保证总收入为最多？销售，问如何定价以保证总收入为最多？ 0 max11injjiijnjiiycyaybW（对对偶偶问问题题）有有下下列列式式子子：原问题原问题对偶问题对偶问题目标函数目标函数maxmin约束条件约束条件变量数量变量数

6、量约束条件个数约束条件个数约束条件个数约束条件个数变量数量变量数量例三、例三、23x1 x2 原问题原问题12y1 22128y2 12816y3401612y40412对偶问题对偶问题231 1、对称型对偶问题：知、对称型对偶问题：知 P P，写出，写出 D D。 0XbAX CXmaxZ P矩矩阵阵形形式式：二、线性规划的对偶实际二、线性规划的对偶实际一、对偶问题的方式一、对偶问题的方式 0YCYA min YbWD 例一、写出线性规划问题的对偶问题例一、写出线性规划问题的对偶问题 0,5643 7 32 532432max321321321321321xxxxxxxxxxxxxxxZ解：

7、首先将原式变形解：首先将原式变形 0,5 64 3 7 32532432max32132132132321xxxxxxxxxxxxxxxZ 留意：以后不强调等式右段项留意：以后不强调等式右段项 b0 b0，缘由在对偶，缘由在对偶单纯型表中只保证单纯型表中只保证 而不保证而不保证 ，故，故 b b可以是负数。可以是负数。0 j 01 bB 0,4675343232 532min 321321321321321yyyyyyyyyyyyyyyW对对偶偶问问题题：2 2、非对称型对偶问题、非对称型对偶问题 0XbAX max CXZP矩矩阵阵形形式式： 无无符符号号限限制制（无无约约束束） min Y

8、CYAYbWD例二、原问题例二、原问题 0,5643732532432max321321321321321xxxxxxxxxxxxxxxZ 无无约约束束解解：对对偶偶问问题题为为 ,467534 3 2 32 532min 321321321321321yyyyyyyyyyyyyyyW2 2、混合型对偶问题、混合型对偶问题 无无约约束束无无约约束束矩矩阵阵形形式式：23123232221211313212111332211213232131222212112121112211,0,0min,0maxYYYCAYAYAYCAYAYAYYbYbYbWDXXbXAXAbXAXAbXAXAXCXCZP

9、 例三、例三、 无无约约束束4321432142143214321, 0, 06 43 247 23 523 4 532maxxxxxxxxxxxxxxxxxxxxZ原问题原问题 无无约约束束32132131321321321,0,01 72 54 3332 2234 645minyyyyyyyyyyyyyyyyyW对偶问题对偶问题综上所述，其变换方式归纳如下：综上所述，其变换方式归纳如下：原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标函数目标函数 max目标函数目标函数 min约约束束条条件件m个个m个个变变量量0000= =无约束无约束变变量量n个个n

10、个个约约束束条条件件0000无约束无约束= =约束条件右端项约束条件右端项目标函数变量的系数目标函数变量的系数目标函数变量的系数目标函数变量的系数约束条件右端项约束条件右端项例四、线性规划问题如下：例四、线性规划问题如下： 无无约约束束、4321432431432143210 06 442 25 3 532min,xxx,xxxxxxxxxxxxxxxZ 无无约约束束对对偶偶问问题题：3213213213121321,0,01 4 5233 2 2 645maxyyyyyyyyyyyyyyyyW 无无约约束束、，4321432143243214321321321321321321 ,00247

11、32543 0432 4323min2 0,564 37 32532 422min.1xxxxxxxxxxxxxxxxxxxZ. xxxxxxxxxxxxxxxZ练习：练习： 无无约约束束答答案案：32132132132131321321321321321321y0,y0,y44y4y4y 37y3y3y 23yy 2y32y y 253max.2 0.yy0,y46y7y5y24yy 3y2y 3y2y 532max.1yyyWyyyWmin Z= - CXs.t. - AX- bX 01 1、对称性定理：对偶问题的对偶是原问题。、对称性定理：对偶问题的对偶是原问题。 min W= Y bs

12、.t. YA C Y 0max Z=C Xs.t. AXb X 0对偶的定义对偶的定义对偶的定义对偶的定义max W = -Ybs.t. YA C Y 0二、对偶问题的性质二、对偶问题的性质2 2、弱对偶原理弱对偶性：设、弱对偶原理弱对偶性：设 和和 分别是问题分别是问题P P和和D D的可行解，那么必有的可行解，那么必有_X_Y njmiiijjbyxcbYXC11_ ,即即 推论推论. .假设假设 和和 分别是问题分别是问题P P和和D D的可行的可行解，那么解，那么 是是D D的目的函数最小值的一个下界；的目的函数最小值的一个下界； 是是P P的目的函数最大值的一个上界。的目的函数最大值

13、的一个上界。_XCbY_X_Y 推论推论.在一对对偶问题在一对对偶问题P和和D中，假设其中，假设其中一个问题可行但目的函中一个问题可行但目的函数无界，那么另一个问题数无界，那么另一个问题不可行；反之不成立。这不可行；反之不成立。这也是对偶问题的无界性。也是对偶问题的无界性。无可行解无可行解关于无界性有如下结论：关于无界性有如下结论：问题无界问题无界无可行解无可行解问题无界问题无界对偶问题对偶问题原问题原问题 0,024 2max21212121xxxxxxxxZ无界无界如：如：原原 0,012 24min21212121yyyyyyyyW无可无可行解行解对对 推论推论.在一对对偶问题在一对对偶

14、问题P和和D中，假设一中，假设一个可行如个可行如P，而另一个不可行，如，而另一个不可行，如D，那么该，那么该可行的问题无界。可行的问题无界。例一、例一、 02023220322 432max41432143214321xxxxxxxxxxxxxZ试估计它们目的函数的界，并验证弱对偶性原理。试估计它们目的函数的界，并验证弱对偶性原理。P解：解： 0,04233322 212 2020min212121212121yyyyyyyyyyyyWD 由察看可知：由察看可知： =1.1.1.1T， =1.1，分别，分别是是P和和D的可行解。的可行解。Z=10 ，W=40，故有，故有 ，弱对偶定理成立。由推

15、论可知，弱对偶定理成立。由推论可知，W 的的最小值不能小于最小值不能小于10，Z 的最大值不能超越的最大值不能超越40。_XCbY_X_Y例二、知例二、知 0,1222max32132132121xxxxxxxxxxxZ : p 0,02122min:2121212121yyyyyyyyyyWD 试用对偶实际证明原问题无界。试用对偶实际证明原问题无界。 解：解： =0.0.0T是是 P 的一个可行解，而的一个可行解，而 D 的第的第一个约束条件不能成立由于一个约束条件不能成立由于y1 , y2 0)。因此，对偶。因此，对偶问题不可行，由推论可知，原问题无界。问题不可行，由推论可知，原问题无界。

16、_X例例3 3、知、知 0,11 max :21212121xxxxxxxxZP 0, 1 1 min :21212121yyyyyyyyWD显然，这两个问题都无可行解。显然，这两个问题都无可行解。 3 3、最优性判别定理：、最优性判别定理： 假设假设 X X* * 和和 Y Y* * 分别是分别是 P P 和和 D D 的可行解且的可行解且 CXCX* * = Y = Y* * b b，那么那么X X* *. Y. Y* *分别是问题分别是问题 P P和和D D 的最优解。的最优解。 例如，在例例如，在例1 1中，可找到中，可找到 X X* *= =0.0.4.40.0.4.4T T， Y

17、Y* *= =1.21.2，0.20.2, ,那么那么Z Z* * =28 =28，W W* * =28. =28.故故X X* * .Y .Y* *分分别是别是 P P和和D D 的最优解。的最优解。 4 4、对偶定理强对偶性：、对偶定理强对偶性： 假设一对对偶问题假设一对对偶问题 P P 和和 D D 都有可行解，那么它们都有可行解，那么它们都有最优解，且目的函数的最优值必相等。都有最优解，且目的函数的最优值必相等。 推论推论. .假设假设 P P 和和 D D 的恣意一个有最优解，那么另的恣意一个有最优解，那么另一个也有最优解，且目的函数的最优值相等。一个也有最优解，且目的函数的最优值相

18、等。 综上所述，一对对偶问题的关系，只能有下面三种情综上所述，一对对偶问题的关系，只能有下面三种情况之一出现：况之一出现：.都有最优解，分别设为都有最优解，分别设为X* 和和 Y*，那么必有，那么必有CX* =Y*b；. 一个问题无界，那么另一个问题无可行解；一个问题无界，那么另一个问题无可行解；.两个都无可行解。两个都无可行解。 5 5、互补松弛定理：、互补松弛定理： 设设X X* *和和Y Y* *分别是问题分别是问题 P P 和和 D D 的可行解，那么它们的可行解，那么它们分别是最优解的充要条件是分别是最优解的充要条件是剩剩余余变变量量或或或或ssssYXXYXCAYXYAXbY.00

19、)(00)( 同时成立同时成立 普通而言，我们把某一可行点如普通而言，我们把某一可行点如X*和和Y* 处的处的严厉不等式约束包括对变量的非负约束称为松约严厉不等式约束包括对变量的非负约束称为松约束，而把严厉等式约束称为紧约束。所以有如下推论：束，而把严厉等式约束称为紧约束。所以有如下推论： 设一对对偶问题都有可行解，假设原问题的某一约设一对对偶问题都有可行解，假设原问题的某一约束是某个最优解的松约束，那么它的对偶约束一定是束是某个最优解的松约束，那么它的对偶约束一定是其对偶问题最优解的紧约束。其对偶问题最优解的紧约束。例例4、知、知 032 235 95243min51543215432543

20、21xxxxxxxxxxxxxxxZ试经过求对偶问题的最优解来求解原问题的最优解。试经过求对偶问题的最优解来求解原问题的最优解。解：对偶问题为解：对偶问题为 0,)5(923)4(55)3(2)2(4)1(332max2121212121221yyyyyyyyyyyyyW 用图解法求出：用图解法求出： Y*=1 . 3， W=11。将将y*1=1， y*2=3 代入对偶约束条件，代入对偶约束条件，125式为紧约束，式为紧约束，34为松约束。为松约束。令原问题的最优解为令原问题的最优解为X* = x1.x2.x3.x4.x5T，那么，那么根据互补松弛条件，必有根据互补松弛条件，必有x3 = x4

21、 =0(1 . 3)12345 又由于又由于y*10， y*2 0，原问题的约束必为等式，原问题的约束必为等式，即即 322352152xxxxx 5251321xxxx化简为化简为此方程组为无穷多解此方程组为无穷多解 令令x5 =0,x5 =0,得到得到x1=1x1=1，x2=2 x2=2 即即X X* *1 =1 =1.2.0.0.01.2.0.0.0T T为原问题的为原问题的一个最优解，一个最优解，Z=11Z=11。 再令再令 x5 =2/3 x5 =2/3，得到，得到x1=5/3x1=5/3，x2=0 x2=0 即即X X* *2 2 5/3.0.0.0.2/35/3.0.0.0.2/

22、3T T也是原问题的一个最优解，也是原问题的一个最优解，Z Z* * =11 =11。例例5、知原问题的最优、知原问题的最优解为解为X* =0.0.4T，Z=12 试求对偶问题试求对偶问题的最优解。的最优解。 无无约约束束321321321321321, 0, 04 16 3253234maxxxxxxxxxxxxxxxxZ解：解： 无约束无约束321321321321321, 0, 03654 3 132 42minyyyyyyyyyyyyyyyW123将将X* =0 . 0 . 4代入原问题中，有下式：代入原问题中，有下式： 4 4 1 246 32 20532321321321xxxxx

23、xxxx所以，根据互补松弛条件，必有所以，根据互补松弛条件，必有y*1= y*2=0，代入对，代入对偶问题偶问题 3式，式， y3 =3。因此，对偶问题的最优解为。因此，对偶问题的最优解为 Y*=0 . 0 . 3，W=12。6 6、对偶问题的解、对偶问题的解利用原问题的最优单纯利用原问题的最优单纯形表和改良单纯形表求形表和改良单纯形表求解对偶问题的最优解。解对偶问题的最优解。. .设原问题为：设原问题为： maxZ=CX maxZ=CX AX b AX b X0 X0引入引入xs xs ，构建初始基变量，然后，用单纯形法求解。，构建初始基变量，然后，用单纯形法求解。当检验数满足当检验数满足j

24、0 j0 ，那么求得最优解。此时，那么求得最优解。此时， xs xs对对应的应的js js 为为- Y- Y* * ，故求对偶，故求对偶Y Y* * ，只需将最优单纯形，只需将最优单纯形表上表上xs xs 对应的检验数反号即可。对应的检验数反号即可。CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1ZCB B-1b0CNCB B-1NCB B-1例一、例一、 0,150510032170251810max2121212121xxxxxxxxPxxZ 0,185321025150100170min321321321321yyyyyyyyyDyyyW 0 150 5 100 32

25、170 250001810max5152142132154321xxxxxxxxxxxxxxxZcj1018000cBxBbx1x2x3x4x50 x317052100170/20 x410023010100/30 x515015001150/5-Z01018000icj1018000cBxBbx1x2x3x4x50 x3540/7001-23/711/710 x150/71005/7-3/718x2200/7010-1/72/7-Z-4100/7000-32/7-6/7初初始始表表最终表最终表 由上表可知：由上表可知： X*=50/7 . 200/7T，Z* =4100/7对偶问题的最优解：

26、对偶问题的最优解： Y*=0 . 32/7 . 6/7，W* =4100/7也就是外加工时的收费规范。也就是外加工时的收费规范。. .设原问题：设原问题： maxZ=CX maxZ=CX AX=b AX=b X0 X0此时，矩阵此时，矩阵A A中没有现成的矩阵中没有现成的矩阵I I，必需经过参与人工，必需经过参与人工变量来凑一个单位矩阵，再用大变量来凑一个单位矩阵，再用大M M法或两阶段法求解。法或两阶段法求解。 如何求如何求Y Y* * ，经分析得出如下结论：，经分析得出如下结论： B =0 B =0 最优基变量检验数向量最优基变量检验数向量 I =CI I =CI CB B-1 CB B-

27、1 初始初始基变量检验数向量基变量检验数向量 D = CD D = CD CB B-1D CB B-1D 非基变量非基变量检验数向量检验数向量 所以，所以， Y Y* * = CI = CI I I 例二、例二、 0123241123max3131321321321xxxxxxxxxxxx P 无约束无约束32132121321321, 0, 01212324311minyyyyyyyyyyyDyyyW cj3-1-100-M-McBxBbx1x2x3x4x5x6x73x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3-Z-2000

28、-1/3-1/31/3-M 2/3- Mcj3- 1- 100- M- McBxBbx1x2x3x4x5x6x70 x4111-21100011- Mx63-4120-1103/2- Mx71-20100011-Z3-6M-1+M-1+3M0-M00i 所以，所以， X*=4 . 1 . 9，Z* = 2 y*1= (0 4 )=1/3 y*2=(M 6 )= M(1/3M)=1/3 y*3 =(M 7 )= M(2/3 M)=2/3 Y*=1/3 . 1/3 . 2/3 W* = 2 初始基变量的检验数初始基变量的检验数4 =1/3，6 =1/3M, 7 =2/3M 定义：在一对定义：在一对

29、 P 和和 D 中，假设中，假设 P 的某个约束条件的某个约束条件的右端项常数的右端项常数bi 添加一个单位时，所引起的目的函数添加一个单位时，所引起的目的函数最优值最优值Z* 的改动量的改动量y*i 称为第称为第 i 个约束条件的影子价钱，个约束条件的影子价钱，又称为边沿价钱。又称为边沿价钱。 0 D 0 minmax YCYAXbAXPYbW CX Z三、对偶问题的经济解释三、对偶问题的经济解释影子价钱影子价钱 设：设：B是问题是问题 P的最优基，由前式可知，的最优基，由前式可知， Z*=CB B-1b = Y*b =y*1b1+ y*2b2+y*Ibi+y*mbm 当当bi 变为变为bi

30、+1 时其他右端项不变，也不影响时其他右端项不变，也不影响B，CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1ZCB B-1b0CNCB B-1NCB B-1 目的函数最优值变为：目的函数最优值变为： Z*= y*1b1+ y*2b2+y*I bi+1 +y*mbm Z*= Z* Z* = y*i )2 , 1(*miybZii 也可以写成：也可以写成：即即y*i 表示表示Z*对对 bi的变化率。的变化率。 其经济意义是：在其它条件不变的情况下，单位资源其经济意义是：在其它条件不变的情况下，单位资源变化所引起的目的函数的最优值的变化。即对偶变量变化所引起的目的函数的最优值的变

31、化。即对偶变量yi 就是第就是第 i 个约束条件的影子价钱。个约束条件的影子价钱。 也可以了解为目的函数最优值对资源的一阶偏导数也可以了解为目的函数最优值对资源的一阶偏导数但问题中一切其它数据都坚持不变。但问题中一切其它数据都坚持不变。 假设第假设第i 种资源的单位市场价钱为种资源的单位市场价钱为mi ，当，当yi mi 时，时，企业情愿购进这种资源，单位纯利为企业情愿购进这种资源，单位纯利为yimi ，那么有，那么有利可图；假设利可图；假设yi mi ，那么企业有偿转让这种资源，那么企业有偿转让这种资源，可获单位纯利可获单位纯利miyi ，否那么，企业无利可图，甚至，否那么，企业无利可图，甚

32、至亏损。亏损。 0,150510032170251810max2121212121xxxxxxxxPxxZ010 20 30 40 50 6010 2 0 3 0 4 0 50 x2 x1123( 50/7. 200/7 )74132)719918()75510( Z多了多了 32/7 32/7x1010 20 30 40 50 6010 2 0 3 0 4 0 50 x2 123( 55/7. 199/7 )74100)720018()75010( Z010 20 30 40 50 6010 2 0 3 0 4 0 50 x2 x1123( 50/7. 200/7 )74106)720218

33、()74710( Z010 20 30 40 50 6010 2 0 3 0 4 0 50 x2 x1123( 47/7. 202/7 )多了多了 6/7 6/7 对偶单纯形法是求解线性规划的另一的根本方法。对偶单纯形法是求解线性规划的另一的根本方法。它是根据对偶原理和单纯形法的原理而设计出来的，它是根据对偶原理和单纯形法的原理而设计出来的，因此称为对偶单纯形法。不要简单了解为是求解对偶因此称为对偶单纯形法。不要简单了解为是求解对偶问题的单纯形法。问题的单纯形法。 由对偶实际可以知道，对于一个线性规划问题，我由对偶实际可以知道，对于一个线性规划问题，我们可以经过求解它的对偶问题来找到它的最优解

34、。们可以经过求解它的对偶问题来找到它的最优解。四、对四、对 偶偶 单单 纯纯 形形 法法 也就是说，求解原问题也就是说，求解原问题P P时，可以从时，可以从P P的一的一个根本解非基可行解开场，逐渐迭代，使目的函个根本解非基可行解开场，逐渐迭代，使目的函数值数值Z=Y b= CB B-1b =CXZ=Y b= CB B-1b =CX减少，当迭代到减少，当迭代到XB=B-1b0XB=B-1b0时，即找到了时，即找到了P P的最优解，这就是对偶的最优解，这就是对偶单纯形法。单纯形法。 同原始单纯形求法一样，求解对偶问题同原始单纯形求法一样，求解对偶问题D D，也可，也可以从以从D D的一个根本可行

35、解开场，从一个根本可行解的一个根本可行解开场，从一个根本可行解迭代到另一个根本可行解，使目的函数值减少。迭代到另一个根本可行解，使目的函数值减少。对偶对偶 单纯形表单纯形表max存在存在bi 0 至至少有一个少有一个初始表初始表 全部全部j0 迭迭代代迭代规那么坚迭代规那么坚持原问题可行持原问题可行解解最终表最终表全部全部 bi 0全部全部j0 在原问题解不可行，对偶在原问题解不可行，对偶问题解可行的根底上迭代，问题解可行的根底上迭代，至原问题解可行，对偶问至原问题解可行，对偶问题解也可行，也就同时到题解也可行，也就同时到达最优。达最优。 用对偶单纯形法求解原问用对偶单纯形法求解原问题时必需满

36、足两个条件：题时必需满足两个条件：1 单纯形表的常数列中单纯形表的常数列中至 少 有 一 个 负 的 分 量 。至 少 有 一 个 负 的 分 量 。 存在存在 bi 0 2 单纯形表的检验数行单纯形表的检验数行的全部元素不大于的全部元素不大于0。 全全部部j0 用对偶单纯形法求解原问题用对偶单纯形法求解原问题 maxZ = CX AX = b X 0 步骤如下：步骤如下：1假设初始表假设初始表j0，bi 0，那么目前解为最优解。，那么目前解为最优解。 假设初始表假设初始表j0，存在，存在bi 0 至少有一个，那么至少有一个，那么转入下一步进展迭代。转入下一步进展迭代。2选出基变量：选出基变量

37、： minbi | bi0 =b k ,那么那么k行为主元行，行为主元行，x k 出基。出基。3选入基变量：选入基变量： min j /a kj | a kj0, 那么以 x j 为入基变量，用单纯形法继续迭代，即可求出最优解。 二基变量的价值系数 Cj 发生改动， Cj Cj=Cj+Cj (Cj可正可负)，一切非基变量的检验数都改动，计算新的检验数。 假设新的检验数： 1j0， 原最优解坚持不变。 ( 2 ) j0, 那么以大于0的检验数中最大的变量为入基变量，用单纯形法继续迭代，即可求出最优解。 例：某企业利用三种资源消费两种产品的最优方案例：某企业利用三种资源消费两种产品的最优方案问题归

38、结为以下线性规划问题归结为以下线性规划 0,45 802903 45 max2121212121xxxxxxxxxxZ知最优表如下。知最优表如下。1 1确定确定x2x2的系数的系数c2c2的变化范围，使原最优的变化范围，使原最优解坚持最优；解坚持最优；2 2假设假设c2=6c2=6，求新，求新的最优方案。的最优方案。 一、一、 价值系数价值系数cjcj的变化分析的变化分析cj54000CBXBbx1x2x3x4x50 x3250012-55x1351001-14 x2 10 010-12000-1-3 0,45 802903 45 max2121212121xxxxxxxxxxZ4 = c25

39、 05 = 52c2 0 5/2 c2 5cj5c2 000CBXBbx1x2x3x4x50 x3250012-55x1351001-1c2 x2 10 010-12000c2 - 55 - 2c2最优解最优解X X* *= =3535，1010，2525，0 0，0 0T T坚持不变。坚持不变。1Cj56000CBXBbx1x2x3x4x50 x3250012-55x1351001-16 x2 10 010-12j 0001-70 x425/2001/21-5/25x145/210-1/203/26 x2 45/2 011/20-1/2j00-1/20-9/2x1*=45/2，x2*=45/

40、2，x4*=25/2，x3*= x5*=0，z*=495/22 二、右端常数bi的变化分析1. 假设假设B-1b0 , 那么原最优解还是最优解，那么原最优解还是最优解， 即最优基即最优基B不变，但解的数值发生改动。不变，但解的数值发生改动。 XB=B-1b,其它其它 x为为02. 假设假设B-1b 0, 那么用对偶单纯形法继续求那么用对偶单纯形法继续求解。解。3确定使最优基不变的资源限量范围。确定使最优基不变的资源限量范围。 用用B-1b0计算。计算。 XB= B1b例：对于上例中的线性规划作以下分析：例：对于上例中的线性规划作以下分析：1 1b3b3在什么范围内变化，原最优基不变？在什么范围

41、内变化，原最优基不变？2 2假设假设b3=55b3=55，求出新的最优解。，求出新的最优解。 0,45 802903 45Z max2121212121xxxxxxxxxx二、右端常数二、右端常数bibi的变化分析的变化分析cj54000CBXBbx1x2x3x4x50 x3250012-55x1351001-14 x2 10 010-12000-1-32 1- 01 1 05- 2 1最优基：最优基：B=P3，P1，P2B1=1 2 1- 01 1 05- 2 1 3b8090 333b280b805b - 250 3b8090B1=0 解得解得40b35040b350，即当，即当b340b

42、340，50 50 时，最优基时，最优基B B 不变不变z*=580b3+480+2b3=80+3b3333b280b805b-250*2*1*3xxx=2当当 b3= 55 时时 333b280b805b-250 30 25 25=x2 x1x50-11/5-3/500j0-1/52/51020 4 03/5-1/5013051-2/5-1/50050-32-1-5x50-1000j -101030 x2 4 100125x152100-25x30 x4x3x2x1bXBCB0045Cj三、三、 添加一个新变量的分析添加一个新变量的分析例例2.10 续例续例2.8设企业研制了一种新产设企业研

43、制了一种新产品，对三种资源的耗费系数列向量以品，对三种资源的耗费系数列向量以P6表示表示P6= 。问它的价值系数。问它的价值系数c6符合什么条符合什么条件件才必需安排它的消费？设才必需安排它的消费？设c6=3，新的最优，新的最优消费方案是什么？消费方案是什么？2/112/36=c6CBB1P6 =c60，5，4 = c65/202/116P2 1- 01 1 05- 2 12/112/302/11=B1P6 =Cj540003CBXBbx1x2x3x4x5x60 x3250012-515x1351001-11/26 x2 10 010-120j 000-1-31/23x6250012-515x145/210-1/203/204 x2 10 010-120j00-1/2-2-1/20四、四、 添加新的约束条件的分析添加新的约束条件的分析例例2.11 假设在例假设在例2.8中，还要思索