运筹学 线性规划灵敏度分析

第二章 线性规划灵敏度分析 线性规划灵敏度分析4课时 课时

在实际问题中，规划模型中的大多数数 在实际问题中， 据是测量、统计、评估或决策而得出来的。 据是测量、统计、评估或决策而得出来的。 因此有必要分析当这些数据发生波动时会对 最优解和最优值产生什么影响。这就是灵敏 最优解和最优值产生什么影响。 度分析。 度分析。

§2.1 价值系数 cj 的变化分析 一般市场条件一变， j 值就会发生变化， c 下面我们将分 析 cj 的变化会导致最优单纯形表怎样变化？max z = c Τ x

设标准 LP 问题

Ax = b 的最优单纯形表为 s.t. x ≥ 0xB xNB 1 N- cB B N + c NT T 1

xBZ

B 1b- cB B bT 1

I O

运筹学xBZ

xB

xN

线性规划

B 1b- cB B bT 1

I O

B 1 N- cB B N + c NT T 1

从上表可看出 cj 的变化会只导致 σ N 和 z 的变化。若仍有 T T T T σ N = cB B 1 N cN ≤ 0, zmin = cB B 1b , x = ( B 1b, O)T ≥ 0 时,它还是最优单纯形 表. 当 c 改变为 c* = c + c 时* T T T T T T T σ NT = ( cB + cB ) B 1 N + ( cN + cN ) = σ N + ( cB B 1 N + cN ), * 若 σ NT ≤ O , 则 x = ( B 1b, O)T ≥ 0 仍是最优解，最优值变为

T T T T zmin = (cB + cB ) B 1b = cB B 1b + cB B 1b

否则把以 c*代入要按单纯形法断续迭代。

运筹学

线性规划

* 1. 如果只有一个非基变量的系数 ck = ck + ck ,则只有 σ k 变化为

T * T * σ k* = cB Ak ck = cB Ak ck + ( ck ck ) = σ k + ck

所以当 σ k* ≤ 0 ck ≤ σ k 时，最优表还是最优表，否则把以 ck* 代入要按单纯形法断续迭代。* 2. 如果只有一个基变量的系数 ck = ck + ck ,则只有 σ k 变化为

T * T * σ k* = cB Ak ck = cB Ak ck + (ck ck ) = σ k + ck = 0 + ck = ck

需把第 r 行乘 ck 去减第 0 行得新单 若基变量 xk 对应第 r 行， 纯形表。

运筹学max Z = 300 x1 + 500 x2 x1 ≤ 4 2 x ≤ 12 2 s.t. 3 x1 + 2 x2 ≤ 18 x1 , x2 ≥ 0

线性规划

例 在例 1.1 中工厂生产门窗两种产品的最优计划问题归结为下列线 性规划

已知最优单纯形表如下

300xB

500

0

0

0

b’ 2 6 2

x10 0 1

x20 1 0 0

x31 0 0 0

x41/3 1/2 -1/3 -150

x5-1/3 0 1/3 -100

θ

x3 x2 x1

-3600 0

(1)确定门的利润 c 由 300 元变为 500 元时，最大利润如何变化？ 1 (2)若门窗的利润 c ,c 都发生了变化，最大利润如何变化？(求二种产品的价格 1 2 波动范围使原最优解保持最优)

运筹学

线性规划

解 ： 设 c1 的 增 量 是 c1 = 200 , 因 为 x1 是 基 变 量 ， 只 有 σ 1 发 生 变 化σ 1* = σ 1 + c1 = 0 + c1 = c1 ,代入上表得

不是最优表，继续迭代， 得，最优解 X*=(2,6,2, x 3 0,0)保持不变。最优

值 变为 4000。x3

300

500

0

0

0

xB x2 x1

b’ 2 6 2 -3600 2 6 2

x10 0 1 200 0 0 1

x20 1 0 0 0 1 0 0

x31 0 0 0 1 0 0 0

x41/3 1/2 -1/3 -150 1/3 1/2 -1/3 -250/3

x5-1/3 0 1/3 -100 -1/3 0 1/3 -100/3

θ

x2 x1

-4000 0

运筹学设 c1 , c2 的增量为 c1 , c2 * T T T T T σ NT = σ N ( cB B 1 N cN ) = σ N cB B 1 N

线性规划

