常见的运筹学灵敏度分析

格式：ppt
大小：1.59 MB
文档页数：33

下载文档原格式

常见的运筹学灵敏度分析

cj
4
3
0
0
CB
XB
b
x1
x2
x3
x4
3
x2
4
5
x1
6
0
1
3/5
-2/5
1
0
-2/5
3/5
Z
42
0
0
-1/5
8/5
13
用单纯形法迭代得最优解表如下：
cj
4
3
0
CB
XB
b
x1
x2
x3
0
x3
20/3
0
5/3
1
5
x1
26/3
1
2/3
0
Z
130/3 0
1/3
0
0
x4 -2/3 1/3 16/15
（3）技术系数aij变化的分析第一种情况（当jJN）：即aij为非基变量xj的技术系数
6/5
继续迭代以求出新的最优解。
11
（2）当CB(即基变量的目标函数系数)中某个Cj发生变化时
则会影响到所有变量的检验数σ=CBB-1A－C
解不等式组
CB B1 A C 0
就可得到 Cj的范围
例18 设基变量x1的系数C1变化为 C1 C1 ，在最优性不变的条件下，试确定 C1 的范围
*Big M
0
0
0
0
0
0
23
2、增加新约束的灵敏度分析 Final tableau (Total iteration=3)
Basis C(j) X1
4.000
S1
0
X1 3.000
X2 4.000

灵敏度分析(运筹学)

--25-- --第2章对偶问题--
目标函数中价值系数cj的变化分析
分为cj是对应的非基变量和基变量两种情况。
(1) 若cj是最终单纯形表中，非基变量xj的系数，要保证最终表中这个检验数仍小于或等于零。
(2) 若cj是最终单纯形表中，基变量xj的系数，要保证最终表中所以的非基变量的检验数仍小于或等于零。
③cj变化：直接反映到最终表中，计算检验数。 ④增加一个约束方程：直接反映到最终表中。 ⑤增加新产品：仿照pj变化。
2．分析原理及步骤：
（2）检查改变后的最终表是否符合单纯形表的结构要求（基变量的值中无负数，基变量的系数向量构成单位矩阵，基变量的检验数全为0），或是否符合对偶单纯形表的结构要求（检验数中无正数，基变量的检验数全为0，基变量的系数向量构成单位矩阵）;
（3）检查原问题是否仍为可行解; （4）检查对偶问题是否仍为可行解;
2．分析原理及步骤：
（5）按照下表所列情况得出结论或继续计算的步骤。
原问题可行解可行解非可行解非可行解
对偶问题可行解非可行解可行解非可行解
结论或继续计算的步骤
原最优基不变
用单纯形法继续迭代
用对偶单纯形法继续迭代引入人工变量，扩大原单纯形表继续计算
0
x5 4 0 0
3
x2 2 0 1
00
0
x3 1 -2 1/2 -3/2
0
x4 1/4 1/2 -1/8 -1/8
0
x5 θ 0 1 0 0
B-1 是最终计算表中的最优基的逆
0
B 1 (b
b)
B 1b
B 1 b
B 1b
B
1
br
0

运筹学灵敏度分析(最全版)PTT文档

c + c YP 表中b列中有负数，即解答列有负数，故可用对偶单纯形法求最优解。
1、代表产品的单位利润或单位售价时，灵敏j度分析可用于j 预先确定保j持现有生产规模条件下单位产品利润或单价的可变范围。
解题步骤：先用单纯形法解题，然后考虑参数变化，最后确定变化范围。
△c2/2≤0和△c2/8-1/8≤0
br bi / air ;
i=1，2，…，m i=1，2，…，m
air < 0
br bi / air
得到公式:
5=-8, △b2≤2/0.
ma ab ix irai{r0} brm iab inira{ ir0}
（2）当cr是基底变量xr的系数，即cr CB，cr变化 cr后，有
故△c2的变化范围:
例题: 将上面例题进行实际应用。每台设备台时的影子价格为元。若该厂又从别处抽出4台时用于生产两种产品，求这时该厂生产两种产品的最优方案。
表中b列中有负数，即解答列有负数，故可用对偶单纯形法求最优解。
最优解见下表
cj
CB XB b 2 x1 4 0 x3 2 3 x2 3
cj-zj
230 0 0 x1 x2 x3 x4 x5 1 0 0 0.25 0 0 0 1 -0.25 -05 0 1 0 0 0.25 0 0 0 -0.5 -0.75
5=-8, △b2≤2/0.
2每台3设例备0台：时的0求影子0第价格一为元章。例题中当第二个约束条件b2变化范围△b2。
△c2≥-1.
每台设备台时的影子价格为元。
设基变量x2的系数c2变化△c2，在原最优解不变的条件下，确定△c2的变化范围。
x1 x2 x3 x4 x5 0 0 1 -0.

