第2章线性规划的对偶理论与灵敏度分析

1、.第第2章章 线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析2.1 线性规划的对偶问题线性规划的对偶问题2.2 对偶问题的基本性质对偶问题的基本性质2.3 影子价格影子价格2.4 对偶单纯形法对偶单纯形法2.5 灵敏度分析灵敏度分析.2.1.1 对偶问题的提出对偶问题的提出例例1 第一章例第一章例1中美佳公司利用公司资源生产两种家中美佳公司利用公司资源生产两种家电产品时，其线性规划问题为：电产品时，其线性规划问题为：12max2zxxs.t.2515x 126224xx125xx12,0 x x (P).2.1.1 对偶问题的提出对偶问题的提出这时，如果有另一家公司想购买美佳公司

2、的资源全部这时，如果有另一家公司想购买美佳公司的资源全部资源，那么它至少应出多少的价格，才会使美佳公司资源，那么它至少应出多少的价格，才会使美佳公司愿意出让？愿意出让？解：设其购买三种资源的价格分别为解：设其购买三种资源的价格分别为y1, y2, y3, 总花费总花费为为w，则：，则：123min15245wyyy2312362521 yyyyys.t.y1, y2, y30 (D).2.1.1 对偶问题的提出对偶问题的提出123min15245wyyy2312362521 yyyyys.t.y1, y2, y3012max2zxxs.t.2515x 126224xx125xx12,0 x x

3、 (P) (D).2.1.1 对偶问题的提出对偶问题的提出1 122max.nnzc xc xc x11 1122111.jjnna xa xa xa xb21 1222222.jjnna xa xa xa xb1 122.mmmjjmnnma xaxa xa xb.s.t.0(1,., )jxjn1y2ymy.1122.jjmjmja ya ya yc.2.1.1 对偶问题的提出对偶问题的提出1 122min.mmwb xb yb ys.t.111212111.iimma ya ya ya yc121222222.iimma ya ya yayc0(1,2,.,)jyim.1122.nnin

4、imnmna ya ya yayc1x2xmx.1 122.iiinnia xa xa xb.2.1.2 对偶问题的对称形式对偶问题的对称形式max. .0zCXAXbstX(P)min. .0wYbYAcstY(D)123(,)Yy yy对称式对偶模型：对称式对偶模型：（1）其变量均具有非负约束）其变量均具有非负约束（2）约束条件当目标函数求极大时均取）约束条件当目标函数求极大时均取“ ”（3）约束条件当目标函数求极大时均取）约束条件当目标函数求极大时均取“ ”.2.1.2 对偶问题的对称形式对偶问题的对称形式例例2：写出下面问题的对偶规划：写出下面问题的对偶规划maxZ= 5X1 +6X2

5、 3X1 -2X2 74X1 +X2 9X1 , X2 0minW=7y1 +9y23y1+4y2 5 -2y1 +y2 6y1, y2 0.2.1.2 对偶问题的对偶问题的“非对称非对称”形式形式原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标函数目标函数 max zn个个00无约束无约束变量变量m个个 =约束条件约束条件约束条件右端项约束条件右端项目标函数变量的系数目标函数变量的系数目标函数目标函数 min wn个个=约束条件约束条件变量变量m个个00无约束无约束约束条件右端项约束条件右端项目标函数变量的系数目标函数变量的系数.2.1.2 对偶问题的对称

6、形式对偶问题的对称形式例例3：写出下面问题的对偶规划：写出下面问题的对偶规划1234min235zxxxx1234235xxxx2134224xxxx2413236xxxx12340;,0,xx xx无约束无约束.2.1.2 对偶问题的对称形式对偶问题的对称形式解：解：123max546wyyy1232322yyx213223xyy1233325yyy 1230;0,yyy1231323yyy无约束无约束.2.1.2 对偶问题的一般形式对偶问题的一般形式练习：练习： 写出下面线性规划的对偶规划模型写出下面线性规划的对偶规划模型12max23zxxs.t.1223xx1225xx 1231xx1

