运筹学 第3版 课件 04 线性规划灵敏度分析

第4章线性规划灵敏度分析问题提出前面假定cj，aij，bi是常数，实际上，cj（市场价格决定），aij（工艺条件决定），bi（根据经济效果决定，市场与影子价格），这些变量都会随着市场、工艺等条件的改变而改变。1、当这些参数一个或几个发生变化时，问题的最优解或最优基如何变化；

2、参数在什么范围内变化时，问题的最优解或最优基不变。

针对以上现象讨论两个问题:

重新求解？CBCN0b表头CBXBXNXSBNIb初始表…………CBIB-1NB-1B-1b最优表CB-CBICN-CBB-1N0-CBB-1CBB-1b检验数求解思路问题提出（2/2）2、b变化影响1、C（CBCN）变化影响3、A（BN）变化影响最优解和目标函数值检验数行N

变化：主要影响非基变量检验数和系数列向量B变化：系数矩阵、检验数和目标函数、最优解主要内容§4-2资源数量变化的分析（右端常数项bi的变化）§4-3技术系数aij的变化§4-1目标函数系数的变化（

cj

的变化）§4-1目标函数系数的变化cj的变化对检验数有影响，进而影响解的最优性。cj对应的变量又分为基变量、非基变量，两者变化会对σj产生不同的影响。一、ck为非基变量xk的价值系数

二、cr为基变量xr的价值系数

2-11000CBXBbx1x2x3x4x5x6-1x2240151300x670020112x12110412000-2-1-10问题：x3的价值系数c3在什么范围变化，使得最优解不变？分析：x3非基变量c3减少：

3减少，负c3增加：

3增加，负、0、正Δc32即：c3

1+2一、ck为非基变量xk的价值系数（1/2）例4－1当非基变量xk对应的ck变为

时，

（不同于xk的另外任一变量xj对应的检验数

不会发生变化。）

当时，最优解不变，即:当ck为非基变量xk的价值系数时，最优解不变的Δck的变化范围为此时最优解、最优值不变。

一、ck为非基变量xk的价值系数（2/2）c2的变化范围为：

－2－0.5×Δc2

≤0－0.25+0.125×Δc2≤0得：得：Δc2的变化范围

34000CBXBbx1x2x3x4x53x141000.2500x5400-20.514x22010.5-0.125020000－0.5×Δc2+0.125×Δc2例4－2生产计划问题：产品乙收益的变化范围

甲乙资源约束原材料128设备A4016设备B0412获利34二、cr为基变量xr的价值系数（1/2）-2-0.25当基变量xr对应的cr变为

任意非基变量xj有

若最优解不变，则所有

二、cr为基变量xr的价值系数（2/2）任意变量xj的检验数:

（j=1，2，…，n）

负数正数

（3）Δcr的变化范围由检验数行与xr所在行的系数来确定

（1）小结34000x1x2x3x4x5341000.2500400-20.5142010.5-0.12502000-2-0.250

Δck（对应非基变量）的变化范围：Δcr（对应基变量）的变化范围：§4-2约束右端常数项的变化一、br发生变化，最优解改变最优基不变（影子价格不变）最优基改变（影子价格改变）二、最优基不变（影子价格不变），Δbr允许变化的范围一、br发生变化，最优解改变设第r种资源br发生变化△

br，则

设备A增加2，即

所以，最优基不变，最优解为

cj34000CBXBbx1x2x3x4x53x141000.2500x5400-20.514x22010.5-0.125000-2-0.250影子价格不变cj34000CBXBbx1x2x3x4x53x14.51000.2500x5500-20.514x21.75010.5-0.125000-2-0.250一、br发生变化——最优基不变例4-3生产计划问题，用到原材料、设备A、设备B三项资源例4－4生产计划问题增加4单位原材料，即

因为

，最优解变为非可行解，所以用对偶单纯形法迭代，

过程如下

cj34000CBXBbx1x2x3x4x53x14

1000.2500x5400-20.514x22

