运筹学方法在物流运输中的应用研究.doc

《运筹学方法在物流运输中的应用研究.doc》由会员分享，可在线阅读，更多相关《运筹学方法在物流运输中的应用研究.doc（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、摘要随着经济全球化和信息技术的发展，物流运输与先进的现代信息技术、数学模型工具紧密结合。运用各种运筹学优化方法对配送中各环节进行管理和决策，实现最佳协调与配合，以适应现代综合物流的大批量化、共同化的特点，可以减少物流成本，提高物流的效率和经济效益。从公司层面看，降低了运营成本，提高了客服质量和经济效益；从社会层面看，提高了车辆的利用率，减少了车辆对道路的占有率，实现社会和谐。关键词：运筹学；物流运输；供应链；优化模型ABSTRACTWith economic globalisation and the development of information technologyandlogist

2、ictransportandadvancedmoderninformationtechnologyandmathematical models tools integrated.Optimization method using a variety ofoperationalresearchinvariousaspectsofdistributionmanagementanddecision-making to achieve optimal coordination and cooperation to meet themodern integrated logistics of a lar

3、ge number of quantitative and commoncharacteristics,so you can reduce cost and improve the efficiency and cost-effectivelogistics.From the company level,lower operating costs,improve customer servicequality and economic efficiency;from the social level,to improve vehicle utilization,reducing the sha

4、re of vehicles on the road to achieve social harmony.Key words：Operations Research；Logistics；Supply Chain；Optimization model目录第一章中国物流行业现状及存在的问题.11.1 我国物流行业发展的现状分析11.2 我国物流存在面临的问题3第二章运筹学方法简介.52.1 运筹学释义与发展简史52.2 运筹学研究的基本方法6第三章运筹学在最短路问题中的应用.83.1 Dijkstra 算法.83.2 数学模型93.3 Dijkstra 算法详细过程举例113.4 Dijkstra

5、 算法优劣13第四章运筹学在最大流问题中的应用.154.1 建立数学模型.154.2 求最大流的算法步骤.184.3 模型过程详解.19第五章结束语.22参考文献.23附录:专业英语翻译24致谢33前言当人们还在对谁能最后一个被列入十大产业振兴规划充满了种种猜测时，2009 年 2 月 25 日，国务院常委会议审议物流等其它特殊性重要性行业入围，其原因是什么呢？这个让人感到陌生的产业又是一个怎样的行业呢？“物流”一词最早来源于美国。2001 年 8 月 1 日正式实施的中华人民共和国国家标准物流术语中，对物流进行了定义：“物流是从供应地向接收地的实体流动过程。根据实际需要，将运输、储存、装卸、

6、搬运、包装、流通加工、配送、信息处理等基本功能实施有机结合。”评价物流体系有五个主要因素，它们是：品质、数量、时间、地点和价格。品质是指物流过程中，物料的品质保持不变。数量是指符合经济性的数量要求和运输活动中往返运输载重尽可能满载等。时间是指以合理费用及时送达为原则做到的快速。地点是指选择合理的集运地及仓库，避免两次无效运输及多次转运。价格是指保证质量及满足时间要求的前提下尽可能降低物流费用。让我们看一看物流在近几年的发展情况吧。2006 年在国家继续加强和改善宏观调控政策的影响下，我国物流运行仍保持较快增长。2006 年前三季度，我国社会物流总费用为 22253 亿元，同比增长。2008 年

7、，全国社会物流总额 89.9 万亿元，同比增长，仍然保持了较快增长态势，但增幅比 2007 年回落 6.7 个百分点。2008 年，全国社会物流总费用为 54542 亿元，同比增长，增幅比 2007 年回落 4.4个百分点。社会物流总费用与 GDP 的比率比 2007 年下降了 0.1 个百分点。2008年，经历了罕见的雨雪冰冻、汶川地震等灾害的重大考验和国际金融危机的严峻挑战，但是我国物流业仍然实现了平稳较快发展。要发展经济物流业是重中之重。中国经济要发展，商品要流通，那么物流业是首当其冲。物流业是国民经济发展的助推器和加速器，现代物流决定了现代经济发展的规模、效益和质量。本文通过对物流行业

