第四章-动态规划.ppt

动态规划 Dynamic Programming（DP）
动态规划
奔狙弱懊阶贰忻浴惋刽抽扮鸡报褂逗丝延减不哮讽嫁硒鱼鬼尘桓慧赣吟奠第四章-动态规划第四章-动态规划
动态规划 Dynamic Programming（DP）
引言
动态规划作为运筹学的一个重要分支是解决多阶段决策过程最优化的一种非常有效的方法。
1951年, RBellman
多阶段决策问题
一系列相互联系的
单阶段决策问题
最优性原理
贝尔曼的名著《动态规划》于1957年出版，这成了动态规划的第一本著作。
丽嘉排孙晰嘲遣赁棘秆剂纺弊贯艘馏吓壳胶肯捌碑腑湿氛瑰疼猫贴聋怠陡第四章-动态规划第四章-动态规划
动态规划 Dynamic Programming（DP）
引言
动态规划的方法，在工程技术、企业管理、工农业生产及军事等部门中有着广泛的应用，并且获得了显著的效果。
最优路径问题
资源分配问题
生产与库存问题
设备更新问题
经济管理方面的应用
…
牡看悉激豌啮互鄂援默烩栋泳似猩尽轨取翁籍钩啊簇相显炳茫诸驳嘉仅讣第四章-动态规划第四章-动态规划
动态规划 Dynamic Programming（DP）
引言
由于动态规划的方法在众多方面的应用，使他已经成为现代企业管理中的一种重要的决策方法。

此外，许多实际问题采用动态规划方法去处理，常比线性规划或非线性规划更加有效。
特别对于离散型的问题，由于解析数学无法施展其术，而动态规划方法就成为一种非常有效的工具。
鞠氏廉邓衙萤水奔摹然柯牡央沼殿侠奏邵栈狠控董雕钓叮掷基浴兹受岗肌第四章-动态规划第四章-动态规划
动态规划 Dynamic Programming（DP）
多阶段决策过程的最优化
多阶段决策过程：
整个决策过程可按时间或空间顺序分解成若干相互联系 的阶段，每一阶段都需作出决策，全部过程的决策是一个决策序列。
多阶段决策过程最优化的目标：
达到整个活动过程的总体效果最优，而非各单个阶段最优的简单总和。
圃待们痉吸与纺昌胜粳姨堡陷上哨陵化瀑彤黎输强铂汹距职钩氮抹否悟犬第四章-动态规划第四章-动态规划
动态规划 Dynamic Programming（DP）
动态规划典例
例——最短路线问题
农膜刑寡荣庐愉纵绚碟珊浓疤催终诅词消汝硝撂泡威龟葱卞娃霉粕傲局僻第四章-动态规划第四章-动态规划
5
3
1
3
6
8
7
6
6
8
3
5
3
4
2
1
3
8
2
2
3
3
3
5
5
2
6
6
4
3
A
B1
B2
C2
C3
C4
C1
D3
D2
D1
E3
E2
E1
F2
F1
G
动态规划 Dynamic Programming（DP）
动态规划典例----最短路问题
寻找A点到G点的最短线路
4
3
7
5
9
7
6
8
13
10
9
12
13
16
18
该点到G点的
最短距离
绒鄙闸播苟牟王舰箍扑殴菜昭辣问膨晕报蛛雪咙醚稻泡场搐蔼怕秦们弱浑第四章-动态规划第四章-动态规划
动态规划 Dynamic Programming（DP）
动态规划典例----最短路问题
A点到G点的最短线路如下，最短距离18。
A
B1
C2
D1
E2
F2
G
对于以上的最短线路问题：
逆序动态递推的方法
简单的枚举方法
575次运算
43次运算
？运算量
溯桓庸彩峦罢卧架族宠较异锗媚忌糜蒜邢奔物蔗朴滁钎获溜杏鲁衔汲吾丹第四章-动态规划第四章-动态规划
动态规划 Dynamic Programming（DP）
动态规划的基本概念
1、阶段（stage）
对整个决策过程的自然划分，通常根据时间顺序或空间特征来划分阶段，以便按阶段的次序逐段解决整个过程的优化问题。阶段变量通常用k表示（k = 1，2，3，…，n）。
2、状态（state）
每个阶段开始时过程所处的自然状况或客观条件。它应能描述过程的特征并具有“无后效性”，即当前阶段状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关。
状态变量 —— sk（state variable）
允许状态集合 —— Sk（set of admissible states）
姿咬晚