010.5-0.125000-2-0.250x1x3x2＋0－8＋2[-2]1002-0.25-0.503400140.250010300.25000-0.75-124最优基：最优解：最优值：影子价格改变！！！原材料设备A设备B一、br发生变化——最优基改变∴

的变化范围为：

b2的变化范围为：即：

二、最优基不变，Δbr允许变化的范围（1/4）cj34000CBXBbx1x2x3x4x53x141000.2500x5400-20.514x22010.5-0.125000-2-0.250例4－5求生产计划问题

的变化范围

,所以

时，

时，

则Δbr的变化范围为：

负中取大≤≤正中取小

负数正数最终表中松弛变量对应的系数矩阵最终表中的b列最终表中第r个松弛变量对应的系数列向量，即

，仍设第r种资源发生Δbr的变化，则

二、最优基不变，Δbr允许变化的范围（2/4）由以上分析可知，最优基不变则必有

二、最优基不变，Δbr允许变化的范围（3/4）34000341000.2500400-20.5142010.5-0.125000-2-0.250△br的变化范围：负中取大≤≤正中取小

（3）△br的范围是由b列与第r个松弛变量对应的系数列向量来确定的。

（1）（2）说明：1、上述公式只能判断一个br发生变化的情况，当多个br同时发生变化时，不适用。2、注意区分br的变化范围与Δbr的变化范围。3、b的变化肯定会引起最优解的变化，但最优基（影子价格）是否改变要应用上述公式判断。4、Δbr的变化范围也确定第r种原材料买入或卖出的范围（以例4-4为例说明），一旦超出该范围影子价格就会发生变化。二、最优基不变，Δbr允许变化的范围（4/4）§4-3技术系数A

的变化二、结构改进（列向量发生变化）三、增加新产品四、增加约束条件

五、改变约束条件

一、A中某个元素的变化列的变化行的变化例4－6cj2-11000CBXBbx1x2x3x4x5x6-1x2240151300x670020112x12110412000-2-1-10一、A中某个元素的变化（1/2）求解x3的技术系数a13不影响最优解的变化范围。非基变量 此处讨论的是：非基变量xj的系数列向量pj的某个分量aij发生变化。※非基变量的系数aij的变化仅影响该非基变量的检验数。

假设非基变量的系数

aij

’＝aij＋Δ

aij∴Δaij向小的方向变化有一个下限，向大的方向变化不会影响当前最优解。∵σj＜0非基变量一、A中某个元素的变化（2/2）二、结构改进（列向量发生变化）（1/11）—非基变量例4－7

cj2-11000CBXBbx1x2x3x4x5x6-1x2240151300x670020112x12110412000-2-1-101、非基变量的系数列向量Pk

计算检验数

则最优解不变；

（1）若，（2）若，则将和代入单纯形表，用单纯形法继续迭代。

二、结构改进（列向量发生变化）（2/11）—非基变量

二、结构改进（列向量发生变化）（3/11）—非基变量

2-11000CBXBbx1x2x3x4x5x6-1x2240151300x670020112x12110412000-2-1-101221-1x21701012-11x37/200101/21/22x135/210013/2-1/2000-1-3/2-1/2利用单纯形法继续迭代求优2-11000CBXBbx1x2x3x4x5x6例4－8

生产计划问题

分析以上两种情况对原最优解会有什么影响？

二、结构改进（列向量发生变化）（4/11）—基变量

cj34000CBXBbx1x2x3x4x53x141000.2500x5400-20.514x22010.5-0.125000-2-0.2502、基变量的系数列向量

Pk①迭代后直接得到最优解；

②迭代后原问题和对偶问题均为非可行解；

③迭代后原问题为非可行解（对偶单纯形法）；对偶问题为非可行解（单纯形法）。

（2）迭代，使xk的系数列向量迭代恢复为单位列向量，再根据恢复后的状态处理

（1）将和代入最终表，最终表中xk的系数列向量不再是单位列向量；

二、结构改进（列向量发生变化）（5/11）—基变量

