koorio.com
海量文库 文档专家
当前位置:首页 >> 数学 >>

规划数学ch2-3


第三节 对偶规划
一、对偶线性规划问题
?max f = 4 x1 + 3 x2 ? s.t . ? ? ? 2 x1 + 2 x2 ≤ 1600 ? ? 5 x1 + 2.5 x2 ≤ 2500 ? x1 ≤ 400 ? ? ? x1 , x2 ≥ 0
若工厂不打算生产汽车,而想把钢材、工时、座椅 等原材料出售。问应如何定价?

例:继续考虑汽车生产问题:
? m ax f = 4 x 1 + 3 x 2 ? s .t . ? ? ( y1 ) ? 2 x 1 + 2 x 2 ≤ 1600 ? ? 5 x 1 + 2.5 x 2 ≤ 2500 ( y 2) ? x 1 ≤ 400 ( y3 ) ? ? ? x1 , x 2 ≥ 0 称以上两个问题为互为对偶问题.

设每吨钢材的售价: y1 没个工时的售价: y2 每套座椅的售价: y3

?min g = 1600 y1 + 2500 y2 + 400 y3 ? s.t . ? ? ? 2 y1 + 5 x2 + y3 ≥ 4 ? 2y + 2.5 y ≥ 3 1 2 ? ? ? y1 , y2 , y3 ≥ 0

则工厂将生产一辆轿车(货车)所需要的原材料出售出去所得利润 不应小于其自己制造时所获得的利润.

即 : 2 y1 + 5 y2 + y3 ≥ 4 (轿车) 2 y1 + 2.5 y2 ≥ 3 (货车)

y1,y2,y3:称为影子价格 1)是出让资源的最低价格(出售与自己生产利润相同)

就购买方而言,希望购买全部原材料的费用越小越好
P1

2)不是市场价格。当市场价格>影子价格时,出售 原材料;当市场价格<影子价格时,自己生产
P2

2. 一般情形:
例2:

max z = 2 x1 + 3 x 2 ? 2 x1 + 2 x 2 ≤ 12 ? ? x1 + 2 x 2 ≤ 8 ? s .t ?4 x1 ≤ 16 ?4 x ≤ 12 ? 2 ? ? x1 , x 2 ≥ 0
原问题 (对偶问题)

P:
? min ω = 12 y1 + 8 y2 + 16 y3 + 12 y4 ? s.t . 2 y + y + 4 y + 0 y ≥ 2 ? 1 2 3 4 ? 2 y1 + 2 y2 + 0 y3 + 4 y4 ≥ 3 ? ? y1 , y2 , y3 , y4 ≥ 0 ?
对偶问题 (原问题)

max Z = CX ? AX ≤ b s.t . ? ? X ≥0
m个约束,n个变量

D :

min W = Yb ?YA ≥ C s.t ? ? Y ≥0
n个约束,m个变量

? a11 " a1n ? ? x1 ? ? b1 ? ? ? ? ? ? ? A=? # # ?, X = ? # ?,b = ? # ?; ?a ? ? ? ?b ? ? m1 " amn ? ? xn ? ? m? Y = ( y1 ," , ym ) , C = ( c1 ," , cn )
注:原问题若为等式约束AX=b,可等价地写成AX≤b -AX≤-b。则所得对 偶问题中,其决策变量可表示为两类非负变量的差,进而,对偶问题的 决策变量将不受非负约束(自己推导一下该结论)。

P3

P4

线性规划的对偶模型
原问题(或对偶问题) 约束条件右端项 目标函数变量的系数 目标函数 max m个 约 束 ≤ 条 ≥ 件 = n个 变 ≥0 量 ≤0 无约束 对偶问题(或原问题) 目标函数变量的系数 约束条件右端项 目标函数 min m个 变 ≥0 量 ≤0 无约束 n个 ≥ ≤ = 约 束 条 件
P5

例:写出如下线性规划的对偶规划
( y1 )
原问题

( y2 ) ( y3 )

对偶问题

二、对偶定理
性质1 (对称性定理):对偶问题的对偶是原问题。

性质2 弱对偶原理(弱对偶性):设 X 0和 Y 0分别是问题(P)和 (D)的可行解,则必有
CX
0

≤ Y 0b

即:

∑c
j =1

n

j

xj ≤

∑yb
i =1 i

m

i

max Z=C X s.t. AX≤ ≥b X ≥0

min W= Y b s.t. YA ≥ C Y≤0
1× m

推论1: 原问题任一可行解的目标函数值是其对偶问题目标函数值 的下界;反之,对偶问题任意可行解的目标函数值是其原问题目 标函数值的上界。 推论2: 在一对对偶问题(P)和(D)中,若其中一个问题可行但 目标函数无界,则另一个问题无可行解;反之不成立。这也是对 偶问题的无界性。 推论3:在一对对偶问题(P)和(D)中,若一个可行(如P), 而另一个不可行(如D),则该可行的问题目标函数值无界。
P7 P8

