灵敏度分析(运筹学)ppt课件.ppt

《灵敏度分析(运筹学)ppt课件.ppt》由会员分享，可在线阅读，更多相关《灵敏度分析(运筹学)ppt课件.ppt（60页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、大连海事大学交通运输管理学院2.5.1 单纯形法的矩阵描述2.5.2 图解法灵敏度分析2.5.3 单纯形法灵敏度分析l在单纯形法的迭代中，我们注意到，迭代过程中主要应用了矩阵的行变换，如在某一行上乘以一个不等于0的乘数k,或在某一行上乘以常数k加到另一行上。这种迭代过程相当于左乘一个相应的初等阵，而初等阵及其乘积为可逆矩阵。l因此，约束方程系数矩阵的迭代实际上相当于左乘相应的可逆矩阵。Cj x1x2x3x4XBbCB1 1 1 0 1 2 0 12 3 0 034x3 x400cj - zj 23001/2 0 1 -1/2 1/2 1 0 1/2x3 x212cj - zj 1/2 0 0

2、-3/2031 0 2 -1 0 1 -1 1x1 x221cj - zj 0 0 -1 -12311B12B1. 约束方程系数矩阵的变化约束方程系数矩阵 ，进行初等行变换，相当于左乘一个相应的初等阵。即 ，在A中所包含的矩阵B，左乘 后，则得到 。 2. 约束方程右端项的变化3. 目标函数系数的变化由 ，得 ，两边左乘基变量的目标函数系数 ，得到 与 得到用单纯形表表示如下：XS = bB N EXB = b E N B-1初始表 XB XN XS cj - zj 0,0 N S最终表 XB XN XS cj - zj B N 0,0 表中，b =B-1 b N =B -1 N 或者 Pj

3、=B -1 PjN = CN-CB B-1 N或者j =Cj-CBB-1 PjS = -CB B-1-第2章 对偶问题-7-练习： 用单纯形法解目标规划问题时，有如下二个单纯形表，试求括弧中未知数al的值。 x1x2x3x4XBb(b) (c) (d) 1 0 -1 3 (e) 0 1(a) 1 - 2 0 0 6 1x4 x5cj - zj XB bx1 x2 x3 x4 x5x1 x5cj - zj x5(g) 2 -1 1/2 0 (h) (i) 1 1/2 10 7 (j) (k) (l) (f) 4以前讨论线性规划问题时，假定ij，bi,cj都是常数。但实际上这些系数往往是估计值和预

4、测值。如市场条件一变，cj值就会变化；ij往往是因工艺条件的改变而改变；bi是根据资源投入后的经济效果决定的一种决策选择。显然，当线性规划问题中某一个或几个系数发生变化后，原来已得结果一般会发生变化。因此，所谓灵敏度分析灵敏度分析，是指当线性规划问题中的参数发生变化后，引起最优解如何改变的分析。 xxz2132max jx x x xx xxtsj5 , 2 , 10124164821222. .212121用图解法求得的最优解为Q（4，2）点。即生产甲产品4件，乙产品2件。u考虑目标函数系数变化对例题中最优产量解有什么影响。甲产品的利润为2元，乙产品的利润为3元，如果其中一种产品的利润增加，

5、公司就会增加该产品的产量，如果其中一种产品的利润减少，公司就会减少该产品的产量。但问题是，利润变化多少时，管理者才应该决定改变产量呢？u每个目标函数都有一个最优范围，目标函数系数在此范围内变化，模型最优解保持不变。u下面用图解法求解这个最优范围。l只要目标函数直线的斜率处于直线x1+2x2=8与直线4x1=16的斜率之间，Q2点就仍然是最优解的点。l目标函数直线的斜率z=c1x1+c2x2的斜率-c1 /c2 小于等于-0.5l如果甲产品的单位利润不变，乙产品的单位利润改变，可得甲产品的利润范围c11.5.同理，乙产品的利润最优范围0C24。l当两个系数C1、C2都改变时，我们仍然可以用目标函

