当前位置:
文档之家› 教育第五章 线性规划问题的灵敏度分析
教育第五章 线性规划问题的灵敏度分析
(1)非基变量对应的价值系数的灵敏度分析
要保持 (cj cj)zj 0 故有cj (cj zj)
6
例5.1
153 4
CB XB b
x1 x2 x3 x4
0 x5 100 1/4 0 -13/4 0 4 x4 200 2 0 -2 1
5 x2 100 -3/4 1 11/4 0
1300 4.25 5 5.75 4
最优解/最优值的变化情况; (2)分析线性规划相关参数和条件在什么范围内变化,其最优
基/最优解/最优值不变。
灵敏度分析内容: (1)参数 Cj,bi,aij的影响分析; (2) 增加约束或变量的影响分析;
3
5.2 灵敏度分析工具与原理
(1)灵敏度分析工具
Pj’ =B-1Pj
b’=B-1b
σj =Cj-CBB-1Pj=Cj-CBPj’
设x4的价值系数增加c4,对应k=2(第二行)
ma x32.25 ,01.25c4mi n 2.2 75 , 1 1 0.25 c41, 3.75 c45
• 有一边为空集如何处理
• 为什么akj=0不出现在任何一边的集合中
• 与对偶单纯型法找入变量的公式一样
9
例2:maxf (x) (21)x1 (32)x2
cj-zj -3.25 0 -2.75 0
00 0 x5 x6 x7 1 1/4 -1 0 1 -1 0 -3/4 1 0 0.25 1 0 -0.25 -1
x1,x3为非基变量 所以 c1 3.25, c1 4.25
c3 2.75, c3 5.75
7
(2)基变量对应的价值系数的灵敏度分析
• 由于基变量对应的价值系数在CB不中考出虑现,ark因=0此的它情会况影,响因所为当
5
5.3 价值系数 cj 的灵敏度分析
• cj 变动可能由于市场价格的波动,或生产成本的变动 • cj 的灵敏度分析是在保证最优基变量不变的情况下,分析cj
允许的变动范围cj • cj 的变化会引起检验数的变化,有两种情况
– 非基变量对应的价值系数变化,不影响其它检验数 – 基变量对应的价值系数变化,影响所有非基变量检验数
0 x5 100 1/4 0 -13/4 0
4 x4 200 2 0 -2 1
5 x2 100 -3/4 1 11/4 0
1300 4.25 5 5.75 4
cj-zj -3.25 0 -2.75 0
00 0 x5 x6 x7 1 1/4 -1 0 1 -1 0 -3/4 1 0 0.25 1 0 -0.25 -1
2x1 3x2 12
s.t.
4x1
16 5x2 15
x1, x2 0
试求价值系数变化范围为多少时原问题最优解不变
10
上例题的最优单纯形表为:
2 3 0 00 CB XB b x1 x2 x3 x4 x5 2 X1 3 1 0 1/2 0 -1/5 0 x4 4 0 0 -1/2 1 4/5 3 x2 3 0 1 0 0 1/5 OBJ=15 cj-zj 0 0 -1 0 -1/5
原问题 对偶问题 可行 可行
结论或继续计算的步骤 仍为最优解
可行 不可行
迭代求出最优(单纯形法)
不可行 可行
迭代求出最优(对偶单纯形法)
不可行 不可行 引入人工变量,编制新单纯形表进行求1解2
• 设XB=B1b是最优解,则有XB=B1b0 • b的变化不会影响检验数
• b的变化量b可能导致原最优解变为非可行解
a' 1, n 1
a' 1, n i
a' 1,n m
设
B 1
a' k ,n1
a' k ,ni
a' k ,nm
a
'
mLeabharlann ,n1a' m,ni
a' m,nm
b b1, b2 , , (bk bk ), bm T
为保证最优解的基变量 不发生变化 , 必须满足
XB B 1b b 0
有非基变量的检验数
ark=0时,cj的变化不影响zk,
• 只有一个基变量的 cj 发生变化,同变时化因量为基 c变j 量检验数始终
• 令 cj 在CB中的第k行,研究非基变为量0,xj 机不会考成虑本其的变变化化。
m
m
zj zj (ci ci)aij ciaij ciakj
i1
i1
要满足cj (zj zj ) 0, 则有cj zj akjck
max1/12c1 min11//55 2c1 1, 0c1 3
max
1/ 5 1/ 5
c2
1 c2, 2 c2
11
5.4 右端项 bi 的灵敏度分析
约束条件右端项bi的变化在实际问题中反映为可用资源数量的变 化。由对偶单纯形法可看出b变化反映到最终单纯形表上将引起右 边系数列数字的变化,结论可能出现第一或第三的两种情况。出现第 一种情况时,问题的最优基不变,变化后的b列值为最优解。出现 第三种情况时,用对偶单纯形法迭代继续找出最优解 。
大家好
1
第五章 线性规划问题的灵敏度分析
(又称为后优化分析)
• 线性规划是静态模型 • 参数发生变化,原问题的最优解还是不是最优
• 哪些参数容易发生变化:C, b, A
• 每个参数发生多大的变化不会破坏最优解 • 灵敏度越小,解的稳定性越好
2
5.1 灵敏度分析的概念与内容
灵敏度分析概念: (1)当线性规划有关参数和条件发生变化时,分析其最优基/
Z0=CBTB-1b=CBb’ (2)灵敏度分析原理
(LP)最优基保持不变 σj ≤0 b’≥0
4
(3)分析结论
原问题 对偶问题
可行
可行
结论或继续计算的步骤 仍为最优解
可行 不可行 迭代求出最优(单纯形法)
不可行 可行 迭代求出最优(对偶单纯形法)
不可行 不可行 引入人工变量,编制新单纯形表 进行求解
当 akj 0, 有
当akj 0, 有
ck
c
j
zj
akj
akj
0
ck
cj zj akj
akj
0
为保证所有非基验 变数 量仍 检满足最优 , 有条件
maxcj zj j akj
akj 0cj'
mincj zj j akj
akj 0
8
153 4
CB XB b
x1 x2 x3 x4
13
x
当a '
B
'B
1
i,nk
(b
0,
则 b )有 B
1b
当 Ba'i,n1k
b
0,
则 b ' 有 B 1
b
0
bi bb12'a' 'i,bnk'kB
b
' m
1
0
b
k
0
bbbi12'' a'i,bnk'kb