动态规划方法在物流管理中的应用研究

I摘要随着我国经济的不断发展，现代物流业作为第三利润源，已经越来越多受到大中小企业的重视，尽可能地减少物流总成本也成为企业关注的焦点，企业家们已经开始从整个物流系统的角度来衡量和分析物流活动的耗费情况，用全局的思想来优化每一项物流活动。因此，物流管理作为物流活动的的必要环节，其耗费人力，财力以及物力的多少，直接关系着物流活动的成本问题。但通过多方资料对我国物流管理的研究，发现不少企业仍然使用原始的管理方法，借鉴国外的大型企业的优秀物流管理方法。结合我国实际国情，提出了在物流管理中使用动态规划的方法，动态规划是运筹学的分支，是求解决策过程最优化的数学方法。使用动态规划来进行物流管理，能合理的利用相关的措施，有效的降低各项管理活动的总成本。提过企业的经济效益。本文通过将详细对动态规划方法和物流管理两个关键点进行分析，并将把使用动态规划解决物流管理的问题作为该篇的重心来进行论述，分别对物流管理中的资源分配问题，存贮问题，最短路问题和背包问题进行实际的案例分析。来论证动态规划方法对物流管理起到的重要作用。关键词：动态规划；物流管理； 物流成本；存贮问题IIAbstractWith Chinas economy continues to develop modern logistics industry as the third profit source, has been more and more medium and small companies to survive, to minimize total logistics costs become the focus of attention of the enterprise, entrepreneurs have begun from the entirelogistics point of view of the system to measure and analyze the cost of logistics activities, the idea of global optimization of a logistics activities. , Logistics management as a necessary part of logistics activities, the cost of human, financial and material resources, is directly related to the cost of logistics activities. Through the multi-information on Chinas logistics management, many companies still use the original management, drawing on the large foreign enterprises of the outstanding logistics management methods. Chinas actual conditions, using dynamic programming methods in logistics management, dynamic programming is a branch of operations research, mathematical methods for solving decision-making process optimization. Using dynamic programming to logistics management, rational use of relevant measures to effectively reduce the total cost of the management activities. Mentioned that the economic efficiency of enterprises.This paper analyzed in detail the two key points of the dynamic programming methods and logistics management, and use dynamic programming to solve the problem of logistics management as the center of gravity of the article discusses the resource allocation problem in logistics management, storage problem, the shortest path problem and the knapsack problem for the actual case studies. To demonstrate the dynamic programming method of logistics management play an important role.Key words：Dynamic programming; logistics management; logistics cost; Storage problemIII目录第一章 绪论 .11.1 研究背景及意义 .11.2 研究概况 .11.2.1 动态规划简介 .11.2.2 物流管理简介 .31.2.3 动态规划在物流管理上的应用 .51.3 国内外研究现状 .5第二章 动态规划的应用研究.102.1 动态规划的基本理论 .102.1.1 动态规划的介绍 .102.1.2 多阶段决策过程的数学描述 .112.1.3 动态规划的基本概念 .122.1.4 动态规划的数学模型 .142.1.5 动态规划的四大要素及分类 .162.2 动态规划模型的建立与求解 .172.2.1 动态规划模型的建立 .172.2.2 动态规划求解的基本方法 .202.2.3 基本方程分段求解时的几种常用算法 .21第三章 物流管理概述.223.1 物流管理的发展概况 .223.2 物流管理的介绍 .243.2.1 物流管理的主要内容 .243.2.2 物流管理的分类 .243.2.3 物流管理的原则 .263.2.4 物流管理的三个阶段 .273.2.5 核心. .283.3 物流管理的目的和作用 .293.3.1 物流管理的目的 .29IV3.3.2 物流管理的作用 .293.4 现代物流管理的特征 .31第四章 动态规划在物流管理中的应用.334.1 资源分配问题 .334.1.1 决策变量取离散值的分配问题 .334.1.2 决策为连续变量的资源分配问题 .354.2 存贮控制问题 .404.3 最短路线问题 .434.4 背包问题 .46结论.49参考文献.51致谢.53附录一 中文译文.附录二 外文资料原文.（论文）1动态规划在物流管理中的应用研究第一章 绪论1.1 研究背景及意义1918 年，英国犹尼利弗的哈姆勋爵成立了“即时送货股份有限公司” ，目的是在全国范围内把商品及时送到批发商、零售商和用户手中，这事物流公司最早的雏形。随着社会的不断进步和经济的断发展，现代物流成为了集运输、搬运、储存、保管、包装、装卸、流通加工和物流信息处理等基本功能为一体，由供应地流向接受地以满足社会需求的一种经济活动。其核心目标是在物流全过程中以最小的综合成本来满足顾客的需求。国际上普遍把物流称为“降低成本的最后边界”，排在降低原材料消耗、并且提高劳动生产率之后的“第三利润源泉”，是企业整体利润的最大源泉。所以，各国的企业才越来越重视物流，逐渐把企业的物流管理当作一个战略新视角，变为现代企业管理战略中的一个新的着眼点，通过制定各种物流战略，从物流这一巨大的利润空间去寻找出路，以增强企业的竞争力。而好的物流管理方法成为企业生产研究的重中之重。我国把物流作为一个学科来研究,并与国外物流界发生是近二十年才开始的。与一些发达国家相比，我国物流业从各方面都要一些差距的。就目前来说我国的物流前景大好，据调查我国物流成本占 GDP 的比重逐年下降，从这个角度来讲，当下降速度超过 GDP 速度时，物流行业应该是创造的产值越来越低的一个行业。但这并不意味着物流行业没有前景。物流成本占 GDP 比重的下降除了产业结构调整（第三产业物流需求较低）因素之外，物流管理水平的提高是一个主要因素。目前我国物流成本占 GDP 比重为 20%左右，美国为 10%左右，抛除产业结构因素，我国的比重比美国的比重应该高 5%左右。也就是说随着越来越多的物流企业掌握先进的物流技术和管理水平之后，我国物流成本占 GDP 的比重将会持续下降。那这些掌握先进物流管理水平的企业将是我国物流行业的胜利者。本文所要论述的中心就是应用最简单的方法来进行物流管理活动。 6（论文）21.2 研究概况1.2.1 动态规划简介动态规划(dynamic programming)是运筹学的一个分支，是求解决多阶段决策过程(decision process)最优化问题的一种数学方法。20 世纪 50 年代初美国数学家R.E.bellman 等人在研究多阶段决策过程(multistep decision process)的优化问题时，针对多阶段决策问题的特点，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法。动态规划的最优化原理：作为整个过程的最优策略具有这样的性质，无论过去的状态和决策如何，对前面所形成的状态而言，余下的诸决策必构成最优策略。利用这个原理，可以把多阶段决策问题的求解过程看成一个连续的递推过程，由后向前逐步推算。在求解时，各状态前面的状态和决策，相对其后面的子问题，相当于初始条件，并不影响后面过程的最优策略。所以，动态规划方法解题的基本思路，是将一个多阶段决策问题转化为依次求解多个单阶段的决策问题，从而简化计算过程。这种转化的实现是从终点出发一步步反推，即采用逆序算法。成功的解决了生产管理、工程技术等方面的许多实际问题。1957 年，R Bellman 发表了该分支领域的第一本专著动态规划 。动态规划是现代企业管理中的一种重要决策方法，可用于解决最优路径问题、资源分配问题、生产计划与库存、投资、装载、排序等问题及生产过程的最优控制等。由于它独特的解题思路，在处理某些优化问题是，比线性规划和非线性规划方法更有效。任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。(1) 最优化原理（最优子结构性质） 一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。(2) 无后效性我们要求状态具有下面的性质：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定（论文）3了。也就是说，过程的每一次实现可以用一个状态序列表示，在前面的例子中每阶段的状态是该线路的始点，确定了这些点的序列，整个线路也就完全确定。从某一阶段以后的线路开始， 当这段始点给定时，不受以前线路（所通过的点）的影响。状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。Y Y1/b-aa b X a b X图 1-1 无后效性(3) 子问题的重叠性 动态规划将原来具有指数级复杂度的搜索算法改进成了具有多项式时间的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。 动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。 21.2.2 物流管理简介物流管理（Logistics Management）是指在社会在生产过程中，根据物质资料实体流动的规律，应用管理的基本原理和科学方法，对物流活动进行计划、组织、指挥、协调、控制和监督，使各项物流活动实现最佳的协调与配合，以降低物流成本，提高物流效率和经济效益。物流体系的四个核心是：采购、仓储、配送、运输。现代物流管理是建立在系统论、信息论和控制论的基础上的。(1) 物流管理的基本内容主要分六个： 物流作业管理：物流作业管理强调低成本、高质量和快速响应。企业利用作业（论文）4成本法测算与物流活动相关的费用，使得物流成本明晰化。然后，在作业成本法的基础上，应用作业管理思想来进行物流管理，深入开展企业作业的增值性分析和因果关系分析。 物流战略管理：物流战略管理是指通过物流战略设计、战略实施、战略评价与控制等环节，调节物流资源、组织结构等最终实现物流系统宗旨和战略目标的一系列动态过程的总和。 物流成本管理：物流成本管理（Logisticscostcontrol）是对物流相关费用进行的计划、协调与控制。物流成本管理是通过成本去管理物流，即管理的对象是物流而不是成本。物流成本管理可以说是以成本为手段的物流管理方法。 物流服务管理：物流企业要取得竞争优势，向集约化发展是一条必由之路。物流的配送中心不仅只提供仓储和运输服务，还必须开展配货、配送和各种提高附加值的流通加工服务项目，也可按客户的的需要提供其他个性化服务。物流企业一方面要与货主企业结成战略伙伴关系，以保证得到长期的货源；一方面要与货主企业结成战略伙伴关系，以保证得到长期的货源；一方面要有助于货主企业的产品迅速进入市场，提高竞争力，从而实现互利共赢。因此，对于物流企业而言，服务质量和服务水平正逐步成为比价格更为重要的选择因素。 7 物流组织与人力资源管理：对专门从事物流经营和管理活动的组织和个人进行有效的管理，以提高企业的工作效率提升企业的经济效益。 供应链管理：围绕核心企业，通过对信息流，物流, 资金流的控制，从采购原材料开始，制成中间产品及最终产品，最后由销售网络把产品送到消费者手中。它是将供应商,制造商，分销商，零售商,直到最终用户连成一个整体的功能网链模式来进行计划、协调、操作、控制和优化的各种活动和过程。(2) 物流管理的原则主要有三点: 物流管理的总原则物流合理化物流管理的具体原则很多，但最根本的指导原则是保证物流合理化的实现。所谓物流合理化，就是对物流设备配置和物流活动组织进行调整改进，实现物流系统整体优化的过程。它具体表现在兼顾成本与服务上，即以尽可能低的物流成本，获得可以接受的物流服务，或以可以接受的物流成本达到尽可能高的服务水平。 物流合理化的基本思想（论文）5物流活动各种成本之间经常存在着此消彼长的关系，物流合理化的一个基本的思想就是“均衡”的思想，从物流总成本的角度权衡得失。不求极限，但求均衡，均衡早就合理。 物流管理面临的新挑战近年来，很多先进的信息技术的出现，极大地推动了物流行业的巨变。我们不能再以传统的观念来认识信息时代的物流，物流也不再是物流功能的简单组合运作，它现在已是一个网的概念。加强连通物流结点的效率，加强系统的管理效率已成为整个物流产业面临的关键问题。 151.2.3 动态规划在物流管理上的应用动态规划说到底是一种特殊的决策序列，它使得一个问题可以逐步推导到最优解，准确而又快捷的解决繁杂的物流管理问题。因此在物流管理的中能多次的使用它的理论和计算方法。该篇论文就对物流管理中常见的资源分配问题，存贮控制问题，运输最短路问题和背包问题用动态规划方法分别予以详细的计算和分析。1.3 国内外研究现状物流概念从上个世纪 70 年代末引入我国，90 年代中期开始出现“物流热” 。进入新世纪以来，也就是“十五”时期，我国现代物流跨越“起步期” ，进入理性、务实、持续、快速发展的新阶段。现代物流的产业地位得以确立。今年 3 月，全国十届人大四次会议通过的国民经济和社会发展第十一个五年规划纲要 ，在第四篇“加快发展服务业” ,第十六章“拓展生产性服务业”里面，单列一节“大力发展现代物流业” 。这在我国国民经济和社会发展规划的历史上也是第一次，标志着现代物流的产业地位在国家规划层面得以确立。物流产业平稳快速发展。据国家发改委、国家统计局和中国物流与采购联合会统计：“十五”时期，我国社会物流总额扣除价格因素，年均增长 15%左右，明显快于“十五”时期 GDP 增长的水平；我国社会物流总费用与 GDP 的比率由 2000 年的 19.4%下降到 2005 年的 18.6%，等于节约社会物流费用合计 1090亿元；物流业增加值 2005 年超过 1.2 万亿元，同比增长 12.7%，占当年服务业增加值的 16.6%。今年上半年，我国社会物流总额继续保持快速增长，达到 26.8 万亿元，按可比价格计算同比增长 15.3%；社会物流总费用与 GDP 的比率继续下降，由去年全年的 18.6%，下降至 18.4 %，下降 0.2 个百分点。物流企业群体迅速成长。 “十五”（论文）6时期，传统大型国有物流企业改制重组，加快向现代物流转型，民营物流企业瞄准市场需求，发展势头迅猛，外资物流企业“抢滩”中国物流市场，形成了“三足鼎立”的物流企业群体。制造业和流通业物流运作模式发生了转变。许多制造企业运用现代物流理念，实施流程再造，分离外包物流业务，出现了销售物流向生产物流、供应物流延伸的趋势，一体化运作、供应链管理初现端倪。流通企业不断强化自身物流能力，大力发展连锁经营、物流配送和电子商务等现代营销方式，促进了商流、物流、信息流和资金流的融合，极大地改变了传统流通模式。物流基础设施和信息化建设进度加快。 “十五”期间，我国物流相关行业固定资产投资年均增速达 19.7%，比“九五”时期加