6、数斜率的变化范围来确定最优解是否改变。l由于系数的改变，最优值z可能发生变化而不再是原值了。2x1+2x2=12x2x1OQ1Q4Q3Q24x1=164x2 =12x1+2x2=8 xxz2132max jx x x xx xxtsj5 , 2 , 10124164821222. .212121约束条件右端值每增加一个单位引起的最优值的改进量称为对偶对偶价格价格。对偶价格只适用于在右端值仅发生了很小变动的情况0124164823221212121x ,xxxxx:xxzmax约束条件目标函数l在其他系数不变的情况下，一些参数在一定范围内变化最优解不变。但是如果一些参数的变化较大，最优解就可能发

7、生变化。l这样就要问：这些参数在什么范围内变化时，问题的最优基（或最优解）不变，或者当这些参数中的一个或几个发生变化时，问题的最优解会有何变化。这就是灵敏度分析要研究解决的问题。当某一个参数发生变化后，引起最优解如何改变的分析。可以改变的参数有：bi约束右端项的变化，通常称资源的改变；cj 目标函数系数的变化，通常称市场条件的变化；pj 约束条件系数的变化，通常称工艺系数的变化；其他的变化有：增加一种新产品、增加一道新的工序等。（1）借助最终单纯形表将变化后的结果按下述基本原则反映到最终表里去。bi变化： （b+b）=B-1 （b+b）= B-1 b+ B-1 b = b+B-1 bpj变化：

8、（pj+ pj ）= B-1 （pj+ pj ）= B-1 pj+ B-1 pj = pj + B-1 pj cj变化：直接反映到最终表中，计算检验数。增加一个约束方程：直接反映到最终表中。增加新产品：仿照pj变化。（2）检查改变后的最终表是否符合单纯形表的结构要求（基变量的值中无负数，基变量的系数向量构成单位矩阵，基变量的检验数全为0），或是否符合对偶单纯形表的结构要求 （检验数中无正数，基变量的检验数全为0，基变量的系数向量构成单位矩阵）;（3）检查原问题是否仍为可行解;（4）检查对偶问题是否仍为可行解;（5）按照下表所列情况得出结论或继续计算的步骤。原问题原问题对偶问题对偶问题结论或继续

9、计算的步骤结论或继续计算的步骤可行解可行解原最优基不变可行解非可行解用单纯形法继续迭代非可行解可行解用对偶单纯形法继续迭代非可行解非可行解引入人工变量，扩大原单纯形表继续计算资源数量变化是指资源中某系数br发生变化，即br=br+br。并假设规划问题的其他系数都不变。这样使最终表中原问题的解相应地变化为XB=B-1(b+b)这里b=(0,，br,0,，0)T。只要XB0，因最终表中检验数不变，故最优基不变，但最优解的值发生了变化，所以XB为新的最优解。新的最优解的值可允许变化范围用以下方法确定。mrirrrrmrrirrrrraaabbabababBbBbBbBbBbbB11111111000

