当前位置：文档之家 › 2对偶理讲义论与灵敏度分析

2对偶理讲义论与灵敏度分析

  • 格式：ppt
  • 大小：2.09 MB
  • 文档页数：4

下载文档原格式

  / 4

合集下载

对偶理论和灵敏度分析

对偶理论和灵敏度分析
从新的基，基变量开始。
可编辑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

运筹学 第2章对偶问题与灵敏度分析

运筹学 第2章对偶问题与灵敏度分析

可得到
(2) (2) 1 0 a13 a1 m (2) (2) 0 1 a23 a2 m E2 E1 A 0 0 a( 2 ) a( 2 ) m3 mm
14
重复以上的步骤，直到获得
1 1 Em E2 E1 A I 1

18
（4）基变换计算 将新的基 P3 , P4 , P2 单位矩阵。计算：
1 / 2 2 1 / 2 1 P2 0 1 0 ；构造E1 1 0 4 1/ 4 1 / 4 主元素
换入变量
22
确定换出变量
B11b i 1 min B P 0 1 1 1 B P 1 1 i 2 16 3 min , , 2 对应x3 1 4 0


23
由此得到新的基
B2 P 1, P 4, P 2 1 1 B1 P 1 4 0 1 1 0 0 2 4 E2 4 1 0 0 0 0 1 1 0 0 1 0 1/ 2 1 1 B2 E2 B1 4 1 0 0 1 0 0 0 1 0 0 1/ 4 1 0 1/ 2 4 1 2 0 0 1/ 4
1 0 1 / 2 1 0 0, 0 ( 2 ,0,3 ) 4 1 3 0 0 0 0 1 / 4 0 1 2 , 1 / 4 对应 x3 , x5
正检验数 换入变量
27
确定换出变量
1 B2 b i 1 m in B 1P B2 P5 0 2 5 i 2 8 3 m in , , 4 对应x4 1/ 2 2 1/ 4

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

运筹学对偶理论与灵敏度分析
17
（6）（互补松驰性）
若X*、Y*分别是原问题和对偶问题的可行解，则X*、Y*是最优解的充要条件是： Y*XS=0,YSX*=0 (其中XS，YS分别是原问题和对偶问题的松驰变量向量)。
证明：设原问题和对偶问题的标准型是 原问题
对偶问题
max Z CX
s.t.
AX X, Xs
Xs 0
b
CX (0) Y (0)b CX
所以 X是(0最) 优解。
15
（5）（强对偶定理） 若互为对偶问 题之一有最优解，则另一问题必有最优解，且它们的 目标函数X值* 是相原等问题。的最优解，对应基阵B必存在
C CB B1A 0
即得到 Y *A， C其中
Y * CB B 1
若 Y * 是对偶问题的可行解，它使
3x5 2 x4 2x5
3
解：对偶问题为
maxW 2 y1 3y2
x2 3x5 2
x1
x2
2x5
3
化简为
x1 1 x5
x2
2
3x5
y2 3
(1)
y1 y2 4
( 2)
5
y1 y1
y2 2 y2 5
( 3) ( 4)
3y1 2 y2 9
( 5)
y1, y2 0
n
max z c j x j j 1
s.t.
n
aij x j bi ,
j1
i 1, 2,
,m
x
j
0,
j 1, 2, , n
特点：对偶变量符号不限
对偶问题:
m
minW bi yi i 1
s.t.
m
aij yi c j ,
i1

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

