许香敏最优化方法ppt

《许香敏最优化方法ppt》由会员分享，可在线阅读，更多相关《许香敏最优化方法ppt（63页珍藏版）》请在金锄头文库上搜索。

1、第十讲 动态规划 (Dynamic Programming) 动态规划的基本概念和思想 最短路径问题 投资分配问题 背包问题 排序问题1动态规划是运筹学的一个分支，是求解多阶段决策过程最优化问题的数学方法。动态规划在经济管理、工程技术、工农业生产及军事部门中都有着广泛的应用，并且获得了显著的效果。学习动态规划，我们首先要了解多阶段决策问题。2最短路径问题：给定一个交通网络图如下，其中两点之间 的数字表示距离（或运费），试求从A点到G点的最短距离 （总运输费用最小）。123456AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531 3 68 7 6368533842221333 5

2、256 6433背包问题 有一个徒步旅行者，其可携带物品重量的限度 为a 公斤，设有n 种物品可供他选择装入包中。已知每种 物品的重量及使用价值（作用），问此人应如何选择携带 的物品（各几件），使所起作用（使用价值）最大？物品 1 2 j n重量（公斤/件 ）a1 a2 aj an每件使用价值 c1 c2 cj cn类似的还有工厂里的下料问题、运输中的货物装载问题、 人造卫星内的物品装载问题等。4生产决策问题：企业在生产过程中，由于需求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个 生产过程中逐月或逐季度地根据库存和需求决定生产计划。机器负荷分配问题：某种机器可以在高低两种不同

3、的负荷 下进行生产。要求制定一个五年计划，在每年开始时，决 定如何重新分配完好的机器在两种不同的负荷下生产的数 量，使在五年内产品的总产量达到最高。航天飞机飞行控制问题：由于航天飞机的运动的环境是不断变化的，因此就要根据航天飞机飞行在不同环境中的情况，不断地决定航天飞机的飞行方向和速度（状态），使之能最省燃料和完成飞行任务（如软着陆）。5根据过程的特性可以将过程按空间、时间等标志分为 若干个互相联系又互相区别的阶段。 在每一个阶段都需要做出决策，从而使整个过程达到 最好的效果。 各个阶段决策的选取不是任意确定的，它依赖于当前 面临的状态，又影响以后的发展。 当各个阶段的决策确定后，就组成了一个

4、决策序列， 因而也就决定了整个过程的一条活动路线，这样的一 个前后关联具有链状结构的多阶段过程就称为多阶段 决策问题。多阶段决策过程的特点：6针对多阶段决策过程的最优化问题，美国数学家Bellman等 人在20世纪50年代初提出了著名的最优化原理，把多阶段 决策问题转化为一系列单阶段最优化问题，从而逐个求解， 创立了解决这类过程优化问题的新方法：动态规划。对最佳路径（最佳决策过程）所经过的各个阶段，其中每 个阶段始点到全过程终点的路径，必定是该阶段始点到全 过程终点的一切可能路径中的最佳路径（最优决策），这 就是Bellman提出的著名的最优化原理。简言之， 一个最优策略的子策略必然也是最优的

5、。Bellman在1957年出版的Dynamic Programming是动 态规划领域的第一本著作。7例1、从A 地到E 地要铺设一条煤气管道,其中需经过三级 中间站，两点之间的连线上的数字表示距离，如图所示。 问应该选择什么路线，使总距离最短？ 二. 最短路径问题AB2B1B3C1C3D1D2E5214112610104312 1113965810521C28解：整个计算过程分四个阶段，从最后一个阶段开始。第四阶段（D E）： D 有两条路线到终点E 。 显然有AB2B1B3C1C3D1D2E5214112610104312 1113965810521C29首先考虑经过 的两条路线第三阶段

6、（C D）： C 到D 有 6 条路线。(最短路线为 )AB2B1B3C1C3D1D2E521412610104312 1113965810521C210AB2B1B3C1C3D1D2E521412610104312 1113965810521C2(最短路线为 )考虑经过 的两条路线11AB2B1B3C1C3D1D2E521412610104312 1113965810521C2(最短路线为 )考虑经过 的两条路线12AB2B1B3C1C3D1D2E521412610104312 1113965810521C2(最短路线为 )第二阶段（B C）： B 到C 有 9 条路线。首先考虑经过 的3条

7、路线13AB2B1B3C1C3D1D2E521412610104312 1113965810521C2(最短路线为 )考虑经过 的3条路线14AB2B1B3C1C3D1D2E521412610104312 1113965810521C2(最短路线为 )考虑经过 的3条路线15AB2B1B3C1C3D1D2E521412610104312 1113965810521C2(最短路线为 )第一阶段（A B）： A 到B 有 3 条路线。（最短距离为19）16动态规划是用来解决多阶段决策过程最优化的一种数量 方法。其特点在于，它可以把一个n 维决策问题变换为几个 一维最优化问题，从而一个一个地去解决。

