《动态规划实例教学课件》由会员分享，可在线阅读，更多相关《动态规划实例教学课件（155页珍藏版）》请在金锄头文库上搜索。
1、动态规划,动态规划问题实例 动态规划的基本概念与原理 动态规划应用举例,引 言,动态规划是解决多阶段决策过程最优化的一种方法。该方法 是由美国数学家贝尔曼（R. E. Bellman)等人在20世纪50年代 初提出的。并成功地解决了生产管理、工程技术等方面的许 多问题，从而建立了运筹学的一个新的分支，即动态规划。 Bellman在1957年出版了Dynamic Programming一书，是 动态规划领域中的第一本著作。,1 动态规划问题实例,例1 给定一个线路网络，,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,
2、4,8,4,3,5,6,2,3,1,4,3,要从A向F铺设一条输油管道，,各点间连线上的数字表示距离，问应选择什么路线，可使总,距离最短？,动态规划是解决多阶段决策问题的一种方法。所谓多阶段,决策问题是指这样的决策问题：其过程可分为若干个相互联,系的阶段，每一阶段都对应着一组可供选择的决策，每一决,策的选定即依赖于当前面临的状态，又影响以后总体的效果。,A,B,C,D,E,状态A,状态B,状态C,状态D,状态E,状态F,决策A,决策D,决策E,当每一阶段的决策选定以后，就构成一个决策序列，称为一个,决策B,决策C,策略，它对应着一个确定的效果。多阶段决策问题就是寻找使,此效果最好的策略。,2
3、动态规划的基本概念与原理,一。基本概念,阶段：是指问题需要做出决策的步数。阶段总数常记为n，相 应的是n个阶段的决策问题。阶段的序号常记为k，称为阶段 变量，k=1,2, ,n. k即可以是顺序编号也可以是逆序编号， 常用顺序编号。,状态：各阶段开始时的客观条件，第k阶段的状态常用状态 变量 表示，状态变量取值的集合成为状态集合，用 表示。,例如，例1中，,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,第1阶段,第2阶段,第3阶段,第4阶段,第5阶段,状态 1,状态 2,
4、状态 3,状态 4,状态 5,状态 6,决策：是指从某阶段的某个状态出发，在若干个不同方案中,做出的选择。表示决策的变量，称为决策变量，用 表示,例如： 表示走到C阶段,当处于C2 路口时，下一 步奔D1.,时的允许决策集合记为 ，例如：,状态转移方程：是从上一阶段的某一状态值转变为下一阶段 某一状态值的转移规律，用,表示。,决策变量允许的取值范围称为允许决策集合，第k阶段状态为,指标函数：分阶段指标函数和过程指标函数。阶段指标函数,是指第k阶段从状态 出发，采取决策 时的效益，用,表示。而过程指标函数从第k阶段的某状态出发，,采取子策略,时所得到的阶段效益之和：,最优指标函数：表示从第k阶段
5、状态为 时采用最佳策略,到过程终止时的最佳效益。记为,其中 opt 可根据具体情况取max 或min。,基本方程：此为逐段递推求和的依据，一般为：,式中opt 可根据题意取 max 或 min.,例如，例1的基本方程为：,最优性原理：最优策略的子策略必为最优。不管过去的状态,和决策如何，从眼下直到最后的诸决策必构成最优子策略。,动态规划应用举例,例1 最短路线问题,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,逆序递推方程：,（1）k=5 时，状态,它们到F 点的距离即为
6、,最短路。,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,（2）k=4 时，状态,它们到F 点需经过中途,点E，需一一分析从E 到 F的最短路：先说从D1到F 的最短路,有两种选择：经过 E1, E2, 比较最短。,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,
7、6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,这说明由 D1 到F 的最短距离为7，其路径为,相应的决策为：,这说明由 D2 到F 的最短距离为5，其路径为,相应的决策为：,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,即 D3 到F 的最短距离为5，其路径为,相应的决策
8、为：,（3）k=3 时，状态,这说明由 C1 到F 的最短距离为12，相应的决策为,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,即由 C2 到F 的最短距离为10，相应的决策为,即由 C3 到F 的最短距离为8，相应的决策为,即由 C4 到F 的最短距离为9，相应的决策为,A,B1,B2,C1,C2,C
9、3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,（4）k=2时，状态,这说明由 B1 到F 的最短距离为13，相应的决策为,即由 B2到F 的最短距离为15，相应的决策为,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,
10、3,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,（1）k=1 时，只有一个状态点A, 则,即由 A到F 的最短距离为17，相应的决策为,所以最优路线为：,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,再按计算顺序反推可得最优决策序列：,顺序递推方程：,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,
11、7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,例1：,1阶段,2阶段,3阶段,4阶段,5阶段,行走方向,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,K=1 时,注意到：,所以,K=2 时,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,K=3 时,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,
12、5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,或,类似地，可算出：,最优策略：,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,或,最短路径：,最短路长：,注：顺序解法与逆序解法无本质区别，一般来说，当初始状 态给定时用逆序解法，当终止状态给定时用顺序解法。若问
13、 题给定了一个初始状态与一个终止状态，则两种方法均可使 用。,例2 资源分配问题（离散型）,例：设有6万元资金用于4个工厂的扩建，已知每个工厂的利 润增长额同投资额的大小有关，见下表。问应如何确定对这 四个工厂的投资额，使总利润增长额最大？,表1 利润增长额,（百元）,解：把对四个工厂的投资依次看成4个阶段的决策过程，,确定对第k个工厂的投资额看成第k个阶段的决策， k=1,2,3,4。图示如下：,工厂1,工厂2,工厂3,工厂4,投资x1,投资x2,投资x3,投资x4,状态,状态,状态,状态变量 ：可用于第k, k+1,n个工厂的投资额。,决策变量 ：第 k 阶段对第 k 个工厂的投资额。,允
14、许决策集 ：,状态转移方程：,其中,阶段指标函数 ：第 k 阶段投资 元时所产生的利 润。（见上表）,最优指标函数 ：第 k 阶段状态为 且采取最佳投资 策略，从第 k 个工厂以及以后的最大总利润。,逆序法基本递推方程：,工厂1,工厂2,工厂3,工厂4,投资x1,投资x2,投资x3,投资x4,状态,状态,状态,表1 利润增长额,（百元）,解：（1）k=4时,考虑：若到最后一个，第4个工厂投资时，还有资金 ， 若投资于第4个工厂的资金为 ，则最大利润为,工厂1,工厂2,工厂3,工厂4,投资x1,投资x2,投资x3,投资x4,状态,状态,状态,表1 利润增长额,（百元）,（注意到此时 =0）,自然问：现在还有多少钱？即 =？,=0，100，200，300，400，500，600都有可能。,下面分情况讨论：,工厂1,工厂2,工厂3,工厂4,投资x1,投资x2,投资x3,投资x4,状态,状态,状态,表1 利润增长额,（百元）,时，,时，,其他种情况类似讨论，我们把所有的结果汇总成一个表2。,表1 利润增长额,（百元）,表2 k=4 时决策表,
