当前位置：文档之家 › 第6章 单纯形法的灵敏度分析

第6章 单纯形法的灵敏度分析

  • 格式：ppt
  • 大小：687.50 KB
  • 文档页数：68

下载文档原格式

  / 68

合集下载

第6章单纯形法的灵敏度分析与对偶

第6章单纯形法的灵敏度分析与对偶

这个约束条件的对偶价格就和这个剩余变量的
z
有关了。这将使得最优目
j
标值特别“恶化”而不是改进，故这时约束条件的对偶价格应取 z j 值的相反
数- z j。
对于含有等于号的约束条件，其约束条件的对偶价格就和该约束方
程的人工变量有关了。其约束条件的对偶价格就等于此约束方程的人工变
量的 z j值。
管理运筹学
XB
bb12
5
5
,
X
B
5
5
b3 15
15
对于b1：比值的分母取B－1的第一列，这里只有β11=1，而β21=β31=0，则
1
max
b1
11
5 1
5
Δb1无上界，即Δb1≥－5，因而b1在[35,+∞) 内变化时对偶价格不变。
管理运筹学
18
§1 单纯形表的灵敏度分析
对于b2：比值的分母取B－1的第二列，β12＜0，β22＞0，则
§1 单纯形表的灵敏度分析
一、目标函数中变量Ck系数灵敏度分析
1.在最终的单纯形表里，X k是非基变量 由于约束方程系数增广矩阵在迭代中只是其本身的行的初等变换与Ck没有任何关系， 所以当Ck变成Ck+ Ck时，在最终单纯形表中其系数的增广矩阵不变，又因为Xk是非 基变量，所以基变量的目标函数的系数不变，即CB不变，可知Zk也不变，只是Ck变
xBi di1
|
d 'i1
0
50
而Min
xBi di1
|
d 'i1
0
25,故有当 50
b1
25,即250
b
b
325第一个
约束条件的对偶价格不变。

运筹学-单纯形法灵敏度对偶

运筹学-单纯形法灵敏度对偶

若新增约束如下：
max z 50x1 100x2 x1 x2 300 2x1 x2 400 x2 250 10x1 30x2 5000(电力约束) x1, x2 , 0
x1 x2 s1
把最优解x1=50,x2 =250代入电力约束 1050+30 250=80005000 新约束不满足,最优解变化
例题：已知某线性规划初始可行基是（S1 S2 S3 a1）， 最终单纯形表如下，求对偶价格不变时的△bi变化范围
x1 x2 s1
50 100 0
X1 50
1
0
0
S3 0
0
0
0
X2 100 0
1
0
s1 0
0
0
1
Zj
50 100 0
δj
0
0
0
（1） △b1的变化范围： ?
（2） △b2的变化范围：?
（3） △b3的变化范围： ? （4） △b4的变化范围：?
1 0 1 2 0.5
B1 p6'
2
1
1
0.5
2
0 0 1 1.5 1.5
Z6' 50 0.5 0 (2) 100 1.5 175
' 6
C6
Z6'
150 175
25
δ6´<0，最优解不变，即仍生产Ⅰ50件，Ⅱ100件。
2、变量xk系数列由pk变为pk´，在最终单纯形表 上xk是基变量
x1 x2 s1
50 100 0
X1 50 1
0
0
S3 0
0
0
0
X2 100 0
1
0
s1 0
0

第6章 单纯形法的灵敏度分析与对偶2007-10-15

第6章 单纯形法的灵敏度分析与对偶2007-10-15
目标:min f=300y1+400y2+250y3
s.t. y1+2y2>=50
y1+y2+y3>100
y1,y2,y3 >=0
❖ 目标:max z=50x1+100x2
❖ S.t. ❖ x1+x2<=300 ❖ 2x1+x2<=400 ❖ x2<=250
❖
❖ x1,x2>=0
原问题
目标:min f=300y1+400y2+250y3 s.t.
x1的目标函数系数C’有：
50-50=c1+ L ≤C‘=C1+△C1≤ c1+R=50+50，
0≤C‘≤100时，最优解不变。
**********************最优解如下*************************
目标函数最优值为 : 27500
变量
最优解 相差值
-------
-------- --------
设备B
2
设备C
0
II
资源限制
1
300台时
1
400
1
250
生产I可获得50元,II可获得100元,如何安排生产,获得 MAX?
模型
❖ 目标:max z=50x1+100x2 ❖ S.t. x1+x2<=300 ❖ 2x1+x2<=400 ❖ x2<=250 ❖ x1,x2>=0
假设现在有一个公司要租用工厂设备，那 么工厂获取利润有两种方法，一是自己生 产，二是出租设备资源。自己生产已有模 型。那么，如果出租，那么如何构建模型？ 设备价格为Ay1,By2,Cy3; 则

韩伯棠管理运筹学(第三版)_第六章_单纯形法的灵敏度分析与对偶

韩伯棠管理运筹学(第三版)_第六章_单纯形法的灵敏度分析与对偶

