当前位置：文档之家 › 第二章 对偶理论灵敏度分析

第二章 对偶理论灵敏度分析

  • 格式：ppt
  • 大小：3.73 MB
  • 文档页数：44

下载文档原格式

  / 44

合集下载

对偶理论和灵敏度分析

对偶理论和灵敏度分析
从新的基，基变量开始。
可编辑ppt 23
福州大学公共管理学院
计算非基变量的检验数，确定换入变 量。
N1 CN1 CB1B11N1 ( 注意：N1 P1,P5 )
2,
0
(
0,0,3
1 )0
0 1
1/ 21 0 0 4 0
0 0 1/ 4 0 1
2, 3 / 4 对应 x1,x5
换入变量
a( 2) 23
a( 2) m3
a( 2) 2m
a( 2)
mm
可编辑ppt 13
福州大学公共管理学院
重复以上的步骤，直到获得
1
EmE2E1A
1
A1
1
可编辑ppt 14
福州大学公共管理学院
• 求单形法求解线性规划问题：
maxz 2x1 3x2 0x3 0x4 0x5
可编辑ppt
24
福州大学公共管理学院
(3) 确定换出变量
计算：
表示选择>0的元素
min
B11b B11P1
i i
B11P1 0
m
in
2 1
,16,3 4 0
2
对应x 1
可编辑ppt 25
福州大学公共管理学院
B 2 P1 , P4 , P2
主元素
1
1
1 0 0
P1 4
B3 P1 ,P5 ,P2 ;
换入变量x5 的系数向量是
1 0 1 / 2 0 1 / 2
B21P5
4
1
2 0 2 主元素
0 0 1 / 4 1 1 / 4
可编辑ppt 32
福州大学公共管理学院
计算B逆矩阵

运筹学——2对偶理论和灵敏度分析

运筹学——2对偶理论和灵敏度分析

MaxZ x1 2 x2 x3
x1 x2 x3
ST
:

x1 2 x1

x2 x2
x3 x3
2 1 2
x1 0, x2 0, x3无约束
MinW

2u1 u1 u2
u22u23 u3
1
ST
:


u1 u2 u3 u1 u2 u3
Min W =600y1+400y2+300y3+200y4
s.t. 3y1+2y2+ y3+ y4≥2000
4y1+ y2+3y3+2y4≥4000 2y1+2y2+3y3+4y4≥3000

y1, y2, y3, y4≥0
2
二、对偶问题
（1）对称LP问题的定义
第一类对称形式
MaxZ CT X
解：用x2= -x2’, x3=x3’-x3’’ 代入上述LP问题，并将其
Max
Z
= x1
x1-2x2’ +x3’-x3’’ -x2’ -x3’+x3’’ ≤ 2
化为第一类对称形式
x1+x2’+x3’ -x3’’ ≤ 1
s.t. -x1 -x2’ -x3’+x3’’ ≤-1
-2x1+x2’ -x3’+x3’’ ≤-2 x1, x2’, x3’, x3’’ ≥0
Max Z =2x1+3x2 s.t. x1+ 2x2≤8
4x1 ≤ 16 4x2≤ 12 x1 ,x2 ≥0
对偶
Min W =8y1+16y2+12y3

运筹学对偶理论与灵敏度分析

运筹学对偶理论与灵敏度分析
（4）（最优性定理），若X(0)、Y(0)分别是互为对偶问题的可行解，且C X(0) =
Y(0) b，则X(0) 、Y(0)分别是它们的最优解。
（5）（强对偶定理）若互为对偶问题之一有最优解，则另一问题必有最优解 ，且它们的目标函数值相等。
（6）（互补松驰性）若X*、Y*分别是原问题和对偶问题的可行解，则X*、Y* 是最优解的充要条件是：Y*XS=0,YSX*=0 (其中XS，YS分别是原问题和对偶问题的松驰变量向量)。
x4
0
x4
15
x1, x2 , x3 , x4 0
模型二：决策变量： 甲、乙两种产品的数量
max Z 3x1 5x2 2x1 3x2 25
s.tx1 2x2 15 x1, x2 0
X (5, 5)T , Z 40, Y (1,1)
X (5,5, 25,15)T, Z 40, Y (6,11,1,1)
6
对于一般情况下线性规划问题如何写出对偶问题。对于等 式约束可以把它写成两个不等式约束，对于“≥”的不等式，可 以两边同乘“－1”，再根据对称形式的对偶关系写出对偶问题 ，然后进行适当的整理，使式中出现的所有系数与原问题中的 系数相对应。
归纳-----表2.2
7
表2.2
Max 约束条件数=m 第i个约束条件 “≤” “≥” “=”
3
二、对偶理论
1、原问题与对偶问题--对称形式
max Z CX
s.t.
AX X 0
b
minW Yb YA C
s.t.Y 0
(1) 原问题中的约束条件个数等于它的对偶问题中的变量数； (2) 原问题中目标函数的系数是其对偶问题中约束条件的右端项； (3) 约束条件在原问题中为“≤”，则在其对偶问题中为“≥”； (4) 目标函数在原问题中为求最大值，在其对偶问题中则为求最小值

