运筹学灵敏度举例
1.已知以下线性规划问题
max z= 2x1 +x2
s.t.
x1 +2x2 -x1 x1,
x2,
-x3 +x3 x3
≤8 ≤4 ≥0 0 0 0 8/2 12/3
+x2 -2x3
的最优单纯形表如下:
z x1 x5
(1) 求使最优基保持不变的c2=1的变化范围
C 2 -1 1+
CB 2 0
z x1 x5
3-≥0,≤3,即c2≤4。当c2=5,即
=4
z x1 x5
x
2进基,x1离基
z x2 x5
新的最优解为x1=0,x2=0,x3=0,x4=0,x5=0,max z=20 (2) 对c1=2进行灵敏度分析
C 1 -1 0 0 2+
CB 2+ 0
z x1 x5
z x
x x x x 0 RHS 3203/2
30,3,当≥-3/2时,即c1≥1/2时,最优基保持不变。 202
当c1=4时,=4-2=2,最优基保持不变,最优解的目标函数制为z=16+8=32。
1(3)增加一个新的变量x6,c6=4,a6。
2
1
z6c6Wa6c6204242
2
T
1011
Y6Ba6
1123
1
新的单纯形表为
z x1 x5
x6进基,x5离基
z x1 x6
新的最优解为x1=4,x2=0,x3=0,x4=0,x5=0,x6=4,max z=24。
(4)增加一个新的约束x2+x3≥2,求新的最优基和最优解。
z x1 x5 x6
z
x
x 3/1
x 3/1
x
x
x
RHS
用对偶单纯形法求解
z x
z x1 x5 x2
x x x x x RHS 新的最优解为x1=4,x2=2,x3=0,x4=0,x5=6,x6=0,max z=10。
2.
(1)利润最大化的线性规划模型为: max z= 25x1 +12x2 +14x3 s.t.
3x1 2x1 x1 x1,
+2x2
+3x2 x2, x x x x +x3 +2x3
x3,
+15x4 +4x4 +3x4 +2x4 x4 x x x x ≤2400 ≤3200 ≤1800 ≥0 x x x x RHS RHS 单纯形表为: z x
z x5 x6 x7
x1进基,x5离基 z x
z x1 x6 x7
x3进基,x6离基
z x1 x3 x7 x2进基,x1离基
z x2 x3 x7 最优解为:x1=0,x2=400,x3=1600,x4=0,x5=0,x6=0,x7=600,max z=27200
即最优生产计划为:产品A不生产;产品B生产400万件;产品C生产1600万件; 产品D不生产,最大利润:27200万元。
原料甲:耗用2400吨,没有剩余;原料乙:耗用3200吨,没有剩余;原料丙:耗用1200吨,剩余600吨。
(问三种原料的利用率?)
(2) 产品A利润变化范围: -C -25+ -12 -CB -12 -14 0
z x2 x3 x7
-14 -15 0 0 0 0 -1-≤0,≥-1,-c1’=-c1+≥-25-1=-26,即c1≤26(万元/万件)
产品B利润变化范围: -C -25 -12+ z x
x -CB
z
-12+ x2 -14 x3 0
x7
-14 x -15 x 0 x 0 x 0 x 0 RHS 101215/4084/5
,,-1≤≤12,-13≤-12+≤0,-13≤-c2’≤0,
61/201241/4016
即:0≤c2’≤13。
产品C利润的变化范围: -C -25 -12 -14+ -CB -12
z x2
-15 0 0 0 0 -14+ x3
0 x7
101213/20,14 41/208
-1≤≤8,-15≤-14+≤-6,-15≤-c3’≤-6,6≤c3’≤15
产品D的变化范围 -C z -CB -12 -14 0
z x2 x3 x7
-25 x
-12 x -14 x -15+
x 0 x 0 x 0 x 0 RHS -21-≤0,≥-21,-15+≥-36,-c4’≥-36,c4’≤36。
(3) 求三种原料的影子价格和四种产品的机会成本
由最优单纯形表可知,原料甲、乙、丙的影子价格分别为:
6万元/吨、4万元/吨、0万元/吨。 产品A、B、C、D的机会成本分别为(
qa
ii1
m
ij
):
26万元/万件、12万元/万件、14万元/万件、36万元/万件。 产品A、D在最优解中不安排生产的原因是机会成本大于利润。
(4) 在最优解中,原料甲的影子价格(6万元/吨)最大,因此这种原料最紧缺。如果原料A增加120吨,最优单纯形表的右边常数成为:
1/21/4024001204006001000
B1b01/2032001600016000
3/23/411800600180420
因此最优基保持不变,影子价格不变,原料的紧缺程度不变。
运筹学灵敏度举例
1.已知以下线性规划问题
max z= 2x1 +x2
s.t.
x1 +2x2 -x1 x1,
x2,
-x3 +x3 x3
≤8 ≤4 ≥0 0 0 0 8/2 12/3
+x2 -2x3
的最优单纯形表如下:
z x1 x5
(1) 求使最优基保持不变的c2=1的变化范围
C 2 -1 1+
CB 2 0
z x1 x5
3-≥0,≤3,即c2≤4。当c2=5,即
=4
z x1 x5
x
2进基,x1离基
z x2 x5
新的最优解为x1=0,x2=0,x3=0,x4=0,x5=0,max z=20 (2) 对c1=2进行灵敏度分析
C 1 -1 0 0 2+
CB 2+ 0
z x1 x5
z x
x x x x 0 RHS 3203/2
30,3,当≥-3/2时,即c1≥1/2时,最优基保持不变。 202
当c1=4时,=4-2=2,最优基保持不变,最优解的目标函数制为z=16+8=32。
1(3)增加一个新的变量x6,c6=4,a6。
2
1
z6c6Wa6c6204242
2
T
1011
Y6Ba6
1123
1
新的单纯形表为
z x1 x5
x6进基,x5离基
z x1 x6
新的最优解为x1=4,x2=0,x3=0,x4=0,x5=0,x6=4,max z=24。
(4)增加一个新的约束x2+x3≥2,求新的最优基和最优解。
z x1 x5 x6
z
x
x 3/1
x 3/1
x
x
x
RHS
用对偶单纯形法求解
z x
z x1 x5 x2
x x x x x RHS 新的最优解为x1=4,x2=2,x3=0,x4=0,x5=6,x6=0,max z=10。
2.
(1)利润最大化的线性规划模型为: max z= 25x1 +12x2 +14x3 s.t.
3x1 2x1 x1 x1,
+2x2
+3x2 x2, x x x x +x3 +2x3
x3,
+15x4 +4x4 +3x4 +2x4 x4 x x x x ≤2400 ≤3200 ≤1800 ≥0 x x x x RHS RHS 单纯形表为: z x
z x5 x6 x7
x1进基,x5离基 z x
z x1 x6 x7
x3进基,x6离基
z x1 x3 x7 x2进基,x1离基
z x2 x3 x7 最优解为:x1=0,x2=400,x3=1600,x4=0,x5=0,x6=0,x7=600,max z=27200
即最优生产计划为:产品A不生产;产品B生产400万件;产品C生产1600万件; 产品D不生产,最大利润:27200万元。
原料甲:耗用2400吨,没有剩余;原料乙:耗用3200吨,没有剩余;原料丙:耗用1200吨,剩余600吨。
(问三种原料的利用率?)
(2) 产品A利润变化范围: -C -25+ -12 -CB -12 -14 0
z x2 x3 x7
-14 -15 0 0 0 0 -1-≤0,≥-1,-c1’=-c1+≥-25-1=-26,即c1≤26(万元/万件)
产品B利润变化范围: -C -25 -12+ z x
x -CB
z
-12+ x2 -14 x3 0
x7
-14 x -15 x 0 x 0 x 0 x 0 RHS 101215/4084/5
,,-1≤≤12,-13≤-12+≤0,-13≤-c2’≤0,
61/201241/4016
即:0≤c2’≤13。
产品C利润的变化范围: -C -25 -12 -14+ -CB -12
z x2
-15 0 0 0 0 -14+ x3
0 x7
101213/20,14 41/208
-1≤≤8,-15≤-14+≤-6,-15≤-c3’≤-6,6≤c3’≤15
产品D的变化范围 -C z -CB -12 -14 0
z x2 x3 x7
-25 x
-12 x -14 x -15+
x 0 x 0 x 0 x 0 RHS -21-≤0,≥-21,-15+≥-36,-c4’≥-36,c4’≤36。
(3) 求三种原料的影子价格和四种产品的机会成本
由最优单纯形表可知,原料甲、乙、丙的影子价格分别为:
6万元/吨、4万元/吨、0万元/吨。 产品A、B、C、D的机会成本分别为(
qa
ii1
m
ij
):
26万元/万件、12万元/万件、14万元/万件、36万元/万件。 产品A、D在最优解中不安排生产的原因是机会成本大于利润。
(4) 在最优解中,原料甲的影子价格(6万元/吨)最大,因此这种原料最紧缺。如果原料A增加120吨,最优单纯形表的右边常数成为:
1/21/4024001204006001000
B1b01/2032001600016000
3/23/411800600180420
因此最优基保持不变,影子价格不变,原料的紧缺程度不变。