7、20,xx无约束无约束123min224zxxxs.t.1232342xxx123,0,x xx无约束无约束1232333xxx1232432xxx.2.2 对偶问题的基本性质对偶问题的基本性质1. 对称性对称性 对偶问题的对偶问题是原问题对偶问题的对偶问题是原问题 （P）与（）与（D）互为对偶，没有要求原问题一定）互为对偶，没有要求原问题一定要是要是max型，对偶问题一定要是型，对偶问题一定要是min型型2. 弱对偶性弱对偶性 设设X, Y分别为分别为(P), (D)的任一可行解，则的任一可行解，则CX Yb证：因为证：因为X, Y分别为分别为(P), (D)的可行解，那么有：的可行解，那么

8、有：AX b YAXYb YA C YAX CX CX Yb.2.2 对偶问题的基本性质对偶问题的基本性质2. 弱对偶性弱对偶性 由上述弱对偶性可推出：由上述弱对偶性可推出：若若(P)为无界解，则为无界解，则(D)无可行解无可行解若若(D)为无界解，则为无界解，则(P)无可行解无可行解CXYb？课本中关于弱对偶性的推论如何理解？课本中关于弱对偶性的推论如何理解.2.2 对偶问题的基本性质对偶问题的基本性质推论推论1 原问题任一可行解的目标函数值是其对偶问题原问题任一可行解的目标函数值是其对偶问题目标函数值的下界，反之，对偶问题任一可行解的目目标函数值的下界，反之，对偶问题任一可行解的目标函数值

9、是其原问题目标函数值的上界。标函数值是其原问题目标函数值的上界。推论推论2 若原问题有可行解且目标函数值无界，则其对若原问题有可行解且目标函数值无界，则其对偶问题无可行解；反之，对偶问题有无界解，原问题偶问题无可行解；反之，对偶问题有无界解，原问题无可行解。（但逆向不成立）无可行解。（但逆向不成立）推论推论3 若原问题有可行解，对偶问题无可行解，则原若原问题有可行解，对偶问题无可行解，则原问题目标函数值无界；反之，对偶问题有可行解，而问题目标函数值无界；反之，对偶问题有可行解，而原问题无可行解，则对偶问题的目标函数值无界。原问题无可行解，则对偶问题的目标函数值无界。.2.2 对偶问题的基本性质

10、对偶问题的基本性质3. 最优性最优性 设设 ， 分别为分别为(P)与与(D)的可行解，且的可行解，且 ，则则 ，证：对任一可行解证：对任一可行解X, 由弱对偶性由弱对偶性 ，故故 ，同理，同理XYCXYb*XX*YYCXYbCX*XX*YY.2.2 对偶问题的基本性质对偶问题的基本性质4. 强对偶性（对偶定理）强对偶性（对偶定理） 若若(P)有最优解，则有最优解，则(D)也有最优解，且二者最优值也有最优解，且二者最优值相等相等证：对证：对(P)增加松弛变量增加松弛变量Xs, 化为：化为：max0szCXXs.t.,0sX X sAXIXb.2.2 对偶问题的基本性质对偶问题的基本性质4. 强对

11、偶性（对偶定理）强对偶性（对偶定理） 证证：（续）：（续）设其最优基为设其最优基为B, 终表为：终表为：cj C 0CB XB B-1b B-1A B-1I 检验数检验数C - CBB-1A 0 CBB-1IC - CBB-1A 00 CBB-1I 0取取1BYC B.2.2 对偶问题的基本性质对偶问题的基本性质4. 强对偶性（对偶定理）强对偶性（对偶定理） 证证：（续）：（续）则则 满足：满足：1BYC B0CYA00YYAC0Y 是是(D)的可行解，且的可行解，且 ，由最有性定理，可得：由最有性定理，可得： 1*BYbC B bzY1*BYYC B.2.2 对偶问题的基本性质对偶问题的基本

