运筹学05-灵敏度分析.ppt

第五章线性规划灵敏度分析,5.1目标函数系数的灵敏度分析5.2右端项的灵敏度分析5.3约束系数的灵敏度分析5.4参数规划,上表中6个常数a1,a2,a3,b,1,2取值在什么范围可使1、现可行解最优，且唯一？何时不唯一？2、现基本解不可行；3、问题无可行解；4、无有限最优解；5、现基本解可行，由x1取代x6目标函数可改善。,线性规划标准形式,(1)、参数A，b，C在什么范围内变动，对当前方案无影响？,(2)、参数A，b，C中的一个(几个)变动，对当前方案影响？,(3)、如果最优方案改变，如何用简便方法求新方案？,当线性规划问题中的一个或几个参数变化时，可以用单纯形法从头计算，看最优解有无变化，但这样做既麻烦又没有必要。,灵敏度分析一词的含义是指对系统或事物因周围条件变化显示出来的敏感程度的分析。,5.1目标函数系数的灵敏度分析,考虑检验数,(1)若ck是非基变量的系数：,解：最优单纯形表,例,试求c3在多大范围内变动时，原最优解保持不变。,从表中看到3=c3+c3-(c2a13+c1a23)可得到c39/5时，原最优解不变。,(2)若ck是基变量的系数,例,求c2在什么范围内变动时，原最优解保持不变。,下表为最优单纯形表,考虑基变量系数c2发生变化,从表中看到可得到-3c21时，原最优解不变。,设分量br变化为br+br，根据前面的讨论：最优解的基变量xB=B-1b，那么只要保持B-1(b+b)0，则最优基不变，即基变量保持，只有值的变化；否则，需要利用对偶单纯形法继续计算。,5.2右端项的灵敏度分析,例,求当b1在由8变动为12时，原最优解是否保持不变，若变动求出新的最优解。,解:下表为最优单纯形表,将b代入原最优单纯形表中，运用对偶单纯形法计算最优解。,经一次迭代后，求得新的最优解:(43200)T,(1)增加一个变量增加一个变量，相当于系数矩阵增加一列。增加变量xn+1则有相应的Pn+1,cn+1。那么计算出B-1Pn+1,n+1=cn+1-cBpn+1填入最优单纯形表,若n+10则最优解不变；否则，进一步用单纯形法求解。,5.3约束系数的灵敏度分析,例,求当增加x6,P6=(2,6,3)T,c6=5时，原最优解是否保持不变，若变动求出新的最优解。,解:下表为最优单纯形表,用单纯形法进一步求解，可得：x*=(1,1.5,0,0,0,2)Tf*=16.5,(2)增加一个约束条件增加一个约束条件相当于系数矩阵中增加一行。增加一个约束条件之后，应把最优解带入新的约束，若满足则最优解不变，否则填入最优单纯形表作为新的一行，引入一个新的非负变量（原约束若是小于等于形式可引入非负松弛变量，否则引入非负人工变量），并通过矩阵行变换把对应基变量的元素变为0，进一步用单纯形法或对偶单纯形法求解。,例,求当增加3x1+2x215时，原最优解是否保持不变，若变动求出新的最优解。,解:下表为最优单纯形表,将3x1+2x2+x6=15代入原最优单纯形表。,经对偶单纯形法迭代一步，可得：最优解为(3.5,2.25,0,0,3,2)T，最优值为13.75,(3)技术系数改变(计划生产的产品工艺结构改变)非基变量xj工艺改变只影响单纯形表Pj列，j.关键看j0?还是0?.用增加新变量类似方法解决。基变量xj工艺改变，复杂，在此暂不予讨论。,最优单纯形表为,（1）P3由(-13)T改为(-12)T（2）P1由(-12)T改为(11)T,例,解：（1）P3由(-13)T改为(-12)T由最由单纯形表可知,所以原最优解不变,（2）P1由(-12)T改为(11)T由最优单纯形表可知,代入最优单纯形表，用P1代替P1,所以，新的最优解为:(0,5/7,11/7,0,0)T最优值为：-59/7,5.4参数线性规划,在线性规划的实际应用中，由于某种原因，线性规划问题的目标函数的价值系数C和约束条件的右端常数b会随着某个参数而连续变动。当数据随着某个参数连续变化时，研究其对最优解的影响，即为参数线性规划问题。目标函数的价值系数含有参数的线性规划问题右端常数含有参数的线性规划问题,(1)目标函数的价值系数含有参数的线性规划问题,求解步骤：令=0，求得最优解与最优基B；根据求得的区间；运用单纯形法求得其余区间的最优解。,例,解：化为标准形；求=0的最优解与最优基B,则=0时最优解为(01002300020)T,根据求得的区间,即当,时最优解为,运用单纯形法求得其余区间的最优解,最优解为,当,时,当,时,参变量的取值范围与最优解为,（2）右端常数含有参数的线性规划问题,求解步骤：令=0，求得最优解与最优基B；根据求得的区间；运用对偶单纯形法求得其余区间的最优解。,例,解：化为标准形；求=0的最优解与最优基B,根据求得的区间；,则=0时最优解为(0100