8、现状的探讨，从实际问题出发，建立数学模型，运用运筹学方法，对运输问题中最常见也是最重要的最短路径问题，最大可行流问题进行了优化。第一章第一章中国物流行业现状及存在的问题中国物流行业现状及存在的问题1.11.1 我国物流行业发展的现状分析我国物流行业发展的现状分析一、物流业发展规模、水平及效率现状对我国物流业的调研是研究我国物流业发展政策的重要任务之一，其目的是从宏观上摸清我国物流业的总体情况，为在宏观政策层面进行决策创造条件。通过调研分析并借鉴以往相关研究成果，我们认为，我国物流业按照现代物流业发展特点和趋势衡量，尚处于起步发展初期，与经济发达国家和地区的物流业发展水平相比还存在不小的差距。（

9、一）物流合理化的现状及差距一般认为物流活动由运输、储存、包装、搬运装卸、流通加工和信息传递等功能组成，物流业规模应为各类物流企业以物流服务方式完成的各种经营活动工作量的总和。鉴于我国尚未建立以物流业为基础的统计体系，目前无法准确反映物流的总规模，因此，可根据物流一般要通过运输环节这一特点，以全国各种运输方式完成货物运输量大致反应物流的总规模。2000 年，全国各种运输方式完成货物运输量达 135.8 亿吨和 44452.3 亿吨公里。但我国在物流的合理化方面与物流发达国家相比，差距不小，主要表现为：1.物流组织不尽合理，受资源分布、流通体制、产业布局和企业生产组织的影响，物资舍近求远、迂回流动

10、的现象较为严重；大量物流活动缺乏专业化、组织化物流服务，服务水平低，物流费用高。2.涉及物流环节的运输企业特别是国有运输企业，企业经济效益普遍较差。根据交通统计资料所反映的财务状况，铁路、公路、水运、民航等国有交通运输企业 1998 年处于全行业亏损状态，此后虽经扭亏攻坚，但仍有相当部分的国有运输企业处于亏损状态，有的处于严重亏损状态，甚至到了资不抵债的地步。3.物流相关产业表现出的资产收益率以及对国民经济发展贡献率较低，与庞大的物流规模不相吻合，我国目前每万元 GDP 产生的运输量为 4972 吨公里，物流费用占 GDP 的 20%左右，而美国、日本上述数据分别为 870 吨公里和 10%，

11、700吨公里和 14%。即便扣除欧美经济发达国家工业化水平较高的因素，我国的差距也是明显的。（二）物流服务能力的现状及差距2001 年，铁路运营里程达近 7 万公里（大约相当于美国在大规模建设铁路时期高峰年一年的建成铁路规模）；全国公路通车总里程达 143.5 万公里，高速公路达 19331 公里，高速公路里程仅次于美国跃居世界第二位；2001 年，新扩建沿海中级以上泊位 37 个，新增吞吐能力 6187 万吨，而 2000 年主要沿海生产用码头 7639 个，其中万吨级以上深水泊位 536 个；2001 年内河新增和改善航道402 公里，新扩建港口码头中级以上泊位 43 个，新增吞吐能力 5

12、36 万吨，而 2000年，内河通航里程 11.93 万公里，内河主要港口生产用码头泊位 6184 个，其中万吨级以上深水泊位 55 个；2001 年，民用机场达 143 个；2000 年，长输油气管道 2.47 万公里。另据2001 年中国交通年鉴，2000 年，我国民用汽车保有量1608.91万辆，其中载货汽车达698.32万辆，铁路机车14472台，货车总数439943辆；水运民用轮、驳船达 5128.1 万吨位，其中远洋海运船舶 2619 万吨位。此外，据有关资料，全国商业、物资流通及外贸部门拥有仓库面积达 2 亿平方米，冷库容量 400 万吨，铁路专用线 800 多条。因此，我国物流

13、基础设施和装备已初具规模，从适应和满足物流服务需求的能力角度分析，已无太大制约。但是，由于交通运输、物资流通、信息服务等行业，目前尚不具备按物流活动规律和需求进行组织和管理的能力和环境，尤其是运输、装卸、包装技术和组织管理较为落后，与国外先进水平差距较大，使现有物流基础设施及其技术装备未能充分发挥其效能，只能满足低水平、低效率的物流服务需求，不能适应和支持对于生产组织程度要求日高、支持现代企业营销网络建设和营销活动所表现出的物流要求。物流各环节的衔接较差，运转效率不高，反映为货物在途时间、储存时间、基础设施劳动生产率等方面均有较大的改善和提高余地。仅以货运汽车的生产率水平为例，美国营运汽车的单

