PPT《运筹学》

运筹学 灵敏度分析与线性规划的对偶理论 灵敏度分析 图解法下的灵敏度分析定义:研究LP问题中目标函数系数C与约束条件中系数矩阵A与常数向量b的变化(局部或全部变动)对LP的最优解 与最优值 的影响程度分析的问题称为LP的灵敏度分析.

由于C,b,A通常表述产品需求,原材料价格,未来的商品售价及企业的加工能力、资源消耗,故在数学建模时的估计有可能出现误差,且未来的环境亦是不确定的,有可能出现变化,因此有必要对应用问题的解作灵敏度分析. 图解法下的灵敏度分析灵敏度分析通常讨论如下内容:C,b,A变动(局部或全部)后LP最优解是否仍存在?若存在的话,最优解有多大程度的变化?C,b,A在什么范围内变动时能保证LP的原最优解不变?若C,b,A的变动超出上述范围后,如何利用LP的原最优解 来求解变动后的 最优解.这些C,b,A的变动,在出现情况下对决策者有利?在什么情况下对决策者不利?此称为对偶价格研究对象(C的变动对目标最优解的影响). 各种问题求解问题建模求解算法(理论、算法步骤、计算复杂性)解的存在性、唯一性、可靠性(误差分析、灵敏度分析) 估计有误差未来环境变动 数值解 精确解 灵敏度分析 误差分析 数值解 估计正确 LPa(LP原规划) max z=50x1+100x2

0 100

200 300

200 100

300 400 x1+x2=300 2x1+x2=400 x2=250 B(50,250) C(100,200) D z=50x1+100x2 LPb(C的变动对LP最优解的影响) max z=60x1+50x2

0 100

200 300

200 100

300 400 x1+x2=300 2x1+x2=400 x2=250 B(50,250) C(100,200) D z=60x1+50x2 LPc(b1的变动对LP最优解的影响) max z=50x1+100x2

0 100

200 300

200 100

300 400 2x1+x2=400 x2=250 D x1+x2=300 x1+x2=310 (50,250) B (100,200) C B'

(60,250) z=50x1+100x2 LPd(b2的变动对LP最优解的影响) max z=50x1+100x2

0 100

200 300

200 100

300 400 x1+x2=300 2x1+x2=400 x2=250 B(50,250) C D C'

G'

z=50x1+100x2 命题Ⅰ:在例1的优化模型中,A,b不变,讨论C变动的如下问题:欲使LP的最优解不变,仍为 ,C1与C2应满足什么条件?当C2=100 不变,欲使LP 的最优解不变,仍为 ,C1应满足什么条件?当C1=50 不变,欲使LP 的最优解仍为 ,C2应满足什么条件?当C1,C2均变动,例如C1=60,C2=50时,最优解是否变动?欲使最优解变动为 ,求C1,C2应满足的条件? 解:由图(a),原最优解 对应B点,设LE,LF,LG直线之斜率分别为kE,kF,kG,则由对应直线方程可得kE= -1,kF=0,kG= -2,kz= - G1/G2,此中kz为等值线z=50x1+100x2之斜率.由图(a)中知,欲使最优点仍为B,则应有当C2=100时,由*式知,需要 方使最优点不变.当C1=50时,由*式知,需要 方使最优点不变. 解:当C1=60,C2=50时,由图(b)知最优点为C (100,200),故最优解 且由*式知:此时显然不满足条件 欲使最优解变动为 即最优点为C时,由图(b)知应有 此时有最优值 z(100,200)=100C1+200C2. 问题Ⅱ:在例1的优化模型中,C不变,讨论b与A分别变动时的如下问题:b1=300?310,b2,b3,A不变时,求设备(台时)的对偶价格Pb1.b2=400?410,b1,b3,A不变时,求原料(克)的对偶价格Pb2. 解: 计算机解法下的灵敏度分析(P102~P112) LP: LP '

(见上表)LP 注1 注2 LP'

最终单纯形表 注3 设G为R3中的凸集,它有8个顶点,每一个顶点对应一个基本可行解,当采用单纯形表迭代时,其基本原则是以一个初始顶点开始,然后沿相邻顶点行进(迭代),直到终点(最优解)为止.注意到在R3中的凸集D的每一个顶点的相邻顶点有三个(也可有五个如(b)等)凸集D中,每一顶点或基本可行解对应一个基矩阵,则相邻顶点对应的基矩阵只有一列不同),因此从一个起点B0(对应一个初始基本可行解或初始基)开始,沿相邻顶点行进(迭代),直到终点(对应最优解)B2的迭代或运行路径可以有多条,如B0?B1?B2,B0?B5?B4?B3?B2等,这多条路径尽管有相同的起点(初始可行解),相同的终点(最优解),但迭代步数可以不等. B0 B1 B5 B4 B2 B3 B0 B1 B2 B3 B4 B5 B6 B7 D (a) (b) LP:L次迭代 LP '

r次迭代 例9 对上述LP的C1(又称价值系数)作灵敏度分析 -50