1 1 / 3 1 / 3 c c c = (0, 150, 100) (0, c2 , c1 ) 0 1 / 2 0 = (0, 150 2 + 1 , 100 1 2 3 3 0 1 / 3 1 / 3

若在单纯形表上做则是300 500 0 0 0

xBx3 x2 x1

b’ 2 6 2 -3600-3600- 2 c1 - 6 c2

x10 0 1

x20 1 0

x31 0 0 00

x41/3 1/2 -1/3 -150 150 + c1 c2 3 2

x5-1/3 0 1/3 -100 100 c1 3

θ

c10

c 20

所以 150 +

c1 c2 ≤ 0, 3 2 c 100 1 ≤ 0 3

时，即 300 ≤ c1 ≤ 4500 时最优生产方案不变。 300 ≤ c2

但最优值会发生变化。 这些我们可用 Excel 规划求解帮我们做。

注：这里是分别市场上二种得到的结论，若考虑产品价格同时变化，则要求为 900 + 2 c1 ≤ c2, 若 c = 150时， 则 200 ≤ c , 若 c = 150时， 则 600 ≤ c , 1 2 1 2 3 300 ≤ c1

在用规划求解时，我们选择敏感性报告并保存得敏感性报告表如下

11. Microsoft Excel 11.0 敏感性报告 xls]Sheet1 工作表 [例1.1.xls]Sheet1 报告的建立: 2011-9-28 10:10:53 报告的建立: 201110: 10:

可变单元格 单元格 名字 $B$4 可变单元格→ Max Z=∑cjxj $C$4 可变单元格→ 约束 单元格 名字 $D$7 a1j→ ∑aijxj $D$8 a2j→ ∑aijxj $D$9 a3j→ ∑aijxj 终 阴影 约束 允许的 允许的 值 价格 限制值 增量 减量 2 0 4 1E+30 2 12 150 12 6 6 18 100 18 6 6 终 递减 目标式 允许的 允许的 值 成本 系数 增量 减量 2 0 300 450 300 6 0 500 1E+30 300

价值系数cj的变 价值系数 的变 化的灵敏度分析

右端常数bi的变化 右端常数 的变化 的灵敏度分析

即敏感性报告给出的是分别变化的灵敏度分析。 敏感性报告给出的是分别变化的灵敏度分析。

运用敏感性报告给出的产品价值同时变化的灵敏度分析敏感性报告中给出的只是单个产品价值变化的灵敏度分析,对同时变化有 敏感性报告中给出的只是单个产品价值变化的灵敏度分析 对同时变化有 如下一种间单的分析方法: 如下一种间单的分析方法

百分之百法则——若目标函数系数同时变动，则当它们相 对其允许增量或允许减量的相对变化率之和不超过百分之 百(100%)时，最优解不变，则当它们相对其允许增量或 允许减量的相对变化率之和超过百分之百(100%)时，不 能确定最优解是否改变。 运用见P35也可利用软件做交叉变化分析来取代. 也可利用软件做交

叉变化分析来取代.

运筹学 §2.2 右端常数 bi 的灵敏度变化分析 灵敏度变化分析

线性规划

标准 LP 问题的最优单纯形表中还可看出，当右端常数向量 b 改变为 b* = b + b 时，只有表的最后一列会发生变化，故只需修改最 后一列即可。修改的方法如下： , b * = B 1b* = B 1 (b + b) = b + B 1 b* T T T z0 = cT b * = cB B 1b* = cB B 1 (b + b) = z0 + cB B 1 b B * T 若 b * ≥ O ,则 x = ( B 1b* , O)T 是最优解，最优值为 z0 = cT b * = z0 + cB B 1 b , B 否则用对偶单纯形法断续求解。 对于上例作下列分析： 例：对于上例作下列分析： (3)车间 2 可用工时 b2 增加 1 小时，总利润如何变化，最优解是

否发生变化？ (4)若同时改变三个车间的可用工时，总利润如何变化，最优解是 否发生变化？ 解：总利润和最优解都与 b 有关都会发生变化，一般我们关心最优 基是否会变，即生产的品种是否会变。

运筹学 2 1 1/ 3 1 / 3 0 b * = b + B 1 b = 6 + 0 1 / 2 0 1 2 0 1/ 3 1 / 3 0 设 b2 的增量是 b2 = 1 , , 2 1 / 3 7 / 3 = 6 + 1 / 2 = 13 / 2 ≥ 0 2 1 / …… 此处隐藏：4286字，全部文档内容请下载后查看。喜欢就下载吧 ……