第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

第06章 排队论

排队论起源于 1909 年丹麦电话工程师 A. K.爱尔朗的工作,他对电话通话拥挤问 题进行了研究。1917 年,爱尔朗发表了他的著名的文章—“自动电话交换中的概率理 论的几个问题的解决”。排队论已广泛应用于解决军事、运输、维修、生产、服务、库 存、医疗卫生、教育、水利灌溉之类的排队系统的问题,显示了强大的生命力。 排队是在日常生活中经常遇到的现象,如顾客到商店购买物品、病人到医院看病常 常要排队。此时要求服务的数量超过服务机构(服务台、服务员等)的容量。也就是说, 到达的顾客不能立即得到服务,因而出现了排队现象。这种现象不仅在个人日常生活中 出现,电话局的占线问题,车站、码头等交通枢纽的车船堵塞和疏导,故障机器的停机 待修,水库的存贮调节等都是有形或无形的排队现象。由于顾客到达和服务时间的随机 性。可以说排队现象几乎是不可避免的。 排队论(Queuing Theory)也称随机服务系统理论,就是为解决上述问题而发展 的一门学科。它研究的内容有下列三部分: (i)性态问题,即研究各种排队系统的概率规律性,主要是研究队长分布、等待 时间分布和忙期分布等,包括了瞬态和稳态两种情形。 (ii)最优化问题,又分静态最优和动态最优,前者指最优设计。后者指现有排队 系统的最优运营。 (iii)排队系统的统计推断,即判断一个给定的排队系统符合于哪种模型,以便 根据排队理论进行分析研究。 这里将介绍排队论的一些基本知识,分析几个常见的排队模型。 §1 基本概念 1.1 排队过程的一般表示 下图是排队论的一般模型。 图 1 排队模型 图中虚线所包含的部分为排队系统。各个顾客从顾客源出发,随机地来到服务机构,按 一定的排队规则等待服务,直到按一定的服务规则接受完服务后离开排队系统。 凡要求服务的对象统称为顾客,为顾客服务的人或物称为服务员,由顾客和服务员 组成服务系统。对于一个服务系统来说,如果服务机构过小,以致不能满足要求服务的 众多顾客的需要,那么就会产生拥挤现象而使服务质量降低。 因此,顾客总希望服务 机构越大越好,但是,如果服务机构过大,人力和物力方面的开支也就相应增加,从而 会造成浪费,因此研究排队模型的目的就是要在顾客需要和服务机构的规模之间进行权 衡决策,使其达到合理的平衡。 1.2 排队系统的组成和特征 一般的排队过程都由输入过程、排队规则

  • 2021-10-31
  • 阅读233
  • 下载0
  • 36页
  • pdf