运筹学扰动参数规划和灵敏分析名校讲义.pptx

《运筹学扰动参数规划和灵敏分析名校讲义.pptx》由会员分享，可在线阅读，更多相关《运筹学扰动参数规划和灵敏分析名校讲义.pptx（27页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、1 扰动及参数规划 （2）1若b进行小变b（不影响最优解集的变更）时，其最优费用如何变化？这种情况，最小费用cost变化为：cost=YT(b)=y1b 1+y2b 2+ymb m (6)这个漂亮结果根据对偶理论可一目了然，这是因为，b未引起基础解集变化，故对偶解也未变化。当然最优费用的变化必为YT(b)。值得指出的是，此时最优解集未变化，但最优解的数值会变化，系统求解方程为：第1页/共27页1 扰动及参数规划 （3）由此知，扰动后的新基础可行解X+X最优，且旧的最优对偶解Y仍保持最优。保持这个结论的唯一条件是，b应足够小，使基础分量xj+xj0。2若b的变化b太大或者是退化阵，则新的解变化可

2、引用参数规划理论来解释。设有2个设备矢量（右端系数）b0和b1，引进参数 和线段：b()=(1)b 0+b1 (0 1)现保持A和C不变，则矢量b()族产生了线性规划族：AX=(1)b0+b1 (0 1)X0，CTX=min=()(11)问题是，最小费用()如何随参数 的变化而变化？第2页/共27页1 扰动及参数规划 （4）定理：若（11）式中，当=0和=1时可分别得出相应最优解为X0和X1时，则当0(jB)，x0s=0(s B)，A扰动必产生基础矩阵扰动；M=(aj)jB最后，解得第5页/共27页1 扰动及参数规划 （7）最后，推导一下M阵扰动M后，其逆阵M1=U之扰动U。推导可得：第6页/

3、共27页2 保持最优基时的参数灵敏度分析（1）为分析方便，举一实例说明。例1-29 某车间生产3种产品，产品型号为I，每件产品消耗机时分别为6，5和8小时，占有存储空间分别为10，20和10；其利润分别为5，4.5和6。此外，I型产品限制量为8。车间共有机时和存储空间分别为60和150。问该车间应生产各类产品多少件才能获得最大利润？第7页/共27页2 保持最优基时的参数灵敏度分析（2）解该问题的线性规划模型为max z=5x1+4.5x2+6x3 6x1+5x2+8x3 60 10 x1+20 x2+10 x3150 x1 8 其中，x1，x2，x3分别表示I，型产品产量。x1，x2，x3全0

4、。第8页/共27页2 保持最优基时的参数灵敏度分析（3）写成标准线性规划（加松驰变量）：6x1+5x2+8x3+x4 =6010 x1+20 x2+10 x3 +x5 =150 x1 +x6 =85x1+4.5x2+6x3 z=0注意：上面的标准线性规划与以前讲的略有差别，即为：AX=b，X0，CTX=max (50)第9页/共27页2 保持最优基时的参数灵敏度分析（4）其中，CTX是求极大而不是极小。这无本质差别。这只影响判断行元素符号及判断规则。为了与以前对应，也把检验元素(zjcj)改为(cjzj),这样，判断规则也就一样了。即：当所有(cjzj)0，就最优。若(cjzj)0，xs可进入

5、基础集B。根据此规则，可将该问题的初始单纯形表格示如表1-7中。第10页/共27页2 保持最优基时的参数灵敏度分析（5）Via1a2a3a4a5a6b基变量x1x2x3x4x5x6x4658160 x51020101150 x610018cjzj=54.560000Via1a2a3a4a5a6b基变量x1x2x3x4x5x6x4658160 x51020101150 x610018cjzj=54.560000Vi a1 a2 a3 a4 a5 a6b 基变量 x1 x2 x3 x4 x5 x6x4 x5 x6 6 5 8 1 10 20 10 1 1 0 0 1601508 cjzj=5 4.

