数学建模讲义之优化模型
数学建模讲义之
优化模型
数学建模讲义之优化模型
一 引言,最优化方法的发展进程
最优化方法和理论来源于军事, 管理和经济 。
我国古代军事天才孙武所著, 孙子兵法, 成书于公
元前五世纪春秋末期, 是我国也是世界上最古老的
军事理论著作,, 孙子兵法, 十三篇把军事运筹学
的思想, 理论和方法阐述得淋漓尽致, 可谓达到了
神化的地步 。 连外国人也对孙武子倍加赞赏, 1984
年美国军事运筹学会出版专著, System Analysis
and Modeling in Defence》, 书中称孙武子是世
界上第一个军事运筹学的实践家 。
两次世界大战, 尤其是二战中提出的很多均是
最优化问题, 诸如搜索潜艇问题;护航问题;布雷
问题;轰炸问题以及运输问题等等 。 二战中所提到
的军事问题及其解决方法有如下特点:
数学建模讲义之优化模型
数据是实践中的真实数据;解决问题的人员组成是多学科的;
处理问题的方法渗透着物理学的思想 。 第二次世界大战以后最优
化方法的应用由军事问题转入民用问题, 提出了现代管理的理论
和方法, 如计划管理, 运输管理, 工程建设管理, 库存管理, 工
业工程管理等等 。
1930年苏联数学家 Cantolovch首创图上作业法解决小规模
( 以二维为类 ) 得线性规划问题, 如物资调运方案, 合理下了方
案等 。 而大规模的线性规划 ( 高维问题 ) 则是在电子计算机问世
以后才得发展;
1936年美国的经济学家列昂? 夫首创投入产出分析法, 而反
映国民经济动态运行的大型投入产出表的制定也是在大型计算机
的支持下才能够实现;
数学建模讲义之优化模型1935-1940年 Dodge( 道奇 ) 和 Blaket( 白莱盖 ) 首
创统计抽样法, 为此后数理统计学科发展奠定基础 。
二战以后, 科学和工业的蓬勃发展引起了许多新的
变化, 主要表现在:生产规模日益庞大, 生产技术日益
复杂, 商业经营日趋国际化, 环境污染和生态问题日益
严重 。
管理人员和计划人员面临十分复杂的问题, 迫切需
要一种统筹兼顾, 行之有效的科学方法来处理复杂的管
理问题 。 一个最典型的例子即是邮递员问题或旅行商问
题 。
数学建模讲义之优化模型
(一)优化模型的数学描述
下的最大值或最小值,其中
.,.,,,,,)( mih i 210 ??x
.,...,,),)(()( pigg ii 2100 ??? xx
设计变量(决策变量)
目标函数
),.,,,,,( nxxxx 321?x
将一个优化问题用数学式子来描述,即求函数
)( xfu ?
在约束条件
和
x
)(xf
??x 可行域
二 优化模型的一般意义
数学建模讲义之优化模型
.,.,,,,,)(.,mihts i 210 ??x
.,...,,),)(()( pigg ii 2100 ??? xx
??? xxfu )(m a x )m i n (or
tos u b j e c tts,.,受约束于”之意
数学建模讲义之优化模型
(二)优化模型的分类
1.根据是否存在约束条件
有约束问题和无约束问题。
2.根据设计变量的性质
静态问题和动态问题。
3.根据目标函数和约束条件表达式的性质
线性规划,非线性规划,二次规划,多目标规划等。
数学建模讲义之优化模型
( 1)非线性规划
目标函数和约束条件中,至少有一个非线性函数。
.,.,,,,,)(.,mihts i 210 ??x
.,...,,),)(()( pigg ii 2100 ??? xx
??? xxfu )(m i n
数学建模讲义之优化模型
?
?
?
?
?
??
??
?
?
?
?
?
.,.,,,,,
.,.,,,,,
..
m i n
nix
nibxa
ts
xcu
i
n
k
ikik
n
i
ii
210
21
1
1
( 2)线性规划( LP)
目标函数和所有的约束条件都是设计变量
的线性函数。
数学建模讲义之优化模型
( 3)二次规划问题
目标函数为二次函数,约束条件为线性约束
?
?
?
?
?
??
??
???
?
??
?
??
.,.,,,,.
.,.,,,,,
..
)(m i n
,
nix
nibxa
ts
xxbxcxfu
i
n
j
ijij
n
ji
jiij
n
i
ii
210
21
2
1
1
11
数学建模讲义之优化模型
5,根据变量具有确定值还是随机值
确定规划和随机规划。
4,根据设计变量的允许值
整数规划( 0-1规划)和实数规划。
数学建模讲义之优化模型
(三)建立优化模型的一般步骤
1.确定设计变量和目标变量;
2.确定目标函数的表达式;
3.寻找约束条件。
数学建模讲义之优化模型例 1 工厂设址问题( 混合整数规划 )
欲在 m个地方建造规模不同的工厂,并假定这些工
厂生产同一产品 (简化问题起见 ),工厂附近已有 n个零售
商店承销工厂产品。
n
n
m
m
m
bbb
BBB
fff
aaa
AAA
...,
...,
...,
...,
...,
21
21
21
21
21
产品需求量:
零售商店:
建厂费用:
产品数量:
工厂厂址:
设 表示从 运送一件产品到 所需运费,问如
何安排建厂计划(修建哪些工厂),既满足零售需求,
又使得建厂和运输总费用最小。
ijc i
A jB
数学建模讲义之优化模型解:此问题需设立两件决策变量:
表示 运至 的产品数量
该决策变量取非负实数
该决策变量表示一种状态,只能取 0或 1。
目标函数:总费用 S
ijx
iA jB ),1,,1( njmi ??
mi
A
Ay
i
i
i,1 0
1 ?
?
?
??
处建厂不在
处建厂在
? ?
? ?
??
m
i
n
j
ijijii xcyfS
1 1
][
数学建模讲义之优化模型
Model,
鉴于决策变量的性质,称此类线性规划为混合
整数规划
?
?
?
?
?
?
?
?
?
???
??
??
??
?
?
?
?
n1,j,m1,i 0
m1,i 1or 0
m1,i
n1,j
..
m i n
1
1
非负实数
ij
i
ii
n
j
ij
j
m
i
ij
x
y
yax
bx
ts
S
数学建模讲义之优化模型
工厂定期订购原料,存入仓库供生产之用;
车间一次加工出一批零件,供装配线每天生产之用;
商店成批购进各种商品,放在货柜里以备零售;
水库在雨季蓄水,用于旱季的灌溉和发电。
例 2 存贮模型
(四)简单优化模型举例
存贮量多少合适?
存贮量过大,存贮费用太高;存贮量太小,会导致一
次性订购费用增加,或不能及时满足需求。
数学建模讲义之优化模型
问题 1 不允许缺货的存贮模型
配件厂为装配线生产若干种部件,轮换生
产不同的部件时因更换设备要付生产准备费
(与生产数量无关),同一部件的产量大于需
求时因积压资金、占用仓库要付存贮费。今已
知某一部件的日需求量 100件,生产准备费 5000
元,存贮费每日每件 1元。如果生产能力远大于
需求,并且不允许出现缺货,试安排该产品的
生产计划,即多少天生产一次(称为生产周
期),每次产量多少,可使总费用最小。
数学建模讲义之优化模型
问题分析
若每天生产一次,每次 100件,无存贮费,生产
准备费 5000元,每天费用 5000元;
若 10天生产一次,每次 1000件,存贮费
900+800+…+100=4500 元,生产准备费 5000元,
总计 9500元,平均每天费用 950元;
若 50天生产一次,每次 5000件,存贮费
4900+4800+…+100=122500 元,生产准备费 5000
元,总计 127500元,平均每天费用 2550元;
寻找 生产周期、产量、需求量、生产准备费和
存贮费之间的关系,使每天的费用最少。
数学建模讲义之优化模型
模型假设
1 连续化,即设生产周期 T 和产量 Q 均为连续量;
2 产品每日的需求量为常数 r ;
3 每次 生产准备费 C1,每日每件产品存贮费 C2;
4 生产能力为无限大(相对于需求量),当存贮量
降到零时,Q件产品立即生产出来供给需求,即
不允许缺货。
数学建模讲义之优化模型
模型建立
总费用与变量的关系
总费用 =生产准备费 +存贮费
存贮费 =存贮单价 *存贮量
存贮量 =?
数学建模讲义之优化模型
设 t 时刻的存贮量为 q(t), t = 0时生产 Q 件,
存贮量 q(0) = Q,q(t) 以需求速率 r 线性递减,
直至 q(T) = 0,如图。 q(t) = Q- r t,Q = r T 。
o
t
q
Q
T
r
A
不允许缺货模型的存贮量 q(t)
存贮量的计算
数学建模讲义之优化模型
一个周期内存贮量
dttqT?0 )(
一个周期内存贮费
dttqc T?02 )(
2
QT? (A的面积 )
一个周期的总费用
dttqccC T??? 021 )(
22
2
2121
rTccQTcc ????
每天平均费用
22
1 rTc
T
c
T
CTC ???)(
数学建模讲义之优化模型
2 2
1 rTc
T
cTCT ??)(m i n满足求
模型求解
用微分法
02221 ????? rcTcTC )(
rc
cT
2
12?
2
12
c
rcrTQ ??
每天平均最小费用
rccC 212?
著名的 经济订货批量公式( EOQ公式) 。
数学建模讲义之优化模型
结果解释
rc
cT
2
12?
2
12
c
rcrTQ ?? rccC 212?
当准备费 c1 增加时,生产周期和产量都变大;
当存贮费 c2 增加时,生产周期和产量都变小;
当日需求费 r 增加时,生产周期变小而产量变大。
这些定性结果符合常识,而定量关系(平方根,系
数 2 等)凭常识是无法得出的,只能由数学建模得到。
数学建模讲义之优化模型
rc
cT
2
12? rccC 212?
1 0 0 010
10015 0 0 0 21
??
???
CT
rcc
,得
当,,,
这里得到的费用 C与前面计算得 950元有微
小差别,你能解释吗?
在本例中
数学建模讲义之优化模型
敏感性分析
讨论参数 rcc,,
21
有微小变化时对生产周期 T 影响。
由相对变化量衡量对参数的敏感程度。
T 对 c1 的敏感程度记为 ),(
1cTS
11
1 cc
TTcTS
?
??),(
T
c
dc
dT 1
1
? T
c
rc
c
rc
1
2
1
2
2
2
2
1
??
2
1?
2
1
2 ??),( cTS 2
1??),( rTS
数学建模讲义之优化模型
意义是当准备费增加 1%时,生产周期增加 0.5% ;
而存贮费增加 1%时,生产周期减少 0.5% ;
日需求量增加 1%时,生产周期减少 0.5% 。
2
1
1 ?),( cTS 2
1
2 ??),( cTS 2
1??),( rTS
当 rcc,,
21
有微小变化对生产周期影响不太大。
数学建模讲义之优化模型
思考
1 建模中未考虑生产费用(这应是最大一笔费
用),在什么情况下才可以不考虑它?
2 建模时作了“生产能力无限大”的简化假设,
如
果生产能力有限,是大于需求量的一个常数,
如何建模?
数学建模讲义之优化模型
模型假设
1 连续化,即设生产周期 T 和产量 Q 均为连续量;
2 产品每日的需求量为常数 r ;
3 每次 生产准备费 C1,每日每件产品存贮费 C2;
4 生产能力为无限大(相对于需求量),允许缺
货,每天每件产品缺货损失费 C3,但缺货数量需
在下次生产(订货)时补足。
问题 2 允许缺货的存贮模型
数学建模讲义之优化模型
模型建立
总费用 =生产准备费 +存贮费 +缺货损失费
存贮费 =存贮单价 *存贮量
缺货损失费 =缺货单价 *缺货量
存贮量 =?,缺货量 =?
数学建模讲义之优化模型
因存贮量不足造成缺货,因此 q(t) 可取负值,
q(t) 以需求速率 r 线性递减,直至 q(T1) = 0,如
图。 q(t) = Q-r t,Q = r T1 。
o
t
q
Q
T
r
A
允许缺货模型的存贮量 q(t)
R
T1 B
数学建模讲义之优化模型
一个周期内缺货损失费
一个周期内存贮费
dttqc T? 102 )(
2
1
2
QTc?
一个周期的总费用
r
QrTc
r
QccC
22
2
3
2
21
)( ????
每天平均费用
dttqc T
T? 13
)( 2 13 ))(( TTQrTc ???
r
QrTc
2
2
3
)( ??
r
Qc
2
2
2?
rT
QrTc
rT
Qc
T
cQTC
22
2
3
2
2
1 )(),( ????
数学建模讲义之优化模型
满足求 QT,
模型求解
用微分法 令
3
32
2
12
c
cc
rc
cT ????
32
3
2
12
cc
c
c
rcQ
?
???
每天平均最小费用
),( QTCC ???
rT
QrTc
rT
Qc
T
cQTC
22
2
3
2
2
1 )(),(m in ????
0 0 ?
?
??
?
?
Q
QTC
T
QTC ),(,),(
数学建模讲义之优化模型
每个周期的供货量 TrR ??
3
32
2
12
c
cc
rc
crR ???
3
32
c
cc ???
与不允许缺货模型相比较,有
QRQQTT ??? ?????,/,
数学建模讲义之优化模型
QRQQTT ??? ?????,/,
结果解释
QRQQTT ?????? 1,,,? 即允许缺货时,
周期和供货量增加,周期初的存贮量减少。
2)缺货损失费愈大,愈小,愈接近,
愈接近 。
1)
? T? T RQ,?
Q
3
32
c
cc ???
3),时,当 1
3 ??? ?c QRQQTT ?????,,
不允许缺货模型可视为允许缺货模型的特例。
数学建模讲义之优化模型(例 3)结构优化设计
结构设计的传统工作在于使设计能够安全的承受
所设计的载荷,结构优化设计是对设计准标规范的优
化。以下是结构系统极小重量设计的一个例子 —两杆
桁架的优化设计。(人字架最优设计)
现考虑图 1所示的平面桁架 。 它是由两根钢管构
成, 顶点为两杆的共同端点, 两杆的另两个支点固定,
跨度即是两支点间的距离 2S,要考虑的问题是选择管
的厚度和平均直径以及桁架的高度, 使得在承受 2ω
之下的桁架的总重量为最小 。
数学建模讲义之优化模型解:设该问题的决策变量为:
( 管的平均直径 )
( 管的厚度 )
(桁架的高度 )
则钢管的重量 ( 目标函数 ) 钢管剖面
应为 载荷 2ω
其中 是钢管的密度。 高
跨度
2S
图 1(两杆桁架)
1x
2x
3x
2123221 )(2 xsxx ???
1x
2x
3x
?
数学建模讲义之优化模型
约束条件包括以下四个方面:(主要约束是空间
限制和压力限制)
① 由于空间限制, 桁架高度不应超过 b1,即
② 管的直径同管的厚度之比不应超过 b2,即
③ 钢管的压应力不应超过钢管的屈服压力, 即
,其中 b3是常数
④ 桁架的高度, 管的直径和厚度的选取必须使得
在该载荷下不发生弯曲, 即压应力不超过临界压力
,其中 b4为常数
13 bx ?
221 bxx ?
321321232 )( xxxbxsW ??
)()( 222131421232 xxxxbxsW ???
数学建模讲义之优化模型综上所述,该桁架的优化设计问题可表达为下述
非线性规划:
?
?
?
?
?
?
?
?
?
??
????
???
??
??
)3,2,1(0
0)()(
0)(
0
0
..
2
2
2
1314
212
3
2
3213
212
3
2
221
13
ix
xxxxbxsW
xxxbxsW
xbx
bx
TS
i
2123221 )(m in xsxx ?
数学建模讲义之优化模型
其他费用,450元 /千吨
? 应如何分配水库供水量,公司才能获利最多?
? 若水库供水量都提高一倍,公司利润可增加到多少?
元 /千吨 甲 乙 丙 丁
A 160 130 220 170
B 140 130 190 150
C 190 200 230 /
引水管理费
例 4自来水输送
收入,900元 /千吨
支出
A,50
B,60
C,50
甲,30; 50
乙,70; 70
丙,10; 20
丁,10; 40
水
库
供
水
量(
千
吨)
小
区
基
本
用
水
量(
千
吨)
小
区
额
外
用
水
量(
千
吨)(以天计)
数学建模讲义之优化模型
总供水量,160
确定送水方案 使利润最大
问题
分析
A,50
B,60
C,50
甲,30; 50
乙,70; 70
丙,10; 20
丁,10; 40
< 总需求量,120+180=300
总收入 900?160=144,000(元 ) 收入,900元 /千吨
其他费用,450元 /千吨
支出 引水管理费
其他 支出 450?160=72,000(元 )
使引水管理费最小
数学建模讲义之优化模型
供应
限制
约束
条件
需求
限制
线性
规划
模型
(LP)
5014131211 ???? xxxx
50
60
333231
24232221
???
????
xxx
xxxx
8030 312111 ???? xxx
14070 322212 ???? xxx
3010 332313 ???? xxx
5010 2414 ??? xx
目标
函数
33323124232221
14131211
230200190150190130140
170220130160
xxxxxxx
xxxxZM i n
???????
????
水库 i 向 j 区的日供水量为 xij( x34=0)决策变量
模型建立 确定 3个水库向 4个小区的供水量
数学建模讲义之优化模型
模型求解 OBJECTIVE FUNCTION VALUE
1) 24400.00
VARIABLE VALUE REDUCED COST
X11 0.000000 30.000000
X12 50.000000 0.000000
X13 0.000000 50.000000
X14 0.000000 20.000000
X21 0.000000 10.000000
X22 50.000000 0.000000
X23 0.000000 20.000000
X24 10.000000 0.000000
X31 40.000000 0.000000
X32 0.000000 10.000000
X33 10.000000 0.000000
利润 =总收入 -其它费
用 - 引 水 管 理 费
=144000-72000-24400
= 47600( 元 )
A(50)
B(60)
C(50)
甲 (30;50)
乙 (70;70)
丙 (10;20)
丁 (10;40)
50
50 40
10
10
引水管理费 24400(元 )
数学建模讲义之优化模型
目标
函数
总供水量 (320) > 总需求量 (300)
每个水库最大供水量都提高一倍
利润 = 收入 (900) –其它费用 (450) –引水管理费
利润 (元 /千吨 ) 甲 乙 丙 丁
A 290 320 230 280
B 310 320 260 300
C 260 250 220 /
33323124232221
14131211
2 2 02 5 02 6 03 0 02 6 03 2 03 1 0
2 8 02 3 03 2 02 9 0
xxxxxxx
xxxxZM a x
???????
????
供应
限制 B,C 类似处理 50:A 14131211 ???? xxxx
10014131211 ???? xxxx
问题讨论
确定送水方案 使利润最大
需求约束可以不变
数学建模讲义之优化模型
求解 OBJECTIVE FUNCTION VALUE
1) 88700.00
VARIABLE VALUE REDUCED COST
X11 0.000000 20.000000
X12 100.000000 0.000000
X13 0.000000 40.000000
X14 0.000000 20.000000
X21 30.000000 0.000000
X22 40.000000 0.000000
X23 0.000000 10.000000
X24 50.000000 0.000000
X31 50.000000 0.000000
X32 0.000000 20.000000
X33 30.000000 0.000000
这类问题一般称为
“运输问题”
(Transportation
Problem)
总利润 88700( 元 )
A(100)
B(120)
C(100)
甲 (30;50)
乙 (70;70)
丙 (10;20)
丁 (10;40)
40
100
50 30
50
30
数学建模讲义之
优化模型
数学建模讲义之优化模型
一 引言,最优化方法的发展进程
最优化方法和理论来源于军事, 管理和经济 。
我国古代军事天才孙武所著, 孙子兵法, 成书于公
元前五世纪春秋末期, 是我国也是世界上最古老的
军事理论著作,, 孙子兵法, 十三篇把军事运筹学
的思想, 理论和方法阐述得淋漓尽致, 可谓达到了
神化的地步 。 连外国人也对孙武子倍加赞赏, 1984
年美国军事运筹学会出版专著, System Analysis
and Modeling in Defence》, 书中称孙武子是世
界上第一个军事运筹学的实践家 。
两次世界大战, 尤其是二战中提出的很多均是
最优化问题, 诸如搜索潜艇问题;护航问题;布雷
问题;轰炸问题以及运输问题等等 。 二战中所提到
的军事问题及其解决方法有如下特点:
数学建模讲义之优化模型
数据是实践中的真实数据;解决问题的人员组成是多学科的;
处理问题的方法渗透着物理学的思想 。 第二次世界大战以后最优
化方法的应用由军事问题转入民用问题, 提出了现代管理的理论
和方法, 如计划管理, 运输管理, 工程建设管理, 库存管理, 工
业工程管理等等 。
1930年苏联数学家 Cantolovch首创图上作业法解决小规模
( 以二维为类 ) 得线性规划问题, 如物资调运方案, 合理下了方
案等 。 而大规模的线性规划 ( 高维问题 ) 则是在电子计算机问世
以后才得发展;
1936年美国的经济学家列昂? 夫首创投入产出分析法, 而反
映国民经济动态运行的大型投入产出表的制定也是在大型计算机
的支持下才能够实现;
数学建模讲义之优化模型1935-1940年 Dodge( 道奇 ) 和 Blaket( 白莱盖 ) 首
创统计抽样法, 为此后数理统计学科发展奠定基础 。
二战以后, 科学和工业的蓬勃发展引起了许多新的
变化, 主要表现在:生产规模日益庞大, 生产技术日益
复杂, 商业经营日趋国际化, 环境污染和生态问题日益
严重 。
管理人员和计划人员面临十分复杂的问题, 迫切需
要一种统筹兼顾, 行之有效的科学方法来处理复杂的管
理问题 。 一个最典型的例子即是邮递员问题或旅行商问
题 。
数学建模讲义之优化模型
(一)优化模型的数学描述
下的最大值或最小值,其中
.,.,,,,,)( mih i 210 ??x
.,...,,),)(()( pigg ii 2100 ??? xx
设计变量(决策变量)
目标函数
),.,,,,,( nxxxx 321?x
将一个优化问题用数学式子来描述,即求函数
)( xfu ?
在约束条件
和
x
)(xf
??x 可行域
二 优化模型的一般意义
数学建模讲义之优化模型
.,.,,,,,)(.,mihts i 210 ??x
.,...,,),)(()( pigg ii 2100 ??? xx
??? xxfu )(m a x )m i n (or
tos u b j e c tts,.,受约束于”之意
数学建模讲义之优化模型
(二)优化模型的分类
1.根据是否存在约束条件
有约束问题和无约束问题。
2.根据设计变量的性质
静态问题和动态问题。
3.根据目标函数和约束条件表达式的性质
线性规划,非线性规划,二次规划,多目标规划等。
数学建模讲义之优化模型
( 1)非线性规划
目标函数和约束条件中,至少有一个非线性函数。
.,.,,,,,)(.,mihts i 210 ??x
.,...,,),)(()( pigg ii 2100 ??? xx
??? xxfu )(m i n
数学建模讲义之优化模型
?
?
?
?
?
??
??
?
?
?
?
?
.,.,,,,,
.,.,,,,,
..
m i n
nix
nibxa
ts
xcu
i
n
k
ikik
n
i
ii
210
21
1
1
( 2)线性规划( LP)
目标函数和所有的约束条件都是设计变量
的线性函数。
数学建模讲义之优化模型
( 3)二次规划问题
目标函数为二次函数,约束条件为线性约束
?
?
?
?
?
??
??
???
?
??
?
??
.,.,,,,.
.,.,,,,,
..
)(m i n
,
nix
nibxa
ts
xxbxcxfu
i
n
j
ijij
n
ji
jiij
n
i
ii
210
21
2
1
1
11
数学建模讲义之优化模型
5,根据变量具有确定值还是随机值
确定规划和随机规划。
4,根据设计变量的允许值
整数规划( 0-1规划)和实数规划。
数学建模讲义之优化模型
(三)建立优化模型的一般步骤
1.确定设计变量和目标变量;
2.确定目标函数的表达式;
3.寻找约束条件。
数学建模讲义之优化模型例 1 工厂设址问题( 混合整数规划 )
欲在 m个地方建造规模不同的工厂,并假定这些工
厂生产同一产品 (简化问题起见 ),工厂附近已有 n个零售
商店承销工厂产品。
n
n
m
m
m
bbb
BBB
fff
aaa
AAA
...,
...,
...,
...,
...,
21
21
21
21
21
产品需求量:
零售商店:
建厂费用:
产品数量:
工厂厂址:
设 表示从 运送一件产品到 所需运费,问如
何安排建厂计划(修建哪些工厂),既满足零售需求,
又使得建厂和运输总费用最小。
ijc i
A jB
数学建模讲义之优化模型解:此问题需设立两件决策变量:
表示 运至 的产品数量
该决策变量取非负实数
该决策变量表示一种状态,只能取 0或 1。
目标函数:总费用 S
ijx
iA jB ),1,,1( njmi ??
mi
A
Ay
i
i
i,1 0
1 ?
?
?
??
处建厂不在
处建厂在
? ?
? ?
??
m
i
n
j
ijijii xcyfS
1 1
][
数学建模讲义之优化模型
Model,
鉴于决策变量的性质,称此类线性规划为混合
整数规划
?
?
?
?
?
?
?
?
?
???
??
??
??
?
?
?
?
n1,j,m1,i 0
m1,i 1or 0
m1,i
n1,j
..
m i n
1
1
非负实数
ij
i
ii
n
j
ij
j
m
i
ij
x
y
yax
bx
ts
S
数学建模讲义之优化模型
工厂定期订购原料,存入仓库供生产之用;
车间一次加工出一批零件,供装配线每天生产之用;
商店成批购进各种商品,放在货柜里以备零售;
水库在雨季蓄水,用于旱季的灌溉和发电。
例 2 存贮模型
(四)简单优化模型举例
存贮量多少合适?
存贮量过大,存贮费用太高;存贮量太小,会导致一
次性订购费用增加,或不能及时满足需求。
数学建模讲义之优化模型
问题 1 不允许缺货的存贮模型
配件厂为装配线生产若干种部件,轮换生
产不同的部件时因更换设备要付生产准备费
(与生产数量无关),同一部件的产量大于需
求时因积压资金、占用仓库要付存贮费。今已
知某一部件的日需求量 100件,生产准备费 5000
元,存贮费每日每件 1元。如果生产能力远大于
需求,并且不允许出现缺货,试安排该产品的
生产计划,即多少天生产一次(称为生产周
期),每次产量多少,可使总费用最小。
数学建模讲义之优化模型
问题分析
若每天生产一次,每次 100件,无存贮费,生产
准备费 5000元,每天费用 5000元;
若 10天生产一次,每次 1000件,存贮费
900+800+…+100=4500 元,生产准备费 5000元,
总计 9500元,平均每天费用 950元;
若 50天生产一次,每次 5000件,存贮费
4900+4800+…+100=122500 元,生产准备费 5000
元,总计 127500元,平均每天费用 2550元;
寻找 生产周期、产量、需求量、生产准备费和
存贮费之间的关系,使每天的费用最少。
数学建模讲义之优化模型
模型假设
1 连续化,即设生产周期 T 和产量 Q 均为连续量;
2 产品每日的需求量为常数 r ;
3 每次 生产准备费 C1,每日每件产品存贮费 C2;
4 生产能力为无限大(相对于需求量),当存贮量
降到零时,Q件产品立即生产出来供给需求,即
不允许缺货。
数学建模讲义之优化模型
模型建立
总费用与变量的关系
总费用 =生产准备费 +存贮费
存贮费 =存贮单价 *存贮量
存贮量 =?
数学建模讲义之优化模型
设 t 时刻的存贮量为 q(t), t = 0时生产 Q 件,
存贮量 q(0) = Q,q(t) 以需求速率 r 线性递减,
直至 q(T) = 0,如图。 q(t) = Q- r t,Q = r T 。
o
t
q
Q
T
r
A
不允许缺货模型的存贮量 q(t)
存贮量的计算
数学建模讲义之优化模型
一个周期内存贮量
dttqT?0 )(
一个周期内存贮费
dttqc T?02 )(
2
QT? (A的面积 )
一个周期的总费用
dttqccC T??? 021 )(
22
2
2121
rTccQTcc ????
每天平均费用
22
1 rTc
T
c
T
CTC ???)(
数学建模讲义之优化模型
2 2
1 rTc
T
cTCT ??)(m i n满足求
模型求解
用微分法
02221 ????? rcTcTC )(
rc
cT
2
12?
2
12
c
rcrTQ ??
每天平均最小费用
rccC 212?
著名的 经济订货批量公式( EOQ公式) 。
数学建模讲义之优化模型
结果解释
rc
cT
2
12?
2
12
c
rcrTQ ?? rccC 212?
当准备费 c1 增加时,生产周期和产量都变大;
当存贮费 c2 增加时,生产周期和产量都变小;
当日需求费 r 增加时,生产周期变小而产量变大。
这些定性结果符合常识,而定量关系(平方根,系
数 2 等)凭常识是无法得出的,只能由数学建模得到。
数学建模讲义之优化模型
rc
cT
2
12? rccC 212?
1 0 0 010
10015 0 0 0 21
??
???
CT
rcc
,得
当,,,
这里得到的费用 C与前面计算得 950元有微
小差别,你能解释吗?
在本例中
数学建模讲义之优化模型
敏感性分析
讨论参数 rcc,,
21
有微小变化时对生产周期 T 影响。
由相对变化量衡量对参数的敏感程度。
T 对 c1 的敏感程度记为 ),(
1cTS
11
1 cc
TTcTS
?
??),(
T
c
dc
dT 1
1
? T
c
rc
c
rc
1
2
1
2
2
2
2
1
??
2
1?
2
1
2 ??),( cTS 2
1??),( rTS
数学建模讲义之优化模型
意义是当准备费增加 1%时,生产周期增加 0.5% ;
而存贮费增加 1%时,生产周期减少 0.5% ;
日需求量增加 1%时,生产周期减少 0.5% 。
2
1
1 ?),( cTS 2
1
2 ??),( cTS 2
1??),( rTS
当 rcc,,
21
有微小变化对生产周期影响不太大。
数学建模讲义之优化模型
思考
1 建模中未考虑生产费用(这应是最大一笔费
用),在什么情况下才可以不考虑它?
2 建模时作了“生产能力无限大”的简化假设,
如
果生产能力有限,是大于需求量的一个常数,
如何建模?
数学建模讲义之优化模型
模型假设
1 连续化,即设生产周期 T 和产量 Q 均为连续量;
2 产品每日的需求量为常数 r ;
3 每次 生产准备费 C1,每日每件产品存贮费 C2;
4 生产能力为无限大(相对于需求量),允许缺
货,每天每件产品缺货损失费 C3,但缺货数量需
在下次生产(订货)时补足。
问题 2 允许缺货的存贮模型
数学建模讲义之优化模型
模型建立
总费用 =生产准备费 +存贮费 +缺货损失费
存贮费 =存贮单价 *存贮量
缺货损失费 =缺货单价 *缺货量
存贮量 =?,缺货量 =?
数学建模讲义之优化模型
因存贮量不足造成缺货,因此 q(t) 可取负值,
q(t) 以需求速率 r 线性递减,直至 q(T1) = 0,如
图。 q(t) = Q-r t,Q = r T1 。
o
t
q
Q
T
r
A
允许缺货模型的存贮量 q(t)
R
T1 B
数学建模讲义之优化模型
一个周期内缺货损失费
一个周期内存贮费
dttqc T? 102 )(
2
1
2
QTc?
一个周期的总费用
r
QrTc
r
QccC
22
2
3
2
21
)( ????
每天平均费用
dttqc T
T? 13
)( 2 13 ))(( TTQrTc ???
r
QrTc
2
2
3
)( ??
r
Qc
2
2
2?
rT
QrTc
rT
Qc
T
cQTC
22
2
3
2
2
1 )(),( ????
数学建模讲义之优化模型
满足求 QT,
模型求解
用微分法 令
3
32
2
12
c
cc
rc
cT ????
32
3
2
12
cc
c
c
rcQ
?
???
每天平均最小费用
),( QTCC ???
rT
QrTc
rT
Qc
T
cQTC
22
2
3
2
2
1 )(),(m in ????
0 0 ?
?
??
?
?
Q
QTC
T
QTC ),(,),(
数学建模讲义之优化模型
每个周期的供货量 TrR ??
3
32
2
12
c
cc
rc
crR ???
3
32
c
cc ???
与不允许缺货模型相比较,有
QRQQTT ??? ?????,/,
数学建模讲义之优化模型
QRQQTT ??? ?????,/,
结果解释
QRQQTT ?????? 1,,,? 即允许缺货时,
周期和供货量增加,周期初的存贮量减少。
2)缺货损失费愈大,愈小,愈接近,
愈接近 。
1)
? T? T RQ,?
Q
3
32
c
cc ???
3),时,当 1
3 ??? ?c QRQQTT ?????,,
不允许缺货模型可视为允许缺货模型的特例。
数学建模讲义之优化模型(例 3)结构优化设计
结构设计的传统工作在于使设计能够安全的承受
所设计的载荷,结构优化设计是对设计准标规范的优
化。以下是结构系统极小重量设计的一个例子 —两杆
桁架的优化设计。(人字架最优设计)
现考虑图 1所示的平面桁架 。 它是由两根钢管构
成, 顶点为两杆的共同端点, 两杆的另两个支点固定,
跨度即是两支点间的距离 2S,要考虑的问题是选择管
的厚度和平均直径以及桁架的高度, 使得在承受 2ω
之下的桁架的总重量为最小 。
数学建模讲义之优化模型解:设该问题的决策变量为:
( 管的平均直径 )
( 管的厚度 )
(桁架的高度 )
则钢管的重量 ( 目标函数 ) 钢管剖面
应为 载荷 2ω
其中 是钢管的密度。 高
跨度
2S
图 1(两杆桁架)
1x
2x
3x
2123221 )(2 xsxx ???
1x
2x
3x
?
数学建模讲义之优化模型
约束条件包括以下四个方面:(主要约束是空间
限制和压力限制)
① 由于空间限制, 桁架高度不应超过 b1,即
② 管的直径同管的厚度之比不应超过 b2,即
③ 钢管的压应力不应超过钢管的屈服压力, 即
,其中 b3是常数
④ 桁架的高度, 管的直径和厚度的选取必须使得
在该载荷下不发生弯曲, 即压应力不超过临界压力
,其中 b4为常数
13 bx ?
221 bxx ?
321321232 )( xxxbxsW ??
)()( 222131421232 xxxxbxsW ???
数学建模讲义之优化模型综上所述,该桁架的优化设计问题可表达为下述
非线性规划:
?
?
?
?
?
?
?
?
?
??
????
???
??
??
)3,2,1(0
0)()(
0)(
0
0
..
2
2
2
1314
212
3
2
3213
212
3
2
221
13
ix
xxxxbxsW
xxxbxsW
xbx
bx
TS
i
2123221 )(m in xsxx ?
数学建模讲义之优化模型
其他费用,450元 /千吨
? 应如何分配水库供水量,公司才能获利最多?
? 若水库供水量都提高一倍,公司利润可增加到多少?
元 /千吨 甲 乙 丙 丁
A 160 130 220 170
B 140 130 190 150
C 190 200 230 /
引水管理费
例 4自来水输送
收入,900元 /千吨
支出
A,50
B,60
C,50
甲,30; 50
乙,70; 70
丙,10; 20
丁,10; 40
水
库
供
水
量(
千
吨)
小
区
基
本
用
水
量(
千
吨)
小
区
额
外
用
水
量(
千
吨)(以天计)
数学建模讲义之优化模型
总供水量,160
确定送水方案 使利润最大
问题
分析
A,50
B,60
C,50
甲,30; 50
乙,70; 70
丙,10; 20
丁,10; 40
< 总需求量,120+180=300
总收入 900?160=144,000(元 ) 收入,900元 /千吨
其他费用,450元 /千吨
支出 引水管理费
其他 支出 450?160=72,000(元 )
使引水管理费最小
数学建模讲义之优化模型
供应
限制
约束
条件
需求
限制
线性
规划
模型
(LP)
5014131211 ???? xxxx
50
60
333231
24232221
???
????
xxx
xxxx
8030 312111 ???? xxx
14070 322212 ???? xxx
3010 332313 ???? xxx
5010 2414 ??? xx
目标
函数
33323124232221
14131211
230200190150190130140
170220130160
xxxxxxx
xxxxZM i n
???????
????
水库 i 向 j 区的日供水量为 xij( x34=0)决策变量
模型建立 确定 3个水库向 4个小区的供水量
数学建模讲义之优化模型
模型求解 OBJECTIVE FUNCTION VALUE
1) 24400.00
VARIABLE VALUE REDUCED COST
X11 0.000000 30.000000
X12 50.000000 0.000000
X13 0.000000 50.000000
X14 0.000000 20.000000
X21 0.000000 10.000000
X22 50.000000 0.000000
X23 0.000000 20.000000
X24 10.000000 0.000000
X31 40.000000 0.000000
X32 0.000000 10.000000
X33 10.000000 0.000000
利润 =总收入 -其它费
用 - 引 水 管 理 费
=144000-72000-24400
= 47600( 元 )
A(50)
B(60)
C(50)
甲 (30;50)
乙 (70;70)
丙 (10;20)
丁 (10;40)
50
50 40
10
10
引水管理费 24400(元 )
数学建模讲义之优化模型
目标
函数
总供水量 (320) > 总需求量 (300)
每个水库最大供水量都提高一倍
利润 = 收入 (900) –其它费用 (450) –引水管理费
利润 (元 /千吨 ) 甲 乙 丙 丁
A 290 320 230 280
B 310 320 260 300
C 260 250 220 /
33323124232221
14131211
2 2 02 5 02 6 03 0 02 6 03 2 03 1 0
2 8 02 3 03 2 02 9 0
xxxxxxx
xxxxZM a x
???????
????
供应
限制 B,C 类似处理 50:A 14131211 ???? xxxx
10014131211 ???? xxxx
问题讨论
确定送水方案 使利润最大
需求约束可以不变
数学建模讲义之优化模型
求解 OBJECTIVE FUNCTION VALUE
1) 88700.00
VARIABLE VALUE REDUCED COST
X11 0.000000 20.000000
X12 100.000000 0.000000
X13 0.000000 40.000000
X14 0.000000 20.000000
X21 30.000000 0.000000
X22 40.000000 0.000000
X23 0.000000 10.000000
X24 50.000000 0.000000
X31 50.000000 0.000000
X32 0.000000 20.000000
X33 30.000000 0.000000
这类问题一般称为
“运输问题”
(Transportation
Problem)
总利润 88700( 元 )
A(100)
B(120)
C(100)
甲 (30;50)
乙 (70;70)
丙 (10;20)
丁 (10;40)
40
100
50 30
50
30