14、车吨年产量约为66 万吨公里，而我国这一指标仅为 2 万吨公里左右。同时，物流的社会化服务水平低，专业化物流服务企业势单力薄，生产企业经营管理相对落后，对现代物流组织的利用缺乏自觉性。既有的政策体系基础，特别是管理体制和政策执行机制的困扰也在一定程度上成为提高物流服务水平的制约因素。（三）物流服务水平的现状与差距近几年来，随着我国对外开放逐渐步入较深层次，国外企业为扩大生产规模及提高市场份额，基于现代物流组织理念的物流服务需求不断增加，为其提供专业化物流服务的企业开始出现且发展很快，但这些企业大多具有外商投资或外商培训与指导背景。我国经济正面临向高效率高效益方向转轨，经济增长方式的转变已成为国

15、民经济的发展目标和指导方针。我国的专业物流服务企业也开始大量涌现，“物流热”在全国兴起就是最好的见证。目前，上海、广州、北京、深圳、天津、武汉等经济中心城市物流专业化服务发展较快。专业化物流企业的出现，为在高效率前提下组织物流创造了条件。但由于这些企业数量较少、规模有限，加之服务领域和覆盖范围较为有限，从我国物流总体质量方面的状况分析，大力发展专业物流服务的空间和有待充分挖掘的物流利润潜力巨大。1.21.2 我国物流存在面临的问题我国物流存在面临的问题根据物流业发展现状及趋势，物流质量可以表现为物流时间、物流费用和物流效率三个方面，而我国物流业目前在此方面的总体表现难尽人意。1.物流时间长。我

16、国工业生产中物流活动所占时间为整个供应过程的 90%以上，物流过程中运输以及生产、销售准备过程中的存储所占时间比重又相对较高。目前我国铁路货车的运营速度仅 46.4 公里左右，散装、集装箱等高效运输方式比重较低，装卸时间较长；公路货车的运营速度也不足 50 公里；内河航运速度更低；原材料、半成品及产成品的在库周转时间平均在 3 个月左右。按照国际国内已有装备技术水平及运输组织技术，缩短物流时间的潜力很大。2.物流费用高。根据调研及有关资料分析，我国许多商品总成本中，物流费用已占到 20%40%，每年因包装造成的损失约 150 亿元，因装卸、运输造成的损失约 500 亿元，保管不善造成的损失在

17、30 亿上下，公路货运因缺乏合理的物流组织，空驶率多年来保持在 50%左右；铁路因能力不足，使相当数量的商品失去销售机会或无法保证企业提供客户满意的服务；水运因运输组织方式不能适应市场需求变化，使许多产品失去了低价运输的途径。因此，分析我国物流费用和企业物流成本较高问题的成因，很大程度上是物流组织不合理造成的。这些不合理的或可以减少的费用，是完全可以通过加快发展现代物流业而得以避免的。3.物流效率较低。为衡量一个国家或地区的物流效率，目前使用较多的是全社会物流费用在 GDP 中的比重。美国目前为 10%左右，近十年随着现代物流业的兴起，这一比值呈缓慢下降趋势。日本、英国的情况与美国类似。我国学

18、者近几年从不同侧面对这一问题进行了研究，由于受到统计口径与统计渠道的限制，尚未得出较为准确的数字，但现有研究成果（包括本课题组主要成员完成的相关研究成果）显示，我国全社会物流支出占 GDP 的比值在 20%左右。据此与发达国家相比，即使考虑我国产业结构中第一、二次产业布局、规模导致的完成单位 GDP的物流量较大的现实因素，我国提高物流效率的潜力也是相当惊人的。近些年来，物流管理与物流技术在工业发达国家得到了广泛的应用和发展。现代物流已成为包含交通运输、产品的生产、流通和消费过程中诸环节的物流系统，是国家经济在高起点上持续发展的重要基础。随着现代科技、管理和信息技术在物流系统中的广泛应用，以及我

19、国高实现经济增长方式的转变，物流业将成为适合于我国市场经济发展的基础产业之一。鉴于我国物流业发展的相对落后状况，为适应现代物流业发展的特点和潮流，抓住现代物流业发展的历史机遇，我们必须用一种新的思维与观念，从战略的高度来探讨我国生产、流通、消费等领域中物流活动的发展特点和发展规律，积极推进专业化物流的发展，为现代物流业在我国的成熟和发展创造条件。第二章运筹学方法简介2.1 运筹学释义与发展简史运筹学一词起源于 20 世纪 30 年代。据大英百科全书释义，“运筹学是一门应用于管理有组织系统的科学”，“运筹学为掌管这类系统的人提供决策目标和数量分析的工具”。中国大百科全书的释义为：运筹学“用数学方

