文档介绍：动态规划DP
动态规划DP
(Dynamic Programming)
动态规划是现代企业管理中一种重要的决策方法,它是解决多阶段决策过程最优化的一种数学方法。
动态规划大约产生于五十年代,1951年美国数学家贝尔曼(R1>.Bellman)等人,根据一类多阶段决策问题的特点,把多阶段决策问题变换为一系列相互联系的单阶段问题。然后逐个加以解决。同时,他提出了解决这类问题的最优原理,研究了许多实际问题,从而创建了解决最优化问题的一种新的方法----动态规划。
动态规划的方法,在工程技术、企业管理、军事等部门都有广泛的应用。在企业管理中,动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存问题、装载问题、排序问题、设备更新问题、生产过程最优控制问题。需要特别强调的是:动态规划是求解一类问题的方法,是考察问题的一种途径,而不是一种特殊的算法。因而不像线性规划那样有一个标准的数学表达式和明确定义的一组规则。故需要有丰富的想象去建模,创造性地去求解。
一、多段决策问题的提出
例1生产与存储问题
某工厂每季度需供应市场一定数量的产品(600,700,500,1200),未销售完的产品存入仓库(每件每季度1元),现要制定生产计划,在满足市场需求的条件下,使一年的生产与存储费用最少。生产费用为:件数的平方成正比,。
例2最短路问题
设有一辆汽车由A城到B城,中间可经过V1到V8城市,各城市的交通路线及距离如下图所示,问应选择哪一条路线,可使总距离最短。
由上述例题可知,在实际生产、科学试验、经济活动的过程中,有一类活动的过程,由于其特殊性。可将该过程分为若干个相联系的阶段,在每个阶段都要做出决策,全部过程的决策就形成一个决策序列,每一个阶段的决策有许多种方案选择,从而形成多种决策策略,在这些决策策略中选择一个最优的策略,使在预定的标准下达到最好效果,这就是多阶段决策问题。
二、多阶段决策的有关概念
三、动态规划的基本思想和基本方程
以最短路线为例介绍动态规划的思想。常识告诉我们,最短路线有一个重要特点:如果由起点A经过B,C,D,E,F点到达终点G是一条最短的路线,则由点B出发经过C,D,E,F点到达终点G的这条子路线。就必然是从点B出发到达终点的所有可能选择的不同路线中最短的一条。此特点可用反正发来证明。
根据最短路线这一特点,我们就得到了寻找最短路线的方法,假设已求得从点B出发到达终点的最短路线,再选择从A到B两点间的一条最短路线,就求得了从起点A到终点G的一条最短路线。那么,如何求从点B出发到达终点的最短路线呢,再假设已求得从点C出发到达终点的最短路线,再选择从B到C两点间的一条最短路线,就求得了从起点B到终点G的一条最短路线。
以这样的思路,只要能求出F到G的最短路,就可以求出E到G的最短路,从而递推的求出,D,C,B,A 到G的最短路。所以动态规划方法就是从终点逐段向始点方向寻找最优解的一种方法,即就是从最后一段开始,用由后向前逐步递推的方法,求出各点到G点的最短路线,最后求得有A点到G点的最短路线。
四、动态规划的最优性原理
()
“作为整个过程的最优策略具有这样的性质:无论过去的状态和决策如何,对前面的决策所形成的状态而言,余下的决策必须构成最优策略。”简言之,一个最优策略的子策略总是最优的。
五、解法举例
现利用动态规划的基本方程求解例1中的生产与存储问题。
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
E
C2
一、最短路径问题
求从A到E的最短路径
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
E
C2
f5(E)=0
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
E
C2
f4(D1)=5
f5(E)=0
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
E
C2
f4(D2)=2
f5(E)=0
f4(D1)=5
2
5
1
12
14
10
6
10
4
13
11
1