8.动态规划.ppt

1第八章动态规划(Dynamic Programming) ?学习目标?了解动态规划的研究对象及特点; ?理解动态规划的基本概念; ?掌握最优化原理与动态规划模型; ?掌握动态规划的建模过程; ?理解动态规划的求解要求; ?(常见的动态规划问题)掌握动态规划的求解方法与技巧。 2第八章动态规划(Dynamic programming) ?五十年代贝尔曼(B. E. Bellman) 为代表的研究成果?属于现代控制理论的一部分?以长远利益为目标的一系列决策?最优化原理,可归结为一个递推公式 3 第一节多阶段决策过程及实例一、多阶段决策过程在生产和科学试验中,有一类活动的过程,由于它的特殊性, (1) 可将过程分为若干个互相联系的阶段, (2) 在它的每一个阶段都需要作出决策, (3) 从而使整个过程达到最好的活动效果。各个阶段的选取不是任意的,它依赖于当前面临的状态,又影响以后的发展。当各个阶段的决策确定后,就组成了一个决策序列。这种可以把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程,也称序贯决策过程。这种问题就称为多阶段决策问题。状态 12 …… n 状态状态状态状态决策决策决策 4 在多阶段决策问题中,各个阶段采取的决策,一般来说是与时间有关的,决策依赖于当前的状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来的,故有“动态”的含义。因此,把处理它的方法称为动态规划方法。但是,一些与时间没有关系的静态规划问题,只要人为的引进“时间”因素, 也可把它视为多阶段决策问题,用动态规划方法去处理。需指出:动态规划是求解某类问题的一种方法,是考察问题的一种途径,而不是一种算法。必须对具体问题进行具体分析,运用动态规划的原理和方法,建立相应的模型,然后再用动态规划方法去求解。 5 通常的决策问题分为两大类: 静态决策动态决策不考虑时间的变化,一次性决策。考虑时间的变化,多阶段决策。 6 例 1 如下图,给定一个线路网络,两点之间连线上的数字表示两点间的距离(或费用),试求一条由 A到G的铺管线路,使总距离为最短(或总费用最小)。二、多阶段决策过程实例 B 1A C 3F 2F 1E 3E 2E 1D 3D 2D 1C 4 C 2C 1B 2G 53 136876 683534 2138 2233 355266 437 贪心算法?每一步都走最短的线路: A —B 2—C 4—D 3—E 2—F 2—G,长度为 21 ?最短的线路: A —B 1—C 2—D 1—E 2—F 2—G,长度为 18 B 1A C 3F 2F 1E 3E 2E 1D 3D 2D 1C 4 C 2C 1B 2G 53 136876 683534 2138 2233 355266 438枚举法?列出每条可能的路线,然后算出每条路的长度,从中选择最优路线。?缺点是线路太多,随点数增加很快。 B 1A C 3F 2F 1E 3E 2E 1D 3D 2D 1C 4 C 2C 1B 2G 53 136876 683534 2138 2233 355266 439动态规划 B 1A C 3F 2F 1E 3E 2E 1D 3D 2D 1C 4 C 2C 1B 2G 53 136876 683534 2138 2233 355266 43 43 759 768 13 10 9 12 13 16 18 该点到 G点的最短距离第一阶段第二阶段第三阶段第四阶段第五阶段第六阶段从G到A的解法称为逆序解法从 A 到G的解法称为顺序解法 10 ?例2(机器负荷分配问题) 某企业拥有完好的机器 y台,将它们按照高负荷和低负荷两种生产方式生产,已知收益函数分别是: g=g(x) 和 h=h(x) x 为机器数量。设高负荷下生产时机器的年完好率为a,低负荷下生产时机器的年完好率为 b(0≤a≤1, 0≤b≤1) 问:对总数量为 y的机器进行分配用于生产,试制定一个五年计划,应如何分配每年投入高负荷和低负荷的机器数量,才能使总收益最大?( n个阶段的决策问题)