迭代 基
次数 变 量
CB
x1 x2 。 s1 50 100 0
s2
s3
0 0b
x1 50 1 0 1
0 -1 50
S2 0 0 0 -2
1 1 50
2
x2 100 0 1 0
0 1 250
zj
50 100 50 0 50
σj=cj-zj
0 0 -50
0 -50 2750 0
❖
从上表可以发现设备台时数的约束方程中的松弛变量S1
j ck akj 0, ck akj j ,
当a kj
0, ck
j
akj
,这里 j
akj
0;
当a kj
0, ck
j
akj
,这里 j
akj
0;
而当j k时, k ck ck zk ck ck zk ckaKK ,
因为xk是基变量,知 k 0, akk 1,故知 k 0.
x1 x2 s1 50 100 0 1 01 0 0 -2 0 10
s2
s3
00
b
0 -1 50
1 1 50
0 1 250
zj σj=cj-zj
50 100 50 0 0 -50
0 50 0 -50
Z= 27500
先对非基变量s1的目标函数的系数C3进行灵敏度 分析。这里σ3=-50，所以当C3 的增量ΔC3≤-(-50)即 ΔC3≤50时，最优解不变，也就是说S1的目标函数的系 数C′3=C3+△C3≤0+50=50时，最优解不变。
规划问题的对偶价格就不变。而要使所有的基变量仍然
是基变量只要当bj 变化成b′j =bj+△bj时，原来的基不变所 得到的基本解仍然是可行解，也就是所求得的基变量的

管理运筹学 第6章 目标规划

管理运筹学 第6章 目标规划

目标规划问题及模型
∵正负偏差不可能同时出现，故总有：
x1－x2+d--d+ =0
若希望甲的产量不低于乙的产量，即不希望d->0,用目标约束可
表为:
min{d }
x1
x2
d
d
0
若希望甲的产量低于乙的产量，即不希望d＋>0,用目标约束可
表为:
min{d }
x1
x2
d
d
0
若希望甲的产量恰好等于乙的产量，即不希望d＋>0,也不希望
2x1 2x2 12
s.t
4
x1 x1
2x2
8 16
4x2 12
x1 , x2 0
其最优解为x1＝4，x2＝2，z＊＝14元
目标规划问题及模型
但企业的经营目标不仅仅是利润，而且要考虑多个方面，如： (1) 力求使利润指标不低于12元； (2) 考虑到市场需求，甲、乙两种产品的生产量需保持1:1的比
标决策的需要而由线性规划逐步发展起来的一个分支。 由于现代化企业内专业分工越来越细，组织机构日益复
杂，为了统一协调企业各部门围绕一个整体的目标工作，产 生了目标管理这种先进的管理技术。目标规划是实行目标管 理的有效工具，它根据企业制定的经营目标以及这些目标的 轻重缓急次序，考虑现有资源情况，分析如何达到规定目标 或从总体上离规定目标的差距为最小。
min Z = f（ d ++ d - ）
（2） 要求不超过目标值，但允许达不到目标值，即只有使 正偏差量要尽可能地小（实现最少或为零）
min Z = f（ d +）
目标规划问题及模型
例1. 某企业计划生产甲，乙两种产品，这些产品分别要在 A,B,C,D四种不同设备上加工。按工艺文件规定，如表所示。

第六章单纯形法灵敏度分析与对偶

第六章单纯形法灵敏度分析与对偶
X4 19 2 4/3 0 X3 50 -1/2 -1/3 1 σj= cj - zj -4 -2/3 0
X4 X5 X6 19 0 0 1 2/3 -10/3 0 -1/6 4/3 0 -13/3 -10/3
bθ
2 1 Z = 88
∴ 最优生产计划是：生产1个单位产品C，生产2个单位产 品D，不生产A、B产品。可得最大总利润 88 个单位。
可能改变 C – CBB-1A ≤ 0 变
求出使该表达式仍然成立的 C 的变化范围
若 C 的变化超出该范围，则原最优解将改变
例1：某工厂用甲、乙两种原料生产A、B、C、 D
四种产品，要求确定总利润最大的最优生产 计划。该问题的线性规划模型如下：
Max Z = 9 x1 +8x2 + 50x3 + 19x4
则：在原最终单纯形表上，新变量对应的系数列为Pj '= B-1Pj，
检验数为 σj= Cj – CBB-1 Pj
若 σj= Cj – CBB-1 Pj ≤ 0，则原最优解不变；
若 σj= Cj – CBB-1 Pj ≥ 0，则继续迭代以求出新的最优解。
例3： 沿用例1 ►
如果该工厂考虑引进新产品E ，已知生产 E 产品1 个单位要消耗甲材料3个单位和乙材料1个单位。
要求：⑶产品E 的利润达到多少时才值得投产？
解： 设生产 E 产品X7个单位，单位产品的利润为C7，
则模型变为：
Max Z = 9 x1 +8x2 + 50x3 + 19x4 + 0x5 + 0x6+ C7x7 3x1+ 2 x2 + 10 x3 + 4 x4 + x5 + 3 x7 = 18（甲材料） 2x3+ 1/2x4 + x6 + x7 = 3 （乙材料）

管理运筹学ppt6第六章 单纯形法的灵敏度分析与对偶ok

