运筹学课件灵敏度分析.pptx

1、运筹学教程2、灵敏度分析的内容：、灵敏度分析的内容：目标函数的系数变化对最优解的影响；目标函数的系数变化对最优解的影响；约束方程右端系数变化对最优解的影响；约束方程右端系数变化对最优解的影响；约束方程组系数阵变化对最优解的影响约束方程组系数阵变化对最优解的影响 ； 回答两个问题回答两个问题运筹学教程这些系数在什么范围内发生变化时，最优这些系数在什么范围内发生变化时，最优基不变（即最优解或最优解结构不变）？基不变（即最优解或最优解结构不变）？系数变化超出上述范围时，如何用最简便系数变化超出上述范围时，如何用最简便的方法求出新的最优解？的方法求出新的最优解？二、二、 进行灵敏度分析的基本原则进行灵

2、敏度分析的基本原则 运筹学教程miiijjjjjjyaczcPBPbBb111)(运筹学教程原问题原问题对偶问题对偶问题结论或继续计算的步骤结论或继续计算的步骤可行解可行解可行解可行解非可行解非可行解非可行解非可行解可行解可行解非可行解非可行解可行解可行解非可行解非可行解问题最优解或最优基不变问题最优解或最优基不变单纯形求解最优解单纯形求解最优解对偶单纯形求解最优解对偶单纯形求解最优解引进人工变量，新单纯形引进人工变量，新单纯形表重新计算表重新计算运筹学教程 三、三、 灵敏度分析举例：灵敏度分析举例：例例1-1 0,52426155. .2max212121221xxxxxxxtsxxZ引入非

3、负的松弛变量引入非负的松弛变量x3, x4,x5, 将该将该LP化为化为 标准型标准型：运筹学教程0,52436155. .0002max543215214213254321xxxxxxxxxxxxxtsxxxxxZ用单纯形法求解如下：用单纯形法求解如下：运筹学教程Cj 2 1 0 0 0CB 基基 b X1 x2 x3 x4 x50 x3 15/22 x1 7/21 x2 3/20 0 1 5/4 -15/21 0 0 -1/20 1 0 -1/4 3/2 Cj-Zj0 0 0 -1/4 -1/2运筹学教程1、价值系数、价值系数Cj变化变化（1）当）当cj是非基变量的价值系数是非基变量的价值

4、系数它的变它的变化只影响化只影响 一个检验数一个检验数。j例：例：c4发生变化时，发生变化时， ，最优解不变，最优解不变否则否则 0,可使用可使用原单纯形法原单纯形法继续迭代求出新继续迭代求出新的最优解。的最优解。 044NBCCBNN1运筹学教程（2）当）当cj是基变量的价值系数是基变量的价值系数它的变化它的变化将影响所有非基变量的检验数将影响所有非基变量的检验数.NBCCBNN1 当当cj变化时，如能保持变化时，如能保持 ，则当前解仍为，则当前解仍为最优解，最优解，否则否则可用可用单纯形法单纯形法继续迭代继续迭代求出新求出新的最优解的最优解。0N运筹学教程例例1-1:(1)1-1:(1)如

5、果产品如果产品1 1的利润降至的利润降至1.51.5元元/ /件，产品件，产品2 2的利润增加的利润增加至至2 2元元/ /件，工厂的最优生产计划？件，工厂的最优生产计划？（2 2）如果产品）如果产品1 1的利润不变，则产品的利润在什么范围内变的利润不变，则产品的利润在什么范围内变化，工厂的最优生产计划不变？化，工厂的最优生产计划不变？Cj 1.5 2 0 0 0CB 基基 b X1 x2 x3 x4 x50 x3 15/21.5 x1 7/2 2 x2 3/20 0 1 5/4 -15/21 0 0 -1/20 1 0 -1/4 3/2 Cj-Zj0 0 0 1/8 -9/4运筹学教程Cj

6、1.5 2 0 0 0CB 基基 b X1 x2 x3 x4 x50 x4 61.5 x1 22 x2 30 0 4/5 1 -61 0 -1/5 0 10 1 1/5 0 0 Cj-Zj0 0 -1/10 0 -3/2运筹学教程Cj 2 1 + 0 0 0CB 基基 b X1 x2 x3 x4 x50 x3 15/22 x1 7/21+ x2 3/20 0 1 5/4 -15/21 0 0 -1/20 1 0 -1/4 3/2 Cj-Zj0 0 0 -1/4+ /4 -1/2-3 /2运筹学教程23213102321,04412c范围应满足：所以产品利润的变化运筹学教程2、分析、分析bi（右

7、端常数）变化：右端常数）变化： 当当bi发生变化时，将影响所有基变量的取值。发生变化时，将影响所有基变量的取值。：bBXB1保持保持B-1b0,当前的基仍为最优基，最优解的结构当前的基仍为最优基，最优解的结构不变（取值改变）；不变（取值改变）；（B-1b）0,当前基为非可行基当前基为非可行基,但是仍保持为对偶但是仍保持为对偶可行基可行基, 可用对偶单纯形法求出新的最优解；可用对偶单纯形法求出新的最优解；运筹学教程仍然来看例仍然来看例1-11-1：（1 1）如果设备）如果设备A A和调试工序的每天的能力不变，设备和调试工序的每天的能力不变，设备B B每每天的能力增加到天的能力增加到3232h h

8、，分析公司最优的生产计划的变化；分析公司最优的生产计划的变化；（2 2）如果设备）如果设备A A和设备和设备B B每天的能力不变，则调试工序在每天的能力不变，则调试工序在什么范围内变化，问题的最优基不变。什么范围内变化，问题的最优基不变。 22100802/34/102/14/102/154/5108011bBbb）解：（运筹学教程Cj 2 1 0 0 0CB 基 b X1 x2 x3 x4 x50 x3 35/22 x1 11/21 x2 -1/20 0 1 5/4 -15/21 0 0 -1/20 1 0 -1/4 3/2 Cj-Zj0 0 0 -1/4 -1/2将其反映到最终的单纯形表，

9、原问题非可行解，将其反映到最终的单纯形表，原问题非可行解，采用采用dualdual单纯形法单纯形法运筹学教程Cj 2 1 0 0 0CB 基 b X1 x2 x3 x4 x50 x3 152 x1 50 x4 20 5 1 0 01 1 0 0 10 -4 0 1 -6 Cj-Zj0 -1 0 0 -2运筹学教程232321272152152/32/2/15002/34/102/14/102/154/51521bbbBb列数字为反映到单纯形表，为设每天的调试可用能力）解：（11当当b b0 0问题的最优基不变，问题的最优基不变，解得：解得：所以调试能力在所以调试能力在4 4 6 6h h运筹学

10、教程3、增加一个变量xj的分析继续计算。如果最优解不变；、如果、计算、计算分析步骤：,0,032111jjjjmiiijjjjjPBPyaczc如果该厂计划推出新产品如果该厂计划推出新产品3 3，生产一件所需要设备，生产一件所需要设备A,B A,B 以及调试工序的时间分别是以及调试工序的时间分别是3 3h,4h,2hh,4h,2h，该产品的预期利该产品的预期利润润3 3元元/ /件，分析该种产品是否值得投产？如投产，对该件，分析该种产品是否值得投产？如投产，对该公司的最优生产计划有何改变？公司的最优生产计划有何改变？运筹学教程20724323410214102154511243)21,41,

