第六章 动态规划
Chapter 6
Dynamic Programming
§6.1引例
例6.1 最短路径问题
图6.1
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示从起点A到终点E之间各点的距离。求A到E的最短路径。
如果用穷举法，则从A到E一共有3×3×2=18条不同的路径，逐个计算每条路径的长度，总共需要进行4×18=72次加法计算；对18条路径的长度做两两比较，找出其中最短的一条，总共要进行18－1=17次比较。如果从A到E的站点有k个，则总共有3k-1×2条路径， 用穷举法求最短路径总共要进行(k+1)3k-1×2次加法，3k-1×2-1次比较。当k的值增加时，需要进行的加法和比较的次数将迅速增加。例如当k=10时，加法次数为433026次，比较39365次。
以上求从A到E的最短路径问题，可以转化为三个性质完全相同，但规模较小的子问题，即分别从B1、B2、B3到E的最短路径问题。
记从Bi (i=1, 2, 3) 到E的最短路径为S(Bi)，则从A到E的最短距离S(A)可以表示为：
同样，计算S(B1)又可以归结为性质完全相同，但规模更小的问题，即分别求C1，C2，C3到E的最短路径问题S(Ci) (i=1, 2, 3)，而求S(Ci)又可以归结为求S(D1)和S(D2)这两个子问题。从图1.1.1可以看出，在这个问题中，S(D1)和S(D2)是以知的，它们分别是：
S(D1)=5，S(D2)=2
因而，可以从这两个值开始，逆向递归计算S(A)的值。计算过程如下：
即
S(C1)=8 且如果到达C1，则下一站应到达D1；
S(C2)=7 且如果到达C2，则下一站应到达D2；
S(C3)=12 且如果到达C3，则下一站应到达D2；
由此，可以计算S(Bi)：
即
S(B1)=20 且如果到达B1，则下一站应到达C1；
S(B2)=14 且如果到达B2，则下一站应到达C1；
S(B3)=19 且如果到达B3，则下一站应到达C2；
由此，可以计算S(A)：
最后，可以得到：从A到E的最短路径为A B2 C1 D1 E
以上计算过程及结果，可用图6.2表示，可以看到，以上方法不仅得到了从A到D的最短路径，同时，也得到了从图中任一点到E的最短路径。
以上过程，仅用了18次加法，11次比较，计算效率远高于穷举法。
§6.2 动态规划的基本概念 最短路径问题
由例6.1可以看出，动态规划问题具有以下基本特征：
1、问题具有多阶段决策的特征。阶段可以按时间划分，也可以按空间划分。
2、每一阶段都有相应的“状态”与之对应，描述状态的量称为“状态变量”。
3、每一阶段都面临一个决策，选择不同的决策将会导致下一阶段不同的状态，同时，不同的决策将会导致这一阶段不同的目标函数值。
4、每一阶段的最优解问题可以递归地归结为下一阶段各个可能状态的最优解问题，各子问题与原问题具有完全相同的结构。能否构造这样的递推归结，是解决动态规划问题的关键。这种递推归结的过程，称为“不变嵌入”。
为了将以上特征形式化，我们提出以下动态规划的基本概念。
阶段k：表示决策顺序的离散的量，阶段可以按时间或空间划分。
状态Sk：能确定地表示决策过程决策过程当前特征的量。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。
状态变量xk：表示每一状态可以取不同值的变量。
决策（Decision）dk：从某一状态向下一状态过度时所做的选择。决策是所在状态的函数，记为dk(xk)。
决策允许集合Dk(xk)：在状态xk下，允许采取决策的全体。
状态转移方程xk+1=T(xk,dk)：某一状态以及该状态下的决策，与下一状态之间的函数关系。
阶段指标函数vk(xk,dk)：从状态xk出发，选择决策dk所产生的第k阶段指标。
过程指标函数V(xk,dk,dk+1,…,dn)：从状态xk出发，选择决策dk,dk+1,…,dn所产生的过程指标。动态规划
要求
对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗
过程指标具有可分离性，即
Vk,n(xk, dk,dk+1,…,dn)=vk(xk,dk)+Vk+1(xk+1,dk+1,…,dn)
称指标具有可加性，或
Vk,n(xk, dk,dk+1,…,dn)=vk(xk,dk)×Vk+1(xk+1,dk+1,…,dn)
称指标具有可乘性。
最优指标函数fk(xk)：从状态xk出发，对所有的策略Pk,n，过程指标Vk,n的最优值，即
对于可加性指标函数，上式可以写为
对于可乘性指标函数，上式可以写为
以上式子称为动态规划最优指标的递推方程，是动态规划的基本方程。
终端条件：为了使以上的递推方程有递推的起点，必须要设定最优指标的终端条件，即确定最后一个状态n下最优指标fn(xn)的值。
阶段5
阶段4
阶段3
阶段2
阶段1
图6.3
2
5
10
8
5
6
9
3
12
11
13
4
10
6
10
14
12
1
5
2
例6.2 利用以上基本概念，重新求解例6.1。
将问题分成五个阶段，第k阶段到达的具体地点用状态变量xk表示，例如：x2=B3表示第二阶段到达位置B3，等等。这里状态变量取字符值而不是数值。
将决策定义为到达下一站所选择的路径，例如目前的状态是x2=B3，这时决策允许集合包含三个决策，它们是
D2(x2)=D2(B3)={B3C1, B3C2, B3C3}
最优指标函数fk(xk)表示从目前状态到E的最短路径。终端条件为
f5(x5)=f5(E)=0
其含义是从E到E的最短路径为0。
第四阶段的递推方程为：
从f5(x5)到f4(x4)的递推过程用下表表示：
x4
D4(x4)
x5
v4(x4,d4)
v4(x4,d4)+f5(x5)
f4(x4)
最优决策d4*
D1
D1E
E
5
5+0=5*
5
D1E
D2
D2E
E
2
2+0=2*
2
D2E
其中*表示最优值，在上表中，由于决策允许集合D4(x4)中的决策是唯一的，因此这个值就是最优值。
由此得到f4(x4)的表达式。由于这是一个离散的函数，取值用列表表示：
f4(x4) 的表达式
x4
f4(x4)
最优决策d4*
D1
5
D1E
D2
2
D2E
第三阶段的递推方程为：
从f4(x4)到f3(x3)的递推过程用表格表示如下：
x3
D3(x3)
x4
v3(x3,d3)
v3(x3,d3)+f4(x4)
f3(x3)
最优决策d3*
C1
C1D1
C1D2
D1
D2
3
9
3+5=8*
9+2=11
8
C1D1
C2
C2D1
C2D2
D1
D2
6
5
6+5=11
5+2=7*
7
C2D2
C3
C3D1
C3D2
D1
D2
8
10
8+5=13
10+2=12*
12
C3D2
由此得到f3(x3)的表达式：
x3
f3(x3)
最优决策d3*
C1
8
C1D1
C2
7
C2D2
C3
12
C3D2
第二阶段的递推方程为：
从f3(x3)到f2(x2)的递推过程用表格表示如下：
x2
D2(x2)
x3
v2(x2,d2)
v2(x2,d2)+f3(x3)
f2(x2)
最优决策d2*
B1
B1C1
B1C2
B1C3
C1
C2
C3
12
14
10
12+8=20*
14+7=21
10+12=22
20
B1C1
B2
B2C1
B2C2
B2C3
C1
C2
C3
6
10
4
6+8=14*
10+7=17
4+12=16
14
B2C1
B3
B3C1
B3C2
B3C3
C1
C2
C3
13
12
11
13+8=21
12+7=19*
11+12=23
19
B3C2
由此得到f2(x2)的表达式：
x2
f2(x2)
最优决策d2*
B1
20
B1C1
B2
14
B2C1
B3
19
B3C2
第一阶段的递推方程为：
从f2(x2)到f1(x1)的递推过程用表格表示如下：
x1
D1(x1)
x2
v1(x1,d1)
v1(x1,d1)+f2(x2)
f1(x1)
最优决策d1*
A
A B1
A B2
AB3
B1
B2
B3
2
5
1
2+20=22
5+14=19*
1+19=20
19
A B2
由此得到f1(x1)的表达式：
x1
f1(x1)
最优决策d1*
A
19
A B2
从表达式f1(x1)可以看出，从A到E的最短路径长度为19。由f1(x1)向f4(x4)回朔，得到最短路径为：
A B2 C1 D1 E
§6.3资源分配问题
例6.3 有资金4万元，投资A、B、C三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目A、B、C的投资效益（万吨）和投入资金（万元）的关系见下表：
项目
投入资金
A
B
C
1万元
15万吨
13万吨
11万吨
2万元
28万吨
29万吨
30万吨
3万元
40万吨
43万吨
45万吨
4万元
51万吨
55万吨
58万吨
求对三个项目的最优投资分配，使总投资效益最大。
阶段k：每投资一个项目作为一个阶段；
状态变量xk：投资第k个项目前的资金数；
决策变量dk：第k个项目的投资；
决策允许集合：0≤dk≤xk
状态转移方程：xk+1=xk-dk
阶段指标：vk(xk,dk)见表中所示；
递推方程：fk(xk)=max{vk(xk,dk)+fk+1(xk+1)}
终端条件：f4(x4)=0
k=4，f4(x4)=0
k=3，0≤d3≤x3，x4=x3-d3
x3
D3(x3)
x4
v3(x3,d3)
v3(x3,d3)+f4(x4)
f3(x3)
d3*
0
0
0
0
0+0=0
0
0
1
0
1
0
0+0=0
11
1
1
0
11
11+0=11*
2
0
2
0
0+0=0
30
2
1
1
11
11+0=11
2
0
30
30+0=30*
3
0
3
0
0+0=0
45
3
1
2
11
11+0=11
2
1
30
30+0=30
3
0
45
45+0=45*
4
0
4
0
0+0=0
58
4
1
3
11
11+0=11
2
2
30
30+0=30
3
1
45
45+0=45
4
0
58
58+0=58*
k=2，0≤d2≤x2，x3=x2-d2
x2
D2(x2)
x3
v2(x2,d2)
v2(x2,d2)+f3(x3)
f2(x2)
d2*
0
0
0
0
0+0=0
0
0
1
0
1
0
0+11=11
13
1
1
0
13
13+0=13*
2
0
2
0
0+30=30*
30
0
1
1
13
13+11=24
2
0
29
29+0=29
3
0
3
0
0+45=45*
45
0
1
2
13
13+30=43
2
1
29
29+11=40
3
0
43
43+0=43
4
0
4
0
0+58=58
59
2
1
3
13
13+45=58
2
2
29
29+30=59*
3
1
43
43+11=54
4
0
55
55+0=55
k=1，0≤d1≤x1，x2=x1-d1
x1
D1(x1)
x2
v1(x1,d1)
v1(x1,d1)+f2(x2)
f1(x1)
d1*
4
0
4
0
0+59=59
60
1
1
3
15
15+45=60*
2
2
28
28+30=58
3
1
40
40+13=53
4
0
51
51+0=51
最优解为x1=4, d1*=1, x2=x1-d1=3, d2*=0, x3=x2-d2*=3, d3=3, x4=x3-d3=0，
即项目A投资1万元，项目B投资0万元，项目C投资3万元，最大效益为60万吨。
§6.4 背包问题
例6.4 设有n种物品，每一种物品数量无限。第i种物品每件重量为wi公斤，每件价值ci元。现有一只可装载重量为W公斤的背包，求各种物品应各取多少件放入背包，使背包中物品的价值最高。
这个问题可以用整数规划模型来描述。设第i种物品取xi件（i=1,2,…,n，xi为非负整数)，背包中物品的价值为z，则
max
z=
c1x1
+c2x2
+…
+cnxn
s.t.
w1x1
+w2x2
+…
+wnxn
≤W
x1,
x2,…,
xn
为非负整数
阶段k： 第k次装载第k种物品（k=1,2,…,n）
状态变量xk： 第k次装载时背包还可以装载的重量；
决策变量dk： 第k次装载第k种物品的件数；
决策允许集合： Dk(xk)={dk|0 dkxk/wk，dk为整数}；
状态转移方程： xk+1=xk-wkdk
阶段指标： vk=ckdk
递推方程： fk(xk)=max{ckdk+fk+1(xk+1)}=max{ckdk+fk+1(xk-wkdk)}
终端条件： f4(x4)=0
对于一个具体问题：
c1=65，c2=80，c3=30
w1=2，w2=3，w3=1
以及 W=5
用动态规划求解
对于k=3
列出f3(x3)的数值表
f3(x3)
x3
D3(x3)
x4
30d3+f4(x4)
f3(x3)
d3*
0
0
0
0+0=0
0
0
1
0
1
1
0
0+0=0
30+0=30*
30
1
2
0
1
2
2
1
0
0+0=0
30+0=30
60+0=60*
60
2
3
0
1
2
3
3
2
1
0
0+0=0
30+0=30
60+0=60
90+0=90*
90
3
4
0
1
2
3
4
4
3
2
1
0
0+0=0
30+0=30
60+0=60
90+0=90
120+0=120*
120
4
5
0
1
2
3
4
5
5
4
3
2
1
0
0+0=0
30+0=30
60+0=60
90+0=90
120+0=120
150+0=150*
150
5
对于k=2
列出f2(x2)的数值表
f2(x2)
x2
D2(x2)
x3
80d2+f3(x3)
f2(x2)
d2*
0
0
0
0+f3(0)=0+0=0*
0
0
1
0
1
0+f3(1)=0+30=30*
30
0
2
0
2
0+f2(2)=0+60=60*
60
0
3
0
1
3
0
0+f3(3)=0+90=90*
80+f3(0)=80+0=80
90
0
4
0
1
4
1
0+f3(4)=0+120=120*
80+f3(1)=80+30=110
120
0
5
0
1
5
2
0+f3(5)=0+150=150*
80+f3(2)=80+60=140
150
0
对于k=1
列出f1(x1)的数值表
f1(x1)
x1
D1(x1)
x2
65d1+f2(x2)
f1(x1)
d1*
0
0
0
0+f2(0)=0+0=0*
0
0
1
0
1
0+f2(1)=0+30=30*
30
0
2
0
1
2
0
0+f2(2)=0+60=60
65+f2(0)=65+0=65*
65
1
3
0
1
3
1
0+f2(3)=0+90=90
65+f2(1)=65+30=95*
95
1
4
0
1
2
4
2
0
0+f2(4)=0+120=120
65+f2(2)=65+60=125
130+f2(0)=130+0=130*
130
2
5
0
1
2
5
3
1
0+f2(5)=0+150=150
65+f2(3)=65+90=155
130+f2(1)=130+30=160*
160
2
由题意知，x1=5，由表f1(x1)、f2(x2)、f3(x3)，经回朔可得：
d1*=2，x2=x1-2d1=1，d2*=0，x3=x2-3d2=1，d3*=1，x4=x3-d3=0
即应取第一种物品2件,第三种物品1件,最高价值为160元,背包没有余量。
由f1(x1)得列表可以看出，如果背包得容量为W=4，W=3，W=2和W=1时，相应的最优解立即可以得到。
§6.5 机器负荷分配问题
最短路径问题和背包问题的状态变量和决策变量都只能取离散的整数值。当状态变量和决策变量的取值范围很大，或者这些变量是连续的，用列举的方法就比较困难或者根本不可能了。这就需要用连续变量的处理方法。
例6.5 机器负荷分配问题
某种机器可以在高、低两种负荷下生产。高负荷生产条件下机器完好率为0.7，即如果年初有u台完好机器投入生产，则年末完好的机器数量为0.7u台。系数0.7称为完好率。年初投入高负荷运行的u台机器的年产量为8u吨。系数8称为单台产量。低负荷运行时，机器完好率为0.9，单台产量为5吨。设开始时有1000台完好机器，要制订五年
计划
项目进度计划表范例计划下载计划下载计划下载课程教学计划下载
，每年年初将完好的机器一部分分配到高负荷生产，剩下的机器分配到低负荷生产，使五年的总产量为最高。
构造动态规划模型如下：
阶段k：运行年份（k=1,2,3,4,5,6），其中k=1表示第一年初，…，依次类推；k=6表示第五年末（即第六年初）；
状态变量xk：第k年初完好的机器数（k=1,2,3,4,5,6），其中x6表示第五年末（即第六年初）的完好机器数；
决策变量dk：第k年投入高负荷运行的机器数；
状态转移方程：xk+1=0.7dk+0.9(xk-dk)
决策允许集合：Dk(xk)={dk|0dkxk}
阶段指标：vk(xk,dk)=8dk+5(xk-dk)
终端条件：f6(x6)=0
递推方程：
fk(xk)=max{vk(xk,dk)+fk+1(xk+1)}
dkDk(xk)
=max{8dk+5(xk-dk)+fk+1[0.7dk+0.9(xk-dk)]}
0dkxk
根据题意，本题的决策允许集合应该是一个整数集合，但由于决策允许集合中可取的决策数量很大，一一列举计算量很大，不妨认为状态变量和决策变量都是连续的，得到最优解后，再作取整处理。
f5(x5)=max{8d5+5(x5-d5)+f6(x6)}
0d5x5
=max{3d5+5x5}=8x5, d5*=x5
0d5x5
f4(x4)=max{8d4+5(x4-d4)+f5(x5)}
0d4x4
=max{8d4+5(x4-d4)+8x5}
0d4x4
=max{8d4+5(x4-d4)+8[0.7d4+0.9(x4-d4)]}
0d4x4
=max{1.4d4+12.3x4}=13.7x4, d4*=x4
0d4x4
f3(x3)=max{8d3+5(x3-d3)+f4(x4)}
0d3x3
=max{8d3+5(x3-d3)+13.7x4}
0d3x3
=max{8d3+5(x3-d3)+13.7[0.7d3+0.9(x3-d3)]}
0d3x3
=max{0.28d3+17.24x3}=17.52x3, d3*=x3
0d3x3
f2(x2)=max{8d2+5(x2-d2)+f3(x3)}
0d2x2
=max{8d2+5(x2-d2)+17.52x3}
0d2x2
=max{8d2+5(x2-d2)+17.52[0.7d2+0.9(x2-d2)]}
0d2x2
=max{-0.504d2+20.77x2}=20.77x2, d2*=0
0d2x2
f1(x1)=max{8d1+5(x1-d1)+f2(x2)}
0d1x1
=max{8d1+5(x1-d1)+20.77x2}
0d1x1
=max{8d1+5(x1-d1)+20.77[0.7d1+0.9(x1-d1)]}
0d1x1
=max{-1.154d1+23.69x1}=23.69x1, d1*=0
0d1x1
由此可以得到：
f1(x1)=23.69x1, d1*=0
f2(x2)=20.77x2, d2*=0
f3(x3)=17.52x3, d3*=x3
f4(x4)=13.60x4, d4*=x4
f5(x5)=8x5 d5*=x5
用x1=1000代入，得到五年最大产量为
f1(x1)=f1(1000)=23690
每年投入高负荷运行的机器数以及每年初完好的机器数为：
x1=1000
d1*=0, x2=0.7d1+0.9(x1-d1)=900
d2*=0, x3=0.7d2+0.9(x2-d2)=810
d3*=x3=810, x4=0.7d3+0.9(x3-d3)=567
d4*=x4=567, x5=0.7d4+0.9(x4-d4)=397
d5*=x5=397, x6=0.7d5+0.9(x5-d5)=278
在这个例子中，状态变量的终端值x6是未加约束的，如果要求在第五年末（即第六年初）完好的机器数不少于500台，这时决策变量d5的决策允许集合将成为：
D5(x5)={d5|0.7d5+0.9(x5-d5)500, d50}
即
0.9x5-0.2d5500, d50
或
0d54.5x5-2500
容易想象，这时的最大产量将比x6是自由的情况下小。
这个例子可以推广到一般情况。设高负荷生产时机器的完好率为k1，单台产量为p1；低负荷完好率为k2，单台产量为p2。若有t满足
则从1～t-1年，年初将全部完好机器投入低负荷运行，从t～n年，年初将全部完好机器投入高负荷运行，这样的决策，将使总产量达到最大。
§6.6 生产库存问题
例6.6 一个工厂生产某种产品，1～7月份生产成本和产品需求量的变化情况如下表：
月份(k)
1
2
3
4
5
6
7
生产成本(ck)
11
18
13
17
20
10
15
需求量(rk)
0
8
5
3
2
7
4
为了调节生产和需求，工厂设有一个产品仓库，库容量H=9。已知期初库存量为2，要求期末（七月低）库存量为0。每个月生产的产品在月末入库，月初根据当月需求发货。求七个月的生产量，能满足各月的需求，并使生产成本最低。
阶段k：月份，k=1,2,…,7,8；
状态变量xk：第k个月初（发货以前）的库存量；
决策变量dk：第k个月的生产量；
状态转移方程：xk+1=xk-rk+dk；
决策允许集合：Dk(xk)={dk | dk0, rk+1xk+1H}
={dk | dk0, rk+1xk-rk+dkH}；
阶段指标：vk(xk,dk)=ckdk；
终端条件：f8(x8)=0, x8=0；
递推方程：fk(xk)=min{vk(xk,dk)+fk+1(xk+1)}
dkDk(xk)
=min{ckdk+fk+1(xk-rk+dk)}
dkDk(xk)
对于k=7
因为
x8=0
有
d7=0
递推方程为
f7(x7)=min{c7d7+f8(x8)}=0
d7=0
对于k=6
因为 d7=0
所以 x7=r7=4
而 x6-r6+d6=x7=4
因此有 d6=x7+r6-x6=4+7-x6=11-x6
也是唯一的决策。因此递推方程为：
f6(x6)=min{c6d6+f7(x7)}
d6=11-x6
=10d6=10(11-x6)=110-10x6
对于k=5
f5(x5)=min{c5d5+f6(x6)}
d5D5(x5)
=min{20d5+110-10x6}
d5D5(x5)
=min{20d5+110-10(x5-r5+d5)}
d5D5(x5)
=min{20d5+110-10(x5-2+d5)}
d5D5(x5)
=min{10d5-10x5+130}
d5D5(x5)
D5(x5)={d5| d50, r6x5-r5+d5H}
={d5|d50, r6+r5-x5d5H+r5-x5}
={d5| d50, 9-x5d511-x5}
因为x5H=9，因此9-x50，决策允许集合可以简化为
D5(x5)={d5| 9-x5d511-x5}
递推方程成为
f5(x5)=min{10d5-10x5+130}
9-x5d511-x5
=10(9-x5)-10x5+130
=220-20x5， d5*=9-x5
对于k=4
f4(x4)=min{c4d4+f5(x5)}
d4D4(x4)
=min{17d4+220-20x5}
d4D4(x4)
=min{17d4+220-20(x4-r4+d4)}
d4D4(x4)
=min{17d4+220-20(x4-3+d4)}
d4D4(x4)
=min{-3d4-20x4+280}
d4D4(x4)
D4(x4)={d4| d40, r5x4-r4+d4H}
={d4| d40, r5+r4-x4d4H+r4-x4}
={d4| d40, 5-x4d412-x4}
={d4| max[0,5-x4]d412-x4}
由于在f4(x4)的表达式中d4的系数是-3，因此d4在决策允许集合中应取集合中的最大值，
即 d4=12-x4
由此 f4(x4)=-3(12-x4)-20x4+280
=-17x4+244
对于k=3
f3(x3)=min {c3d3+f4(x4)}
d3D3(x3)
=min {13d3+244-17x4}
d3D3(x3)
=min {13d3+244-17(x3-r3+d3)}
d3D3(x3)
=min {-4d3-17x3+329)}
d3D3(x3)
D3(x3)={d3| d30,r4x3-r3+d3H}
={d3| d30,r4+r3-x3d3H+r3-x3}
={d3| d30,8-x3d314-x3}
={d3| max[0,8-x3]d314-x3}
由此
f3(x3)=-4(14-x3)-17x3+329
=-13x3+273, d3*=14-x3
对于k=2
f2(x2)=min{c2d2+f3(x3)}
d2D2(x2)
=min{18d2+273-13x3}
d2D2(x2)
=min{18d2+273-13(x2-r2+d2)}
d2D2(x2)
=min{18d2+273-13(x2-8+d2)}
d2D2(x2)
=min{5d2-13x2+377}
d2D2(x2)
D2(x2)={d2|d20,r3x2-r2+d2H}
={d2|d20,r3+r2-x2d2H+r2-x2}
={d2|d20,13-x2d217-x2}
因为 13-x2>0
所以 d2(x2)={d2|13-x2d217-x2}
由此 f2(x2)=5(13-x2)-13x2+377
=-18x2+442, d2*=13-x2
对于k=1
f1(x1)=min{c1d1+f2(x2)}
d1D1(x1)
=min{11d1+442-18x2}
d1D1(x1)
=min{11d1+442-18(x1-r1+d1)}
d1D1(x1)
=min{11d1+442-18(x1-0+d1)}
d1D1(x1)
=min{-7d1-18x1+442}
d1D1(x1)
D1(x1)={d1|d10,r2x1-r1+d1H}
={d1|d10,r2+r1-x1d1H+r1-x1}
={d1|d10,8-x1d19-x1}
根据题意 x1=2
所以 D1(x1)={d1| 6d17}
由此 d1=7
f1(x1)=-7d1-18x1+442
=-7×7－18×2＋442
=357
将以上结果
总结
初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf
成下表：
k
1
2
3
4
5
6
7
ck
11
18
13
17
20
10
15
rk
0
8
5
3
2
7
4
xk
2
9
5
9
9
7
4
dk
7
13-x2=4
14-x3=9
12-x4=3
9-x5=0
11-x6=4
0
§6.7设备更新问题
一台设备的价格为P，运行寿命为n年，每年的维修费用是设备役龄的函数，记为C(t)，新设备的役龄为t=0。旧设备出售的价格是设备役龄的函数，记为S(t)。在n年末，役龄为t的设备残值为R(t)。现有一台役龄为T的设备，在使用过程中，使用者每年都面临“继续使用”或“更新”的策略，
阶段k：运行年份；
状态变量xk：设备的役龄t；
决策变量dk：
状态转移方程：
阶段指标：
递推方程：
终端条件：
fn(t)=-R(t)
设具体数据如下：
t
0
1
2
3
4
5
6
7
C(t)
10
13
20
40
70
100
100
--
S(t)
--
32
21
11
5
0
0
0
R(t)
--
25
17
8
0
0
0
0
且 n=5，T=2，P=50
由上表开始，终端条件为：
f6(1)=-25，f6(2)=-17，f6(3)=-8
f6(4)=f6(5)=f6(6)=f6(7)=0
对于k=5
对于k=4
对于k=3
对于k=2
对于k=1
由以上计算可知，本问题有两个决策，它们对应的最小费用都是115。这两个决策是：
年份
1
2
3
4
5
决策1
更新
更新
继续
更新
继续
决策2
更新
继续
更新
更新
继续
§6.8具有转向费用的最短路径问题
设城市的道路结构如右图所示。两个路口之间标的数字表示通过这一段道路所需的费用（单位：元），该城市有一项奇怪的交通规则：车辆经过每个路口时，向左或向右转弯一次，要收取“转弯费”3元。现有一辆汽车从A点出发到P点，求包括转弯费用在内，费用最小的行驶路线。
与本章前面介绍的最短路线问题不同，由于考虑转弯费用，从任一路口出发到达终点的最优路线不仅取决于当前的位置，而且与如何到达当前位置有关。如果仍旧用当前所在位置作为状态变量，用行进的方向作为决策变量，这样，从某一状态出发的最优决策，不仅与当前状态有关，还与这一状态以前的决策有关。这样就不满足动态规划“状态的无后效性”的要求。
为了满足动态规划的这一要求，必须重新构造状态变量。现将这个问题的动态规划模型构造如下：
阶段k：设起点A为第一阶段，到达B或C为第二阶段，如此等等。到达终点P为第七阶段。
状态变量：(xk, rk), (k=1, 2, …, 6)，其中xk为第k阶段所在位置，rk为从xk出发行进的方向：
终点P的状态变量为(P, )，表示行进方向为空集。由图可见，点G，J，K，M，N，O，P只有一个状态，其余的点都有两个状态。
由于状态变量包括所在位置和行进方向两个因素，决策变量也就已经包含在状态变量之中了。
最优指标：fk(xk, rk)表示从xk出发，按rk方向前进一步，最终到达P的最小费用（包括转弯费用）。
阶段指标：
uk(xk)—从xk出发上行一步的路程费用（不包括转弯费用）；
dk(xk)—从xk出发下行一步的路程费用（不包括转弯费用）。
递推方程：
终端条件： f7(P, )=0
k=7
对应于P只有一个状态x7=(P, )，相应的最优指标为：
f7(x7)=f7(P, )=0
k=6
对应于N只有一个状态x6=(N, d)，相应的最优指标为：
f6(N, d)=d6(N, d)+f7(P, )=2+0=2，
最优路线上的下一状态为x7*=（P, ）。
对应于点O只有一个状态x6=(O, u)，相应的最优指标为：
f6(O, u)=u6(O, u)+f7(P, )=1+0=1， x7*=(P, )
k=5
对应于K只有一个状态x5=(K, d)，相应的最优指标为：
f5(K, d)=d5(K, d)+f6(N, d)=1+2=3， x6*=(N, d)
对应于L有两个状态x5=(L, u)，x5=(L, d)，相应的最优指标分别为：
f5(L, u)=u5(L, u)+f6(N, d)+3=2+2+3=7, x6*=(N, d)
f5(L, d)=d5(L, d)+f6(O, u)+3=8+1+3=12， x6*=(O, u)
对应于M只有一个状态x5=(M, u)，相应的最优指标为：
f5(M, u)=u5(M, u)+f6(O, u)=4+1=5， x6*=(O, u)
k=4
对应于G只有一个状态x4=(G, d)，相应的最优指标为：
f4(G, d)=d4(G, d)+f5(K, d)=3+3=6， x5*=(K, d)
对应于H有两个状态x4=(H, u)和x4=(H, d)，相应的最优指标分别为：
f4(H, u)=u4(H, u)+f5(K, d)+3=3+3+3=9， x5*=(K, d)
对应于I有两个状态x4=(I, u)和x4=(I, d)，相应的最优指标分别为：
f4(I, d)=d4(I, d)+f5(M, u)+3=2+5+3=10， x5*=(M, u)
对应于J只有一个状态x4=(J, u)，相应的最优指标为：
f4(J, u)=u4(J, u)+f5(M, u)=2+5=7， x5*=(M, u)
k=3
对应于D有两个状态x3=(D, u)和x3=(D, d)，相应的最优指标为：
f3(D, u)=u3(D, u)+f4(G, d)+3=2+6+3=11， x5*=(G, d)
对于E有两个状态x3=(E, u)和x3=(E, d)，相应的最优指标为：
对于F有两个状态x3=(F, u)和x3=(F, d)，相应的最优指标为：
f3(F, d)=d3(F, d)+f4(J, u)+3=4+7+3=14, x4*=(J, u)
k=2
对于B有两个状态x2=(B, u)和x2=(B, d)，相应的最优指标为：
对于C有两个状态x2=(C, u)和x2=(C, d)，相应的最优指标为：
浙公网安备 33021202002483