运筹学教程老师课件第2对偶理论

1、第三章 线性规划的对偶理论 与灵敏度分析 n线性规划的对偶问题 n对偶问题的基本性质n影子价格n对偶单纯形法n灵敏度分析n参数线性规划窗含西岭千秋雪，门泊东吴万里船对偶是一种普遍现象Dual Simplex Method，1954年美国数学家C.莱姆基提出对偶单纯形法。单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。 设某工厂生产两种产品甲和乙，生产中需设某工厂生产两种产品甲和乙，生产中需4种设备按种设备按A，B，C，D顺

2、序加工，每件产品加工所需的机时数、每件产品的利润值及每顺序加工，每件产品加工所需的机时数、每件产品的利润值及每种设备的可利用机时数列于下表种设备的可利用机时数列于下表 ：产品数据表产品数据表 设备设备产品产品ABCD产品利润产品利润（元件）（元件） 甲甲 21402乙乙 22043设备可利用设备可利用机时数（时）机时数（时） 1281612问：充分利用设备机时，工厂应生产甲和乙型产品各多少件才问：充分利用设备机时，工厂应生产甲和乙型产品各多少件才能获得最大利润？能获得最大利润？1. 解：设甲、乙型产品各生产x1及x2件，则数学模型为： 0,124164821222.32max212121212

3、1xxxxxxxxtsxxz反过来问：若厂长决定不生产甲和乙型产品，决定出租机器反过来问：若厂长决定不生产甲和乙型产品，决定出租机器用于接受外加工，只收加工费，那么种机器的机时如何定用于接受外加工，只收加工费，那么种机器的机时如何定价才是最佳决策？价才是最佳决策？在市场竞争的时代，厂长的最佳决策显然应符合两条：（1）不吃亏原则。即机时定价所赚利润不能低于自己加工甲、乙型产品所获利润。由此原则，便构成了新规划的不等式约束条件。 （2）竞争性原则。即在上述不吃亏原则下，尽量降低机时总收费，以便争取更多用户。或者说租借方希望总的收购价越小越好(目标)设设A、B、C、D 设备的机时价分别为设备的机时价

4、分别为y1、y2、y3、y4，则新的线，则新的线性规划数学模型为：性规划数学模型为： 0,340222042.1216812min4321432143214321yyyyyyyyyyyytsyyyy把同种问题的两种提法所获得的数学模型用表2表示，将会发现一个有趣的现象。原问题与对偶问题对比表A（y1） B（y2）C（y3） D（y4） 甲（甲（x1） 21402乙（乙（x2） 220431281612 min max z 2. 0,124164821222.32max2121212121xxxxxxxxtsxxz1234123412341234min12816122402s.t 22043,0

5、yyyyyyyyyyyyy yyy原问题原问题（对偶问题）（对偶问题）对偶问题对偶问题（原问题）（原问题）从上例来看从上例来看, ,对偶问题有其明显的经济含义对偶问题有其明显的经济含义. .（1）对称形式特点：目标函数求极大值时，所有约束条件为号，变量非负; 目标函数求极小值时，所有约束条件为号，变量非负. max Z 0 PCXAXbX： : min 0DWY bA YCY已知P，写出Dn 任何线性规划问题都有其对偶问题任何线性规划问题都有其对偶问题. .列向量行向量n个变量n个约束例如：(P) 2x 2 206038045060212112121 xxyxyxxxxz,max 121212

6、12min8060. . 2360 4250 ,0yystyyyyyy例2.1 写出线性规划问题的对偶问题 0,5643 7 32 532432max321321321321321xxxxxxxxxxxxxxxZ解：首先将原问题变形为对称形式,再写出对偶式123123123123123m ax2342352 3 7 3 465,0Zxxxxxxxxxxxxxxx 123123123123123min23523 23 43 576 4,0wyyyyyyyyyyyyyyy (2) 非对称型对偶问题 若给出的线性规划不是对称形式，可以先化成对称形式再写对偶问题。也可直接按教材表2-2中的对应关系写出

