运筹学第11讲灵敏度分析ppt课件

1、第1页 对偶问题的经济解释对偶问题的经济解释影子价钱影子价钱Duality Theory 线性规划的对偶问题线性规划的对偶问题 对偶单纯形法对偶单纯形法 灵敏度分析灵敏度分析 对偶问题的根本性质对偶问题的根本性质第二章第二章 线性规划的对偶实际线性规划的对偶实际第2页1 1、什么是灵敏度分析？、什么是灵敏度分析？ 是指研讨线性规划模型的某些参数是指研讨线性规划模型的某些参数(bi, cj, aij(bi, cj, aij或限制量或限制量xj, xj, 约束条件约束条件的变化对最优解的影响及其程度的分析过程的变化对最优解的影响及其程度的分析过程 。一、含义和研讨对象一、含义和研讨对象njjjxc

2、z1max1 1,0 1,nijjijja xbimxjn（）（）s.t.第3页回答两个问题：回答两个问题： 这些系数在什么范围内发生变化时，最优解不变？这些系数在什么范围内发生变化时，最优解不变？系数变化超出上述范围，如何用最简便的方法求出系数变化超出上述范围，如何用最简便的方法求出新的最优解？新的最优解？2 2、灵敏度分析的研讨对象：、灵敏度分析的研讨对象： 目的函数的系数目的函数的系数 cj cj 变化对最优解的影响；变化对最优解的影响； 约束方程右端系数约束方程右端系数 bi bi 变化对最优解的影响；变化对最优解的影响； 约束方程组系数矩阵约束方程组系数矩阵 A A 变化对最优解的影

3、变化对最优解的影响响 ； 一、含义和研讨对象一、含义和研讨对象第4页 1、在最终单纯形表的根底上进展； 2、尽量减少附加的计算任务量； 二、进展灵敏度分析的根本原那么二、进展灵敏度分析的根本原那么第5页将参数的改动经过计算反映到最终单纯形表上来将参数的改动经过计算反映到最终单纯形表上来. .检查能否仍为原问题的可行解检查能否仍为原问题的可行解. .检查能否仍为对偶问题的可行解检查能否仍为对偶问题的可行解. .4. 4. 根据不同情况决议继续计算或得到结论根据不同情况决议继续计算或得到结论. .三、灵敏度分析的步骤三、灵敏度分析的步骤原问题原问题对偶问题对偶问题结论或继续计算的步骤结论或继续计算

4、的步骤可行解可行解可行解可行解非可行解非可行解非可行解非可行解可行解可行解非可行解非可行解可行解可行解非可行解非可行解问题的最优解或最优基不变问题的最优解或最优基不变用单纯形法继续迭代求最优解用单纯形法继续迭代求最优解用对偶单纯形法继续迭代求最优解用对偶单纯形法继续迭代求最优解引进人工变量，编制新的单纯形表重引进人工变量，编制新的单纯形表重新计算新计算第6页4. 分析添加一个约束条件的变化分析添加一个约束条件的变化四、灵敏度分析的主要内容四、灵敏度分析的主要内容1. 分析分析 cj 的变化的变化2. 分析分析 bi 的变化的变化3. 分析添加一个变量分析添加一个变量 xj 的变化的变化5. 分

5、析系数分析系数 aij 的变化的变化系数矩阵系数矩阵Anjjjxcz1max1 1,0 1,nijjijja xbimxjn（）（）s.t.第7页 对偶问题决策变量的最优解对偶问题决策变量的最优解 ：X*=B-1bCNCBB-1N 0CBB-1 0 原问题基变量的最优解：原问题基变量的最优解：Z*=CBB-1b最优值：最优值：Y*T= CBB-1第8页Y*T= CBB-1 XB I 0基变量基变量非基变量非基变量XBjjcz基变量基变量 基变量基变量 基可基可 系数系数 行解行解 CNCBB-1N B-1N B-1XN XsB-1bCBB-1bCBB-1Z*=CBB-1b jjjjccc 分析

6、分析 cj cj 的变化的变化原问题原问题对偶问题对偶问题结论或继续计算的步骤结论或继续计算的步骤可行解可行解可行解可行解非可行解非可行解非可行解非可行解可行解可行解非可行解非可行解可行解可行解非可行解非可行解问题的最优解或最优基不变问题的最优解或最优基不变用单纯形法继续迭代求最优解用单纯形法继续迭代求最优解用对偶单纯形法继续迭代求最优解用对偶单纯形法继续迭代求最优解引进人工变量，编制新的单纯形表重引进人工变量，编制新的单纯形表重新计算新计算0 0 最优值能最优值能够已变够已变第9页 x1, x2 0maxs.t. 2x1 + 2x2 12z = 2x1 + 3x2 4x1 16 5x2 15

7、 变化变化 x1, x2 0maxs.t. 2x1 + 2x2 12z = (2 +1) x1 + (3 +2) x2 4x1 16 5x2 15jc BC基b23000qi1xjjcz4x2x20330100 1/53101/201/5400214/500101/51x2x3x4x5x分析分析1和和2分别在什么范围变化时，最优解不变？分别在什么范围变化时，最优解不变？例例1-1第10页 x1, x2 0maxs.t. 2x1 + 2x2 12z = 2x1 + 3x2 4x1 16 5x2 15 变化变化 x1, x2 0maxs.t. 2x1 + 2x2 12z = (2 +1) x1 +

8、 (3 +2) x2 4x1 16 5x2 15jc BC基b23000qi1xjjcz4x2x20330100 1/53101/201/5400214/500101/51x2x3x4x5x12 当当2=02=0时，将时，将1 1 反映反映在最终单纯形表中，可得在最终单纯形表中，可得011 ；12 11 1 从而，表中解仍为最优从而，表中解仍为最优解的条件是解的条件是01 即当即当时问题的最优解不变。时问题的最优解不变。21 1 例例1-1分析分析1和和2分别在什么范围变化时，最优解不变？分别在什么范围变化时，最优解不变？第11页 x1, x2 0maxs.t. 2x1 + 2x2 12z =

9、 2x1 + 3x2 4x1 16 5x2 15 变化变化 x1, x2 0maxs.t. 2x1 + 2x2 12z = (2 +1) x1 + (3 +2) x2 4x1 16 5x2 15jc BC基b23000qi1xjjcz4x2x20330100 1/53101/201/5400214/500101/51x2x3x4x5x 当当1=01=0时，将时，将2 2 反反映映在最终单纯形表中，可得在最终单纯形表中，可得23 2 从而，表中解仍为最优从而，表中解仍为最优解的条件是解的条件是02 即当即当时问题的最优解不变。时问题的最优解不变。1 1 23 例例1-1分析分析1和和2分别在什么

10、范围变化时，最优解不变？分别在什么范围变化时，最优解不变？第12页 美佳公司方案消费美佳公司方案消费I I、IIII两种产品，每天消费条件如表，问两种产品，每天消费条件如表，问 (1) (1)该公司应如何安排消费方案才干使总利润最多该公司应如何安排消费方案才干使总利润最多? ? (2) (2)假设产品假设产品的利润降至的利润降至1.51.5百元百元/ /单位，而产品单位，而产品的利润的利润增增 至至2 2百元百元/ /单位，最优消费方案有何变化单位，最优消费方案有何变化 ？ (3) (3)假设产品假设产品的利润不变，那么产品的利润不变，那么产品的利润在什么范围的利润在什么范围内变内变 化时，该

11、公司的最优消费方案将不发生变化？化时，该公司的最优消费方案将不发生变化？例例2-1设备设备A(h)设备设备B(h)调试工序调试工序(h)(h)利润利润(百元百元) 每天可每天可用才干用才干资源资源产品产品0562112115245第13页例例2-1如何安排消费方案才干使总利润最多？如何安排消费方案才干使总利润最多？解：解：(1) 设设x1, x2分别表示分别表示、两种产品的消费数量，得两种产品的消费数量，得LP模型模型max z = 2x1+x2 s.t. 5x2 15 6x1+2x2 24 x1+ x2 5 x1, x2 0用单纯形法求解得最终单纯形表用单纯形法求解得最终单纯形表设备设备A(

12、h)设备设备B(h)调试工序调试工序(h)(h)利润利润(百元百元) 每天可每天可用才干用才干资源资源产品产品0562112115245第14页例例2-1如何安排消费方案才干使总利润最多？如何安排消费方案才干使总利润最多？解：解：(1) 设设x1, x2分别表示分别表示、两种产品的消费数量，得两种产品的消费数量，得LP模型模型max z = 2x1+x2 s.t. 5x2 15 6x1+2x2 24 x1+ x2 5 x1, x2 0用单纯形法求解得最终单纯形表用单纯形法求解得最终单纯形表jc BC基b210003xjjcz1x2x0213/20101/43/215/2001 5/4 15/2

13、7/2100 1/41/20001/41/21x2x3x4x5x得最优解为：得最优解为：X*=(7/2, 3/2, 15/2, 0, 0)Tzmax=8.5(百元百元)。即每天消费即每天消费3.5单位产品单位产品，1.5单位产品单位产品时总利润最多，且时总利润最多，且第15页max z = 2x1+x2 s.t. 5x2 15 6x1+2x2 24 x1+ x2 5 x1, x2 0例例2-1产品产品利润降至利润降至1.5百元百元/单位，产品单位，产品的利润的利润增至增至2百元百元/单位，消费方案如何变化？单位，消费方案如何变化？解：解：(2) 将产品将产品、的利润变化反映在最终单纯形表中，可

14、得的利润变化反映在最终单纯形表中，可得max z = 1.5x1+2x2 s.t. 5x2 15 6x1+2x2 24 x1+ x2 5 x1, x2 0因有非基变量的检验数大于零因有非基变量的检验数大于零jc BC基b210003xjjcz1x2x0213/20101/43/215/2001 5/4 15/27/2100 1/41/20001/41/21x2x3x4x5x需继续用单纯形法迭代计算，需继续用单纯形法迭代计算，1.5221.5 1/8 9/4 第16页max z = 2x1+x2 s.t. 5x2 15 6x1+2x2 24 x1+ x2 5 x1, x2 0例例2-1产品产品利

15、润降至利润降至1.5百元百元/单位，产品单位，产品的利润的利润增至增至2百元百元/单位，消费方案如何变化？单位，消费方案如何变化？解：解：(2) 将产品将产品、的利润变化反映在最终单纯形表中，可得的利润变化反映在最终单纯形表中，可得max z = 1.5x1+2x2 s.t. 5x2 15 6x1+2x2 24 x1+ x2 5 x1, x2 0因有非基变量的检验数大于零因有非基变量的检验数大于零需继续用单纯形法迭代计算，需继续用单纯形法迭代计算，jc BC基b210004xjjcz1x2x021301 1/500600 4/5162101/510003/21x2x3x4x5x1.5221.5

16、01/10得最优解为：得最优解为：X*=(2, 3, 0, 6, 0)T阐明随产品利润的改动，为获得最高利润，应将消费方案调整为每天消阐明随产品利润的改动，为获得最高利润，应将消费方案调整为每天消费费2单位产品单位产品，3单位产品单位产品，且，且 zmax=9(百元百元)。第17页max z = 2x1+x2 s.t. 5x2 15 6x1+2x2 24 x1+ x2 5 x1, x2 0例例2-1解：解：(3) 将产品将产品的利润变化反映在最终单纯形表中，可得的利润变化反映在最终单纯形表中，可得max z = 2x1+(1+c2)x2 s.t. 5x2 15 6x1+2x2 24 x1+ x

17、2 5 x1, x2 0表中解仍为最优解的条件是表中解仍为最优解的条件是产品产品的利润在什么范围内变化时，最优消费的利润在什么范围内变化时，最优消费方案不会发生变化？方案不会发生变化？jc BC基b210003xjjcz1x2x0213/20101/43/215/2001 5/4 15/27/2100 1/41/20001/41/21x2x3x4x5x21 c21 c2144 c23122 c02144 c；023122 c即即故当产品故当产品的利润在的利润在 范围变化时，最优消费方案不变。范围变化时，最优消费方案不变。113 2c2 ,2311+c2第18页Y*T= CBB-1 XB I 0

18、基变量基变量非基变量非基变量XBjjcz基变量基变量 基变量基变量 基可基可 系数系数 行解行解 CNCBB-1N B-1N B-1XN XsB-1bCBB-1bCBB-1Z*=CBB-1b jjjjccc 分析分析 cj cj 的变化的变化原问题原问题对偶问题对偶问题结论或继续计算的步骤结论或继续计算的步骤可行解可行解可行解可行解非可行解非可行解非可行解非可行解可行解可行解非可行解非可行解可行解可行解非可行解非可行解问题的最优解或最优基不变问题的最优解或最优基不变用单纯形法继续迭代求最优解用单纯形法继续迭代求最优解用对偶单纯形法继续迭代求最优解用对偶单纯形法继续迭代求最优解引进人工变量，编制

19、新的单纯形表重引进人工变量，编制新的单纯形表重新计算新计算0 0 第19页B-1N B-1Y*T= CBB-1 XB I 0基变量基变量非基变量非基变量XBjjcz基变量基变量 基变量基变量 基可基可 系数系数 行解行解 CNCBB-1N XN XsB-1bCBB-1bCBB-1Z*=CBB-1b bbb原问题原问题对偶问题对偶问题结论或继续计算的步骤结论或继续计算的步骤可行解可行解可行解可行解非可行解非可行解非可行解非可行解可行解可行解非可行解非可行解可行解可行解非可行解非可行解问题的最优解或最优基不变问题的最优解或最优基不变用单纯形法继续迭代求最优解用单纯形法继续迭代求最优解用对偶单纯形法

20、继续迭代求最优解用对偶单纯形法继续迭代求最优解引进人工变量，编制新的单纯形表重引进人工变量，编制新的单纯形表重新计算新计算分析分析 bi bi 的变化的变化()1= BXBbb0 0 最优解或最优最优解或最优值能够已变值能够已变第20页 x1, x2 0maxs.t. 2x1 + 2x2 12z = 2x1 + 3x2 4x1 16 5x2 15 变化变化 x1, x2 0maxs.t. 2x1 + 2x2 12 +1z = 2 x1 + 3 x2 4x1 16 +2 5x2 15 +3分析分析ii分别在什么范围变化时，最优基不变？分别在什么范围变化时，最优基不变？例例1-2jc BC基b23

21、000qi1xjjcz4x2x20330100 1/53101/201/5400214/500101/51x2x3x4x5x1(3,4,3)TBXB b11/201/5214/5001/5B1()BXBbb1BXBb0 第21页 x1, x2 0maxs.t. 2x1 + 2x2 12z = 2x1 + 3x2 4x1 16 5x2 15 变化变化 x1, x2 0maxs.t. 2x1 + 2x2 12 +1z = 2 x1 + 3 x2 4x1 16 +2 5x2 15 +3例例1-2解：解：先分析先分析1的变化范围的变化范围:1Bb 1(3,4,3)TBXB b11/201/5214/5

22、001/5B1()BXBbb1BXBb0 11/201/5214/50001/5011/220为使最优基不变，那么需为使最优基不变，那么需 , 即即0BX113/24203从而得到从而得到162 同理可得同理可得2与与3的取值范围的取值范围分析分析ii分别在什么范围变化时，最优基不变？分别在什么范围变化时，最优基不变？第22页 美佳公司方案消费美佳公司方案消费I、II两种产品，每天消费条件两种产品，每天消费条件如表，问如表，问 (4)设备设备A和调试工序每天才干不变，而设备和调试工序每天才干不变，而设备B才干才干添加到添加到32，问最优消费方案如何变化？，问最优消费方案如何变化？ (5)假设设

23、备假设设备A和和B的才干不变，调试工序才干在什的才干不变，调试工序才干在什么范围内变化时，问题的最优基不变？么范围内变化时，问题的最优基不变？例例2-2设备设备A(h)设备设备B(h)调试工序调试工序(h)(h)利润利润(百元百元) 每天可每天可用才干用才干资源资源产品产品0562112115245max z = 2x1+x2 s.t. 5x2 15 6x1+2x2 24 x1+ x2 5 x1, x2 0得最优解为：得最优解为：X*=(7/2, 3/2, 15/2, 0, 0)T第23页max z = 2x1+x2 s.t. 5x2 15 6x1+2x2 24 x1+ x2 5 x1, x2

24、 0例例2-2解：解：(4) 由最终单纯形表，可得由最终单纯形表，可得max z = 2x1+x2 s.t. 5x2 15 6x1+2x2 24+8 x1+ x2 5 x1, x2 0jc BC基b210003xjjcz1x2x0213/20101/43/215/2001 5/4 15/27/2100 1/41/20001/41/21x2x3x4x5x设备设备B B可用才干添加到可用才干添加到3232，消费方案如何变化？，消费方案如何变化？第24页15/415/2001/41/2801/43/20 max z = 2x1+x2 s.t. 5x2 15 6x1+2x2 24 x1+ x2 5 x

25、1, x2 0例例2-2解：解：(4) 由最终单纯形表，可得由最终单纯形表，可得max z = 2x1+x2 s.t. 5x2 15 6x1+2x2 24+8 x1+ x2 5 x1, x2 0jc BC基b210003xjjcz1x2x0213/20101/43/215/2001 5/4 15/27/2100 1/41/20001/41/21x2x3x4x5x设备设备B B可用才干添加到可用才干添加到3232，消费方案如何变化？，消费方案如何变化？1Bb 1022反映到最终单纯形表可得反映到最终单纯形表可得1BBXXBb第25页15/415/2001/41/2801/43/20 max z

26、= 2x1+x2 s.t. 5x2 15 6x1+2x2 24 x1+ x2 5 x1, x2 0例例2-2解：解：(4) 由最终单纯形表，可得由最终单纯形表，可得max z = 2x1+x2 s.t. 5x2 15 6x1+2x2 24+8 x1+ x2 5 x1, x2 0jc BC基b210003xjjcz1x2x0213/20101/43/215/2001 5/4 15/27/2100 1/41/20001/41/21x2x3x4x5x设备设备B B可用才干添加到可用才干添加到3232，消费方案如何变化？，消费方案如何变化？1Bb 1022反映到最终单纯形表可得反映到最终单纯形表可得1

27、BBXXBb35/2 11/2 1/2 第26页max z = 2x1+x2 s.t. 5x2 15 6x1+2x2 24 x1+ x2 5 x1, x2 0例例2-2解：解：(4) 由最终单纯形表，可得由最终单纯形表，可得max z = 2x1+x2 s.t. 5x2 15 6x1+2x2 24+8 x1+ x2 5 x1, x2 0jc BC基b210003xjjcz1x2x0213/20101/43/215/2001 5/4 15/27/2100 1/41/20001/41/21x2x3x4x5x设备设备B B可用才干添加到可用才干添加到3232，消费方案如何变化？，消费方案如何变化？3

28、5/2 11/2 1/2 表中原问题为非可行解，用表中原问题为非可行解，用对偶单纯形法继续计算得对偶单纯形法继续计算得出基出基0miniiirbbbmin/0jrjrja aq入基入基第27页表中原问题为非可行解，用表中原问题为非可行解，用max z = 2x1+x2 s.t. 5x2 15 6x1+2x2 24 x1+ x2 5 x1, x2 0例例2-2解：解：(4) 由最终单纯形表，可得由最终单纯形表，可得max z = 2x1+x2 s.t. 5x2 15 6x1+2x2 24+8 x1+ x2 5 x1, x2 0jc BC基b210003xjjcz1x4x0203/20101/43

29、/215/2001 5/4 15/27/2100 1/41/20001/41/21x2x3x4x5x设备设备B B可用才干添加到可用才干添加到3232，消费方案如何变化？，消费方案如何变化？35/2 11/2 1/2 对偶单纯形法继续计算得对偶单纯形法继续计算得 1 2 4 6 0 15 5 0 0 5 1 1 1 2 0 最优解为：最优解为：X*=(5, 0, 15, 2, 0)T阐明随设备阐明随设备B才干的添加，为获得最高利润，应将消费方案调整为每天才干的添加，为获得最高利润，应将消费方案调整为每天仅消费仅消费5单位产品单位产品，且，且 zmax=10(百元百元)。第28页例例2-2解：解

30、：jc BC基b210003xjjcz1x2x0213/20101/43/215/2001 5/4 15/27/2100 1/41/20001/41/21x2x3x4x5x调试工序才干在什么范围变化，最优基不变？调试工序才干在什么范围变化，最优基不变？max z = 2x1+x2 s.t. 5x2 15 6x1+2x2 24 x1+ x2 5 x1, x2 0max z = 2x1+x2 s.t. 5x2 15 6x1+2x2 24 x1+ x2 5+b3 x1, x2 0(5) 由由 最终单纯形表，可得最终单纯形表，可得第29页例例2-2解：解：max z = 2x1+x2 s.t. 5x2

31、 15 6x1+2x2 24 x1+ x2 5 x1, x2 0max z = 2x1+x2 s.t. 5x2 15 6x1+2x2 24 x1+ x2 5+b3 x1, x2 0(5) 由由 最终单纯形表，可得最终单纯形表，可得 由由 ，计算得，计算得11BBXBbbXBb 115/415/201/41/201/43/2B1(15/2,7/2,3/2)TBXB b3133315152215/415/207101/41/202201/43/23322BBBbXXBbXbbb 调试工序才干在什么范围变化，最优基不变？调试工序才干在什么范围变化，最优基不变？第30页例例2-23133315152215/415/207101/41/202201/43/23322BBBbXXBbXbbb 因此当调试工序才干在因此当调试工序才干在 范围变化时，问题的最优基不变。范围变化时，问题的最优基不变。调试工序才干在什么范围变化，最优基不变？调试工序才干在什么范围变化，最优基不变？为使最优基不变，那么需为使最优基不变，那么需 , 即即0BX333151522710223322bbb从而得到从而得到311b 4,655+b3第31页B-1N B-1Y*T= CBB-1 XB I 0基变量基变量非基变量非基变量XBjjcz基变