《运筹学-扰动、参数规划和灵敏度分析(名校讲义)》由会员分享，可在线阅读，更多相关《运筹学-扰动、参数规划和灵敏度分析(名校讲义)（28页珍藏版）》请在金锄头文库上搜索。
1、第十一、十二讲第十一、十二讲 扰动扰动扰动扰动 、参数、参数规规规规划划 和灵敏度分析和灵敏度分析 1 扰动及参数规划 2 保持最优基时的参数灵敏度分析 1 1 扰动扰动 及参数及参数规规划划 （1 1）在实际应用的问题中，各种参数数据往往不准确，因此了解参 数数据变化对已求得的解有多大影响非常重要。 为简化，设问题题非退化的标准线性规划：AX=b，X0，CTX=min (1) 前已叙及，单纯形每个阶段都在求解对偶矢量Y的平衡解：YTaj=cj(jB) (2) 其中，B是当前基础解集，当Y是对偶可行解时，就达最优解 。 即： YTajcj (j=1,n) (3) 与此时相对应的X也必是(1)的
2、最优解，Y必是对偶最优解：YTAjCT，YTb=max (4)min cost= CTX= YTb (cost表示目标费用值) (5)1 1 扰动扰动 及参数及参数规规划划 （2 2）1若b进行小变b（不影响最优解集的变更）时，其最优费用 如何变化？这种情况，最小费用cost变化为：cost= YT (b)=y1b 1+y2b 2+ymb m (6)这个漂亮结果根据对偶理论可一目了然，这是因为，b未 引起基础解集变化，故对偶解也未变化。当然最优费用的变化 必为YT(b)。值得指出的是，此时最优解集未变化，但最优解的数值会 变化，系统求解方程为：1 1 扰动扰动 及参数及参数规规划划 （3 3）
3、由此知，扰动后的新基础可行解X+X最优，且旧的最优对偶 解Y仍保持最优。保持这个结论的唯一条件是，b应足够 小，使基础分量xj+xj0。 2若b的变化b太大或者是退化阵，则新的解变化可引用参数 规划理论来解释。设有2个设备矢量（右端系数）b0和b1，引进参数 和线段：b( )=(1 )b 0+ b1 (0 1)现保持A和C不变，则矢量b( )族产生了线性规划族：AX=(1 )b0+ b1 (0 1)X0，CTX = min = ( ) (11) 问题是，最小费用 ( )如何随参数 的变化而变化？1 1 扰动扰动 及参数及参数规规划划 （4 4）定理：若（11）式中，当 =0和 =1时可分别得出
4、相应最优 解为X0和X1时，则当0( jB)， x0s=0(s B)， A扰动必产生基础矩阵扰动； M =(aj) jB最后，解得1 1 扰动扰动 及参数及参数规规划划 （7 7）最后，推导一下M阵扰动M后，其逆阵M1=U之扰动U。 推导可得：2 2 保持最优基时的参数灵敏度保持最优基时的参数灵敏度 分析分析 （1 1）为分析方便，举一实例说明。例1-29 某车间生产3种产品，产品型号为I，每 件产品消耗机时分别为6，5和8小时，占有存储空间分别 为10，20和10；其利润分别为5，4.5和6。此外，I型产品 限制量为8。车间共有机时和存储空间分别为60和150。 问该车间应生产各类产品多少件
5、才能获得最大利润？2 2 保持最优基时的参数灵敏度保持最优基时的参数灵敏度 分析分析 （2 2）解该问题的线性规划模型为max z=5x1+4.5x2+6x36x1+5x2+8x3 6010x1+20x2+10x3150x1 8 其中，x1，x2，x3分别表示I，型产品产量。x1，x2， x3全0。2 2 保持最优基时的参数灵敏度保持最优基时的参数灵敏度 分析分析 （3 3）写成标准线性规划（加松驰变量）：6x1+5x2+8x3+x4 =6010x1+20x2+10x3 +x5 =150x1 + x6 =85x1+4.5x2+6x3 z =0注意：上面的标准线性规划与以前讲的略有差别，即为：A
6、X=b，X0，CTX=max (50)2 2 保持最优基时的参数灵敏度保持最优基时的参数灵敏度 分析分析 （4 4）其中，CTX是求极大而不是极小。这无本质差别。这只影响判断行元素符号及判断规则。为了与以前对应，也把检验元素(zjcj)改为(cjzj),这样，判断规则也就一样了。即 ：当所有(cjzj)0，就最优。若(cjzj)0，xs可进入基础集B。根据此规则，可将该问题的初始单纯形表格示如表1-7中。2 2 保持最优基时的参数灵敏度保持最优基时的参数灵敏度 分析分析 （5 5）Via1a2a3a4a5a6b基变量x1x2x3x4x5x6 x46581 60x5102010 1 150x61
7、00 18cjzj =54.560000Via1a2a3a4a5a6b基变量x1x2x3x4x5x6 x46581 60x5102010 1 150x6100 18cjzj =54.560000Vi a1 a2 a3 a4 a5 a6b 基变量 x1 x2 x3 x4 x5 x6x4 x5 x6 6 5 8 110 20 10 11 0 0 160 150 8cjzj = 5 4.5 6 0 0 00表1-7 初始单纯形表格 2 2 保持最优基时的参数灵敏度保持最优基时的参数灵敏度 分析分析 （6 6）Via1a2a3a4a5a6b基变量x1x2x3x4x5x6 x46581 60x51020
8、10 1 150x6100 18cjzj =54.560000Via1a2a3a4a5a6b基变量x1x2x3x4x5x6 x46581 60x5102010 1 150x6100 18cjzj =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 1/14 11 11/7 2/7 -1/14cjzj = 0 0 -4/7 -11/14 -1/35 0表1-8 最终单纯形表格2 2 保持最优基时的参数灵敏度保持最优基时的
9、参数灵敏度 分析分析 （7 7）Via1a2a3a4a5a6b基变量x1x2x3x4x5x6 x46581 60x5102010 1 150x6100 18cjzj =54.560000Via1a2a3a4a5a6b基变量x1x2x3x4x5x6 x46581 60x5102010 1 150x6100 18cjzj =54.560000下面将结合例1-29进行参数灵敏度过分析。1 目标函数系数cj变化（单一系数变化）设xj是非基变量，令变化后系数cj = cj + cj。由于xj是非基变量，故cj只影响末行检验数 ，为使最优基不 变，只需保证变化后的 即可。即使： 2 2 保持最优基时的参数
10、灵敏度保持最优基时的参数灵敏度 分析分析 （8 8）Via1a2a3a4a5a6b基变量x1x2x3x4x5x6 x46581 60x5102010 1 150x6100 18cjzj =54.560000Via1a2a3a4a5a6b基变量x1x2x3x4x5x6 x46581 60x5102010 1 150x6100 18cjzj =54.560000故知： (51)从例1-29中的表1-8可知，当c3变为c3+ c3时，则应使： c3 4/7设x(r)是最优表格中第r行一基底变量，令其目标系数c(r)变为c (r)= c(r)+ c(r)，其它数据不变，则表格最未一行中的检验数据 变为
11、 ，其值为； 2 2 保持最优基时的参数灵敏度保持最优基时的参数灵敏度 分析分析 （9 9）Via1a2a3a4a5a6b基变量x1x2x3x4x5x6 x46581 60x5102010 1 150x6100 18cjzj =54.560000Via1a2a3a4a5a6b基变量x1x2x3x4x5x6 x46581 60x5102010 1 150x6100 18cjzj =54.560000故知： (52)(设x(r)矢量a(r)在表格中第k列)。为使上式变为标准形式，即使(52)式所示的新检验数 ，即从表格反映出仍为最优变量，则需从检验行减去第r行的行的c（r）倍（因为第r行基变量系数
12、为1，故正好使(52)式中消去c(r)。这样，可得到所有非基变量的检验数为： 2 2 保持最优基时的参数灵敏度保持最优基时的参数灵敏度 分析分析 （1010）Via1a2a3a4a5a6b基变量x1x2x3x4x5x6 x46581 60x5102010 1 150x6100 18cjzj =54.560000Via1a2a3a4a5a6b基变量x1x2x3x4x5x6 x46581 60x5102010 1 150x6100 18cjzj =54.560000其中， 是最优表格中第r个约束条件变量xj之系数。由于第r行中，其它基变量所对应的系数为0，故变换后，其 判断行的对应检验数仍为0。为保持最优，必须使 ，即 ，亦即为： 2 2 保持最优基时的参数灵敏度保持最优基时的参数灵敏度 分析分析 （1111）Via1a2a3a4a5a6b基变量x1x2x3x4x5x6 x46581 60x5102010 1 150x6100 18cjzj =54.560000Via1a2a3a4a5a6b基变量x1x2x3x4x5x6 x46581 60x5102010 1 150x6100 18cjzj =54.560000在例1-29的表1-8中，令x(3)=x1的系数c(3)=c1变为c1+ c1，则Dc1变化范围为： 即：2 2 保持最优基时的参
