《第五讲线性规划灵敏度分析课件.ppt》由会员分享，可在线阅读，更多相关《第五讲线性规划灵敏度分析课件.ppt（30页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第五讲线性规划灵敏度分析2023/4/61第1页，此课件共30页哦第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析一一.目标函数系数的变化目标函数系数的变化二二.约束右端常数项的变化约束右端常数项的变化 三三.系数矩阵系数矩阵A的变化的变化四四.用用Excel进行灵敏度分析进行灵敏度分析2023/4/62第2页，此课件共30页哦一、目标函数系数的变化一、目标函数系数的变化第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析价值系数价值系数c c发生变化：发生变化：考虑检验数考虑检验数 j j=c cj jCCB BB B-1-1P Pj j，j j=1,2,=1,2,n n1.1.若若c cj
2、 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 j2023/4/63第3页，此课件共30页哦第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析一、目标函数系数的变化一、目标函数系数的变化1.1.若若c cj j是非基变量的系数：是非基变量的系数：例题例题Max z=-2x1-3x2-4x3S.t.-x1-2x2-x3+x4 =-3 -2x1+x2-3x
3、3+x5=-4 x1,x2,x3,x4,x5 02023/4/64第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 时，原最优解不变。时，原最优解不变。2023/4/65第5页，此课件共30页哦第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析一、目标函数系数的变化一、目标函数系数的变化2.2.若若c cr r是基变量的系数：是基变量的系数：因因c
4、rCB，当，当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。于是得到。于是得到:2023/4/66第6页，此课件共30页哦第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析一、目标函数系数的变化一、目标函数系数的变化2.2.若若c cr r是基变量的系数：是基变量的系数：c
5、cr r可变化的范围是可变化的范围是:2023/4/67第7页，此课件共30页哦第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析一、目标函数系数的变化一、目标函数系数的变化例例 试以例试以例1 1的最终表为例。的最终表为例。设基变量设基变量x x2 2的系数的系数c c2 2变化变化c c2 2，在原最优解不变条件下，在原最优解不变条件下，确定确定c c2 2的变化范围。的变化范围。解：解：这时最终计算表便成为下表所示。这时最终计算表便成为下表所示。2023/4/68第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之间变化，而不影响之间变化，而不影响原最优解。原最优解。一、目标函数系数的变化一、目标函数系数的变化2023/4/69第9页，此课件共30页哦第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析二、约束右端常数项的变化二、约束右端常数项的变化 资资源源数数量量变变化化是是指指资资源源中中某某系系数数b br r发发生生变变化化，即即b br r=b br r+b br r。并并假假
7、设设规规划划问问题题的的其其他他系系数数都都不不变变。这这样样使使最最终终表表中中原原问问题题的的解解相相应应地地变变化化为：为：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为为新新的的最优解。新的最优解的值可允许变化范围用以下方法确定。最优解。新的最优解的值可允许变化范围用以下方法确定。2023/4/610第10页，此课件共30页哦第五讲第五讲 线性规划灵敏度
8、分析线性规划灵敏度分析二、约束右端常数项的变化二、约束右端常数项的变化新的最优解的值可允许变化范围用以下方法确定。新的最优解的值可允许变化范围用以下方法确定。2023/4/611第11页，此课件共30页哦第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析二、约束右端常数项的变化二、约束右端常数项的变化新的最优解的值可允许变化范围用以下方法确定。在最终表中求得的经过变化后的在最终表中求得的经过变化后的b b列的所有元素，要求列的所有元素，要求 ：于是得到：于是得到：2023/4/612第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 2023/4/613第13页，此课件共30页哦第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析二、约束右端常数项的变化二、约束右端常数项的变化可计算可计算b b2 2：由
10、上式，可得由上式，可得 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。2023/4/614第14页，此课件共30页哦第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析二、约束右端常数项的变化二、约束右端常数项的变化练习题：练习题：从例从例1 1中，若该厂又从其他处抽调中，若该厂又从其他处抽调4 4个单位的原
11、材料个单位的原材料用于生产产品甲，乙。求这时该厂生产产品甲，乙的最用于生产产品甲，乙。求这时该厂生产产品甲，乙的最优方案。优方案。2023/4/615第15页，此课件共30页哦第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析三、系数矩阵三、系数矩阵A的变化的变化1.A1.A中某个元素的变化：中某个元素的变化：若系数矩阵中若系数矩阵中a aijij变化了变化了 a aijij ，且它是非基变量的系数列向量，且它是非基变量的系数列向量的分量。的分量。而在单纯形最终计算表中，非基变量xj的检验数为：则：故：2023/4/616第16页，此课件共30页哦第五讲第五讲 线性规划灵敏度分析线性规划灵敏度
12、分析三、系数矩阵三、系数矩阵A的变化的变化2.A2.A中某列向量的变化：中某列向量的变化：若系数矩阵若系数矩阵A A中某一列向量中某一列向量P Pj j发生了变化，且其对应的变量发生了变化，且其对应的变量x xj j为非为非基变量，那么基变量，那么P Pj j的变化仅影响起自身的检验数。的变化仅影响起自身的检验数。如果如果 ，则说明变化后并不影响当前解；，则说明变化后并不影响当前解；如果如果 ，则说明变化后影响当前解，需重新迭代；，则说明变化后影响当前解，需重新迭代；若系数矩阵若系数矩阵A A中某一列向量中某一列向量P Pj j发生了变化，且其对应的变量发生了变化，且其对应的变量x xj j为
13、为基变量，则需恢复该列向量为单位列向量后，再处理。基变量，则需恢复该列向量为单位列向量后，再处理。2023/4/617第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，则其在最终表的列向量数，则其在最终表的列向量数字为：字为：2023/4/618第18页，此课件共30页哦第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析0-1/4-201/2cj-zj 0101/41/2-1/80-21/20011/2-11/4442x1x5x
15、2304x5x4x3x2x1B1bXBCB00043cj0-1/2-200 cj-zj 0101/21-1/40-21/20011008120 x1x5x2304x5x4x3x2x1B1bXBCB00043cj由上表可得：原问题和对偶问题都得到了最优解。由上表可得：原问题和对偶问题都得到了最优解。2023/4/619第19页，此课件共30页哦第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析三、系数矩阵三、系数矩阵A的变化的变化2.A2.A中某列向量的变化：中某列向量的变化：例：仍以例例：仍以例1 1为例，若原计划生产产品甲的工艺结构有了改进，为例，若原计划生产产品甲的工艺结构有了改进，这时有
16、关它的技术系数向量变为这时有关它的技术系数向量变为P P1 1=(4,4,2)=(4,4,2)T T，试分析对原最优计，试分析对原最优计划有什么影响划有什么影响?解：变化后的系数列向量记为解：变化后的系数列向量记为P P1 1，则其在最终表的列向量，则其在最终表的列向量数字为：数字为：将以上计算结果填入最终表将以上计算结果填入最终表x x1 1 的列向量位置，得下表。的列向量位置，得下表。2023/4/620第20页，此课件共30页哦第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析0-1/4-200.5cj-zj 0101/41/2-1/80-21/20011-43/2442x1x5x230
17、4x5x4x3x2x1B1bXBCB00043cj 恢复恢复P P1 1为单位列向量，得到下表：为单位列向量，得到下表：05/4-200cj-zj 0101/43/2-1/20-21/2001100420-4x1x5x2304x5x4x3x2x1B1bXBCB00043cj2023/4/621第21页，此课件共30页哦第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析05/4-200cj-zj 0101/43/2-1/20-21/2001100420-4x1x5x2304x5x4x3x2x1B1bXBCB00043cj 分析知：应在第三个约束条件中加入人工变量，即：分析知：应在第三个约束条件中
18、加入人工变量，即：001/2M-3/41/2M-3/4-1/2M-M+40cj-zj 0 0 10101/43/21/20-2-1/200-11004204x1x5x630-M x6x5x4x3x2x1B1bXBCB -M00043cj2023/4/622第22页，此课件共30页哦第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析由上表可得：原问题得到了最优解。由上表可得：原问题得到了最优解。-M+3/200 0-3/45/20cj-zj -1/2 -3 20100011/4-1/2-11/23-2100288x1x5x4300 x6x5x4x3x2x1B1bXBCB -M00043cj -M
19、+4-5/60 0-7/300cj-zj 0 -1 0-1/61/32/30011/3-1/6-4/30101002/38/340/3x1x2x4340 x6x5x4x3x2x1B1bXBCB -M00043cj2023/4/623第23页，此课件共30页哦第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析三、系数矩阵三、系数矩阵A的变化的变化3.A3.A中增加一列或一行的变化：中增加一列或一行的变化：例例 以以例例1 1为为例例。设设该该厂厂除除了了生生产产产产品品甲甲，乙乙外外，现现有有一一种种新新产产品品丙丙。已已知知生生产产产产品品丙丙，每每件件需需消消耗耗原原材材料料及及设设备备A
20、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的检验数为：的检验数为：说明安排生产产品丙是有利的。说明安排生产产品丙是有利的。2023/4/624第24页，此课件共30页哦第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析 (2)(
21、2)设分析应安排生产的方案：设分析应安排生产的方案：填入到最终单纯形表中可得：填入到最终单纯形表中可得：10-1/4-1/4-200cj-zj 1 0 1/20101/41/2-1/80-21/2001100442x1x5x2304 x6x5x4x3x2x1B1bXBCB 600043cj2023/4/625第25页，此课件共30页哦第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析 10-1/4-1/4-200cj-zj 1 0 1/20101/41/2-1/80-21/2001100442x1x5x2304 x6x5x4x3x2x1B1bXBCB 600043cj 00-1/2-1/2-2
22、0-1cj-zj 1 0 00101/41/2-1/40-21/200110-1/2440 x6x5x2604 x6x5x4x3x2x1B1bXBCB 600043cj由上表可得：原问题得到了最优解。由上表可得：原问题得到了最优解。2023/4/626第26页，此课件共30页哦第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析 例例 仍仍以以例例1 1为为例例。若若企企业业为为了了提提高高产产品品质质量量，考考虑虑给给产产品品甲甲、乙乙增增加加一一道道精精加加工工工工序序，并并在在设设备备C C上上进进行行加加工工。甲甲、乙乙两两种种产产品品在在C C上上的的单单位位加加工工台台时时分分别别为
23、为（2 2，4 4）。已已知知设设备备C C的的可可用用工工作作时时间间为为1212个台时，试问增加这道精加工工序以后，对原最优计划方案有何影响个台时，试问增加这道精加工工序以后，对原最优计划方案有何影响?三、系数矩阵三、系数矩阵A的变化的变化3.A3.A中增加一列或一行的变化：中增加一列或一行的变化：解：增加一道工序等于增加一个约束条件，表达式为：解：增加一道工序等于增加一个约束条件，表达式为：即：即：则以该松弛变量为基变量，得到新单纯形表为：则以该松弛变量为基变量，得到新单纯形表为：2023/4/627第27页，此课件共30页哦第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析 10-1/
24、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 600043cj2023/4/628第28页，此课件共30页哦第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析 00-1/4-200cj-zj 0 0 0 101001/41/2-1/800-21/2-2
25、00101000442-4x1x5x2x63040 x6x5x4x3x2x1B1bXBCB 600043cj -10-1/4-1/4000cj-zj 0 -1 1/4 -1/201001/41/2-1/800001001010004812x1x5x2x33040 x6x5x4x3x2x1B1bXBCB 600043cj2023/4/629第29页，此课件共30页哦第五讲第五讲 线性规划灵敏度分析线性规划灵敏度分析由上表可得：原问题得到了最优解。由上表可得：原问题得到了最优解。总结总结（1 1）若修正后的原问题与对偶问题的解都是可行解，则修正后的解仍）若修正后的原问题与对偶问题的解都是可行解，则修正后的解仍是可行解。是可行解。（2 2）若出现原问题是可行解，对偶问题是非可行解，则按单纯形法继续迭）若出现原问题是可行解，对偶问题是非可行解，则按单纯形法继续迭代求出最代求出最 优解。优解。（3 3）若对偶问题是可行解，原问题是非可行解，则按对偶单纯形法继续）若对偶问题是可行解，原问题是非可行解，则按对偶单纯形法继续迭代求出最优解。迭代求出最优解。（4 4）若原问题与对偶问题的解均是非可行解，这时就要引入人工变量，）若原问题与对偶问题的解均是非可行解，这时就要引入人工变量，建立新的单纯形表重新计算。建立新的单纯形表重新计算。2023/4/630第30页，此课件共30页哦