6、5 6 0 0 00表1-7 初始单纯形表格第11页/共27页2 保持最优基时的参数灵敏度分析（6）Via1a2a3a4a5a6b基变量x1x2x3x4x5x6x4658160 x51020101150 x610018cjzj=54.560000Via1a2a3a4a5a6b基变量x1x2x3x4x5x6x4658160 x51020101150 x610018cjzj=54.560000经过单纯形法求解，获得最优单纯形表示于表1-8中。Vi a1 a2 a3 a4 a5 a6b 基变量 x1 x2 x3 x4 x5 x6x2 x6 x1 1 -2/7 -1/7 3/35 -11/7 -2/7

7、 1/14 1 1 11/7 2/7 -1/14 cjzj=0 0 -4/7 -11/14 -1/35 0表1-8 最终单纯形表格第12页/共27页2 保持最优基时的参数灵敏度分析（7）Via1a2a3a4a5a6b基变量x1x2x3x4x5x6x4658160 x51020101150 x610018cjzj=54.560000Via1a2a3a4a5a6b基变量x1x2x3x4x5x6x4658160 x51020101150 x610018cjzj=54.560000下面将结合例1-29进行参数灵敏度过分析。1 目标函数系数cj变化（单一系数变化）设xj是非基变量，令变化后系数cj=cj

8、+cj。由于xj 是非基变量，故cj只影响末行检验数 ，为使最优基不变，只需保证变化后的 即可。即使：第13页/共27页2 保持最优基时的参数灵敏度分析（8）Via1a2a3a4a5a6b基变量x1x2x3x4x5x6x4658160 x51020101150 x610018cjzj=54.560000Via1a2a3a4a5a6b基变量x1x2x3x4x5x6x4658160 x51020101150 x610018cjzj=54.560000故知：(51)从例1-29中的表1-8可知，当c3变为c3+c3时，则应使：c3 4/7设x(r)是最优表格中第r行一基底变量，令其目标系数c(r)变

9、为c(r)=c(r)+c(r)，其它数据不变，则表格最未一行中的检验数据 变为 ，其值为；第14页/共27页2 保持最优基时的参数灵敏度分析（9）Via1a2a3a4a5a6b基变量x1x2x3x4x5x6x4658160 x51020101150 x610018cjzj=54.560000Via1a2a3a4a5a6b基变量x1x2x3x4x5x6x4658160 x51020101150 x610018cjzj=54.560000故知：(52)(设x(r)矢量a(r)在表格中第k列)。为使上式变为标准形式，即使(52)式所示的新检验数 ，即从表格反映出仍为最优变量，则需从检验行减去第r行的

10、行的c（r）倍（因为第r行基变量系数为1，故正好使(52)式中消去c(r)。这样，可得到所有非基变量的检验数为：第15页/共27页2 保持最优基时的参数灵敏度分析（10）Via1a2a3a4a5a6b基变量x1x2x3x4x5x6x4658160 x51020101150 x610018cjzj=54.560000Via1a2a3a4a5a6b基变量x1x2x3x4x5x6x4658160 x51020101150 x610018cjzj=54.560000其中，是最优表格中第r个约束条件变量xj之系数。由于第r行中，其它基变量所对应的系数为0，故变换后，其判断行的对应检验数仍为0。为 保 持

11、 最 优，必 须 使 ，即 ，亦即为：第16页/共27页2 保持最优基时的参数灵敏度分析（11）Via1a2a3a4a5a6b基变量x1x2x3x4x5x6x4658160 x51020101150 x610018cjzj=54.560000Via1a2a3a4a5a6b基变量x1x2x3x4x5x6x4658160 x51020101150 x610018cjzj=54.560000在例1-29的表1-8中，令x(3)=x1的系数c(3)=c1变为c1+c1，则c1变化范围为：即：第17页/共27页2 保持最优基时的参数灵敏度分析（12）Via1a2a3a4a5a6b基变量x1x2x3x4x

12、5x6x4658160 x51020101150 x610018cjzj=54.560000Via1a2a3a4a5a6b基变量x1x2x3x4x5x6x4658160 x51020101150 x610018cjzj=54.5600002约束条件右端值bi单独变化之分析为推导方便，现列出线性规划的初始单纯形表与相应的最优单纯形表，分别示于表1-9和表1-10中。表1-9（初始表格）a11x1+a12x2+a1nxn+xn+1 =b1 ak1x1+ak2x2+aknxn +xn+k =bk am1x1+am2x2+amnxn +xn+m =bm第18页/共27页2 保持最优基时的参数灵敏度分析

