运筹学课件：空中交通系统动态规划VIP

空中交通系统优化与管理动态规划什么是动态规划动态规划是解决多阶段决策过程最优化的一种方法。1951年美国数学家贝尔曼（R·Bellman）等人提出了解决这类问题的“最优化原理”，并研究了许多实际问题。什么是动态规划在工程技术、企业管理、工农业生产及军事部门中都有广泛应用：解决最优路径问题、资源分配问题、生产调度问题、库存问题、装载问题、排序问题、设备更新问题、生产过程最优控制问题等等。动态规划模型分类：离散确定型、离散随机型、连续确定型、连续随机型。5.1多阶段决策问题的最优化多阶段决策问题，是指可将过程划分为若干个互相联系的阶段，在它的每一个阶段都需要作出决策，并且一个阶段的决策确定以后，常影响下一阶段的决策，从而影响整个过程的活动。各个阶段所确定的决策就构成一个决策序列，通常称为策略。由于每一个阶段可供选择的决策往往不只一个，因而就有许多策略可供选择。多阶段的决策问题，就是要在允许选择的那些策略中，选择一个最优策略，使在预定的标准下达到最好的效果。5.1多阶段决策问题的最优化5.1多阶段决策问题的最优化阶段往往可以用时段来表示。在各个时间阶段，采用不同的决策是随时间而变动的，这就有“动态”的含义。它是在时间的推移过程中要在每一段选择最恰当的决策，以期整体上达到最优。5.1多阶段决策问题的最优化

动态规划在一定条件下也可以解决一些与时间无关的问题，只要人为地引进"时段"因素以后，这些问题就可变为一个多阶段决策问题。5.1多阶段决策问题的最优化

例1

生产与存贮问题

某工厂每月需供应市场一定数量的产品，并将所余产品存入仓库。一般某月适当增加产量可降低生产成本，但超产部分存入仓库会增加库存费用。要求确定一个逐月的生产计划，在满足需求条件下，使一年的生产与存贮费用之和最小。

全年分为12个阶段逐次决策。5.1多阶段决策问题的最优化例2投资决策问题某公司现有资金Q万元，在今后5年内考虑给A，B，C，D

4个项目投资，这些项目投资的回收期限、回报率均不相同，问该公司应如何确定这些项目每年的投资额，使到第5年末拥有资金的本利总额最大。这是一个5阶段决策问题。5.1多阶段决策问题的最优化例3设备更新问题

企业在使用设备时都要考虑设备的更新问题，因为设备越陈旧所需的维修费用越多，但购买新设备则要一次性支出较大的费用；现某企业要决定一台设备未来8年的更新计划，已预测了第j年购买设备的价格为Kj，设Gj为设备经过j年后的残值，Cj为设备连续使用j-1年后在第j年的维修费(j＝1，2，…，8)，问应在哪些年更新设备可使总费用最小。这是一个8阶段决策问题

例4：最短路线问题5.1多阶段决策问题的最优化图5-35.2动态规划的基本概念和基本原理动态规划的基本概念使用动态规划方法解决多阶段决策问题，首先要将实际问题写成动态规划模型，此时要用到以下概念：阶段；状态；决策和策略；(4)状态转移；(5)指标函数。

例4最短路线问题5.2.1 动态规划的基本概念图5—3如图5-3所示，给定一个线路网络图，要从A地向F地铺设一条输油管道，各点间连线上的数字表示距离，问应选择什么路线，可使总距离最短。阶段和阶段变量：将所给问题的过程，按时间或空间特征分解成若干互相联系的阶段，以便按次序去求每阶段的解，常用字母k表示阶段变量。例4中，从A到F,

