数学建模动态规划docx.docx
《数学建模动态规划docx.docx》由会员分享，可在线阅读，更多相关《数学建模动态规划docx.docx（44页珍藏版）》请在冰点文库上搜索。
数学建模动态规划docx
动态规划
教学内容：
•:
•动态规划问题实例
•动态规划的基本概念与原理
•动态规划应用举例
动态规划是解决多阶段决策过程最优化的一种方法。
该方法是由美国数学家贝尔曼（R.E.Bellman）等人在20世纪50年代初提出的。
他们针对多阶段决策问题的特点，提出了解决这类问题的“最优化原理”，并成功地解决了生产管理、工程技术等方面的许多问题，从而建立了运筹学的一个新的分支，即动态规划。
Bellman在1957年出版了《DynamicProgramming^一书，是动态规划领域中的第一本著作。
动态规划是解决多阶段决策问题的一种方法，是现代企业管理中的一种重要决策方法，可用于最优路径问题、资源分配问题、生产计划和库存问题、投资问题、装载问题、排序问题及生产过程的最优控制等。
动态规划模型的分类：
以“时间”角度可分成：
离散型和连续型。
从信息确定与否可分成：
确定型和随机型。
1从目标函数的个数可分成：
单目标型和多目标型。
多阶段决策过程是指这样一类特殊的活动过程，他们可以按时间顺序分解成若干相互联系的阶段，在每个阶段都要做出决策，全部过程的决策是一个决策序列，所以多阶段决策过程也称为序贯决策过程。
这种问题就称为多阶段决策问题。
二、多阶段决策问题的特点
过程可分为若干个相互联系的阶段；每一阶段都对应着一组可供选择的决策；每一决策的选定即依赖于当前面临的状态，又影响以后总体的效果。
三、具体实例
1＞最短路线冋题
给定一个线路网络，要从A向F铺设一条输油管道，各点间连
线上的数字表示距离，问应选择什么路线，可使总距离最短?
7
Bi
这
7
2、生产与存储问题:
某工厂每月需供应市场一定数量的产品。
供应需求所剩余产品应存入仓库，一般地说，某月适当增加产量可降低生产成本，但超产部分存入仓库会增加库存费用，要确定一个每月的生产计划，在满足需求条件下，使一年的生产与存储费用之和最小。
动态规划的基本概念与原理
动态规划的基本概念
阶段；
状态；
决策和策略；状态转移方程;
指标函数。
rfs怎态规划的基本概念与原理
一。
基本概念
阶段：
是指问题需要做出决策的步数。
阶段总数常记为n,相{应的是n个阶段的决策问题。
阶段的序号常记为k,称为阶段|变量，k二1,2,…,n.k即可以是顺序编号也可以是逆序编号，|常用顺序编号。
|
状态：
各阶段开始时的客观条件，第k阶段的状态常用状态/变量吐表示，状态变量取值的集合成为状态集合，用比{表示。
f
例如，案例仲,Sl={A},S2={Bl,B2}.
是指从某阶段的某个状态出发，在若干个不同方案中做出的选择。
表示决策的变量，称为决策变量，用加（》）表示。
Uk（sj表示第k阶段当状态处于Sk时的决策变量。
）
<例如：
均0=。
表示走到C阶段,当处于C2路口时，下一|步到I决策变量允许的取值范围称为允许决策集合，第k阶段状态为（耳时的允许决策集合记为Dg,例如：
0（BJ={G,C2G}\
（策略：
一个按顺序排列的决策组成的集合。
由每段的决策
按顺序排列组成的决策函数序列{%（◎IM仙）•…6（心
称为k子过程策略。
简称子策略，记为p胡（辅）艮卩
I%ii（$k）={Uk（$k），Uk+l（S}£+l）・.>Un（®n）}
当kh时，此决策函数序列成为全过程的一个策略，简称策略，i己为：
P5⑻）円5（旳），6（曲）…，UMSn）卜
在实际问题中，可供选择的策略有一定的范围，此范围称为允许策略集合，用P表示。
状态转移方程：
是从上一阶段的某一状态值转变为下一阶段
某一状态值的转移规律，用
是指第k阶段从状态Sk出发，采取决策uk时的效益，用坯⑸，务）表示。
而过程指标函数是从第k阶段的某状态岀发,采取子策略卩认脈円％（闕，％］（齡时所得到的阶段效益之和：
VkjiGk.Pkji）=艺卩j（匚，叫）
3丸‘
最优指标函数：
表示从第k阶段状态为》时采用最佳策略
Pk,n（碣到过程终止时的最佳效益。
记为
齐（必）=，pQ=呻叫4
pg
其中opt可根据具体情况取max或min。
基本方程：
此为逐段递推求和的依据，一般为:
fk©k）=opt｛叫（弘绰（必））+£+1（竦⑸））｝£=仏〃一1，・・・21
听$⑸）
Z+iG”+i）=。
式中opt可根据题意取max或min.
例如，案例1的基本方程为：
和决策如何，从眼下直到最后的诸决策必构成最优子策略。
动态规划的优点：
•可把一个N维优化问题化成N个一维优化问题求解。
•函数方程中附加某些约束条件，可使求解更加容易。
•求得最优解以后，可得所有子问题的最优解。
动态规划的缺点：
•“一个”问题，“一个”模型，“一个”求解方法。
且求解技巧要求比较高，没有统一处理方法。
例1最短路线冋题
基本思想：
如果起点A经过而到终点F,则由0出发经到F点这条子路线，是从5到F的最短路线。
所以，寻找最短路线，应该从最后一段开始找，然后往前递推。
决策变量线（吐）:
第k阶段当状态处于吐时，决定下一个状态的位置
状态转移方程绰G）:
上一阶段到下一阶段的转移规则指标函数山侃暫）：
从状态出发，采取决策时的路程距离最优指标函数不凤）:
第k阶段状态为Sk时且釆用最佳走线策略，使从k位置及以后的路线最短。
/6（56）=°
（1）k=5时，状态S5={E^E2}它们到F点的距离即为最短路。
=min{3+4,5+3}=7.
这说明由。
1到尸的最短距离为7,其路径为D】tE]TF.
相应的决策为：
u；（Dl）=El.
=min{6+4,2+3}=5.
这说明由D2到F的最短距离为5,其路径为D2^E2^F./
相应的决策为：
“;（Z）2）=E2・）
九（6）=min{〃4（2，d）+人（d），〃4（2，巧）+人©）}）
=min{l+4,3+3}=5.
即D3到F的最短距离为5,其路径为D3TE1TF.
相应的决策为：
＜（D3）=Er
/3（G）=min{4（G，P）+九（D）a（C],Z）2）+九（》2）}=min{5+7,8+5}=12.
这说明由5到F的最短距离为12,相应的决策为
%4（0）=E「I
*
UP）=E
A（C2）=min{d3（C2,Dl）+f4（D^d^C2,D2）+f4（D2）}
=min{4+7,5+5}=10.
即由C2到F的最短距离为10,相应的决策为w；（C2）=Z）2.
/3（C3）=min{^3（C3,D2）+/4（D2）^3（C3,D3）+/4（D3）}
=min{3+5,4+5}=8.
%3（C]）=D]•^；（C2）=Z）2.
4
/s（C4）=min{“（C』）+/4（D2）^3（COD3）+/4（D3）}
=min{8+5,4+5}=9.
即由C4到F的最短距离为9,相应的决策为
*_%3（°4）=°3・
f2W=min{〃2（dC）+人（G）,叭（d，C2）+人（C2）,I
〃2（d,C3）+人（C3）}=min{2+12,3+10,6+8}=13.
）
f2（B2）=min{J2（B2,C2）+/3（C2）^2（B2?
C3）+/3（C3）5
6/2（B25C4）+/3（C4）}=min{8+10,7+8,7+9}=15.
（1）k=1时，只有一个状态点A,则
/1（A）=min{^1（A,B1）+/2（B1）^1（A,B2）+/2（B2）}
=min{4+13,5+15}=17.
*
况3（C]）—D]・u；（C2）=D2.
4
3<（Bl）=c2.
*-%2（〃2）=C3・
再按计算顺序反推可得最优决策序列：
***
u\（A）=w2（^i）=C»w3（C2）=D2j
u；（D2）=E2,u；（E2）=F.
所以最优路线为：
ATB]TC?
TZ）2T佼TF
fl（B2）={dl（B2,A）+Usl）}
注意到：
/o（Si）=/o（A）=O
所以
=u；（BJ=A齐（场）=5,u；（B2）=A
1
*
/2（C1）=H（C1,B1）+/；（B1）}=2+4=6%2（G）=d
二min{3+4,8+5}=7w*（C2）=B{
/2（C3）=minH（C3,B1）+/1（51）^2（C3,B2）+/；（B2）}
=min{6+4,7+5}=10,
）
/2（c4）=H（C4,B2）+£（场）}=7+5=12,
fsW
=mind（9,C\）+乙（G）,d2{D{,C2）+/2（C2）}
=min{5+6,4+7}=ll
*_*
%3（0）=G，或m3（D1）=C2类似地，可算岀：
*
九（3）=12u3（D2）=C2
厶①）=14^3（^3）=C3
：
（即"
（G）=4
D
3
6
7
3
e2
b2
7
C4
3
（卩）=5或
*-
“3（»2）=C2
*7■=
“3（»3）=C3
2
3
Da
*
01
8
4
5
3
C
4
4
F
A
*_
%2（^2）=§
U2（C4）=〃2
九（耳）=14
九（3）=14
町（卩）=
*
%4（d）=D、
%4（丘2）=D?
人（0=17最优策略：
n；（F）=E
W3（0）=C?
心（眄洛
2W4（^2）=Q
*
%2（°2）=B]
g）=ll
/g）=12
£
（2）=14
ui（d）=4
最短路径：
ATB]TC?
T2T耳TF
最短路长：
人（0=17
注：
顺序解法与逆序解法无本质区别，一般来说，当初始状态给定时用逆序解法，当终止状态给定时用顺序解法。
若问题给定了一个初始状态与一个终止状态，则两种方法均可使用。
応分配问题（离散型）
例：
设有6万元资金用于4个工厂的扩建，已知每个工厂的利润增长额同投资额的大小有关，见下表。
问应如何确定对这四个工厂的投资额，使总利润增长额最大？
表1利润增长额gj（x/）（百元）
、、投资额
工厂（i）
0100200300400500600
1
0204260758590
2
0254557657073
3
0183961789095
4
0284765748085
解：
把对四个工厂的投资依次看成4个阶段的决策过程,"确定对第k个工厂的投资额看成第k个阶段的决策，
k=1,2,3,4o图示如下：
状态转移方程：
Sk+\二Sk_Xk，k=1,2,3,4.其中=600阶段指标函数gg：
第k阶段投资忑元时所产生的利润。
（见上表）
最优指标函数fS:
第k阶段状态为几且采取最佳投资策略，从第k个工厂以及以后的最大总利润。
逆序法基本递推方程：
[fk（»）=“max{gk（忑）+fk+l（如）}k=4,3,2」
<0Mg"
表1利润增长额gjSJ（百元）
、\投资额
工厂（i）
0100200300400500600
4
0284765748085
解：
（1）k二4时
考虑：
若到最后一个，第4个工厂投资时，还有资金S4,
若投资于第4个工厂的资金为兀,则最大利润为
表1利润增长额gjSJ（百元）
、\投资额
工厂（i）
0100200300400500600
4
0284765748085
（注意到此时厶6）二0）
办（为）=max{g4（^4）+/5（^）}
0=max{g4（^4）}
0
表1利润增长额gjSJ（百元）
、\投资额
工厂（i）
0100200300400500600
4
0284765748085
自然问：
现在还有多少钱？
即几二？
»二0，100,200，300,400,500,600都有可能。
下面分情况讨论:
办⑸）和器*2）｝賈營刃（“）｝弋爹幺（“）｝
$4=100时，
九⑸）二0出险｛&4（勺）｝=。
豐爲直4（兀）｝=董爲｛刃（兀）｝
=max{0,28}=28・兀；=100
其他种情况类似讨论，我们把所有的结果汇总成一个表2。
表2k=4时决策表
X
尤&4）
*
x4
0
100
200
300400
500
600
0
0
0
0
100
0
28
28
100
200
0
28
47
47
200
300
0
28
47
65
65
300
400
0
28
47
6574
74
400
500
0
28
47
6574
80
80
500
600
0
28
47
6574
80
85
85
600
表1利润增长额©（勺）（百元）
、\投资额工厂（i）、\
0100200300400500600
1
0204260758590
2
0254557657073
3
0183961789095
4
0284765748085
（2）k二3时到第三个工厂投资时，可利用的资金还有S3,
若向第三个工厂投资七（万元），则自此即以后最大利润为:
厶（$3）=max｛g3（%3）+/4G4）｝
0=0监瓷底（花）+九（33-七）｝Sk+i=
同样问：
S3二？
，即现在还有多少钱？
它是允许决策集上界。
同理53g53={0,100,200,300,400,500,600}
■f
表1利润增长额gj（y）（百元）
、\投资额工厂（i）7\
0100200300400500600
3
0183961789095
仅举一例:
$3=300
/3（300）=max{g3）+办㈤。
—心）}
0max
a：
3=0,100,200,300
{&3（兀3）+/4（3。
0-兀3）}
=max{g3（0）+f4（300—0）忌（100）+九（300—100）,（200）+/4（300-200）,（300）+/4（300-300）}
=max{g3（0）+f4（300）,g3（100）+f4（200）,g?
（200）+九（100）心（300）+九（0）}
表2k=4时决策表
\^4
&4（厂）
伽）
*
x4
0100200300400500600
0
100
200
300
400
500
600
0
028
02847
0284765
028476574
02847657480
0284765748085
0
28
47
65
74
80
85
0
100
200
300
400
500
600
/3（300）=max{g3（0）+九（300）,心（100）+办（200）,
g3（200）+九（100）也（300）+九（0）}
二max{0+65」8+47,39+2&61+0}=67
所有情况讨论结果汇总成下表:
表3k=3时决策表
\勺
g?
（%3）+ZlG3—可）
\
广3（$3）
$3\
0100200300400500600
0
0+0
0
0
100
0+2818+0
28
0
200
0+4718+2839+0
47
0
300
0+6518+4739+2861+0
67
200
400
0+7418+6539+4761+2878+0
89
300
500
0+8018+7439+6561+7478+2890+0
108
300
600
0+8518+8039+7461+6578+4790+2895+0
126
300
$2WS2={0,100,200300,400,500,600}
仅举一例:
吐=600
于2（600）=max{g2（x2）+f3（600-x2）}
0max{g?
（x?
）+/>（600-x?
）}
x2=0,100,200,300,400,500,600
=max{g2（0）+f3（600-0）5g2（l00）+扎（600-100）,g2（200）+f3（600-200）,g2（300）+扎（600—300）,g2（400）+f3（600-400）,g2（500）+扎（600-500）g2（600）+厶（600—600）}
投资额
工厂⑴
0100200300400500600
2
0254557657073
表1利润增长额g^Xj）（百元）
£（600）=maxfe2（0）+厶（600）,g2（100）+^（500）,g2（200）+/3（400）,g?
（300）+f3（300）,g2（400）+£（200）,g2（500）+£（100）g2（600）+£（0）}
=max{0+扎（600）,25+扎（500）,
45+厶（400）,57+厶（300）,
65+厶（200）,70+厶（100）,
73+厶（0）}
\兀3
&3（兀3）+/46-花）
\
右（归）
*Xo
$3\
0100200300400500600
D
0
0+0
0
0
100
0+2818+0
28
0
200
0+4718+2839+0
47
0
300
0+6518+4739+2861+0
67
200
400
0+7418+6539+4761+2878+0
89
300
500
0+8018+7439+6561+7478+2890+0
108
300
600
0+8518+8039+7461+6578+4790+2895+0
126
300
f2（600）=max{0+f3（600）,25+f3（500）,45+f3（400）,57+f3（300）,
65+/3（200）,70+厶（100）,73+£（0）}
二max{0+126,25+108,45+89,57+67,65+47,
70+2&73+0）=45+89=134.*_
—上UU
吐的其它取值情况及相应的最优决策列于下表
表4k二2时决策表
\兀2
孔\
&2（兀2）+去（＞2—兀2）
血⑸）
兀；
0100200300400500600
0
100
200
300
400
500
600
0+0
0+2825+0
0+4725+2845+0
0+6725+4745+2857+0
0+8925+6745+4757+2865+0
0+10825+8945+6757+4765+2870+0
0+12625+10845+8957+6765+4770+2873+0
0
28|
53'
73
92
114
134
0
0
100
200
100或200
100
200
时，此时S]=600,
/1（51）=/1（6OO）=max{g]（“）+EGi—“）}
0般加）+/2（6°0-“）｝
max{gi（x）+（600-x）}
可二0,100,200,300,400,500,600
=max{gl（0）+九（600-0）,g】（100）+九（600-100）,®（200）+£（600-200）,®（300）+£（600-300）,g]（400）+厶（600-400）,g]（500）+厶（600-500）^（600）+/2（600-600）}
表1利润增长额gi（勺）（百元）
7
工厂（i
殳资额
0100200300400500600
1
0204260758590
A（600）=max{&（0）+/2（600-0）,y（100）+为（600-100）,gi（200）+f2（600-200）,幻（300）+f2（600—300）,gi（400）+f2（600-400）,g]（500）+f2（600-500）^（600）+^（600-600）}
=max{0+力（600-0）,20+f2（600一100）,
42+f2（600-200）,60+厶（600-300）,
75+£（600-400）,85+力（600-500）
90+『2（600—600）}
&2（兀2）+力（吐—勺）
EG）
*
兀2
0100200300400500600
0
100
200
300
400
500
600
0+0
0+2825+0
0+4725+2845+0
0+6725+4745+2857+0
0+8925+6745+4757+28砧+0
0+1
升级会员 