11、0(361631666PBPyaciii运筹学教程Cj 2 1 0 0 0 3CB 基基 b X1 x2 x3 x4 x5 x60 x3 15/22 x1 7/21 x2 3/20 0 1 5/4 -15/2 -71 0 0 -1/2 00 1 0 -1/4 3/2 2Cj-Zj0 0 0 -1/4 -1/2 1运筹学教程Cj 2 1 0 0 0 3CB 基基 b X1 x2 x3 x4 x5 x60 x3 51/42 x1 7/23 x6 3/40 7/2 1 3/8 -9/4 01 0 0 -1/2 00 1/2 0 -1/8 3/4 1Cj-Zj0 -1/2 0 -1/8 -5/4 0运

12、筹学教程4、分析参数、分析参数 aij的变化的变化参数参数 aij的变化导致的变化导致系数阵系数阵A的元素发生变化。相当于增的元素发生变化。相当于增加加1个新变量（系数阵个新变量（系数阵A增加增加1列），如果列），如果 xj在最终单纯在最终单纯形表中为基变量，则形表中为基变量，则aij的变化会使相应的的变化会使相应的B ,B-1发生变发生变化，有可能出现原问题与对偶问题无可行解的情况。化，有可能出现原问题与对偶问题无可行解的情况。引引进人工变量，使用单纯形法计算。进人工变量，使用单纯形法计算。q如果该厂生产的产品如果该厂生产的产品2 2，生产一件所需要设备，生产一件所需要设备A,B A,B 以

13、及调试工序的时间分别变为以及调试工序的时间分别变为8 8h,4h,1hh,4h,1h，该产品的该产品的利润变为利润变为3 3元元/ /件，对该公司的最优生产计划有何改件，对该公司的最优生产计划有何改变？变？运筹学教程解：将改变的产品看作是一件新的产品，生产量解：将改变的产品看作是一件新的产品，生产量X2将其反映到单纯形表将其反映到单纯形表2/12/12/1114823410214102154512/3148)2/1 , 4/1 , 0(3,148, 321 2222PBPPCCj 2 1 3 0 0 0CB 基基 b X1 x2 X2 x3 x4 x50 x3 15/22 x1 7/21 x2

14、 3/20 0 11/2 1 5/4 -15/21 0 0 -1/20 1 0 -1/4 3/2 Cj-Zj0 0 3/2 0 -1/4 -1/2Cj 2 1 3 0 0 0CB 基基 b X1 x2 x2 x3 x4 x50 x3 -92 x1 23 x2 30 0 0 1 4 -241 0 0 0 1/2 -20 1 1 0 -1/2 3Cj-Zj0 0 0 0 1/2 -5原问题与对偶问题均为非可行解，先使原问题转化为可行解原问题与对偶问题均为非可行解，先使原问题转化为可行解第一行的约束：第一行的约束：x x3+4x+4x4-24x-24x5=-9,=-9,乘以（乘以（-1-1），加上人

15、工变），加上人工变量量 -x -x3-4x-4x4+24x+24x5 +x+x6 =9=9Cj 2 1 3 0 0 0 -MCB 基基 b X1 x2 x2 x3 x4 x5 x6- M x6 92 x1 23 x2 30 0 0 -1 - 4 24 11 0 0 0 1/2 -2 00 1 1 0 -1/2 3 0Cj-Zj0 0 0 -M -4M -5+24M 0运筹学教程Cj 2 3 0 0 0 -MCB 基基 b x1 x2 x3 x4 x5 x60 x5 3/82 x1 11/43 x2 15/80 0 -1/24 -1/6 1 1/241 0 -1/12 1/6 0 1/120 1

16、 1/8 0 0 -1/8Cj-Zj0 0 -5/24 -1/3 0 -M+5/24运筹学教程 运筹学教程 设产品设产品1 1，2 2经过调试后，必须增加环境调试工序，经过调试后，必须增加环境调试工序，1 1产品产品每件须环境调试每件须环境调试3 3h h， 2 2产品每件须环境调试产品每件须环境调试2 2h h，环境调试环境调试可用能力可用能力1212h h，分析增加工序后的最优生产计划。分析增加工序后的最优生产计划。Cj 2 1 0 0 0 0CB 基基 b X1 x2 x3 x4 x5 x60 x3 15/22 x1 7/21 x2 3/20 x6 120 0 1 5/4 -15/2 0

17、1 0 0 -1/2 00 1 0 -1/4 3/2 03 2 0 0 0 1Cj-Zj0 0 0 -1/4 -1/2 0122434运筹学教程Cj 2 1 0 0 0 0CB 基基 b X1 x2 x3 x4 x5 x60 x3 15/22 x1 7/21 x2 3/20 x6 -3/20 0 1 5/4 -15/2 01 0 0 -1/2 00 1 0 -1/4 3/2 00 0 0 -1/4 -3/2 1Cj-Zj0 0 0 -1/4 -1/2 0Cj 2 1 0 0 0 0CB 基基 b X1 x2 x3 x4 x5 x60 x3 152 x1 41 x2 00 x5 10 0 1 5/2 0 -51 0 0 1/3 0 -1/30 1 0 -1/2 0 10 0 0 1/6 1 -2/3Cj-Zj0 0 0 -1/6 0 -1/3运筹学教程jijij运筹学教程运筹学教程