第二章 对偶理论和灵敏度分析
经整理得 : min 20 y1 10 y2 5 y3 3 y1 4 y2 y3 4 s.t. 2 y1 3 y2 y3 5 y 0, y 0, y 不限 2 3 1
Slide 12
4 5 5 0
第二章 对偶理论和灵敏度分析
c
CB
CN
x
b XB -Z B-1b -CBB-1b
θ
XB
B-1B 0
XN
B-1N CN－CBB-1 N
二、对偶问题的经济含义
每一个线性规划问题，都存在一个与它密切相关的线性 规划的问题，我们称其中的任一个为原问题，另一个为对 偶问题。任何线性规划问题都有其对偶问题。 对偶思想： 周长一定的矩形,以正方形面积最大 面积一定的矩形,以正方形周长最小 P6 例1.1：MAXZ=3X1+2X2+5X3 S.T. X1+2X2+X3<=430 3X1+2X3<=460 X1+4X2<=420 X1,X2,X3>=0
《运筹学》 第二章 对偶理论和灵敏度分析 Slide 4
设X1、X2、X3分别为生产甲、乙、丙三种产品的产量。 解见P71表1.63。 假如有另外一个工厂要求租用该厂的全部生产能力另做 他用。 那么该厂的厂长应该如何来确定合理的租金（各道工序 的每分钟加工能力的定价）呢? 出租所得的利润应不小于原来用于生产甲、乙、丙三种 产品的利润。 而对于租用生产能力的厂家，考虑的是在尽量满足上述 条件的基础上，总的租用花费最少。 设Y1、Y2、Y3为第一、第二、第三道工序每分钟的租金 。
《运筹学》 第二章 对偶理论和灵敏度分析 Slide 17
五、对偶单纯形法
对偶单纯形法是应用对偶原理求解原问题线性规划的一 种方法，采用的技术是在原问题的单纯形表格上进行对偶处 理。 注意：对偶单纯形法不是求解对偶问题的单纯形法。 对偶单纯形法的基本思想：当一个原始问题从可行但不 最优开始，并继续保持可行直到取得最优解的时候，也就是 它的对偶问题从不可行但比最优还好开始并继续保持最优直 到取得可行最优解。 当原问题在寻找最优性的时候，对偶问题相应地寻找可 行性。P56图1.12

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

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

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 弱对偶性

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

第二章 线性规划问题的对偶理论与灵敏度分析总结一．对偶问题统一归纳表注意：对偶问题允许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 为换出基的变量。

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


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

对偶问题与灵敏度分析

②告诉经营者以怎样的代价去取得紧缺资源。 ③提示设备出租或原材料转让的基价。 ④告诉经营者补给紧缺资源的数量，不要盲目大量补给。 ⑤借助影子价格进行内部核算。
第一讲 对偶理论
解释例1的对偶问题的数学模型
Max Z= 3x1 +5 x2
x1
≤8
S.t.
2x2 ≤12 3x1 +4 x2 ≤36
x1 , x2 ≥0
第一讲 对偶理论
一、对偶问题
• 对原企业而言，它用于出租或转让的资源收益不应 低于自行生产产品所获得的利润，才肯出租或转让。
• 在这个问题上厂长面临着两种选择：自行生产或出 租设备。首先要弄清两个问题：
①如何合理安排生产，取得最大利润? ②为保持利润水平不降低，资源转让的最低价格是多少？
• 问题 ①的最优解：x1=4，x2=6，Z*=42。
(3) 按照θ=Min{j /alj | alj<0 }= k /alk确定xk进基变量。 (4) 以alk为主元素，按单纯形法的方法进行迭代，得到新的表重复
(2).
第一讲 对偶理论
例题：使用对偶单纯形法
• Min W= 8y1+12y2+36y3
y1 + 0y2 + 3y3 ≥ 3 S.t. 0y1 + 2y2 + 4y3 ≥ 5
此时，同时达到最优解
j 1
i 1
Z bi
*

yi*
bi为第i种资源的拥有量
• 说明yi是右端项bi每增加一个单位的第i种资源对目标函数Z的贡献。 • 对偶变量 yi在经济上表示原问题第i种资源的边际价值。
• 对偶变量的值 yi*所表示的第i种资源的边际价值，称为影子价值。

