灵敏度分析(运筹学)教材课件.ppt
《灵敏度分析(运筹学)教材课件.ppt》由会员分享,可在线阅读,更多相关《灵敏度分析(运筹学)教材课件.ppt(60页珍藏版)》请在三一办公上搜索。
1、第五节灵敏度分析,大连海事大学交通运输管理学院,2.5.1 单纯形法的矩阵描述2.5.2 图解法灵敏度分析2.5.3 单纯形法灵敏度分析,第五节灵敏度分析,在单纯形法的迭代中,我们注意到,迭代过程中主要应用了矩阵的行变换,如在某一行上乘以一个不等于0的乘数k,或在某一行上乘以常数k加到另一行上。这种迭代过程相当于左乘一个相应的初等阵,而初等阵及其乘积为可逆矩阵。因此,约束方程系数矩阵的迭代实际上相当于左乘相应的可逆矩阵。,2.5.1 单纯形法的矩阵描述,Cj,x1,x2,x3,x4,XB,b,CB,1 1 1 0 1 2 0 1,2 3 0 0,34,x3 x4,00,cj-zj,2,3,0,
2、0,1/2 0 1-1/2 1/2 1 0 1/2,x3 x2,12,cj-zj,1/2 0 0-3/2,03,1 0 2-1 0 1-1 1,x1 x2,21,cj-zj,0 0-1-1,23,2.5.1 单纯形法的矩阵描述,1.约束方程系数矩阵的变化约束方程系数矩阵,进行初等行变换,相当于左乘一个相应的初等阵。即,在A中所包含的矩阵B,左乘 后,则得到。2.约束方程右端项的变化3.目标函数系数的变化由,得,两边左乘基变量的目标函数系数,得到 与 得到,2.5.1 单纯形法的矩阵描述,用单纯形表表示如下:,XS=b,B N E,XB=b E N B-1,初始表 XB XN XS,cj-zj
3、0,0 N S,最终表 XB XN XS,cj-zj B N 0,0,表中,b=B-1 b N=B-1 N 或者 Pj=B-1 PjN=CN-CB B-1 N或者j=Cj-CBB-1 PjS=-CB B-1,-第2章 对偶问题-,-7-,练习:用单纯形法解目标规划问题时,有如下二个单纯形表,试求括弧中未知数al的值。,x1,x2,x3,x4,XB,b,(b)(c)(d)1 0-1 3(e)0 1(a)1-2 0 0,6 1,x4 x5,cj-zj,XB b,x1 x2 x3 x4 x5,x1 x5,cj-zj,x5,(g)2-1 1/2 0(h)(i)1 1/2 10 7(j)(k)(l),(
4、f)4,以前讨论线性规划问题时,假定ij,bi,cj都是常数。但实际上这些系数往往是估计值和预测值。如市场条件一变,cj值就会变化;ij往往是因工艺条件的改变而改变;bi是根据资源投入后的经济效果决定的一种决策选择。显然,当线性规划问题中某一个或几个系数发生变化后,原来已得结果一般会发生变化。因此,所谓灵敏度分析,是指当线性规划问题中的参数发生变化后,引起最优解如何改变的分析。,2.5.2 图解法灵敏度分析,例子,用图解法求得的最优解为Q(4,2)点。即生产甲产品4件,乙产品2件。,考虑目标函数系数变化对例题中最优产量解有什么影响。甲产品的利润为2元,乙产品的利润为3元,如果其中一种产品的利润
5、增加,公司就会增加该产品的产量,如果其中一种产品的利润减少,公司就会减少该产品的产量。但问题是,利润变化多少时,管理者才应该决定改变产量呢?每个目标函数都有一个最优范围,目标函数系数在此范围内变化,模型最优解保持不变。下面用图解法求解这个最优范围。,1.目标函数系数的变化,只要目标函数直线的斜率处于直线x1+2x2=8与直线4x1=16的斜率之间,Q2点就仍然是最优解的点。目标函数直线的斜率z=c1x1+c2x2的斜率-c1/c2 小于等于-0.5如果甲产品的单位利润不变,乙产品的单位利润改变,可得甲产品的利润范围c11.5.同理,乙产品的利润最优范围0C24。当两个系数C1、C2都改变时,我
6、们仍然可以用目标函数斜率的变化范围来确定最优解是否改变。由于系数的改变,最优值z可能发生变化而不再是原值了。,2、约束条件右端值的变化,约束条件右端值每增加一个单位引起的最优值的改进量称为对偶价格。对偶价格只适用于在右端值仅发生了很小变动的情况,在其他系数不变的情况下,一些参数在一定范围内变化最优解不变。但是如果一些参数的变化较大,最优解就可能发生变化。这样就要问:这些参数在什么范围内变化时,问题的最优基(或最优解)不变,或者当这些参数中的一个或几个发生变化时,问题的最优解会有何变化。这就是灵敏度分析要研究解决的问题。,2.5.3 单纯形法灵敏度分析,当某一个参数发生变化后,引起最优解如何改变
7、的分析。可以改变的参数有:bi约束右端项的变化,通常称资源的改变;cj 目标函数系数的变化,通常称市场条件的变化;pj 约束条件系数的变化,通常称工艺系数的变化;其他的变化有:增加一种新产品、增加一道新的工序等。,1.灵敏度分析的概念:,(1)借助最终单纯形表将变化后的结果按下述基本原则反映到最终表里去。bi变化:(b+b)=B-1(b+b)=B-1 b+B-1 b=b+B-1 bpj变化:(pj+pj)=B-1(pj+pj)=B-1 pj+B-1 pj=pj+B-1 pj cj变化:直接反映到最终表中,计算检验数。增加一个约束方程:直接反映到最终表中。增加新产品:仿照pj变化。,2分析原理及
8、步骤:,(2)检查改变后的最终表是否符合单纯形表的结构要求(基变量的值中无负数,基变量的系数向量构成单位矩阵,基变量的检验数全为0),或是否符合对偶单纯形表的结构要求(检验数中无正数,基变量的检验数全为0,基变量的系数向量构成单位矩阵);(3)检查原问题是否仍为可行解;(4)检查对偶问题是否仍为可行解;,2分析原理及步骤:,(5)按照下表所列情况得出结论或继续计算的步骤。,2分析原理及步骤:,2.1资源数量变化的分析,资源数量变化是指资源中某系数br发生变化,即br=br+br。并假设规划问题的其他系数都不变。这样使最终表中原问题的解相应地变化为XB=B-1(b+b)这里b=(0,,br,0,
9、,0)T。只要XB0,因最终表中检验数不变,故最优基不变,但最优解的值发生了变化,所以XB为新的最优解。新的最优解的值可允许变化范围用以下方法确定。,B-1 是最终计算表中的最优基的逆,最优基不变,即在最终表中求得的经过变化后的b列的所有元素要求不小于0,例如求例题中第二个约束条件b2的变化范围。,解:利用题中最终计算表中的数据:,-第2章 对偶问题-,-21-,可计算b2:,由上式,可得b2-4/0.25=-16,b2-4/0.5=-8,b22/0.125=16。所以b2的变化范围是-8,16;显然原b2=16,加它的变化范围后,b2的变化范围是8,32。,例 从表得知,第一种资源的影子价格
10、为1.5元,若该厂又从其他处抽调4单位资源用于生产产品,。求这时该厂生产产品,的最优方案。,解 先计算B-1b,将结果反映到最终表1-5中,得 表2-10。,-第2章 对偶问题-,-24-,由于表2-10中b列有负数,故用对偶单纯形法求新的最优解。计算结果见表2-11。,表2-11,-第2章 对偶问题-,-25-,即该厂最优生产方案应改为生产4件产品,生产3件产品,获利z*=42+33=17(元)从表2.11 看出x3=2,即设备还有2小时未被利用,目标函数中价值系数cj的变化分析,分为cj是对应的非基变量和基变量两种情况。(1)若cj是最终单纯形表中,非基变量xj的系数,要保证最终表中这个检
11、验数仍小于或等于零。(2)若cj是最终单纯形表中,基变量xj的系数,要保证最终表中所以的非基变量的检验数仍小于或等于零。,例:设基变量x2的系数c2变化c2,在原最优解不变条件下,确定c2的变化范围。,解 这时表1-5最终计算表便成为下表所示。,若保持原最优解,从表2-12的检验数行可见应有由此可得c2-3 和c21。c2的变化范围为-3c21即x2的价值系数c2可以在0,4之间变化,而不影响原最优解。,3 技术系数ij的变化,分两种情况来讨论技术系数ij的变化,下面以具体例子来说明。例:分析在原计划中是否应该安排一种新产品。设该厂除了生产产品,外,现有一种新产品III。已知生产产品III,每
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 灵敏度 分析 运筹学 教材 课件

链接地址:https://www.31ppt.com/p-2160349.html