吉林大学本科运筹学.ppt

《吉林大学本科运筹学.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章动态规划动态规划的基本方法动态规划应用举例1清华大学出版社动态规划什么是动态规划解决多阶段决策过程最优化的一种数学方法。动态规划的形成产生于20世纪50年代。1951年美国数学家贝尔曼(R.Bellman)等人，根据一类多阶段决策问题的特点，把多阶段决策问题变换为一系列互相联系的单阶段问题，然后逐个加以解决。与此同时，他提出了解决这类问题的“最优性原理”，研究了许多实际问题，从而创建了解决最优化问题的一种新的方法——动态规划。动态规划的应用在工程技术、企业管理、工农业生产及军事等部门中都有广泛的应用，并且获得了显著的效果。2清华大学出版社动态规划动态规划在企业管理中的

2、主要应用领域最优路径问题资源分配问题生产调度问题库存问题装载问题排序问题设备更新问题生产过程最优控制问题等等动态规划是求解某类问题的一种方法，是考查问题的一种途径，而不是一种特殊算法(如线性规划是一种算法)。因而，它不像线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。3清华大学出版社动态规划动态规划模型的分类根据多阶段决策过程的时间参量是离散的还是连续变量，分为离散决策过程和连续决策过程。根据决策过程的演变是确定性的还是随机性的，又可分为确定性决策过程和随机性决策过程。组合起来可分为离散确定性离散随机性连续确定性连续随机性本书主要研

3、究离散确定性决策过程。4清华大学出版社第8章动态规划的基本方法第1节多阶段决策过程及实例第2节动态规划的基本概念和基本方程第3节动态规划的最优性原理和最优性定理第4节动态规划和静态规划的关系5清华大学出版社第1节多阶段决策过程及实例例1最短路线问题给定一个线路网络，两点之间连线上的数字表示两点间的距离(或费用)，试求一条由A到G的铺管线路，使总距离为最短(或总费用最小)。6清华大学出版社第1节多阶段决策过程及实例多阶段决策过程在生产和科学实验中，有一类活动的过程，由于它的特殊性，可将过程分为若干个互相联系的阶段，在它的每一个阶段都需要作出决策，从而使整个过程达到最好的活动效

4、果。因此，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展。当各个阶段决策确定后，就组成了一个决策序列，因而也就决定了整个过程的一条活动路线。这种把一个问题可看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，也称序贯决策过程。7清华大学出版社第1节多阶段决策过程及实例例2机器负荷分配问题某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u1的关系为g=g(u1)这时，机器的年完好率为a，即如果年初完好机器的数量为u，到年终时完好的机器就为au，0＜a＜1，在低负荷下生产时，产品的年产量

5、h和投入生产的机器数量u2的关系为h=h(u2)相应的机器年完好率为b,0＜b＜1。假定开始生产时完好的机器数量为s1。要求制定一个五年计划，在每年开始时，决定如何重新分配完好的机器在两种不同的负荷下生产的数量，使在五年内产品的总产量达到最高。8清华大学出版社第2节动态规划的基本概念和基本方程例1中求A到G的最短路线问题是动态规划中一个典型例子。现通过讨论它的解法，说明动态规划方法的基本思想，并阐述有关基本概念。由图8-2可知，从A点到G点可以分为6个阶段。在第一阶段，A为起点，终点有B1、B2两个，因而这时走的路线有两个选择，一是走到B1；一是走到B2，若选择走到B2的决

6、策，则B2就是第一阶段决策的结果。它既是第一阶段路线的终点，又是第二阶段路线的始点。在第二阶段，再从B2点出发，有一个可供选择的终点集合｛C2，C3，C4｝；若选择由B2走至C2，则C2就是第二阶段的终点，同时又是第三阶段的始点。递推下去可看到：各个阶段的决策不同，路线就不同。显然，当某阶段的始点给定后，会影响后面各阶段的行进路线和整个路线的长短，而后面各阶段路线的发展不受这点以前各阶段决策的影响。故此问题的要求是：在各个阶段上选则一个恰当的决策，使得由这些决策组成的一个决策序列所决定的一条路线是总路程最短的一条。9清华大学出版社2.1动态规划的基本概念1．阶段把所给问题的

7、过程，恰当地分为若干个相互联系的阶段，以便能按一定的次序去求解。描述阶段的变量称为阶段变量，常用k表示。阶段的划分，一般是根据时间和空间的自然特征来划分，但要便于把问题的过程能转化为多阶段决策的过程。如例1可分为6个阶段来求解，k分别等于1、2、3、4、5、6。10清华大学出版社2.1动态规划的基本概念2．状态状态表示每个阶段开始所处的自然状况或客观条件，它描述了研究问题过程的状况，又称不可控因素。在例1中，状态就是某阶段的出发位置。它既是该阶段某支路的起点，又是前一阶段某支路的终点。通常一个阶段有若干个状态，第一