运筹学胡运权清华版205灵敏度分析.ppt

《运筹学胡运权清华版205灵敏度分析.ppt》由会员分享，可在线阅读，更多相关《运筹学胡运权清华版205灵敏度分析.ppt（48页珍藏版）》请在优知文库上搜索。

1、 第五节第五节 灵敏度分析灵敏度分析 一、分析一、分析 的变化的变化 二、分析二、分析 的变化的变化 三、增加一个变量三、增加一个变量 的分析的分析 四、分析四、分析 的变化的变化 五、增加一个约束条件的分析五、增加一个约束条件的分析jcibjxija 灵敏度问题灵敏度问题l背景：背景：线性规划问题中，线性规划问题中，都是都是常数，但这些系数是估计值和预测值。常数，但这些系数是估计值和预测值。市场的变化市场的变化 值变化；值变化；工艺的变化工艺的变化 值变化；值变化；资源的变化资源的变化 值变化。值变化。jiijcba,jcibijal问题：问题：当这些系数中的一个或多个发生变化当这些系数中的

2、一个或多个发生变化时，原最优解（基）会怎样变化？时，原最优解（基）会怎样变化？当这些系数在什么范围内变化时，原当这些系数在什么范围内变化时，原最优解（基）仍保持不变？最优解（基）仍保持不变？若最优解发生变化，如何用最简单的若最优解发生变化，如何用最简单的方法找到现行的最优解？方法找到现行的最优解？l研究内容：研究内容：研究线性规划中，研究线性规划中，的变的变化对最优解的影响化对最优解的影响。jiijcba,l研究方法：研究方法：图解法图解法对偶理论分析对偶理论分析仅适用于含仅适用于含2个变量个变量的线性规划问题的线性规划问题在单纯形表中在单纯形表中进行分析进行分析实例：实例：某家电厂家利用现有

3、资源生产两种产品，有关数据如下表：设备设备A 设备设备B调试工序调试工序利润（元）利润（元）0612521115时时24时时 5时时D如何安排生产，如何安排生产，使获利最多？使获利最多？厂厂家家设设 产量产量 产量产量1x2x0,5 2426 155 2max 212121221xxxxxxxs.t.xxz32154213543212/14/10002/34/10102/32/14/10012/72/154/51002/1500012yyyyyxxxxxxxxjjzc 原问题最优解对偶问题最优解（相差负号）XB b一、分析一、分析 的变化的变化jc cj的变化仅影响原最优表的检验行，即的变化仅

4、影响原最优表的检验行，即原最优解的最优性可能会变化原最优解的最优性可能会变化。基列基列常数列常数列X XSXBB-1bB-1A B-1cj-zj-CBB-1bC-CBB-1A -CBB-1原最优表原最优表最优性不变，则原最优解不变。最优性不变，则原最优解不变。最优性改变，则原最优解改变，最优性改变，则原最优解改变，用原始单纯形法，找出新最优解。用原始单纯形法，找出新最优解。例例5 5 在上述美佳公司的例子中在上述美佳公司的例子中 设备设备A 设备设备B调试工序调试工序利润（元）利润（元）0612521115时时24时时 5时时D1.52问题1：当 该公司最优生 产计划有何变化？2,5.121c

5、c解解:把变化反映到原最终单纯形表上把变化反映到原最终单纯形表上4/98/10002/34/10102/322/14/10012/75.12/154/51002/15000025.121354321xxxxxxxxbXCBBjcjjzc 重新计算检验行重新计算检验行非最优，采用原始单纯形法继续迭代非最优，采用原始单纯形法继续迭代4/98/10002/34/10102/322/14/10012/75.12/154/51002/15000025.121354321xxxxxxxxbXCBBjcjjzc 换基后单纯形表为换基后单纯形表为2/3010/100005/11032105/10125.161

