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

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

  • 格式：pptx
  • 大小：588.45 KB
  • 文档页数：51

下载文档原格式

  / 51

合集下载

第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
韩伯棠管理运筹学(第三版)_第六章_单纯形法的灵敏度分析与对偶

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


迭代 基
次数 变 量
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时，原来的基不变所 得到的基本解仍然是可行解，也就是所求得的基变量的
第六章单纯形法灵敏度分析与对偶

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

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
《管理运筹学》第四版 第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
分析
单纯形法的灵敏度分析与对偶

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


目标函数： max z=50x1+100x2
x1+ x2≤300 s.t. 2x1+x2≤400
x2≤250 x1 ≥0, x2≥0
max z=50x1+100x2
x1+ x2+s1=300
s.t.
2x1+x2+s2=400
x2+s3 =250
x1 ≥0, x2≥0, si≥0
一、线性规划问题解的基本概念
△C3 ≤－（－50）=50；
c’=c+△C<=0+50=50
最优解不变。
（2）再分析基变量的系数分析：
ck k
max J ak jjak j0 ckm J i ak n jjak j0
例如对基变量X1的系数C1进行灵敏度分析：
从表中获得了:
a11=1, a12=0, a13=1, a14=0, a15=-1
❖
OBJ COEFFICIENT RANGES
❖ VARIABLE CURRENT ALLOWABLE ALLOWABLE
❖
COEF INCREASE DECREASE
❖
X1
50.000000 50.000000 50.000000
❖
X2
100.000000 INFINITY 50.000000
❖
RIGHTHAND SIDE RANGES
4. 对偶问题的约束条件系数矩阵A是原问题的AT
maxz c1x1 c2x2 cnxn
a11x1 a12x2 a1nxn b1
s.t.
a21x1 a22x2 a2nxn b2
am1x1 y2 bm ym
对偶单纯形法+灵敏度分析讲解

对偶单纯形法+灵敏度分析讲解

答：不能。因为此时右边常数项为负数，解不可 行。为了保证初始解可行
北京联合大学 耿钰
第四节 对偶单纯形法
例 用对偶单纯形法求解
maxZ x1 4x2 3x4
x1 2x2 x3 x4 3
x
2x j
10 jx2
1,24,x33,4 x4

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、当原问题达到最优时，松弛变量经过上述转换后构成的检验 数的相反数为其对偶问题的一个可行解，反之亦成立
-1 x1 7 0 x3 4
7
1 7/2 0 5/2 -2 -1/2 0 3/2 1 3/2 -1 -1/2 0 -1/2 0 -1/2 -2 -1/2
最优解 X*=（7，0，4， 0）T
Z*=-7
北京联合大学 耿钰
例6 用对偶单纯形法求解
min w 2x1 3x2 4x3
（P）
x1 2x2 x3 3 2x1 x2 3x3 4
原问题不 可行，应 该换基迭 代。但按 对偶单纯 形法的思 想，每次 均应保证 检验数均 非正
cj
CB XB b -1 x1 3 0 x6 -8
3
-1 -4 0 -3 0 0
x1 x2 x3 x4 x5 x6 1 2 - 1 1 -1 0 0 -3 -2 -3 2 1 0 -2 -1 -2 -1 0
运筹学第二章第6讲

运筹学第二章第6讲

