第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
  • 阅读230
  • 下载0
  • 12页
  • pdf

第05章 图与网络

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

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

第06章 排队论

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

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

第09章 插值与拟合

插值:求过已知有限个数据点的近似函数。 拟合:已知有限个数据点,求近似函数,不要求过已知数据点,只要求在某种意义 下它在这些点上的总偏差最小。 插值和拟合都是要根据一组数据构造一个函数作为近似,由于近似的要求不同,二 者的数学方法上是完全不同的。而面对一个实际问题,究竟应该用插值还是拟合,有时 容易确定,有时则并不明显。 §1 插值方法 下面介绍几种基本的、常用的插值:拉格朗日多项式插值、牛顿插值、分段线性插 值、Hermite 插值和三次样条插值。 1.1 拉格朗日多项式插值 1.1.1 插值多项式 用多项式作为研究插值的工具,称为代数插值。其基本问题是:已知函数 f (x)在 区间[a,b]上n +1个不同点 x0 , x1 ,L, xn 处的函数值 yi = f (xi) (i = 0,1,L,n) ,求一个 至多n 次多项式 ? n (x) = a0 + a1x +L+ an x n (1) 使其在给定点处与 f (x)同值,即满足插值条件 ? n (xi) = f (xi) = yi (i = 0,1,L,n) (2) ? n (x)称为插值多项式,xi(i = 0,1,L,n) 称为插值节点,简称节点,[a,b]称为插值区 间。从几何上看,n 次多项式插值就是过n +1个点(xi , f (xi)) (i = 0,1,L,n) ,作一条 多项式曲线 y = ? n (x) 近似曲线 y = f (x) 。 n 次多项式(1)有n +1个待定系数,由插值条

  • 2021-10-31
  • 阅读238
  • 下载0
  • 26页
  • pdf

第07章 对策论

§1 引言 社会及经济的发展带来了人与人之间或团体之间的竞争及矛盾,应用科学的方法来 解决这样的问题开始于 17 世纪的科学家,如 C.,Huygens 和 W.,Leibnitz 等。现代对 策论起源于 1944 年 J.,Von Neumann 和 O.,Morgenstern 的著作《Theory of Gamesand Economic Behavior》。 对策论亦称竞赛论或博弈论。是研究具有斗争或竞争性质现象的数学理论和方法。 一般认为,它既是现代数学的一个新分支,也是运筹学中的一个重要学科。对策论发展 的历史并不长,但由于它所研究的现象与人们的政治、经济、军事活动乃至一般的日常 生活等有着密切的联系,并且处理问题的方法又有明显特色。所以日益引起广泛的注意。 在日常生活中,经常看到一些具有相互之间斗争或竞争性质的行为。具有竞争或对 抗性质的行为称为对策行为。在这类行为中。参加斗争或竞争的各方各自具有不同的目 标和利益。为了达到各自的目标和利益,各方必须考虑对手的各种可能的行动方案,并 力图选取对自己最为有利或最为合理的方案。对策论就是研究对策行为中斗争各方是否 存在着最合理的行动方案,以及如何找到这个合理的行动方案的数学理论和方法。 §2 对策问题 对策问题的特征是参与者为利益相互冲突的各方,其结局不取决于其中任意一方的 努力而是各方所采取的策略的综合结果。 先考察一个实际例子。 例 1(囚徒的困境) 警察同时逮捕了两人并分开关押,逮捕的原因是他们持有大 量伪币,警方怀疑他们伪造钱币,但没有找到充分证据,希望他们能自己供认,这两个 人都知道:如果他们双方都不供认,将被以持有大量伪币罪被各判刑 18 个月;如果双 方都供认伪造了钱币,将各被判刑 3 年;如果一方供认另一方不供认,则供认方将被从 宽处理而免刑,但另一方面将被判刑 7 年。将嫌疑犯 A 、 B 被判刑的几种可能情况列 于表 1。

  • 2021-10-31
  • 阅读183
  • 下载0
  • 13页
  • pdf