8、需指出：动态规划是求解某类问题的一种方法，是考察 问题的一种途径，而不是一种算法。必须对具体问题进行具 体分析，运用动态规划的原理和方法，建立相应的模型，然 后再用动态规划方法去求解。即在系统发展的不同时刻（或阶段）根据系统所处的状 态，不断地做出决策；动态决策问题的特点：系统所处的状态和时刻是进行决策的重要因素；找到不同时刻的最优决策以及整个过程的最优策略。17动态规划方法的关键：在于正确地写出基本的递推关系式和恰当的边界条件（简称基本方程）。要做到这一点，就必须将问题的过程分成几个相互联系的阶段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题转化成一组同类型的子问题，然后逐

9、个求解。即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。182、在多阶段决策过程中，动态规划方法是既把当前一段和未来一段分开，又把当前效益和未来效益结合起来考 虑的一种最优化方法。因此，每段决策的选取是从全局来 考虑的，与该段的最优选择答案一般是不同的.最优化原理：作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面的决策所形成 的状态而言，余下的决策序列必然构成最优子策略。也就 是说，一个最优策略的子策略也是最优的。 3、在求整个问题的最优策略时，由于初始状态是已知的

10、，而每段的决策都是该段状态的函数，故最优策略所 经过的各段状态便可逐段变换得到，从而确定了最优路 线。19动态规划求解的多阶段问题的特点： 每个阶段的最优决策过程只与本阶段的初始状态有关 ，而与以前各阶段的决策（即为了到达本阶段的初始 状态而采用哪组决策路线无关）。换言之，本阶段之 前的状态与决策，只是通过系统在本阶段所处的初始 状态来影响本阶段及以后各个阶段的决策。或者说， 系统过程的历史只能通过系统现阶段的状态去影响系 统的未来。 具有这种性质的状态称为无后效性（即马尔科夫性） 状态。 动态规划方法只适用于求解具有无后效性状态的多阶 段决策问题。20现有数量为a（万元）的资金，计划分配给n

11、 个工厂,用 于扩大再生产。假设：xi 为分配给第i 个工厂的资金数量（万元）； gi(xi)为第i 个工厂得到资金后提供的利润值（万元）。问题：如何确定各工厂的资金数，使得总的利润为最大 。 据此，有下式：三. 投资分配问题21令：fk(x) 表示 以数量为 x 的资金分配给前k 个工厂，所 得到的最大利润值。用动态规划求解，就是求 fn(a) 的问题。当 k=1 时， f1(x) = g1(x) （因为只给一个工厂） 当1kn 时，其递推关系如下：设：y 为分给第k 个工厂的资金（其中 0y x ），此时还 剩 x y（万元）的资金需要分配给前 k1 个工厂,如果采 取最优策略，则得到的最

12、大利润为fk1(xy) ,因此总的利润为：gk(y) fk1(xy) 22如果a 是以万元为资金分配单位，则式中的y 只取非负整 数0，1，2，x。上式可变为：所以，根据动态规划的最优化原理，有下式：23例2：设国家拨给60万元投资，供四个工厂扩建使用，每 个工厂扩建后的利润与投资额的大小有关，投资后的利润函 数如下表所示。投资利润0102030405060g1(x)0205065808585 g2(x)0204050556065 g3(x)0256085100110115 g4(x)0254050606570解：依据题意，是要求 f4(60) 。24按顺序解法计算。 第一阶段：求 f1(x)

13、。显然有 f1(x) g1(x)，得到下表投资 利润0102030405060f1(x) g1(x)0205065808585 最优策略0102030405060第二阶段：求 f2(x)。此时需考虑第一、第二个工厂如何进行 投资分配，以取得最大的总利润。25最优策略为（40，20），此时最大利润为120万元。同理可求得其它 f2(x) 的值。26最优策略为（30，20），此时最大利润为105万元。27最优策略为（20，20），此时最大利润为90万元。最优策略为（20，10），此时最大利润为70万元。28最优策略为（10，0）或（ 0 ， 10 ） ，此时最大利润为 20万元。f2(0) 0。最

14、优策略为（0，0），最大利润为0万元。得到下表最优策略为（20，0），此时最大利润为50万元。29投资 利润0102030405060f2(x)020507090105120 最优策略(0,0)(10,0 ) (0,10 )(20,0) (20,10 )(20,20 )(30,20 )(40,20 )第三阶段：求 f3(x)。此时需考虑第一、第二及第三个工 厂如何进行投资分配，以取得最大的总利润。30最优策略为（20，10，30），最大利润为155万元。同理可求得其它 f3(x) 的值。得到下表31投资 利润0102030405060f3(x)0256085110135155 最优 策略(0,0,0 )(0,0,10 )(0,0,20 )(0,0,30 )(20,0,20 )(20,0,30 )(20,10,30 )第四阶段：求 f4(60)。即问题的最优策略。32最优策略为（20，0，30，10），最大利润为160万元。33有一个徒步旅行者，其可携带物品重量的限度为a 公斤，设 有n 种物品可供他选择装入包中。已知每种物品的重量及使用 价值（作用），问此人应如何选择携带的物品（各几件），使 所起作用（使用价值）最大？物品 1 2 j n重量（公斤/件） a