12
例题4：写出以下模型的对偶问题
max z = 3 x1 − 2 x2 − 5 x3 + 7 x4 + 8 x5 x2 − x3 + 3 x4 − 4 x5 = −6 2 x1 + 3 x2 − 3 x3 − x4 ≥ 2 − x1 + 2 x3 − 2 x4 ≤ −5 s.t. − 2 ≤ x1 ≤ 10 5 ≤ ≤ 25 x2 , ≥ 0, 为自由变量 x5 x3 x4
OR1
对偶问题（或原问题） 对偶问题（或原问题） 目标函数 MinW
约束条件数： 约束条件数：n 第i个约束条件类型为“≥” 个约束条件类型为“ ” 个约束条件类型为 个约束条件类型为“ ” 第i个约束条件类型为“≤” 个约束条件类型为 个约束条件类型为“ 第i个约束条件类型为“=” 个约束条件类型为 对偶变量数： 个 对偶变量数：m个 第i个变量 个变量≥0 个变量 个变量≤0 第i个变量 个变量 第i个变量是自由变量 个变量是自由变量
OR1
15
2 弱对偶性：极大化原问题的任一可行解的目标 弱对偶性： 函数值不大于其对偶问题任意可行解的目标函数 值。即： C X≤ Yb
证明：设原问题为maxZ=CX, AX ≤b ，X ≥0. ≥0. 证明： 原问题为maxZ=CX,
为原问题的可行解， ≤b， X 为原问题的可行解，有AX ≤b，
二.对偶线性规划的定义 对偶线性规划的定义
max Z = CX ( LP ) AX ≤ b S .T . X ≥ 0
称线性规划(DLP)为线性规划 为线性规划(LP)的对偶线性规划 称线性规划 为线性规划 的对偶线性规划
minω = yb ( DLP ) yA ≥ C S .T . y ≥ 0

对偶单纯形法

§6 对偶单纯形法在介绍对偶单纯形法之前，让我们先利用对偶理论来重温一下单纯形法的基本思想，以便给单纯形法一种新的解释。

考虑线性规划（LP ）和其对偶规划（DP ）：x c T min b w T max(LP) s.t ⎩⎨⎧≥=0x b Ax (DP) s.t TT c A w ≤我们已经知道，（LP ）的单纯形表为基变量 x 1 x 2 ┄ x nx B B -1 A B -1bf c B T B -1 A – c T c B T B –1b定理1 设(LP)的任一基本解为x 0，它对应于基B ，并作(w 0 )T = c B T B –1。

若x 0 和w 0 分别是(LP)和（DP ）的可行解，则x 0 和w 0 也分别是(LP)和（DP ）的最优解。

证明 因w 0 是（DP ）的可行解，即 (w 0 )T A ≤ c T从而有 c B T B –1A - c T ≤ 0 此式说明，x 0是对应于基B 的基本可行解，且所有的检验数λj ≤ 0故x 0是（LP ）的最优解。

此外，还有(w 0 )T b = c B T B –1 b = c B T x B 0 = c x 0从而由线性规划的对偶定理知，w 0 也是（DP ）的最优解。

证毕。

由以上证明过程可看到：x 0（（LP ）的任一基本解）的检验数全部非正与(w 0 )T = c B T B –1是对偶问题（DP ）的可行解等价。

据此我们可对单纯形法作如下解释：从一个基本解x 0出发迭代到另一个基本解，在迭代过程中始终保持解的可行性（基本可行解），同时使它所对应的对偶规划的解w 0（满足（w 0 ）T = c B T B –1 ）的不可行性逐步消失（即检验数逐步变为非正）；直到w 0是（DP ）的可行解，x 0就是（LP ）的最优解。

因（LP ）和（DP ）互为对偶问题，故基于对称的想法，我们也可以把迭代过程建立在满足对偶问题（DP ）的可行解上，即在迭代过程中保持对应的对偶问题的解w 0的可行性（从而x 0的检验数全部非正），逐步消除原问题（LP ）的基本解x 0的不可行性（即使x 0非负），最后达到双方同时为可行解，x 0和w 0也就同时为最优解了。

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