12、性质4. 强对偶性（对偶定理）强对偶性（对偶定理） (1)由性质由性质4可知，对偶问题最优解的表可知，对偶问题最优解的表达式达式Y* = ?(2)求求Y*是否要重新求解是否要重新求解(D) CBB-1 不需要，可以从原问题不需要，可以从原问题(P)的单纯形终的单纯形终表获得表获得.2.2 对偶问题的基本性质对偶问题的基本性质例如，在前面美佳公司的生产计划中，其单纯形终表为：例如，在前面美佳公司的生产计划中，其单纯形终表为： 2 1 0 0 0 x1 x2 x3 x4 x5 0 x3 15/22 x1 7/21 x2 3/2 0 0 1 5/4 15/2 1 0 0 1/4 -1/2 0 1 0

13、 -1/4 3/2 0 0 0 -1/4 -1/2jjcBXBC1B bi.2.2 对偶问题的基本性质对偶问题的基本性质由上表可直接得到问题由上表可直接得到问题(P)的最优解和最优值：的最优解和最优值： X* = (7/2, 3/2, 15/2, 0, 0)T Z* = 8.5根据强对偶性可得：根据强对偶性可得： Y* = (0, 1/4, 1/2) Y* = 8.5.2.2 对偶问题的基本性质对偶问题的基本性质5. 互补松弛性（松紧定理）互补松弛性（松紧定理）设设 ， 分别为分别为(P)和和(D)的可行解，则：的可行解，则： , 是最优解是最优解 其中，其中， ， 为最优解中松弛变量部分。为

14、最优解中松弛变量部分。XYXY0ssYXY XsXsY.2.2 对偶问题的基本性质对偶问题的基本性质证：证：将将(P)、(D)的约束条件化为等式：的约束条件化为等式：sAXIXbsYA Y IC因为因为 ， 是最优解，所以是最优解，所以 ，即：，即：XYCXYb()()ssYA Y I XY AXIXssYAXY XYAXYX而而0,0ssY XYX故只有：故只有：0ssY XYX.2.2 对偶问题的基本性质对偶问题的基本性质原始问题变量原始问题变量原始问题的松弛变量原始问题的松弛变量1xjxnx1nxn ixn mx1mymjym ny1yiymy对偶问题变量对偶问题变量对偶问题的松弛变量对

15、偶问题的松弛变量0jmjx y0in iy x在如上的一对变量中，其中一个大于在如上的一对变量中，其中一个大于0，另一个一定等于，另一个一定等于0.2.2 对偶问题的基本性质对偶问题的基本性质在线性规划问题中在线性规划问题中（1）如果对应于某一约束条件的对偶变量值为）如果对应于某一约束条件的对偶变量值为非非0，则该约束条件取严格等式，则该约束条件取严格等式（2）如果约束条件取严格不等式，则其对应的）如果约束条件取严格不等式，则其对应的对偶变量一定为对偶变量一定为0.2.2 对偶问题的基本性质对偶问题的基本性质例例4 已知如下线性规划问题已知如下线性规划问题12345min23523wxxxxx

16、s.t.12345234xxxxx12345233xxxxx已知其对偶问题最优解已知其对偶问题最优解 , , 试利用对偶理论，找出原问题的最优解。试利用对偶理论，找出原问题的最优解。 *145y *235y *5z .2.2 对偶问题的基本性质对偶问题的基本性质解：先写出其对偶问题解：先写出其对偶问题12max43zyys.t.1222yy123yy12235yy122yy1233yy12,0y y (1)(2)(3)(4)(6)将将 ， 的值代入的值代入左边左边5个约束条件中，个约束条件中，得约束（得约束（2），（），（3），），（4）为严格等式，）为严格等式，由互补松弛性定理得：由互补松弛

17、性定理得：*1y*2y234xxx又又 , ，所以，所以对应于原问题的约束对应于原问题的约束条件取等式条件取等式*1y*20y .2.2 对偶问题的基本性质对偶问题的基本性质所以：所以：12345234xxxxx12345233xxxxx1534xx1523xx*(1,0,0,0,1)TX .2.3 对偶问题的经济解释对偶问题的经济解释2.3.3 对偶松弛变量的经济解释对偶松弛变量的经济解释 产品的差额成本产品的差额成本2.3.1 对偶问题最优解的经济解释对偶问题最优解的经济解释 资源的影子价格资源的影子价格2.3.2 对偶约束的经济解释对偶约束的经济解释 产品的机会成本产品的机会成本2.3.

