运筹学 第2版 教学课件 作者 沈荣芳 第七章　动态规划.ppt

《运筹学 第2版 教学课件 作者 沈荣芳 第七章　动态规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章　动态规划第一节　最短线路问题第二节　动态规划的基本概念和原理第三节　动态规划应用举例第四节　决策变量连续的动态规划问题第五节　乘积形式的目标函数第六节　随机型动态规划问题第一节　最短线路问题一、最短线路问题及其解法图7-1是一个线路网络图。从A到E要修建一条石油管道。管道必须在B、C、D三处设立加压站。在B处有B1，B2，B3三个不同地址可供选择作为建站点。当然，从A到这3个点的距离是不同的；同样，C和D处也都有不同的地址可供选择。图上的圆圈称为节点，表示地址，两个节点之间的箭线称为线或边，表示可以修建管道，线上的数字表示两个地址之间的距离。现在的问题是在许多条

2、从A到E的线路中，找出一条最短的，称为最短线路问题。一、最短线路问题及其解法1.逆序法2.顺序法一、最短线路问题及其解法图　7-11.逆序法图　7-22.顺序法图　7-3第二节　动态规划的基本概念和原理一、多阶段决策问题二、动态规划的基本概念三、最优化原理与动态规划方程一、多阶段决策问题如果一个问题的求解过程可以按空间(例如最短线路问题)、按时间(例如后面将要讨论的生产计划问题)，或者按问题的要求可以划分成相互关联的若干阶段，而每个阶段都需要作出决策，当所有阶段的决策都确定后，整个问题的求解策略也就确定了，那么这样的问题称为多阶段决策问题。不论按哪种因素分段，统称为时段

3、，于是问题成为按时段的变动而作出决策的问题，这就是“动态”的含义。二、动态规划的基本概念1.阶段和阶段变量2.状态和状态变量3.决策和决策变量4.策略和子策略5.状态转移函数6.阶段损益和策略效益二、动态规划的基本概念正确地划分阶段是运用动态规划求解问题的基础。一般说来，如何划分并没有固定的模式，只能依靠经验和技巧。有的问题，虽不能像最短线路问题那样明显地分段，但适当增加节点可以转化为多阶段决策问题来求解。例如图7-4所示求A到G的最短线路问题。从网络图上看不出明显的阶段划分，但增加节点后，将问题化为图7-5所示的情况，便成为多阶段决策问题。1.阶段和阶段变量图　7-4

4、1.阶段和阶段变量图　7-52.状态和状态变量在多阶段决策过程中，每个阶段的起始位置或状况称为该阶段的状态。每个阶段的初始状况又是前一个阶段的一个终止状况(当然，第一阶段除外)。因而，一旦各个阶段的状态都确定之后，整个过程也就完全确定。从这个意义上说，多阶段决策过程也就是各个状态的演变过程。应当注意，不同的问题，其状态的含义也不同。3.决策和决策变量知道了阶段k的状态sk后，就要作出关于这一个阶段的决策。所谓决策，就是从本阶段的状态出发，如何演变到下一阶段状态所作的抉择。描述决策的变量称为决策变量。通常用xk表示第k个阶段的决策。4.策略和子策略对一个多阶段决策问题，由

5、第1个阶段到最后阶段(设为阶段n)，当每一个阶段的决策都确定后，构成的决策序列称为一个整体策略，简称策略。由于每个阶段都有若干个可能的状态和不同的可能决策，因而具有许多不同的策略可供选择。其中能够满足预期目标的子策略，称为从sk出发的最优子策略。5.状态转移函数顺序状态转移函数与逆序状态转移函数统称为状态转移函数。多阶段决策问题有的可以用逆序法，即状态转移用顺序状态转移函数来求解；也可以用顺序法求解，但有的问题却只能用逆序法来求解，因此我们主要讨论逆序法求解。用逆序法求解，要用顺序状态转移函数，因此，如不加说明，以后总是指顺序状态转移函数。6.阶段损益和策略效益前面在最

6、短线路问题中已经指出，从A到E的最优线路有这样的特点：如果最短线路经过第k阶段的状态sk，那么从sk出发到达终点的这条线路对于从sk出发到达终点的所有线路来说，必是最短线路。在实际生活中具有这样特点的问题很多。美国科学家贝尔曼研究了这类问题，提出了求解多阶段决策问题的最优化原理。三、最优化原理与动态规划方程最优化原理　对于多阶段决策问题，作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，就前面决策所形成的状态而言，余下的诸决策必然构成一个最优子策略。用动态规划求解多阶段决策问题的基本思想是：利用最优化原理，建立动态规划方程，即建立动态规划的数学模型，然后求

7、得其最优解。三、最优化原理与动态规划方程基本步骤为：(1)将问题的求解过程恰当地分成若干阶段，一般可按问题所处的空间或时间进行划分，并确定阶段变量，对n个阶段问题来说，k=1,2,…,n。(2)正确地选择状态变量sk，它应当满足无后效性等三个条件，并确定状态集合Sk。(3)确定决策变量xk(sk)及阶段的允许决策集合Dk(sk)。(4)写出状态转移函数(5)根据题意，列出指标函数Fk,n,fk(sk),F1,n,f1(s1)。三、最优化原理与动态规划方程第三节　动态规划应用举例例1　生产与存储问题　一个工厂生产的某种产品，在一定的时期内，