Ling Xueling
第三章 线性规划敏感性分析和计算机解法敏感性分析：
除最优解外,为决策者提供有价值的 额外 信息计算机求解：
解决两个以上变量 L.P,问题
Ling Xueling
第一节 敏感性分析介绍一,概念
1,L.P,一般式
),....,2,1(0
),....,2,1(
..
m a xm a x
1
1
njx
mibxa
ts
xcz
j
n
j
ijij
n
j
jj
Ling Xueling
第一节 敏感性分析介绍一,概念
2,什么是敏感性分析最优后分析 。 就是在 L.P,求出最优解之后,要研究：
1） 当 C j 发生变化时,对最优解 x j 的影响是什么？
2） 当 b i 发生变化时,对最优解 值 z ＝ o.f,的影响是什么？
3,为什么要进行敏感性分析？
1） 现实世界是 动态变化 的,所有系数都会变化,如：市场变化,售价的变化将导致利润率的变化,进而导致目标函数之系数的变化
2） 有些数据是 可控 的,如：是否加班？ 将导致可用工时的变化
3） 不少模型中的数据本来就是估计的,近似 的对修正了的 L.P,模型不再重新求解,也要有足够的信息回答上述变化所带来的影响－－对最优解的影响,即：动态变化或近似估计允许的范围是什么？
Ling Xueling
二,实例－－ Par,公司问题
1,原问题及最优解
Max 10x1 + 9 x2
s.t.
7/10 x1 + x2? 630 最优解
1/2 x1 + 5/6 x2? 600 x1 = 540
x1 + 2/3 x2? 708 x2 = 252
1/10 x1 + 1/4 x2? 135
x1,x2? 0
第一节 敏感性分析介绍凌晨,凌晨,
Ling Xueling
二,实例
2,cj 变化与最优解 xj
1） 若 c1 = 10 变成 7,问：最优解变化吗？
2） 若 c2 在 (5,13) 变化时最优解不变,如何评价 c2 = 9？
3） 若仅当 c2? (8.9,9.25) 时最优解不变,超出这个范围哪怕一点点,最优解就会变,又如何评价 c2 = 9？
3,bi 变化与最优解 值 z
1） bi 变化时,z 如何变化？
2） bi 增加时,附加工时的价值 (z2－ z1) 是什么？
第一节 敏感性分析介绍凌晨,凌晨,
Ling Xueling
一,关于 cj 的变化
1,保优区域的定义使最优解不发生变化,cj 的允许变化区间注意：只保最优解,不保目标函数值 ！
2,Cj 保优区域的几何求法因为 o.f,直线在最优解点处 顺 时针旋转－－ 下 界； 逆 时针旋转
－－ 上 界,得：
故,cj 的保优区域是：
令 c2 = 9 6.3? c1? 13.5
c1 = 10 6.67? c2? 14.29 ( 暂时不讨论 联立 变化 ）
第二节 敏感性分析图解法凌晨,凌晨,
10
7
2
3
2
1
c
c
Ling Xueling
一,关于 cj 的变化
3,特殊情况的讨论令 z = 18 x1 + 9 x2
则最优解是 x1 = 708 x2 = 0
令 c2 = 9 从 得下界 13.5? c1
从 得上界 c1?＋
即得 C 1 保优区域,13.5? C1 < +
第二节 敏感性分析图解法凌晨,凌晨,
2
3
2
1 cc
2
1
c
c?
Ling Xueling
二,关于右手边值 b i （ 资源 ） 的变化要研究,1） 可行域如何变化？
2） 最优解如何变化？
3） 变化值的意义是什么？
1,实例在 Par,公司问题的第一个约束式中令 b1 = 640
则因为可行域增大,最优解变成,x1 = 527.5,x2 = 270.75
o.f,= 7711.75
即：利润增加 7711.75 - 7668 = 43.75 =
也即,4.375 / 工时 （ 对 C&D 工序来说 ） 。
第二节 敏感性分析图解法凌晨,凌晨,
z?
Ling Xueling
二,关于右手边值 b i （ 资源 ） 的变化
2,影子价格的定义约束条件右手边常数每增加一个单位时,目标函数 o.f,所 增加 的数值成为影子价格
3,影子价格的意义
1） 加班费的依据－－ 4.375 是 C&D 车间支付加班费的上限
2） 对外揽活的依据－－若对外加工的报酬在 4.375 之上,可以考虑节约出部分工时搞外加工
3） 注意,（ 1） 有些 bi 变化对 o.f,没有影响,故,任何不是可行域之限界的约束条件的影子价格 ＝ 0,如 S 车间
（ 2） 显然,影子价格仅仅当 bi 变化不大时有效,若 bi
不断变化,则其他约束条件可能变成限界而使 o.f,发生其他的变化 。 问题,使影子价格 有意义 的范围时什么？
第二节 敏感性分析图解法凌晨,凌晨,
Ling Xueling
二,关于右手边值 b i （ 资源 ） 的变化
4,b i 允许变化的区间
1） 对偶价格定义 （ dual price）
b i 每增加一个单位时,o.f,的 改善 值显然,在 max 问题中,dual = shadow
在 min 问题中,dual = － shadow
2） b i 可行区间 （ range of feasibility） 定义使得对偶价格有效的区间称为 b i 的 可行 区间意义：可行,要保证,对偶,有效,即：资源配置的增,减幅度应该控制在有效,可行范围内 ！
问题：如何求 b i 的可行区间？ －－下面一节解决 。
第二节 敏感性分析图解法凌晨,凌晨,
Ling Xueling
一,,MS”软件简介微机 DOS 版本,简单易学二,MS 实例求解 （ Par.公司问题 ）
1,分式还是小数？ （ 保留小数点后 5 位 ）
Max 10x1 + 9 x2
s.t.
0.7 x1 + x2? 630 ( C&D )
0.5 x1 + 0.8333 x2? 600 ( S )
x1 + 0.66667 x2? 708 ( F )
0.1 x1 + 0.25 x2? 135 ( I&P )
x1,x2? 0
第三节 L.P,计算机解法凌晨,凌晨,
Ling Xueling
二,MS 实例求解
2,软件启动进入 A,盘
MS （ 回车 ）
定数据盘：决定,草稿纸,
在,Top Level Menu” 中选,L.P.”
在,L.P,Menu” 中选,Create a New Problem”
注意：
1） 非负约束不要输入
2）,?” 约束只要输入,<”。
第三节 L.P,计算机解法凌晨,凌晨,
Ling Xueling
三,计算机输出信息的解释
Objective Function Value = 7667.99463
Variable Value Reduced Costs
x1 539.99841 0.00000
x2 252.00113 0.00000
Constraint Slack/Surplus Dual Prices
1 0.00000 4.37496
2 120.00000 0.00000
3 0.00000 6.93753
4 17.99988 0.00000
第三节 L.P,计算机解法凌晨,凌晨,
Ling Xueling
Objective Coefficient Ranges
Variable Lower Limit Current Value Upper
x1 6.30000 10.00000 13.49993
x2 6.66670 9.00000 14.28572
Right Hand Side Ranges
Constraint Lower Limit Current Value Upper
1 495.59998 630.00000 682.36316
2 479.99930 600.00000 No Limit
3 580.00146 708.000000 900
4 117.00012 135.00000 No Limit
第三节 L.P,计算机解法凌晨,凌晨,
Ling Xueling
1,最优解和缩减成本 （ reduced costs）
对于每一个决策变量 xj,为使其在最优解中取得正数,其对应的
o.f,之系数 cj 所必须改变的值的大小此例中,x1 = 540 > 0,x2 = 252 > 0,故,对应缩减成本均为 0
2,松弛 /剩余和对偶价格界限约束 slack = 0
非界限约束 slack? 0
因为对偶价格是 改善 值,所以有松弛的约束式对偶价格 ＝ 0
3,敏感性分析
1〕 c j 保优区域 （ Objective Coefficient Ranges） －－使最优解有效的区间,c1 = 10?[6.3,13.5]
2〕 b i 可行区间 （ Right Hand Side Ranges ） －－使对偶价格有效的区间,b1 = 630? [495.6,682.4]
第三节 L.P,计算机解法凌晨,凌晨,
Ling Xueling
4,关于联立变化
1〕 计算机输出的结果中,没有讨论联立变化,是独立变化 ！
2〕 讨论联立变化的 100％ 法则若所有变化的百分比之和不超过 100％,称此联立变化满足 100％ 法则,此时,对偶价格依然保持有效设 Par,公司问题中第一,三约束同时发生变化 b1 = 630 650
b3 = 708 808
则,因为 b1 / b3 的可行区间分别是 （ 495.6,682.4) / (708,900)
按照公式得联立变化百分比是：
故,b1 / b3 的对偶价格仍然皆有效 。
第三节 L.P,计算机解法凌晨,凌晨,
原始值最大允许量－
ii
i
bb
b
%100%27.90708900 1006304.682 20
Ling Xueling
销售双工无线电联络系统问题
1,目标：利润最大
2,条件和约束四种渠道：专业批发商 / 一般批发商 / 零售 / 邮购不同渠道时：不同利润 / 不同广告成本 / 不同售后服务时间资源和有关数据：
单位广告预算 10,8,9,15,可用总量,5000
单位服务时间 2,3,3,0,总可用时间,1800
已安排生产 600
第三渠道已签约 150
利润率 90 / 84 / 70 / 60 （ 课堂练习建立模型 ） 。
两个以上决策变量的 L.P,问题例子凌晨,凌晨,
Ling Xueling
数学模型
max z = max 90x1 + 84x2 + 70x3 + 60x4
s.t.
10x1 + 8x2 + 9x3 + 15x4? 5000
2x1 + 3x2 + 3x3? 1800
x1 + x2 + x3 + x4 = 600
x3? 150
x1,x2,x3,x4? 0
两个以上决策变量的 L.P,问题例子凌晨,凌晨,
Ling Xueling
计算机输出结果的部分解释：
X4 之 reduced cost = 45:
除非单位利润再增加 45,达 60+45=105,否则无法利用邮购渠道进行销售第四约束 （ 已签约 150单位 ） dual price = - 17:
每增加 1 单位签约量,会使利润下降 17 单位每减少 1 单位签约量,会使利润上升 17 单位 。
两个以上决策变量的 L.P,问题例子凌晨,凌晨,
Ling Xueling
The End of Chapter 3
第三章 线性规划敏感性分析和计算机解法敏感性分析：
除最优解外,为决策者提供有价值的 额外 信息计算机求解：
解决两个以上变量 L.P,问题
Ling Xueling
第一节 敏感性分析介绍一,概念
1,L.P,一般式
),....,2,1(0
),....,2,1(
..
m a xm a x
1
1
njx
mibxa
ts
xcz
j
n
j
ijij
n
j
jj
Ling Xueling
第一节 敏感性分析介绍一,概念
2,什么是敏感性分析最优后分析 。 就是在 L.P,求出最优解之后,要研究：
1） 当 C j 发生变化时,对最优解 x j 的影响是什么？
2） 当 b i 发生变化时,对最优解 值 z ＝ o.f,的影响是什么？
3,为什么要进行敏感性分析？
1） 现实世界是 动态变化 的,所有系数都会变化,如：市场变化,售价的变化将导致利润率的变化,进而导致目标函数之系数的变化
2） 有些数据是 可控 的,如：是否加班？ 将导致可用工时的变化
3） 不少模型中的数据本来就是估计的,近似 的对修正了的 L.P,模型不再重新求解,也要有足够的信息回答上述变化所带来的影响－－对最优解的影响,即：动态变化或近似估计允许的范围是什么？
Ling Xueling
二,实例－－ Par,公司问题
1,原问题及最优解
Max 10x1 + 9 x2
s.t.
7/10 x1 + x2? 630 最优解
1/2 x1 + 5/6 x2? 600 x1 = 540
x1 + 2/3 x2? 708 x2 = 252
1/10 x1 + 1/4 x2? 135
x1,x2? 0
第一节 敏感性分析介绍凌晨,凌晨,
Ling Xueling
二,实例
2,cj 变化与最优解 xj
1） 若 c1 = 10 变成 7,问：最优解变化吗？
2） 若 c2 在 (5,13) 变化时最优解不变,如何评价 c2 = 9？
3） 若仅当 c2? (8.9,9.25) 时最优解不变,超出这个范围哪怕一点点,最优解就会变,又如何评价 c2 = 9？
3,bi 变化与最优解 值 z
1） bi 变化时,z 如何变化？
2） bi 增加时,附加工时的价值 (z2－ z1) 是什么？
第一节 敏感性分析介绍凌晨,凌晨,
Ling Xueling
一,关于 cj 的变化
1,保优区域的定义使最优解不发生变化,cj 的允许变化区间注意：只保最优解,不保目标函数值 ！
2,Cj 保优区域的几何求法因为 o.f,直线在最优解点处 顺 时针旋转－－ 下 界； 逆 时针旋转
－－ 上 界,得：
故,cj 的保优区域是：
令 c2 = 9 6.3? c1? 13.5
c1 = 10 6.67? c2? 14.29 ( 暂时不讨论 联立 变化 ）
第二节 敏感性分析图解法凌晨,凌晨,
10
7
2
3
2
1
c
c
Ling Xueling
一,关于 cj 的变化
3,特殊情况的讨论令 z = 18 x1 + 9 x2
则最优解是 x1 = 708 x2 = 0
令 c2 = 9 从 得下界 13.5? c1
从 得上界 c1?＋
即得 C 1 保优区域,13.5? C1 < +
第二节 敏感性分析图解法凌晨,凌晨,
2
3
2
1 cc
2
1
c
c?
Ling Xueling
二,关于右手边值 b i （ 资源 ） 的变化要研究,1） 可行域如何变化？
2） 最优解如何变化？
3） 变化值的意义是什么？
1,实例在 Par,公司问题的第一个约束式中令 b1 = 640
则因为可行域增大,最优解变成,x1 = 527.5,x2 = 270.75
o.f,= 7711.75
即：利润增加 7711.75 - 7668 = 43.75 =
也即,4.375 / 工时 （ 对 C&D 工序来说 ） 。
第二节 敏感性分析图解法凌晨,凌晨,
z?
Ling Xueling
二,关于右手边值 b i （ 资源 ） 的变化
2,影子价格的定义约束条件右手边常数每增加一个单位时,目标函数 o.f,所 增加 的数值成为影子价格
3,影子价格的意义
1） 加班费的依据－－ 4.375 是 C&D 车间支付加班费的上限
2） 对外揽活的依据－－若对外加工的报酬在 4.375 之上,可以考虑节约出部分工时搞外加工
3） 注意,（ 1） 有些 bi 变化对 o.f,没有影响,故,任何不是可行域之限界的约束条件的影子价格 ＝ 0,如 S 车间
（ 2） 显然,影子价格仅仅当 bi 变化不大时有效,若 bi
不断变化,则其他约束条件可能变成限界而使 o.f,发生其他的变化 。 问题,使影子价格 有意义 的范围时什么？
第二节 敏感性分析图解法凌晨,凌晨,
Ling Xueling
二,关于右手边值 b i （ 资源 ） 的变化
4,b i 允许变化的区间
1） 对偶价格定义 （ dual price）
b i 每增加一个单位时,o.f,的 改善 值显然,在 max 问题中,dual = shadow
在 min 问题中,dual = － shadow
2） b i 可行区间 （ range of feasibility） 定义使得对偶价格有效的区间称为 b i 的 可行 区间意义：可行,要保证,对偶,有效,即：资源配置的增,减幅度应该控制在有效,可行范围内 ！
问题：如何求 b i 的可行区间？ －－下面一节解决 。
第二节 敏感性分析图解法凌晨,凌晨,
Ling Xueling
一,,MS”软件简介微机 DOS 版本,简单易学二,MS 实例求解 （ Par.公司问题 ）
1,分式还是小数？ （ 保留小数点后 5 位 ）
Max 10x1 + 9 x2
s.t.
0.7 x1 + x2? 630 ( C&D )
0.5 x1 + 0.8333 x2? 600 ( S )
x1 + 0.66667 x2? 708 ( F )
0.1 x1 + 0.25 x2? 135 ( I&P )
x1,x2? 0
第三节 L.P,计算机解法凌晨,凌晨,
Ling Xueling
二,MS 实例求解
2,软件启动进入 A,盘
MS （ 回车 ）
定数据盘：决定,草稿纸,
在,Top Level Menu” 中选,L.P.”
在,L.P,Menu” 中选,Create a New Problem”
注意：
1） 非负约束不要输入
2）,?” 约束只要输入,<”。
第三节 L.P,计算机解法凌晨,凌晨,
Ling Xueling
三,计算机输出信息的解释
Objective Function Value = 7667.99463
Variable Value Reduced Costs
x1 539.99841 0.00000
x2 252.00113 0.00000
Constraint Slack/Surplus Dual Prices
1 0.00000 4.37496
2 120.00000 0.00000
3 0.00000 6.93753
4 17.99988 0.00000
第三节 L.P,计算机解法凌晨,凌晨,
Ling Xueling
Objective Coefficient Ranges
Variable Lower Limit Current Value Upper
x1 6.30000 10.00000 13.49993
x2 6.66670 9.00000 14.28572
Right Hand Side Ranges
Constraint Lower Limit Current Value Upper
1 495.59998 630.00000 682.36316
2 479.99930 600.00000 No Limit
3 580.00146 708.000000 900
4 117.00012 135.00000 No Limit
第三节 L.P,计算机解法凌晨,凌晨,
Ling Xueling
1,最优解和缩减成本 （ reduced costs）
对于每一个决策变量 xj,为使其在最优解中取得正数,其对应的
o.f,之系数 cj 所必须改变的值的大小此例中,x1 = 540 > 0,x2 = 252 > 0,故,对应缩减成本均为 0
2,松弛 /剩余和对偶价格界限约束 slack = 0
非界限约束 slack? 0
因为对偶价格是 改善 值,所以有松弛的约束式对偶价格 ＝ 0
3,敏感性分析
1〕 c j 保优区域 （ Objective Coefficient Ranges） －－使最优解有效的区间,c1 = 10?[6.3,13.5]
2〕 b i 可行区间 （ Right Hand Side Ranges ） －－使对偶价格有效的区间,b1 = 630? [495.6,682.4]
第三节 L.P,计算机解法凌晨,凌晨,
Ling Xueling
4,关于联立变化
1〕 计算机输出的结果中,没有讨论联立变化,是独立变化 ！
2〕 讨论联立变化的 100％ 法则若所有变化的百分比之和不超过 100％,称此联立变化满足 100％ 法则,此时,对偶价格依然保持有效设 Par,公司问题中第一,三约束同时发生变化 b1 = 630 650
b3 = 708 808
则,因为 b1 / b3 的可行区间分别是 （ 495.6,682.4) / (708,900)
按照公式得联立变化百分比是：
故,b1 / b3 的对偶价格仍然皆有效 。
第三节 L.P,计算机解法凌晨,凌晨,
原始值最大允许量－
ii
i
bb
b
%100%27.90708900 1006304.682 20
Ling Xueling
销售双工无线电联络系统问题
1,目标：利润最大
2,条件和约束四种渠道：专业批发商 / 一般批发商 / 零售 / 邮购不同渠道时：不同利润 / 不同广告成本 / 不同售后服务时间资源和有关数据：
单位广告预算 10,8,9,15,可用总量,5000
单位服务时间 2,3,3,0,总可用时间,1800
已安排生产 600
第三渠道已签约 150
利润率 90 / 84 / 70 / 60 （ 课堂练习建立模型 ） 。
两个以上决策变量的 L.P,问题例子凌晨,凌晨,
Ling Xueling
数学模型
max z = max 90x1 + 84x2 + 70x3 + 60x4
s.t.
10x1 + 8x2 + 9x3 + 15x4? 5000
2x1 + 3x2 + 3x3? 1800
x1 + x2 + x3 + x4 = 600
x3? 150
x1,x2,x3,x4? 0
两个以上决策变量的 L.P,问题例子凌晨,凌晨,
Ling Xueling
计算机输出结果的部分解释：
X4 之 reduced cost = 45:
除非单位利润再增加 45,达 60+45=105,否则无法利用邮购渠道进行销售第四约束 （ 已签约 150单位 ） dual price = - 17:
每增加 1 单位签约量,会使利润下降 17 单位每减少 1 单位签约量,会使利润上升 17 单位 。
两个以上决策变量的 L.P,问题例子凌晨,凌晨,
Ling Xueling
The End of Chapter 3