6、5/4006000025.121454321xxxxxxxxbXCBBjcjjzc 新最优解 问题问题2：设产品：设产品II利润为利润为 ，求原最优解不变时求原最优解不变时 的范围。的范围。)1(的变化仅影响的变化仅影响 的变化；的变化；在最后一张单纯形表中求出变化的在最后一张单纯形表中求出变化的 ；原最优解不变，即原最优解不变，即 ；由上述不等式可求出由上述不等式可求出 的范围。的范围。2cjj0j方法：方法：232141410002/34/10102/312/14/10012/722/154/51002/1500001221354321xxxxxxxxbXCBBjcjjzc 时，仍最优即：

7、当13102321,04141把变化反映到原最终单纯形表上把变化反映到原最终单纯形表上二、分析二、分析 的变化的变化ib bi的变化仅影响常数列，即原最的变化仅影响常数列，即原最优解的可行性可能会变化：优解的可行性可能会变化：基列基列常数列常数列X XSXBB-1bB-1A B-1cj-zj-CBB-1bC-CBB-1A -CBB-1原最优表原最优表若若 bbB-1b-CBB-1b把变化反映到原最优表上把变化反映到原最优表上1.可行性不变（可行性不变（B-1b0），），则则原最优基不变。原最优基不变。2.可行性改变（可行性改变（B-1b 0），则原最优基改变则原最优基改变;用对偶单纯形法，找出

8、最优解。用对偶单纯形法，找出最优解。例例6 在上述美佳公司的例子中在上述美佳公司的例子中问题问题1：设备：设备B B的能力增加到的能力增加到32小时，小时，原最优计划有何变化？原最优计划有何变化？2/34/102/14/102/154/511B080b解：解：22101bB2/12/112/3522102/32/72/15111bBbBbB2/14/10002/34/10102/112/14/10012/1122/154/51002/3500001221354321xxxxxxxxbXCBBjcjjzc 把变化反映到原最优单纯形表中把变化反映到原最优单纯形表中主元主元2001061040201

9、001152001501500001241354321xxxxxxxxbXCBBjcjjzc 新的最优解新的最优解换基迭代得：换基迭代得：问题问题2：设调试工序可用时间为：设调试工序可用时间为 小时，求小时，求 ，原最优基保持不变。，原最优基保持不变。)5(?2/3)1(2/)7(2/15)1(524152/34/102/14/102/154/511bB32154213543212/14/10002/34/10102/32/14/10012/72/154/51002/1500012yyyyyxxxxxxxx把变化反映到原最优单纯形表中把变化反映到原最优单纯形表中0,1100最优基不变即：2/3

10、)1(2/)7(2/15)1(jjzc XB b三、增加一个变量三、增加一个变量 的分析的分析jx基列基列常数列常数列X XSXBB-1bB-1A B-1cj-zj-CBB-1bC-CBB-1A -CBB-1原最优表原最优表基列基列常数列常数列X XSXSbA Icj-zj0C 0原初始表原初始表xjPjcj新新把变化反映到原最优表上把变化反映到原最优表上xjB-1Pjcj-CBB-1Pj 例例7：设生产第三种产品，产量为设生产第三种产品，产量为 件，件，对应的对应的 求最优生产计划。求最优生产计划。6xTPc)2,4,3(,3662/1,4/1,01BCB2/34/102/14/102/15

11、4/511B解：解：12432/1,4/1,036166PBCcB207616PBP把变化反映到原最优单纯形表中把变化反映到原最优单纯形表中2/14/10002/34/10102/312/14/10012/722/154/51002/1500001221354321xxxxxxxxbXCBBjcjjzc 120736x主元主元换基后有：换基后有：4/58/102/104/38/102/104/332/14/10012/724/98/312/704/5100001261354321xxxxxxxxbXCBBjcjjzc 010036x新的最优解新的最优解 增加一个变量相当于增加一种产品。增加一个

12、变量相当于增加一种产品。分析步骤：分析步骤：1、计算、计算2、计算、计算3、若、若 ，原最优解不变；，原最优解不变；若若 ，则按单纯形表继续迭代，则按单纯形表继续迭代 计算找出最优解。计算找出最优解。jBjjjjPBCczc1jjPBP10 j0 j总结：总结：四、分析四、分析 的变化的变化ija原最优表基列基列常数列常数列 x1.xj.xn XS XBB-1b B-1 P1.B-1 Pj.B-1 Pn B-1 cj-zj-CBB-1b .cj-CBB-1Pj.若Pj Pj把变化反映到原最优表B-1Pjcj-CBB-1Pj 上表可能不再满足单纯形表特点：基变量下方是单位列向量，需通过初等行变换

13、把基变量下方化为单位列向量。例例8：若家电若家电II每件需设备每件需设备A、B和调试工时和调试工时变为变为8h、4h和和1h，利润变为，利润变为c23。求最优生产计划。求最优生产计划。解：解：2/31482/1,4/1,0322/12/12/111482/34/102/14/102/154/512P32154213543212/14/10002/34/10102/32/14/10012/72/154/51002/1500012yyyyyxxxxxxxxXB b把变化反映到原最优单纯形表中把变化反映到原最优单纯形表中3x21/23/21/211/2jjzc x2基变量基变量非单位列向量非单位列向

14、量32-9 0 0 1 4 -24000032x1x3bXCBBjcjjzc x2x1x2x3x4x52 1 0 0 1/2 -23 0 1 0 -1/2 30 0 0 1/2 -5（P）不可行）不可行（D）不可行）不可行？第第1行约束可写为行约束可写为9244543xxx9244543xxx加入人工变量加入人工变量x692446543xxxx32 9 0 0 -1 -4 24-M00032x1x6bXCBBjcjjzc x2x1x2x3x4x52 1 0 0 1/2 -23 0 1 0 -1/2 30 0 -M 1/2-4M -5+24M00016xM-Mx61/241/12-1/832 3

15、/8 0 0 -1/24 -1/6 1000032x1x5bXCBBjcjjzc x2x1x2x3x4x511/4 1 0 -1/12 1/6 015/8 0 1 1/8 0 0 0 0 -5/24 -1/3 0-M+5/24新最优解新最优解五、增加一个约束条件的分析五、增加一个约束条件的分析 增加一个约束条件相当于增添一道工序。增加一个约束条件相当于增添一道工序。分析方法：分析方法：将最优解代入新的约束中将最优解代入新的约束中（1）若满足要求，则原最优解不变；）若满足要求，则原最优解不变；（2）若不满足要求，则原最优解改变，）若不满足要求，则原最优解改变，将新增的约束条件添入最终的将新增的约

16、束条件添入最终的单纯形表中继续分析。单纯形表中继续分析。例例9：设家电设家电I、II经调试后，还需经过一道经调试后，还需经过一道环境试验工序。家电环境试验工序。家电I每件需环境试验每件需环境试验3h，家电家电II每件每件2h，又环境试验工序每天生产能，又环境试验工序每天生产能力为力为12h。试分析最优生产计划。试分析最优生产计划。解：解：122321 xx将原问题最优解将原问题最优解x17/2，x23/2代代入新约束入新约束122/272/322/73因不满足新约束，所以最优解改变。不满足新约束，所以最优解改变。加入松弛变量，加入松弛变量，填入原最优表填入原最优表0 x612 15/2 0 0 1 5/4 -15/2 0000012x1x3bXCBBjcjjzc x2x1x2x3x4x5 0 0 0 -1/4 -1/2 0非单位列向量非单位列向量x67/2 1 0 0 1/4 -1/2 03/2 0 1 0 -1/4 3/2 012 3 2 0 0 0 102行行（3）4行行3行行（2）4行行0 x612 15/2 0 0 1 5/4 -15/2 0000012x1x3bXCBBjcj