10、0)(解：利用题中最终计算表中的数据：0124164823221212121x ,xxxxx:xxzmax约束条件目标函数-第2章 对偶问题-21-0008/12/14/12440008/12/112/1204/102440022211bbbBbB由上式，可得b2-4/0.25=-16，b2-4/0.5=-8，b22/0.125=16。所以b2的变化范围是-8，16；显然原b2 =16，加它的变化范围后， b2的变化范围是8，32。2800040125. 05 . 015 . 02025. 001bBcj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 0 3 x1 x5

11、 x2 4+0 4-8 2+2 1 0 0 0 0 1 0 -2 0.5 0.25 0.5 0.125 0 1 0 cj-zj 0 0 -1.5 -0.125 0 -第2章 对偶问题-24-cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 0 3 x1 x3 x2 4 2 3 1 0 0 0 0 1 0 1 0 0.25 -0.25 0 0 -0.5 0.25 cj-zj 0 0 0 -0.5 -0.75 表2-11-第2章 对偶问题-25-即该厂最优生产方案应改为生产4件产品，生产3件产品，获利z*=42+33=17(元)从表2.11 看出x3=2，即设备还有2小时

12、未被利用 分为cj是对应的非基变量和基变量两种情况。(1) 若cj是最终单纯形表中，非基变量xj的系数，要保证最终表中这个检验数仍小于或等于零。 (2) 若cj是最终单纯形表中，基变量xj的系数，要保证最终表中所以的非基变量的检验数仍小于或等于零。解解 这时表1-5最终计算表便成为下表所示。0124164823221212121x ,xxxxx:xxzmax约束条件目标函数若保持原最优解，从表2-12的检验数行可见应有由此可得c2-3 和c21。c2的变化范围为 -3c21即x2的价值系数c2可以在0，4之间变化，而不影响原最优解。 0818025 . 122cc和分两种情况来讨论技术系数ij

13、的变化，下面以具体例子来说明。例：分析在原计划中是否应该安排一种新产品。设该厂除了生产产品，外，现有一种新产品III。已知生产产品III，每件使用设备2台时，需消耗原材料A，B各为6kg，3kg；每件可获利5元。问该厂是否应生产该产品和生产多少?0124164823221212121x ,xxxxx:xxzmax约束条件目标函数(1) 设生产产品II为x3台，其技术系数向量P3=(2,6,3)T，然后计算最终表中对应x3的检验数3=c3-CB-13=5-(1.5,0.125,0)(2,6,3)T=1.250说明安排生产产品III是有利的。(2) 计算产品在最终表中对应 x3的列向量 25. 0

14、25 . 13620125. 05 . 015 . 02025. 0031PB 并将(1)，(2)中的计算结果填入最终计算表 1-5，得表 2-13(a)。 由于b列的数字没有变化，原问题的解是可行解。但检验数行中还有正检验数，说明目标函数值还可以改善。(3) 将x3作为换入变量，x5作为换出变量，进行迭代，求出最优解。计算结果见表2-13(b)，这时得最优解：x1=1,x2=1.5，x3=2。总的利润为16.5元。比原计划增加了2.5元。例10 分析原计划生产产品的工艺结构发生变化。仍有下例为例，若原计划生产产品的工艺结构有了改进，这时有关它的技术系数向量变为P1=(2,5,2)T，每件利润

15、为4元，试分析对原最优计划有什么影响? 0124164823221212121x ,xxxxx:xxzmax约束条件目标函数375. 05 . 025. 12520125. 05 . 015 . 02025. 0011PB同时计算出x1的检验数为c1-CBB-1P1=4-(1.5,0.125,0)(2,5,2)T=0.375将以上计算结果填入最终表x1的列向量位置.得表2-14。cj 4 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 0 3 x1 x5 x2 4 4 2 1.25 0.5 0.375 0 0 1 0 -2 0.5 0.25 0.5 0.125 0 1 0 c

16、j-zj 0.375 0 -1.5 -0.125 0 可见x1为换入变量，x1为换出变量，经过迭代。得到表2-15 cj 4 3 0 0 0 CB XB b x1 x2 x3 x4 x5 4 0 3 x1 x5 x2 3.2 2.4 0.8 1 0 0 0 0 1 0 -2 0.5 0.2 0.4 0.2 0 1 0 cj-zj 0 0 -1.5 -0.2 0 表2-15表明原问题和对偶问题的解都是可行解。所以表中的结果已是最优解。即应当生产产品，3.2单位；生产产品，0.8单位。可获利15.2元。注意：若碰到原问题和对偶问题均为非可行解时，就需要引进人工变量后重新求解。解解 方法与例10相同

17、，以x1代替x1，并计算列向量375. 15 . 325. 12540125. 05 . 015 . 02025. 0011PBx1的检验数为c1-CBB-1P1=4-（1.5,0.125,0)(4,5,2)T = -2.625。将这些数字填入最终表1-15的x1列的位置，得到表2-16。cj 4 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 0 3 x1 x5 x2 4 4 2 1.25 -3.5 1.375 0 0 1 0 -2 0.5 0.25 0.5 0.125 0 1 0 cj-zj -2.625 0 -1.5 -0.125 0 将表2-16的x1变换为基变量，替