0 1 0 0 1 0 1 -1 1 1 300 400 250 = 50 50 250
b'= B-1 b=
-2 0
σj= Cj-CBB-1 P j
CB CB 0 0 0 XB x3 x4 x5 j CB CB 50 0 XB x1 x4 b b
50 x1 1 2 0
50
100 x2 1 1 1
怎么样 简单吧
对称型线性规划问题
2、非对称型对偶问题
表 对偶变换的规则
好难记呀！
原问题(max,) 技术系数矩阵 A 价值系数 C 右端项 b 第 i 行约束条件为 型 第 i 行约束条件为 型 第 i 行约束条件为 = 型 决策变量 xj 0 决策变量 xj 0 决策变量 xj 不限
最 终 3/5 -3/10 1/10 3/10 -1/10 单 纯 -2/5 1/5 -2/5 -1/5 2/5 形 表 0 -1/2 -1/2 ½-M ½-M 格
x3
x4
x5
x6
x7
例5：对称形线性规划问题：
maxZ=50x1+100x2+0x3 +0x4 +0x5 maxZ=50x1+100x2 x1 +x2 ≤300 x1 +x2 +x3 =300
XS
b
B CB
检验数j
当迭代若干步，基变量为X B时，新的单纯形表: Cj
CB XB CB CN XN B-1N CN- CB B-1N 0 XS B-1 - CB B-1
XB
B-1b
I 0
检验数j
举例
maxZ=3x1 +5 x2 +0x3 +0x4+0x5 =0 x1 + x3 =8 2x2 + x4 =12 3x1 +4 x2 + x5=36

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

单纯形法的灵敏度分析与 线性规划对偶理论
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

《管理运筹学》第三版习题答案(韩伯棠教授)

第 2 章 线性规划的图解法11a.可行域为 OABC 。

b.等值线为图中虚线所示。

12c.由图可知，最优解为 B 点，最优解： x 1 = 769 。

7 2、解：15 x 2 =7， 最优目标函数值：a x 210.60.1O1有唯一解 x 1 = 0.2 函数值为 3.6 x 2 = 0.6 b 无可行解 c 无界解 d 无可行解 e 无穷多解1 2 2 1 2f 有唯一解20 x 1 =3 8函数值为 92 33、解：a 标准形式：b 标准形式：c 标准形式：x 2 =3max fmax f= 3x 1 + 2 x 2 + 0s 1 + 0s 2 + 0s 3 9 x 1 + 2x 2 + s 1 = 30 3x 1 + 2 x 2 + s 2 = 13 2 x 1 + 2x 2 + s 3 = 9x 1 , x 2 , s 1 , s 2 , s 3 ≥ 0 = −4 x 1 − 6x 3 − 0s 1 − 0s 2 3x 1 − x 2 − s 1 =6x 1 + 2x 2 + s 2 = 10 7 x 1 − 6 x 2 = 4 x 1 , x 2 , s 1 , s 2 ≥max f = −x ' + 2x '− 2 x '' − 0s − 0s' ''− 3x 1 + 5x 2− 5x 2 + s 1 = 702 x ' − 5x ' + 5x '' = 50122 ' ' '' 3x 1 + 2 x 2 − 2x 2− s 2 = 30' ' ''4 、解：x 1, x 2, x 2, s 1 , s 2 ≥ 0标准形式： max z = 10 x 1 + 5x 2 + 0s 1 + 0s 23x 1 + 4 x 2 + s 1 = 9 5x 1 + 2 x 2 + s 2 = 8 x 1 , x 2 , s 1 , s 2 ≥ 0s 1 = 2, s 2 = 0标准形式： min f = 11x 1 + 8x 2 + 0s 1 + 0s 2 + 0s 310 x 1 + 2x 2 − s 1 = 20 3x 1 + 3x 2 − s 2 = 18 4 x 1 + 9x 2 − s 3 = 36x 1 , x 2 , s 1 , s 2 , s 3 ≥ 0s 1 = 0, s 2 = 0, s 3 = 136 、解：b 1 ≤c 1 ≤ 3c 2 ≤ c 2 ≤ 6d x 1 = 6x 2 = 4e x 1 ∈ [4,8]x 2 = 16 − 2x 1f 变化。

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


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

运筹学第8讲：对偶单纯形法及灵敏度分析简介