18、4 互补松弛关系的经济解释互补松弛关系的经济解释.2.3.1 影子价格影子价格根据前述对偶定理可知，对偶问题最优解的表根据前述对偶定理可知，对偶问题最优解的表达式达式Y* = CBB-1CBB-1 对偶问题的最优解对偶问题的最优解 买主的最低出价买主的最低出价CBB-1 原问题资源的影子价格原问题资源的影子价格 当该资源增加当该资源增加1单位时引起的总收入的增量单位时引起的总收入的增量 卖主的内控价格卖主的内控价格设设D的最优解为的最优解为Z*（注：与（注：与P最优值相同）最优值相同）, 则：则：*1 12 2.m mZY by by by b*iiZyb.2.3.1 影子价格影子价格例例5

19、请根据美佳公司生产计划安排的单纯形终表请根据美佳公司生产计划安排的单纯形终表指出：指出：资源设备资源设备A、B和调试工序的影子价格，并解释和调试工序的影子价格，并解释其经济意义其经济意义.2.3.1 影子价格影子价格例例5 美佳公司生产计划安排的单纯形终表如下：美佳公司生产计划安排的单纯形终表如下： 2 1 0 0 0 x1 x2 x3 x4 x5 0 x3 15/22 x1 7/21 x2 3/2 0 0 1 5/4 15/2 1 0 0 1/4 -1/2 0 1 0 -1/4 3/2 0 0 0 -1/4 -1/2jjcBXBC1B bi.2.3.1 影子价格影子价格解：解：1*0Ay设备

20、 台时的影子价格 21*4y设 备 B台 时 的 影 子 价 格 31*2y调试工序台时的影子价格 即再增加设备即再增加设备A台时，利润不会增加台时，利润不会增加即再增加即再增加1个设备个设备B台时，利润增加台时，利润增加1/4元元即再增加即再增加1个调试台时，利润增加个调试台时，利润增加1/2元元.2.3.1 影子价格影子价格2515x 126224xx125xx3155152273622422 73522x30, y1=0 x4=0, y20 x5=0, y30.2.3.1 影子价格影子价格因为，影子价格只是表示某种资源在企业内部的因为，影子价格只是表示某种资源在企业内部的虚拟价格，而不等

21、于资源的市场价格虚拟价格，而不等于资源的市场价格.2.3.1 影子价格影子价格影子价格在管理决策中的应用影子价格在管理决策中的应用这种资源对目标增益的影响越大这种资源对目标增益的影响越大这种资源对该企业越稀缺、贵重这种资源对该企业越稀缺、贵重管理措施：管理措施：通过挖掘革新、降低消耗或及时补充该种资源通过挖掘革新、降低消耗或及时补充该种资源重视对该资源的管理；重视对该资源的管理；.2.3.1 影子价格影子价格某种资源的影子价格为某种资源的影子价格为0，表明：，表明：这种资源对该企业而言，是相对富余的这种资源对该企业而言，是相对富余的管理措施：管理措施：通过对企业内部的改造、挖掘和增加对影子价格

22、通过对企业内部的改造、挖掘和增加对影子价格大于零的资源的投入，使原有剩余资源得到充分大于零的资源的投入，使原有剩余资源得到充分利用利用以市场价出售以市场价出售.2.3.1 影子价格影子价格影子价格影子价格 市场价格，则买进该资源市场价格，则买进该资源影子价格影子价格 0 xn+i = 0 yi0 xn+i = 0 0in iy xxj0 ym+j = 0 xj=0 ym+j 0 在利润最大化的生产计划中在利润最大化的生产计划中(1) 影子价格大于影子价格大于0的资源没有剩余；的资源没有剩余； 有剩余的资源影子价格为有剩余的资源影子价格为0(2)安排生产机会成本等于利润的产品；机会成本大于利润的