m× n n×1 m×1 1× n

A , X, b ,C

Y

性质3 最优性定理:如果 X 0是原问题的可行解, Y 0 是其对偶 问题的可行解,并且:

性质5 互补松弛性:设X0和Y0分别是P问题 和 D问题 的可行 解,则它们分别是最优解的充要条件是:

CX 0 = Y 0 b

即 : z=w

则 X 0是原问题的最优解,Y 0是其对偶问题的最优解。

?Y 0 X s = 0 ? 0 ?Y s X = 0
其中:Xs、Ys为松弛变量

性质4 强对偶性:若原问题及其对偶问题均具有可行解, 则两者均具有最优解,且它们最优解的目标函数值相等。
还可推出另一结论:若(LP)与(DP)都有可行解,则两者都有 最优解,若一个问题无最优解,则另一问题也无最优解。

性质6 检验数定理 原问题单纯形表的检验数行对应于对偶 问题的一个解。且原问题的基变量对应于对偶问题的松弛变 量,原问题的松弛变量对应于对偶问题的基变量。

P9

P10

A = ( B, N ), C = (C B , C N )

max Z=C X
≤b s.t. AX≥

原问题单纯形表中检验数行与对偶问题的对应关系
原问题 检验数 对偶问题

YS = (YS1 , YS2 ), YA ? YS = Y ( B, N ) ? (YS1 , YS2 ) = (YB ? YS1 , YN ? YS2 )

X ≥0
原问题:

XB 0 YS1

XN CBB?1N?CN Y S2

XS CBB?1 Y

min W= Y b s.t. YA ≥ C
2

Y≤0
对偶问题:

当求得原问题一个解,X B = B ?1b.检验数为C B B ?1 N ? C N ,

令Y = C B B ?1 , 则YS 1 = YB ? C B = 0; YS 2 = YN ? C N = C B B ?1 N ? C
P11 P12

? m ax f = 4 x 1 + 3 x 2 ? s .t . ? ? ( y1 ) ? 2 x 1 + 2 x 2 ≤ 1600 ? ? 5 x 1 + 2.5 x 2 ≤ 2500 ( y 2) ? x ≤ 400 ( y3 ) 1 ? ? ? x1 , x 2 ≥ 0

?max f = 4 x1 + 3 x2 ? s.t. ? ? ? 2 x1 + 2 x2 + x3 = 1600 ? ? 5 x1 + 2.5 x2 + x4 = 2500 ? x1 + x5 = 400 ? ? ? x1 , x2 , x3 , x4 , x5 ≥ 0

?max f = 4 x1 + 3 x2 ? s.t . ? ? 2 x1 + 2 x2 + x3 = 1600 ? ? ? 5 x1 + 2.5 x2 + x4 = 2500 ? x1 + x5 = 400 ? ? ? x1 , x2 , x3 , x4 , x5 ≥ 0

?max(? g ) = ?1600 y1 ? 2500 y2 ? 400 y3 ? s.t . ? ? ? - 2 y1 ? 5 y2 ? y3 + y4 = ?4 ? - 2 y ? 2.5 y + y = ?3 1 2 5 ? ? y1 , y2 , y3 , y3 , y4 ≥ 0 ?

? min g = 1600 y1 + 2500 y2 + 400 y3 ? s.t . ? ? ? 2 y1 + 5 x2 + y3 ≥ 4 ? 2y + 2.5 y ≥ 3 1 2 ? ? y1 , y2 , y3 ≥ 0 ?

? max(? g ) = ?1600 y1 ? 2500 y2 ? 400 y3 ? s.t . ? ? ? - 2 y1 ? 5 y2 ? y3 ≤ ?4 ? - 2 y ? 2.5 y ≤ ?3 1 2 ? ? y1 , y2 , y3 , y3 , y4 ≥ 0 ?

对偶解:
P13

y1 = 1, y2 = 0.4, y3 = 0; y4 = 0, y5 = 0
P14

三、对偶单纯形法
?

对偶单纯形法的基本步骤:
(1)首先确定换出变量:选择b列负数中绝对值最大的 基变量为换出变量。 (2)确定换入变量:用换出变量那一行具有负数绝对 值的系数分别除同列的检验数,取绝对值最小者所对 应的变量为换入变量。 (3)把换出变量的那一行除以该行的主元素的系数, 使主元为1. (4)进行初等行变换:使主元列除主元外的其它元素 都变成0 。 (5)进行最优解检验:如果所有基本解都非负,则此 解即为最优解;如果基本解中还有负值,则重复(1 )继续迭代,直到所有基变量为非负的数值为止。