例4－8生产计划问题

产品甲的工艺改为

解：分析对原最优解会有什么影响？

①迭代后直接得到最优解

二、结构改进（列向量发生变化）（6/11）—基变量

cj34000CBXBbx1x2x3x4x53x141000.2500x5400-20.514x22010.5-0.125000-2-0.25030434000341000.2500400-20.5142010.5-0.125000-2-0.2500.5-10.250.581000.501200-2110010.5-0.25000-2-0.5024迭代，使x1的系数列向量迭代恢复为单位列向量，再根据恢复后的状态处理单纯形表迭代后直接得到最优解二、结构改进（列向量发生变化）（7/11）—基变量

34000②迭代后原问题和对偶问题均为非可行解

例4－8生产计划问题：产品甲的工艺改为

二、结构改进（列向量发生变化）（8/11）—基变量

cj34000CBXBbx1x2x3x4x53x141000.2500x5400-20.514x22010.5-0.125000-2-0.2501-41.5-6cj34000CBXBbx1x2x3x4x53x141000.2500x52000-21.514x2-4010.5-0.5000-21.250引入人工变量（i）x2所在行同乘-1（ii）引入人工变量x6用单纯形法继续迭代求解迭代，原问题和对偶问题均为非可行解。cj34000CBXBbx1x2x3x4x53x141000.2500x52000-21.514x2-4010.5-0.5000-21.25000104-M-0.5M-0.75+0.5M0040-1-0.50.50-M-M二、结构改进（列向量发生变化）（9/11）—基变量

最优解：二、结构改进（列向量发生变化）（10/11）—基变量

cj34000-MCBXBbx1x2x3x4x5x63x141000.25000x52000-21.510-Mx640-1-0.50.50104-M-0.5M-0.75+0.5M003x1210.50.2500-0.50x5803-0.501-30x480-2-110202.5-200-M+1.53x12/3101/30-1/604x28/301-1/601/3-10x416/300-4/312/3000-1/30-5/6-M+4③迭代后原问题为非可行解：用对偶单纯形法迭代

迭代后对偶问题为非可行解：用单纯形法迭代

二、结构改进（列向量发生变化）（11/11）—基变量

新产品的相关数据是P新、c新和σ新判断是否生产该产品：

例4－9生产计划问题计划生产新产品丙

若σ新≥0，则生产该产品，问：①是否应该生产该产品；②生产多少？

代入最终表，用单纯形法迭代，求得生产量。

和同时将

若σ新<

0，则不生产该产品。三、增加新产品（增加一列）（1/2）cj34000CBXBbx1x2x3x4x53x141000.2500x5400-20.514x22010.5-0.125000-2-0.250例4－9生产计划问题：计划生产新产品丙解：①用

表示产量

，说明生产该新产品利润增加。

问：①是否应该生产该产品；②生产多少？

代入最终表，用单纯形法迭代，得

将

和②

所以应该生产III三、增加新产品（增加一列）（2/2）其最终表见右表，增加一个约束条件

，问如何变化？

cj21000CBXBbx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2000-1/4-1/2经过以下两步判断

（1）将原问题最优解代入该约束条件，满足，最优解不变。否则，进入（2）

（2）将新增约束条件加入一个松弛变量代入单纯形表，迭代求解。将最终表中的解代入该约束为

不满足该约束，所以最优解变化

四、增加约束条件（增加一行）（1/2）例4－10已知

cj21000CBXBbx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2000-1/4-1/200x315/20015/4-15/202x17/21001/4-1/201x23/2010-1/43/200x6000-1/4-1/200x315/20015/4-15/202x17/21001/4-1/201x23/2010-1/43/200x6000-1/4-1/2001232000100003/220-3/43/210-3/200-1/4-3/210然后用对偶单纯形法继续迭代求解。求解过程，略基变量变换为单位向量四、增加约束条件（增加一行）（2/2）

cj2-11000CBXBbx1x2x3x4x5x6-1x2240151300x670020112x12110112000-2-1-10按列分析：