运筹学第二章对偶理论与灵敏度分析

运筹学第二章对偶理论与灵敏度分析

x1
x2
xj
xn 0
减少一件产品可以节省的资源
机会成本a1jy1+ a2jy2+ …… aijyi+ ……amjym
表示减少一件产品所节省的资源可以增加的利润
运筹学第二章对偶理论与灵敏度分析
4、产品的差额成本（Reduced Cost）
机会成本
差额成本
利润
min w b1y1 b2 y2 bm ym
运筹学第二章对偶理论与灵敏度分析
min w=YTb
ATY ≥ CT st.
Y ≥0
1,若原问题目标是求极大化，则对偶问题的目标是 极小化，反之亦然。
特对 点偶
问 题 的
2,原问题的约束系数矩阵与对偶问题的约束系数矩 阵互为转置矩阵。
3,极大化问题的每个约束对应于极小化问题的一个 变量，其每个变量对应于对偶问题的一个约束。
6 y2 + y3 ≥2
题对 偶
St. 5y1 + 2y2 + y3 ≥1
问
y1、y2 、y3 ≥0
最终表
210 0
CB 基 b x1 x2 x3 x4
0 x3 15/2 0 0 1 5/4 2 x1 7/2 1 0 0 1/4 1 x2 3/2 0 1 0 -1/4
cj－zj
0 0 0 -1/4
0 x5 -15/2 -1/2 3/2 -1/2
≤
≥
约束条件
≥
≤
变量
=
无约束
≥
≥
变量
≤
≤
无约束
=
运筹学第二章对偶理论与灵敏度分析
约束条件
§2.2 对偶问题的基本性质
性质1 弱对偶性

第二章线性规划的对偶理论4-灵敏度分析

第二章线性规划的对偶理论4-灵敏度分析

第二章线性规划的对偶理论4-灵敏度分析是指对系统或事物因周围条件变化显示出来的敏感程度的分析。

以前在线性规划问题中，都假定问题中的a ij ，b i ，c j 是已知数。

但实际上这些数往往是一些估计和预测的数据，如c j 随市场条件的改变而改变；a ij 随工艺条件的改变而改变；b i 则是根据资源投入后能产生多大经济效果来决定的一种决策变量。

当这些参数中的一个或几个变化时，问题的最优解会有什么变化，或者这些参数在一个多大的范围内变化时，问题的最优解不变。

这就是灵敏度分析所要研究解决的问题。

第二章对偶理论与灵敏度分析2.4 灵敏度分析C N -C B B -1N -C B B -10c j -z j B -1N B -1I C B X B B -1b X N X s X B非基变量基变量当B 为最优基时，上表检验数行应≤0灵敏度分析的步骤可以归纳如下：1.将参数的改变计算反映到最终单纯形表上来：△b /=B -1△b △P /j =B -1 △P j (c j -z j ) /= c j -∑=*m i iij y a12. 检查原问题是否仍为可行解3. 检查对偶问题是否仍为可行解4. 按下表所列情况得出结论和决定继续计算的步骤原问题对偶问题结论或继续计算的步骤可行解可行解问题的最优解或最优基不变可行解非可行解用单纯形法继续迭代求最优解非可行解可行解用对偶单纯形法继续迭代求最优解非可行解非可行解引进人工变量，编制新的单纯形表重新计算一、分析c的变化j的变化二、分析bi的分析三、增加一个变量xj的变化四、分析参数aij五、增加一个约束条件的分析、分析c j 的变化例：在最初讲的第一个例子中，（1）若甲种产品的利润降至1.5元/件，而乙的利润增至2元/件时，该公司的最优生产计划有何变化；解：(1) 将甲、乙的利润变化直接反映到最终单纯形表中得下表c j1.52000C B基b x 1x 2x 3x 4x 50x 315/20015/4-15/21.5x 17/21001/4-1/22x 23/2010-1/43/2c j -z j 0001/8-9/4[ ]例一c j →21000C B基b x 1x 2x 3x 4x 50x 315051000x 424620100x 5511001c j -z j →210000x 315051002x 1412/601/600x 5102/30-1/61c j -z j →01/30-1/300x 315/20015/4-15/22x 17/21001/4-1/21x 23/2010-1/43/2c j -z j →000-1/4-1/2[ ][ ]最优解为X = (2/7, 2/3, 15/2, 0, 0)T ，代入目标函数得z = 8.5。

