对偶理论DualityTheory

《对偶理论DualityTheory》由会员分享，可在线阅读，更多相关《对偶理论DualityTheory（86页珍藏版）》请在装配图网上搜索。

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 3

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

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

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

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

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

9、XCZP 例三、例三、无无约约束束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,0024732543

11、 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.t.YA C Y 0max

12、 Z=C Xs.t.AXb X 0对偶的定义对偶的定义对偶的定义对偶的定义max W=-Ybs.t.YA C Y 0（二）、对偶问题的性质（二）、对偶问题的性质2 2、弱对偶原理（弱对偶性）：设、弱对偶原理（弱对偶性）：设 和和 分别是问题分别是问题（P）和（）和（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 2020min212121212121yyyyyyyyyyyyW（D）由观察可知：由观察可知：=（1.1.1.1）T，=（1.1），分别），分别是（是（P）和（）和（D）的可行解。）的可行

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

16、可行，由推论不可行，由推论可知，原问题无界。可知，原问题无界。_X例例3 3、已知、已知 0,11 max :21212121xxxxxxxxZP 0,1 1 min :21212121yyyyyyyyWD显然，这两个问题都无可行解。显然，这两个问题都无可行解。3 3、最优性判别定理：、最优性判别定理：若若 X*和和 Y*分别是分别是 P 和和 D 的可行解且的可行解且 CX*=Y*b，则则X*.Y*分别是问题分别是问题 P和和D 的最优解。的最优解。例如，在例例如，在例1 1中，可找到中，可找到 X*=（0.0.4.40.0.4.4）T T，Y*=（1.21.2，0.20.2）,则则Z*=2

17、8，W*=28.故故X*.Y*分别分别是是 P和和D 的最优解。的最优解。4 4、对偶定理（强对偶性）：、对偶定理（强对偶性）：若一对对偶问题若一对对偶问题 P 和和 D 都有可行解，则它们都有都有可行解，则它们都有最优解，且目标函数的最优值必相等。最优解，且目标函数的最优值必相等。推论推论.若若 P 和和 D 的任意一个有最优解，则另一个的任意一个有最优解，则另一个也有最优解，且目标函数的最优值相等。也有最优解，且目标函数的最优值相等。综上所述，一对对偶问题的关系，只能有下面三种情综上所述，一对对偶问题的关系，只能有下面三种情况之一出现：况之一出现：.都有最优解，分别设为都有最优解，分别设为

18、X*和和 Y*，则必有，则必有CX*=Y*b；.一个问题无界，则另一个问题无可行解；一个问题无界，则另一个问题无可行解；.两个都无可行解。两个都无可行解。5 5、互补松弛定理：、互补松弛定理：设设X*和和Y*分别是问题分别是问题 P 和和 D 的可行解，则它们分别的可行解，则它们分别是最优解的充要条件是是最优解的充要条件是剩剩余余变变量量或或或或ssssYXXYXCAYXYAXbY.00)(00)(同时成立同时成立 一般而言，我们把某一可行点（如一般而言，我们把某一可行点（如X*和和Y*）处的严）处的严格不等式约束（包括对变量的非负约束）称为松约束，格不等式约束（包括对变量的非负约束）称为松约

19、束，而把严格等式约束称为紧约束。所以有如下推论：而把严格等式约束称为紧约束。所以有如下推论：设一对对偶问题都有可行解，若原问题的某一约束设一对对偶问题都有可行解，若原问题的某一约束是某个最优解的松约束，则它的对偶约束一定是其对是某个最优解的松约束，则它的对偶约束一定是其对偶问题最优解的紧约束。偶问题最优解的紧约束。例例4、已知、已知 032 235 95243min5154321543254321xxxxxxxxxxxxxxxZ试通过求对偶问题的最优解来求解原问题的最优解。试通过求对偶问题的最优解来求解原问题的最优解。解：对偶问题为解：对偶问题为 0,)5(923)4(55)3(2)2(4)1