23、产安排生产机会成本等于利润的产品；机会成本大于利润的产品不安排生产品不安排生产.2.4 对偶单纯形法对偶单纯形法二、对偶单纯形法基本步骤二、对偶单纯形法基本步骤 max型型(1) 作初始表，要求全部作初始表，要求全部j 0 ( 0)(2) 判定：判定： B-1 b全全 0，停停。否则，取否则，取max B-1 b =(B-1 b)l B-1 b0令第令第 l 行的行的Xj l为换出变量为换出变量.(3)确定换入变量确定换入变量 若若Xi l行的行的alj 全全 0 ，停，原问题无可行解。，停，原问题无可行解。 若若Xi l行的行的alj 有有alj 0 ,则求则求j k =min =aljal

24、kalj 0 Xk为换入变量为换入变量2.4 对偶单纯形法对偶单纯形法(4) 以以alk 为主元，换基迭代为主元，换基迭代.2.4 对偶单纯形法对偶单纯形法例例6 用对偶单纯形法求下述线性规划问题用对偶单纯形法求下述线性规划问题123min15245wyyy2312362521 yyyyys.t.y1, y2, y30.2.4 对偶单纯形法对偶单纯形法解：先将问题改写为：解：先将问题改写为：,123max15245wyyy 234123562521yyyyyyys.t.yi0(i = 1, , 5).2.4 对偶单纯形法对偶单纯形法在上述两个约束条件两端乘在上述两个约束条件两端乘“-1”,12

25、3min15245wyyy 234123562521yyyyyyy s.t.yi0(i = 1, , 5).2.4 对偶单纯形法对偶单纯形法列出单纯形表，用对偶单纯形法进行计算：列出单纯形表，用对偶单纯形法进行计算：-15 -24 -5 0 0 y1 y2 y3 y4 y50 y3 -20 y4 -1 0 -6 -1 1 0-5 -2 -1 0 1 -15 -24 -5 0 0jcBXBC1B bji* .2.4 对偶单纯形法对偶单纯形法列出单纯形表，用对偶单纯形法进行计算：列出单纯形表，用对偶单纯形法进行计算：-15 -24 -5 0 0 y1 y2 y3 y4 y50 y3 -20 y4

26、-1 0 -6 -1 1 0-5 -2 -1 0 1 -15 -24 -5 0 0jcBXBC1B bji* .2.4 对偶单纯形法对偶单纯形法-15 -24 -5 0 0 y1 y2 y3 y4 y5-24 y2 1/4-5 y3 1/2-5/4 1 0 -1/4 1/415/2 0 1 1/2 -3/2 -15/2 0 0 -7/2 -3/2jcBXBC1B bjiY*=(0,1/4,1/2,0,0), w = 8.5(元元).2.4 对偶单纯形法对偶单纯形法从上述对偶单纯形法的求解中，可以看出其优点：从上述对偶单纯形法的求解中，可以看出其优点：(1) 初始解可以是非可行解，当检验数均为非

27、正数时，初始解可以是非可行解，当检验数均为非正数时，就可以进行基变换，此时无需加入人工变量，因此可就可以进行基变换，此时无需加入人工变量，因此可以简化计算以简化计算(2) 当变量多余约束条件时，用对偶单纯形法计算可以当变量多余约束条件时，用对偶单纯形法计算可以减少计算工作量减少计算工作量(3) 在灵敏度析及整数规划的割平面法中，有时需要用在灵敏度析及整数规划的割平面法中，有时需要用对偶单纯形法以简化问题的处理对偶单纯形法以简化问题的处理.2.4 对偶单纯形法对偶单纯形法但对偶单纯形法也有其局限性：但对偶单纯形法也有其局限性：对于多数线性规划问题，在初始单纯形表中其对偶问对于多数线性规划问题，在