0 -50

0 0 σ(2)

27500 50

0 50

100 50 z(2)

250 1

0 0

1 0

100 x2

50 1

1 -2

0 0

0 s2

50 -1

0 1

0 1

50 x1

2 0

0 0

100 50 b(i) s3 s2 s1 x2 x1 CBi xBi i 解1 解2

0 0

0 σ(2)

0 100 z(2)

250 1

0 0

1 0

100 x2

50 1

1 -2

0 0

0 s2

50 -1

0 1

0 1 x1 r

0 0

0 100 b(i) s3 s2 s1 x2 x1 CBi xBi i 对上述LP的b1作灵敏度分析解 max z=50x1+100x2LP: s.t x1+x2≤300 2x1+x2≤400 x2≤250 x1,x2≥0 max z=x1+100x2LP'

: s.t x1+x2≤300 2x1+x2≤400 x2≤250 x1,x2≥0

100 0

50 50 -1

0 1

0 1 x1

2 50

1 1 -2

0 0 s2

250 1

0 0

1 0 x2

27500 50

0 50

100 50 z(2) -50

0 -50

0 0 σ(2)

100 0

0 50

50 -1

0 1

0 1 s1

1 75

150 -1

1 0

0 2 s2 --

250 1

0 0

1 0 x2

25000 100

0 0

100 0 z(1) -100

0 0

0 50 σ(1)

250 400

300 比值

0 0

0 100

50 σ(0)

0 0

0 0

0 0 z(0)

250 1

0 0

1 0

0 s3

400 0

1 0

1 2

0 s2

300 0

0 1

1 1

0 s1

0 0

0 0

100 50 b(i) s3 s2 s1 x2 x1 CBi xBi i 最优解不变条件

100 0

50 -1

0 1

0 1 x1

2 50

1 1 -2

0 0 s2

250 1

0 0

1 0 x2

0 100 z(2)

0 0

0 σ(2)

100 0

0 50

50 -1

0 1

0 1 s1

1 75

150 -1

1 0

0 2 s2 --

250 1

0 0

1 0 x2

100 0

0 100

0 z(1) -100

0 0

0 σ(1)

250 400

300 比值

0 0

0 100 σ(0)

0 0

0 0

0 0 z(0)

250 1

0 0

1 0

0 s3

400 0

1 0

1 2

0 s2

300 0

0 1

1 1

0 s1

0 0

0 0

100 b(i) s3 s2 s1 x2 x1 CBi xBi i 结论:当时,不仅LP'

与LP有相同最优解,见迭代过程亦相同.一般迭代过程可不同,但最终单纯形表结果相同,由于迭代过程为初等行变换,故变换后之方程与原方程同解,故不影响最终结果,此二数应在0点的两侧.

0 对决策者有利对决策者不利 PBi0 经济含义 要求 符号 LP: LP '

证:1 若在LP最终单纯形表中,xk为基变量,此时原最优解的可行性与最优性都可能遭到破坏,故需修改初始单纯形表并重新计算. 例9 在原例1中,该厂除生产Ⅰ,Ⅱ产品外,现又试制成一种新产品Ⅲ,并知生产单位产品Ⅲ需设备2台时,消耗原料A需0.5Kg,原料B需1.5Kg,此时可获利150元,试问该厂是否应该生产产品Ⅲ,或此时保持原方案是否合适?若该厂对产品Ⅲ的工艺结构又有了改进,此时生产单位产品Ⅲ需使用1.5设备台时,消耗原料A需2Kg,消耗原料B需1Kg,而同时经计算每件产品Ⅲ的利润为160元,问此时该厂对原生产计划是否要改变?如何改变? 解设xj―生产j产品的数量,j=1,2,3,则上述问题可看作原LP1的扩充或修改. max z=50x1+100x2LP1: s.t x1+x2+s1=300 2x1+x2+s2=400 x2+s3=250 x1,x2,s1,s2,s3≥0 max z=50x1+100x2+150x3LP2: s.t x1+x2+2x3+s1=300 2x1+x2+0.5x3+s2=400 x2+1.5x3+s3=250 xj, sj≥0, j=1,2,3 故该厂仍应保持原生产方案,即生产产品Ⅰ50件,产品Ⅱ250件,不生产产品Ⅲ可得最大利润2.75万元. 解当该厂对产品Ⅲ工艺结构改进后,该生产计划问题可看作原问题LP1?LP3 (本例得到退化的最优解) max z=50x1+100x2LP1: s.t x1+x2+s1=300 2x1+x2+s2=400 x2+s3=250 x1,x2,s1,s2,s3≥0 max z=50x1+100x2+160x3LP2: s.t x1+x2+1.5x3+s1=300 2x1+x2+2x3+s2=400 x2+x3+s3=250 xj, sj≥0, j=1,2,3 即此时该厂不生产产品Ⅰ与Ⅱ,单独生产产品Ⅲ200件可获得最大利润32000元=3.2万元

0 3........