20、(332max2121212121221yyyyyyyyyyyyyW 用图解法求出：用图解法求出：Y*=（1.3），），W=11。将将y*1=1，y*2=3 代入对偶约束条件，代入对偶约束条件，（1）（）（2）（）（5）式为紧约束，（）式为紧约束，（3）（）（4）为松约束。）为松约束。令原问题的最优解为令原问题的最优解为X*=（x1.x2.x3.x4.x5）T，则根据，则根据互补松弛条件，必有互补松弛条件，必有x3=x4=0(1.3)（1）（2）（3）（4）（5）又由于又由于y*10，y*2 0，原问题的约束必为等式，即，原问题的约束必为等式，即 322352152xxxxx 5251321x

21、xxx化简为化简为此方程组为无穷多解此方程组为无穷多解 令令x5=0,得到得到x1=1，x2=2 即即X*1=（1.2.0.0.0）T为原问题的为原问题的一个最优解，一个最优解，Z=11。再令再令 x5=2/3，得到，得到x1=5/3，x2=0 即即X*2（5/3.0.0.0.2/3）T也是原问题的一个最优解，也是原问题的一个最优解，Z*=11。例例5、已知原问题的最、已知原问题的最优解为优解为X*=（0.0.4）T，Z=12 试求对偶问题试求对偶问题的最优解。的最优解。无无约约束束321321321321321,0,04 16 3253234maxxxxxxxxxxxxxxxxZ解：解：无约

22、束无约束321321321321321,0,03654 3 132 42minyyyyyyyyyyyyyyyW（1）（2）（3）将将X*=（0.0.4）代入原问题中，有下式：）代入原问题中，有下式：4 4 1 246 32 20532321321321xxxxxxxxx所以，根据互补松弛条件，必有所以，根据互补松弛条件，必有y*1=y*2=0，代入对偶，代入对偶问题问题（3 3）式，）式，y3 =3。因此，对偶问题的最优解为。因此，对偶问题的最优解为 Y*=（0.0.3），），W=12。6 6、对偶问题的解、对偶问题的解利用原问题的最优单纯利用原问题的最优单纯形表和改进单纯形表求形表和改进单纯

23、形表求解对偶问题的最优解。解对偶问题的最优解。.设原问题为：设原问题为：maxZ=CX AX b X0引入引入xs，构建初始基变量，然后，用单纯形法求解。当，构建初始基变量，然后，用单纯形法求解。当检验数满足检验数满足j0，则求得最优解。此时，则求得最优解。此时，xs对应的对应的js 为为-Y*，故求对偶，故求对偶Y*，只要将最优单纯形表上，只要将最优单纯形表上xs 对应的检验数反号即可。对应的检验数反号即可。CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1ZCB B-1b0CNCB B-1NCB B-1例一、例一、0,150510032170251810max2121212

24、121xxxxxxxxPxxZ 0,185321025150100170min321321321321yyyyyyyyyDyyyW 0 150 5 100 32 170 250001810max5152142132154321xxxxxxxxxxxxxxxZcj1018000cBxBbx1x2x3x4x50 x317052100170/20 x410023010100/30 x515015001150/5-Z01018000icj1018000cBxBbx1x2x3x4x50 x3540/7001-23/711/710 x150/71005/7-3/718x2200/7010-1/72/7-Z

25、-4100/7000-32/7-6/7初初始始表表最终表最终表 由上表可知：由上表可知：X*=（50/7.200/7）T，Z*=4100/7对偶问题的最优解：对偶问题的最优解：Y*=（0.32/7.6/7），），W*=4100/7也就是外加工时的收费标准。也就是外加工时的收费标准。.设原问题：设原问题：maxZ=CX AX=b X0此时，矩阵此时，矩阵A中没有现成的矩阵中没有现成的矩阵I，必须通过加入人工，必须通过加入人工变量来凑一个单位矩阵，再用大变量来凑一个单位矩阵，再用大M法或两阶段法求解。法或两阶段法求解。如何求如何求Y*，经分析得出如下结论：，经分析得出如下结论：B=0 最优基变量检

26、验数向量最优基变量检验数向量 I=CI CB B-1 初始基变量检验数向量初始基变量检验数向量 D=CD CB B-1D 非基变量检验数向量非基变量检验数向量 所以，所以，Y*=CI 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-1/3-1/31

27、/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 定义：在一对定义：在一对 P 和和 D 中，若中，若 P 的某个约束条件的的某个约束条件的右端

28、项常数右端项常数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+1 时（其余右端项不变，也不影响时（其余右端项不变，也不影响B），），CCBCN0C

29、BXBbXBXNXSCBXBB-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的变化率。的变化率。其经济意义是：在其它条件不变的情况下，单位资源其经济意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。即对偶变量变化所引起的目标函数的最优值的变化。即对偶变量yi 就是第就是第 i 个约束条件的影子价格。个约束条件的影子价格。也可以理解为目标

30、函数最优值对资源的一阶偏导数也可以理解为目标函数最优值对资源的一阶偏导数（但问题中所有其它数据都保持不变）。（但问题中所有其它数据都保持不变）。若第若第i 种资源的单位市场价格为种资源的单位市场价格为mi，当，当yi mi 时，时，企业愿意购进这种资源，单位纯利为企业愿意购进这种资源，单位纯利为yimi，则有利，则有利可图；如果可图；如果yi mi，则企业有偿转让这种资源，可，则企业有偿转让这种资源，可获单位纯利获单位纯利miyi，否则，企业无利可图，甚至亏损。，否则，企业无利可图，甚至亏损。0,150510032170251810max2121212121xxxxxxxxPxxZ010 20

31、 30 40 50 6010 2 0 3 0 4 0 50 x2 x1123(50/7.200/7)74132)719918()75510(Z多了多了 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()74710(Z010 20 30 40 50 6010 2 0 3 0 4 0 50 x2 x1123(47/7.202/7)多了多了 6/7 对

32、偶单纯形法是求解线性规划的另一的基本方法。对偶单纯形法是求解线性规划的另一的基本方法。它是根据对偶原理和单纯形法的原理而设计出来的，它是根据对偶原理和单纯形法的原理而设计出来的，因此称为对偶单纯形法。不要简单理解为是求解对偶因此称为对偶单纯形法。不要简单理解为是求解对偶问题的单纯形法。问题的单纯形法。由对偶理论可以知道，对于一个线性规划问题，我由对偶理论可以知道，对于一个线性规划问题，我们能够通过求解它的对偶问题来找到它的最优解。们能够通过求解它的对偶问题来找到它的最优解。四、对四、对 偶偶 单单 纯纯 形形 法法 也就是说，求解原问题（也就是说，求解原问题（P P）时，可以从（）时，可以从（

33、P P）的一）的一个基本解（非基可行解）开始，逐步迭代，使目标函个基本解（非基可行解）开始，逐步迭代，使目标函数值（数值（Z=Y b=CB B-1b=CX）减少，当迭代到）减少，当迭代到XB=B-1b0时，即找到了（时，即找到了（P P）的最优解，这就是对偶）的最优解，这就是对偶单纯形法。单纯形法。同原始单纯形求法一样，求解对偶问题（同原始单纯形求法一样，求解对偶问题（D D），也可），也可以从（以从（D D）的一个基本可行解开始，从一个基本可行解）的一个基本可行解开始，从一个基本可行解（迭代）到另一个基本可行解，使目标函数值减少。（迭代）到另一个基本可行解，使目标函数值减少。对偶对偶 单纯形

34、表单纯形表max存在存在bi 0（至（至少有一个）少有一个）初始表初始表 全部全部j0 迭迭代代迭代规则保持迭代规则保持原问题可行解原问题可行解最终表最终表全部全部 bi 0全部全部j0 在原问题解不可行，对偶在原问题解不可行，对偶问题解可行的基础上迭代，问题解可行的基础上迭代，至原问题解可行，对偶问至原问题解可行，对偶问题解也可行，也就同时达题解也可行，也就同时达到最优。到最优。用对偶单纯形法求解原问用对偶单纯形法求解原问题时必须满足两个条件：题时必须满足两个条件：（1）单纯形表的常数列中单纯形表的常数列中至 少 有 一 个 负 的 分 量。至 少 有 一 个 负 的 分 量。存在存在 bi

35、 0 （2）单纯形表的检验数行单纯形表的检验数行的全部元素不大于的全部元素不大于0。全全部部j0 用对偶单纯形法求解原问题用对偶单纯形法求解原问题 maxZ=CX AX=b X 0 步骤如下：步骤如下：1若初始表若初始表j0，bi 0，则目前解为最优解。，则目前解为最优解。若初始表若初始表j0，存在，存在bi 0（至少有一个），则转入（至少有一个），则转入下一步进行迭代。下一步进行迭代。2选出基变量：选出基变量：minbi|bi0=b k,则则k行为主元行，行为主元行，x k 出基。出基。3选入基变量：选入基变量：min j/a kj|a kj0,则以则以 x j 为入基变量，用单纯为入基变量

36、，用单纯形法继续迭代，即可求出最优解。形法继续迭代，即可求出最优解。（二）基变量的价值系数（二）基变量的价值系数 Cj 发生改变，发生改变，Cj Cj=Cj+Cj (Cj可正可负可正可负)，所，所有非基变量的检验数都改变，计算新的检验有非基变量的检验数都改变，计算新的检验数。数。若新的检验数：若新的检验数：（1）j0，原最优解保持不变。原最优解保持不变。(2)j0,则以大于则以大于0的检验数中最大的变的检验数中最大的变量为入基变量，用单纯形法继续迭代，即可量为入基变量，用单纯形法继续迭代，即可求出最优解。求出最优解。例：某企业利用三种资源生产两种产品的最优计划例：某企业利用三种资源生产两种产品

37、的最优计划问题归结为下列线性规划问题归结为下列线性规划 0,45 802903 45 max2121212121xxxxxxxxxxZ已知最优表如下。已知最优表如下。（1 1）确定）确定x2的系数的系数c2的的变化范围，使原最优解变化范围，使原最优解保持最优；保持最优；（2 2）若）若c2=6，求新的最，求新的最优计划。优计划。一、一、价值系数价值系数c cj j的变化分析的变化分析cj54000CBXBbx1x2x3x4x50 x3250012-55x1351001-14 x2 10 010-12000-1-3 0,45 802903 45 max2121212121xxxxxxxxxxZ4

38、 =c25 05 =52c2 0 5/2 c2 5cj5c2 000CBXBbx1x2x3x4x50 x3250012-55x1351001-1c2 x2 10 010-12000c2-55-2c2最优解最优解X*=（35，10，25，0，0）T保持不变。保持不变。（1）Cj56000CBXBbx1x2x3x4x50 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/2，x4*=25/2，x3*

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

40、）若）若b3=55，求出新的最优解。，求出新的最优解。0,45 802903 45Z max2121212121xxxxxxxxxx二、右端常数二、右端常数b bi i的变化分析的变化分析cj54000CBXBbx1x2x3x4x50 x3250012-55x1351001-14 x2 10 010-12000-1-32 1-01 1 05-2 1最优基：最优基：B=（P3，P1，P2）B1=（1）2 1-01 1 05-2 1 3b8090 333b280b805b -250 3b8090B1=0 解得解得40b350，即当，即当b340，50 时，最优基时，最优基B 不变不变z*=5（80

41、b3）+4（80+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）设企业研制了一种新产品，对三种资源的消耗系数列向量以P6表示P6=。问它的价值系数c6符合什么

42、条件才必须安排它的生产？设c6=3，新的最优生产计划是什么？2/112/36=c6CBB1P6=c6（0，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中，还要考虑一个新的资源约束：4x1+

43、2x21504x1+2x2+x6=1500,45 802903 45 max2121212121xxxxxxxxxxzX*=（35，10，25，0，0）T4x1+2x2+x6=150cj540000CBXBbx1x2x3x4x5x60 x3250012-505x1351001-104 x2 10 010-1200 x6150420001000-1-30Cj540000CBXBbx1x2x3x4x5x60 x3250012-505x1351001-104x210010-1200 x6 150 420001j 000-1-300 x3250012-505x1351001-104x210010-12

44、00 x6-10 000-201j000-1-300 x3150010-515x1301000-11/24x21501002-1/20 x4 5 00010-1/2j0000-3-1/2五、五、其它变化情况的分析其它变化情况的分析1.cj和bi同时变化的情况例例2.12 在例2.8中，假定c2由4上升为6，b3增加到55，试问最优解将会发生什么变化？0,45 802903 45 max2121212121xxxxxxxxxxz2 1-01 1 05-2 1B1=B =5580902 1-01 1 05-2 1558090302525代替最优表的b列，并把c2改为6cj56000CBXBbx1x

45、2x3x4x50 x3-250012-55x1251001-16 x2 30 010-12j0001-7原问题与对偶问题均非可行解，表中第一方程是x3+2x45x5=25，两边乘以（-1），得：x32x4+5x5=25，再引入人工变量x6：x32x4+5x5+x6=25以x6为基变量，增添第6列，应用大M法继续求解。Cj56000-MCBXBbx1x2x3x4x5x6-Mx62500-1-2515x1251001-106 x2 30 010-120j 00-M-2M+15M-700 x5500-1/5-2/5105x13010-1/53/501/56 x2 20 012/5-1/50-2/5j

46、00-7/5-9/50-M+7/5新的最优计划产量为x1*=30，x2*=20，z*=270。x32x4+5x5+x6=252.技术系数aij的变化例例2.13 在例2.8中，第一种产品的消耗系数改变为 ，价值系数不变，求新的最优解。2/12/32/31P0,45 802903 45 max2121212121xxxxxxxxxxz2 1-01 1 05-2 1B1=2/1122/12/32/32 1-01 1 05-2 111PBCj54000CBXBbx1x2x3x4x50 x3252012-55x1351001-14 x2 10-1/210-12j 000-1-3Cj54000CBXBbx1x2x3x4x50 x3252012-55x1351001-14 x2 10-1/210-12j 000-1-30 x3-450010-35x1351001-14 x2 27.5 010-1/23/2j000-3-10 x51500-1/3015x15010-1/3104 x2 5 011/2-1/20j 00-1/3-30