（应用数学专业论文）物流工程调度的最小贴现成本方法.pdf

ab s t r a c t i n t h e d e v e l o p m e n t o f e c o n o m i c s , t h e d e c i s i o n - m a k e r s o ft e n n e e d t h e i r k n o w l e d g e i n o p e r a t i o n a l r e s e a r c h a n d m a n a g e m e n t t o s o l v e a l a r g e n u m b e r o f c o m p l i c a t e d f u n d p l a n n i n g p r o b l e m s . a n d t h e n t h e p r o b l e m i n m a n a g i n g t h e e x p a n d i n g l o a n t h a t m e e t s t h e d e m a n d o f t h e m a r k e t w i l l d e r i v e o n e k i n d o f s e q u e n c i n g p r o b l e m s i n c l u d i n g p r o d u c t i v ity e x p a n d i n g , w h i c h i s t h e e x t e n s i o n o f o n e - d i m e n s i o n a l s e q u e n c i n g p r o b l e m s . t h e e ff e c t i v e m e t h o d o f s o l v i n g t h e p r o b l e m s o f o n e - d i m e n s i o n a l s e q u e n c i n g p r o b l e m s i s t h e d y n a m i c p r o g r a m m i n g o f e m b e d d i n g i n t h e s t a t e s p a c e . l o g i s t i c s i s a n i m p o r t a n t i n d u s t ry i n t h e n a t i o n a l d e v e l o p m e n t o f e c o n o m i c s . h t h e p r o c e s s o f i n f r a s t r u c t u r e c o n s t r u c t i o n a n d o p e r a t i o n m a n a g e m e n t , w e o ft e n e n c o u n t e r a s e r i e s o f i m p o r ta n t i s s u e s t o d e c i d e . t h e d y n a m i c p r o g r a m m i n g i s t h e m o s t o p t im i z e d o p e r a t i o n a l re s e a r c h b r a n c h e s in s t u d y i n g a m u lt i - s t a g e d e c i s i o n m a k i n g p r o c e s s . i n m y p a p e r i s y s t e m a t i c a l l y i n t r o d u c e t h e b a s i c i d e a s o f t h e d y n a m i c p ro g r a m m i n g a n d d e s c r ib e t h e d y n a m i c p r o g r a m m i n g o f e m b e d d i n g i n t h e s t a t e s p a c e i n d e ta i l . t h e s e a r e a p p l i e d t o t h e d e p l o y m e n t o f l o g i s t i c s p ro j e c t ， a n d s o l v e t h e m in i m u m d i s c o u n t e d c o s t i n t h e d e p l o y m e n t o f l o g i s t i c s p r o j e c t . wi t h t h e a i d o f t h e c o m p u t e r , t h e d y n a m i c p r o g r a m m i n g o f e m b e d d i n g i n t h e s t a t e s p a c e c a n w o r k o u t t h e b e s t i n v e s t m e n t s c h e m e e ff e c t i v e l y , e s p e c i a l l y i n t h e l a r g e a n d l o n g t e r m i n v e s t m e n t i s s u e s . s o it i s r e a l i s t i c a l l y m e a n in g f u l f o r u s t s t u d y t h e m i n i m u m d i s c o u n t e d c o s t i n t h e d e p l o y m e n t o f l o g i s t i c s p r o j e c t b y u s i n g t h i s m e t h o d . k e y w o r d s : l o g i s t i c s r e p l a c e m e n t d e p l o y m e n t d y n a m i c p rog r a m m in gi n t h e s t a t e s p a c e n 南开大学学位论文版权使用授权书 本人完全了 解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容:按照学校要求提交学位论文的印刷本和电子版 本;学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、 数字化或其它手段保存论文; 学校有权提供目 录检索以及提供 本学位论文全文或者部分的阅览服务; 学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电 子版; 在不以赢利为目 的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学 位 论 文 作 者 签 名 ，i -t, l .5 、 诺 年1 1 月才日 -. . . . . 月 . 叫 . . . . . . . 目 . . . . . . 目 . . . . . . 内 目 . . . 门 . 门 . 叫 . 户 目 . . . 月 . 闷 . . 目 . . . 月 . . 娜 目 . ， . .， . ， ， 月 . .月 . . . . ， . . . . 目 . ， . . . 口 月 口 . . . . . . . ， 门 . 妇 . . j . 门 . . . 闷 ， 目 . . . . . . 门 娜 . . . . 月 . . . 月 . . . . . 月 . . . . . . 经指导教师同意， 本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名: 学位论文作者签名: 解密时间: 年月日 各密级的最长保密年限及书写格式规定如下: .了，1户，魂.，月，j 尸 气尸， 一气， 门 -， 一，甲 沪 户 咋种户 一 产广夕一2一 公了 ， r了 飞 一一 分 内 部 5 年( 最 长5 年。 可 少 于5 年) 厂 二 秘密1 0 年 ( 最长1 0 年， 可少于1 0 年) 妙 * 岭 煲 印 年 ，秒 于 20 年 ， 一、- 南开大学学位论文原创性声明 本人郑重声明: 所呈交的学位论文， 是本人在导师指导下， 进行 研究工作所取得的成果。 除文中己经注明引用的内 容外， 本学位论文 的研究成果不包含任何他人创作的、 已 公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体， 均己 在文中以明 确方式标明。 本学位论文原创性声明的 法律责任 由本人承担。 学位论文作者签名: w 年 i -ta , 叔 f l 月 才 日 第一章引言 第一章引言 在经济发展中，大量复杂的资金规划问 题常常需要决策者借助于运筹学、 管理学等方法来解决。 这当中， 满足市场需求的扩大贷款管理问 题等可以 提出 一类含生产力扩充的排序问题，它是一维排序问题的推广。物流工程调度的最 小贴现成本问题就是含生产力扩充的排序问 题，而解决一维排序问题的行之有 效的方法是嵌入状态空间的动态规划方法。 物流是国民经济发展的重要产业，发展现代物流对于提高国民经济运行的 质量和效益，优化资源配置，改善投资环境，促进企业结构调整，提高我国经 济实力，具有十分重要的意义。 动态规划是研究多阶段决策过程最优化的运筹学分支。有些经营管理活动 由 一系列相互关联的阶段组成，在每个阶段依次进行决策，而且上一阶段的输 出状态就是下一阶段的输入状态，各阶段决策之间互相关联，因而构成一个多 阶段的决策过程。动态规划研究多阶段决策过程的总体优化，即从系统总体出 发，要求各个阶段决策所构成的决策序列使目 标函数值达到最优。 嵌入状态 空间的 动态 规 划方 法d p 2 是m o r in 和e s o g b u e 于1 9 7 1 年提出的 一 种算法，是解决一维排序问题非常有效的方法，与传统的动态规划方法d p i 比 较缩减了计算量。 本文系统地介绍了 动态规划的 基本思想， 详细地论述了嵌入状态空间的动态 规划方法d p 2 ，不仅用嵌入状态空间的动态规划方法d p 2 研究了物流工程调度 的最小贴现成本问 题，而且在大规模问 题和多维排序问 题上进行了 理论上的研 究: 并尝试用c语言对物流工程调度的最小贴现成本问 题进行程序设计，这不 仅对物流工程调度的最小贴现成本方法的 研究有了新的突破，而且对一类含生 产力扩充的排序问题有了新的研究方向。 第二章 现代物流概述 第二章现代物流概述 随着科学技术的迅猛发展和经济全球化趋势的增强，世界各国经济发展面 临着前所未有的机遇与挑战。现代物流作为现代经济的重要组成部分，在国民 经济和社会发展中发挥着重要作用。 第一节物流的概念及特征 “ 物流” 一词源于国外，最早出 现于美国。它最初来自 美国 在第二次世界 大战期间，为使军需物资供应快速而合理，所使用的一个术语 ( p h y s i c a l d i s t ri b u ti o n ) 。 在 经济界 使 用“ p h y s i c a l d i s t r i b u ti o n ”是第 二次 世界 大战以 后， 原 意是指“ 物流的 分发” 。 美国 从2 0 世纪6 0 年 代 逐渐用“ l o g i ti c s ( 后勤) 一 词取 代了“ p h y s i c a l d i s t r i b u t io n 一词， 2 0 世 纪7 0 年代日 本引 进并 将其翻 译为 “ 物流气 我国引入“ 物流” 这个概念是在2 0 世纪7 0 年代， 广泛应用是9 0 年代以 后。 2 0 0 1 年公布的中华人民共和国国家标准 物流术语(gb/i 1 8 3 5 4 - 2 0 0 1 )中明 确指出，物流即“ 物品从供应地向接收地的实体流动过程。根据实际需要， 将 运输、存储、 装卸、搬运、 包装、流通加工、配送、信息处理等基本功能实现 有机结合气 社会生产力的发展推动着物流的发展。第二次世界大战后，随着计算机技 术、 信息技术的飞速发展， 供应链的思想、系统化的 观念成为物流的新理念， 发达国家企业掀起回归主业、集中力量于核心业务的高潮，专门从事第三方物 流服务的企业成批涌现， 标志着物流步入现代物流的新阶段。 现代物流是相对于传统物流而言的。它是在传统物流的技术上，引入高科 技手段，即运用计算机进行信息联网，并对物流信息进行科学管理，从而使物 流速度加快、 准确率提高、 库存减少、 成本降低，以 此延伸和放大传统物流的 功能。 现代物流是根据客户的需要， 运用系统观念，以 最经济的费 用， 将运输、 存储、装卸、搬运、包装、流通、加工、 配送、信息处理等基本功能实现有机 结合，形成完整的供应链，为用户提供多 功能、一体化的综合性服务。现代物 第二章现代物流概述 流的特征可以概括为以下几方面: ( 1 ) 物流系统化 物流系统化是系统科学在物流管理中 应用的结果。系统科学在物流领域中 得到广泛的应用，人们利用系统科学的思想和方法建立物流系统，包括社会物 流系统和企业物流系统。从系统科学的角度讲，物流也是社会大系统的一部分。 物流系统不是运输、储存、 包装等子系统的简单叠加， 而是通过彼此的内 在联系，在共同目 的下形成的一个系统。构成系统的功能要素之间存在着相互 作用的关系。 ( 2 ) 物流网 络化 物流网络化是指利用电子网络技术进行物流信息交换，根据物流网络的发 展需要，企业运用网络技术建立起信息网络。 物流网络是建立在工商企业网络 和 交 通 运 输网 络 基 础 上 的 ， 并 在 此 基 础 上 形 成 全国 性、 区 域 性 及 至 全 球 性 的 分 销和物流配送网络。 ( 3 ) 物流精益化 精益化生产方式是由日 本企业创立的生产方式，精益生产涉及准时化生产、 全面质量管理、团体作业等工作方式。精益化的核心思想是以尽可能少的生产 要素 ( 如人力、物力、财力、时间和空间) 创造出尽可能多的客户需求价值。 物流精益化运作的基本原则是降低成本，提高价值，以顾客或用户为市场链， 创造价值链、作业过程无缝连接的供应链。 ( 4 ) 物流信息化 现代物流可以 理解为物资的物理性流通与信息流通的结合，信息在实现物 流系统化、物流作业一体化方面发挥着重要作用。 传统物流的各个功能要素之间缺乏有机的联系，对物流活动的控制往往是 事后控制。 而现代物流通过信息将各项物流功能活动有机结合在一起，通过信 息可以 控制物流系统按照预定的目 标运行。准确地掌握信息，如库存信息、需 求信息，可以 减少非效率、非增值的物流活动，提高物流效率和物流服务的可 能性。 ( 5 ) 物流整体最优化 物流管理追求的是物流系统的 最优化， 物流系统的最优化包括物资资源最 优化、客户资源最优化、业务流程最优化、 操作规程最优化、供应链管理最优 化、组织结构最优化、物流功能最优化和运输线路最优化。 第二章现代物流概述 物流系统的最优化在成本管理上体现为物流总成本最小化，物流总成本最 小化是物流合理化的重要标志。传统的管理方法将注意力集中于尽可能使每一 项个别物流活动成本最小化，而忽视了物流总成本，忽视了各项之间的相互关 系。 现代物流建立在降低物流总成本的基础之上， 利用物流要素之间存在的效 益背反关系，通过物流各个功能活动的相互配合和总体协调达到物流总成本最 小化的目的。 第二节 物流在国民经济中的地位和作用 2 . 2 . 1 物流在国民经济中的地位 第一，物流是国民 经济的动脉，是连接国民 经济各个部分的纽带。 一个国家的经济是由 众多的产业、部门 和企业组成的整体， 而这些部门、 企业优势分布在全国不同的地区，属于不同的所有者。物流通过不断输送各种 物质产品，使生产者不断获得原材料、姗料以 保证生产过程的正常进行，同时 又不断将产品运送给不同需求者，使这些需求者的生产、生活得以正常进行。 这些相互依赖的实体，是靠物流来联系的， 物流使国民经济成为一个有内 在联 系的整体。 第二，物流技术的进步与发展是决定国民经济生产规模和产业结构变化的 重要因素。 物流技术的进步和发展促进了我国生产的 社会化、专业化、规范化。畅通 的物流有利于社会分工和生产的集中化、规模化。许多大的社会分工、地区分 工受到物流的制约， 对物流提出更高的要求，也有许多产业是在物流提供了该 产业与消费者的联系条件之后才发展起来的。 第三， 物流是企业不断进行生产的前提保证， 又是实现商品流通的基础口 国民经济是一个不断生产和不断消费的循环过程。物流是企业不断地进行 生产的外部环境和前提保证。 在生产企业内 部， 各种物质资料在各个生产场所 和工序间的相继传递，是靠生产工艺中不断的物流活动完成的，物流是保证企 业生产顺利进行的前提条件。 物流是实现商品流通的物质基础。商品流通是商流与物流的有机结合，没 第二章现代物流概述 有畅通的物流，就无法完成商品流通过程。物流能力的大小，如运输、包装、 储存等能力的大小，直接决定了商品流通的规模和速度，物流是保证市场上商 品供给的重要因素。 2 . 2 . 2 物流在国民经济中的作用 物流构成商品流通的物质内容，没有物流，就无法实现商品流通，社会再 生产也无法进行。物流活动的合理化以及物流费用的节减，对于稳定物价、促 进生产和消费的协调发展起到重要的作用.从国民经济整体来看，物流费用在 国内生产总值 ( g d p )中所占比重还是相当高的。物流在国民 经济中的作用主 要体现在以 下几方面: 第一，合理的 物流可以 使商品的 价值和使用价值得以 实 现。 物流是实现商品价值和使用价值的条件。无论是生产资料还是生活资料， 在其进行生产性消费 之前，其价值和使用价值都是潜在的。 物流是把这种潜在 的价值和使用价值变成现实的价值和使用价值的关键。 合理的物流能按生产的需要及时为企业生产提供劳动资料和劳动对象，从 而促进生产的迅速发展。物流可以 将生产资料按质按量齐备地供应给生产企业， 实现其价值和使用价值。 合理的 物流可以 将企业的生活资料及时、 准确地送到消费者手中，实现其 价值和使用价值。 物流一方面可以 有效地促进资 金的周转、货币的回笼， 促进 社会再生产的进行，另一方面，物流又可以不断地满足消费者对生活资料的需 求， 提高人民生活质量。 第二，合理的物流可以 最大限度地满足社会和劳动者的物质和文化的需求。 合理的物流既可以最大限度地满足社会和劳动者日 益增长的物质和文化需 要， 还可以 促进人们的思想开放、观念更新。 合理的物流会使地区经济与外界 交流活跃，增加人员的交往，因而极有利于开拓视野、启迪思维，促进观念更 新，促进社会进步。 第三，合理的物流可以提高经济效益， 起到第三利润源泉的作用。 在物流过程中 始终要消耗和占 有一定的生产资料， 合理的物流能够节约大 量的生产资料。对物流过程进行合理控制，不仅可以减少生产资料在流通环节 的损耗，而且还可以在生产资料综合利用、节约代用、加工改制等方面起作用， 第二章现代物流概述 充分发挥生产资料的效用。 合理的物流能消除迂回运输、相向运输、过远运输等不合理运输，在节约 运力方面发挥重要作用， 增加企业效益。一切不合理的 运输都会延长商品的 运 输时间，增大在途物资的数量，增加企业成本。 合理的物流可以控制企业的商品库存，减少不必要的物资储存，加速物资 周转，更好地发挥现有物资的效用。在物资资源量不变的情况下，停留在流通 过程中的物资越多，停留时间越长，社会占用资金越多，投入消费的物资越少， 其效用发挥越少。同时，储存在仓库中的物资或多或少都会有价值损失，还要 增加储存费 用， 合理的 物流会使这种损失降 到最低限度. 合理的物流能够成为国家或地区财政收入的主要来源，能够造就大量的就 业领域， 成为科技进步的主要发源地和现代科技的应用领域。 第三节发展现代物流的意义 现代物流概念引入我国虽有数年，但由于受长期计划经济体制的影响和经 济发展水平的制约，我们对现代物流的认识和实践，与发达国家相比还有较大 的差距。我国己 经加入世贸组织，中国经济要融入世界经济，必须加快营造现 代物流发展的 宏观环境。中国企业要参与国内 外市 场竞争，必须加快采用先进 的物流管理理念、技术和组织方式，不断提高企业的核心竞争力。在目 前情况 下， 推进我国 现代物流发展的重要意义可表现为以 下几个方面: 第一，推进现代物流是提高经济运行质量和效益的需要。 随着经济全球化的发展，企业的采购、仓储、销售、配送等协作关系日 趋 复杂，企业间竞争己不单是产品性能和质量的竞争，也包含物流能力的竞争。 目 前，不少企业仍沿用计划经济时期以生产为中心的管理模式，造成一方面生 产企业原材料和产品库存过大，占 用资金较多;另一方面，运输仓储企业有效 货源不足， 现有设施不能充分利用， 导致企业资 金周转不灵， 经济运行质量不高。 有关资料显示，1 9 9 9 年我国独立核算工业企业流动资金占用为3 1 0 4 2 亿元 ( 人 民币) ， 资金年周转速度为1 .2 次: 而发达国家的周转速度为1 5 - 1 8 次， 如果我 国企业的流动资金周转速度达到发达国家水平，那么，我国 3万亿元流动资金 将相当于4 5 万亿元以上。 2 0 0 0 年我国全社会支出的流通费用达1 7 8 8 0 亿元， 约占g d p 的2 0 %; 而发达国家仅为1 0 %， 如果我国全社会流通费用降低1 个百 第二章现代物流概述 分点，就可以节约资金 1 7 8亿元。由 此可见，我国物流领域存在巨大的经济效 益潜力。 现代物流是对流通方式的一场革命， 它作为一种先进的管理技术和组织方 式， 对资源进行优化整合， 从整体上改变了企业的一些运行方式。它要求企业 以市场为导向，以需求为目 标，最大限度地降低企业产品总成本，提高服务质 量和经济效益。因此， 推进现代物流是提高经济运行质量和效益的需要。 第二，发展现代物流是改善国 家投资环境的需要。 改革开放以来，各地区为了加快经济的发展，都在采取各种措施吸引外资 发展经济。对于投资者来说，投资地点的选择，不仅要考虑当地的经济条件和 优惠政策，还要考虑作为提高企业竞争力的物流环境，即物流基础设施和物流 服务质量。 物流环境的好坏，己 成为投资者评价一个地区投资环境的 重要内 容。 我国物流发展处于起步阶段，目前还难以吸引更多的境外投资和企业在国 内市场中竞争的需要。加快现代物流的发展，对于改善投资环境，吸引更多投 资，促进我国经济发展，具有深远而现实的意义。 第三，发展现代物流是应对经济全球化的需要。 目 前，全球采购、全球销售、本土化生产趋势越来越明显，我国已加入世 贸组织，国内经济与世界经济将更紧密地融合在一起。“ 入世” 之后，我国物 流业面临来自 两个方面的巨大压力。一方面，对于专业物流企业来说，拥有资 金、技术和管理优势的外国物流企业进入我国市场，将对我国的物流企业构成 严峻的挑战，我国物流企业急需应用现代物流理念和先进的运作方式，提高物 流服务水平，以应对物流市场的国际竞争。另一方面，对于工商企业而言，迫 切需要高质量的现代物流系统为之提供服务，以降低生产和流通成本， 提高企 业及其产品参与国际市场的竞争力。另外，我国大量的境外投资企业，均需要 优质高效的现代物流服务作为其经营和发展的保障。因此，无论从满足我国工 商企业、境外投资企业的服务要求，还是提高我国专业物流企业的服务竞争水 平，加强现代物流业的发展，都是非常需要的。 随着国民 经济的持续发展， 现代物流已 经受到我国各级政府和企业的高 度重 视，现代物流业必将成为新世纪我国经济发展的重要产业。 第二章 现代物流概述 第四节 资金的时间 价值 资金的时间价值就是资金在使用过程中产生的 价值增值。 盈利和利息是资 金时间价值的两种表现形式，二者都是时间因素的体现，是衡量资金时间价值 的参考尺度. 终值( f u t u re v a lu e , f v ) 是将当 前的一笔资 金按复利利率计算到将来某一时 刻的价值。 现值 ( p r e s e n t v a l u e , p v ) 是指把将来某一时刻的资金按复利折算到当 前的 价值. 假如 我 们 在 银行 存 入 一 笔 货 款p v o 。 银 行 利 率 为。 ， 则 到 第 一 年 底获 得的 利 息 收 入 为 r p v o ， 利 息 加 上 存 款 本 金 总 额 为 ( 1 + r ) p v o ; 第 二 年 年 底 所 获 得 的 利 息 收 入 为 ， ( 1 十 r ) p v , ， 加 上 本 金 ( 1 十 r p v o 可 以 得 到 收 入 总 额 为 ( 1 + r 了 尸 v u : 以 此 类 推 ， 则 到 第， 年 年 底 所 拥 有 的 存 款 总 额 为 凡 二 ( 1 + r ) p v . ， 也 就 是 说 将 货 币 的 投资 赢利 特性考虑 进去 之后， 现时 货币 量p v o ， 与n 年后的 货币 量f v 之间 是 等价的，即有下式 p v o f v 式中pv 称为 现值，f v为 第n ( 1 + r r 年 年 底 终 值 ， ( 1 + r r 为 一 次 性 复 利 终 值 系 数 。 例1某人买了价值 1 0 0 元的 债券， 年利率1 0 0/ a ，问五年后该债券的价值是 多少? 解 峨 一 p 气 ( 1 + r ) ” 一 1 0 0 ( 1 + 1 0 % ) ， 二 1 6 1 .1 ( 元 ) 例2上例中，债券五年后的价值为1 6 1 . 1 元，那么它的现值是多少? 解p v o = f v 1 6 1 . 1 二 二 一二 留 ( 1 + r 广 ( 1 + 1 0 % ) 1 0 0 ( 元) 资金的时间价值的意义表现为以下几方面: ( 1 )充分体现时间因素对经济效益的影响， 提高决策的质量; ( 2 ) 树立时间 就是金钱的 观念，提高资 金的 利用效率和投资效益; 3 ) 有利于资源的优化配置，使资源向效益高的地方流动，提高国民经济 的整体实力; ( 4 ) 用于缩短项目 建设周期， 早日 发挥投资效益。 第三章 动态规划简介 第三章动态规划简介 第一节动态规划的基本概念 动态规划是在本世纪5 0 年代初，为了 解决一类多阶段决策问 题而诞生的。 所谓 “ 动态” ，指的是在问题的多阶段决策中， 按某一顺序，根据每一步所选决 策的不同，将随即引起状态的转移，最终在变化的状态中产生一个决策序列。 动态规划就是为了使产生的决策序列在符合某种条件下达到最优。 3 . 1 . 1 动态规划的数学描述 首先例举一个典型且很直观的多阶段决策问题。 例3 . 1 现有一张地图，各结点代表城市， 两结点间 连线代表道路，线上数 字表示城市间的距离。如下图所示，试找出从结点a 到结点e的最短路径。 一 a 5 阶段!i 图3 . 1 各城市间的距离 本问题的解决可采用一般的穷举法，即找出所有可能的路径，再去逐一比 较并选择出路径最短的那条。 这样虽然能解决问题， 但随着结点数增加，其运 算量将成指数级增长，因而效率极低。于是，为了更好地解决这一问题，便产 第三章 动态规划简介 生了动态规划。 如图3 . 1 从a 到e共分为4 个阶段， 即第一阶段从a到b， 第二阶段从b 到 c，第三阶段从c 到d，第四阶段从d到e。除起点a 和终点e 外，其它各点 既是上一阶段的终点又是下一阶段的起点。例如从a 到b的第一阶段中，a 为 起点 ， 终点 有a，b 2 ，b 3 三个， 因 而 这时走的 路 线有三 个 选 择， 一是走到b 1 , 一是 走到b 2 ， 一是 走到b 3 。 若 选择凡的决 策， 几就是 第 一阶 段在我 们决策之 下 的结果，它既是第一阶段路线的终点，又是第二阶段路线的始点。 在第二阶段， 再 从b 2 点 出 发 ， 对 于 b 2 点 就 有 一 个 可 供 选 择 的 终 点 集 合 cc 2 , c 3 卜若 选 择 由 b 2 走 至c 2 为 第 二 阶 段的 决 策， 则c 2 就是 第 二 阶 段 的 终 点， 同 时 又 是 第 三 阶 段的 始点。同理递推下去，可看到各个阶段的决策不同，线路就不同。很明显，当 某阶段的起点给定时， 它直接影响着后面各阶段的行进路线和整个路线的长短， 而后面各阶段的路线的发展不受这点以前各阶段的影响。故此问题的要求是: 在各个阶段选取一个恰当的决策， 使由这些决策组成的一个决策序列所决定的 一条路线，其总路程最短。 这样， 运用动态规划思想大大节省了计算量。可以看出，动态规划是解决 此类多阶段决策问 题的一种行之有效的方法。 3 . 1 . 2 动态规划中的名词术语 下面介绍动态规划中的一些常用术语: ( 1 )阶段 将所给问题的过程，按时间或空间特征分解成若千个互相联系的阶段，以 便按次 序去求每阶段的解。 表示阶段序号的变量称为阶段变量， 一般用字母k 表 示。 在例3 . 1 中， 从a到e 可分解为a 到b，b到c， c到d， d到e四个阶段， k =1 , 2 , 3 , 4 。 ( 2 )状态 各阶段开始时的客观条件叫做状态。描述各阶段状态的变量称为状态变量， 常 用 表 示 第k 阶 段 的 状 态变 量。 状 态 变 量 的 取 值 集 合 称 为 状 态 集 合， 用s t 表 示 。 在 例3 .1 中 ， s 3 = 刁. s 2 = ab 2 , 几 , s 3 = ( q , c z , c , , .s 6 = 1 dd 2 ( 3 )决策 一个阶段的状态确定后，可以做出不同的选择，从而演变成到下一个阶段 第三章 动态规划简介 的 某 状 态， 这 种 选 择 称 为 决 策 。 描 述 决 策 的 变 量 称 为 决 策 变 量， 用u t ( s k ) 表 示 第k 阶 段 当 状 态 为 s k 时 的 决 策 变 量 。 给 定 状 态 变 量 的 取 值 后 ， 决 策 变 量u k ( s k ) 全 体 可 取 值 组 成 的 集 合 称 为 第 k 阶 段 从 出 发 的 允 许 决 策 集 合 ， 用d k ( s k ) 表 示 。 在 例3 . 1 中 ， 从 第 二 阶 段 尽 出 发 的 允 许 决 策 集 合 几( 几 ) = q ， q ， 若 决 定 选 择 c z ， 则 u 2 ( 及 ) = q ( 4 )策略 由 决策组成的序列称为策略。从初始状态s , 开始，由各阶段的决策 u , ( s j ( k = 1 , 2 , . . . n ) 组 成 的 序 列 称 为 全 过 程 策 略 ， 简 称 策 略 。 用 a ( s o = i m ( s 1 ) , u 2 ( s a , . . . u . ( s ) ) 表示。 从第k 阶段开始到终止状态的过程称为后部子过程 ( 或称k 子过程) 。 由k 子过程各阶段的决策组成的序列称为k 子过程策略，简称为子策略， 记 作p i , ( 4， 即p k ，二 ( ) 一 u k ( s k ) , u k + i ( s k * i ) , . .u . ( n ) 实际问题中，可供选择的策略有一定范围，称此范围为允许策略集合， 记 作几( s k ) ( k = 1 , 2 , . . . , n - 1 ) , 允许策略集合中达到最优效果的策略称为最优策略。 ( 5 ) 状态转移方程 若第k 阶 段的 状态s k 和决 策u k 给定， 则第k + l 阶 段的 状态s k + 1 随 之而定， s k s 1 与 ， u k 之 间 存 在 函 数 关 系 ， 记 作 a l 二 t ( s k , u k ， 称 此 关 系 为 状 态 转 移 方 程 。 在 例3 . 1 中 ， 状 态 转 移 方 程 为 + l = u k ( s , ) 。 ( b ) 指标函数 指标函数是衡量过程优劣的数量指标，它是定义在全过程和所有后部子过 程 上 的 数 量 函 数 。 用 v , ( s ., p . ) 表 示 初 始 状 态 为 s , 采 取 策 略 p i， 时 全 过 程 的 指 标 函 数 值 。 用 v k , ( s k p k r, ) 表 示 在 第 k 阶 段 状 态 为 采 用 策 略 p k ， 时 ， 后 部 子 过 程 的 指 标函 数 值. 显 然， 对 于 给定的 状态 ， 指 标函 数 值随 策 略改 变， 采 用 不同 的策略可以得出不同的指标函数值。 指标函数取得最优值 ( 最大值或最小值) 时，相应的策略称为最优策略。 最 优 指 标 函 数 记 作f k ( ) 人( ) ， 它 与 指 标 函 数 v k ( s k i p k ,. ) 间 的 关 系 为 =o p t p . r - .( = . ) v k ,n ( ， 几 ， ) 其中 几 ,n ( s , ) 表 示 以 s k 为 起 始 状 态 的 允 许 子 策 略 集 合 ， o p t 表 示 取 最 优 值。 指 标 函 数 应 具 有 可 分 离 性 ， 并 满 足 递 推 关 系 ， 即v k ， 可 表 示 成 ， u k 和y t + iw 第三章 动态规 划简介 的函数，常见的指标函数的形式有下面两种: w vk r = 全 、 ( 、 ，uj ) i 峨 2 v kr = 加(sj， 、 ) 其 中 v i l s u i 是 第 .1 阶 段 的 阶 段 指 标 。 ( 7 )最优策略和最优轨线 使 指 标 函 数 v kr ( s k p k r ) 达 到 最 优 值 的 策 略 成 ， 称 为 第 后 部 子 过 程 中 的 最 优 策 略 ， 使 指 标 函 数 v r ( .,. , p . ) 达 到 最 优 值 的 策 略 凡称 为 全 过 程 中 的 最 优 策 略，简称为最优策略。 按 最 优 策 略 p er 和 状 态 转 移 方 v s k + . = t 体 tlk ) 得 出 的 状 态 序 列 s , s z s n+ 1 称为最优轨线。 3 . 1 . 3 运用动态规划需符合的条件 最优化原理和无后效性是动态规划必须符合的两个条件。 ( 1 )最优化原理 最优化原理可这样阐述: 一个最优化策略具有这样的性质，不论过去状态 和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策 略。简而言之，一个最优化策略的子策略总是最优的。 最优化原理是动态规划的基础，任何问题，如果失去了最优化原理的支持， 就不可能用动态规划方法计算。 ( 2 )无后效性 “ 过去的步骤只能通过当 前状态影响未来的发展，当前的状态是历史的总 结” 。 这条特征说明动态规划只适用于解决当 前决策与过去状态无关的问题。 状 态，出现在策略任何一个位置，它的地位相同，都可实施同样策略，这就是无 后效性的内涵. 第二节 动态规划的基本定理和基本方程 动态规划发展的早期阶段，从简单逻辑出发给出了所谓最优性原理，然后 在最优策略存在的前提下导出基本方程，再由 这个方程求解最优策略。后来在 第三章动态规划简介 动态规划的应用过程中发现，最优性原理不是对任何决策过程普遍成立，它与 基本方程不是无条件等价，二者之间也不存在任何确定的蕴含关系。基本方程 在动态规划中起着更为本质的作用。 3 . 2 . 1 动态规划的最优性定理 定 理 3 .1对 于 给 定 的 初 始 状 态 、 ， 策 略 凡= 1 时 ， 城 ， ， 可 卜p ( s . ) 是 最 优 策略的 充要条件是对于任意的k , l k n ， 有 v , ( s .,p r ) = o p t r s - , f p s - , ( + )iv4-1(一 op t， _ vk, (; 。 ， ) 几 , . 4 , ( t ) 1 其 中 p i = ( p . , p ) , 可 是 由 初 始 状 态 s , 和 子 策 略 p l.k 。 确 定 的 第 * 阶 段 状 态 。 证明( 1 )先证必要性。 设p . 是 最 优 策 略， 由 于 指 标 函 数 有 可 分 离 性， 对 任 一 个k 有 v , ( s p i ) = o p t r - p ( 0 o p t p 明, ( s ) v , ( , ., p i ) vl ,k-, (sl,p lk -j) + v ,., (s k ,p kr ) 其 中 可 与 前 部 子 策 略 p ik - i 对 应 ， 每 个 子 策 略 p l,k - i 对 应 一 个 确 定 的 ， 以 此 为 起 始 点 有 一 个 允 许 子 策 略 集 合 ， 记 作 p k,n ( sk ) 在 集 合 p ( s ) 上 求 最 优 解 ， 等 价 于 先 在 与 某 一 允 许 子 策 略 p lk - i e p ,， 一 ; ( s , ) 对 应 的 子 策 略 集 合 p k . ( s k ) 上 求 最 优 解 ， 然 后 再 求 这 些 子 最 优 解 在 集 合 p ,n ( s . ) 上 的最优解，否则将产生矛盾。因此上式可以写成 v , ( s 凡) = o p 犷 八 ， _ 声 凡 t - t ( 1 , ) =o p t p u - , e p .k ( i ) 、 opt( _， v,k-i (si.pik-l)+vk n (sk,pk,n)pt,ep,0st) 、，一 (s pl.k-1)+ 、 opt。 vk (sk ,pk )p.,ep.i ( 2 ) 再 证 充 分 性 。 设 允 许 策 略 集 合p , 使 定 理 中 条 件 成 立 ， 下 面 证 明 p , 是 最优策略。 设 p ,， 二 ( p i.k - i. p k r, ) e p n ( s i ) 是 任 一 个 允 许 策 略 ， 对 极 大 化 问 题 则 有 第三章 动态规划简介 v i, ( 、 ， 。 ， ) = v ,k-1 ( 8 i, p l,k- t ) + v k,i ( s k , p k j, ) _ v l， 一 ， ( s i, p .， 一 ， ) + m a x p k . e p . . . ( + )v k s ( s k a p k,n ) 、 二 、): ， (、 ，二 一 ，+ 。 m ax。 vk. (sk, pk ) iptaept.st 根 据 假 设 ， 上 式 右 端 正 是 v , ( s , , 凡) ， 因 此 凡是 最 优 策 略 。 在充分性的证明中，若为极小化问题，只需把不等号的方向改变. 推 论 若 允 许 策 略 凡是 最 优 策 略 ， 则 对 于 任 意 的 袱 1 k _ 0 ) 可以 分 解 为 初 始 生 产 力 与 在时 间 ， 每 个 工 程 所具 有 的生产力之和，于是一维排序问题可以建立如下模型: m in 全 c , (1 十 ， )-(t,) s 1 . 全 q , (t) 二 d (t) t/1 e 0 , t ( 4 . 1 ) ( 4 . 2 ) 其 中 (x ) = m in 如 y 2 x j y e n ; , t t j 否则。 第四章 含生产力扩充的一维排序 第二节 一维排序的扩展和问题的转换 设s , = l p 9 ,p zl，.,易 】 ， 耳 ! 。 1,2 .,n ) ， 而 且p al p lil v 1, .1 = 1,2 ， 一 ， 于 是凡表 示一 个1 一 工 程序列i s n。这样， 一维 序列问 题由 原来的 求 (t ， t 2 ， . . . ， t n ) 以满足 ( 4 . 1 )和 ( 4 .2 )转化为求序列 仇1, 114 帆l， tlz l . . 晰j u l 芳 以满足如下模型: m ink ,.s c , ( 1 + r ) - (4 ) ( 4 . 3 ) s 1 . i q , ( t ) 2 d ( t ) v t e 0 , t j ( 4 .4 ) 其 中 方 括 号 表 示 工 程 在 序 “ 中 的 位 置 ， ， 为 n 卧个 可 能 序 ” 中 的 个 或 较 少 个 的 工 程 集 合 。 在 这 里 ， 从 ， 个 工 程 中 选 ，项 ， 则 有 卜而 “ 勺 种 类 中 ， 考 虑 工 程 的 排 ” ” 题 ， 因 而 “ (i 111帐 度 “ 的 工 程 选 择 序 ” ” 从 0 至 ， 共 “ 1-0 i ri个 工 程 序 ” 。 、 为 长 “ “ 的 工 程 序 ” ，则 问 题 化 为 求 n 卧序 列中 最优的一个，从而化为一个一维问 题， 并且每一个工序集称为一个置换调 度，因而整 个问 题转化成寻找一个满足约束条件的最优的 置换调度。 若 d ( t ) 在 0 , 月上 是 单 调 非 减 的 ， 则 一 维 调 度 问 题 可 以 化 为 一