第二章 线性规划问题的对偶理论与灵敏度分析总结

第二章 线性规划问题的对偶理论与灵敏度分析总结

第二章 线性规划问题的对偶理论与灵敏度分析总结一．对偶问题统一归纳表注意：对偶问题允许i b 小于0，也正是对于原问题i b 小于0，才引入了后面的对偶单纯形法解决问题。

二．对偶问题的基本性质⎩⎨⎧≥≤=0X ..max 设原问题为b AX t s CXz⎩⎨⎧≥≥=是列向量,0A .. min 对偶问题为TY Y C Y t s Yb TTω1.对称定理：对偶问题的对偶是原问题2.弱对偶性定理：若Y X 和分别是原问题和对偶问题的可行解，则有b TY X C ≤推论（1）max 问题的任一可行解的目标是对偶问题最优目标值的一个下界。

min 问题的任一可行解的目标函数 值是原问题最优目标值的一个上界。

（2）若原问题可行且其目标函数值无界，则对偶问题无可行解。

反之对偶问题可行且其目标函数值无界，则原问题无可行解。

（3）若原问题有可行解而对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而原问题无可行解，则对偶问题目标函数值无界。

3. 最优性定理：若Y X 和分别是原问题和对偶问题的可行解，并且b TY X C =，则X 是原问题最优解，Y 是其对偶问题的最优解4. 强对偶性：若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。

5.互不松弛性：若Y X 和分别是原问题和对偶问题的可行解，则它们分别是最优解的充要条件是：0ˆ,ˆˆ0ˆ1j 1=<=>∑∑==i i nj ij i nj j ij i y b xa b x a y则如果，则如果练习：判断下列说法是否正确：(1) 任何线性规划问题存在并具有惟一的对偶问题；(✓)(2) 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；(✗)(3) 设j ˆx ，i ˆy 分别为标准形式的原问题与对偶问题的可行解，*j x ，*i y 分别为其最优解，则恒有n n m m**j j j j i i i i j 1j 1i 1i 1ˆˆc x c x b y b y ====≤=≤∑∑∑∑；(✓) (5) 已知*i y 为线性规划的对偶问题的最优解，若*i y 0>，说明在最优生产计划中第i 种资源已完全耗尽；(✓) (6) 已知*i y 为线性规划的对偶问题的最优解，若*i y 0=，说明在最优生产计划中第i 种资源一定有剩余；(✗)简析：对(5)、(6)，由互补松弛性质判断，具体详见课本P59三．对偶单纯形法(1). 对偶单纯形法应用前提： 1.检验数行全部非正2.变量取值有负数(2). 对偶单纯形法计算步骤：1.确定换出基变量 取{}i rb min b =，其对应变量r x 为换出基的变量。

第2章对偶理论与灵敏度分析

第2章对偶理论与灵敏度分析

五.互补松弛性（松紧定理）
在线性规划问题的最优解中，如果对应某一约束
条件的对偶变量值为非零，则该约束条件取严格等式；
反之如果约束条件取严格不等式，则其对应的对偶变
量一定为零。也即：
n
若yˆi 0, 则有 aij xˆ j bi ,即xˆsi 0
n
j 1
若 aij xˆ j bi ,即xˆsi 0, 则有yˆi 0
minW=bTy
bT (12 8 16 12 )
y1 y2 y3
4x1 16 4x2 12
x1 x2 0
minW=12y1+8y2 +16y3+12y4
y4
ATy CT
AT 2140
2204
y1
CT
y2 y3
2 3
y4
2y1 +y2 +4y3 2 2y1 +2y2 +y4 3 y1 … y4 0
x (0,5,0)
对于对偶问题的可行解y (5,0)
有 80.
由弱对偶性,最优目标函数值z* *有上.下界。 25 z* * 80
互补松弛定理: 在线性规划问 题的最优解中，
一 . 对称性 ：
对偶问题的对偶是原问题
二. 弱对偶性：
若x′是原问题的可行解，y′是对偶问题的可行 解。则有 cx′≤y′b
弱对偶性的三个推论
推论(1)： 原问题任一可行解的目A标≦函Z数=W值是≦其B对偶
问题目标函数值的下界，反之对偶问题任一可行解的 目标函数值是其原问题目标函数值的上界。
推论(2)： 若原问题（对偶问题）为无界解，则其对 偶问题（原问题）无可行解。注 ： 其逆不成立。
由此y1，y2，y3的取值应满足:

第二章 对偶理论及灵敏度分析

第二章 对偶理论及灵敏度分析
2013-11-13 11
写对偶问题的练习（1）
min z= 2x1+4x2-x3 s.t. 3x1- x2+2x3 ≥ 6 -x1+2x2-3x3 = 12 2x1+x2+2x3 ≤ 8 x1+3x2-x3 ≥ 15 x1≥0 x2≤0 x3: Free
max y=6w1+12w2+8w3+15w4 s.t. 3w1- w2+2w3+ w4≤ 2 -w1+2w2+ w3+3w4 ≥ 4 2w1- 3w2+2w3- w4 = -1 w1 ≥ 0,w2Free 3 ≤ 0,w4 ≥ 0 ,w
2013-11-13 16
当B为最优基时，XB为最优解时，则有： CN-CBB-1N≤0 -CBB-1≤0
∵CB-CBI=0
代入得： CN－CBB-1N+CB-CBI≤0 C－CBB-1(B+N)≤0 整理得： C－CBB-1 A≤0 -CBB-1≤0
令CBB-1为单纯形乘子，Y‘＝CBB-1 则： Y’ A≥C’ C－Y’ A≤0 -Y’≤0 Y’ ≥0 W＝Y’b=CBB-1b=Z 所以当原问题为最优解时，对偶问题为可行解且具有相 2013-11-13 17 同的目标函数值。
2013-11-13
第一种产品 第二种产品
x1 x2
6
原始问题为 min z=2x1+3x2-x3
s.t. x1+2x2+x3≥6
原始问题是极小化问题 原始问题的约束全为≥ 原始问题有3个变量，2个约束 原始问题的变量全部为非负
2x1-3x2+2x3≥9
x1, x2, x3≥0 根据定义，对偶问题为 max y=6y1+9y2 s.t. y1+2y2≤2 2y1- 3y2≤3 y1+2y2≤-1 y1, y2≥0

第08次课--第二章 对偶理论与灵敏度分析

第08次课--第二章 对偶理论与灵敏度分析

24
第二节 改进单纯形法
则
B E
1
1
1 r0 s0
B
1
又已知 B 故只需求
E
1 r0 s0
考虑增广矩阵
( Er0s0 I )
国防科技大学
25
第二节 改进单纯形法
( Er0s0 I )
1 0 0 1 0 0 0 0
26
r i
1
0 0 0
0 0 0
, em

1 B 1 : Er B 1 0 s0
q : ir0 ; ir0 js0 ; js0 q
第二节 改进单纯形法
例 1.11 用改进单纯形法求解以下线性规划问题：
max Z 2 x1 x2 x1 x2 x3 x1 x2 6 x1 2 x2
解：
16
国防科技大学
1
第二节 改进单纯形法
假设已对线性规划模型进行标准化
max Z CX AX b X 0
初始可行基 B 为单位阵，N 是非基变量的系数子矩阵，有:
系数矩阵：
A B, N mn
X B xi1 , xi2 ,
X N x j1 ,
基变量： 非基变量：

, xim
, an 0 ，计算 B b ai1 ,
T
1

, aim

T
xir air r 1, , m x a s 1, , n m 基可行解 X： j j s s
18
国防科技大学
第二节 改进单纯形法
（ 2 ） s 1, 其中
, n m ，计算 j C B B Pj C j ，

第二章对偶理论及灵敏度分析