20、法研究经济、民政和国防等部门在内外环境的约束条件下合理分配人力、物力、财力等资源，使实际系统有效运行的技术科学，它可以用来预测发展趋势，制订行动规划或优选可行方案”（自动控制与系统工程卷，1991 年版）。朴素的运筹学思想在我国古代文献中就有不少记载，例如田忌赛马等事。齐王赛马的事是说一次齐王和田忌赛马，规定双方各出上、中、下三个等级的马各一匹。如果按同等级的马比赛，齐王可获全胜，但田忌采用的策略是以下马对齐王的上马，以上马对齐王的中马，以中马对齐王的下马，结果田忌反以二比一获胜。但运筹学这个术语的正式使用是在 1938 年，当时英国为解决空袭的早期预警，做好反侵略战争准备，积极进行“雷达”的

21、研究。但随着雷达性能的改善和配置数量的增多，出现了来自不同雷达站的信息以及雷达站同整个防空作战系统的协调配合问题。1938年 7月，波得塞（Bawdsey）雷达站的负责人罗伊（A.P.Rowe）提出立即进行整个防空作战系统运行的研究，并用“operational research”一词作为这方面研究的描述，这就是 O.R.（运筹学）这个术语的起源。后来发展到每一个英军指挥部都成立运筹学小组。1942 年美国和加拿大也都相继成立运筹学小组，这些小组在确定扩建舰队规模，开展反潜艇战的侦察和组织有效的对敌轰炸等方面做了大量研究，为取得反法西斯战争的胜利及运筹学有关分支的建立作出了贡献。自 20 世纪

22、 60 年代以来，被认为是运筹学开始普及和迅速发展的时期。此阶段的特点是运筹学进一步细分为各个分支，专业学术团体迅速增多，更多的期刊创办，运筹学书籍大量出版，以及更多学校将运筹学课程纳入教学计划之中。第三代电子数字计算机的出现，促使运筹学得以用来研究一些大的复杂的系统，如城市交通、环境污染、国民经济计划等。我国第一个运筹学小组于 1956 年在中国科学院力学研究所成立，1958 年建立了运筹学研究室。1980 年 4 月成立了中国运筹学学会。在农林、交通运输、建筑、机械、冶金、石油化工、水利、邮电、纺织等部门，运筹学的方法已开始得到应用推广。我国各高等院校，特别是各经济管理类专业中已普遍把运筹

23、学作为一门专业的主干课程列入教学计划之中。由于运筹学在提高组织机构的效率方面已取得显著的成绩，它的影响还在继续扩展。目前国际上著名的运筹学刊物有：ManagementScience，OperationsResearch，Interface，Journal of Operational Research Society，EuropeanJournal ofOperations Research 等。2.2 运筹学研究的基本方法任何一门学科从研究范畴上大致都可以分为以下四个方面：从观察现象所得到的结果和进行这种观察所需要的特殊方法；理论或模型的建立；将理论与观察相结合，并从结果得到预测；将这些预测

24、同新的观察相比较，并加以证实。运筹学也不例外，围绕着模型的建立、修正与实施，对上述四个方面的研究可划分为以下步骤。一、分析和表述问题任何决策问题进行定量分析前，首先必须认真地进行定性分析。一是要确定决策目标，明确主要要决策什么，选取上述决策时的有效性度量，以及在对方案比较时这些度量的权衡；二是要辨认哪些是决策中的关键因素，在选取这些关键因素时存在哪些资源或环境限制。分析时往往先提出一个初步的目标，通过对系统中各因素和相互关系的研究，使这个目标进一步明确化。此外还需要同有关人员，特别是决策的关键人员深入讨论，明确有关研究问题的过去与未来，问题的边界、环境以及包含这个问题在内的更大系统的有关情况，

25、以便在对问题的表述中明确要不要把整个问题分成若干较小的子问题。在上述分析基础上，可以列出表述问题的各种基本要素，包括哪些是可控的决策变量，那些是不可控的变量，确定限制变量取值的各种工艺技术条件，以及确定优化和对方案改进的目标。二、建立模型模型是对现实世界的事物、现象、过程和系统的简化描述，或其部分属性的模仿，是对实际问题的抽象概括和严格的逻辑表达。模型表达了问题中可控的决策变量、不可控变量、工艺技术条件及目标有效度量之间的相互关系。建立模型后，可以通过输入各种数据资料，分析各种因素同系统整体目标之间的因果关系，从而确立一套逻辑的分析问题的程序方法。建立模型时既要尽可能包含系统的各种信息资料，又

