运筹学06-线性规划的灵敏度分析与对偶.ppt

《运筹学06-线性规划的灵敏度分析与对偶.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第六章单纯型法灵敏度分析与对偶6.1单纯型表的灵敏度分析6.2线性规划的对偶问题6.3对偶规划的基本性质6.4对偶单纯型法上表中6个常数a1,a2,a3,b,1,2取值在什么范围可使1、现可行解最优，且唯一？何时不唯一？2、现基本解不可行；3、问题无可行解；4、无有限最优解；5、现基本解可行，由x1取代x6目标函数可改善。CCBXBb'x1x2x3x4x5x6x3b4a110a20x42-1-501-10x63a3-300-41σ1σ200-30线性规划标准形式(1)、参数A，b，C在什么范围内变动，对当前方案无影响？(2)、参数A，b，C中的一个(几个)变动，对当前方案影响？

2、(3)、如果最优方案改变，如何用简便方法求新方案？当线性规划问题中的一个或几个参数变化时，可以用单纯形法从头计算，看最优解有无变化，但这样做既麻烦又没有必要。灵敏度分析一词的含义是指对系统或事物因周围条件变化显示出来的敏感程度的分析。灵敏度分析的步骤：1．将参数的改变通过计算反映到最终单纯形表上来；2．检查原问题的解是否仍为可行解；3．检查原问题的最优解是否仍为最优解；4．按下表所列情况得出结论决定继续计算的步骡。6.1.1目标函数系数的灵敏度分析考虑检验数(1)若ck是非基变量的系数：例解：最优单纯形表试求c3在多大范围内变动时，原最优解保持不变。CI-2-3-400CBXBbx

3、1x2x3x4x5-3X22/501-1/5-2/51/5-2X111/5107/5-1/5-2/5-z00-9/5-8/5-1/528/5从表中看到σ3=c3+Δc3-(c2×a13+c1×a23)可得到Δc3≤9/5时，原最优解不变。Ci-2-3-4+Δc300CBXBbx1x2x3x4x5-3X22/501-1/5-2/51/5-2X111/5107/5-1/5-2/5-z00-9/5+Δc3-8/5-1/528/5(2)若ck是基变量的系数例求c2在什么范围内变动时，原最优解保持不变。例:下表为最优单纯形表,考虑基变量系数c2发生变化从表中看到可得到-3≤Δc2≤1时，原最

4、优解不变。设分量br变化为br+br，根据前面的讨论：最优解的基变量xB=B-1b，那么只要保持B-1(b+b)≥0，则最优基不变，即基变量保持，只有值的变化；否则，需要利用对偶单纯形法继续计算。6.1.2右端项的灵敏度分析例求当b1在由16变动为20时，原最优解是否保持不变，若变动求出新的最优解。解:下表为最优单纯形表将b’代入原最优单纯形表中，运用对偶单纯形法计算最优解。经一次迭代后，求得新的最优解:(40200)T(1)增加一个变量增加一个变量，相当于系数矩阵增加一列。增加变量xn+1则有相应的pn+1,cn+1。那么计算出B-1pn+1,n+1=cn+1-cBpn+1

5、填入最优单纯形表,若n+1≤0则最优解不变；否则，进一步用单纯形法求解。6.1.3约束系数的灵敏度分析例:前例增加x6,p6=(2,6,3)T,c6=5计算得到用单纯形法进一步求解，可得：x*=(1,1.5,0,0,0,2)Tf*=16.5C230005CBXBbx1x2x3x4x5x62x141001/403/20x5400-21/21[2]3x22011/2-1/800.25-z00-3/2-1/805/4-14(2)增加一个约束条件增加一个约束条件相当于系数矩阵中增加一行。增加一个约束条件之后，应把最优解带入新的约束，若满足则最优解不变，否则填入最优单纯形表作为新的一行，引

6、入一个新的非负变量（原约束若是小于等于形式可引入非负松弛变量，否则引入非负人工变量），并通过矩阵行变换把对应基变量的元素变为0，进一步用单纯形法或对偶单纯形法求解。例:前例增加3x1+2x2≤15，原最优解不满足这个约束。于是经对偶单纯形法迭代一步，可得：最优解为（3.5,2.25,0,0,3,2)T，最优值为13.75Ci230000CBXBbx1x2x3x4x5x62x141001/4000x5400-21/2103x22011/2-1/8000x6-100-1-1/201-z00-3/2-1/800-14(3)技术系数改变(计划生产的产品工艺结构改变)①非基变量xj工艺改变只

7、影响单纯形表Pj列，j.关键看j0?还是>0?.用增加新变量类似方法解决。②基变量xj工艺改变，复杂，在此暂不予讨论。例:Maxz=-2x1-3x2-4x3s.t-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4x1,x2,x3,x4,x5≥0最优单纯形表为（1）P3由(-1–3)T改为(-1–2)T（2）P1由(-1–2)T改为(1–1)TCj-2-3-400CBXBbx1x2x3x4x5-3X22/501-1/5-2/51/5-2X111/5