第6章-动态规划PPT课件.ppt

《第6章-动态规划PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三部分动态规划第一章动态规划的基本方法§1动态规划的研究对象特征：包含有随时同变化的因素和变量，整个过程可以分为若干个相互联系的阶段，而且每个阶段都要做出决策。1.应用：企业管理：动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存问题、装载问题、排序问题、设备更新问题、生产过程最优控制问题等等。2.多阶段决策过程及实例在生产和科学实验中，有一类活动的过程，由于它的特殊性，可将过程分为若干相互联系的阶段。在它的每一个阶段都需要作出决策，从而使整个过程达到最好的活动效果，因此，各个阶段决策的选取不是任意确定的

2、，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成了一个决策系列，因而也就确定了整个过程的一条活动路线，这种把一个问题可看作是一个前后关联具有链状结构的多阶段过程（如图1所示）就称为多阶段决策过程，也称序贯决策过程，这种问题就称为多阶段决策问题。3.n状态1决策2决策决策状态状态状态状态图1链状结构的多阶段过程4.多阶段决策问题很多，现举例如下：例1：最短路问题如图2，给定一个线路网络，两点之间连线上的数字表示两点间的距离（或费用），试求一条由A到G的铺管线路，使总距离为最短（或总费用最小）。5.AB

3、23B1C1C2C3C4D1D2D3E1E2E3F1F2G53136876683533842221335526643图26.例2：机器负荷分配问题某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u1的关系为这时，机器的年完好率为a，即如果年初完好机器的数量为u，到年终时完好的机器就为au，0

4、时，决定如何重新分配完好的机器在两种不同的负荷下生产的数量，使在五年内产品的总产量达到最高？8.§2动态规划的基本概念一、阶段和阶段变量在多阶段决策过程中，为了表示决策和过程的发展而引入阶段的概念，一个阶段就是需要作出决策的子问题。通常阶段是按照决策进行的时间或空间上的先后顺序划分的，用阶段变量k表示。9.二、状态和状态变量状态表示某一阶段初所处的位置或状况，通常一个阶段包含若干个状态，描述状态的变量称为状态变量。常用sk表示第k阶段的某一状态。所有状态变量组成的集合，称为状态变量集合。常用Sk表示第k阶段的状态变量集合。

5、三、决策和决策变量决策就是某阶段状态给定以后，从该状态演变到下一阶段某状态的选择。描述决策的变量，称为决策变量。常用xk（sk）表示第k阶段当状态处于sk时的决策变量，在实际问题中，决策变量的取值往往限制在某一范围内，此范围称为允许决策集合，通常用Dk（sK）表示第k阶段的允许决策集合，显然有：10.11.在实际过程中，可供选择的策略有一定的范围，此范围称为允许策略集合，用P表示，从允许策略集合中找出达到最优效果的策略称为最优策略。五、状态转移方程在多阶段决策过程中，第k阶段到第（k+1）阶段的演变规律，称为状态转移方程。

6、当给定了第K阶段的状态变量sk和决策变量xk时，根据状态转移方程，第（k+1）阶段的状态Sk+1的值也随之而定。也就是说，sk+1将依某种函数关系与（sk,xk（sk））相对应，这种对应关系常记为：12.13.14.一、动态规划方法的基本原理动态规划方法的基本思想：1．动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界条件（简言之为基本方程），要做到这一点，必须先将问题的过程分成几个相互联系的阶段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题化成一族同类型的子问题，然后逐个求解，即从边界条件开始

7、，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。§3动态规划的基本方法15.2．在多阶段决策过程中，动态规划方法是既把前一段和未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的。3．在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优策略所经过的各段状态便可逐次变换得到，从而确定了最优路线。二、动态规划的基本方程动态规

8、划函数基本方程的一般形式为：16.其中“opt”是最优化的意思，视具体的问题可能是求“max”，也可能是求“min”。动态规划最优化原理：“作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。”动态规划最优化原理：“作为整个过程