第五讲线性规划灵敏度分析.ppt

《第五讲线性规划灵敏度分析.ppt》由会员分享，可在线阅读，更多相关《第五讲线性规划灵敏度分析.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五讲线性规划灵敏度分析2022/10/91现在学习的是第1页，共30页第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析一一.目标函数系数的变化目标函数系数的变化二二.约束右端常数项的变化约束右端常数项的变化 三三.系数矩阵系数矩阵A的变化的变化四四.用用Excel进行灵敏度分析进行灵敏度分析2022/10/92现在学习的是第2页，共30页一、目标函数系数的变化一、目标函数系数的变化第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析价值系数价值系数c c发生变化：发生变化：考虑检验数考虑检验数 j j=c cj jCCB BB B-1-1P Pj j，j j=1,2,=1,2,n n1.1.

2、若若c cj j是非基变量的系数：是非基变量的系数：设设c cj j变化为变化为 c cj j +c cj j ：则则j=cj+cj CBB-1Pj=j+cj若使当前最优解不变，则若使当前最优解不变，则 j j00即：即：c cj j +c cj j C CB BB B-1-1P Pj j=YP=YPj j2022/10/93现在学习的是第3页，共30页第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析一、目标函数系数的变化一、目标函数系数的变化1.1.若若c cj j是非基变量的系数：是非基变量的系数：例题例题Max z=-2x1-3x2-4x3S.t.-x1-2x2-x3+x4 =-3 -

