第三章-第五节-灵敏度分析.ppt

第5节灵敏度分析p以以前前讨讨论论线线性性规规划划问问题题时时，假假定定ij，bi,cj都都是是常常数数。但但实实际际上上这这些些系系数数往往往往是是估估计计值值和和预预测测值值。如如市市场场条条件件一一变变，cj值值就就会会变变化化；ij往往往往是是因因工工艺艺条条件件的的改改变变而而改改变变；bi是是根根据据资资源源投投入入后后的的经经济济效效果果决决定定的的一一种种决决策策选择。选择。p因此提出这样两个问题：因此提出这样两个问题：(1)当当这这些些系系数数有有一一个个或或几几个个发发生生变变化化时时，已已求求得得的的线线性性规划问题的最优解会有什么变化；规划问题的最优解会有什么变化；(2)或或者者这这些些系系数数在在什什么么范范围围内内变变化化时时，线线性性规规划划问问题题的的最最优优解解或或最最优优基基不不变变。后后一一个个问问题题将将在在第第6节节参参数数线线性性规划中讨论。规划中讨论。5/26/20241.什么是灵敏度分析 灵敏度分析是要在求得最优解以后，解决以下几灵敏度分析是要在求得最优解以后，解决以下几方面的问题：方面的问题：p线性规划问题中的各系数在什么范围内变化，不线性规划问题中的各系数在什么范围内变化，不会影响已获得的最优基。会影响已获得的最优基。p如果系数的变化超过以上范围，如何在原来最优如果系数的变化超过以上范围，如何在原来最优解的基础上求得新的最优解解的基础上求得新的最优解p当线性规划问题增加一个新的变量或新的约束，当线性规划问题增加一个新的变量或新的约束，如何在原来最优解的基础上获得新的最优解如何在原来最优解的基础上获得新的最优解。5/26/20242.线性规划问题中某一个或几个系数发生变化p显然，当线性规划问题中某一个或几个系数发生变化后，原来已得结果一般会发生变化。当然可以用单纯形法从头计算，以便得到新的最优解。这样做很麻烦，而且也没有必要。因在单纯形法迭代时，每次运算都和基变量的系数矩阵B有关，因此可以把发生变化的个别系数，经过一定计算后直接填入最终计算表中，并进行检查和分析，可按表3-10中的几种情况 进行处理。5/26/20243表 3-10下面就各种情况分别按节进行讨论。5/26/20244.1.若ck是非基变量的系数：设ck变化为 ck+ck，则k=k+ck 只要 k 0,即 ck -k，则 最优解不变；否则，将最优单纯形表 中的检验数 k 用 k取代，继续用单 纯形法的表格计算。5.1 目标函数中价值系数cj的变化分析 考虑检验数 j5/26/20245.例5.1:Max Max z z=-2=-2x x1 1-3-3x x2 2-4-4x x3 3 S.t.S.t.-x x1 1-2-2x x2 2-x x3 3+x x4 4 =-3=-3 -2 -2x x1 1+x x2 2-3-3x x3 3+x x5 5=-4=-4 x x1 1,x x2 2,x x3 3,x x4 4,x x5 5 00例题5/26/20246.例：最优单纯形表例：最优单纯形表 从表中看到3=c3+c3-(c2a13+c1a23)可得到c3 9/5 时，原最优解不变。5/26/20247.只要对所有非基变量 j 0，则最优解 不变；否则，将最优单纯形表中的检验数 j 用 j取代，继续单纯形法的表格计算。Maxj/asjasj0csMinj/asjasj0 2、若 cj 是基变量的系数：设 cj 变化为 cj+cj，那么5/26/20248.例5.2:Max Max z z=2=2x x1 1+3+3x x2 2+0+0 x x3 3+0+0 x x4 4+0+0 x x5 5 s.t.s.t.x x1 1+2+2x x2 2+x x3 3 =8=8 4 4x x1 1+x x4 4 =16=16 4 4x x2 2+x x5 5=1212 x x1 1,x x2 2,x x3 3,x x4 4,x x5 5 0 0 举例5/26/20249.下表为最优单纯形表,考虑 基变量系数c2发生变化从表中看到j=cj-(c1a1j+c5 a5j+(c2+c2)a2j)j=3,4可得到-3c21时，原最优解不变。5/26/202410.课本例7例例7 7 在第二章例1中，若家电1的利润不变，则家电2的利润在什么范围内变化时，美佳公司最优生产计划不变？解解 设家电2的利润为(1+)元，反映到最终的单纯形表中如下：5/26/202411.为使表中的解仍为最优，应有解得即家电2的利润变化范围应满足5/26/202412.5.2 资源数量(右端常数br)变化的分析p资 源 数 量 变 化 是 指 资 源 中 某 系 数 br发 生 变 化，即br=br+br。并假设规划问题的其他系数都不变。这样使最终表中原问题的解相应地变化为XB=B-1(b+b)这里b=(0,，br,0,，0)T。只要XB0，因最终表中检验数不变，故最优基不变，但最优解的值发生了变化，所以XB为新的最优解。新的最优解的值可允许变化范围用以下方法确定注：B-1 是最终计算表中的最优基的逆是最终计算表中的最优基的逆5/26/202413.b列的元素变化5/26/202414.b列的元素变化5/26/202415.例5.3:在例5.2中最优单纯形表如下 5/26/202416.0 0.25 0 这里 B B-1=-2 0.5 1 0.5-0.125 0 各列分别对应 b1、b2、b3 的单一变化因此，设 b1 增加 4，则 x1,x5,x2分别变为：4+04=4,4+(-2)4=-40,2+0.54=4用对偶单纯形法进一步求解，可得：x*=(4,3,2,0,0)T f*=175/26/202417.例：求下例（例5.2）中第二个约束条件b2的变化范围5/26/202418.p解：最优单纯形表如下：5/26/202419.可计算b2：由上式，可得b2-4/0.25=-16，b2-4/0.5=-8，b22/0.125=16。所以b2的变化范围是-8，16；显然原b2=16，加它的变化范围后，b2的变化范围是8，32。5/26/202420.若增加一个新变量 xn+1 则有相应的pn+1,cn+1发生变化。那么计算出B B-1pn+1,n+1=cn+1-cri ari n+1 填入最优单纯形表,若 n+1 0 则最优解不变；否则，进一步用单纯形法求解即可。5.3 增加一个变量xj的分析5/26/202421.例例5.4:5.4:若在上例中增加变量x6,p6=(2,6,3)T,c6=5 计算得到用单纯形法进一步求解，可得：x*=(1,1.5,0,0,0,2)T z*=16.55/26/202422.aij的变化使系数矩阵A A中元素发生变化.若变量xj 在最终单纯形表中为非基变量，则与增加变量 xn+1 的情况类似（5.3），假设 pj 变化，那么，重新计算出 B B-1pj和j=cj-cri ari j 填入最优单纯形表，若 j 0 则最 优解不变；否则，进一步用单纯形法求解。（例子从略）5.4 分析参数aij的变化5/26/202423.参数aij的变化若变量xj在最终单纯形表中为基变量，则aij的变化将使相应的B和B-1发生变化，因此有可能出现原问题和对偶问题均为非可行解的情况，这时需要引进人工变量将原问题的解转化为可行解，再用单纯形法求解（例见课本例11）5/26/202424.增加一个约束之后，应把最优解代入新的约束，若满足则最优解不变，否则填入最优单纯形表作为新的一行，引入一个新的非负变量（原约束若是小于等于形式可引入非负松弛变量，否则引入非负人工变量），并通过矩阵行变换把对应基变量的元素变为0，进一步用单纯形法或对偶单纯形法求解。5.5 增加一个约束条件的分析5/26/202425.例5.2增加3x1+2x215，原最优解不满足这个约束。于是经对偶单纯形法一步，可得最优解为（3.5,2.25,0,03,2)T，最优值为 13.755/26/202426.第第8 8节节*参数线性规划参数线性规划p灵敏度分析时，主要讨论在最优基不变情况下，确定系数aij，bi，cj的变化范围。而参数线性规划是研究这些参数中某一参数连续变化时，使最优解发生变化的各临界点的值。即把某一参数作为参变量，而目标函数在某区间内是这个参变量的线性函数，含这个参变量的约束条件是线性等式或不等式。因此仍可用单纯形法和对偶单纯形法分析参数线性规划问题。其步骤是：5/26/202427.参数线性规划的步骤参数线性规划的步骤p(1)对含有某参变量t的参数线性规划问题,先令t=0，用单纯形法求出最优解；p(2)用灵敏度分析法，将参变量t直接反映到最终表中；p(3)当参变量t连续变大或变小时，观察b列和检验数行各数字的变化。若在b列首先出现某负值时，则以它对应的变量为换出变量；于是用对偶单纯形法迭代一步。若在检验数行首先出现某正值时，则将它对应的变量为换入变量；用单纯形法迭代一步；p(4)在经迭代一步后得到的新表上，令参变量t继续变大或变小，重复步骤(3)，直到b列不能再出现负值，检验数行不能再出现正值为止。5/26/202428.8.1 8.1 参数参数c c的变化的变化p例1 试分析以下参数线性规划问题当参数t0时的最优解变化。5/26/202429.解 将此模型化为标准型5/26/202430.令t=0，用单纯形法求解得最终单纯形表如下5/26/202431.将c的变化直接反映到上表中，得如下表：计算t的变化范围5/26/202432.当 t 值变化，在40，即0t9/7时，为最优解(2,6,2,0,0)T；当 t 值增大，t(3/2)/(7/6)=9/7时，在检验数行首先出现40；表示还可以继续改进。t=9/7为第一临界点。当t9/7时，40，这时x4作为换入变量。用单纯形法迭代一步，得下表。5/26/202433.当t继续增大t(5/2)/(1/2)=5时，在检验数行首先出现50，在50，即9/7t5时，得最优解(4,3,0,6,0)T。t=5为第二临界点。当t5时，50，这时x5作为换入变量，用单纯形法迭代一步，得下表。t 继续增大时，在检验数行恒有2，30，故当t5时，最优解为(4，0，0，12，6)T。5/26/202434.8.2 8.2 参数参数b b的变化分析的变化分析例2 分析以下线性规划问题，当t0时，其最优解的变化范围。5/26/202435.解解 将上述模型化为标准型5/26/202436.令t=0，用单纯形法迭代两次，求解的结果见下表:5/26/202437.将此计算结果反映到最终表中可得下表：5/26/202438.在上表中进行分析，当t增大至t2时，则b0；即0t2时，最优解为(2-t.4,0,0)T。当t2时，则b10；故将x1作为换出变量，用对偶单纯形法迭代一步，得下表5/26/202439.结论p从表可见，当t6时，问题无可行解；当2t6时，问题的最优解为 (0，6-t，0，-6+3t)T。5/26/202440.第3章 结束！5/26/202441.