28、初始单纯形表中其对偶问题应是基可行解这一点很难实现，所以对偶单纯形法题应是基可行解这一点很难实现，所以对偶单纯形法一般不单独使用一般不单独使用.2.4 对偶单纯形法对偶单纯形法练习练习1：用对偶单纯形法求解：用对偶单纯形法求解123min234wxxx12312323234xxxxxxs.t.xj0(j = 1, , 3).2.4 对偶单纯形法对偶单纯形法练习练习2：用对偶单纯形法求解：用对偶单纯形法求解124max43zxxx 1234123423242xxxxxxxxs.t.xj0(j = 1, , 4).2.5 灵敏度分析灵敏度分析灵敏度灵敏度指系统或事物因周围条件变化显示出来的敏感程度

29、指系统或事物因周围条件变化显示出来的敏感程度1jjBjcC B P10B b最优性最优性可行性可行性.2.5 灵敏度分析灵敏度分析灵敏度分析步骤灵敏度分析步骤1. 将参数的改变通过计算反映到最终单纯形表上来将参数的改变通过计算反映到最终单纯形表上来2. 检查员问题是否仍为可行解检查员问题是否仍为可行解3. 检查对偶问题是否仍为可行解检查对偶问题是否仍为可行解原问题原问题对偶问题对偶问题结论或继续计算的步骤结论或继续计算的步骤可行解可行解可行解可行解问题的最优解不变问题的最优解不变可行解可行解非可行解非可行解用单纯形法继续迭代求解用单纯形法继续迭代求解非可行解非可行解可行解可行解用对偶单纯形法继

30、续迭代求解用对偶单纯形法继续迭代求解非可行解非可行解非可行解非可行解引入人工变量，重新计算求解引入人工变量，重新计算求解.2.5.1 分析分析cj的变化的变化例例7在第在第1章例章例1的美佳公司例子中的美佳公司例子中：（1）若家电）若家电1的利润将至的利润将至1.5元元/件，美佳公司最优生件，美佳公司最优生产计划有何变化产计划有何变化（2）若家电）若家电1的利润不变，则家电的利润不变，则家电2的利润在什么范的利润在什么范围内变化时，该公司的最优生产计划将不发生改变？围内变化时，该公司的最优生产计划将不发生改变？.jcBXBC1B bji2.5.1 分析分析cj的变化的变化 2 1 0 0 0

31、x1 x2 x3 x4 x50 x3 15/22 x1 7/21 x2 3/2 0 0 1 5/4 15/2 1 0 0 1/4 -1/2 0 1 0 -1/4 3/2 0 0 0 -1/4 -1/21.5 21.52 1/8-9/4.1.5 2 0 0 0 x1 x2 x3 x4 x50 x4 61.5 x1 22 x2 3 0 0 5/4 1 -6 1 0 -1/5 0 1 0 1 1/5 0 0 0 0 -1/10 0 -3/2jjcBXBC1B bi因为，检验数全非正，该解为最优解，即：因为，检验数全非正，该解为最优解，即：*(2,3,6,0,0)TX *19()BZC B b元2.5

32、.1 分析分析cj的变化的变化.2.5.1 分析分析cj的变化的变化 2 0 0 0 x1 x2 x3 x4 x50 x3 15/22 x1 7/2 x2 3/2 0 0 1 5/4 15/2 1 0 0 1/4 -1/2 0 1 0 -1/4 3/2 0 0 0jjcBXBC1B bi1111-1/4-1/2114413221104413022为保持最优解不变，应有：为保持最优解不变，应有：113.2.5.2 分析分析bi的变化的变化例例8在第在第1章例章例1的美佳公司例子中的美佳公司例子中：（1）若设备）若设备A和调试工序的每天能力不变，而设备和调试工序的每天能力不变，而设备B每天的能力增

33、加到每天的能力增加到32h，分析公司最优计划的变化；，分析公司最优计划的变化；（2）若设备）若设备A和设备和设备B每天可用能力不变，则调试工每天可用能力不变，则调试工序能力在什么范围内变化时，问题的最优基不变？序能力在什么范围内变化时，问题的最优基不变？.2.5.2 分析分析bi的变化的变化 2 0 0 0 x1 x2 x3 x4 x50 x3 15/22 x1 7/2 x2 3/2 0 0 1 5/4 15/2 1 0 0 1/4 -1/2 0 1 0 -1/4 3/2 0 0 0jjcBXBC1B bi11-1/4-1/2.2.5.2 分析分析bi的变化的变化解：解：（1）由已知得，）由已