可以分成从A到B(B有两种选择)，从B到C(C有四种选择)，从C到D(D有三种选择)，从D到E(E有两种选择)，再从E到F,五个阶段。k＝1，2，3，4，5。5.2.1 动态规划的基本概念动态规划的基本概念状态和状态变量：状态表示某一阶段初所处的位置或状况。通常一个阶段包含若干个状态。描述状态的变量称为状态变量，常用sk表示第k阶段的某一状态，状态变量sk的集合称为状态集合，用Sk表示。5.2.1 动态规划的基本概念在例4中，第一阶段状态为A,第二阶段状态：B1，B2，或s1=A， s21=B1 ，s22= B2。状态变量的集合:S1 = {A}S2 ＝ {B1，B2 }S3 ＝ {C1，C2， C3，C4 }S4＝{D1，D2，D3}S5＝{E1，E2 }动态规划中的状态应具有如下性质：代表性。能够反映过程的演变特征。可知性。能够通过某种方式，直接或间接地确定下来。无后效性。所谓无后效性，是指某阶段的状态，只对该阶段状态以后过程的演变起作用，而不受以前各阶段状态的影响。这就是说，过程的过去历史只能通过当前的状态去影响它的未来的发展，当前的状态就是未来过程的初始状态5.2.1 动态规划的基本概念5.2.1 动态规划的基本概念要正确地定义状态变量，就必须对问题具有深入的观察和理解，可以从下面两个方面来考虑：把阶段连系在一起的因素是什么?需要用什么信息来进行当前的决策，而不用检查以前阶段所作决策的可行性。5.2.1 动态规划的基本概念决策和决策变量:

决策就是某阶段状态给定以后，从该状态演变到下一阶段某状态的选择。描述决策的变量，称为决策变量。常用uk(sk)表示第k阶段当状态为sk时的决策变量。在实际问题中，决策变量的取值往往限制在一定范围内，我们称此范围为允许决策集合，常用Dk(sk)表示第k阶段从状态sk出发的允许决策集合，显然有：uk(sk)

Dk(sk) 。5.2.1 动态规划的基本概念5.2.1 动态规划的基本概念在例4中，从第二阶段的状态集合为S2={B1,B2}

，从B1出发，允许决策集合为：D2(B1)＝{C1，C2，C3}如我们决定选择C3：，则可表为：u2(B1)＝C3策略和最优策略:由第1阶段开始到最后一个阶段终点为止的过程，称为问题的全过程。由每阶段的决策uk(sk)组成的决策序列就构成一个全过程策略，简称为策略，记为P1,n：P1,n(s1)={u1(s1),u2(s2),…

,un(sn)}由过程的第k阶段开始到终点为止的过程，称为原过程的后部子过程(或称为k子过程)。其决策函数序列称为k子过程策略，简称子策略，记为Pk,n

即：Pk,n(sk)={uk(sk),uk+1(sk+1),…

,un(sn)}5.2.1 动态规划的基本概念– 允许策略集合用P表示。从允许策略集合中找出达到最优效果的策略称为最优策略。在上图中，用P1,5={A，B1，C2，D2，E1，F}是一个策略，P3,5={C2，D2，E1，F}

是P1,5的一个子策略。5.2.1 动态规划的基本概念状态转移方程动态规划中本阶段的状态往往是上一阶段状态和上一阶段的决策结果。如果给定了第k段的状态sk

，则第k+1段的状态sk+1

也就完全确定。状态转移方程：由k段到k十l段的状态转移规律,sk+1

=Tk

(sk,uk)。例4中，状态转移方程为：sk+1

= uk(sk)5.2.1 动态规划的基本概念动态规划的基本概念指标函数及最优指标函数在多阶段决策过程最优化问题中，用来衡量所实现过程的优劣的数量指标，称为指标函数；它是一个定义在全过程和所有后部子过程上的确定的数量函数，常用Vk,n表示．即：Vk,n=

Vk,n（sk,sk+1,…,sn）指标函数Vk,n的最优值，称为相应的最优指标函数，记为fk(sk)。5.2动态规划的基本概念和基本原理5.1.2.动态规划的基本原理Bellman最优化原理作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。结合例4最短路线问题介绍动态规划的基本思想。从过程的最后一段开始，用逆序递推方法求解，逐步求各段各点到终点厂的最短路线，最后求得A点到F点的最短路线。5.1.2.动态规划的基本原理

第一步，从s＝5开始，状态变量s5可取两种状态E1，E2，它们到F点的路长分别为f5

(E1

)

4 f5

(E2

)

3第二步，k＝4，状态变量s5可取三个值D1，D2，D3，这是经过一个中途点到达终点F的两级决策问题，从D1到F只有两条路线，需加以比较，取其中最短的，即：

1 2 5 2

1 1 5 1

5

3

min

7

d(D,E)

f

(E

) 3

4

d(D

,

E )

f

(E )

f4

(D1

)

min

5

2

3

6

4

min

2 2 5 2

d(D

,

E )

f(E

)

d

(D2

,

E1

)

f5

(E1

)f4(D2)

min14 1u*(D)

E2u*(D )

E4 2

53

3

1

4

min

3 2 5 2

d(D,E)