第二章对偶理论及灵敏度分析
三、非对称形式的原-对偶问题
四、对偶问题的写法
第3页，共68页。
返回本章目录
引言
在实际问题中，一个问题的优化往往可以从不同的 两个角度提出问题。
譬如，要求在有限资源条件下生产利润最大；或在一 定生产能力条件下使资源消耗最少。
所以，在线性规划中，对任一给定的求最大值问题，相 应也存在一个求最小值的问题。且两者包括有相同的数据。
6x3 4
1
x1 x1
x2 x3 x3 , x2 , x3 , x3 0
4
x1x, 1x2,
x2 x3
x3 x3 , x3 0
4
第14页，共68页。
max z x1 4 x2 3 x3 3 x3
2 x1 3 x2 5 x3 5 x3 2
3 x1 x1 x2
m aaay111iin21 nyyyw1110 a aab(1222iyn12 y1yy222 1,b2 2 ,y2 ,aam a mmm)12 nyyymmm bmycccm 12n
(2.4)
第7页，共68页。
矩阵形式表示的原问题与对偶问题
原问题： maxz CX XAX0b (2.5)
4 3 3
5
y
1
6 y 2
y 3
y 3
3
y1 , y 2 , y 3 , y 3 0
min w 2 y1 y 2 4 y 3
2 y1 3 y2 y3 1
3 5
y1 y1
y2 6y
y3 4 2 y3 3
5
y
1
6
y2
y3
3
y1 0 , y 2 0 , y 3无约束
第15页，共68页。
min w 2 y1 y 2 4 y 3

运筹学课件第二章 线性规划的对偶理论与灵敏度分析

运筹学课件第二章 线性规划的对偶理论与灵敏度分析
第二章 线性规划对偶理论与灵敏度分析
第一节 线性规划的对偶问题
一、对偶问题 若例1工厂的决策者不生产产品，有另一企业租赁 其所有资源。厂方为了在谈判时心中有数，需掌握 资源的最低价码，以便衡量对方出价，对出租与否 做出抉择。 在这个问题上厂长面临着两种选择：自行生产或出 租设备。首先要弄清两个问题： ①合理安排生产能取得多大利润? ②为保持利润水平不降低，资源转让的最低价格是
CX Yb
推论1 极大化原问题任意一个可行解的目标函数值 是其对偶问题目标函数值的下界。反之极小化问 题任意一个可行解的目标函数值是其原问题目标 函数值的上界。
推论2 若原问题(对偶问题)具有无界解，则其对偶 问题（原问题）无可行解。
推论3 若原问题(对偶问题)有可行解而其对偶问题 （原问题）无可行解，则其对偶问题（原问题） 目标函数值无界。
我们称这个线性规划问题为例1线性规划问题（我们 称为原问题）的对偶问题。
二、对称形式对偶问题
根据上述例题可见，对于对称形式的线性规划问题 ，
我们可以马上得出它的对偶问题：
Max Z C X
Min w Y 'b
AX b
X
0
A'Y C Y 0
三、非对称形式对偶问题
原问题（对偶问题）
约束条件系数矩阵 约束条件右端项向量 目标函数中价格系数向量
重复步骤2-4。
若 br 0，而对所有j，有aij 0，则原问题无可行解。
第四节 对偶单纯形法
例题：P61
练习题： minω=2x1+3x2+4x3 x1+2x2+ x3 ≥3 2x1– x2+3x3 ≥4 x1 , x2 , x3 ≥0
第五节 灵敏度分析

运筹学第二章 线性规划的对偶理论与灵敏度分析

运筹学第二章 线性规划的对偶理论与灵敏度分析

现在换个角度分析这个问题。假若由于 某种原因，该企业（称为甲方）打算放弃 这些生产项目，而另一家企业（称为乙方）
希望收购这些资源。那么，如何确定三种
资源的转让价格，在自己方不受损失的前
提下、又要乙方愿意接受，使买卖能够成
交？
设三种资源的定价分别为y1，y2，y3 （单位：百元）。对甲方来说，企业甲利用 1吨原料A和5吨原料B，生产一单位甲产品， 收入2百元。转让这些原料的收入不能低于2
对偶问题的特点
•若原问题目标是求极大化，则对偶问 题的目标是极小化，反之亦然 •原问题的约束系数矩阵与对偶问题的 约束系数矩阵互为转置矩阵 •极大化问题的每个约束对应于极小化 问题的一个变量，其每个变量对应于对 偶问题的一个约束。
一 般 线 性 规 划 问 题 的 对 偶 问 题
对偶问题对应表
max z CX AX b X 0
这个性质说明，原问题与对偶问题是 相互对偶的。
定理2（弱对偶定理） 设
X ( x1 , x2 ,, xn )T
与 Y ( y1 , y2 ,, ym ) 分别是（ 2.3）与（2.4） 的可行解，则
C X Yb
。
推论1 极大化问题的任意一个可行解所 对应的目标函数值是其对偶问题最优目标 函数值的一个下界。 推论2 极小化问题的任意一个可行解所对 应的目标函数值是其对偶问题最优目标函 数值的一个上界。
i 1
m
m aij yi c j i 1 y 0 i
j 1,2,, n i 1,2,, m
（2.4）
我们称线性规划（2.4）为线性规划（2.3） 的对偶规划。
写成矩阵形式，原问题
max z CX AX b X 0 它的对偶问题