在单纯形法中,b列得到原问题的基本可行解 ,而检验数行zj-cj得到对偶问题的基本解。 对偶单纯形法: 保持对偶可行(zj-cj ≥0),原问 题从非可行解开始迭代,使逐步达到基本可行 解,从而使原问题和对偶问题均达到最优解。

?

P15

P16

用对偶单纯形法求解: 例:

对偶单纯形法
max Z ′ = ?9 x1 ? 12 x2 ? 15 x3 = ?10 ??2 x1 ? 2 x2 ? x3 + x4 ??2 x ? 3 x ? x + x5 = ?12 ? 1 2 3 ? + x6 = ?14 ?? x1 ? x2 ? 5 x3 ? ? x1?6 ≥ 0
cj cB 0 0 0
zj zj-cj
P17

m in Z = 9 x1 + 1 2 x 2 + 1 5 x 3 ? 2 x1 + 2 x 2 + x 3 ≥ 1 0 ? ? 2 x1 + 3 x 2 + x 3 ≥ 1 2 ? ? x1 + x 2 + 5 x 3 ≥ 1 4 ? x j ≥ 0 ( j = 1, 2 , 3 ) ?
解:(1)将模型转化为求最大化问题,约束方程化为等 式求出一组基本解,因为对偶问题可行,即全部检验数 非负(求max问题)。

-9 xB x4 x5 x6 x1 -2 -2 -1 0 9

-12 -15 x2 -2 -3 -1 0 12 x3 -1 -1 -5 0 15

0 x4 1 0 0 0

0 x5 0 1 0 0

0 x6 0 0 1 0

b -10 -12 -14 0

θi

(

9 12 15 , , ) ?1 ?1 ?5
P18

cj cB 0 0 -15
zj zj-cj

-9 xB x4 x5 x3 x1 -9/5 -9/5 1/5
-3 6

-12 x2 -9/5 -14/5 1/5
-3 9

-15

0 x4 1 0 0
0 0

0 x5 0 1 0
0 0

0 x6 -1/5 -1/5 -1/5
3 3

x3 0 0 1
-15 0

b -36/5 -46/5 14/5
-42
(

θi

对偶单纯形法
cj -9 xB x1 x2 x3
zj zj-cj

-12 x2 0 1 0 -12 0

-15 x3 0 0 1 -15 0

0 x4 -14/9 1 1/9 1/3 1/3

0 x5 1 -1 0 3 3

0 x6 1/9 0 -2/9 7/3 7/3 b 2 2 2 -72

30 45 15 , , ) ?9 ?14 ?1

cB -9 -12 -15

x1 1 0 0 -9 0

cj cB 0 -12 -15
zj zj-cj

-9 xB x4 x2 x3 x1 -9/14 9/14 1/14
-123/14

-12 -15 x2 0 1 0 x3 0 0 1

0 x4 1 0 0 0 0

0 x5 -9/14 -5/14 1/14 45/14 45/14

0 x6 -1/14 1/14

b -9/7 23/7
(

θi

3/14

-12 -15 0 0

-3/14 15/7 ?9 ?9 ?1 33/14 ? 501 7 33/14

3 45 33 , , )

原问题的最优解为:X*=(2 , 2 , 2 , 0 , 0 , 0),f* =72 其对偶问题的最优解为:Y*= (1/3 , 3 , 7/3),W*= 72
P20

P19

几点说明:
用对偶单纯形法求解线性规划是一种求解方 法,而不是去求对偶问题的最优解。 对偶单纯形法与普通单纯形法的换基顺序不一 样,普通单纯形法是先确定进基变量后确定出 基变量,对偶单纯形法是先确定出基变量后确 定进基变量。

min

Z = 9 x 1 + 12 x 2 + 15 x 3

? 2 x 1 + 2 x 2 + x 3 ≥ 10 ? ? 2 x 1 + 3 x 2 + x 3 ≥ 12 ? ? x 1 + x 2 + 5 x 3 ≥ 14 ? x j ≥ 0 ( j = 1 .2 .3 ) ?

可采用大M法,基于普通单纯形法直接求解上述问题:
max( ? Z ) = ? 9 x1 ? 12 x 2 ? 15 x 3 ? M x 5 ? M x 7 ? M x 9 ? 2 x1 + 2 x 2 + x 3 ? x 4 + x 5 = 10 ? ? 2 x1 + 3 x 2 + x 3 ? x 6 + x 7 = 12 ? ? x1 + x 2 + 5 x 3 ? x 8 + x 9 = 14 ? all x j , x j ≥ 0 ?

但与对偶单纯形法相比,计算会相当麻烦!
P21 P22

练习:
用对偶单纯形法解如下问题:

改写成标准形:
?max(? g ) = ?1600 y1 ? 2500 y2 ? 400 y3 ? s.t . ? ? ? - 2 y1 ? 5 y2 ? y3 + y4 = ?4 ? - 2 y ? 2.5 y + y = ?3 1 2 5 ? ? y y y y y , , , , ≥ ? 1 2 3 3 4 0

?min g = 1600 y1 + 2500 y2 + 400 y3 ? s.t . ? ? ? 2 y1 + 5 x2 + y3 ≥ 4 ? 2y + 2.5 y ≥ 3 1 2 ? ? ≥ y , y , y ? 1 2 3 0

P23

P24


推荐相关:

规划数学ch2-1.pdf

规划数学ch2-1 - 第二章、线性规划 ?线性规划(Linear 线性规划(L


ch2-3利用矩阵运算实现图形的几何变换.pdf

ch2-3利用矩阵运算实现图形的几何变换_数学_自然科学_专业资料。实验2-3利


数据结构与算法(吴跃)ch2-3_图文.ppt

数据结构与算法(吴跃)ch2-3 - 数组 ADT Array { 数据对象:


Ch2-3-2 隐函数导数_图文.ppt

Ch2-3-2 隐函数导数 - 第三节 隐函数和参数方程求导 第二章 一、隐函数


ch2.3 连续型随机变量_图文.ppt

ch2.3 连续型随机变量 - 第二章 第节 连续型随机变量 应用数理学院 第二章 第节 连续型随机变量 连续型随机变量X所有可能取值充满一 个区间, 对这种...


数学建模规划模型讲解_图文.ppt

2、线性规划模型 3、线性规划的性质。 4、线性规划的主要算法。 5、用数学...是20世纪50年代至 60年代,其奠基人应是苏联数学家Cantolovch 和美国 数学家G...


线性规划问题的数学模型_图文.ppt

线性规划问题的数学模型 - 第 1章 第 2章 第 3章 第 4章 第 5章 线性规划问题的数学模型 单纯形方法 对偶线性规划问题 运输问题 整数规划 Linear ...


Ch2章 对偶理论3_图文.ppt

Ch2章 对偶理论3 - Chapter 2 对偶理论 Dual Theory 2.1 线性规划的对偶模型 Dual Model of LP 2.2 对偶性质 Dual property 2...


ch2第二节-表上作业法_图文.ppt

ch2第二节-表上作业法 - §3.2 运输问题求解表上作业法 由于运输问题系数矩阵的特殊性,如果直接使用线 性规划单纯形法求解计算,则无法利用这些有利条 件。...


ch2_3系统传函_图文.ppt

ch2_3系统传函 - 第五讲 第二章-3 序列的傅立叶变换Z变换 1/39 第


数学规划与lingo软件.doc

数学规划与lingo软件 - 数学建模实验(三) 数学规划与 Lingo 软件 专业:14 系统科学 姓名:梅建辉 学号:20141221460 一、实验目的 1.了解非线性规划问题...


离散数学ch7[3]关系的合成_图文.ppt

离散数学ch7[3]关系的合成 - 离散数学 第部分 集合论 关系论3 关系的


数学技巧线性规划_图文.ppt

数学技巧线性规划 - Ch13:合售作介 指老:源教授 M95


数学物理方法姚端正CH2作业解答.pdf

数学物理方法姚端正CH2作业解答_理学_高等教育_教育专区。数学物理方法姚端正第三版答案 数理方法 CH2 作业解答 P33.习题 2.1 3.利用积分不等式,证明 (1) | ...


Ch2.2 数学模型作业解答.doc

数学模型》作业解答 数学模型》第二章(2)(2009 年 3 月 13 日)


贝叶斯统计 ch2贝叶斯推断_图文.ppt

贝叶斯统计 ch2贝叶斯推断 - Made Madeby bycyh cyh 第


ch2回归模型_图文.ppt

ch2回归模型_数学_自然科学_专业资料。计量经济学 ...§2.2 统计检验 Statistical Test §2.3 多元线性...(2)根据一般经济理论和长期规划,对参数事先有一个...


ch2 bayes推断_图文.pdf

ch2 bayes推断 - Ch2 贝叶斯推断 主讲教师:董雪梅 主要内容 ?


小学数学教师个人三年发展规划.doc

小学数学教师个人三年发展规划(2016-2018) 洪秀兰 作为一名青年教师, 没有什么...文档贡献者 chyabing3 贡献于2018-02-19 1/2 相关文档推荐 ...


数学建模作业5数学规划模型---供应与选址的问题.doc

数学建模作业5数学规划模型---供应与选址的问题_数学...('liaoch',x0,A,B,Aeq,beq,vlb,vub) 程序...1 料场 1 料场 2 3 0 2 5 0 3 4 0 4 ...

网站首页 | 网站地图
All rights reserved Powered by 酷我资料网 koorio.com
copyright ©right 2014-2019。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com