18、换x1，得表2-17。 cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 4 0 3 x1 x5 x2 3.2 15.2 -2.4 1 0 0 0 0 1 0 -2 0.5 0.2 1.2 0.4 0 1 0 cj-zj 0 0 -1.5 0.4 0 从表2-17可见原问题和对偶问题都是非可行解。于是引入人工变量x6。因在表2-17中x2所在行，用方程表示时为0 x1+x2+0.5x3-0.4x4+0 x5= -2.4引入人工变量x6后，便为-x2-0.5x3+0.4x4+x6=2.4将x6作为基变量代替x2，填入表2-17，得到表2-18。这时可按单纯形法求解。X4为换

19、入变量，x6为换出变量。经基变换运算后，得到表2-19的上表。在表2-19的上表中，确定x2为换入变量，x5为换出变量。经基变换运算后，得到表2-19的下表。此表的所有检验数都为非正，已得最优解。最优生产方案为生产产品，0.667单位；产品，2.667单位，可得最大利润10.67元。 cj 4 3 0 0 0 -M CB XB b x1 x2 x3 x4 x5 X6 4 0 0 x1 x5 x4 2 8 6 1 0 0 0.5 3 1 0.25 -0.5 -1.25 0 0 1 0 1 0 0.5 -3 2.5 cj-zj 0 1 -1 0 -M+2 4 3 0 x1 x2 x4 0.667

20、12.667 12.667 1 0 0 0 0 1 0 -2 0.5 0 0 1 -0.33 0.33 0.83 0 -1 0 cj-zj 0 3-M -0.5M 0 -0.33 -M+3 除以上介绍的几项分析以外，还可以作增减约束条件等分析。留给同学自己考虑。步骤：（2）具体构造模型：选择合适的决策变量、确定目标函数的表达式、约束条件的表达式，分析各变量取值的符号限制。（1）分析问题：确定决策内容、要实现的目标以及所受到的限制条件。例1：某工厂在生产过程中需要使用浓度为80%的硫酸100 吨，而市面上只有浓度为30%，45%，73%，85%，92%的硫酸出售， 每吨的价格分别为400、700

21、、1400、1900和2500元。 问：采用怎样的购买方案，才能使所需总费用最小？设 第j 种硫酸需购买 xj 吨，则 Minz=400 x1+700 x2+1400 x3+1900 x4+2500 x5st. x1+x2+x3+x4+x5=100 30 x1+45x2+73x3+85 x4+92x5=10080 x10, x20, x30, x40, x50例2：设有下面四个投资机会： 甲：在三年内，投资人应在每年年初投资，每年每元投资可获利0.2元，每年取息后可重新将本息用于投资。 乙：在三年内，投资人应在第一年年初投资，每两年每元投资可获利0.5元，两年后取息，取息后可重新将本息用于投资

22、。这种投资最多不得超过20,000元。 丙：在三年内，投资人应在第二年年初投资，两年后每元投资可获利0.6元。这种投资最多不得超过15,000元。 丁：在三年内，投资人应在第三年年初投资，一年后每元投资可获利0.4元。这种投资最多不得超过10,000元。 假定在这三年为一期的投资中，每期的开始有30,000元资金可供使用，问：采取怎样的投资计划，才能在第三年年底获得最大收益？设 xij第 i 年投资于第 j 项目上的资金量，则st. x11+ x1230,000 x12 20,000 x21+ x2330,000 x12+ 0.2 x11 x23 15,000 x31+ x3430,000 x