② 原问题有可行解（b≥0）, 对偶问题无可行解（存在δj>0），采 用单纯形法继续求解
③ 原问题无可行解（存在bi<0）, 对偶问题有可行解（ δ≤0 ）， 采用对偶单纯形法继续求解
④ 原问题无可行解（存在bi<0）, 对偶问题无可行解（存在δj>0）， 设法使bi>0，并引入人工变量，采用大M 法继续求解
P38：例3.6
某公司生产甲、乙、丙、丁四种产品，已知制造单件产品时分
别占用的设备A、B的台时，设备A、B每天可用于生产的能力 以及单件产品的收益情况如下表所示。问该公司应该如何制定 最优生产计划？ 项目 甲 乙 丙 丁 每天可用能力
设备A（h） 设备B（h）
单件利润(元)
3 2
4
2 3
3
1 2
上式两边左乘B-1，得到
题的最优基B不变，我们可以直接 求出新问题的最优解
X B B1b B1NX N
(1)
运筹学
第8讲：对偶单纯形法及灵敏度分析简介
设 Pj
为初始单纯形表中的第j 列列向量，
设 Pj’为最终单纯形表中的第j 列列向量 例如： 3 P 1 2 我们不难得到：
运筹学
第8讲：对偶单纯形法及灵敏度分析简介
同时，
Pj ' B1Pj
(3)
例如：
3 5 2 5 3 1 B P 1 1 2 0 P ' 2 5 3 5
1
再考察式(1)，由于XN＝[0, 0]T，因而
X B * B1b
(2) 解：设乙的收益c2直接反映到原问题的最终单纯形表中，得到
为使最优生产计划不变，则δ3, δ4 ,δ5, δ6 ≤0，得到
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