f(E

)

d

(D3,

E1

)

f5

(E1

)f4

(D3

)

minu*(D)

E4 3 1u*(C)

D3 4 3f3

(C4

)

9u*(C)

D3 3 2f3

(C3

)

8u*(C)

D3 2 2f3

(C2

)

103 1 1u*(C)

D3 1k

3时,

f

(C

)

122 2 3u*(B)

Cf2

(B2

)

152u*(B)

C2 1k

2时,

f2

(B1

)

132 11d

(

A,

B

)

f (B

)1

5

15

4

13

min

17

2 2 2

d

(

A,

B

)

f (B

)

k

1时,

f

(

A)

min最短路为17,路径为A

B1

C2

D2

E2

Fu*(A)

B1 1图7-2

f6

(s6

)

0)

f (s )} k

5,4,3,2,1k

1 k

1(sk,

ukkfk(sk)

min{duk动态规划方法的基本思想：将多阶段决策过程划分阶段，恰当地选取状态变量、决策变量及定义最优指标函数，从而把问题化成一族同类型的子问题，然后逐个求解。求解时从边界条件开始，逆(或顺)过程行进方向，逐段递推寻优。在每一个子问题求解时，都要使用它前面已求出的子问题的最优结果，最后一个子问题的最优解，就是整个问题的最优解。动态规划方法是既把当前一段与未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法，因此每段的最优决策选取是从全局考虑的，与该段的最优选择一般是不同的。5.1.2.动态规划的基本原理Bellman最优化原理：作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。

n

1

n

1(s )

0

f

动态规划的基本方程是递推逐段求解的根据，一般的动态规划基本方程可以表为：

fk(sk

)

opt {vk(sk,

uk)

fk

1(sk

1

)}

uk

Dk(

sk)

k

n,

n

1,...,15.1.2.动态规划的基本原理动态规划的基本解题步骤如下：第一步：划分阶段；第二步：确定状态变量及其取值范围；代表性。2)可知性。3)无后效性。第三步：确定决策变量及其取值范围；第四步：建立状态转移方程；第五步：确定指标函数第六步：建立动态规划基本方程，然后从k＝n开始，逐段向前推移，直到求出f1(s1)时，就得到了整个过程的最优解，包括最优策略和相应的最优指标函数值5.1.2.动态规划的基本原理动态规划模型的建立与求解动态规划模型的建立

资源分配问题例5 某公司有资金10万元，若投资于项目j(j＝1，2，3)的投资额为xi时，其收益分别为g1(x1)3＝4x1，g2(x2)＝9x2，g3(x3)＝2x

2，问应如何分配投资数额才能使总收益最大?

x

0 (i

1,2,3)

i

x1

x2

x3

103maxz

4x1

9x2

2x2且满足约束这是一个与时间无明显关系的静态最优化问题，可列出其静态模型： 求x1，x2，x2：，使5.3.1动态规划模型的建立

用动态规划方法求解：基本方程：3阶段k：k=1,2,3状态变量sk

：第k段可以投资于第k项到第3个项目的资金数。决策变量xk

：决定给第k个项目投资的资金数。状态转移方程：

sk+1＝

sk

-

xk

。指标函数：Vk

,3

gi

(

xi

)i

k最优指标函数人fk(sk)：当可投资金数为sk时，投资第k——3项所得的最大收益数k k k k k

1 k

10

xk

skf (

s )

max

{g (

x )

f (

s )} k

3,

2,1

f4(

s4)

05.3.1动态规划模型的建立收益船厂012345A035789B046899C0137910例6 船舶总公司拟将5万元资金投放到下属A、B、C三个船厂，各船厂在获得资金后的收益如表5-1所示。试用动态规划方法求使总收益最大的投资分配方案。表5-15.3.1动态规划模型的建立解：阶段k：k=1,2,3状态变量sk

：第k段可以投资于第k项到第3个项目的资金数。

S1

{5}

{0

,1,

2

,

3,

4,

5} k

2,

3

S

k决策变量xk

:为第k阶段分配给第k个船厂的资金数。显然:Dk(sk)

{0,1,2,3,

4,

5} k

1,

2

,

3– 状态转移方程：sk

1k

1,2,

3

sk

xk5.3.1动态规划模型的建立xk

Dk(sk

)–指标函数：阶段指标函数gk(sk)如表5-1所示–最优指标函数人fk(sk)：当可投资金数为sk时，投资第

k——3项所得的最大收益数–基本方程：