26、要抓住本质的因素。一般建模时尽可能选择建立数学模型，即用数学语言描述的一类模型。三、求解模型和优化方案即用数学方法或其他工具（如编写计算机程序）对模型求解。根据问题的要求，可分别求出最优解、次最优解或满意解；依据对解的精度的要求及算法上实现的可能性，又可区分为精确解和近似解等。近年来出现的启发式算法和一些软计算方法为一些结构复杂的运筹学模型的求解提供了有力的工具。四、测试模型及对模型进行必要的修正将实际问题的数据资料代入模型，找出精确的或近似的解，这解毕竟是模型的解。为了检验得到的解是否正确，常采用回溯的方法，即将历史的资料输入模型，研究得到的解与历史实际的符合程度，以判断模型是否正确。当发现

27、有较大误差时，要将实际问题同模型重新对比，检查实际问题中的重要因素在模型中是否已考虑，检查模型中各公式的表达是否前后一致。当输入发生微小变化时，检验输出变化的相对大小是否合适，当模型中各参数取极值时，检验问题的解，还要检验模型是否容易求解，并在规定时间内算出所需要的结果等，以便在发现问题，对已构建的模型进行修正。五、建立对解的有效控制任何模型都有一定的适用范围，模型的解是否有效，要首先注意模型是否继续有效，并依据灵敏度分析的方法，确定最优解保持稳定时的参数变化范围。一旦外界条件参数变化超出这个范围时，及时对模型和导出的解进行修正。六、方案的实施方案实施是很关键的一步，但也是很困难的一步。只有实

28、施方案后，研究成果才富有收获。这一步要求明确：方案由谁实施，什么时间实施，如何实施，要求估计实施过程可能遇到的阻力，并为此制订相应的克服困难的措施。上述步骤往往需要交叉反复进行。因此在运筹学的研究中，除对系统进行定性分析和收集必要的资料外，一项主要工作是努力去建立一个用以描述现实世界复杂问题的数学模型。这个模型是近似的，它既精确到足以反映问题的本质，又粗略到能够求出数量上的解。第三章运筹学在最短路问题中的应用利用运筹学中的图论和线性规划方法，对已有的空运水运、公路运输、管道运输、铁路运输组成的交通网，根据不同的决策目标制定不同的调运方案。可以是最短时间的运输路线、最少费用的运输路线或是最大运输

29、量最低运费的运输线路等。通过选择最佳运输路线、最佳货物调运、装卸方案，达到降低物流成本的目的。这里讨论最短配送线路的设计。最短路问题一般描述如下：在一个赋权图（或者说网络）中，给定一个始点sv和一个终点tv，求sv到tv的一条路，使路长最短（即路的各边权数之和最小）。许多实际问题都归结为最短路问题，例如两地间的管道铺设，线路安装，道路修筑，线路选取等等；再如工厂布局，设备更新等问题也可转化为最短路问题。本章将介绍求最短路的常用方法Dijkstra（狄克斯屈）标号算法。3.1 Dijkstra 算法最短线路计算法在图论中归结为从给定一个点 到任一其他点的最短线路问题。最基本的方法是由 Dijks

30、tra 提出的。可用于求解指定两点sv，tv间的最短路，或从指定点sv到其余各点的最短路，目前被认为是求无负权网络最短路问题的最好方法，算法的基本思路基于以下原理：若序列sv，1v，1nv，nv是从sv到tv的最短路，则序列sv，1v，1nv必为sv到1nv的最短路。下面给出 Dijkstra 算法基本步骤，采用标号法。可用两种标号：T 标号与 P标号，T 标号为试探性标号（tentative label）,P 为永久性标号(permanentlabel),给iv点一个 P 表示从sv到iv点的最短路权，iv点的标号不再改变。给iv点一个 T 标号时，表示从sv到iv点的估计最短路权的上界，是

31、一种临时标号，凡没有得到 P 标号的点都有 T 标号。算法每一步都把某一点的 T 标号改为 P 标号，当终点tv得到 P 表号时，全部计算结束。对于有 n 个顶点的图，最多经过 n-1 步就可以得到从始点到终点的最短路。算法步骤：（1）给sv以 P 标号，()sP v=0，其余各点均给 T 标号，()iT v。（2）若iv点为刚得到 P 标号的点，考虑这样的点jv：（iv，jv）属于 E，且jv为 T 标号。对jv的 T 标号进行如下的更改：T(jv)=minT(jv),P(iv)ijl（3）比较所有具有 T 标号的点，把最小者改为 P 标号，即：iP v=minT(iv)当存在两个以上最小者

