动态规划讲解+例子.ppt

讲动态规划(DynamicProgramming)动态规划是运筹学的一个分支，是求解多阶段决策过程最优化问题的数学方法。动态规划在经济管理、工程技术、工农业生产及军事部门中都有着广泛的应用，并且获得了显著的效果。学习动态规划，我们首先要了解多阶段决策问题。最短路径问题：给定一个交通网络图如下，其中两点之间的数字表示距离（或运费），试求从A点到G点的最短距离（总运输费用最小）。背包问题有一个徒步旅行者，其可携带物品重量的限度为a公斤，设有n种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？生产决策问题：企业在生产过程中，由于需求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季度地根据库存和需求决定生产计划。根据过程的特性可以将过程按空间、时间等标志分为若干个互相联系又互相区别的阶段。在每一个阶段都需要做出决策，从而使整个过程达到最好的效果。各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展。当各个阶段的决策确定后，就组成了一个决策序列，因而也就决定了整个过程的一条活动路线，这样的一个前后关联具有链状结构的多阶段过程就称为多阶段决策问题。针对多阶段决策过程的最优化问题，美国数学家Bellman等人在20世纪50年代初提出了著名的最优化原理，把多阶段决策问题转化为一系列单阶段最优化问题，从而逐个求解，创立了解决这类过程优化问题的新方法：动态规划。例1、从A地到E地要铺设一条煤气管道,其中需经过三级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？解：整个计算过程分四个阶段，从最后一个阶段开始。首先考虑经过的两条路线AAAAAA动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，它可以把一个n维决策问题变换为几个一维最优化问题，从而一个一个地去解决。需指出：动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算法。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。动态规划方法的关键：在于正确地写出基本的递推关系式和恰当的边界条件（简称基本方程）。要做到这一点，就必须将问题的过程分成几个相互联系的阶段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题转化成一组同类型的子问题，然后逐个求解。即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。2、在多阶段决策过程中，动态规划方法是既把当前一段和未来一段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的.动态规划求解的多阶段问题的特点：每个阶段的最优决策过程只与本阶段的初始状态有关，而与以前各阶段的决策（即为了到达本阶段的初始状态而采用哪组决策路线无关）。换言之，本阶段之前的状态与决策，只是通过系统在本阶段所处的初始状态来影响本阶段及以后各个阶段的决策。或者说，系统过程的历史只能通过系统现阶段的状态去影响系统的未来。具有这种性质的状态称为无后效性（即马尔科夫性）状态。动态规划方法只适用于求解具有无后效性状态的多阶段决策问题。现有数量为a（万元）的资金，计划分配给n个工厂,用于扩大再生产。假设：xi为分配给第i个工厂的资金数量（万元）；gi(xi)为第i个工厂得到资金后提供的利润值（万元）。问题：如何确定各工厂的资金数，使得总的利润为最大。令：fk(x)表示以数量为x的资金分配给前k个工厂，所得到的最大利润值。用动态规划求解，就是求fn(a)的问题。如果a是以万元为资金分配单位，则式中的y只取非负整数0，1，2，…，x。上式可变为：例2：设国家拨给60万元投资，供四个工厂扩建使用，每个工厂扩建后的利润与投资额的大小有关，投资后的利润函数如下表所示。最优策略为（30，20），此时最大利润为105万元。最优策略为（20，20），此时最大利润为90万元。最优策略为（10，0）或（0，10），此时最大利润为20万元。有一个徒步旅行者，其可携带物品重量的限度为a公斤，设有n种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？设xj为第j种物品的装件数（非负整数）则问题的数学模型如下：其递推关系式为：例3：求下面背包问题的最优解物品(xi)物品(xi)物品(xi)2021/5/18所以，最优解为X＝（1.1.0），最优值为Z=13。排序问题指n种零件经过不同设备加工是的顺序问题。其目的是使加工周期