fk(sk

)

m

ax {gk(xk

)

f

k

1

(

s

k

1

)}4 4k

3,

2

,

1

f (

s )

0

用逆序法由最后一阶段向前推进计算。5.3.1动态规划模型的建立x3f3

(s3

)

max{g3

(x3

)

f4

(s4

)}K=3时：阶段s3g3

(x3)f3

(s3

)f4(s4

)x3

*k=300000111012330237703499045101005阶段s2x2g2(x2

)f

2

(

x2

)f3(s2

x2

)x2

*k=20000001000+1=1f3(1)=1144+0=4f3(0)=012000+3=3f3(2)=3144f3(1)=1266f3(0)=023007f3(3)=7147f3(2)=3267f3(1)=1388f3(0)=034009f3(4)=91411f3(3)=71269f3(2)=3389f3(1)=1499f3(0)=050010f3(5)=101413f3(4)=

912613f3(3)=723811f3(2)=34910f3(1)=1599f3(0)=0阶段s1x1g1

(x1

)f2

(5

s1

)x1

*k=1500131313141112513837136481245990f1

(5)

14(万元)最优策略(对船厂A、B、C的资金分配序列)是：分给船厂A 1万元，分给船厂B 1万元，分给船厂C3万元最大收益是14万元。由上述计算结果可知:最大收益是：

例4的顺序解法：5.3.2.

逆序法与顺序法

从k＝0开始，f0

(s1

)

f0

(

A)

0

k＝2时，f2

(s3

) 定义有：

f2

(C1

)

d

(B1

,

C1

)

f1

(B1

)

2

4

6

u (C)

B

2 1 1是边界条件

k＝1时，f1

(s2

) 定义有：

f1(B1)

4

f1

(B2

)

5

u1(B1)

A

u1(B2)

Ad

(B1

,

C2

)

f1

(B1

)f2(C2)

min3

4

min

7

d(B

,

C )

f(B

)

2 2 1 2

8

5

u (C )

B

2 2 1

d

(B1

,C3

)

f1

(B1

)2 36

4f (C)

min

min

10

d(B,C)

f(B

)

2 3 1 2

7

5

u(C)

B

2 3 1

f2

(C4

)

d

(B2

,

C4

)

f1

(B2

)

7

5

12

u2(C4)

B2类似有：

f3

(D1

)

11f3

(D2

)

12f3

(D3

)

14f4

(E1

)

14f4

(E2

)

14f5

(F

)

17u3

(D1

)

C1或C2u3

(D2

)

C2u3(D3)

C3u4(E1)

D1u4(E2)

D2u5(F

)

E2路径为:

A

B1

C2

D2

E2

F动态规划模型的求解：1)离散变量的分段穷举算法动态规划模型中的状态变量与决策变量若被限定只能取离散值，则可采用分段穷举法。用分段穷举法求最优指标函数值时，要正确确定每段状态变量取值范围及允许决策集合的范围。连续变量的解法当动态规划模型中状态变量与决策变量为连续变量，就要根据方程的具体情况灵活选取求解方法，如经典解析方法、线性规划方法、非线性规划法或其它数值计算方法等。可用逆序解法和顺序解法来求解。连续变量的离散化解法5.3.2.

逆序法与顺序法

k

3,2,10

xk

sk例5

某公司有资金10万元，若投资于项目j(j＝1，2，3)的投资额为xi时，其收益分别为g1(x1)＝4x1，g2(x2)＝9x2，g3(x3)＝2x32，问应如何分配投资数额才能使总收益最大?解：阶段k=1,2,3;状态变量sk

为第k段可以投资于第k项到第3个项目的资金数；决策变量xk

决定给第k个项目投资的资金数；状态转移方程：

sk+1

＝

sk

-

xk

；最优指标函数fk(sk)表示当可投资金数为sk时，投资第k到第3项所得的最大收益数；f1(s1)

为所求的总收益；递推方程：

fk(

sk)

max{gk(xk

)

f

k

1

(

sk

1

)}4 4

f (

s )

0(a)用逆序解法解例5 3 3 33 30

x

sk＝3时，f (s

)

max

{2x2}k＝2时，

2(s

x )2}2 222 3

2s2}

max

