第7章、第8章复习汇编.ppt

第七章 动态规划（Dynamic Programming）;内容提要; 1、 生产与存储问题 工厂每月供应市场一定数量 的产品 ，并将所余产品 存入仓库。一般某月适当增加产量可降低生产成本，但超产部分存入仓库会增加库存费用。要求确定一个逐月的生产计划，在满足需求条件下，使一年的生产与存贮费用之和最小; 2、机器负荷分配问题; 3、投资决策问题 某公司有资金Q万元，在今后5年内考虑给A\B\C\D4个项目投资，这些项目的投资回收期、回报率均不相同，问该公司如何确定这些项目每年的投资额，使到第5年末拥有资金的本利总额最大。;内容提要;§2动态规划的基本概念和基本原理;　;解：可列出静态规划问题的模型如下; 分阶段：; 基本方程;内容提要;一、 背包问题;二、 生产与存贮问题 ; 设有某种原料，总数量为 a，用于生产 n 种产品。若分配数量 xi 用于生产第 i 种产品，其收益为 gi ( xi )，问应如何分配，才能使生产 n 种产品的总收入最大？; 例3 某公司拟将5台某种设备分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备，可以为公司提供的盈利如表。 问：这五台设备如何分配给各工厂，才能使公司得到的盈利最大。 ;第七章 动态规划 （Dynamic Programming）;第八章 图与网络分析;图与网络分析;图与网络的基本概念;图与网络的基本概念;;链：对于无向图G =（V,E）, 称顶点和边交替的序列 ;连通图：图中任意两点之间均至少有一条通路，否则称为不连通图。 ; 图的图形表示法在较为简单的情况下由于比较直观，所以有一定的优越性，但对于比较复杂的图这种表示方法就不太方便了。故目前一般多用矩阵方法表示图。由于这种方法表示简单，使用方便，目前应用较为普遍。更重要的是，它把图的问题变成为数学计算问题，因而对图的研究可借助于计算机来实现。图的矩阵表示法有权矩阵、邻接矩阵、关联矩阵、回路矩阵等，这里仅介绍其中的两种。;定义：对于网络（赋权图）G=（V，E），其中边 有权 ，构造矩阵 ，其中： 称矩阵A为网络G的权矩阵。;例 如图所示，其权矩阵为： ;定义 设??G=（V，E）中顶点的个数为n，构造一个矩阵 ，其中： 称矩阵A为网络G的邻接矩阵。;邻接矩阵为： 因为G是无向图，所以邻接矩阵是对称的。;图与网络分析;一、树的概念和性质 在各种各样的图中，有一类图是十分简单又非常具有应用价值的图，这就是树。 例已知有 5个城市，要在它们之间架设电话线网，要求任何两个城市都可以彼此通话（允许通过其他城市），并且电话线的条数最少。;图的生成树;最小生成树的定义—— 一颗生成树上所有树枝上权的总和，称为这个生成树的权。具有最小权的生成树为最小生成树。;最小生成树的求法－避圈法;最小生成树的求法－破圈法;图与网络分析;最短路径问题; (Dijkstra)算法 它是在1959年提出来的。目前公认，在所有的权wij ≥0时，这个算法是寻求最短路问题最好的算法。并且，这个算法实际上也给出了寻求从一个始定点vs到任意一个点vj的最短路。;算法步骤：;3.比较所有具有T标号的节点，把最小者改为P标号，即： 当存在两个以上最小者时，可同时改为P标号。若全部节点均为P标号，则停止，否则用vk代替vi，返回步骤（2）。;例;最短路径的应用——设备更新;解：用点vi表示第i年年初购进一台新设备，虚设点v6，表示第六年年初，即第五年年底。 则，边（vi，vj）表示第i年购进的设备一直使用到第j年年初，边上的数字表示该机器从使用到报废支付的总费用。;v1;最短路径的应用——设备更新;最短路径的应用——设备更新;图与网络分析; 在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题等等。而网络系统最大流问题是图与网络流理论中十分重要的最优化问题，它对于解决生产实际问题起着十分重要的作用。 ;对任一G中的边（vi,vj）有流量 fij,称集合f={fij} 为网络G上的一个流。满足下列条件的流f称为可行流 （1）容量限制条件：对于每一条边（vi ,vj）,有 0 ? fij ? cij . （2）平衡条件： 对中间点vi 有 　　　（流入量等于流出量） 对收、发点vs vt，有 ;网络最大流问题——相关概念;网络最大流问题——相关概念