迭代 基变量 CB X1
次数
50
X1
50 1
S2
00
X2
S1
100 0
01
0 -2
10
100 50
Cj-Zj
0
0 -50
S2
S3
00
0 -1
11
01
0 50
0 -50
b
50 50 250 27500
管理运筹学
5
§1 单纯形表的灵敏度分析
我们先对非基变量S1的目标函数的系数C3进行灵敏度分析。 这里δ3=-50，所以当c3的增量Δc3≤50，最优解不变。 再对基变量x1的目标函数的系数c1进行灵敏度分析。 在a11’,a12’,a13’,a14’,a15’中，除a11’外,系数 a13’大于
= Zj + Ck a’Kj
管理运筹学
3
§1 单纯形表的灵敏度分析
根据上式可知
检验数 j(j=1,2,…..,m)变成了 ’j,有 ’ j=Cj-Z’j= j - CK a’Kj 。要使最优解不变，只要当j
k时， ’j <=0
δ j ΔCka'kj 0, ΔCka'kj δ j
当a'kj 0时, ΔCk
0
-50
S2
S3
0
0
0
-1
1
1
0
1
0
50
0 -50
b
50 50 250 27500
从上表我们可以发现各个松弛变量的Zj值，正好等于相应约束条 件的对偶价格。在最优解中S2 =50是基变量，即为，原料A有50千克没 用完，再增加A原料是不会增加利润的， A的对偶价格为0。对于任何 为基变量的松弛变量所对应的约束条件的对偶价格为0。
那么如果c1’取值超出这个范围，必然存在一个检验数 大于0，我们可以通过迭代来得到新的最优解。
管理运筹学
7
§1 单纯形表的灵敏度分析
二、约束方程中常数项的灵敏度分析
迭代 基变 次数 量
2
X1
S2
X2
Zj
Cj -Zj
CB X1 50
50 1 00 100 0
50
0
X2
S1
100
0
0
1
0
-2
1
0
100 50
，满足ΔCk
δj a'kj
，所有小于0的a'kj
满足ΔCk
δj a'kj
，所以可知ΔCk的变化范围为
Max
δj a'kj
a'kj
0
ΔCk
Min
δj a'kj
a'kj
0
管理运筹学
4
§1 单纯形表的灵敏度分析
例：
目标函数：Max z=50X1+100X2 约束条件：X1+X2≤300
2X1+X2≤400 X2≤250 X1，X2≥0 最优单纯形表如下
0，
a15’小于0，可知
3 a13
50 1
50
，有
max
j a'1 j
a
' 1
j
0 50
。同样有
min
j a'1
j
a
' 1
j
0
50
。这样可以知道当-50≤Δc1≤50时，也就是x1的
目标函数c1’在0≤c1’≤100时最优解不变。
在最终的单纯形表中，用C’1代替原来的C1=50,计算得表
cj
b
xB cB x1
x2
x3
x4
x5
x1
1
30
x5
-1
10
zj
cj-zj
管理运筹学
2
§1 单纯形表的灵敏度分析
一、目标函数中变量Ck系数灵敏度分析
1.在最终的单纯形表里，X k是非基变量
Ck Ck+ Ck ， CB不变，Zk也不变，这时 K’= Ck+ Ck- Zk= K+ Ck。要使原来的最优解仍为最 优解，
管理运筹学
6
§1 单纯形表的灵敏度分析
迭代 基变量 CB
X1
X2
S1
S2
S3
次数
b
50 100
0
0
0
X1
C’1 1
0
1
0
-1
50
S2
0
0
0
-2
1
1
50
2
X2
100 0
1
0
0
1
250
Zj
C’1 100
C’1
0
-C’1+100
Cj -Zj
0
0
- C’1
0
C’1-100
从δ3≤0，得到-c1’≤0,即c1’≥0，并且从δ5≤0，得 到c1’≤100。
这个约束条件的对偶价格就和这个剩余变量的
z
有关了。这将使得最优目
j
标值特别“恶化”而不是改进，故这时约束条件的对偶价格应取z j 值的相反
数- z j。
对于含有等于号的约束条件，其约束条件的对偶价格就和该约束方程
单纯形法的矩阵描述
max Z = CX
max Z = CBXB + CNXN
s.t. AX = b
s.t. B·XB+N·XN=b
X≥0
XB,XN ≥0
则XB=B-1(b-NXN)=B-1b-B-1NXN
代入 Z = CBXB+CNXN
= CB(B-1b-B-1NXN)+CNXN
= CBB-1b+(CN-CBB-1N) XN
管理运筹学
8
§1 单纯形表的灵敏度分析
可以看出，上题中对于设备台时数约束来说，当其松弛变量在目标函数
中从0变到Z3=50时，也就是只要当前余下一台时数设备从不能获利变成获利 50元时，譬如有人愿意出50元买一个设备时，我们就不必为生产Ι、П产品
而使用完所有的设备台时了，这说明了设备台时数的对偶价格就是Z3=50元。 对于含有大于等于号的约束条件，添加剩余变量化为标准型。这时
δj a'kj
,这里 δj a'kj
0;
当a'kj 0时, ΔCk
δj a'kj
,这里 δj a'kj
0;
当j
k时，δ'k
Ck
ΔCk
Zk
'
Ck
ΔCk
Zk
ΔCk
a'kk
,因为X
是基
K
变量，
知δk 0，a'kk 1，可知δ'k 0。
要使得最优解不变，对于除了a'kk
以外的所有大于0的a'kj
只要 K+ Ck≤0即可，也就是Ck的增量 Ck≤ - K
2.在最终的单纯形表中， X k是基变量
当Ck变成Ck+ Ck时，最终单纯形表中约束方程的增广矩阵不变，但是基
变量的目标函数的系数CB变了，则Zj(j=1,2,…..,n)一般也变了，不妨设 CB=(CB1, CB2…, Ck,…， CBm),
令XN=0，则 XB= B-1b Z = CBB-1b
若B-1b ≥0，则 X=(B-1b,0)是一个基本可行解。
管理运筹学
1
单纯形法的矩阵描述
EX：已知线形规划问题：
Max Z = 5x1+2x2+3x3
s.t. x1+5x2+2x3 ≤b1
x1-5x2-6x3 ≤b2
x1,x2,x3 ≥0 对于给定的非负常数b1 ，b2，其最优单纯形表如下， 请完成该表，并求出b1 ，b2。
当CB变成=(CB1, CB2。。。,Ck+ Ck,…,CBm),则：
Zj=(CB1, CB2。。。, Ck,…， CBm)(a’1j , a’2j ,…, a’Kj ,…, a’mj)T Z’j=(CB1, CB2。。。, Ck+Ck,…，CBm)(a’1j , a’2j ,…, a’Kj ,…, a’mj)T