管理运筹学ppt6第六章 单纯形法的灵敏度分析与对偶ok

§ 1 单纯形表的灵敏度分析
解：首先求出x3在最终表上的系数列B−1P'6，zj,σj
迭代 基变
x1
x2
s1
s2
s3
x3
次数 量
cB
50 100
0
0
0
160
x1
50
1
0
1
0
-1
10.5
s2
0
0
0
-2
1
1
20
2
x2
100
0
1
0
0
1
1
zj
50
100
50
0
50 125
σj=cj-zj
0
0
-50
0
-50 35
➢ 基变量系数cB变化 ➢ 对所有的zj都变化，包括zk
z j cB p j
假设cB=(cB1, cB2,…, ck ,…,cBm)
(cB1, cB2,…, ck+ck ,…,cBm)
§ 1 单纯形表的灵敏度分析
原最优单纯形表可表示如下。
迭代 基变
…
xk
…
xj
…
次数 量
cB
…
ck
…
cj
…
xB1
若要最优解不变
j = j ck akj
当j≠k时， j
0
akj 0
ck
j
akj
akj 0
ck
j
akj
当j=k时， k ck ck zk
xk为基变量 k 0, akk 1
k = 0
=ck ck zk ck akk
max{
j

运筹学02对偶理论(2)对偶单纯形法,灵敏度与参数分析

运筹学02对偶理论(2)对偶单纯形法,灵敏度与参数分析
从满足条件(2)的基出发去找原问题的最优解→ 对偶单纯形法思想： 从满足条件(2) 的基(一般称为正则基)B出发，经 过换基运算到另一个正则基，即一直保证条件 (2)成立， 直到找到一个满足条件(1)的正则基。
3.3 对偶单纯形法 Dual Simplex Method
Chapter3 对偶理论 Dual Theory
注：当模型的数据发生变化后，不必对线性规划问题
重新求解，而用灵敏度分析方法直接在原线性规划取
得的最优结果的基础上进行分析或求解 . 线性规划的参数分析(Parametric Analysis)是研究和分
析目标函数或约束中含有的参数μ在不同的波动范围内 最优解和最优值的变化情况．这种含有参数的线性规划
3.3 对偶单纯形法 Dual Simplex Method
Chapter3 对偶理论 Dual Theory
X XB σ
b
B-1A B-1b C-CBB－1A －CBB－1b 若上表为最优单纯形表，则下列两个式子同时成立：
(1) B1b 0 (可行性条件，又叫对偶最优性条件)
(2) C CB B 1 A 0 (最优性条件,又叫对偶可行性条件)
4.最优解、无可行解的判断。
作业：教材P81 1.12 (2)
下一节：灵敏度分析与参数分析
3.4 灵敏度与参数分析
Sensitivity and Parametric Analysis
3.4 灵敏度与参数分析 Sensitivity and Parametric Analysis
Chapter3 对偶理论 Dual Theory
3.3 对偶单纯形法 Dual Simplex Method
max z 7 x1 3x 2

灵敏度分析

灵敏度分析
该种情况必须另找新的最优解。此时，只要在原来的单纯形表（注意：是 最终单纯形表）里增加一行，用对偶单纯形法求解即可。
例2.5.5 对于例2.5.1的原问题，如果增加一道生产工序 ，要求产品满足约束条件 x1+ 3 x2 ≤ 9 ，试问应如何安排生产计划，可以使利润最大？
解：首先把表13的最优解代入新约束条件，看是否满足。显然，由于原最优解 不满足新约束，所以，必须寻找新的最优解。
解：先计算B﹣1⊿b。
0 1/4 0
B﹣1⊿b = -2 1/2 1
1/2 -1/8 0 再把结果加到表16的 b 列中。
0
4
0
0 = -8-8
0
00
cj
CB
XB
b
2
3
x1
x2
0
0
x3
x4
2
x1
4 +0
1 00
1/4
0
x5
4 -8
0 0 [-2]
1/2
3
x2
2 +0
0 1 1/2
-1/8
(cj－zj) 或 j
1/3
0
0 -M
x5
x6
-1/6 0
-1
-1/6
0
1/3
0
7/6
1
5/6
-5/6
0
-1/3 -M+3
（五）、增加一个约束条件的分析
增加一个约束条件： 增加约束条件一般意味着可行域的缩小。 情况1:基变量没有改变（即最优解满足增加的约束条件）
该种情况，最优解没变化。（方法：把基变量的值代入约束条件中，如果 满足新的约束条件，就可断定最优解没有变化。） 情况2:基变量不适应新增加的约束条件

灵敏度分析(运筹学).ppt

灵敏度分析(运筹学).ppt

0
0
1
0
0
0
x3
1 0
0 1 1
0 2 -1
-1
0
x4
0 1
0
0
-3/2 -1 1
-1
2.5.1 单纯形法的矩阵描述
1. 约束方程系数矩阵的变化
约束方程系数矩阵
，进行初等行
变换，相当于左乘一个相应的初等阵。
即
，在A中所包含的矩阵B，左
乘 后，则得到
。
2. 约束方程右端项的变化
3. 目标函数系数的变化
1. 灵敏度分析的概念：
当某一个参数发生变化后，引起最优解如何改变的 分析。 可以改变的参数有： bi——约束右端项的变化，通常称资源的改变； cj ——目标函数系数的变化，通常称市场条件的变 化； pj ——约束条件系数的变化，通常称工艺系数的变 化； 其他的变化有：增加一种新产品、增加一道新的工 序等。
2．分析原理及步骤：
（1）借助最终单纯形表将变化后的结果按下述基
本原则反映到最终表里去。
B①-1bi△变b化：=
（b+△b）´=B-1 b´+B-1 △b
（b+△b）=
B-1
b+
②pj变化：（pj+△ pj ）´= B-1 （pj+△ pj ）= B-1 pj+ B-1 △ pj = pj ´+ B-1 △ pj
围来确定最优解是否改变。 由于系数的改变，最优值z可能发生 变化而不再是原值了。
2、约束条件右端值的变化
约束条件右端值每增加一个单位 引起的最优值的改进量称为对偶 价格。
对偶价格只适用于在右端值仅发 生了很小变动的情况
2.5.3 单纯形法灵敏度分析

灵敏度分析

灵敏度分析

§2－6 灵敏度分析(Sensitivity Analysis)灵敏度分析的含义是指对系统或事物因周围条件变化显示出来的敏感程度的分析。

线性规划的灵敏度分析是在建立数学模型和求得最优解之后，针对数据资料变化而作的研究和分析。

这种分析可以从两个方面来看：一是希望知道根据一定数据得到的最优结果，在数据变化到一定程度时，对最优解有什么影响。

二是希望知道要使最优解保持不变，各个数据可以有多大幅度的变动。

灵敏度分析的具体步骤如下:1. 将参数的改变计算反映到最终单纯形表上来： 具体计算方法是，按下列公式计算出由参数,,ij i j a b c 的变化而引起的最终单纯形表上有关数字的变化：*1b B b −Δ=Δ （2.17）*1i i p B p −Δ=Δ （2.18）1()()mj j j j ij i i c z c z a y ∗∗=Δ−=Δ−−∑ （2.19） 2. 检查原问题是否仍为可行解; 3. 检查对偶问题是否仍为可行解；4. 按表（表2-8）所列情况得出结论和决定继续计算的步骤。

表2-8原问题 对偶问题 结论或继续计算的步骤可行解 可行解 仍为问题的最优解可行解 非可行解 用单纯形法继续迭代求最优解 非可行解 可行解 用对偶单纯形法继续迭代求最优解 非可行解非可行解引入人工变量，编制新的单纯形表重新计算下面分别就各个参数改变后的情形进行讨论。

6-1 分析j c 的变化范围目标函数中系数j c 的变化仅仅影响到检验数j j c z −的变 化，所以将j c 的变化直接反映到最终单纯形表中，只可能出现如表2-8中所示的两种情况。

【例6】 已知线性规划问题1122max (2)(3)z x x λλ=+++s.t .1212122212416515,0x x x x x x +≤⎧⎪≤⎪⎨≤⎪⎪≥⎩试分析1λ和2λ分别在什么范围变化，问题的最优解不变。

【解】 当120λλ==，上述线性规划问题的最终单纯形表见表2-3，当20λ=时，将1λ反映到该表中（见表2-9）表2-9表中解为最优解的条件是：11102λ−−≤，111055λ−+≤由此推导得121λ−≤≤时满足上述要求。

《管理运筹学》第四版 第6章 单纯形法的灵敏度分析与对偶 课后习题解析

《管理运筹学》第四版 第6章 单纯形法的灵敏度分析与对偶 课后习题解析

《管理运筹学》第四版课后习题解析第6章单纯形法的灵敏度分析与对偶1．解： （1）c 1≤24 （2）c 2≥6 （3）c s 2≤82．解：（1）c 1≥−0.5 （2）−2≤c 3≤0 （3）c s 2≤0.53．解：（1）b 1≥250 （2）0≤b 2≤50 （3）0≤b 3≤1504．解： （1）b 1≥−4 （2）0≤b 2≤10 （3）b 3≥45. 解：最优基矩阵和其逆矩阵分别为：⎪⎪⎭⎫ ⎝⎛=1401B ，⎪⎪⎭⎫ ⎝⎛-=-14011B ； 最优解变为130321===x x x ，，最小值变为-78； 最优解没有变化； 最优解变为2140321===x x x ，，，最小值变为-96；6．解：（1）利润变动范围c 1≤3，故当c 1=2时最优解不变。

（2）根据材料的对偶价格为1判断，此做法有利。

（3）0≤b 2≤45。

（4）最优解不变，故不需要修改生产计划。

（5）此时生产计划不需要修改，因为新的产品计算的检验数为−3小于零，对原生产计划没有影响。

7. 解：(1)设321,,x x x 为三种食品的实际产量，则该问题的线性规划模型为,, 4005132 4505510 35010168 325.2max 321321321321321≥≤++≤++≤++++=x x x x x x x x x x x x x x x z 约束条件：解得三种食品产量分别为0,75.43321===x x x ，这时厂家获利最大为109.375万元。

(2)如表中所示，工序1对于的对偶价格为0.313万元，由题意每增加10工时可以多获利3.13万元，但是消耗成本为10万元，所以厂家这样做不合算。

（3）B 食品的加工工序改良之后，仍不投产B ，最大利润不变；若是考虑生产甲产品，则厂家最大获利变为169.7519万元，其中667.31110,167.144321====x x x x ，，；（4）若是考虑生产乙产品，则厂家最大获利变为163.1万元，其中382.70,114321====x x x x ，，；所以建议生产乙产品。

运筹学单纯形法的灵敏度分析

运筹学单纯形法的灵敏度分析
的产量就大于零，即需考虑生产丙产品了。
• 所以，丙产品单位利润的变动范围是c3<4；
• 讨论： • 假设此时c3增加到6元，产量应为多少？
C3已超出变动范围
• 代入单纯形表 最后一段 继续计算。
段
Cj ↓
→ 基
0 b
23 x1 x2
6 x3
0 0 Qi x4 x5
2
x1
1
1
0 （-1） 4 -1
0
0
-1 4 -1
1
2 -1 1
0
-3 -5 -1
Bi变化影响哪些因素？
• 当bi变化时，从单纯形法计算过程可知，它不影响检验数， 只影响b列本身，也就是说，它不影响基变量但会改变最优 解的具体数值，如上例中，假设b1发生变化，劳动力使用从 一个劳动力增加到2个劳动力，即b1=2，则
• ∵b变化不影响检验数 • ∴单纯形表最后一段基变量结构不变，仍是x1，x2，改变的
x5
Qi
0
x4
1
1
0
x5
3
Cj-Zj →
1/3
1/3 1/3 1
1/3 （4/3） 7/3 0
2
3
10
0
3
1 9/4 →
0
0
x4 1/4 （1/4）
0
-1/4 1 -1/4 1
→
2
3
x2 9/4 1/4
1 7/4 0 3/4 9
Cj-Zj →
5/4
0 -17/4 0 -9/4
2
x1
1
1
3
3
x2
2
0
Cj-Zj → -8
5b1 3
分析

单纯形法灵敏度分析线性规划对偶理论

单纯形法灵敏度分析线性规划对偶理论
单纯形法的灵敏度分析与 线性规划对偶理论
1 23 4 5
图解法的灵敏度分析
灵敏度分析： 建立数学模型和求得最优解后，研究线性规 划的一个或多个参数（系数）ci , aij , bj 变化 时，对最优解产生的影响。
• 参数多为估计值或预测值，常常不精确 • 参数常常随着其他条件变化而变化
图解法的灵敏度分析
线性规划的对偶问题
• 假设另外一工厂要租用该厂的设备A、B、C，那么 该厂的厂长应该如何来确定合理的租金呢？
• 从出租人的角度：
– 生产1个单位Ⅰ产品所需的各设备的台时的总租金不应少 于自己生产1个单位Ⅰ产品的利润50元。
– 生产1个单位Ⅱ产品所需的各设备的台时的总租金不应少 于自己生产1个单位Ⅱ产品的利润100元。
• 另外， y1 , y2 , y3 ≥ 0
线性规划的对偶问题
max z = 50 x1 + 100 x2 s.t. x1 + x2 ≤ 300 2 x1 + x2 ≤ 400 x2 ≤ 250 x1 , x2 ≥ 0
原问题
min f = 300 y1 + 400 y2 + 250 y3
图解法的灵敏度分析
• 在一定范围内，当约束条件右边常数增加1 个单位时
– 若约束条件的对偶价格大于0，则其最优目标函 数值得到改善（变好）；
– 若约束条件的对偶价格小于0，则其最优目标函 数值受到影响（变坏）；
– 若约束条件的对偶价格等于0，则最优目标函数 值不变。
线性规划的矩阵描述
max z = c1x1 + c2x2 + … + cnxn s.t. a11 x1 + a12 x2 + … + a1n xn = b1

单纯形法解法的矩阵描述及灵敏度分析讲解

单纯形法解法的矩阵描述及灵敏度分析讲解

1.5 x1 7 / 2 1 0 0 1/ 4 1/ 2
2 x2 3 / 2 0 1 0 1/ 4 3 / 2
cj zj 0 0 0 1/8 9/ 4
对变化后的单纯形表继续迭代
c j 1.5 2 0 0
0
CB X B b x1 x2 x3 x4
x5
0 x3 15 / 2 0 0 1 5 / 4 15 / 2
2
-2
-2
B的逆阵 B-1
知识点1
• 目标函数为max时，判断最优的准则为 б≤0；
• 目标函数为min时，迭代过程与max一样 ，判断最优的准则为σ≥0。
知识点2
• 性质6：线性规划的原问题与其对偶问题 之间存在一对互补的基解；其中原问题 的松弛变量对应对偶问题的变量，对偶 问题的剩余变量对应原问题的变量；这 些互相对应的变量如果在一个问题的解 中是基变量，则在另一个问题的解中是 非基变量；将这对互补的基解分别代入 原问题和对偶问题的目标函数有z=ω。
单纯形法解法的矩阵描述及 灵敏度分析
张林刚 经济与管理学院
单纯形解法的矩阵描述
• 线性规划问题
max z CX
s.t.
AX b X 0
• 引入松弛变量Xs,化为标准型：
max z CX 0X s
s.t.
AX IX X 0, X
s s

b 0
单纯形解法的矩阵描述
2
x1 x1
x2 2x3 4x3 4
2
x1, x2, x3 0
加入松弛变量x4、x5，对上述模型进行标准化处理
max z 6x1 2x2 3x3 0x4 0x5
2

(优选)对偶单纯形法灵敏度分析

(优选)对偶单纯形法灵敏度分析

CN-CB B-1 N≤0
ATY ≥ CT;
min w Y T b bTY
-CB B-1 ≤0;
Y≥0Βιβλιοθήκη CB:1×m B-1：m ×m
YT= CB B-1
CB B-1：1 ×m Y： m ×1
ATY CT s.t.
Y 0
从上面可以看出：
1、当原问题达到最优时，松弛变量经过上述转换后构成的检验 数的相反数为其对偶问题的一个可行解，反之亦成立
初始对 偶单纯 形表
此时，初始单纯形表检验数均小于等于0，对偶可行，但原问 题初始解不可行
先选出基变量
后选进基变量cj
-1 -4 0 -3 0 0
CB XB b 0 x5 -3 0 x6 -2
0
x1 x2 x3 x4 x5 x6 -1 -2 1 - 1 1 0 2 1 -4 -1 0 1 -1 -4 0 -3 0 0
2x j
10 jx2
1,24,x33,4 x4
2
该问题用单纯形法求解时，需要先化标准型，此时约束
方程两边左边需要减去剩余变量，同时为了构造单位阵，
需要添加人工变量，采用大M法求解。
思考：上面约束方程化为标准型后，两边乘以-1， 就可得到单位阵。此时能否用单纯形法？原因?
答：不能。因为此时右边常数项为负数，解不可 行。为了保证初始解可行
（优选）对偶单纯形法灵敏度 分析
第四节 对偶单纯形法
对偶单纯形法并不是求对偶问题解的方法，而是利用单纯形 法求解规划问题时运用了对偶理论。
也就是说：对偶单纯形法与单纯形法一样都是是求解线性规划 的一种基本方法。它是根据对偶原理和单纯形法原理设计出来的， 因此称为对偶单纯形法。
在了解对偶单纯形法的实质之前，我们回顾一下单纯形法。

4.5 单纯形法的灵敏度分析解析

4.5 单纯形法的灵敏度分析解析

将其反映到最优单纯形表上可得下表
运
筹
学
40
迭 代 次 数
基 变 量
X1 S2
X1
X2 100 0 0
S1 0 1 -2
S2 0 0 1
S3 0 -1 1
CB
50 0
50 1 0
b
100 -50
2
X2
100 0
ZJ 50 0
1
100 0
0
50 -50
0
0 0
1
50 -50
250
CJ -ZJ
26000
的供应量没有变化，第二种资源的供
应量变为270个单位时，该工厂的最优
生产计划有什么变化；
运
筹
学
32
（2） 如果两种原料的供应量 没有变化，则设备的台时数在什么
范围变化时，该工厂的原来最优生
产计划中所生产的产品仍然投入生
产（最优基不变）；
运
筹
学
33
（3） 如果两种原料的供应量没有 变化，设备的台时数变为350个单位，
运
筹
学
3
只是 ck 变成了 ck ck . 这时 k ck zk
就变成了ck Vck zk k Vck . 要使原来 的最优解仍为最优解，只要 k Vck 0 即 可，也就是 ck 的增量 ck k即可.
运
筹
学
4
2. 在最终的单纯形表中， xk 是基变量 当 ck 变成 ck ck 时，最终单纯形表中约束
0 1 -2
x4
0 0 1
x5
0 -1 1
b
50 50
比值
-50
x1

单纯形法的灵敏度分析

单纯形法的灵敏度分析

bk bk
时，也就是原来的初始单
纯形表中的b向量变成了b’向量
0 0 ... 令 b bk ... 0 则有 b ' b b
9
这样在最终单纯形表中基变量XB的解就变成了
X 'B B .(b b ) B b B b 。
中从0变到Z3=50时，也就是只要当前余下一台时数设备从不能获利变成获利 50元时，譬如有人愿意出50元买一个设备时，我们就不必为生产Ι、П产品
而使用完所有的设备台时了，这说明了设备台时数的对偶价格就是Z3=50元。
对于含有大于等于号的约束条件，添加剩余变量化为标准型。这时 这个约束条件的对偶价格就和这个剩余变量的 z j有关了。这将使得最优目
+ CK a’Kj 。要使最优解不变，只要当J
δj a' kj
δ j ΔC k a' kj 0, ΔC k a' kj δ j 当 a' kj 0时 , ΔC
k

, 这里
0;
当 a' kj 0时 , ΔC
k
, 这里
δj a' kj
0; Z k ΔC a' kk , 因为 X K 是基变量， δj a' kj
14
zj 标值 “变差”而不是改进，故这时约束条件的对偶价格应取
值的相反数-j z
。
对于含有等于号的约束条件，其约束条件的对偶价格就和该约束方程的 人工变量有关了。其约束条件的对偶价格就等于此约束方程的人工变量的 值z j 。
7
下表给出了一个由最终单纯形表对于不同约束类型的对偶价格的取值。

管理运筹学--单纯形法的灵敏度分析与对偶对偶问题讲课讲稿

管理运筹学--单纯形法的灵敏度分析与对偶对偶问题讲课讲稿
2. 初始单纯表中的基变量Xs=b，迭代后的单 纯形表中为XB= B-1b
3. 初始单纯表中的约束系数矩阵为：
[A,I]=[B,N,I] 迭代后的单纯形表中约束系数矩阵为：
[B-1A, B-1I]=[B-1B, B-1N, B-1I]=[I , B-1N, B-1] 4. 若初始矩阵中变量xj的系数向量为Pj，迭代
x4
x5 值
0 x3
8
1
0
1
0
0
0 x4 12 0 2 0 1 0
0 x5 36 3 4 0 0 1
检验数j
3 50 0 0
• 最优基和最优基的逆
Cj
3 5 0 0 0比
CB XB
b
x1
x2 x3
x4
x5 值
0 x3 4 0 0 1 2/3 -1/3
5 x2 6 0 1 0 1/2 0
3 x1 4 1 0 0 -2/3 1/3
0
0
1
表
j
0
0 -50
0
-50
初始单纯形表为:
Cj
CB
CN
0
XB
XN
XS
0
X S
b
B
N
I
检验数j
CB
CN
0
当迭代若干步，基变量为X B时，新的单纯形表:
Cj
CB
CN
0
XB
XN
XS
CB
b X B
B-1
I
检验数j
0
B-1N CN- CB B-1N
B-1 - CB B-1
小结
1. 对应初始单纯表中的单位矩阵I，迭代后的 单纯形表中为B-1
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
管 理 运 筹 学
26
这时与其对应的约束条件譬如说设备台时 数全部用完了，只有当 c j
j , 即 c j z j
时，对应为非基变量的松弛变量要变成入基变 量了。
对于设备台时数约束来说，当其松弛变量
的价格指标从0变到50时，也就是只要当前余 下一台时数设备从不能获利变成获利50元时，
( B, I ) ( I , B )，因此也有： ( B , － I ) ( I , －B )
因此，在初始单纯形表里的系数矩 阵中的单位矩阵正好变成了B1. 如上例 的最终单纯形表如下：
管 理 运 筹 学
33
1
1
迭 代 次 数
基 变 量
X1 S2
X1
X2 100 0 0
S1 0 1 -2
管
理
运
筹
学
4
只是 ck变成了 ck ck . 这时 k ck zk 就变成了ck Vck zk k Vck . 要使原来 的最优解仍为最优解，只要 k Vck 0 即 可，也就是 ck 的增量 ck k 即可.
管
理
运
筹
学
5
2. 在最终的单纯形表中， k 是基变量 x 当 ck 变成 ck ck 时，最终单纯形表中约束
必然存在一个检验数大于0，我们可
以通过迭代来得到新的最优解。
管
理
运
筹
学
18
二、资源指标项的灵敏度分析
资源指标项的灵敏度分析是指： 约束方程中常数项在什么范围内变化
时，其对偶价格不变。因此我们首先
应从单纯形表格中找到有关对偶价格
的信息。
管 理 运 筹 学
19
所谓对偶价格是指：约束条件的常数项
增加一个单位而使得目标函数值得到改进的
管
理
运
筹
学
30
约束 条件 ≤
对偶价格的取值
等于这个约束条件对应的松弛变量的
z j 值。
≥ =
等于这个约束条件对应的剩余变量的 z j值的相反 数，即 z j .
等于这个约束条件对应的人工变量的 z j 值。
管
理
运
筹
学
31
其次，我们已知单纯形法的实质是:
令 A ( B, N ) ，
Ax b
S2 0
S3 0
b
50 50
250
X1 S2 2
C’1 1 0 0
0 0
1 100 0
管 理 运
1 -2
0 C’1 - C’1
筹 学
0 1
0 0 0
-1 1
1 -C’1+100 C’1-100
X2 100 0 ZJ CJ -ZJ C’1 0
17
从σ3≤0，得到-c1’≤0,即c1’≥0，并 且从σ5≤0，得到c1’≤100。 那么如果c1’取值超出这个范围，
如在最优解中S2 =50是基变量，即原 料A有50千克没用完，再增加A原料是不 会增加利润的，故A的对偶价格为0。
管
理
运
筹
学
24
我们知道对于任何的松弛变量它在目标函 数中的系数 c j 0, 而在最终的单纯形表上若松 弛变量为基变量时，都有其检验数 j 0, 那 么为松弛变量的 z j 也为零，因为 z j c j j 0, 这正确反映了对任何为基变量的松弛变量所对 应的约束条件的对偶价格为零。
量的 z j 有关了。这将使得最优目标值特
别“恶化”而不是改进，故这时约束条 件的对偶价格应取 j z
管 理 运 筹
值的相反数 z j .
学
29
对于含有等于号的约束条件，其约束
条件的对偶价格就和该约束方程的人工变
量有关了。其约束条件的对偶价格就等于
此约束方程的人工变量的
zj
值。
下表给出了一个由最终单纯形表对于 不同约束类型的对偶价格的取值。
方程的增广矩阵不变，但是基变量的目标函数的系 数 cB 变了，则 妨设
cB (cB1 , cB 2 ,L , ck ,L cBm ), 当 cB 变成 cB (cB1 , cB 2 ,L , ck Vck ,L cBm ), 则：
z j ( j 1, 2,L n)
一般也变了，不
管
理
运
筹
S2 0 0 1
S3 0 -1 1
CB
50 0
50 1 0
b
50 50
2
X2
100 0
ZJ 50 0
1
100 0
0
50 -50
0
0 0
1
50
250
27500 CJ -ZJ -50
管
理
运
筹
学
34
由上表可知：
1 1 B 2 0
0 1 0
迭代
1 1 1
同时还可以知道： b B 1b. b
管 理 运 筹 学
11
也就是说，要使得最优解不变， 对于除了a'kk以外的 所有大于0的a'kj，Ck的增量满足ΔCk 所有小于0的a'kj满足ΔCk j a' kj ，
j
a' kj
，
所以可知Ck的变化范围为: j j max a'kj 0 ΔCk Min a'kj 0 a' kj a' kj
第六章 单纯形法的灵敏度 分析与对偶
管
理
运
筹
学
1
§1 §2
单纯形表的灵敏度分析 线性规划的对偶问题
§3
§4
对偶规划的基本性质
对偶单纯形法
管
理
运
筹
学
2
第一节 单纯形表的灵敏度分析
管
理
运
筹
学
3
一、目标函数中变量Ck系数灵敏度分析
1.在最终的单纯形表里，Xk是非基变量 由于约束方程系数增广矩阵在迭代中只是其 本身的行的初等变换与ck 没有任何关系，所以当 ck 变成 ck ck 时，在最终单纯形表中其系数的增 广矩阵不变，又因为Xk是非基变量，所以基变量的 目标函数的系数不变，即CB不变，可知Zk也不变，
管 理 运 筹 学
7
＝cB1a1 j＋cB 2 a2 j＋（ck＋ ck）ak j＋cBm am j ＝cB1a1 j＋cB 2 a2 j＋ck akj＋cBm am j＋ ck ak j ＝z j＋ ck ak j
管
理
运
筹
学
8
根据上式可知检验数 了 , 且有： j
学
6
j , a2 j , , akj , amj )T z j (cB1 , cB 2 , , ck , cBm )(a1 a1 j 变成了 zj (cB1 , cB 2 , , ck＋ ck , cBm ) akj a mj
管
理
运
筹
学
35
下面我们研究当右端项 b j 发生变 化时，在什么范围内其对偶价格不变
由于 b j 的变化并不影响系数矩阵的迭
代，故其最终单纯形表中的系数矩阵没有
变化。要使对偶价格不变，只要原来最终 单纯形表中的所有 z j 值都不变化。
管
理
运
筹
学
36
而 z j cB p j , 这样当基变量的系数不变， 即基不变时，原线性规划问题的对偶价 格就不变。而要使所有基变量不变，只 bj 要使当 变化时，原来的基不变得到的 基本可行解仍然是可行解，也就是所求 的基变量的值一定要大于0。
量Δc3≤50时，最优解不变。
再对基变量x1的目标函数的系数c1进行灵敏
度分析。 在a11’,a12’,a13’,a14’,a15’中，除了知道a11’ 50 和 a13’大于0， a15’小于0，可知 3 50, 有:
a13 1
管
理
运
筹
学
15
j ' max a 1 j 0 max 50 50，同理 a '1 j j ' 5 有： min a 1 j 0 min 50. a '1 j a '15
数量。因此可知约束条件的对偶价格与松弛 变量（或剩余变量，或人工变量）的 z j 值 有关系，下面仍以上面的题为例在单纯形表 中找到约束方程的对偶价格。
此题的求解结果与最终单纯形表如下：
管 理 运 筹 学
20
迭 代 次 数
基 变 量
X1 S2
X1
X2 100 0 0
S1 0 1 -2
S2 0 0 1
13
迭 代 次 数
基 变 量
X1 S2
X1
X2 100 0 0
S1 0 1 -2
S2 0 0 1
S3 0 -1 1
CB
50 0
50 1 0
b
50 50
2
X2
100 0
ZJ 50 0
1
100 0
0
50 -50
0
0 0
1
50
250
27500 CJ -ZJ -50
管
理
运
筹
学
14
我们先对非基变量S1的目标函数的系数C3 进行灵敏度分析。这里σ3=-50，所以当c3的增
j ( j 1, 2, m) 变成
j c j z j
c j ( z j ck akj ) (c j z j ) ck akj j ck akj