3、2x1+x2-3x3+x5=-4 x1,x2,x3,x4,x5 02022/10/94现在学习的是第4页，共30页第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析1.1.若若c cj j是非基变量的系数：是非基变量的系数：从表中看到从表中看到 3 3=c c3 3+c c3 3-(-(c c2 2a a1313+c c1 1a a23 23)可得到可得到 c c3 3 9/5 9/5 时，原最优解不变。时，原最优解不变。2022/10/95现在学习的是第5页，共30页第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析一、目标函数系数的变化一、目标函数系数的变化2.2.若若c cr r是基变量

4、的系数：是基变量的系数：因因crCB，当，当cr变化变化cr时，就引起时，就引起CB的变化，这时的变化，这时 (CB+CB)B-1A=CBB-1A+(0，cr，0)B-1A =CBB-1A+cr(r1,r2,，rn)可见，当可见，当cr变化变化cr后，最终表中的检验数是后，最终表中的检验数是 j=cjCBB-1Pjcr arj，j=1,2,，n 若要求原最优解不变，即必须满足若要求原最优解不变，即必须满足j0。于是得到。于是得到:2022/10/96现在学习的是第6页，共30页第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析一、目标函数系数的变化一、目标函数系数的变化2.2.若若c cr r

5、是基变量的系数：是基变量的系数：c cr r可变化的范围是可变化的范围是:2022/10/97现在学习的是第7页，共30页第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析一、目标函数系数的变化一、目标函数系数的变化例例 试以例试以例1 1的最终表为例。的最终表为例。设基变量设基变量x x2 2的系数的系数c c2 2变化变化c c2 2，在原最优解不变条件下，在原最优解不变条件下，确定确定c c2 2的变化范围。的变化范围。解：解：这时最终计算表便成为下表所示。这时最终计算表便成为下表所示。2022/10/98现在学习的是第8页，共30页第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析若保

6、持原最优解，从上表的检验数行可见应有若保持原最优解，从上表的检验数行可见应有由此可得由此可得 c c2 24 4 和和cc2 222。c c2 2的变化范围为的变化范围为 44c c2 222即即x x2 2的价值系数的价值系数c c2 2可以在可以在0 0，6 6之间变化，而不影响原之间变化，而不影响原最优解。最优解。一、目标函数系数的变化一、目标函数系数的变化2022/10/99现在学习的是第9页，共30页第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析二、约束右端常数项的变化二、约束右端常数项的变化 资资源源数数量量变变化化是是指指资资源源中中某某系系数数b br r发发生生变变化化，

7、即即b br r=b br r+b br r。并并假假设设规规划划问问题题的的其其他他系系数数都都不不变变。这这样样使使最最终终表表中中原原问问题题的的解解相应地变化为：相应地变化为：X XB B=B B-1-1(b b+b b)这这里里 b b=(0,=(0,，b br r,0,0,，0)0)T T。只只要要X XB B00，因因最最终终表表中中检检验验数数不不变变，故故最最优优基基不不变变，但但最最优优解解的的值值发发生生了了变变化化，所所以以X XB B为为新的最优解。新的最优解的值可允许变化范围用以下方法确定。新的最优解。新的最优解的值可允许变化范围用以下方法确定。2022/10/91

8、0现在学习的是第10页，共30页第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析二、约束右端常数项的变化二、约束右端常数项的变化新的最优解的值可允许变化范围用以下方法确定。新的最优解的值可允许变化范围用以下方法确定。2022/10/911现在学习的是第11页，共30页第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析二、约束右端常数项的变化二、约束右端常数项的变化新的最优解的值可允许变化范围用以下方法确定。在最终表中求得的经过变化后的在最终表中求得的经过变化后的b b列的所有元素，要求列的所有元素，要求 ：于是得到：于是得到：2022/10/912现在学习的是第12页，共30页第五讲第五讲

9、线性规划灵敏度分析线性规划灵敏度分析二、约束右端常数项的变化二、约束右端常数项的变化例如求例例如求例1 1中第二个约束条件中第二个约束条件b b2 2的变化范围。的变化范围。解：可以利用例解：可以利用例1 1的最终计算表中的数据：的最终计算表中的数据：0 00 0-2-21/21/21 14 41 10 00 01/41/40 04 40 01 11/21/2-1/8-1/80 02 2x x 1 1x x 5 5x x 2 23 30 04 4B1bXBCBx 1x 2x 3x 4x 5cj 2022/10/913现在学习的是第13页，共30页第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分

10、析二、约束右端常数项的变化二、约束右端常数项的变化可计算可计算b b2 2：由上式，可得由上式，可得 b b2 24/0.25=164/0.25=16，b b2 24/0.5=84/0.5=8，b b2 22/0.125=162/0.125=16。所所以以 b b2 2的的变变化化范范围围是是 8 8，1616；显显然然原原b b2 2=16=16，加加它它的的变变化化范范围围后后，b b2 2的的变变化化范范围围是是8 8，3232。2022/10/914现在学习的是第14页，共30页第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析二、约束右端常数项的变化二、约束右端常数项的变化练习题：练

11、习题：从例从例1 1中，若该厂又从其他处抽调中，若该厂又从其他处抽调4 4个单位的原材料用个单位的原材料用于生产产品甲，乙。求这时该厂生产产品甲，乙的最优于生产产品甲，乙。求这时该厂生产产品甲，乙的最优方案。方案。2022/10/915现在学习的是第15页，共30页第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析三、系数矩阵三、系数矩阵A的变化的变化1.A1.A中某个元素的变化：中某个元素的变化：若系数矩阵中若系数矩阵中a aijij变化了变化了 a aijij ，且它是非基变量的系数列向量，且它是非基变量的系数列向量的分量。的分量。而在单纯形最终计算表中，非基变量xj的检验数为：则：故：2

12、022/10/916现在学习的是第16页，共30页第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析三、系数矩阵三、系数矩阵A的变化的变化2.A2.A中某列向量的变化：中某列向量的变化：若系数矩阵若系数矩阵A A中某一列向量中某一列向量P Pj j发生了变化，且其对应的变量发生了变化，且其对应的变量x xj j为非为非基变量，那么基变量，那么P Pj j的变化仅影响起自身的检验数。的变化仅影响起自身的检验数。如果如果 ，则说明变化后并不影响当前解；，则说明变化后并不影响当前解；如果如果 ，则说明变化后影响当前解，需重新迭代；，则说明变化后影响当前解，需重新迭代；若系数矩阵若系数矩阵A A中某一

13、列向量中某一列向量P Pj j发生了变化，且其对应的变量发生了变化，且其对应的变量x xj j为为基变量，则需恢复该列向量为单位列向量后，再处理。基变量，则需恢复该列向量为单位列向量后，再处理。2022/10/917现在学习的是第17页，共30页第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析 例：分析原计划生产产品的工艺结构发生变化。仍以例例：分析原计划生产产品的工艺结构发生变化。仍以例1 1为为例，若原计划生产产品甲的工艺结构有了改进，这时有关它的技术例，若原计划生产产品甲的工艺结构有了改进，这时有关它的技术系数向量变为系数向量变为P P1 1=(1,2,0)=(1,2,0)T T，试分

14、析对原最优计划有什么影响，试分析对原最优计划有什么影响?同时计算出变化后的检验数为：同时计算出变化后的检验数为：c c1 1 C CB BB B-1-1P P1 1=0.5=0.5将以上计算结果填入最终表将以上计算结果填入最终表x x1 1 的列向量位置，得下表。的列向量位置，得下表。三、系数矩阵三、系数矩阵A的变化的变化2.A2.A中某列向量的变化：中某列向量的变化：解：变化后的系数列向量记为解：变化后的系数列向量记为P P1 1，则其在最终表的列向量数，则其在最终表的列向量数字为：字为：2022/10/918现在学习的是第18页，共30页第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析0

15、-1/4-201/2cj-zj 0101/41/2-1/80-21/20011/2-11/4442x1x5x2304x5x4x3x2x1B1bXBCB00043cj0-1/2-200 cj-zj 0101/21-1/40-21/20011008120 x1x5x2304x5x4x3x2x1B1bXBCB00043cj由上表可得：原问题和对偶问题都得到了最优解。由上表可得：原问题和对偶问题都得到了最优解。2022/10/919现在学习的是第19页，共30页第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析三、系数矩阵三、系数矩阵A的变化的变化2.A2.A中某列向量的变化：中某列向量的变化：例：仍

16、以例例：仍以例1 1为例，若原计划生产产品甲的工艺结构有了改进，为例，若原计划生产产品甲的工艺结构有了改进，这时有关它的技术系数向量变为这时有关它的技术系数向量变为P P1 1=(4,4,2)=(4,4,2)T T，试分析对原最优计划有，试分析对原最优计划有什么影响什么影响?解：变化后的系数列向量记为解：变化后的系数列向量记为P P1 1，则其在最终表的列向量数，则其在最终表的列向量数字为：字为：将以上计算结果填入最终表将以上计算结果填入最终表x x1 1 的列向量位置，得下表。的列向量位置，得下表。2022/10/920现在学习的是第20页，共30页第五讲第五讲 线性规划灵敏度分析线性规划灵

17、敏度分析0-1/4-200.5cj-zj 0101/41/2-1/80-21/20011-43/2442x1x5x2304x5x4x3x2x1B1bXBCB00043cj 恢复恢复P P1 1为单位列向量，得到下表：为单位列向量，得到下表：05/4-200cj-zj 0101/43/2-1/20-21/2001100420-4x1x5x2304x5x4x3x2x1B1bXBCB00043cj2022/10/921现在学习的是第21页，共30页第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析05/4-200cj-zj 0101/43/2-1/20-21/2001100420-4x1x5x230

18、4x5x4x3x2x1B1bXBCB00043cj 分析知：应在第三个约束条件中加入人工变量，即：分析知：应在第三个约束条件中加入人工变量，即：001/2M-3/41/2M-3/4-1/2M-M+40cj-zj 0 0 10101/43/21/20-2-1/200-11004204x1x5x630-M x6x5x4x3x2x1B1bXBCB -M00043cj2022/10/922现在学习的是第22页，共30页第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析由上表可得：原问题得到了最优解。由上表可得：原问题得到了最优解。-M+3/200 0-3/45/20cj-zj -1/2 -3 2010

19、0011/4-1/2-11/23-2100288x1x5x4300 x6x5x4x3x2x1B1bXBCB -M00043cj -M+4-5/60 0-7/300cj-zj 0 -1 0-1/61/32/30011/3-1/6-4/30101002/38/340/3x1x2x4340 x6x5x4x3x2x1B1bXBCB -M00043cj2022/10/923现在学习的是第23页，共30页第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析三、系数矩阵三、系数矩阵A的变化的变化3.A3.A中增加一列或一行的变化：中增加一列或一行的变化：例例 以以例例1 1为为例例。设设该该厂厂除除了了生生产

20、产产产品品甲甲，乙乙外外，现现有有一一种种新新产产品品丙丙。已已知知生生产产产产品品丙丙，每每件件需需消消耗耗原原材材料料及及设设备备A A，B B的的数数量量分分别别为为2 2个个单单位位，4h4h，2h2h；每每件件可可获获利利6 6元元。问问该该厂厂是是否否应应生产该产品和生产多少生产该产品和生产多少?解：分析该问题的步骤是：解：分析该问题的步骤是：(1)(1)设生产产品丙为设生产产品丙为x x6 6台，其技术系数向量台，其技术系数向量P P6 6=(2,4,2)=(2,4,2)T T，然后计，然后计算最终表中对应算最终表中对应x x6 6的检验数为：的检验数为：说明安排生产产品丙是有利

21、的。说明安排生产产品丙是有利的。2022/10/924现在学习的是第24页，共30页第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析 (2)(2)设分析应安排生产的方案：设分析应安排生产的方案：填入到最终单纯形表中可得：填入到最终单纯形表中可得：10-1/4-1/4-200cj-zj 1 0 1/20101/41/2-1/80-21/2001100442x1x5x2304 x6x5x4x3x2x1B1bXBCB 600043cj2022/10/925现在学习的是第25页，共30页第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析 10-1/4-1/4-200cj-zj 1 0 1/20101

22、/41/2-1/80-21/2001100442x1x5x2304 x6x5x4x3x2x1B1bXBCB 600043cj 00-1/2-1/2-20-1cj-zj 1 0 00101/41/2-1/40-21/200110-1/2440 x6x5x2604 x6x5x4x3x2x1B1bXBCB 600043cj由上表可得：原问题得到了最优解。由上表可得：原问题得到了最优解。2022/10/926现在学习的是第26页，共30页第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析 例例 仍仍以以例例1 1为为例例。若若企企业业为为了了提提高高产产品品质质量量，考考虑虑给给产产品品甲甲、乙乙增增

23、加加一一道道精精加加工工工工序序，并并在在设设备备C C上上进进行行加加工工。甲甲、乙乙两两种种产产品品在在C C上上的的单单位位加加工工台台时时分分别别为为（2 2，4 4）。已已知知设设备备C C的的可可用用工工作作时时间间为为1212个个台台时时，试试问问增增加加这这道道精精加加工工工工序序以以后后，对对原原最最优优计计划划方方案案有有何影响何影响?三、系数矩阵三、系数矩阵A的变化的变化3.A3.A中增加一列或一行的变化：中增加一列或一行的变化：解：增加一道工序等于增加一个约束条件，表达式为：解：增加一道工序等于增加一个约束条件，表达式为：即：即：则以该松弛变量为基变量，得到新单纯形表为

24、：则以该松弛变量为基变量，得到新单纯形表为：2022/10/927现在学习的是第27页，共30页第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析 10-1/4-1/4-200cj-zj 1 0 1/2 101001/41/2-1/800-21/200014100244212x1x5x2x63040 x6x5x4x3x2x1B1bXBCB 600043cj 00-1/4-1/4-200cj-zj 0 0 0 101001/41/2-1/800-21/2-200101000442-4x1x5x2x63040 x6x5x4x3x2x1B1bXBCB 600043cj2022/10/928现在学习的

25、是第28页，共30页第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析 00-1/4-200cj-zj 0 0 0 101001/41/2-1/800-21/2-200101000442-4x1x5x2x63040 x6x5x4x3x2x1B1bXBCB 600043cj -10-1/4-1/4000cj-zj 0 -1 1/4 -1/201001/41/2-1/800001001010004812x1x5x2x33040 x6x5x4x3x2x1B1bXBCB 600043cj2022/10/929现在学习的是第29页，共30页第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析由上表可得：原

26、问题得到了最优解。由上表可得：原问题得到了最优解。总结总结（1 1）若修正后的原问题与对偶问题的解都是可行解，则修正后的解仍）若修正后的原问题与对偶问题的解都是可行解，则修正后的解仍是可行解。是可行解。（2 2）若出现原问题是可行解，对偶问题是非可行解，则按单纯形法继续迭）若出现原问题是可行解，对偶问题是非可行解，则按单纯形法继续迭代求出最代求出最 优解。优解。（3 3）若对偶问题是可行解，原问题是非可行解，则按对偶单纯形）若对偶问题是可行解，原问题是非可行解，则按对偶单纯形法继续迭代求出最优解。法继续迭代求出最优解。（4 4）若原问题与对偶问题的解均是非可行解，这时就要引入人工变量，）若原问题与对偶问题的解均是非可行解，这时就要引入人工变量，建立新的单纯形表重新计算。建立新的单纯形表重新计算。2022/10/930现在学习的是第30页，共30页