运筹学24灵敏度分析

非基变量的价格系数变化，在原最优解不变的条件下，确定的变化范围。
（2）当cj是基变量的价值系数——它的变化将影响所有非基变量的检验数.
N CN CB B 1 N 为当最cj优变解化，时否，如则能可保用持单纯 N形法0 继，续则迭当代前求解出仍新的最优解。
将cj看作待定参数，令 N CN CB B1N 0
②（B-1b）i<0, 当前基为非可行基, 可用对偶单纯形法求出新的最优解；
③如何求出保持最优基不变的bi的范围? 把bi看作待定参数,令B-1b≥0,求解该不等式组即可；
b发生变化， XB B1(b b)
X B B 1b
B1(b b) B1b B1b
B1b B1(0 , 0 ,L , 0 , br , 0 ,L , 0)T (a1r br ,L , air br ,L , amr br )T br (a1r ,L , air ,L , amr )T
（或消耗的资源量）和单位产品利润，设该种产品的产量为 xk，则 ck 和 Pk 已知，需要进行 “是否投产”的决策。
如果算出的σk<0,说明新产品D不宜投产，否则会使产品总利润下降！
(2) 增加1个约束条件：
相当于系数阵A增加1行
首先将原最优解代入新增约束检查是否满足？是，则说明新增约束不影响最优解。否则再作下面的讨论：
将新增约束标准化，添加到原最优表格中（相当于约束矩阵新增1行）；
进行规格化处理——用矩阵的行变换将当前基变成单位阵；
用适当方法（通常是对偶单纯形法）进行迭代求出新的最优解。
（3）其他情况讨论：某个产品工艺参数改变；新品代替原产品等；
bi air br ≥ 0 i 1 , 2 ,L , m

运筹学灵敏度分析

单击此处添加小标题
原始和对偶问题都取得最优解时，最大利润 max z=min y
单击此处添加小标题
资源价格（元/吨）
单击此处添加小标题
资源限量（吨）
对偶问题是资源定价问题，对偶问题的最优解y1、y2、...、ym称为m种资源的影子价格（Shadow Price）影子价格为当bi有单位增量，若原最终优基不变，总收益Z的变化，也可以说yi是对第i种资源的一种价格估计，由于影子价格是指资源增加时对最优收益的贡献，所以又称它为资源的机会成本或者边际产出当市场价格低于影子价格时，企业应该买进资源用于扩大生产，高于影子价格时，企业应该将已有资源卖掉。影子价格的计算
CS XS b
B E N1
CB XB B-1b
E B-1 B-1N1
σ
0 CS－CB B-1 CN1－CB B-1N1
初始表
对偶的定义
max ω=-Yb s.t. -YA≤-C Y ≥0
min z’=-C X s.t. -AX≥-b X ≥0
2、其他形式问题的对偶
原始问题约束条件的性质，影响对偶问题变量的性质。原始问题变量的性质，影响对偶问题约束条件的性质。
max z=C X s.t. AX≤b X ≥0
以B为基的单纯形表
当XS为松弛变量时CS=0,松弛变量检验数为－CB B-1 ， CB B-1称为单纯形乘子
Cj
CB CN
CB XB B-1b
XB XN
b
B N
B-1b
E B-1N
例4 某工厂要用三种原材料C,P,H混合调配出三种不同规格的产品A,B,D。已知产品的规格要求、单价和原料的供应量、单价如下表。该厂应如何安排生产，能使利润最大？

运筹学第11讲灵敏度分析