第二章对偶理论灵敏度分析

第二章对偶理论灵敏度分析

A 工 时 材 料 单件利润
1 1 2
B
1 4 3
C
1 7 3
拥有量 3 9
A 工 时 材 料 单件利润
1 1 2
B
1 4 3
C
1 7 3
拥有量 3 9
max Z 2 x1 3 x2 3 x3
x1 x2 x3 3 s.t. x1 4 x2 7 x3 9 x 0, x 0, x 0 2 3 1
x1 max Z ( 2,3,3) x 2 x 3
y1 min W (3,9) y 2
1 1 2 y1 1 4 3 1 7 y2 3 s.t. y 1 y 0 2
目标函数 minZ 变量数： m个
第i个变量 ≥0 第i个变量 ≤0 第i个变量是自由变量
min W b1 y1 b2 y 2 bm y m
a11 y1 a21 y2 am1 ym c1 a y a y a y c 12 1 22 2 m2 m 2 a y a y a y c mn m n 1n 1 2 n 2 y1 , y2 , , ym 符号不限
其对偶问题为
4 y1 8 y 2 12 y 3 4 5 y 9 y 13 y 2 1 2 3 3 6 y1 10 y 2 y1符号不限, y 2 0, y 3 0
max Z x1 x 2 5 x 3 7 x 4 x1 3 x 2 2 x 3 x 4 25 2x 7x 2 x 4 60 1 3 30 2 x1 2 x 2 4 x 3 5 x 4 10 , x1 , x 2 0 , x 3 没有非负限制

第二章对偶问题与灵敏度分析

第二章对偶问题与灵敏度分析

a22 y2 a23 y2
a32 y3 a33 y3
c2 c3
对 a14 y1 a24 y2 a34 y3 c4
称 y1无符号限制，y2 0，y3 0
原问题（P）
max
型 对偶问题（D）
相
min
变量约束：
似
方程约束：
变量≥
方程≥
变量无限制
方程=
变量≤
方程≤
方程约束：
方程=
方程≤
第二章线性规划的对偶问题
与灵敏度分析
LP
2.1线性规划的对偶问题
存在
一个线性规划
另一个线性规划
同一个研究对象
极值问题
极值问题
2.1.1问题的引入： 生产计划问题
LP
资源价格问题
甲 y1 A 1 y2 B 2
y3 C 1 利润 4
乙 资源量
1
45
1
80
3
90
5
2.1.1.1资源价格问题的数学模型
Max Z（X）=4x1+5x2 x1 + x2 ≤ 45
原问题
Max Z（X）= c1x1+c2x2+…+cnxn
y1
a11x1 + a12x2+…+a1n xn ≤ b1
.y.2. ym
a21x1 + a22x2+…+a2n xn ≤ b2
………………………………………………….
am1x1 + am2x2+…+amn xn ≤ bm
x1，x2，…，xn ≥0
2、求下列问题的对偶问题
变量个数n 约束方程个数m1

第二章对偶理论与灵敏度分析A4

第二章对偶理论与灵敏度分析A4

第二章对偶理论与灵敏度分析A4第二章对偶理论与灵敏度分析本章内容重点：1、线性规划的对偶问题概念、理论及经济意义；2、线性规划的对偶单纯形法；3、线性规划的灵敏度分析。

线性规划有一个有趣的特性，就是每一个LP问题都存在一个与之相应的LP问题，我们称其中任一个为原问题（记为LP），另一个为对偶问题（记为DP）。

线性规划的这个特性称为对偶性。

线性规划有一个有趣的特性，就是每一个LP问题都存在一个与之相应的LP问题，我们称其中任一个为原始问题（记为LP），另一个为对偶问题（记为DP）。

线性规划的这个特性称为对偶性。

研究线性规划的对偶问题，不仅可以获得许多原始问题的知识，还可以得到原始问题不易直接弄清楚的问题，从而有利于原始问题的求解。

在这一章中，我们将从经济意义上研究线性规划的对偶问题，揭示原问题与对偶问题之间的关系，间接地获得更多的有用的信息，为企业经营决策提供更多的科学依据。

§1 线性规划的对偶问题一、 LP对偶问题的提出例1某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。