34、知得， 则：则：080b 114/515/ 201001/ 41/ 28201/ 43/ 202bBb .2.5.2 分析分析bi的变化的变化解：解：114/515/ 201001/ 41/ 28201/ 43/ 202bBb 115/ 21035/ 27/ 2211/ 23/ 221/ 2bB bb.2.5.2 分析分析bi的变化的变化 2 0 0 0 x1 x2 x3 x4 x50 x3 2 x1 x2 0 0 1 5/4 15/2 1 0 0 1/4 -1/2 0 1 0 -1/4 3/2 0 0 0jjcBXBC1B bi11-1/4-1/215/27/23/235/211/2-1/2

35、.2.5.2 分析分析bi的变化的变化 2 0 0 0 x1 x2 x3 x4 x50 x3 2 x1 x4 0 5 1 0 0 1 1 0 0 1 0 -4 0 1 -6 0 -1 0 0 -2jjcBXBC1B bi11 15 5 2因为，检验数全非正，该解为最优解，即：此时，美因为，检验数全非正，该解为最优解，即：此时，美佳公司只生产佳公司只生产5件家电件家电1.2.5.2 分析分析bi的变化的变化解：解：（2）设调试工序每天可用能力为）设调试工序每天可用能力为 h(5)115214/515/ 20101/ 41/ 20201/ 43/ 232bBb .2.5.2 分析分析bi的变化的变

36、化解：解：115151522215/ 21717/ 22223/ 2333222bB bb +当当 时，问题的最优基不变，可解得时，问题的最优基不变，可解得 0b 11 由此，调试工序的能力在由此，调试工序的能力在4h6h之间之间 .2.5.3 增加一个变量增加一个变量xj的分析的分析增加一个变量在实际问题中反映为增加一个新的品种，增加一个变量在实际问题中反映为增加一个新的品种，其分析步骤如下：其分析步骤如下：1. 计算计算2. 计算计算3. 若若 ，原最优解不变，只需将计算得到的，原最优解不变，只需将计算得到的 直接写入最终单纯形表中；若直接写入最终单纯形表中；若 ，则按单纯，则按单纯形法继

37、续迭代计算找出最优解。形法继续迭代计算找出最优解。*1mjjijiica y1jjpB P0jjPj0j.2.5.3 增加一个变量增加一个变量xj的分析的分析例例9在第在第1章例章例1的美佳公司例子中的美佳公司例子中，设该公司又计划推出，设该公司又计划推出新型号的家电新型号的家电3，生产一件所需设备，生产一件所需设备A、B及调试工序及调试工序的时间分别为的时间分别为3h, 4h, 2h, 该产品的预期盈利为该产品的预期盈利为3元元/件，件，试分析该种产品是否值得投产；如投产，对该公司的试分析该种产品是否值得投产；如投产，对该公司的最优生产计划有何影响？最优生产计划有何影响？.2.5.3 增加一

38、个变量增加一个变量xj的分析的分析解：解：设该公司生产家电设该公司生产家电3的数量为的数量为x6, 由已知可得：由已知可得：c6 = 3, P6 = (3, 4, 2)T3*66133(0,1/ 4,1/ 2) 412ijiica y 由原最终单纯形表可得，由原最终单纯形表可得，Y* = (0, 1/4, 1/2)1615/ 415/ 23701/ 41/ 24001/ 43/ 222jPB P .2.5.3 增加一个变量增加一个变量xj的分析的分析解：解：将其反映到最终单纯形表中：将其反映到最终单纯形表中： 2 1 0 0 0 3 x1 x2 x3 x4 x5 x6 0 x3 15/2 2