{9x

max

{9x0

x2

s20

x2

s222 2f (s )

max

{9x

f3

(s3)}0

x2

s222

x

)2

9

4(s2

x2

)

0令 h2

(s2

,

x2

)

9x2

2(sdh22

2

4

0 x2

s2

29 d

2

h4 d

2xx2

s2

2则极大值在[0,

s ]端点取得f (0)

2s2

,

f (s )

9s2 2 2 2 294dx是极小值x*

s

时,

有最大值2s23 3 32 22 2 22 22 2 222当s

9

时,

f (0)

f (s ),

此时x*

02s

9

时,

f (0)

f (s ),

此时x*

sk＝1时，f1(s1)

max{4

x1

f2

(

s2)} 当f2

(

s2

)

9s2时,但此时

s2

s1

x1

10

0

9

/

2,

与s2

9

/

2矛盾故舍去0

x

s11f1

(10)

max{4x1

9s1

9x1

)}

max{9s1

5x1

)}

9s1x*

00

x1

10 0

x1

102令f (0)

f (s

)时,2s2

9s

, 则s

92 2 2 2 2 22 2 2 11 1 10

x1

10当f (s )

2s

2时,

f

(10)

max

{4

x

2(s

x )2

}211 1 1 1 1 1

4

4(s1

x1)

01d

2hdx2解得x1

s1

1,

而

1

1

0,

所以x1

s1

1是极小点.1比较[0,10]两个端点,

x1

0时,

f1

(10)

200x

10时,

f

(10)

40

,

所以,

x*

01 1 1再由状态方程顺推,

s

s

x*

10

0

102 1 1因为s

9

/

2,

所以x*

0,

s

s

x*

10

0

102 2 3 2 2所以 x*

s

103 3max

z

200万元令h

(s

,

x )

4

x

2(s

x ) ,由dhdx阶段划分和决策变量设置同逆序法；

状态变量sk+1

表示可用于第1个到第k个项目投资的资金数:s4＝10，s3＝s4–x3，s2＝s3–x2，s1＝s2–x1

;状态转移方程：

sk＝

sk+1

-

xk

；最优指标函数fk(sk+1)表示第k阶段投资金数为sk+1时，投资第1到第k项所得的最大收益数；

递推方程：

f

k

(

sk

1

)

k

1,2,3max {gk(xk

)

f

k

1

(

sk

)}0

xk

sk

10 1

f (s)

0 (b)用顺序解法解例5 1 20

x1

s2当k

1,

f1(s2

)

max{g1(

x1)

f0

(s1

)}1 2

max

{4x

}

4s0

x

s

max

{5x2

4s3

}

9s30

x2

s3

4(s3

x2

)}

max{9x2

4s2

}

max

{9x20

x2

s3 0

x2

s30

x2

s3当k

2,

f2

(s3

)

max

{9x2

f1(s2

)}x*

s1 2x*

s2 33

x )}4

