第04章 动态规划

动态规划的发展及研究内容 动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20 世纪 50 年代初 R. E. Bellman 等人在研究多阶段决策过 程(multistep decision process)的优化问题时,提出了著名的最优性原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,逐个求解,创立了解决这类过程 优化问题的新方法—动态规划。1957 年出版了他的名著《Dynamic Programming》,这 是该领域的第一本著作。 动态规划问世以来,在经济管理、生产调度、工程技术和最优控制等方面得到了广 泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题,用动 态规划方法比用其它方法求解更为方便。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但是一些与时 间无关的静态规划(如线性规划、非线性规划),只要人为地引进时间因素,把它视为 多阶段决策过程,也可以用动态规划方法方便地求解。 应指出,动态规划是求解某类问题的一种方法,是考察问题的一种途径,而不是 一种特殊算法(如线性规划是一种算法)。因而,它不象线性规划那样有一个标准的数 学表达式和明确定义的一组规则,而必须对具体问题进行具体分析处理。因此,在学习 时,除了要对基本概念和方法正确理解外,应以丰富的想象力去建立模型,用创造性的 技巧去求解。 例 1 最短路线问题 图 1 是一个线路网,连线上的数字表示两点之间的距离(或费用)。试寻求一条由 A 到G 距离最短(或费用最省)的路线。 图 1 最短

  • 2021-10-31
  • 阅读221
  • 下载0
  • 12页
  • pdf

第05章 图与网络

§1 概论 图论起源于 18 世纪。第一篇图论论文是瑞士数学家欧拉于 1736 年发表的“哥尼 斯堡的七座桥”。1847 年,克希霍夫为了给出电网络方程而引进了“树”的概念。1857 年,凯莱在计数烷CnH2n+2 的同分异构物时,也发现了“树”。哈密尔顿于 1859 年提 出“周游世界”游戏,用图论的术语,就是如何找出一个连通图中的生成圈、近几十年 来,由于计算机技术和科学的飞速发展,大大地促进了图论研究和应用,图论的理论和 方法已经渗透到物理、化学、通讯科学、建筑学、运筹学,生物遗传学、心理学、经济 学、社会学等学科中。 图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示 这些具体事物,用连接两点的线段(直的或曲的)表示两个事物的特定的联系,就得到 了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了 一个数学模型,借助于图论的概念、理论和方法,可以对该模型求解。哥尼斯堡七桥问 题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结 起来,问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次,再回到起点。 图 1 哥尼斯堡七桥问题 当然可以通过试验去尝试解决这个问题,但该城居民的任何尝试均未成功。欧拉为了解 决这个问题,采用了建立数学模型的方法。他将每一块陆地用一个点来代替,将每一座 桥用连接相应两点的一条线来代替,从而得到一个有四个“点”,七条“线”的“图”。 问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特 点,给出了一笔画的一个判定法则:这个图是连通的,且每个点都与偶数线相关联,将 这个判定法则应用于七桥问题,得到了“不可能走通”的结果,不但彻底解决了这个问 题,而且开创了图论研究的先河。 图与网络是运筹学(Operations Research)中的一个经典和重要的分支,所研究的 问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等 诸多领域。下面将要讨论的最短路问题、最大流问题、最小费用流问题和匹配问题等都 是图与网络的基本问题。 我们首先通过一些例子来了解网络优化问题。 例 1 最短路问题(SPP-shortest path problem) 一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地

  • 2021-10-31
  • 阅读216
  • 下载0
  • 50页
  • pdf