第二章线性规划的对偶理论
Duality Theory 对偶问题的经济解释——影子价格线性规划的对偶问题对偶单纯形法灵敏度分析对偶问题的基本性质
1、什么是灵敏度分析？是指研究线性规划模型的某些参数(bi, cj, aij）或限制量（xj, 约束条件）的变化对最优解的影响及其程度的分析过程<也称为优化后分析>。
设备A(h)
设备B(h)
调试工序(h)
利润(百元)
Ⅰ
Ⅱ
每天可用能力
资源
产品
0
5
6
2
1
1
2
1
15
24
5
例2-1
如何安排生产计划才能使总利润最多？
解：
(1) 设x1, x2分别表示Ⅰ、Ⅱ两种产品的生产数量，得LP模型
max z = 2x1+x2 s.t. 5x2 ≤15 6x1+2x2 ≤24 x1+ x2 ≤5 x1, x2 ≥0
用单纯形法求解得最终单纯形表
得最优解为：
X*=(7/2, 3/2, 15/2, 0, 0)T
zmax=8.5(百元)。
即每天生产3.5单位产品Ⅰ，1.5单位产品Ⅱ时总利润最多，且
max z = 2x1+x2 s.t. 5x2 ≤15 6x1+2x2 ≤24 x1+ x2 ≤5 x1, x2 ≥0
5. 分析系数 aij 的变化
系数矩阵A
s.t.
对偶问题决策变量的最优解<影子价格>：
初始单纯形表
最优单纯形表
X*=B-1b
CN－CBB-1N ≤0
－CBB-1 ≤0
原问题基变量的最优解：

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

可变单元格单元格名字 $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
线性规划
不是最优表，继续迭代，得，最优解 X*=（5/3，13/2， 7/3，0，0）生产品种保持不变。最优值变为
7/3 0 500 300 13 / 2 3750 5/3
300
xB
x3
500
0
0
0
b’ 2 6 2
x1
0 0 1
x2
0 1 0 0
x3
1 0 0 0
x4
1/3 1/2 -1/3 -150
x5
-1/3 0 1/3 -100

x2 x1
-3600 200
总利润增加了 150 元。
运筹学
设 b1 , b2 , b3 的增量为 b1 , b2 , b3
2 1 1 / 3 1 / 3 b1 b * b B 1b 6 0 1 / 2 0 b2 2 0 1 / 3 1 / 3 b 3 2 b1 b2 / 3 b3 / 3 2 b1 b2 / 3 b3 / 3 6 b2 / 2 6 b2 / 2 2 b / 3 b / 3 2 b / 3 b / 3 2 3 2 3 若要解仍可行，则 b * 0 ，即

运筹学8_灵敏度分析

CB XB x1 x2 x3 x4 x5 x6 b
0 x4 0 -2 0 1 -1 -1 5
1 x1 1 1 0 0 1 -1 5
3 x3 0 1 1 0 0 1 15
σ
0 -3 0 0 -1 -2
对于b2：β12<0,
β22>0，所以
−
5
=
max{−
b2 }
β 22
≤
Δb1
≤
min{−
b1 }
β12
基变量 xi 的系数 ci 的变化范围
• 检验数 σj =cj - CBB-1 Pj
• 如果 ci 是基变量xi 的系数， ci 变化影响每一个非基变量xj对应的检验数σj
• 当 ci 变为 ci’ = ci +Δci 时，要使得线性规划最优解不
变需要且只需要每一个非基变量xj对应的检验数都有
σj’= cj ’- CBB-1 Pj ≤ 0
什么是灵敏度分析
• 在以前讲的线性规划问题中，aij，bi，cj 均为已知常数，但实际上这些数往往是一些估计和预测的数字，如随市场条件变化， cj 的值就会变化； aij 也会随工艺条件的改变而改变， bi 是各项资源的投入数量，随着企业资金水平的变化也会变化。
• 问题：当这些参数中的一个或几个发生变化时，问题的最优解会有什么变化？这些参数在多大范围内变化时，问题的最优解不变？这就是灵敏度分析。
113000
CB XB x1
x2
x3
x4
x5
x6
b
0 x4 0 -2 0 1 -1 -1 5
1 x1 1 1 0 0 1 -1 5
3 x3 0 1 1 0 0 1 15

运筹学课件灵敏度分析

运筹学教程
Cj
210
CB 基 b X1 x2 x3
0 x3 15 0
51
2 x1 5 1
10
0 x4 2 0
-4 0
Cj-Zj
0
-1 0
00 x4 x5 00 01 1 -6 0 -2
工厂的最优生产计划改为只生产产品1，每天的生产数量5件。
解：（2）
设每天的调试可用能力为5
运筹学教程
1 b' B1b 0
x5
x4
5
24
x1, x2 , x3, x4 , x5 0
用单纯形法求解如下：
运筹学教程
Cj
210 0 0
CB 基 b X1 x2 x3 x4
x5
0 x3 15/2 0 2 x1 7/2 1 1 x2 3/2 0
01 00 10
5/4 -15/2 ¼ -1/2 -1/4 3/2
Cj-Zj
0
8
2
3 / 2 0 2
运筹学教程
将其反映到最终的单纯形表，原问题非可行解，采用dual单纯形法
Cj
2
CB 基 b X1
0 x3 35/2 0
2 x1 11/2 1
1 x2 -1/2 0
Cj-Zj
0
10 x2 x3 01 00 10 00
00 x4 x5 5/4 -15/2 ¼ -1/2 [-1/4] 3/2 -1/4 -1/2
aij
y i
i 1
运筹学教程
（2）、检查原问题是否仍为可行解。（3）、检查对偶问题是否仍为可行解。
原问题
可行解可行解非可行解非可行解
对偶问题
可行解非可行解可行解非可行解

运筹学课件2.5 灵敏度分析

a11 的变化范围。
由于 y 1.5 0 0 0 1 0 1 B 0 .5 0 0 1.25 1 0
当 a11 从3变为 3 a11 时，x1 的检验数变为
c1 z c1 y1
' 1 ' 1
y2
4 1.5
增加新产品相当于增加一个决策变量，系数矩阵也将增加一列
设研制出一种新产品—小旅行车，每辆旅
行车用钢材1.5吨，工时1.25小时，座椅 0.25套，利润3千元，试问该新产品是否该投产？（给出数学模型，再讨论） 1 .5 1.25 p 第一种解法：设该车产量为 x6 ，则 6
4
3
0
0
0
0
xB B 1b x1 x5 200 0 x2 600 0 x1 200 1 x7 -200 0
2600
x2 x3 x4 x5
0 1 0 0 0.5 1 -0.5 -0.5 -0.4 -0.4 0.4 0 1 0 0 0
x7
0 0 0 1
j
0
0
-1
2
-0.4
0
0
cj
CB
0 3 பைடு நூலகம் 0
4
3
0
0
0
0
xB B 1b x1 0 x5 0 x2 200 0 x1 400 1 x3 400 0
2200
x2 x3 x4 x5
0 1 0 0 0 0 0 1 -0.4 -0.4 0.4 0 1 0 0 0
x7
1 2 -1 -2
j
0
0
0
-0.4
0
-2
增加约束后，最优目标函数值不会更好，一般会差一些。

运筹学11-灵敏度分析-b

Operational Research
8
图解灵敏度分析（约束b）
该线性规划问题可以用图解法作如下表达
x2
2x1＋x2 ≤ 8
2x1＋x2 ≤ 9
x1＋3x2 ≤ 8 B G
机器A保持变化率的范围为：从B到F B（0,2.67）；F（8,0） B点对机器A的限制是 2×0＋2.67＝2.67 F点对机器A的限制是 2×8＋0＝16 因此，当约束范围为〔2.67，16〕，变化率一定，14USD/h
线性规划的参数 A B C 会在一定范围内波动。
A B C 代表什么？技术、资源与价值。
• 不变：参数在什么范围内变化，最优解不变？ • 规律变：在什么范围内变化，最优解可很快得到？怎样得到？
可以重新求解，但更为简单的是进行灵敏度分析。
• 再求解：如果不能很快得到最优解，如何继续求解？
Operational Research
因为范围为〔2.67，16〕，收入增加 14×（13-8）＝70 如果A工作能力增加到20小时？
最优解产生于F点
Operational Research
11
代数灵敏度分析（约束b）
讲代数解之前必须复习的一些知识
B 基的初始状态、 B* 最优基的初始状态 B*-1 最优基的逆矩阵，在哪里能够找到？初始E的最终状态 b 是初始约束条件， B*-1 b是最终约束条件
书上解法（公式法）：（1）找到B-1 （2）如求b1的改变，则看矩阵中的第一列
正元素除-bi最大者为下限负元素除-bi最小者为上限
Cj
58 6 0 0
b
CB XB x1 x2 x3 x4 x5
5 x1 1 0 0 2 －1 4
8 x2 0 1 1 －1 1 8

运筹学课件灵敏度分析举例

x2
1 0
x3
1 -1/2
x4
-2 3/2

20 x1 15
j cj z j
CB
30 50
cj xB
50
30
0
0
35 0 x1 7.5 1 j c j z j 1425 0
x2
b
x1
x2
1 0 0
x3
x4

1/2 -1/2 -1/4 3/4 -2.5 -22.5

木工用量 4 x1 3x2 120 木工可使用量油漆工用量负条件。
2 x1 x2 50 油漆工可使用量决策变量还应当满足 x 0 ， x2 0，叫做非 1
例1的数学模型
max z 50x1 30x2
s.t.
4 x1 3x2 120 2 x1 x2 50 x1 , x2 0
x3
1
0
x4
0
1

30
25
x4
j cj z j
0
50
30
0
0
第一次换基并求解
CB
0 50
x3 x1
cj xB b
20 25 1250
50
30
0
x1
0 1 0
x2
（1） 1/2 5
x3
1 0 0
x4
-2 1/2 -25 20 50
0
j cj z j
第二次换基和求解
cj xB
50 30 0 0
CB
30 50
x2
b
x1
0 1 0
x2
1 0 0

运筹学课程04-灵敏度分析资料

XS为松弛变量,XS=(xn+1,xn+2,…,xn+m), I为m×m 矩阵
A ( B, N )
XB X X N
C (CB , CN )
XB ( B, N ) X b BX B NX N b N
2019/4/12 4
NEUQ
B-1b
0
≤0
但B 1b 0不变
Z： CBB-1b
若C N C B B 1 N 0 此表仍为最优，
此时最优解不变但最优值改变
若C N C B B N 0 此表不是最优单纯形表
用单纯形法继续迭代
2019/4/12 9
1
NEUQ
1、非基变量对应的价值系数的灵敏度分析
设 ck 变化为
X B 检验数
CB CB I 0 CB CB B B 0
因此
1 C C B A0 B 1 C B 0 B
1
2019/4/12
7
NEUQ
一、目标函数系数C（价值系统）变化
cj 变动可能由于市场价格的波动，或生产成本的变动
cj 的灵敏度分析是在保证最优解的基变量不变的情况下，
NEUQ
灵敏度分析又称“后验分析”，它是对已经得到的最优
方案改变某些条件来检验最优解的“稳定性”以及目标函数最优值随各种条件变化的“敏感性”；换言之，假定对于已知线性规划问题已求得的最优解是获得的最大利润的生产计划安排，现在如果在生产过程中成本系数向量C，约束常数向量b,约束系数A以及其他条件发生变化或波动，这些变化限制在什么范围内，在原来得到的最优安排仍为最优，而不需要改变工作计划？
' k

运筹学讲义-灵敏度分析

(I A)1Δ Y Δ X

ΔY 0
5
2.4.2 价值系数 cj 的灵敏度分析 • cj 变动可能由于市场价格的波动，或生产成本的变动
• cj 的灵敏度分析是在保证最优解的基变量不变的情况下，分析cj 允许的变动范围cj
• cj 的变化会引起检验数的变化，有两种情况
– 非基变量对应的价值系数变化，不影响其它检验数 – 基变量对应的价值系数变化，影响所有非基变量检验数
bi

bk ak ,ni
bi

bk ak ,ni
要求对所有 k 都成立 , 从而有
max k

ak
bk
,n
i
ak ,ni
0

bi

min k

bk ak ,ni
ak ,n i
0

此时 , 基变量的解值和目标函数会发生变化
2.4.6 新增约束条件的分析
16
2.4.7 灵敏度分析举例
例2.4.3 某工厂生产三种产品 A, B, C，有五种生产组合方案。
下两表给出有关数据。规定每天供应 A产品至少110 个，求收益最大的生产方案。
产量组别
品种
I II III IV V
单位售价 (元 )
A 产品数量
32440
10
B 产品数量
x5 x6 x7 00 0 1 1/4 -1 0 1 -1 0 -3/4 1 0 0.25 1
cj-zj -3.25 0 -2.75 0 0 -0.25 -1
以b2为例, x6是对应的初始基变量，所以有
max01 .205,02100b2min 01.7050 200b213.33, 1000b2133.33

运筹学第二章灵敏度分析

m ax z 300 x1 500 x2
x1 4
s
.t
.
2 3
x2 x1
1 2
2 x
2
18
x 1 , x 2 0
m ax z 300 x1 500 x2 400 x3
x1 2 x3 4
s.t
.
2 3
x2 x1
x3 2x
12 2 x3
18
x1 , x2 , x3 0
改进多少，才能得到该决策变量的正数解。0表示不需再改进。
目标式系数：指目标函数中的系数允许增量、允许减量：表示目标函数中的系数在允许的增
量与减量范围内变化时，原问题的最优解不变。
450和1E+30的含义是什么？
2.2.2 图解法
0<=c1<=750
x2
8
7 6
5
4
3
2
可行域
1
c1=0(z=0x1+500x2) c1=300(z=300x1+500x2)
约束条件系数 a i j 变化的灵敏度分析
变量 x j 变化的灵敏度分析
约束条件数量变化的灵敏度分析
2.2 单个目标函数系数变化的灵敏度分析
只有一个系数cc j j 发生变化，即其他条件均不变，把
300 改成 500
m ax z 300 x1 500 x2
x1 4
s
.t
.
2 3
x x
2 1
规划求解得到
2.8 增加一个约束条件
增加一个约束条件，比如增加电力供应限制时，最优解是否会发生变化？
假设生产一扇门和窗需要消耗电力分别为20kw和 10kw，工厂可供电量最多为90kw，此时应该在原有的模型中加入新的约束条件：

18灵敏度分析(运筹学)

例：
产 6
备用资源 12 20
甲乙利润
问：如何安排产品产量，可获最大利润？如何安排产品产量，可获最大利润？
3
解
maxZ=5X1 +8X2 +6X3 X1+ X2 + X3+X4 X1+2X2+2X3 X1 … X5 ≥0 = 12 +X5 =20
λ6 = C6 - CBB-1 P6 = 10 - (5 8) 2 -1
-1 1 = 10 - 12 = -2 < 0
3 2
结论：结论：无利
12
（1）利润为多少时，投产产品D有利？利润为多少时，投产产品D有利？ λ6 = C6 - CBB-1 P6 = C6 - 12 >0 得 C6 >12 （2） C6 =15 时 ~ P6 = B-1 P6 = 2 -1 -1 1
27
•若c1从5增加到 c2从8减少到若从增加到增加到6, 从减少到减少到7: •C1的允许增加百分比的允许增加百分比=(6-5)/3=0.33% 的允许增加百分比 •C2的允许减少百分比的允许减少百分比=(8-7)/2=0.5% 的允许减少百分比 •0.33%+ 0.5%=0.83%, 最优解不变最优解不变.
∴10≤ b1 ≤ 20
10
(2)、 b1改变 b1=30 、改变,
， B-1 b=
2 -1 -1 1
30
40 = -10 20
11
(三)、添加新变量的灵敏度分析三、对于新产品D 已知1个单位D 例对于新产品D，已知1个单位D要消耗可以得利润10 甲：3 乙：2 可以得利润10 问：投产产品D是否有利？投产产品D是否有利？

运筹学课件第五节灵敏度分析

参数 aij,bi,cj 的变化引起的单纯形表上的有关数字的变化：
b ' B 1b Pj B 1 Pj
' m
(c j z j ) c j aij yi
' i 1
运筹学教程
（2）、检查原问题是否仍为可行解。
（3）、检查对偶问题是否仍为可行解。
原问题
可行解可行解非可行解非可行解
0 0 x3 x4 4/5 1 -1/5 0 1/5 0 -1/10 0
0 x5 -6 1 0 -3/2
随利润的变化，调整如下：
生产产品1为2件，产品2为3件。
运筹学教程
解（2）设产品2的利润1+
Cj
CB 基 b 0 x3 15/2 2 x1 7/2 1+ x2 3/2 Cj-Zj
2 X1 0 1 0 0
运筹学教程
CB 0 2 3
2 x1 基 b x5 3/8 0 x1 11/4 1 x2’ 15/8 0 Cj-Zj 0
Cj

3 x2’ 0 0 1 0
0 0 0 x3 x4 x5 -1/24 -1/6 1 -1/12 1/6 0 1/8 0 0 -5/24 -1/3 0
-M x6 1/24 1/12 -1/8 -M+5/24
将其反映到单纯形表
Cj CB 基 b 0 x3 15/2 2 x1 7/2 1 x2 3/2 Cj-Zj Cj 基 b x3 -9 2 x1 x2’ 3 Cj-Zj
2 X1 0 1 0 0 2 X1 0 1 0 0
1 x2 0 0 1 0 1 x2 0 0 1 0
3 0 X2’ x3 11/2 1 ½ 0 ½ 0 3/2 0 3 x2’ 0 0 1 0 0 x3 1 0 0 0

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

x2
y1
x3
x4
3
x2
4
4
x1
6
0
1 1/5 3/5 -2/5
1
0 1/5 -2/5 3/5
Z
36
0
0 -3/5 1/5
6/5
第二种情况（当jJB）：由于B中元素的改变影响到B-1
的变化，因此也影响到整个单纯形表T(B)的变化。目前的
基B对应的解有可能既不是原始可行，也不是对偶可行。
于是不如重新求解
0
03
x1
x2
x3
x4
y5
0
1
3/5
-2/5 2/5
1
0
-2/5
3/5 2/5
0
0
1/5
6/5 -1/5
18
用单纯形法迭代求得最优解为：
cj
4
3
0
03
CB
XB
b
x1
x2
x3
x4
y5
3
y5
10
4
x1
2
Z
38
0
5/2
3/2
-1 1
1
-1
-1
10
0
1/2
1/2
10
（5）对增加新约束条件的分析
在企业生产过程中，经常有新情况发生，造成原本不
反之,当 j 0 时,最优解改变,需要用单纯形法重新进行迭代,以求得新的最优解.
9
例题17 对于下列线性规划模型,为使最优解不变，讨论非基变量y1的目标函数系数c3的变化范围。
max Z 4 x1 3 x2 2 y1
2 s.t.3
x1 x1

3 2
x x
2 2

16
（4）对增加新产品的分析
设某企业在计划期内，拟议生产新产品Xn+1，并已知新产品的单位利润为 Cn+1 ，消耗系数向量为 Pn+1=(a1,n+1,a2,n+1,…am,n+1)T，此时应如何分析才能确定该新产品是否值得投产？
增加新产品应在不影响企业目前计划期内最优生产的前提下进行。因此可从现行的最优基B出发考虑：
cj
4
3
CB
XB
b
x1
x2
3
x2
3
3/2
1
0
x3
15
-5/2
0
Z
9
1/2
0
0
0
x3
x4
0
1/2
1
-3/2
0
3/2
得到新的最优解为：x1=0,x2=3; maxz=9
8
2.对价值系数Cj变化的分析（1）当CN（非基变量的目标函数系数）中某个Cj发生变化时，只影响到非基变量xj的检验数由于 j (CB B 1 Pj ) (C j C j ) j C j 所以,当 j 0 即当 Cj j 时,最优解不变（最小值）
解：
CB B1 A C 3
4 C110
1 0
3
/5 2/
5

2 3
/ /
5 5

4

C1
3
0
0
4 C1
3
1 5

2 5

C1
6 5

3 5

C1

4

C1
3
0
0
12
0
0
12
5 5 C1
6 5

3 5

C1
4
3
0
0
CB
XB
b
x1
x2
x3
x4
3
x2
4
4
x1
6
0
1
3/5
-2/5
1
0
-2/5
3/5
Z
36
0
0
1/5
6/5
5
从矩阵形式的单纯形表中可知，b2的变化只影响解的可行性B-1b≥0,因此，为使最优解不变，只需变化以后的
B-1b≥0即可。
B1
b

3/ 2
5 /5
2 3/
/ 524
3/5

6

6

0
CB B1 b 3 4126 12
将上述数字替换最优单纯形表中相应位置的数据得：
cj
CB
XB
b
3
x2
12
4
x1
-6
Z
12
4
3
0
0
x1
x2
x3
x4
0
1
3/5
-2/5
1
0
-2/5
3/5
0
0
1/5
6/5
7
用对偶单纯形法迭代，求出的最优单纯形表如下：
5

b2

7542585253bb22

0
由
7542585253bb2200
解得：
16 b2 36
写 B-1
6
若b2变化超过范围，则需用对偶单纯形法进行求解。如 b2=6，则
B1
b

3/ 2
5 /5
2 / 524 12
灵敏度分析=对于市场的变化，我们的决策究竟怎样变化（不需要将它当成一个新问题）
B
Xb
I
-Z
0
N
B-1N
B-1b
Cj-Zj
CB-CBB-1B
灵敏度分析
n
max z cjxj
或
j1

n
ajxj
bi (i 1,2, L ,m)
j1 xj 0(j 1,2, L ,n)
y1 2 y1
24 26

x1
,
x
2

0
(材料约束) (工时约束)
用单纯形法求得其最优表为：
cj
CB
XB
b
3
x2
4
4
x1
6
Z
36
4
320
0
x1
x2
y1
x3
x4
0
1 -1/5 3/5 -2/5
1
0 4/5 -2/5 3/5
0
0 3/5 1/5
6/5
10
解：因为y1为非基变量，其目标函数系数c3的变化只会影
3 2
x x
2 2

y1 2 y1
24 26

x1
,
x
2

0
(材料约束 ) (工时约束)
cj
4
320
0
CB
XB
b
x1
x2
y1
x3
x4
3
x2
4
4
x1
6
0
1 -1/5 3/5 -2/5
1
0 4/5 -2/5 3/5
Z
36
0
0 3/5 1/5
6/5
解：
3 CB B1 P3 C3 1/ 5
灵敏度分析的方法是在目前最优基B下进行的。即当参数A、b、c中的某一个或几个发生变化时，考察是否影响以下两式的成立？
B 1b 0
C B B
1A C
0
3
1、对于参数b的灵敏度分析
从矩阵形式的单纯形表中可以看出，b的变化只影响最优解的变化和最优值的变化。
b
X
XB
B-1b
将约束条件加入松驰变量，化为等式 3 x1 4 x2 x5 30 ，加入最优单纯形表中。
cj
CB
XB
b
3
x2
4
4
x1
6
0
x5
30
Z
36
4
300
0
x1
x2
x3
x4
x5
0
1 3/5 -2/5 0
1
0 2/5 3/5 0
3
40
01
0
0 1/5
6/5 0
在这个表中，由于x1,x2是基变量，必须为单位向量，因此将x1,x2化为单位向量得
若σn+1=CBB-1Pn+1－Cn+1<0，则应投产若σn+1=CBB-1Pn+1－Cn+1>0，则不应投入。
即新产品的机会成本小于目前的市场价格时，应投产否则不应投产。
例19 现有一新产品丙，经预测其单位利润为3，技术消耗系数为P5=（2，2）T，问该产品是否值得投产？
17
解：
5
CB
22/3
1
0
0 2/3 -1/3
0
x3
10/3
0
0
1 1/6 -5/6
Z
106/3 0
0
0 6/7 1/6
22
对于增加新产品和新约束的灵敏度分析，在计算机软件中是用Modify Program 来完成的
1、增加新产品的灵敏度分析
Final tableau (Total iteration=3)
Basis C(j) X1
紧缺的某种资源变成为紧缺资源，对生产计划造成影响
，如水、电和资源的供应不足等，对生产过程提出了新
约束等。
对增加新约束条件的分析方法步骤是：

常见的运筹学灵敏度分析

合集下载