9(s2 3 33 4 3f (

s )

max

{2

x

2

f (

s )}

max

{2

x

20

x3

s4 0

x3

s4当k=3时93所以x*

103dx2则极大值在[0,

s4

]端点取得当x3

0时,

f3

(10)

90,当x3

10时f3

(10)

200d2h

4

0 则x3

4

是极小点3解得x

9

/

4333令 h(s,x)

2x2

9(s

x

)4 3 3 4dx由 dh

4

x

9

0再由状态方程逆推,

s

10

x*

03 3x*

0,

s

s

x*

0, x*

02 2 3 2 1同逆序法结果相同max

z

200万元xksk

1

skk kk k k

1 k

10

xk

skf (

s )

max

{g (

x )

f (

s )} k

n,n

1,...,1

f

n

1

(

sn

1

)

0状态转移方程 :

(i

1,2,...,

n)

xi

0n

i

1

xi

an3)连续变量的离散化解法投资分配问题的一般静态模型为：max

z

gi

(

xi

)i

1动态规划模型，其基本方程为：5.3.2.

逆序法与顺序法由于sk与xk都是连续变量，当各阶段指标gk(xk)没有特殊性质而较为复杂时，要求出fk(sk)会比较困难，这时常常把连续变量离散化求其数值解。具体做法如下：把a分成m份，每份

大小。Sk的取值范围为：{0

，2

,…,m

}

，

的大小可依据问题所要求的精度以及计算机的容量来定。决策变量xk也在离散点0，

，2

， … ，m

上取值，相应的指标函数fk(sk)就被定义在这些离散值上，于是:02

1

q

a(m

)… …012qmq

＝sk，

xk＝p

5.3.2.

逆序法与顺序法(c)按逆序（或顺序）方法，逐步递推求出fn(sn),

…，f1(s1) ，最后求出最优资金分配方案。

x

0 (i

1,2,3)

i

x1

x2

x3

10maxz

4x

9x

2x2 且满足约束1 2 3解: 令

＝2，将区间[0，l0]分割成0，2，4，6，8，10六个点，即状态变量sk集合为{0，2，4，6，8，10}；允许决策集合为0

xk

sk

，xk与sk均在分割点上取值。例5

k

n,n

1,...,1p

0

,1,

2

,...,

q

f

n

1

(

sn

1

)

0

fk(

sk)

max {gk(

p

)

f

k

1

(

sk

p

)}其中q

＝

sk

，

xk

＝p

递推方程就变为了：式中x3与s3的集合均为：{0，2，4，6, 8，10}。计算结果见表7—1。3 3 30

x3

s3当k＝3时，

f (s

)

max

{2x2}

表7-1阶段skxkvkvkn=vk+fk+1fkPkn

*30022x3

=0000228882443232324667272726881281281288101020020020010指标 最优指标

最优决策

表7-2阶段skxkvkvkn=vk+fk+1fkPkn

*2009x2=000020002-022x9=1818+0184000+32=324-022x9=1818+8=2644x9=3636+0=36366000+72=72720-622x9=1818+32=5044x9=3636+8=4465454+0=54810指标计算结果见表7

2最优指标

最优决策k

2时,

f2

(s2

)

max{9x2

f3(s2

x2

)}0

x2

s2阶段skxkvkvkn=vk+fk+1fkPkn

*28000+128=1281280-822x9=1818+72=9044x9=3636+32=6865454+8=6287272+0=7210000+200=2002000-1022x9=1818+1282=14644x9=3636+72=10865454+32=8687272+8=80109090+0=90

表7-2指标计算结果见表7

2最优指标

最优决策k

2时,

f2

(s2

)

max{9x2

f3(s2

x2

)}0

x2

s2

表7-3阶段skxkvkvkn=vk+fk+1fkPkn

*11004x1=00+200=2002000-0-10288+128=13644x4=1624+36=6062454+32=8683232+18=50104040+0=40最优指标

最优决策x1

)} 计算结果见表7

3指标k

1时,

f1

(s1

)

