作者：李忠国 主编
出版社：化学工业出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
现代物流决策实务试读：
前言
2017年8月，北京农业职业学院作为教育部第二批现代学徒制试点单位正式立项，工商企业管理专业、物流管理专业作为现代学徒制项目的试点专业，经过甄选、沟通，专业分别与合作企业签订了联合培养协议，根据教育部第二批现代学徒制试点工作的要求开展工作，在招生招工、双导师师资队伍建设、顶岗实习管理、人才培养方案制订等方面校企双方深入合作，取得了较好成果。《现代物流决策实务》是校企深度融合、学院现代学徒制试点教学工作的经验总结。
现代物流经营的关键就是要以较低的成本满足客户对物流服务的需求。物流系统的各功能要素不仅成本支出大，彼此之间还存在二律背反现象。“现代物流决策实务”是高职院校物流管理专业的一门核心专业课程，能优化物流经营管理中的物流系统，为降低物流总成本提供科学有效的方法，进而提升学生在物流管理工作中的核心业务决策技能。
本书主要根据物流主要业务部门作为模块划分依据，以物流核心部门的业务管理岗位中的常见定量决策问题的解决为教学内容的出发点，以理实一体的教学思想为指导，采用了任务驱动的编写思路组织教材的内容体系。每个任务以物流仓储管理、配送运输调度和物流经理岗位业务管理工作中常见的核心定量决策实例作为任务引入，以本任务操作所需的基本概念和操作步骤为相关知识的内容；任务实施中详细阐述该决策问题求解的详细步骤；最后的实践训练中配备了大量的实践训练习题，帮助学生巩固和提升业务决策能力。具体内容涵盖了物流仓储管理、运输调度和物流经理岗位实际工作中的大部分核心定量决策问题，包括认识物流决策技术、运输路线选择、物资调运与配装、物流设施选址、库存控制与仓储作业排序、物流项目财务分析与资源分配六个模块。
现代物流决策实务（物流运筹学）课程一直存在理论难讲、实践操作复杂等特点，因此本书在编写过程中坚持从物流岗位实际任务出发来讲解任务实施过程，直接教会学生解决问题的方法步骤，不讲数学推理，不从数学角度考虑运筹学体系的完整性。另外，虽然决策分析可以手工计算分析，也可以利用计算机软件运算，但由于物流运筹学软件和物流决策分析软件更新换代快、成本高、灵活性较差，因此本书主要以手工分析运算为主，教会学生如何收集数据资料，如何进行分析决策。由于任务驱动体系的缺陷，书中的例题较少，在使用本书进行教学过程中应加强实践指导，针对不同学生操作的不同问题提出个性化的指导意见，帮助学生提高操作水平；在教学手段上，可以根据条件利用Excel或其他运筹学软件来组织实训和验证性实验。
本书由北京农业职业学院的副教授、高级物流师李忠国任主编，编写了模块二、模块三、模块六；北京农业职业学院讲师、高级物流师石岩，与物美商业集团股份有限公司副总裁张正洋任副主编，其中石岩老师编写了模块五，张正洋副总裁编写了模块四；北京农业职业学院胡军珠老师编写了模块一。编者在多年物流运筹学教学经验的基础上，根据物流岗位实际需要，在使运筹学知识与物流专业知识和业务能力的进一步融合、降低内容难度、更加贴近职业教育方面做出了努力，但编者的水平有限，书中难免存在不妥之处，敬请广大读者批评指正。李忠国2019年1月模块一 认识物流决策技术◆ 知识目标（1）了解运筹学的含义与内容。（2）了解物流决策技术的含义、内容及其在物流管理中的作用。任务 认识物流决策技术任务描述
传说宋真宗在位时，皇宫曾起火。一夜之间，整座皇宫变成了废墟。在废墟上，宋真宗怒道：“没有皇宫，如何上朝，如何议政，如何安居呢？”为了修复这些宫殿，宋真宗派当时的晋国公丁谓（966—1037）主持修缮工程。当时，要完成这项重大的建筑工程，面临着三个大问题：第一，盖皇宫要很多泥土，可是京城中空地很少，取土要到郊外去挖，路很远，得花很多的劳力；第二，修建皇宫还需要大批木材、石料等其他材料，都需要从外地运来，而汴河在郊外，离皇宫很远，从码头运到皇宫还得找很多人搬运；第三，清理废墟后，很多碎砖破瓦等运出京城同样很费事。但由于工期紧，不可能再从外地抽调大量民工；即使能很快调集民工，但这样大的工程如果同时开工，工地上也容不下这么多人。
请从物流角度想一想，在保证工期尽量短的前提下，该如何解决建筑垃圾清运，泥土、木材与石料的调运等物流问题？相关知识一、运筹学（一）运筹学的定义
运筹学主要研究经济活动和军事活动中能用数量来表达的有关策划、管理方面的问题，根据问题的要求，通过数学上的分析、运算，得出各种各样的结果，最后提出综合性的合理安排，以达到最好的效果。运筹学作为一门用来解决实际问题的学科，在处理千差万别的各种问题时，一般有以下几个步骤：确定目标、制订方案、建立模型、制订解法。
运筹学是软科学中“硬度”较大的一门学科，是系统工程学和现代管理科学中的一种基础理论和不可缺少的方法、手段和工具。运筹学已被应用到各种管理工程中，在现代化建设中发挥着重要作用。随着科学技术和生产的发展，运筹学已渗入很多领域，发挥了越来越重要的作用。（二）运筹学的特点（1）广泛应用性 运筹学已被广泛应用于工商企业、军事部门、民政事业等研究组织内的统筹协调问题，故其应用不受行业、部门的限制。（2）实践性 运筹学既对各种经营进行创造性的科学研究，又涉及组织的实际管理问题，它具有很强的实践性，最终应能向决策者提供建设性意见，并应收到实效。（3）系统性 运筹学以整体最优为目标，从系统的观点出发，力图以整个系统最佳的方式来解决该系统各部门之间的利害冲突。对所研究的问题求出最优解，寻求最佳的行动方案，所以它也可看成是一门优化技术，提供的是解决各类问题的优化方法。（三）运筹学的研究方法（1）从现实生活场合抽出本质的要素来构造数学模型，因而可寻求一个跟决策者的目标有关的解。在运筹学研究中，首先需要根据所要解决的问题，明确因变量，提出目标函数。然后分析影响因素有哪些，其中最主要的关键因素是什么。明确自变量，通过收集大量数据，确定函数关系。（2）探索求解的结构并导出系统的求解过程 运筹学建立的模型需要应用到以后相似的问题中，因此一方面要求其求解过程要科学、严谨；另一方面运筹学模型的求解过程长，计算量大，如果采用手工计算，需要耗费大量的时间。随着信息技术的发展，只需要将求解算法详细步骤探索清楚，就可以编成计算机软件进行计算，可大大提高其运算速度。（3）从可行方案中寻求系统的最优解法 一般数学模型计算的最优解不一定是可行的。如图1-1所示，一只兔子在位置O，狗位于A点，已知狗的奔跑速度为v，兔子的奔跑速度为v，兔子发现狗在追12它时，会沿着水平向右的方向逃跑，问狗应该怎样奔跑才能抓到兔子。该问题要是从数学角度出发，可以归结为狗和兔子的相遇问题，根据二者的位置参数和速度参数，就可以计算出二者相遇的地点，假如为B点，则狗在兔子发现自己并开始水平向右奔跑后直接奔B点而去，这样当狗跑到B点时，兔子正好也到B点，狗跑的路程也是最短，消耗体力也最小，从数学上看，一定是最优解。但实际上，如果兔子跑了一小段距离后发现狗根本就不是朝自己来的，完全会停止奔跑，这样即使狗跑到B点也抓不到兔子。可见该最优解根本就不是可行解。而可行解应该是狗在A点时就一直眼睛紧盯兔子跑，兔子一看狗始终朝着自己奔跑，就会全速向右逃跑，而狗也会始终两眼紧盯兔子，随时修正自己的奔跑方向，结果跑出的是一条抛物线，最终会在C点抓住兔子。从中可以看出，狗跑的路程确实长了不少，但这保证能抓到兔子。因此在用模型求出解后一定要与定性相结合，确定解的可行性，一定是在可行解中选择最优解。图1-1 狗追兔（四）运筹学的具体内容
运筹学的具体内容包括：规划论（包括线性规划、非线性规划、整数规划和动态规划）、图论、对策论、排队论、搜索论、可靠性理论等。
1.规划论
数学规划的研究对象是计划管理工作中有关安排和估值的问题，解决的主要问题是在给定条件下，按某一衡量指标来寻找安排的最优方案。它可以表示成求函数在满足约束条件下的极大极小值问题。
数学规划和古典的求极值的问题有本质上的不同，古典方法只能处理具有简单表达式和简单约束条件的情况。而现代的数学规划中的问题目标函数和约束条件都很复杂，而且要求给出某种精确度的数字解答，因此算法的研究特别受到重视。
这里最简单的一种问题就是线性规划。如果约束条件和目标函数都是呈线性关系的就叫线性规划。要解决线性规划问题，从理论上讲都要解线性方程组，因此解线性方程组的方法，以及关于行列式、矩阵的知识，就是线性规划中非常必要的工具。
线性规划及其解法——单纯形法的出现，对运筹学的发展起了重大的推动作用。许多实际问题都可以化成线性规划来解决，而单纯形法又是一个行之有效的算法，加上计算机的出现，使一些大型复杂的实际问题的解决成为现实。
非线性规划是线性规划的进一步发展和继续。许多实际问题如设计问题、经济平衡问题都属于非线性规划的范畴。非线性规划扩大了数学规划的应用范围，同时也给数学工作者提出了许多基本理论问题，使数学中的如凸分析、数值分析等也得到了发展。还有一种规划问题和时间有关，叫作“动态规划”。近年来在工程控制、技术物理和通信中的最佳控制问题中，已经成为经常使用的重要工具。【例1-1】 某企业生产A和B两种产品，每月电力消耗不超过240kW·h，设备不超过150台时，每吨产品电力、设备消耗定额见表1-1。A产品每吨可获利润2000元，B产品每吨可获利润4000元，两种产品各生产多少吨，可使企业在充分利用资源的条件下获利最大？表1-1 企业各产品资源消耗表
建立线性规划模型的程序为：（1）确定变量；（2）列出约束条件；（3）确定目标函数。
例1-1中，变量：X——A产品产量；1
X——B产品产量。2
约束条件：3X+8X＜240；12
6X+3X＜150；12
X＞0，X＞0。12
目标函数：Z=2000X+4000X。max12
计算方法主要有图解法、单纯形法。经计算，得：X=12.3t， X=25.4t， Z=126200元。12max
2.图论
图论是一个古老但又十分活跃的分支，它是网络技术的基础。图论就是以点来代表事物，以边来代表事物之间的关系从而构造出图形，并以图形为研究对象来解决距离最短、时间最少、费用最省、流量最大等实际问题的方法。
图论的创始人是数学家欧拉。1736年他发表了图论方面的第一篇论文，解决了著名的哥尼斯堡七桥问题，相隔100年后，在1847年基尔霍夫第一次应用图论的原理分析电网，从而把图论引进到工程技术领域。20世纪50年代以来，图论的理论得到了进一步发展，将复杂庞大的工程系统和管理问题用图描述，可以解决很多工程设计和管理决策的最优化问题，例如，完成工程任务的时间最少，距离最短，费用最省，等等。图论在数学、工程技术及经营管理等各方面受到越来越广泛的重视。
3.排队论
排队论又叫作随机服务系统理论。它的研究目的是要回答如何改进服务机构或组织被服务的对象，使得某种指标达到最优的问题。比如一个港口应该有多少个码头，一个工厂应该有多少维修人员等。
因为排队现象是一个随机现象，因此在研究排队现象的时候，主要采用的是研究随机现象的概率论作为主要工具。此外，还有微分和微分方程。排队论把它所要研究的对象形象地描述为顾客来到服务台前要求接待。如果服务台已被其他顾客占用，那么就要排队。另外，服务台也时而空闲时而忙碌，就需要通过数学方法求得顾客的等待时间、排队长度等的概率分布。
排队论在日常生活中的应用是相当广泛的，比如水库水量的调节、生产流水线的安排、铁路货场的调度、电网的设计等。
4.可靠性理论
可靠性理论是研究系统故障以提高系统可靠性问题的理论。可靠性理论研究的系统一般分为两类：①不可修系统，如导弹等，这种系统的参数是寿命、可靠度等；②可修复系统，如一般的机电设备等，这种系统的重要参数是有效度，其值为系统的正常工作时间与正常工作时间加上事故修理时间之比。
5.搜索论
搜索论是由于战争的需要而出现的运筹学分支，主要研究在资源和探测手段受到限制的情况下，如何设计寻找某种目标的最优方案，并加以实施的理论和方法。它是在第二次世界大战中，同盟国的空军和海军在研究如何针对轴心国的潜艇活动、舰队运输和兵力部署等进行甄别的过程中产生的。搜索论在实际应用中也取得了不少成效，例如20世纪60年代，美国寻找在大西洋失踪的核潜艇“打谷者号”和“蝎子号”，以及在地中海寻找丢失的氢弹，都是依据搜索论获得成功的。
6.对策论
对策论也叫博弈论，研究当一个主体的行为选择受到其他主体行为选择的影响，而且反过来又影响到其他主体行为选择时的决策和均衡问题。博弈是指一些个人、团队或组织，面对一定的环境条件，在一定的规则下，同时或先后，一次或多次，从各自允许选择的行为或策略中进行选择并加以实施，各自从中取得相应结果的过程。
传统决策理论主要讨论单个企业在资源约束条件下实现利润最大化的市场行为。而博弈论则强调企业在市场竞争环境中竞争各方的市场行为将对自己的市场行为选择产生影响以及自己的行为会对竞争者产生影响的情况下，如何实现利益均衡化的市场行为。
博弈决策的基本规则是：我所做的是给定你所做的我所能做得最好的，你所做的是给定我所做的你能做得最好的。博弈根据行动的先后顺序可分为静态博弈和动态博弈。静态博弈是参与人同时选择或者虽非同时但后行动者并不知道先行动者采取什么样的行动。动态博弈是参与人的行动有先后顺序，并且后行动者能观察到先行动者所选择的行动。博弈根据参与人对信息的掌握情况还可分为完全信息博弈和不完全信息博弈。下面我们来看一个完全信息博弈和不完全信息博弈的例子：
有一个走街串巷收集散落民间文物的古董商，在一个农民家里发现其喂猫的碗竟然是一件非常稀有的文物珍品。于是古董商便假装对这只猫十分喜爱，要从农民手里买下。农民不卖，为此古董商出了大价钱。成交之后，古董商装作不经意地说：“这个碟子它已经用惯了，就一起送给我吧。”农民不干了，说道：“你知道靠这个碟子，我已经卖出多少只猫了吗？”
这是一个“信息博弈”的例子。古董商掌握“碟子是古董”这个信息，他认为农民不知道，这种“信息不对称”对他有利，可他万万没想到，农民不但知道，而且利用了他“认为对方不知道”的错误而大赚了一笔。这才是真正的“信息不对称”。二、物流决策技术（一）物流决策技术的定义
物流决策分析技术主要研究物流活动中能用数量来表达的业务决策方面的问题，根据问题的要求，通过数学上的分析、运算，得出各种各样的结果，最后提出综合性的合理安排，以达到降低物流总成本，提高物流效率的目的。
物流是物品从供应地向接受地的实体流动过程。物流业务过程就是根据实际需要，将运输、储存、装卸、搬运、包装、加工、配送、信息处理等基本功能实施有机结合。在物流业务活动中，面临物流需求预测、物流设施选址决策、设施内部规划、设备设施等项目投资决策、货物库存与采购批量决策、供应商评价与选择、运输方式选择、运输路线规划、包装选择、作业排序、任务指派、物流业务核算等定量决策。物流运筹学就是要在物流经营管理定性决策的基础上，采用定量分析方法，计算出各种各样的结果，最后根据经营管理需要，提出综合性的合理安排，以达到切实降低物流总成本的目的。
物流决策分析技术需要借助一些运筹学的方法来解决物流业务决策问题，但不是简单的运筹学方法在物流中的应用，而是从物流业务与管理活动中的定量决策问题出发，采用科学合理的定量分析方法来进行决策分析，因此除了采用运筹学中的图论、规划模型、运输问题、存储问题等方法之外，还会采用会计和统计分析的有关方法。（二）物流决策技术的内容
根据定义，物流决策分析的内容应该包括整个物流业务与管理活动中能用数量来表达的所有业务决策。而这些定量决策业务贯穿于整个供应链的物流过程，内容多而繁杂。本书将根据物流业务活动需要，考虑一般物流专业课程体系设置与教学特点要求，选择具有一定难度的部分内容作为本书的内容。（1）运输路线选择 运输路线选择包括两点间直送式运输路线选择、单回路分送式运输路线选择、多回路分送式运输路线选择、最大流运输路线选择以及最小费用最大流运输路线选择。（2）货物调运与配装方案编制 货物调运包括不同条件下货物调运方案的编制，货物配装包括一般货物的积载和多品种混装方案的编制。（3）物流设施选址 物流设施选址包括单一设施选址、多设施连续点选址、多设施离散点选址。（4）仓储业务决策 仓储业务决策包括仓库的布局规划、库存控制策略选择、流通加工作业排序。（5）物流项目决策 物流项目决策包括物流项目投资决策分析和物流项目任务指派。（三）物流决策技术应用中的注意事项（1）明确物流活动的目标 物流活动从本质上讲是一种服务活动，就是要在正确的时间，将正确数量和质量的商品以合适的价格和正确的方式送到正确的地点。可见物流活动的经营的关键就是要以较低的成本满足客户对物流服务的需求。（2）正确把握物流成本与物流服务之间的关系 物流成本与物流服务之间存在“效用递减”。一般来说，提高物流服务，物流成本即上升，成本与服务之间受“效用递减法则”的支配。物流服务如处于低水平阶段，追加成本ΔX，物流服务即可上升为ΔY；如处于高水平阶段，同样追加ΔX，则服务水平只能上升至ΔY'，并且ΔY'＜ΔY，如图1-2所示。也就是说处于高水平的物流服务时，成本增加而物流服务水平不能按比例地相应提高。与处于竞争状态的其他企业相比，在处于相当高的服务水平的情况下，想要超过竞争对手，提出并维持更高的服务标准就需要有更多的投入，所以一个企业在做出这种决定时必须慎重。图1-2 服务成本与服务质量关系图
基于物流成本与服务的关系，物流企业的策略选择，总体来说，作为经营管理一环的物流管理，必须首先设定作为物流目的的必要而充分的物流服务水平，然后以较低的成本构筑物流系统进行运作。在实际中，可以根据不同客户、不同管理目标有以下四种选择。
①在物流服务不变的前提下考虑降低成本。不改变物流服务水平，通过改变物流系统来降低物流成本，这是一种尽量降低成本来维持一定服务水平的办法，也即追求效益的办法。
②为提高物流服务，不惜增加物流成本。这是许多企业提高物流服务的做法，是企业在特定顾客或其特定商品面临竞争时，所采取的具有战略意义的做法。
③积极的物流成本对策，即在成本不变的前提下提高服务水平。在给定成本的条件下提高服务质量。这是一种追求效益的办法，也是一种有效地利用物流成本性能的办法。
④用较低的物流成本，实现较高的物流服务。这是增加销售、增加效益、具有战略意义的办法。
以上办法，企业究竟如何选择，应通盘考虑商品战略和地区销售战略，流通战略和竞争对手，物流成本、物流系统所处的环境，以及物流系统负责人所采用的方针等。（3）全面认识物流各功能要素之间存在的“效益背反”关系 物流包括仓储、运输、配送、包装、装卸搬运、流通加工和信息处理七个功能要素。这七个要素也是物流业务活动的七个基本环节。这些功能要素之间存在明显的效益背反现象。比如运输成本的降低必然要求实行大批量的整车运输，但这必然带来仓储成本的大幅度上升，同时要减少运输和装卸搬运中的货物损耗，就需要增加包装强度，这必然导致包装成本上升；要提高物流作业的效率，降低作业成本，必然就需要建立现代化的甚至是智能化的信息系统，这必然导致信息处理成本的大幅度上升。（4）正确认识物流决策分析技术在物流经营管理中的作用——系统降低物流总成本 物流运筹学主要研究物流活动中能用数量来表达的业务决策方面的问题，如选址问题、配送运输路线规划问题、装货问题、物资调运问题、库存问题、项目优化等问题，并根据问题的要求，通过数学上的分析、运算，得出各种各样的结果，最后提出综合性的合理安排，以达到降低物流总成本，提高物流效率的目的。因此，也正是物流运筹学为物流经营管理中优化物流系统，降低物流总成本提供了科学有效的方法。任务实施
丁谓修宫中，丁谓采取的办法是：先叫工人们在皇宫前的大街上挖深沟，挖出来的泥土即作为施工用的土，这样就不必再到郊外去挖了，同时节省了大量运土所需的工人。过了一些时候，施工用土充足了，而大街上出现了宽阔的深沟，一股汹涌的河水从汴河河堤的缺口处奔流出来，涌向深沟之中。等汴河的水和深沟中的水一样高时，一只只装运着石料的木筏缓缓地撑到皇宫前。最后，等到材料运输任务完成之后，再把沟中的水排掉，把工地上的垃圾填入沟中，使沟重新变为平地。一条平坦宽阔的大路静静地躺在皇宫之前。简单归纳起来，就是这样一个过程：挖沟（取土）→引水入沟（水道运输）→填沟（处理垃圾）。
按照这个施工方案，不仅节约了许多时间和劳动力，从而节省了大量经费，而且使工地秩序井然，使城内的交通和生活秩序不受施工太大的影响，确实是很科学的施工方案。
该事例说明办事情如果要达到高效率，就要时时处处统筹兼顾，巧妙安排好财力、物力、人力和时间。同时，降低物流成本最好的办法就是要统筹规划，减少整个系统的物流量。模块二 运输路线选择单元一 两点间直送式运输最短路线选择◆ 知识目标（1）明确两点直送式运输、图、网络、完全图、不完全图、有向图、图的权矩阵、回路、度、奇点、偶点等有关名词的含义。（2）掌握迪克斯彻标号算法、逐次逼近法和弗洛伊德算法、动态规划法的基本步骤及其应用。◆ 能力目标（1）学会求解指定两点间直送运输最短路线。（2）学会求解指定点到网络中其余各点的直送运输最短路线。（3）学会求解网络中任意两点间的直送运输最短路线。任务一 指定两点间直送运输最短路线选择任务描述
某物流公司要把一批货物从如图2-1所示的公路网络中的v点运1到v点。网络中各边旁边的数字表示相应两点之间的公路里程（单位：6km）。试问：汽车应走什么路线才能使行驶的里程最少？图2-1
该任务的一般情况是：某一种货物要从一个发货点运送到一个收货点，运输量不超过车辆的满载量，发货点与收货点之间交通网的每段路线的长度已知。目标是要找出发货点和收货点之间的最短运输路线。相关知识一、图与网络基本知识
1.图的基本概念（1）图与无向图 图由表示具体事物的点（顶点）的集合V={v，v，…，v}和表示事物之间关系边的集合E={e，e，…，e}
12n12m所组成，且E中元素e是由V中的无序元素对［v，v］表示，即iije=［v，v］，记为G=（V，E），并称这类图为无向图。iij
简单说，图就是由表示具体事物的点的集合和表示事物之间关系的边的集合组成的反映事物之间关系的一种工具。因此图与它的边的形状和点的位置安排是没有关系的。无向图就是边没有方向的图，是双向可通的。
例如，图2-2中，有8条边，6个顶点，即V={v，v，…，v}；126E={e，e，…，e}。其中：128图2-2（2）多重边与自环 具有相同端点的边称为多重边或平行边；两个端点落在一个顶点的边称为自环。图2-2中的e与e是多重边，78e是一个自环。4（3）多重图和简单图 含有多重边的图称为多重图；无自环也无多重边的图称为简单图。图2-2就是一个多重图。（4）相邻点和相邻边 同一条边的两个端点称为相邻点，简称邻点；有公共端点的两条边称为相邻边，简称邻边。在实际中可以借助图形工具和相邻关系用来安排不能放在一起的人、货物、项目、课程等。例如6个人围成圈就座，每个人恰好只与相邻者不相识，问：是否可以重新就座，使每个人都与邻座认识？
对于该问题，我们可以用点表示人，用边表示两人相互不认识，绘图［见图2-3（a）］。
要求重新就座后使每个人都与邻座认识，只需要以其中任意一个人为基准，如A，则依次往下排的必须是剩余点中不相邻的，并且最终的序列中相邻两人之间在图中必须不能相邻，如A-D-F-B-E-C-A就能保证彼此之间都认识。
再如，有甲、乙、丙、丁、戊、己6名运动员报名参加A、B、C、D、E、F 6个项目的比赛。报名情况如表2-1所示。问如何安排比赛顺序才能保证每名运动员不连续参加两项比赛。表2-1 6名运动员比赛报名表
同理，用点表示体育项目，用边表示由同一个人参加的项目，绘图见图2-3（b）。要保证每名运动员不连续参加两项比赛，只需在安排项目时相邻两个项目在图2-3（b）中是不相邻即可。A-F-E-D-C-B就可以满足条件。图2-3（5）度（次） 以v为端点的边的条数称为点v的度，记作iid（v）。如图2-2所示，d（v）=1；d（v）=5；d（v）=2；d（v）
i1234=5；d（v）=3；d（v）=0。56（6）悬挂点和悬挂边 度为1的点称为悬挂点；与悬挂点相连的边称为悬挂边。图2-2中v是悬挂点，e是悬挂边。11（7）孤立点 度为零的点称为孤立点。图2-2中的v是孤立点。6（8）奇点与偶点 度为奇数的点称为奇点；度为偶数的点称为偶点。图2-2中v是奇点，v是偶点。23
定理2-1 图G=（V，E）中，所有点的度之和是边数的两倍。即
定理2-1是显然的，因为在计算各点的次时，每条边都计算两次，于是图G中全部顶点的次之和就是边数的2倍。
定理2-2 任一图G=（V，E）中，奇点的个数为偶数。
证：设V、V分别是G中奇点和偶点的集合，由定理2-1可知12
因为是偶数，而也是偶数，故也必是偶数，由于偶数个奇数才能导致偶数，所以有奇点的个数必须为偶数。（9）有向图 边有方向的图。在很多实际问题中，事物之间的联系是带有方向性的。例如水系流向图，就是一个有向图。设V={v，1v，…，v}是由n个顶点组成的非空集合，A={a，a，…，a}是由m2n12m条边组成的集合，且有A中元素a是V中一个有序元素对（v，v），则iij称V和A构成一个有向图，记作G=（V，A），a=（v，v）表明v和viijij分别为a边的起点和终点，称有方向的边a为弧（在图中用带有箭头ii的线表示）。图2-5就是一个有向图。
有向图的出度与入度：有向图中，以v为始点的边数称为点v的ii+-出度，用d（v）表示；以v为终点的边数称为点v的入度，用d（v）iiii表示；v点的出度和入度之和就是该点的度。i
所有顶点的入度之和等于所有顶点的出度之和。（10）完全图 每一对顶点间都有边相连的无向简单图称为完全图。有向完全图则是指任意两个顶点之间有且仅有一条有向边的简单图。
2.网络与有向网络（1）网络 设G=（V，E）中，对任意一条边e∈E，如果相应都有一个权值，则称G为网络。简言之，边旁边有数字的无向图称为网络。图中边旁边的数字称为权，记为w。权可以代表距离、费用、容ij量、流量等。图2-4是一个网络，其中w=w=1；w=w=4；12211331w=2；w=3；w=1；w=5；w=2；w=3。232434254535图2-4
可见，网络不仅指出各点之间的邻接关系，而且也表示各点之间的数量关系，所以网络在图的理论及其应用方面有着重要的地位。（2）有向网络 我们还会碰到这样一类有向图，如图2-5所示，这是某地区的交通运输分布、走向及相应费用示意图。箭头表示走向，箭头旁边的数字表示费用，称这类图为有向网络。图2-5
设在有向图G=（V，A）中对任意一条弧a∈A，如果相应都有ij一个权值w（a）则称G为有向网络。W（a）称为弧a的权，简记为ijijijw（权可以表示距离、费用、时间容量、流量等）。简言之，边有权ij的有向图称为有向网络。
在实际工作中，有很多问题的可行解决方案都可以通过一个有向网络表示，例如：物流渠道的设计、物资运输路线的安排、装卸设备的更新、排水管道的铺设等，所以有向网络被广泛应用于解决工程技术及科学管理等领域的最优化问题。
3.路和回路（1）路 由图中相邻的点与边构成的且点不相同的交错序列，就称为连接该序列首尾两点之间的一条路。如图2-4所示，μ=（v，12e，v，e，v，e，v）连接v与v的路。23346525（2）回路 由图中相邻的点与边构成的且首尾两点相同交错序列，就称为回路。如图2-4中，μ=（v，e，v，e，v，e，v，21122334e，v，e，v）是一条回路。5211
4.路长与最短路（1）路长 路中各边的权之和，称为该条路的路长。如图2-5所示，v与v中间的一条路：v→v→v→v的路长为5+3+6=14。171267（2）最短路 两点间所有路中路长最短的那条路就称为最短路。二、求解指定两点间直送运输最短路的迪克斯彻标号算法的基本步骤（1）给起点v以P标号（永久标号），令P（v）=0，并在图中的ss起点旁标注“”，其余各点均给T标号（临时标号），令T（v）=+∞，ii=1，2，…，n。（2）若v是刚得到P标号的点，考察v的所有相邻的T标号点v，iij并对v的T标号值进行更改：T（v）=min{T（v），P（v）+w}。jjjiij
并在图中点v旁标注新的T标号值：T（v）。jj（3）比较图中所有的T标号点，找出T标号值最小的点，假设为v，并把其改为P标号，即P（v）=min{T（v）}，同时在图中的该点kki旁的T（v）上标注“”，三角形中的P为其永久标号值，并将图中kv边加粗。ik（4）返回第（2）步，直到指定点得到永久标号或所有点都得到永久标号为止。
注意：迪克斯彻标号算法只适用于权为非负的网络。任务实施（1）给起点v以P标号（永久标号），令P（v）=0，并在图中的11起点旁标注“”，其余各点均给T标号（临时标号），令T（v）=+∞，ii=2，3，4，5，6；如图2-6所示。（2）v是刚得到P标号的点，考察v的所有相邻的T标号点v、v，1123并更改其T标号值：T（v）=min{T（v），P（v）+w}=min{+∞，0+4}=422112T（v）=min{T（v），P（v）+w}=min{+∞，0+11}=1133113
并在图中各点旁标注新的T标号值，如图2-6所示。（3）比较图中所有的T标号点。
因为min{T（v），T（v），T（v），T（v），T（v）}=min{4，2345611，+∞，+∞，+∞}=T（v）=42
所以令P（v）=4，并标注在图中，同时将图中边vv加粗；如212图2-6所示。图2-6（4）v是刚得到P标号的点，考察v的所有相邻的T标号点v、v，2245并更改其T标号值：T（v）=min{T（v），P（v）+w}=min{+∞，4+7}=1144224T（v）=min{T（v），P（v）+w}=min{+∞，4+2}=655225
并在图中各点旁标注新的T标号值，如图2-6所示。
因为min{T（v），T（v），T（v），T（v）}=min{11，11，34566，+∞}=T（v）=65
所以令P（v）=6，并标注在图中，同时将图中边vv加粗；见525图2-6。（5）v是刚得到P标号的点，考察v的所有相邻的T标号点v、v，5546并更改其T标号值：T（v）=min{T（v），P（v）+w}=min{11，6+3}=944554T（v）=min{T（v），P（v）+w}=min{+∞，6+8}=1466556
并在图中各点旁标注新的T标号值，如图2-6所示。
因为min{T（v），T（v），T（v）}=min{11，9，14}=T（v）3464=9
所以令P（v）=9，并标注在图中，同时将图中边vv加粗；见454图2-6。（6）v是刚得到P标号的点，考察v的所有相邻的T标号点v、v，4436并更改其T标号值：T（v）=min{T（v），P（v）+w}=min{11，9+1}=1033443T（v）=min{T（v），P（v）+w}=min{14，9+4}=1366446
并在图中各点旁标注新的T标号值，如图2-6所示。
因为min{T（v），T（v）}=min{10，13}=T（v）=10363
所以令P（v）=10，并标注在图中，同时将图中边vv加粗；见343图2-6。（7）v是刚得到P标号的点，考察v的所有相邻的T标号点v，336并更改其T标号值：
T（v）=min{T（v），P（v）+w}=min{13，10+2}=1266336
此时，就剩v一点了，所以直接令P（v）=12，并标注在图66中，同时将图中边vv加粗；如图2-6所示。36
从图2-6可知，从城市v到v的最短路为：v→v→v→v→v→1612543v，路长为12。图中粗线就是起点v到各点的最短路线，各点旁边的61永久标号值就是起点v到各点的最短路的路长。1实践训练（1）有8种化学药品A、B、C、D、E、F、G、H要放进储藏室。从安全角度考虑，下列各组药品不能储存在同一室内：A-C，A-F，A-H，B-D，B-F，B-H，C-D，C-G，D-E，D-G，E-G，F-G，G-H。问：至少需要几间储藏室存放这些药品？（2）10名学生参加6门课程（A～F）考试，由于选修内容不同，考试门数也不一样。每名学生参加考试的课程如表2-2所示。规定考试在三天内结束，每天上下午各安排一门。学生希望每人每天最多只考一门，课程A必须安排在第一天上午，课程F安排在最后一门，课程B只能安排在下午考，试列出一张满足各方面要求的考试日程表。表2-2 10名学生参加考试课程表（3）求如图2-7所示的运输网络中从城市R到W的最短路及其路长。图2-7（4）求如图2-8所示的运输网络中从v到v的最短路及其长度。18图2-8（5）在如图2-9所示的高速路网中，A点是始发点，J是终点，其他各点均为中间点；各边的权表示相应两点之间高速公路的长度，单位是km。试求一条从始发点A到J的最短运输路线。图2-9（6）如图2-10所示为一幅供水管网图，其中v是大型水库，v至12v为需水城市，求v到v的最短供水路线。818图2-10（7）求如图2-11所示的运输网络中从v到v的最短路及其长度。18图2-11（8）如图2-12所示网络中的9个点表示9个在不同地区的城市，它们之间的连线代表它们之间有公路相通，连线旁的数字代表相应的里程（单位：km）。现有一批货物要从城市A运到城市I。运费的多少与路线的长短成正比。求从城市A到I之间的最少运费相应的路线。图2-12（9）如图2-13所示A是仓库，J是商店，求一条从A到J的最短路。图2-13（10）求图2-14中v到v的最短路。111图2-14（11）求图2-15中v到v的最短路。111图2-15任务二 指定点到网络中其他点间的最短运输路线选择任务描述
图2-16是5个城市之间的交通运费图，图中v是物流中心，v、12v、v、v为四个客户所在地，运费为负表示这两城之间能附带运货，345增加的收入大于运费。求物流中心到各客户的最小运费路线及其总运费。图2-16
该任务的一般情况是：某一种货物要从一个发货点分别运送到网络中其余各收货点，运输量不超过车辆的满载量，发货点与收货点之间不止一条路，交通网络中的每段路线的长度已知。在运费与运输距
试读结束[说明：试读内容隐藏了图片]