7、非对称形式的对偶问题。原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）约束条件右端项约束条件右端项目标函数变量的系数目标函数变量的系数目标函数变量的系数目标函数变量的系数约束条件右端项约束条件右端项目标函数目标函数 max目标函数目标函数 min约约束束条条件件m个个m个个变变量量00=无约束无约束变变量量n个个n个个约约束束条条件件00无约束无约束=例2.2 写出下列线性规划问题的对偶问题. 无无约约束束4321432142143214321, 0, 06 43 247 23 523 4 532maxxxxxxxxxxxxxxxxxxxxZ解：原问题的对偶问题

8、为 无无约约束束32132131321321321,0,01 72 54 3332 2234 645minyyyyyyyyyyyyyyyyyW第三章 线性规划的对偶理论与灵敏度分析 n线性规划的对偶问题 n对偶问题的基本性质n影子价格n对偶单纯形法n灵敏度分析n 参数线性规划第二节 对偶问题的基本性质为了便于讨论，下面不妨总是假设针对对称形式：: maxs.t.0ZCXAXbX原问题: mins.t.0WY bA YCY对偶问题原线性规划问题的矩阵表达式加上松弛变量后为： 一、单纯形法的矩阵描述上式中上式中 Xs 为松弛变量，为松弛变量， ，I 为为mm单位矩阵。单位矩阵。 0,00maxss