每件产品在生产中需要占用的设备台时数，每件产品可获得的利润以及三种设备可利用的台时数如下表所示。

求获取利润最大的生产方案。

甲产品乙产品每天设备台时限制设备A0515设备B6224设备C115利润（万元/21吨）这个问题的数学模型与第一章例2类似，设x1, x2分别为产品甲、乙的计划日产量，则有：Max z = 2x1 + x2s.t. 5x2 ≤ 156x1 + 2x2 ≤ 24x1 + x2 ≤ 5x1 , x2 ≥ 0求解得每天最大利润8.5万元。

现在我们从另一个角度来考虑这个问题。

假如有另一个企业要求租用该厂的设备A、B、C，那么该厂的厂长应该如何来确定合理的租金呢？一般来说，有两点需要考虑，一是该厂出租设备要合算；二是要价合理。

所谓合算，就是出租的收入不少于生产利润8.5万元。

而要价合理，就是在合算的前提下，租金要尽量低，这样才能吸引求租者。

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

3/7 0 22/7 4/7 0 6/7 -1 1 -2 -20/7 0 -100/7 1/14 5/14 17/7 3/7 1/7 4/7 1/2 -1/2 1 -9/14 -31/14 -69/7
x2 为进基变量。
(2)
(1,2,0) 1 x3 为基变量， CB (4,2,0) CB c3 4 c3
用单纯形法求新的最优解 cj 2 -1 4 0 x2 x3 x1 x4 CB X B 1 x3 0 5/7 1 1/7 2 x1 1 2/7 0 -1/7 0 x6 0 -2 0 0 j 0 -16/7 0 1/7 0 5 7 1 最 x4 优 x1 1 1 1 0 表 x6 0 -2 0 0 j 0 -3 -1 0
XB
2 x1
-1 x2
4 x3
0 x4
0 x5
0 x6
B 1 b
2 1 1 -10
最 优 表
4 x3 2 x1 0 x6 j
0 1 0 0
5/7 2/7 -2 -31/7
1 0 0 0
1/7 3/7 1 B -1/7 4/7 0 -1 -2/7 -20/7
0 0 1 0
(1)
1 7 3 7 0 10 22 7 B 1b 1 7 4 7 0 4 6 7 0 1 1 2 2 22 7 C B B 1b (4, 2,0) 6 7 100 7 2
2 c 2 C B B 1 P2
5 7 10 0 2 (4, 2, 0) 2 7 7 2
最优解 X (1,0, 2)T 不变
cj
CB
XB
2 x1
-1 x2
4 x3
0 x4
0 x5
0 x6
B 1 b
2 1 1 -10
1
B P2 2 c 2 C B
5 7 1 (1, 2,0) 2 7 2 16 7
B 1 P4 4 c 4 C B
17 0 (1, 2, 0) 1 7 0 1 7
用单纯形法求出最优解：
4
1
3
0
0
0
单 纯 0 x4 形 表 0 x5 一 0 x6
x6
B b
1
4 2 0
j
x3 x1 x6
0 1 0 0
5/7 B1 P2 2/7 -2 -31/7 16 7
1 0 0 0
1/7 3/7B1 P B1 P4 5 -1/7 4/7 0 -1 -2/7 -20/7 1 11 7 7
0 0 1 0
2 1 1 -10 4
(2)
1 x3 为基变量， c3 4 c3
x1
B
1
x2
1
x3
1
7
x4
1
P3
x5
E
b
1
初 始 表 最 优 表
x4
1
1
3
x5 j x1 x2
B
3
3
3
0
3
4
3
0
0
1
0
3
0
b
2
3
1
1 0 0 E 1 0 0
-1 1 4 1-1 B P3 B 2 -1 1 -3 -5 -1
1 1 B b 2
-8
j
最优解： X (1,2,0,0,0)T , Z 8
(1) 5 10 b 3 4 b 4 2 对偶单纯形法求解：
cj
CB
XB
X (1,0, 2)T