39、x1 7/2 1 x2 3/2 0 0 1 5/4 15/2 -7 1 0 0 1/4 -1/2 0 0 1 0 -1/4 3/2 2 - - 3/4 0 0 0 -1/4 -1/2 1jjcBXBC1B bi* .2.5.3 增加一个变量增加一个变量xj的分析的分析解：解：将其反映到最终单纯形表中：将其反映到最终单纯形表中： 2 1 0 0 0 3 x1 x2 x3 x4 x5 x6 0 x3 51/4 2 x1 7/2 3 x6 3/4 0 7/2 1 3/8 -9/4 0 1 0 0 1/4 -1/2 0 0 1/2 0 -1/8 3/4 1 0 -1/2 0 -1/8 -5/4 0jj

40、cBXBC1B bi此时，美佳公司的最优生产计划为每天生产此时，美佳公司的最优生产计划为每天生产7/2件家电件家电1, 3/4件家电件家电2。.2.5.4 分析参数分析参数aij的变化的变化若变量若变量xj在最终单纯形表中为非基变量，其约束条件在最终单纯形表中为非基变量，其约束条件中系数中系数aij的变化分析可参照增加一个变量的变化分析可参照增加一个变量xj的分析的分析若变量若变量xj在最终单纯形表中为基变量，则在最终单纯形表中为基变量，则aij的变化将的变化将使相应的使相应的B和和B-1发生变化，从而有可能出现原问题和发生变化，从而有可能出现原问题和对偶问题均为非可行解的情况，此时，需引入人

41、工变对偶问题均为非可行解的情况，此时，需引入人工变量先将原问题的解转化为可行解，再用单纯形法求解。量先将原问题的解转化为可行解，再用单纯形法求解。.2.5.4 分析参数分析参数aij的变化的变化例例10在第在第1章例章例1的美佳公司例子中的美佳公司例子中，若家电，若家电2每件需设备每件需设备A, B和调试工序工时变为和调试工序工时变为8h, 4h, 1h, 该产品的利润变该产品的利润变为为3元元/件，试重新确定该公司最优生产计划。件，试重新确定该公司最优生产计划。解：解：先将生产工时变化后的新家电先将生产工时变化后的新家电2看作是一种新产品，看作是一种新产品，生产量为生产量为 ，计算，计算 、

42、 ，并反映到最终单纯，并反映到最终单纯形表中：形表中：22p2x. 2 1 3 0 0 0 x1 x2 x3 x4 x5 0 x3 15/2 2 x1 7/2 1 x2 3/2 0 0 11/2 1 5/4 -15/2 1 0 1/2 0 1/4 -1/2 0 1 1/2 0 -1/4 3/2 0 0 3/2 0 -1/4 1/2jjcBXBC1B bi2.5.4 分析参数分析参数aij的变化的变化2x* 因因 已变换为已变换为 ，故用单纯形法将，故用单纯形法将 替换出原基替换出原基变量中的变量中的 ，并在下一表中不再保留，并在下一表中不再保留 2x2x2x2x2x. 2 3 0 0 0 x1

43、 x3 x4 x5 0 x3 -9 2 x1 2 3 3 0 0 1 4 -24 1 0 0 1/2 -2 0 1 0 -1/2 3 0 0 0 1/2 -5 2.5.4 分析参数分析参数aij的变化的变化该表中原问题与对偶问题均为非可行解，故先设法使该表中原问题与对偶问题均为非可行解，故先设法使原问题变为可行解原问题变为可行解 ，该表中第，该表中第1行的约束可写为：行的约束可写为： jjcBXBC1B b2x2x3454249xxx 34564249xxxx. 2 3 0 0 0 -M x1 x3 x4 x5 x6 0 x6 3/8 2 x1 11/4 3 15/8 0 0 -1/24 -1/6 1 1/24 1 0 -1/12 1/6 0 1/12 0 1 1/8 0 0 -1/8 0 0 -5/24 -1/3 0 -M+5/24 jjcBXBC1B b2x2x2.5.4 分析参数分析参数aij的变化的变化此时，美佳公司的最优生产计划为每天生产此时，美佳公司的最优生产计划为每天生产11/4件家件家电电I, 8/15件家电件家电II .2.5.5 增加一个约束条件的分析增加一个约束条件的