第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的取值应满足:
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
3 -y4 ≤ 2
上述第一类对称形式LP问题的对偶问题为：
Max Z = x1－2x2’ +x3’ －x3’’ x1 －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
x 1 , x 2 , x 3 0
M axZ 7 y1 8 y2 y3
解: 上述LP问题的 对偶问题为：
3 y1 4 y2 y3 3
ST
:
3 y1 4 y1
y2 y2
y3 4 y3 0
y 1 , y 2 , y 3 0
7
三、非对称LP问题的对偶问题
例3 写出下列LP问题的对偶问题
2对偶理论与灵敏度分析
精品jing
第一节 对偶问题的提出
一、引例
材料 甲 乙 丙 丁 单件
产品
收益
A 3 2 1 1 2000 x1
B 4 1 3 2 4000 x2
C 2 2 3 4 3000 x3
限额 600 400 300 200
y1 y2 y3 y4
假设工厂考虑不进行生产而把 全部资源都转让，问如何定价 这些资源，既能使其获利不低 于安排生产所获得的收益，又 能使资源租让具有竞争力。
YA C
S .T .
Y
0
（2）对称LP问题的对偶问题
M axZ CX
(L )
(D )
AX b
S .T .
X
0
M in W Y b
YA C
S .T .
Y
0
4
例1 写出下列LP问题的对偶问题
Max Z =2x1+3x2 s.t. x1+ 2x2≤8
4x1 ≤ 16 4x2≤ 12 x1 ,x2 ≥0
Max Z = 2000x1+4000x2+3000x3
s.t. 3x1+4x2+2x3≤600 2x1+ x2+2x3≤400
x1+3x2+3x3≤300 x1+2x2+4x3≤200
x1, x2, x3≥0
Min W =600y1+400y2+300y3+200y4
s.t. 3y1+2y2+ y3+ y4≥2000
对偶
Min W =8y1+16y2+12y3
s.t. y1+4y2 ≥2
2y1 +4y3 ≥3
y1 ,y2,y3 ≥0
5
（3）对偶问题的对偶是原问题
推导过程
Max Z=CX
( L ) s.t. AX≤b
X≥0
变
形
变形对偶 对偶 ( D )
Min W=Yb
s.t. YA≥C
Y≥0
变
形
Min Z ’= (-C)X
解：用x2= -x2’, x3=x3’-x3’’ 代入上述LP问题，并将其 化为第一类对称形式
x1 －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
Min s.t.
W =2u1+u2+2u3
u1+u2+2u3 ≥1 u1 －u2+ u3 ≤2 －u1+u2+ u3 =1
-y1+y2 -y3 -y4 ≤ 1
u1≥0, u3≤0 ,u2无约束
9
Max Z = x1+2x2+x3
Min W =2u1+u2+2u3
(L)
x1+x2-x3 ≤2
s.t. x1 -x2+x3 = 1 2x1+x2+x3 ≥2
称变量yi为第一个LP的第i个对偶变量， 或第一个LP的第i约束相应的对偶变量
3
二、对偶问题
（1）对称LP问题的定义
第一类对称形式
M axZ CX
AX b
S .T .
X
0
（1）变量为非负； （2）约束条件为不等式。
对于max ，约束为“” ；
对于min，约束为“”
第二类对称形式
M in W Y b
(D)
x1≥0, x2≤0 ,x3无约束
u1+u2+2u3 ≥1
s.t. u1 -u2+ u3 ≤2
-u1+u2+ u3 =1 u1≥0, u3≤0 ,u2无约束
对偶关系：一个问题第i个变量的约束情况决定另一问题 第i个约束不等式的方向，反之亦然。
正常的对正常的，不正常的对不正常的
原问题约束条件是等式对应于对偶问题决策变 量无约束，反之亦然
10
例3 直接写出LP问题的对偶问题
MaxZ x1 2 x2 x3
x1 x2 x3
ST
:
x1 2 x1
x2 x2
x3 x3
2 1 2
x1 0, x 2 0, x 3无 约 束
M in W 2 u 1u 22 u 3 u1u22u3 1
( D D ) s.t. (-A)X≥ (-b)
X≥0
Max W ’= Y(-b)
Max W ’= -Yb
s.t. -YA≤ -C
Y≥0
s.t. Y(-A)≤ (-C)
Y≥0
6
例2 写出下列LP问题的对偶问题
M inW 3 x1 4 x2
3 x1 3 x2 4 x3 7
ST
:
4 x1 x2 x3 8 x1 x2 x3 1
Min W =2y1+y2 －y3－2y4
y1+y2 －y3－2y4 ≥ 1 －y1+y2 －y3 +y4 ≥-2 s.t. －y1+y2 －y3－y4 ≥ 1
y1 －y2+y3 +y4 ≥-1 y1, y2, y3, y4 ≥0
令
u1= y1 u2=y2－y3 u3=－y4
则上述问 题变为：
Max Z = x1+2x2+x3 x1+x2-x3 ≤2
s.t. x1 -x2+x3 = 1 2x1+x2+x3 ≥2 x1≥0, x2≤0 ,x3无约束
x1 -x2+x3 ≤ 1 x1 -x2+x3 ≥ 1
x1 -x2+x3 ≤ 1 -x1 +x2-x3 ≤ - 1
-2x1-x2-x3 ≤ -2 Max Z = x1－2x2’ +x3’ －x3’’
4y1+ y2+3y3+2y4≥4000 2y1+2y2+3y3+4y4≥3000
y1, y2, y3, y4≥0
2
比较上述模型，可以得出两者之间的一些关系：
1. 两个问题，一个是极大化，另一个是极小化； 2. 一个问题的变量数等于另一问题的方程数，反 之亦然； 3. 一个问题的目标函数系数是另一个问题的约束 方程右端常数，反之亦然； 4. 两个问题的约束方程系数矩阵互为转置。