Z 10
2 x1 0 1 0 0 0 1 0 0
-1 x2 5/7 2/7 -2 -31/7 0 0 1 0
求出最优解后，分别对以下各 种情况进行灵敏度分析：
5 10 (1) 变右端常数项为：b 3 4 b 4 2 1 (2) 改变目标函数中 x3 的系数 c3 4 c3
2 (3) 改变目标函数中 x2 的系数 c2 1 c2
最 4 x3 优 2 x1 表 0 x6
j
0 1 0 0
5/7 B1 P2 2/7 -2 -31/7
10 0 7
1 0 0 0
1/7 -1/7 0 -2/7
3/7 4/7 -1 -20/7
0 0 1 0
作业2.7 某工厂用原材料甲、乙、丙生产产品A, B, C ，有 关资料如下表所示： A B C 资源
cj
-1 4 0 0 0 x2 x3 x4 x5 x6 b -3 2 4 1 0 0 5 1 1 1 0 1 0 3 1 -1 1 0 0 1 4
4 3 0 最优基：B 1 1 0 1 1 1
2 x1
解：X (1,0, 2)T
cj
CB
Z 10
max S 4 x1 x2 3 x3 2 x1 x2 x3 x4 200 x 2 x 3 x x 500 1 2 3 5 2 x1 2 x2 x3 x6 600 x1 , x2 , x3 , x4 , x5 , 4 b 4 2
cj
-1 4 0 0 0 x2 x3 x4 x5 x6 b -3 2 4 1 0 0 5 1 1 1 0 1 0 3 1 -1 1 0 0 1 4
2 x1
4 3 0 1 1 0 最优基：B 1 1 1
max Z 2 x1 x2 4 x3 3 x1 2 x2 4 x3 5 x x x 3 1 2 3 x1 x2 x3 4 x1 , x2 , x3 0
max Z 2 x1 x2 4 x3 3 x1 2 x2 4 x3 x4 5 x x x x 3 1 2 3 5 x1 x2 x3 x6 4 x1 , x2 , x3 , x4 , x5 , x6 0
第二章 线性规划的对偶理论
2.1
2.2 2.3 2.4
对偶线性规划模型
对偶问题的性质 对偶单纯形法 灵敏度分析与参数分析
第二章 线性规划的对偶理论
2.4 2.4.1 2.4.2 灵敏度分析 价值系数的灵敏度分析 资源限量的灵敏度分析
例：
max Z 2 x1 3 x2 x3 max Z 2 x1 3 x2 x3 1 x 1 x 1 x 1 1 x 1 x 1 x x 1 1 2 3 标准形 3 3 3 3 1 3 2 3 3 4 1 x 4 x 7 x 3 1 x 4 x 7 x x 3 3 1 3 2 3 3 3 1 3 2 3 3 5
2.7 某工厂原材料甲、乙、丙生产产品A,B,C ，有关资 料如下表所示： A B C 资源
(1)怎样安排生产，使利润最大？ 甲 乙 2 1 1 2 1 3 200 500
设A,B,C的产量分别为
x1 , x2 , x3
max S 4 x1 x2 3 x3 2 x1 x2 x3 200 x 2 x 3 x 500 1 2 3 2 x1 2 x2 x3 600 x1 , x2 , x3 0
4
3
1 E 0 P4 P5 0 1 0 0
3
0
b
2
3
1
1 0 0 E 1 0 0
c 3 C B B 1 P3 1 1 (2, 3) 2 3
-1 4 1-1 1 B P3 B 2 -1 1 1 1 -3
B P4
j
-5
B P5
1 1 B b 2
-8 C B B 1 b
B 1 P5 5 c 5 C B
3 7 0 (1, 2, 0) 4 7 1 11 7 2
用单纯形法求新的最优解
cj
CB
XB
2 x1
-1 x2
4 x3
0 x4
0 x5
B 1b (1, 2,0) 1 4 CB 1 0 1
-1
1 c 4 C B B 1 P4 c 5 C B B 1 P5 (2, 3) 4 2 1 0 (2, 3) 0 (2, 3) 8 1 1 5 1
第二章 线性规划的对偶理论
x1 , x2 , x3 0
cj
x1 , x2 , x3 0
x5
0 1 0 p5 0
解：
2
1 1
CB
x1
3
x2
1 4
3
3
x3
1 7
1
3
x4
1
0
j c j CB B1 p j
初 0 始 表 0
x4
b 1
3
x5
j
3 2
3 3
3 1
0 0 p4
A
1 C B 0 B b
p1
p2
p3
cj
CB
XB
2 x1
-1 x2
4 x3
0 x4
0 x5
0 x6
B 1 b
最 优 表
4 x3 0 2 x1 1 0 x6 0 j 0 X (1,0, 2)T Z
5/7 1 1/7 3/7 0 2 22 7 1 6 7 2/7 0 -1/7 B 4/7 0 1 -2 0 0 -1 1 1 2 -31/7 0 -2/7 -20/7 0 -10 100 7 10 基本解不可行，对偶单纯形法求解。