32、时，可同时改为 P 标号。若全部点均为 P 标号则停止。否则用iv代iv转回（2）。3.2 数学模型下面结合具体实例说明一下在具体实际问题中的应用问题：企业使用一台设备，每年年初，企业领导就要确定是购置新的，还是继续使用旧的.若购置新设备，就要支付一定的购置费用；若继续使用，则需支付一定的维修费用.现要制定一个五年之内的设备更新计划，使得五年内总的支付费用最少.已知该种设备在每年年初的价格为：第一年第二年第三年第四年第五年1111121213使用不同时间设备所需维修费为：使用年限0112233445维修费56811183.2.1 建模过程符号说明及问题分析（1）顶点集VXib,i=1,2,3,

33、4,5Xirk(),i=2,3,4,5,6;k=1,2,i-1,每个顶点代表年初的一种决策，其中顶点Xib代表第i年初购置新设备的决策，顶点Xirk()代表第i年初修理用过k年的旧设备的决策（2）弧集E=(,),(,),(),XXXXibibirkib11i=1,2,3,4;k=1,2,i-1(,),()XXibir11,i=1,2,3,4,5(,)(),()XXirkirk11,i=1,2,3,4,5;k=1,2,i-1若第i年初作了决策Xi后，第i+1 年初可以作决策Xi1，则顶点Xi与Xi1之间有弧(Xi,Xi1)，其权 W(Xi,Xi1)代表第i年初到第i+1 年初之间的费用.例如，弧