23、23 +0.2(x11+ x21)+0.5x12 x3410,000 xij0, (i=1,2,3; j=1,2,3,4)x11x12x21x23x31x34123430,000Maxz=0.2 (x11+x21+ x31) + 0.5 x12 + 0.6 x2 3+ 0.4 x34例3：合理下料问题： 要制作100套钢筋架子，每套含2.9米、2.1米、1.5米的钢筋各一根。已知原料长7.4米，问：如何下料，使用料最省？方案下料数长度2.9米2.1米1.5米121221 3123合计(米)7.47.37.27.1 6.6料头(米)00.10.20.30.8设 xj 为第j种方案用料的数量,则M

24、in z=0 x1+0.1x2+0.2x3+0.3x4+0.8x5st. x1+2x2 + x4 =100 2x3+2x4+ x5=100 3x1+ x2+2x3 +3x5=100 xj0, (j=1,2,-,5)思考题：目标函数是否可以选取为 min z=x1+x2+x3+x4+x5 ，为什 么？例4：有A、B两种产品，都需要经过前、后两道化学反应过程。每种产品需要的反应时间及其可供使用的总时间如表示。 每生产一个单位产品B的同时，会产生2个单位的副产品C，且不需外加任何费用。副产品C的一部分可以出售盈利，其余的只能加以销毁。 副产品C每卖出一个单位可获利3元，但是如果卖不出去，则每单位需销

25、毁费用2元。预测表明，最多可售出5个单位的副产品C。 要求确定使利润最大的生产计划。 产品 过程 A B 可利用 时间 前道过程 2 3 16 后道过程 3 4 24 单位利润 4 10 设 产品的产量为 Ax1单位，B x2单位，st. 2x1+3x216 3x1+4x224+3x32x4已售出的产品C x3 单位，销毁的产品C x4单位，则Max z=4x1+10 x22x2=x3+x4x3 5xj0, (j=1,2,3,4)例5：一家昼夜服务的饭店，24小时中需要的服务员数如下表所示。每个服务员每天连续工作8小时，且在时段开始时上班。问：最少需要多少名服务员？试建立该问题的线性规划模型。

26、起 迄 时 间服 务 员 人 数2-6 时46-10 时810 -14 时1014 -18 时718 -22 时1222 -2 时4设 xj第j时段开始上班工作的服务员数，则Min z=x1+x2+x3+x4+x5+x6st. x6+x14 x1+x28 x2+x310 x3+x47 x4+x512 x5+x64 xj0, (j=1,2,-,6)建立线性规划模型要求：（1）要求决策的量是连续的、可控的量，或者是可以简化为连续取值的变量；（2）要求所解决的问题的目标可用数值指标描述，并且能表示成线性函数；（3）存在着多种决策方案可供选择；（4）决策所受到的限制条件可用线性的等式或者不等式表示。练

27、. 某文教用品厂用原材料白坯纸生产原稿纸，日记本和练习本三种产品。该厂现有工人100人，每月白坯纸供应量为30000公斤。已知工人的劳动生产率为：每人每月可生产原稿纸30捆，或生产日记本30打，或练习本30箱。已知原材料消耗为：每捆原稿纸用白坯纸3/10公斤，每打日记本用白坯纸40/3公斤，每箱练习本用白坯纸80/3公斤。又知每生产一捆原稿纸可获利2元，生产一打日记本获利3元，生产一箱练习本获利1元。试确定 ：（1）现有生产条件下获利最大的方案（2）如白坯纸的供应数量不变，当工人数不足时可招收临时工，临时工工资支出为每人每月40元，则该厂要不要招收临时工，招多少临时工最合适？练：童心玩具厂下一年度的现金流（万元）如表所示，表中负号表示该月现金流出大于流入，为此该厂需借款。借款有两种方式：一是于上一年末借一年期贷款，一次得全部贷款额，从1月底起每月还息1%，于12月归还本金和最后一次利息；二是得到短期贷款，每月初获得，于月底归还，月息1.5%。当该厂有多余现金时，可短期存款，月初存入，月末取出，月息0.4%。问该厂应如何进行存贷款操作，既能弥补可能出现的负现金流，又可使年末现金总量为最大？