数学建模动态规划docxWord格式文档下载.docx

数学建模动态规划docxWord格式文档下载.docx

《数学建模动态规划docxWord格式文档下载.docx》由会员分享，可在线阅读，更多相关《数学建模动态规划docxWord格式文档下载.docx（44页珍藏版）》请在冰点文库上搜索。

是指问题需要做出决策的步数。

阶段总数常记为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]•^；

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.

3<

（Bl）=c2.

*-%2（〃2）=C3・

再按计算顺序反推可得最优决策序列：

***

u\（A）=w2（^i）=C»

w3（C2）=D2j

（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

e2

b2

C4

（卩）=5或

*-

“3（»

2）=C2

*7■=

3）=C3

2

Da

01

8

5

C

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

最短路径：

T2T耳TF

最短路长：

人（0=17

注：

顺序解法与逆序解法无本质区别，一般来说，当初始状态给定时用逆序解法，当终止状态给定时用顺序解法。

若问题给定了一个初始状态与一个终止状态，则两种方法均可使用。

応分配问题（离散型）

例：

设有6万元资金用于4个工厂的扩建，已知每个工厂的利润增长额同投资额的大小有关，见下表。

问应如何确定对这四个工厂的投资额，使总利润增长额最大？

表1利润增长额gj（x/）（百元）

、、投资额

工厂（i）

0100200300400500600

0204260758590

0254557657073

0183961789095

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」

0<

xk<

sk

Mg"

表1利润增长额gjSJ（百元）

、\投资额

（1）k二4时

考虑：

若到最后一个，第4个工厂投资时，还有资金S4,

若投资于第4个工厂的资金为兀,则最大利润为

（注意到此时厶6）二0）

办（为）=max{g4（^4）+/5（^）}

0<

X4<

54

=max{g4（^4）}

X4“4

自然问：

现在还有多少钱？

即几二？

»

二0，100,200，300,400,500,600都有可能。

下面分情况讨论:

办⑸）和器*2）｝賈營刃（“）｝弋爹幺（“）｝

$4=100时，

九⑸）二0出险｛&

4（勺）｝=。

豐爲直4（兀）｝=董爲｛刃（兀）｝

=max{0,28}=28・兀；

=100

其他种情况类似讨论，我们把所有的结果汇总成一个表2。

表2k=4时决策表

X

尤&

4）

x4

100

200

300400

500

600

28

47

300

65

400

6574

74

80

85

表1利润增长额©

（勺）（百元）

、\投资额工厂（i）、\

（2）k二3时到第三个工厂投资时，可利用的资金还有S3,

若向第三个工厂投资七（万元），则自此即以后最大利润为:

厶（$3）=max｛g3（%3）+/4G4）｝

X3<

53

=0监瓷底（花）+九（33-七）｝Sk+i=

同样问：

S3二？

，即现在还有多少钱？

它是允许决策集上界。

同理53g53={0,100,200,300,400,500,600}

■f

表1利润增长额gj（y）（百元）

、\投资额工厂（i）7\

仅举一例:

$3=300

/3（300）=max{g3）+办㈤。

—心）}

x3<

max

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）}

\^4

&

4（厂）

伽）

028

02847

0284765

028476574

02847657480

/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\

0+0

0+2818+0

0+4718+2839+0

0+6518+4739+2861+0

67

0+7418+6539+4761+2878+0

89

0+8018+7439+6561+7478+2890+0

108

0+8518+8039+7461+6578+4790+2895+0

126

$2WS2={0,100,200300,400,500,600}

吐=600

于2（600）=max{g2（x2）+f3（600-x2）}

x2<

max{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）}

投资额

工厂⑴

表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

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）

血⑸）

兀；

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

28|

53'

73

92

114

134

100或200

时，此时S]=600,

/1（51）=/1（6OO）=max{g]（“）+EGi—“）}

x{<

s{

般加）+/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（勺）（百元）

工厂（i

殳资额

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

0+8925+6745+4757+28砧+0

0+1