34、(,)()XXbr341代表第三年初买新设备，第四年初决定用第三年买的用过一年的旧设备，其权则为第三年初的购置费与第三、第四年间的维修费之和，即为 12517.这样，可建立本例的网络模型（如图 3-1 所示），加权有向图G1(V,E)图 3-1于是问题转化为顶点Xb1到Xrk6()的最短路问题.五年的最优购置费为()161,2,3,4,5min(,)kbrkd XX其中d(Xb1,Xrk6()为顶点Xb1到Xrk6()的最短路的权.求得最短路的权为 53，而两条最短路分别为XXXXXXbrrbrr1213245162()()()();XXXXXXbrbrrr1213415263()()()()

35、因此，计划为第一、第三年初购置新设备，或第一、第四年初购置新设备，五年费用均最省，为 53.3.2.2.模型改进上图可转化成加权有向图G2(V,E)，图 3-2.图 3-2（1）顶点集=V V V V V V123456,，Vi表第i年初购置新设备的决 策，V6表第五年底.（2）弧集E=(,)V Vij，i=1,2,3,4,5;ij6,弧(,)V Vij表第i年初购进一台设备一直使用到第j年初的决策，其权W(,)V Vij表由这一决策在第i年初到第j年初的总费用，如W(,)V V14=11+5+6+8=30.（3）问题转化为求V1到V6的最短路问题，求得两条最短路为VVV146，VVV136，

36、权为 53，与图 G1(V,E)的解相同3.3 Dijkstra 算法详细过程举例例某企业要将产品从甲地运到乙地，从甲地到乙地有不同的路线可以选择，怎样选择可以使运输路线最短。如下图 3-3 所示：图 3-3运输线路图在甲乙两地的交通图中的1v，2v，8v表示 8 个地名，其中1v表示甲地，8v表示乙地，点之间的连线（边）表示两地之间的公路，边所赋的权数表示两地间公路的长度（单位为公里）。用 Dijkstra 算法求解运输最短路径，也就是找出最短路径，使运输费用最低。解（1）首先给1v以 P 标号，10P v，给其余所有点 T 标号，()iT v（i=2,8）（2）由于 1213,v vv v

37、边属于 E，且23,v v为 T 标号，所以修改这两个点的标号：22112min,min,044T vT vP vl 33113min,min,066T vT vP vl（3）比较所有 T 标号，T(2v)最小，所以令 P(2v)=4。并记录路径12,v v。（4）2v为刚得到 P 标号的点，考察边 2425,v vv v的端点45,v v。44224min,min,459T vT vP vl55225min,min,448T vT vP vl（5）比较所有 T 标号，T(3v)最小，所以令 P(3v)=6。并记录路径13,v v。（6）考虑点3v，有44334min,min 9,649T v

38、T vP vl55335min,min 8,678T vT vP vl（7）比较全部 T 标号中，T(5v)最小，令 P(5v)=8，记录路径25,v v。（8）考察5v，66556min,min,8513T vT vP vl77557min,min,8614T vT vP vl（9）比较全部 T 标号中，T(4v)最小，令 P(4v)=9，记录路径24,v v。（10）考察4v，66446min,min 13,9913T vT vP vl77447min,min 14,9714T vT vP vl（11）比较全部 T 标号中，T(6v)最小，令 P(6v)=13，记录路径56,v v。（12

39、）考察6v，77667min,min 14,13514T vT vP vl88668min,min,13417T vT vP vl（13）比较全部 T 标号中，T(7v)最小，令 P(7v)=14，记录路径57,v v。（14）考察7v，88778min,min 17,14 115T vT vP vl（15）因只有一个 T 标号 T(8v)，令 P(8v)=15，记录路径78,v v，计算结束。全部计算结果见图 3-4，1v到8v之最短路径为12578vvvvv，路长P(8v)=15，即甲地到乙地的最短距离为 15 公里，同时得到1v点到其余各点的最短路，如图 3-4 中粗线表示。图 3-4结

40、果图3.4 Dijkstra 算法优劣总之，Dijkstra 算法在最短路径的求解中广泛应用，是一种既简单又有效的方法，能够用这种简单的方法找出最短路径。需要提醒读者注意的是，这个算法只适合用于全部权为非负情况，如果某边上权为负的，算法失效。这从一个简单例子就可以看到，图 3-5 中，我们按Dijkstra 算法得1()5P v为从1svv的最短路长显然是错误的，从21svvv只有 3。图 3-5负权图第四章运筹学在最大流问题中的应用最大流问题是一类应用极为广泛的问题，在交通运输网络中有人流、车流和物流，人们自然希望在有限的道路网络中能有最大的人流量、车流量和货流量；在供水网络中有水流，供气网

41、络中有气流，金融系统中有现金流，通讯系统中有信息流，人们同样希望这些流量能尽量地大，此即最大流问题。最大流问题中，人们常对以下几个问题感兴趣：其一是在不超载运行条件下，如何安排才能使流量达到最大，及最大流量是多少；其二是这个最大的流量是怎样一个流向，希望给出最大流量运行方案;其三是网络中，在达到最大流量情形下，还有哪些浪费现象（如一段管道容量为 10，而流量仅为 4），而制约流量进一步提高的“瓶颈”又是在什么地方，以便经行改造处理；最后是达到最大流量的同时能否使运行费用降到最低，也称为最小费用最大流问题。4.1 建立数学模型提出问题：有一个输油管道网络，其起点为产油地sv，终点为炼油厂tv，在

42、输送原油过程中，要经过四个中转站1234,v v v v。从sv到1v 2v的管道容量分别为 4 和 8 个单位，而目前经过这两个管道的流量分别为4和1个单位（存在设备闲置浪费现象）；四个中转站中，1v可向23,v v和4v输油，其管道容量和目前流量分别为 4 和 3,4和 0，1 和 1；2v又可向34,v v输油，其容量与流量分别为 2 和 2,2 和 2；又34,v v可直接向炼油厂输油，容量和流量分别为 7 和 2,9 和 3。根据网络流情况，试研究一个输送方案，使其流量提高到最大。我们先来建立起其数学模型，再寻求其解法。以起始点（产油地，以后称为起点）sv为第一个顶点，1234,v

43、v v v为中间顶点，tv（目的地，今后称为终点）为最后一个顶点，按设输油方向便可建立起问题的网络图模型如图 4-1。图4-1其中的弧（在有向网络中边又称为弧）表示管道，箭头方向指向了输送方向。弧旁边的数字对（,ijijCf）表示管道最大通过能力容量ijC和目前的流量ijf，我们的目的是求出一个从sv出发到tv结束的一个有向流，使得总流量达到最大。易见，tv的总输入量为 2+3=5 恰为总输出量。图 4-1 便是本问题的数学模型。为求解，再进一步说明几个有关事项：1.1.容量网络容量网络像图 4-1 所示的网络图称为容量网络，显然有ijijfC，当等号成立时，也称该弧是饱和的。2.2.可行流可

44、行流当ijf满足起点的总输出量等于终点的总输入量。中间点的流入量等于流出量时，称其全体集为一个可行流，记作 ijff，总输出量称为可行流的流量。3.3.链链有向流量网络中一条从始点sv出发，到tv终止的边与顶点的交替序列称为该网络的一条链。记作。如网络图 4-1 中，221133,stv vv vv vv v就是一条链。在这条链上共有 4 条边，其中，（2,sv v），（13,v v），（3,tv v）与整个链的指向一致，称为前向弧（边），其全体记作；(21,v v)与链的指向相反，称为后向弧（边），其全体记作。4.4.网络图中一条链称为可增广链可增广链，是指+中所有弧都是不饱和的且-中的流量

45、不等于零。按此定义，可增广链上的流量是可以通过调整而增大的，我们把流量可增大的幅度值称为调整量调整量记作，显然(,)min.ijijijv vCf若记(,)(,)min,minijijijijijv vv vCff，则min,.从而在可增广链上，可将目前的可行流 f=ijf进行如下调整而获得新的可行流fijf：,(,),(,)ijijijijijfv vffv v使得f的流量增大。在容量网络图 4-1 上可见，弧2(,)sv v还有潜力，因为，2218ssfC。但是，从24(,)v v及23(,)v v流出的流量已经饱和，而使2(,)sv v上的潜力无法发挥。如果我们把通过12(,)v v上的

46、流量 3 改道从13(,)v v上流出，这样便可使2(,)sv v得流量增加 3。这时新增流量须从顶点3v流出 3，由于3(,)tv v的流量为 2，容量为 7，故该弧可接纳新流量 3 而输送到终点tv，这样一次调整后，总流量便增加了 3 个单位，于是得到了调整后的容量网络图 4-2。图4-2将上述说法数量化，则其过程如下：可增广链为221133(,),(,),(,),(,)stv vv vv vv v，而223321(,),(,),(,),(,)stv vv vv vv v，由于 min 8 1,40,724,min 33，故增广量min 3,43，于是新可行流ilf为2213131 34,

47、033,ssffff 332121235,330ttffff。按此思想方法便可给出一种网络最大流的算法标号算法。4.2 求最大流的算法步骤设已有一个可行流 f,标号的方法可分为两步：第一步是标号过程，通过标号来寻找可增广链；第二步是调整过程，沿可增广链调整 f 以增加流量。1.标号过程（1）给始点以标号（,）。（2）选择一个已标号的顶点iv，对于iv的所有未给标号的邻接点jv按下列规则处理：（a）若边(,),ijv v且0ijf，则令min(,),jjiif并给jv以标号(,)ijv。（b）若边(,),ijv v且ijijfC时，令min(,),jijijiCf并给jv以标号(,)ijv。（3

48、）重复（2）直到终点tv被标号或不再有顶点可标号时为止。若tv得到标号，说明存在一条可增广链，转（第 2 步）调整过程。若tv未获得标号，标号过程已无法进行时，说明 f 已是最大流。2.调整过程若(,)ijv v是可增广链上的前向边（1）令若(,)ijv v是可增广链上的后向边若(,)ijv v不在可增广链上（2）去掉所有标号，回到第一步，对可行流f重新标号。4.3 模型过程详解下面为详细解答过程。解（1）先给始点sv标以（,）。（2）检查与sv的邻接点12,v v，发现2v点满足2(,)sv v，且2218ssfC，令2min 8 1,7,v 则给点2v以标号,7sv，1(,)sv v不在可

49、增广链上。（3）检查与2v点邻接的尚未标号的点1,v34,v v，发现1v点满足21(,)v v，且1230f，令1min 3,73v，则给点1v以标号2,3v，23(,)v v，24(,)v v不在可增广链上。（4）检查与1v点邻接的尚未标号的点34,v v，发现13(,)v v，且131304fC，令3min 40,33v，则给点3v以标号1,3v，14(,)v v不在可增广链上。（5）检 查 与3v点 邻 接 的 尚 未 标 号 的 点tv，发 现3(,)tv v，且3327ttfC，令min 72,33tv，则给点tv以标号3,3v。由于tv已经得到标号，说明存在可增广链，所以标号过程

50、结束。见图 4-3ijtijijtijffff图4-3（6）转入调整过程，令3tv为调整量，从tv点开始，由逆可增广链方向按标号3,3v找到3v，令33235ttff。（7）再由3v点标号1,3v找到前一个点1v，并令1313033ff，按1v点 标 号 找 到 点2v，由 于 标 号 为2,3v，21(,)v v为 反 向 边，令2121330ff。（8）由点2v标号,7sv找到点sv，令221 34ssff。调整过程结束，调整后的可行流见图 4-4图4-4（9）重新标号过程，寻找可增广链。这时12348ssttWffff，即为最大流的流量，算法结束。总结我们从一个简单的供应链出发，建立了数