max{4x1

f2

(s10

x1

10计算结果表明，最优决策为：x1*＝0，x2*＝0，x3*＝10，最大收益为f1(10)＝200，与例5结论完全相同。5.4动态规划模型的应用5.4.1背包问题（装载问题）n一位旅行者携带背包去登山，已知他所能承受的背包重量限度为a千克，现有n种物品可供他选择装入背包，第i种物品的单件重量为ai千克，其价值(可以是表明本物品对登山的重要性的数量指标)是携带件数xi的函数ci(xi)

(i=1,2,...,n),问旅行者应如何选择携带各种物品的件数，以使总价值最大？静态数学模型：

max

z

ci

(xi

)i

1ns.t.i ia

x

a

i

1

i

x

0 且为整数(i

1,

2,...,

n)5.4动态规划模型的应用

sk

1状态转移方程：sk

ak

xk0 1k

1,2,...,

n

f (s)

0xk允许决策集合：Dk

(

sk

1

)

{xk

|

0,1,

2,...,[

sk

1

/

ak

]}–最优指标函数：

fk

(

sk

+1

)–基本方程：

fk

(

sk

1

)

max{ck

(

xk

)

f

k

1

(

sk

1

ak

xk

)}

动态规划顺序法：–阶段k：(k=1,2,…,n)

按装入物品排序–状态变量sk

：第k段开始时装入前k种物品的总重量。–决策变量xk

:装入第k件物品的件数。5.4动态规划模型的应用状态转移方程：

sk

1

skak

xkn

1 n

1k

n,...,

2,1xk允许决策集合：Dk(xk)

{0,1,2,...,[sk

/ak]}–最优指标函数：

fk

(

sk

)–基本方程：

fk

(

sk

)

max{ck

(

xk

)

f

k

1

(

sk

1

)}

f(

s )

0

动态规划逆序法：–阶段k：(k=1,2,…,n)

按装入物品排序–状态变量sk

：第k段开始时剩余的空间。–决策变量xk

:装入第k件物品的件数。5.4动态规划模型的应用例7

今有三种货物需要装船，各种货物的重量与运输利润关系如图5-7所示。船的最大装载能力为w＝6(t)，问应如何装载才能使总利润最大?货物种类(i)货物质量(Wi)(t)利润(vi)(千元）12823133418动态规划逆序法：阶段k：(k=1,2,3)

按装入物品排序状态变量sk

：第k段开始时剩余的空间(可装载第k种至第n种的载货量。决策变量xk

:装入第k件货物的数量。5.4动态规划模型的应用状态转移方程： sk

1

skwk

xk

指标函数：阶段指标即为第k阶段装载xk件货物时所创的利润vkxk。– 基本方程：xk

Dk(sk

)sk

{0

,1,...,6}

fk(sk

)

max {vk

xk

f

k

1

(

sk

1

)}

xk

Dk(sk

)sk

{0

,1,...,6}

max {vk

xk

fk

1(sk

wkxk)}k

3,

2,1

f (

s )

0

4 4

5.4动态规划模型的应用K=3时：s3s4=s3-4x3K=2时：K=1时：5.4.2

生产存贮问题（库存问题）

如果已知某企业所生产产品的生产费用、存贮费用和市场的需要量，在其生产能力和存贮能力许可的前提下，正确确定各个时期的生产量，使既完成交货计划，又使总支出最少，这就是生产与存贮问题。例8

某船厂根据合同，从当年起连续4年年末要为客户提供规格型号相同的大型客货船，每年的交船数及生产每艘船的生产费用如表5—5所示。5.4动态规划模型的应用5.4动态规划模型的应用4i

k0

sk

di该厂的生产能力为每年6艘船。在进行生产的年度，船厂还要支出经常费用60万元。若造出的船当年不交货，则每艘船每积压一年造成的积压损失费为40万元。假定开始时及第四年年未交贷后均无积压船只，问船厂应如何安排这四年的生产计划，使所花的总费用为最低?解：动态规划逆序法：阶段k：(k=1,2,3,4)状态变量sk

：第k阶段初贮存(积压)的船数。–决策变量xk

:为第k阶段生产的船数。sk

6

d

k s1

s5

0xk

sk

d

k

最大库存量4xk

sk

dii

kxk

sk

d

kksk

6(k

1)

dii

15.4动态规划模型的应用状态转移方程：sk

1

sk

xk

dk k

1,2,3,

4– 基本方程：k

1 k

1)

f (

s )} k

1,2,3,

4k kk kk0

xk

6f (

s )

min

{v (

s ,

x

f5(s5)

0– 指标函数vk

：就是第k年度的生产成本(包括生产费用与存贮费用两部分)。

0.6

ckxk

0.4

sk 若xk

0vk(sk,xk)

k

1,2,3,

4k k

0.4

s 若x

0k＝2时，d2＝3k＝1时，x1*＝1，x2*=5，x3*＝0，x4*＝25.4.3

设备更新问题

设备更新问题一般提法：在已知一台设备的效益函数r(t)，维修费用函数u(t)及更新费用函数c(t)条件下，要求在n年内的每年年初作出决策,

是继续使用旧设备还是更换一台新的，使n年总效益最大。rk(t)：在第k年设备已使用过t年(或称役龄为t年)，再使用1年时的效益。uk(t)：在第k年设备役龄为t年，再使用一年的维修费用。ck(t)：在第k年卖掉一台役龄为t年的设备，买进一台新设备的更新净费用。a为折扣因子(0

a

1)，表示一年以后的单位收入价值相当于现年的a单位。5.4动态规划模型的应用动态规划模型：阶段k：表示计划使用该设备的年限数。(k=1,…,n)状态变量sk

：第k年初设备已使用过的年数，即役龄。决策变量xk

:是第k年初更新(Replacement)，还是保留使用(keep)旧设备，分别用R与K表示。状态转移方程为：5.4动态规划模型的应用–阶段指标为：k

1ks

s

1 当xk

K(keep

)

1 当xk

R

(

Replacement

)v (s ,

x )

rk(sk)

uk(sk

)若xk

Kj k kk k kk

k

r(0)

u (0)

c (s ) 若x

R5.4动态规划模型的应用–指标函数为：k kj kf (

s )

max

{v (

skk

1 k

1,

x )

f (

s )} k

n,n

1,

...,1

xk

K

或R

fn

1

(

sn

1

)

0实际上：–最优指标函数为：Vk

,n(k

1,2,...,

n)nj

k

vj(sk,

xk)k k k

1

kr (

s )

uk(

sk)

f(

s

1)fk(sk)

max当xk

Kkk kk

1

r (0)

u (0)

c (

s )

f

kk(1) 当x

R

f(

s )

0

n

1 n

1例：设某台新设备的年效益及年均维修费用、更新净费用如下表，试确定今后五年内的更新策略，使总效益最大。（设a=1）（单位：万元）役龄项目012345效益

rk(t)54.543.7532.5运行费

uk(t)0.511.522.53更新费

ck(t)0.51.52.22.533.55.4动态规划模型的应用解：n=55 5 5 55 5r(s)

u(s

)

k

5 f(s)

max

x5

Kx5

R

r5

(0)

u5

(0)

c5

(s5

)状态变量s5可取1，2，3，4f (1)

max

r5

(1)

u

5

(1) x5

K逆序法55 5 55

r(0)

u (0)

c (1) x

R

5

max

4.5

1

3.5x (1)

K

5

0.5

1.5

f (2)

max

r5

(2)

u5

(2)x5

K55 555

r(0)

u (0)

c

(2) x

R

5

max

4

1.5

2.5x(2)

K

5

0.5

2.2

f (3)

max

r5(3)

u5

(3) x5

K55 5 55

r(0)

u (0)

c (3) x

R

5

max

3.75

2

2 x (3)

R

5

0.5

2.5

f(4)

max

r5(4)

u5

(4)x5

K55 555

r(0)

u(0)

c

(4) x

R

5

max

3

2.5

1.5x(4)

R

5

0.5

3

5 5 5 5x5

Kx5

R5 5r(s)

u(s

)

k

5 f(s)

max

r5

(0)

u5

(0)

c5

(s5

)r4

(s4

)

u4

(s4

)

f5

(s4

1)x4

K4 44 4 4 54k

4 f (s )

max

r(0)

u (0)

c

(s )

f (1) x

R

4

状态变量s4可取1，2，35 4x4

Kx4

R4r4

(

s4

)

u

4

(

s4

)

f (

s

1)4

max

4.5

1

2.5

6.5x (1)

R

5

0.5

1.5

3.5

f (1)

maxs4

1

r4

(0)

u

4

(0)

c4(

s4

)

f5

(1)

x4

Kx4

R4r4(s4)

u4(s4)

f5(s4

1)4

max

4

1.5

2

5.8x (2)

R

5

0.5

2.2

3.5

f (2)

maxs4

2

r4(0)

u4

(0)

c4

(s4

)

f5

(1)

r4

(s4

)

u4

(s4

)

f5

(s4

1)x4

K4 44 4 4 54k

4f (s )

max

r(0)

u (0)

c

(s )

f (1) x

R

4

r4(s4)

u4(s4)

f5(s4

1)x4

Kx4

R4s4

34f (3)

max

max

3.75

2

1.5

5.5x(3)

R

5

0.5

2.5

3.5

r4

(0)

u4

(0)

c4

(s4

)

f5

(1)

3 3 3 3 4 3x3

Kx3

R3 3r(s)

u(s)

f(s

1)k

3 f(s)

max

r3

(0)

u3

(0)

c3

(s3

)

f4

(1)此时s3可取1或24 3r3

(

s3

)

u3

(

s3

)

f (s

1)x3

Kx3

R3s3

13f (1)

max

max

4.5

1

5.8

9.5x (1)

R

5

0.5

1.5

6.5

r3

(0)

u3

(0)

c3

(

s3

)

f

4(1)

4 3r3

(

s3

)

u3

(

s3)

f (

s

1)x3

Kx3

R3s3

23f (2)

max

max

4

1.5

5.5

8.8x (2)

R

5

0.5

2.2

6.5

r3

(0)

u3

(0)

c3

(

s3

)

f

4(1)

r2

(

s2

)

u

2

(

s2

)

f

3

(

s2

1)x2

K

x2

R2s2

12f (1)

max

max

4.5

1

8.8

12.5x (1)

R

5

0.5

1.5

9.5

r2

(0)

u

2

(0)

c2(

s2)

f3

(1)

f (s

)

max

r2

(s2

)

u2

(s2

)

f3

(s2

1)x2

K2 22 2 2 32k

2

r(0)

u (0)

c(s)

f (1) x

R

2由于状态s2只能取1，所以有f(s)

max

r1(s1)

u1(s1

)

f2(s1

1)x1

K1 11 1 1 21k

1

r(0)

u(0)

c(s

)

f