9、sXXbIXAXXCXz),(21mnnnsxxxX令非基变量令非基变量 XN =0, XS =0 则得到一个基可行解。则得到一个基可行解。 XB = B-1 b ， Z =CB B-1 b XB XN XS(A，I) X XS =(B，N，I) =(B XB+N XN +I XS)=b以 B B-1-1 左乘上式得左乘上式得： B B-1-1 B XB+ B B-1-1 N XN + B B-1-1 I XS= B B-1-1 bXB= B B-1-1 b B B-1-1 N XN B B-1-1 XS代入目标函数代入目标函数得：得：Z= CX+0Xs =(CB， CN)XB XN+0Xs=

10、 CBXB + CNXN +0Xs= CB(B-1 b B-1 N XN B-1 XS ) + CNXN +0Xs= CBB-1 b CBB-1 N XN CB B-1 XS + CNXN +0Xs= CBB-1 b + (CN CB B-1 N) XN CB B-1 XS 单纯形法计算时，总选取单纯形法计算时，总选取 I 为为初始基初始基，对应基变量为对应基变量为 Xs。假假设迭设迭代若干步后，基变量变为代若干步后，基变量变为XB，在初始单纯形表中对应的，在初始单纯形表中对应的系数矩阵为系数矩阵为B。B将在初始单纯形表中单独列出，而将在初始单纯形表中单独列出，而A中去掉若干列后剩下的列组成矩

11、中去掉若干列后剩下的列组成矩阵阵N，这样初始单纯形表可列成如下形式。，这样初始单纯形表可列成如下形式。 非基变量非基变量基变量基变量XB XNXS0 XS bB NIcj-zjCB CN0 当迭代若干步后，基变量为当迭代若干步后，基变量为X XB B时，则该步的单纯形表中由时，则该步的单纯形表中由X XB B系数系数组成的矩阵为组成的矩阵为I I。又因单纯形法的迭代是对约束增广矩阵进行的又因单纯形法的迭代是对约束增广矩阵进行的行初行初等变换等变换，对应对应X XS S的系数矩阵在新表中应为的系数矩阵在新表中应为B B-1-1。故当基变量为故当基变量为X XB B时，新时，新的单纯形表具有如下形

12、式。的单纯形表具有如下形式。 基变量基变量非基变量非基变量XBXN XSCB XB B B-1-1 bIB B-1-1 N B B-1-1 cj-zj0CN CB B B-1-1 N CB B B-1-1 当迭代后基变量为当迭代后基变量为XB时时，其在初始单纯形表中的系数矩阵为其在初始单纯形表中的系数矩阵为B B，则有：，则有：（1 1）对应初始单纯形表中的单位矩阵对应初始单纯形表中的单位矩阵I I，迭代后的单纯形表中为，迭代后的单纯形表中为B B-1-1 （2）初始单纯形表中基变量初始单纯形表中基变量Xs=bXs=b，迭代后的表，迭代后的表中中 XB= B B-1-1 b（3）初始单纯形表中

13、约束系数矩阵为初始单纯形表中约束系数矩阵为 ，迭代后的，迭代后的 表中约束系数矩阵为表中约束系数矩阵为(B(B-1-1 左乘左乘) ) :INBIA, 1111111,BNBIIBNBBBIBAB非基变量非基变量基变基变量量XB XNXS0 XS bB NIcj-zjCB CN0基变基变量量非基变量非基变量XBXN XSCB XB B B-1-1 bIB B-1-1 N B B-1-1 cj-zj0CN CB B B-1-1 N CB B B-1-1 （4）若初始矩阵中变量若初始矩阵中变量Xj的系数向量为的系数向量为Pj ，迭代后为，迭代后为 ，则有，则有:jPjjPBP1（5）当当B B为最

14、优基时，应有为最优基时，应有: : 01NBCCBN01BCB这时从检验数行看出，若取其这时从检验数行看出，若取其相反数相反数恰好是其对偶问题的一个可行解。恰好是其对偶问题的一个可行解。将这个解代入对偶问题的目标函数值，且有将这个解代入对偶问题的目标函数值，且有： 因因XB的检验数可写为的检验数可写为: zbBCbYwB11BCYB0YCYA则有则有称为称为单纯形乘子单纯形乘子，若令若令1BCB基变量基变量非基变量非基变量XBXN XSCB XB B B-1-1 bIB B-1-1 N B B-1-1 Cj-zj0CN CB B B-1-1 N CB B B-1-1 XN的检验数的检验数 XS

15、的检验数的检验数 0ICCBBXB的检验数的检验数 01ABCCB所以XA的检验数的检验数 二、原规划与对偶问题的变量及解之间的对应关系二、原规划与对偶问题的变量及解之间的对应关系对偶(min型)变量的最优解等于原问题松弛变量的机会成本，或者说原问题松弛变量检验数的绝对值。 容易证明，对偶问题最优解的剩余变量解值等于原问题对应变量的检验数的绝对值。 由于原问题和对偶问题是相互对偶的，因此对偶问题的检验数与原问题的解也有类似上述关系。 更一般地讲，不管原问题是否标准，在最优解的单纯型表中，都有原问题虚变量(松弛或剩余) 的机会成本对应其对偶问题实变量 (对偶变量)的最优解，原问题实变量(决策变量

16、) 的检验数对应其对偶问题虚变量 (松弛或剩余变量)的最优解。因此，原问题或对偶问题只需求解其中之一就可以了。 例3.4 两个互为对偶的线性规划问题，两者分别加上松弛和剩余变量后为： 543210002maxxxxxxz)5 ,.1(05242615552142132jxxxxxxxxxj543210052415minyyyyyw) 5 , 1(0125265321432iyyyyyyyyi两个问题的最终单纯形表见下页： jjzc 原问题变量松弛变量 x1x2x3x4x5x315/20015/415/2x17/21001/41/2x23/20101/43/2000-1/4-1/2 对偶问题的剩

17、余变量对偶问题变量y4y5y1y2y3jjzc 对偶问题变量对偶问题的剩余变量 y1y2y3y4y5y21/4 5/410 1/41/4y31/215/2011/23/215/2007/23/2 原问题松弛变量x3x4x5原问题变量x1x2三、线性规划的对偶定理1. 弱对偶定理定理 对偶问题(min)的任何可行解 Y0，其目标函数值总是不小于原问题(max)任何可行解 X0 的目标函数值。00000000000000000: ,00 0, .0 .XYAXbY ACXYY AC XY AXCXAXbYY bY AXCX证由于分别为原问题和对偶问题的可行解 故有因，因此另外，因， 因此弱对偶定理

18、推论弱对偶定理推论: :nmax问题的任何可行解目标函数值是其对偶 min问题目标函数值的下限； min问题的任何可行解目标函数值是其对偶max问题目标函数值的上限。n 如果原max(min)问题为无界解，则其对偶 min (max)问题无可行解。n 如果原max(min)问题有可行解，其对偶 min (max)问题无可行解，则原问题为无界解。2. 最优解判别定理定理 若原问题的某个可行解X0的目标函数值与对偶问题某个可行解Y0的目标函数值相等，则X0, Y0分别是相应问题的最优解证：由弱对偶定理推论1，结论是显然的。 即CX0 = Y0b CX, Y0b = CX0 Yb 。 证毕。定理(对

19、偶定理) 如果原问题和对偶问题都有可行解，则它们都有最优解，且它们的最优解的目标函数值相等。证：由弱对偶定理推论1可知，原问题和对偶问题的目标函数有界，故一定存在最优解。现证明定理的后一句话。 设 X0 为原问题的最优解，它所对应的基矩阵是 B， X0= B1 b，则其检验数满足 C CBB1A 0 令 Y0= CBB1，则有 Y0 A C ；而对原问题松弛变量的检验数有 0 CBB1I 0，即 Y0 0 。 显然Y0为对偶问题的可行解。因此有对偶问题目标函数值， W(Y0)=Y0b= CBB1 b 而原问题最优解的目标函数值为 Z(X0)=CX0= CBB1 b 故由最优解判别定理可知Y0

20、为对偶问题的最优解。证毕。该定理的证明告诉我们一个非常重要的概念：对偶变量的最优解等于原问题松弛变量的机会成本即对偶变量的最优解是原问题资源的影子价格4. 互补松弛互补松弛定理定理定理 设X0, Y0分别是原问题和对偶问题的可行解，U0为原问题的松弛变量的值、V0为对偶问题剩余变量的值。X0, Y0分别是原问题和对偶问题最优解的充分必要条件是 Y0 U0 + V0 X0 = 0. 证：由定理所设，可知有 A X0 + U0 = b X0, U0 0 (1) Y0 A V0 = C Y0, V0 0 (2)分别以Y0左乘(1)式，以X0右乘(2)式后，两式相减，得 Y0 U0 + V0 X0 =

21、 Y0 b C X0若 Y0 U0 + V0 X0 = 0，根据最优解判别定理， X0, Y0分别是原问题和对偶问题最优解。反之亦然。 证毕。Y0 U 0 + V 0 X 0 = 0 有什么应用u 若(Y 0 )i 0，则 (U 0 )i =0，意味着原问题第 i 约束行必须为 = 约束；对(X0 )i 0 亦如此.miuynjxviijj, 2 , 10, 2 , 100000因 Y0 ，U0 ， V0 ，X0 0 则有：在线性规划问题的最优解在线性规划问题的最优解中，如果对应某一约束条中，如果对应某一约束条件的对偶变量值为件的对偶变量值为非非0，则，则该约束条件取严格等式；该约束条件取严格

22、等式；反之如果约束条件反之如果约束条件取严格取严格不等式不等式，则，则 对应的对偶变对应的对偶变量值为量值为0。第三章 线性规划的对偶理论 与灵敏度分析 n线性规划的对偶问题 n对偶问题的基本性质n影子价格n对偶单纯形法n灵敏度分析n参数线性规划第三节 影子价格对偶问题的经济解释影子价格 1. 影子价格的数学解释：影子价格的数学解释：由对偶问题得基本性质可得：当线性规划原问题求得最优解由对偶问题得基本性质可得：当线性规划原问题求得最优解xj*(j=1, n), 其对偶问题也获得最优解其对偶问题也获得最优解 yi* (i=1, m), 且有且有11nmjjiijizc xb y 定义：在一对定义

23、：在一对 P 和和 D 中，若中，若 P 的某个约束条件的右端项的某个约束条件的右端项常数常数bi （第（第i种资源的拥有量）增加一个单位时，所引起种资源的拥有量）增加一个单位时，所引起目标函数最优值目标函数最优值 z* 的改变量称为第的改变量称为第 i 种资源的影子价格，种资源的影子价格，其值等于其值等于D问题中对偶变量问题中对偶变量 yi*。361）影子价格是一种）影子价格是一种边际价格边际价格在其它条件不变的情况下，单位资源数量的变化所引起在其它条件不变的情况下，单位资源数量的变化所引起的目标函数最优值的变化。即对偶变量的目标函数最优值的变化。即对偶变量 yi 就是第就是第 i 种资源种

24、资源的影子价格。即：的影子价格。即： )2 , 1(*miybZii 2）影子价格是一种）影子价格是一种机会成本机会成本影子价格是在资源最优利用条件下对单位资源的估影子价格是在资源最优利用条件下对单位资源的估价，这种估价不是资源实际的市场价格。因此，从另一价，这种估价不是资源实际的市场价格。因此，从另一个角度说，它是一种机会成本。个角度说，它是一种机会成本。37若第若第i 种资源的单位市场价格为种资源的单位市场价格为mi ，则有当，则有当yi* mi 时，企业愿意时，企业愿意购进这种资源，单位纯利为购进这种资源，单位纯利为 yi*mi ，则有利可图；如果，则有利可图；如果yi* mi ，则企业

25、有偿转让这种资源，可获单位纯利则企业有偿转让这种资源，可获单位纯利miyi * ，否则，企业无，否则，企业无利可图，甚至亏损。利可图，甚至亏损。3）影子价格在资源利用中的应用）影子价格在资源利用中的应用根据对偶理论的互补松弛性定理根据对偶理论的互补松弛性定理:Y*Xs=0 , YsX*=0.表明生产过程中表明生产过程中, 如果某种资源如果某种资源bi未得到充分利用时，该种资未得到充分利用时，该种资源的影子价格为源的影子价格为0；若当资源资源的影子价格不为；若当资源资源的影子价格不为0时，表明时，表明该种资源在生产中已耗费完。该种资源在生产中已耗费完。11 0; 0, nnijjiiiijjij

26、ja xbyya xb也 即时 ，而 当有384）影子价格对单纯形表计算的解释）影子价格对单纯形表计算的解释单纯形表中的检验数单纯形表中的检验数 miiijjjBjjyacPBCc11其中其中 cj 表示第表示第 j种产品的价格种产品的价格; 表示生产该种产品表示生产该种产品所消耗的各项资源的影子价格的总和所消耗的各项资源的影子价格的总和,即产品的隐含成本。即产品的隐含成本。 miiijya1当产值大于隐含成本时，即当产值大于隐含成本时，即 ，表明生产该项产品有，表明生产该项产品有利，可在计划中安排；否则利，可在计划中安排；否则 ，用这些资源生产别的，用这些资源生产别的产品更有利，不在生产中安

27、排该产品。产品更有利，不在生产中安排该产品。0 j 0 j 产品产品资源资源 I II可用量可用量机械设备机械设备 1 28原材料原材料A 4 016原材料原材料B 0 412 X *=(4，2，0，0, 4)T， z* =14cj23000CBXBbx1x2 x3x4x5203x1x5x2442100001-2-3/2-1/81/801000-3/2-1/800,125.0,5.1*3*2*1yyy经济意义经济意义：在在其它条件不变其它条件不变的情况下，的情况下，单位资源变化单位资源变化所引起的目标所引起的目标函数的最优值函数的最优值的变化。的变化。影子价格 (P)的最终单纯形表中松弛变量的

28、检验的最终单纯形表中松弛变量的检验数对应数对应(D)的最优解。的最优解。40具体来说：具体来说：这说明是其他条件不变的情况下，若设备增加一这说明是其他条件不变的情况下，若设备增加一台时，该厂按最优计划安排生产可多获利台时，该厂按最优计划安排生产可多获利1.5元；原材料元；原材料A增加增加1kg，可多获利，可多获利0.125元；原材料元；原材料B增加增加1kg，对获利无，对获利无影响。影响。 41从上图可看到，设备增加一台时，代表该约束条件的直线由移从上图可看到，设备增加一台时，代表该约束条件的直线由移至至，相应的最优解由，相应的最优解由(4，2)变为变为(4，2.5)，目标函数，目标函数z=2

29、4+32.5=15.5，即比原来的增大，即比原来的增大1.5。又若原材料。又若原材料A增加增加1kg时，代表该约束方程的直线由移至时，代表该约束方程的直线由移至，相应的最优解从，相应的最优解从(4，2)变为变为(4.25，1.875)，目标函数，目标函数z=4.25+31.875=14.125。比原。比原来的增加来的增加0.125。原材料。原材料B增加增加1kg时，该约束方程的直线由移时，该约束方程的直线由移至至，这时的最优解不变。，这时的最优解不变。42 这种估价是针对具体工厂的具体产品而存在的一种特殊这种估价是针对具体工厂的具体产品而存在的一种特殊价格，称它为价格，称它为“影子价格影子价格

30、”。在该厂现有资源和现有生产方。在该厂现有资源和现有生产方案的条件下，设备的每小时租费为案的条件下，设备的每小时租费为1.51.5元，元，1kg1kg原材料原材料A A的出的出让费为除成本外再附加让费为除成本外再附加0.1250.125元，元，1kg1kg原材料原材料B B可按原成本出可按原成本出让，这时该厂的收入与自己组织生产时获利相等。让，这时该厂的收入与自己组织生产时获利相等。 影子价格随具体情况而异，在完全市场经济的条件下，影子价格随具体情况而异，在完全市场经济的条件下，当某种资源的市场价低于影子价格时，企业应买进该资源用当某种资源的市场价低于影子价格时，企业应买进该资源用于扩大生产；

31、而当某种资源的市场价高于企业影子价格时，于扩大生产；而当某种资源的市场价高于企业影子价格时，则企业的决策者应把已有资源卖掉。可见影子价格对市场有则企业的决策者应把已有资源卖掉。可见影子价格对市场有调节作用。调节作用。 影子价格越影子价格越大大，说明这种资源越是相对，说明这种资源越是相对 紧缺紧缺。相反，。相反，影子价格越影子价格越小小，说明这种资源相对，说明这种资源相对宽松宽松。第三章 线性规划的对偶理论 与灵敏度分析 n线性规划的对偶问题 n对偶问题的基本性质n影子价格n对偶单纯形法n灵敏度分析n参数线性规划第四节 对偶单纯形法 对偶单纯形法是求解线性规划原问题的另一个基本方法。它是根据对偶

32、原理和单纯形法原理而设计出来的，因此称为对偶单纯形法。不要简单理解为是求解对偶问题的单纯形法。 原来, 求解单纯形法的基本思路是： 对原问题的一个基可行解，判别是否所有检验数cj-zj0(j=1,n)。若是，又基变量中无非零人工变量，即找到了问题最优解；若为否，再找出相邻的目标函数值更大的基可行解，并继续判别，只要最优解存在，就一直循环进行到找出最优解为止。一、基本思路 原单纯型迭代要求每步都是基可行解达到最优解时，检验数 cjzj 0 (max) 或 cjzj 0 (min). 但对于(min, )型所加的剩余变量无法构成初始基础可行解，因此通过加人工变量来解决. 此时, 使用的大M法和二阶

33、段法较繁. 能否从剩余变量构成的初始基非可行解出发迭代，但保证检验数满足最优条件， cjzj 0 (max) 或 cjzj 0 (min) 每步迭代保持检验数满足最优条件，但减少非可行度.46找出一个DP的可行基LP是否可行（XB 0）保持DP为可行解情况下转移到LP的另一个基本解最优解是否循环结束找出一个对偶问题的可行基，保持对偶问题为可行解的条件下，判断找出一个对偶问题的可行基，保持对偶问题为可行解的条件下，判断XB是否可行（是否可行（XB为非负），若否，通过变换基解，直到找到原问题基可行为非负），若否，通过变换基解，直到找到原问题基可行解（即解（即XB为非负），这时原问题与对偶问题同时达

34、到可行解，由对偶定为非负），这时原问题与对偶问题同时达到可行解，由对偶定理可得最优解。理可得最优解。二、迭代步骤1.确定出变量 找非可行解中最小者，即 min bi | bi6 6 时有：时有： z z1010。 6当当-6-6时，基变量时，基变量x x3 3 将小于零，用对偶单纯形法求解得：将小于零，用对偶单纯形法求解得： 611613 得得: :cj21000CB基基bx1x2x3x4x5021x3x1x20100011005/41/41/415/21/23/2cjzj0001/41/24521541274123cj21000CB基基bx1x2x3x4x5021x5x1x2010001-2

35、/15-1/151/5-1/61/60100cjzj00-1/151/3061161300,0,0,0,618319 z 当当-18-18时，基变量时，基变量x x1 1 将小于零，用对偶单纯形法求解得：将小于零，用对偶单纯形法求解得： cj21000CB基基bx1x2x3x4x5021x5x1x2010001-2/15-1/151/5-1/61/60100cjzj00-1/151/306116130初等变换得初等变换得 ：cj21000CB基基bx1x2x3x4x5021x5x3x2-2-153001010-1/2-2/51/2100cjzj-1001/3021725452112得得:-24

36、:-24-18 -18 0,0,0,0,00217254521122112 zcj21000CB基基bx1x2x3x4x5021x5x3x2-2-153001010-1/2-2/51/2100cjzj-1001/3021725452112 当当-24-24时时, , 将小于零，但将小于零，但 所在行元素均为正；故这时问题无可所在行元素均为正；故这时问题无可行解。行解。 2x2xZ()随参数随参数的变化见下页图所示。的变化见下页图所示。 目标函数目标函数 值随值随 值变化的情况如下图所示：值变化的情况如下图所示：)(zZ() 12 6 0 -6 -18 -24 3.0 7.0 10.0 图 2

37、当当 时时Z=10 当当 时时 当当-24-24-18 -18 时时无可行解无可行解 当当 时时66641217z618319 z2112 z 当当-24-24时时某工厂计划期内要安排生产某工厂计划期内要安排生产、两种产品，已知生产单位两种产品，已知生产单位产品所需的设备台时和产品所需的设备台时和A A、B B两种原材料的消耗、以及可获利润两种原材料的消耗、以及可获利润如表所示，问应如何安排计划使该工厂获利最多？如表所示，问应如何安排计划使该工厂获利最多？ 1.1.用单纯形法求解，并指出对偶规划的解；用单纯形法求解，并指出对偶规划的解；2.2.若若b b1 1和和b b3 3不变，则不变，则b

38、 b2 2在什么范围内变化时，问题的最优基不变；在什么范围内变化时，问题的最优基不变； 3. c2在什么范围内变化时最优解不变；在什么范围内变化时最优解不变；4.增加一种新产品增加一种新产品，它的技术系数是，它的技术系数是(2，6，3)T，利润系数是，利润系数是5， 问该厂问该厂是否应生产该产品和生产多少？是否应生产该产品和生产多少？5.若生产产品若生产产品的工艺结构有改进，其技术系数变为（的工艺结构有改进，其技术系数变为（2， 5 ，2)T，利润系，利润系数为数为4，试分析对生产计划有什么影响？，试分析对生产计划有什么影响？课堂作业课堂作业 可可利利用用资资源源 设设备备 原原材材料料 A

39、A 原原材材料料 B B 1 1 4 4 0 0 2 2 0 0 4 4 8 8 台台时时 1 16 6k kg g 1 12 2k kg g 利利润润 2 2 3 3 ？元元 cj 2 3 3 0 0 0 CB XB b x1 x2 x3 x4 x5 0 0 0 x3 x4 x5 8 16 12 1 4 0 2 0 4 1 0 0 0 1 0 0 0 1 - -z 0 2 3 0 0 0 解（1） 初始表 X(3)=(4，2，0，0, 4)T， z3 =14cj23000CBXBbx1x2 x3x4x5203x1x5x24421000010-21/21/41/2-1/8010-1400-3/2-1/80最终表0,125. 0, 5 . 1*3*2*1yyy解：（2）所以，b2的变化范围是-8，16；b2的变化范围是8，32。 000125050 250 2440 0 2211b.bBbB 可得