13、（13）Via1a2a3a4a5a6b基变量x1x2x3x4x5x6x4658160 x51020101150 x610018cjzj=54.560000Via1a2a3a4a5a6b基变量x1x2x3x4x5x6x4658160 x51020101150 x610018cjzj=54.560000表1-10（最终表格）第19页/共27页2 保持最优基时的参数灵敏度分析（14）Via1a2a3a4a5a6b基变量x1x2x3x4x5x6x4658160 x51020101150 x610018cjzj=54.560000Via1a2a3a4a5a6b基变量x1x2x3x4x5x6x465816

14、0 x51020101150 x610018cjzj=54.560000若将表1-9中的bk扰动为bk+bk，则只需将xn+k变为xn+k bk，而令右端bk不变。这样最终表格只有第n+k列发生了变化：ikxn+k变为ik(xn+kbk)=ikxn+k ikbk (i=1,，m)由于ikbk为常数，移至右边得：第20页/共27页2 保持最优基时的参数灵敏度分析（15）Via1a2a3a4a5a6b基变量x1x2x3x4x5x6x4658160 x51020101150 x610018cjzj=54.560000Via1a2a3a4a5a6b基变量x1x2x3x4x5x6x4658160 x51

15、020101150 x610018cjzj=54.560000这说明，当bk变为bk+bk时，最优表格中，只有右边常数项元素发生变化，为仍保持最优，必须使右边常数列元素全0。所以得：,则得：例如：若将例1-29中的b2变为b2+bk（原b2=150），则参见表1-8可得（注意此时对应第5列）：第21页/共27页2 保持最优基时的参数灵敏度分析（16）Via1a2a3a4a5a6b基变量x1x2x3x4x5x6x4658160 x51020101150 x610018cjzj=54.560000Via1a2a3a4a5a6b基变量x1x2x3x4x5x6x4658160 x51020101150

16、 x610018cjzj=54.560000第22页/共27页2 保持最优基时的参数灵敏度分析（17）Via1a2a3a4a5a6b基变量x1x2x3x4x5x6x4658160 x51020101150 x610018cjzj=54.560000Via1a2a3a4a5a6b基变量x1x2x3x4x5x6x4658160 x51020101150 x610018cjzj=54.5600003百分之百规则当右端系数bi(i=1,m)同时变化或目标系数cj(j=1,，n)同时变化时，应符合什么规则才能使最优基保持不变呢？现不加证明的引述“百分之百”规则。当右端系数bk变为bk+bk时，（k=1,

17、，m）。如达到：则最优基必保持不变时，(57)第23页/共27页2 保持最优基时的参数灵敏度分析（18）Via1a2a3a4a5a6b基变量x1x2x3x4x5x6x4658160 x51020101150 x610018cjzj=54.560000Via1a2a3a4a5a6b基变量x1x2x3x4x5x6x4658160 x51020101150 x610018cjzj=54.560000其中，bkmax是bk单独变化时容许向某方向变化的最大值bk应与bkmax变化方向一致。式(57)称为百分之百规则。要注意：百分之百规则是充分条件，而不是必要条件为清楚，令例1-29中的b1与b2同时变化

18、（b3先不变），则其变化范围示于图1-19中。第24页/共27页2 保持最优基时的参数灵敏度分析（19）Via1a2a3a4a5a6b基变量x1x2x3x4x5x6x4658160 x51020101150 x610018cjzj=54.560000Via1a2a3a4a5a6b基变量x1x2x3x4x5x6x4658160 x51020101150 x610018cjzj=54.560000图1-19 b2240B1501280ACDO37.560 65.5b1从图中看出，对于2个系数同时变化的可行域是一个四边形，其中，A，B，C，D，是b1及b2变化之极点，而O是变化前的起始点。同理，目标函数系数同时变化时，需满足：第25页/共27页2 保持最优基时的参数灵敏度分析（20）Via1a2a3a4a5a6b基变量x1x2x3x4x5x6x4658160 x51020101150 x610018cjzj=54.560000Via1a2a3a4a5a6b基变量x1x2x3x4x5x6x4658160 x51020101150 x610018cjzj=54.5600004A阵中元素aij单独变化时的分析（略）第26页/共27页感谢您的观看！第27页/共27页