1、4 4 运输经营管理决策分析运输经营管理决策分析4.1 4.1 运输自营与外包的比较分析运输自营与外包的比较分析4.2 4.2 自运与外包的定量分析自运与外包的定量分析 4.3 4.3 设备配置与更新策略设备配置与更新策略4.4 4.4 运输路线的规划运输路线的规划4.1 运输自营与外包的比较分析运输自营与外包的比较分析 一、物流运输外包一、物流运输外包 1 1、物流运输外包的优势、物流运输外包的优势（1 1） 业务优势业务优势 可以使生产企业获得自己本身不能提供的物流服务可以使生产企业获得自己本身不能提供的物流服务 。（2 2） 成本优势成本优势 一方面，物流外包可降低生产企业运作成本。一方
2、面，物流外包可降低生产企业运作成本。此外，可以避免盲目投资。 （3 3）客户服务优势）客户服务优势 由于第三方物流企业在信息网络和配送结点上具有资源优势，这使得他们在由于第三方物流企业在信息网络和配送结点上具有资源优势，这使得他们在提高顾客满意度上具有独到的优势。提高顾客满意度上具有独到的优势。 2 2、物流运输外包的局限性、物流运输外包的局限性(3(3个方面）个方面）（1）物流企业的素质问题）物流企业的素质问题 物流公司的数目不少，但是良莠不齐。许多物流公司的业务水平、人员素质物流公司的数目不少，但是良莠不齐。许多物流公司的业务水平、人员素质和经营规模都不高。和经营规模都不高。 （2）企业物
3、流资源处理问题）企业物流资源处理问题 沉没成本沉没成本企业在退出某一行业时，其投资形成的固定资产不能被转卖企业在退出某一行业时，其投资形成的固定资产不能被转卖或只能以低价转卖，造成的不可收回的资本损失。或只能以低价转卖，造成的不可收回的资本损失。 全社会物流资源优化配置的角度看，生产企业建设的物流设施存在着总量过全社会物流资源优化配置的角度看，生产企业建设的物流设施存在着总量过剩、结构失调等问题，有的甚至具有极强的专用性，给企业带来巨大的沉没成剩、结构失调等问题，有的甚至具有极强的专用性，给企业带来巨大的沉没成本，形成较高退出障碍。本，形成较高退出障碍。企业退出物流领域时，需要解雇相关的物流部
4、门从业企业退出物流领域时，需要解雇相关的物流部门从业人员。人员。 （3 3）信用风险问题）信用风险问题 新制度经济学派的交易成本理论认为，物流活动的外购属于服务贸易，新制度经济学派的交易成本理论认为，物流活动的外购属于服务贸易，形成市场交易成本的主要原因是信息不对称而导致的信用风险。形成市场交易成本的主要原因是信息不对称而导致的信用风险。 物流服务的行为实际上是一系列物流服务的行为实际上是一系列委托与被委托、代理与被代理委托与被委托、代理与被代理的关系，的关系，是完全以信用体系为基础的。任何一个物流提供者出现信用问题，都将会是完全以信用体系为基础的。任何一个物流提供者出现信用问题，都将会影响物
5、流服务的效率。影响物流服务的效率。 美国，美国，物流企业物流企业要对供应商、工厂要对供应商、工厂提供银行出具提供银行出具的的信誉程度评估报告信誉程度评估报告，在物流委托方出货后，在物流委托方出货后，银行就会为其做信用担保银行就会为其做信用担保。 中国：信用危机导致送货延迟、错误投递等行为的发生以及生产企业中国：信用危机导致送货延迟、错误投递等行为的发生以及生产企业控制物流企业的短期行为，增加了物流服务交易成本。控制物流企业的短期行为，增加了物流服务交易成本。 这种成本的增加可能以两种形式表现出来，即物流外包支出增加和企这种成本的增加可能以两种形式表现出来，即物流外包支出增加和企业信誉度下降。业
6、信誉度下降。 4 4企业运输外包的条件企业运输外包的条件（1）企业是否将物流业务外包，关键看物流业务对其核心）企业是否将物流业务外包，关键看物流业务对其核心能力的影响程度能力的影响程度 （2）企业规模的大小也是影响其实施第三方物流的因素）企业规模的大小也是影响其实施第三方物流的因素 二、物流运输自营二、物流运输自营1 1、生产企业自营物流的两个层次：、生产企业自营物流的两个层次：（1 1）传统的自营物流主要源于生产经营的纵向一体化）传统的自营物流主要源于生产经营的纵向一体化 生产企业生产企业自备仓库、车队等物流设施自备仓库、车队等物流设施，内部设立综合管理部门统一，内部设立综合管理部门统一企业
7、物流运作或者是各部门各司其职、自行安排物流活动。企业物流运作或者是各部门各司其职、自行安排物流活动。 这种自营物流服务还这种自营物流服务还停留在简单的生产管理环节停留在简单的生产管理环节，对生产企业来说，对生产企业来说物流活动完全是一种附属产物物流活动完全是一种附属产物，而且物流沟通产销、降低成本和改进，而且物流沟通产销、降低成本和改进服务的重要作用没有发挥出来。服务的重要作用没有发挥出来。 这种传统的自营物流这种传统的自营物流不能带来产品增值效应不能带来产品增值效应。 （2 2）现代自营物流概念是基于生产企业供应链管理思想而提出的）现代自营物流概念是基于生产企业供应链管理思想而提出的 它把企
8、业的它把企业的物流管理职能提升到战略地位物流管理职能提升到战略地位，即通过科学、有效的物，即通过科学、有效的物流管理实现产品增值，夺取竞争优势。流管理实现产品增值，夺取竞争优势。 一般是在一般是在企业内部设立物流运作的综合管理部门企业内部设立物流运作的综合管理部门，通过资源和功，通过资源和功能的整合，能的整合，专设企业物流部或物流公司来统一管理企业的物流运作专设企业物流部或物流公司来统一管理企业的物流运作。 二、物流运输自营二、物流运输自营2 2、物流运输自营的优势、物流运输自营的优势（1 1）掌握控制权）掌握控制权 通过自营物流运输，企业可以对物流运输系统运作的全过程进行有效通过自营物流运输
9、，企业可以对物流运输系统运作的全过程进行有效的控制。的控制。 （2 2）盘活企业原有资产）盘活企业原有资产 我国目前生产企业中我国目前生产企业中73%73%的企业拥有汽车车队，的企业拥有汽车车队，73%73%的企业拥有仓库，的企业拥有仓库，33%33%的企业拥有机械化装卸设备的企业拥有机械化装卸设备, 3%, 3%的企业拥有铁路专用线。的企业拥有铁路专用线。 （3 3）降低交易成本）降低交易成本 选择物流外包，由于信息的不对称性，企业无法完全掌握物流服务商选择物流外包，由于信息的不对称性，企业无法完全掌握物流服务商完整、真实的资料。企业通过内部行政权力控制原材料的采购和产成品的完整、真实的资料
10、。企业通过内部行政权力控制原材料的采购和产成品的销售，避免多次交易花费以及交易结果的不确定性，降低交易风险，减少销售，避免多次交易花费以及交易结果的不确定性，降低交易风险，减少交易费用。交易费用。 （4 4）避免商业秘密的外露）避免商业秘密的外露 任何一个企业来说，其内部的运营情况都是处于相对封闭的环境下，企任何一个企业来说，其内部的运营情况都是处于相对封闭的环境下，企业为了保持正常的运营，特别是业为了保持正常的运营，特别是对于某些特殊运营环节如原材料的构成、对于某些特殊运营环节如原材料的构成、生产工艺等，不得不采取保密手段生产工艺等，不得不采取保密手段。 当企业当企业将运营中的物流要素外包将
11、运营中的物流要素外包，特别是引入第三方来经营其生产环节，特别是引入第三方来经营其生产环节中的内部物流时，其中的内部物流时，其基本的运营情况就不可避免地向第三方公开基本的运营情况就不可避免地向第三方公开。 而在某一行业专业化程度高、占有较高市场份额的第三方会拥有该行业而在某一行业专业化程度高、占有较高市场份额的第三方会拥有该行业的诸多客户，它们正是企业的竞争对手，企业物流外包就可能会通过第三的诸多客户，它们正是企业的竞争对手，企业物流外包就可能会通过第三方将企业经营中的商业秘密泄露给竞争对手，动摇企业的竞争力。方将企业经营中的商业秘密泄露给竞争对手，动摇企业的竞争力。 （5 5）提高企业的品牌价
12、值）提高企业的品牌价值 企业自建物流系统，就能够企业自建物流系统，就能够自主控制营销活动自主控制营销活动，一方面可以亲自为顾客，一方面可以亲自为顾客服务到家，提高企业在顾客群体中的亲和力，提升企业形象；另一方面，服务到家，提高企业在顾客群体中的亲和力，提升企业形象；另一方面，企业可以掌握最新的顾客信息和市场信息，从而根据顾客需求和市场发展企业可以掌握最新的顾客信息和市场信息，从而根据顾客需求和市场发展动向调整战略方案，提高企业的竞争力。动向调整战略方案，提高企业的竞争力。 3 3、物流运输自营的局限性、物流运输自营的局限性（1 1）资源配置管理难度大）资源配置管理难度大 物流活动最主要的环节就
13、是运输和仓储，因此，物流活动最主要的环节就是运输和仓储，因此，企业自营物流必须具备与生企业自营物流必须具备与生产能力相符的运输力量和仓储容量产能力相符的运输力量和仓储容量。 市场的供需存在着不可预期的波动性市场的供需存在着不可预期的波动性，则为企业经营带来一系列的风险。现，则为企业经营带来一系列的风险。现代物流正在向标准化的方向发展，企业为了保证与价值链上下游的有效链接，代物流正在向标准化的方向发展，企业为了保证与价值链上下游的有效链接，必须要改进物流设备，这将加大企业固定资金的投入必须要改进物流设备，这将加大企业固定资金的投入。 （2 2）管理协调难度大）管理协调难度大 物流活动涉及到企业生
14、产的方方面面，由于各部门都存在着独立的利益，都物流活动涉及到企业生产的方方面面，由于各部门都存在着独立的利益，都追求自身效益的最大化，在我国企业现有经营管理机制下，如何协调各方面的追求自身效益的最大化，在我国企业现有经营管理机制下，如何协调各方面的利益，甚至要求某些部门牺牲自身利益以达到企业整体效益的最大化是一件困利益，甚至要求某些部门牺牲自身利益以达到企业整体效益的最大化是一件困难的事。难的事。 三、比较分析及运作三、比较分析及运作 哪个环节可以自营，哪个环节需要外包完全哪个环节可以自营，哪个环节需要外包完全取决于取决于企业自身的物流处理能力企业自身的物流处理能力和和社会的物流服务能力社会的
15、物流服务能力。 对于物流自理能力不足、规模经济不明显并且物流业务对其核心能力影响甚对于物流自理能力不足、规模经济不明显并且物流业务对其核心能力影响甚小的中小型生产企业应该鼓励物流业务外包。小的中小型生产企业应该鼓励物流业务外包。 联盟或合联盟或合作作自营自营外包外包外 包 或 与外 包 或 与竞 争 者 合竞 争 者 合作作战战略略价价值值高高低低物流资源物流资源 低低 高高物流资源持有性物流资源持有性1.1.彻底外包：彻底外包： 对于物流资产不多，物流业务较少，物流部门人员少的生产企业，可以对于物流资产不多，物流业务较少，物流部门人员少的生产企业，可以将物流业务完全外包。将物流业务完全外包。
16、 也可以采用系统接管的方式。也可以采用系统接管的方式。 2.2.逐步外包：逐步外包： 对于物流资产较多、人员较多、物流业务较多的企业，一般宜采用逐步对于物流资产较多、人员较多、物流业务较多的企业，一般宜采用逐步过渡的方式，按物流业务与产品或地理区域分步实施。过渡的方式，按物流业务与产品或地理区域分步实施。保留仓储将配送外包。保留仓储将配送外包。 保留配送、仓储将运输外包。保留配送、仓储将运输外包。 把企业物流的信息系统外包。把企业物流的信息系统外包。 还可以保留物流资产、人员、业务，只把物流的管理职能外包。还可以保留物流资产、人员、业务，只把物流的管理职能外包。 4.2 4.2 自运与外包的定
17、量分析自运与外包的定量分析 一、可以定量化的因素一、可以定量化的因素1 1企业的生产规模企业的生产规模 2 2自营运输成本自营运输成本3 3专业运输公司的实力和运输价格专业运输公司的实力和运输价格二、不确定因素二、不确定因素 企业的企业的生产规模、各项成本和运输价格都可能发生变生产规模、各项成本和运输价格都可能发生变化化。 有些数据可以通过对历史资料的统计分析，求出它们有些数据可以通过对历史资料的统计分析，求出它们的的概率分布概率分布，这对决策分析有很大帮助。，这对决策分析有很大帮助。 定量分析主要可以采用成本分析法。定量分析主要可以采用成本分析法。 （1 1）成本分析模型）成本分析模型 运输
18、的各项成本费用，也可以按变化方式划分为固定成本和运输的各项成本费用，也可以按变化方式划分为固定成本和变动成本。所谓固定成本，是指与业务量的多少无关的成本费变动成本。所谓固定成本，是指与业务量的多少无关的成本费用。所谓变动成本，是指随业务量的多少而增减的成本开支。用。所谓变动成本，是指随业务量的多少而增减的成本开支。 设：设：C=C=总成本总成本 F=F=固定成本固定成本 V= V=单位变动成本单位变动成本 X=X=运输总量运输总量 则总成本的计算公式为：则总成本的计算公式为： C=F+VXC=F+VX三、定量分析举例三、定量分析举例 某工厂的产品要运往销售地，有两种方案可供选择，即自某工厂的产
19、品要运往销售地，有两种方案可供选择，即自运和外运。运和外运。 如果自己运输，需要添置运输装卸设备，每年将增加设备如果自己运输，需要添置运输装卸设备，每年将增加设备固定成本固定成本1212万元，此外，运输每件产品的直接成本为万元，此外，运输每件产品的直接成本为4040元。元。 如果外运，即委托社会专业运输公司运输，每件要支付如果外运，即委托社会专业运输公司运输，每件要支付100100元。元。 试分析两种方案的选择原则。试分析两种方案的选择原则。 选择原则选择原则设每年产品运输量为设每年产品运输量为X X，则外运（方案，则外运（方案1 1）的总成本为：）的总成本为： C C1 1100X100X令
20、两者之差为零，求出平衡点：令两者之差为零，求出平衡点： 2000 2000 自运（方案自运（方案2 2）的总成本为：）的总成本为： C C2 240X40X120000120000 当运输量当运输量X X大于大于20002000件时，宜采用方案件时，宜采用方案2 2；当运输量；当运输量X X小于小于20002000件时，宜件时，宜采用方案采用方案1 1。 方案选择方案选择 通过对历史资料和企业生产能力的分析预测，该产品运输量通过对历史资料和企业生产能力的分析预测，该产品运输量的分布如表的分布如表4-14-1所示。试分析企业应选择何中运输方案？所示。试分析企业应选择何中运输方案？ 表表4-1 产
21、品运输量的概率分布产品运输量的概率分布 产品运输量（产品运输量（X X） 1000 1000 1500 1500 2000 2000 2500 2500 3000 3000 概率（概率（% %） 20 20 25 25 30 30 15 15 10 10 根据数理统计的原理，产品运输量的期望值为：根据数理统计的原理，产品运输量的期望值为： 10000.215000.2520000.325000.1530000.120037560037530018502000X根据前面的选择原则，该企业应当采用运输方案根据前面的选择原则，该企业应当采用运输方案1 1，即运输外包。，即运输外包。 4.3 4.3
22、设备配置与更新策略设备配置与更新策略 一、设备配置问题一、设备配置问题 任何随机服务系统都包括顾客输入、排队和服务三个过程。根据任何随机服务系统都包括顾客输入、排队和服务三个过程。根据这个共性，才产生了处理这些问题的理论这个共性，才产生了处理这些问题的理论随机服务系统理论，即排随机服务系统理论，即排队论。队论。 介绍利用概率分布函数方法求解设备配置问题的步骤。介绍利用概率分布函数方法求解设备配置问题的步骤。 如何合理地设计和控制随机服务系统，使它既能满足顾客需要，如何合理地设计和控制随机服务系统，使它既能满足顾客需要，又能使机构的花费最为经济，这是我们关心的主要问题。又能使机构的花费最为经济，
23、这是我们关心的主要问题。 例如，按某企业的统计数字表明，必要车辆的数量例如，按某企业的统计数字表明，必要车辆的数量有一定分布，如表有一定分布，如表4-24-2所示。每台车辆每日费用如下：所示。每台车辆每日费用如下： 自备车辆使用费用：自备车辆使用费用：C C1 1 = 500 = 500 元元自备车辆闲置费用：自备车辆闲置费用：C C2 2 = 300 = 300 元元租用车辆费用：租用车辆费用：C C3 3 = 1000 = 1000 元元表表4-2 4-2 必要车辆分布情况必要车辆分布情况车辆（台）车辆（台） 1010辆辆 以下以下 10-15 10-15 辆辆 16-20 16-20 辆
24、辆 21-25 21-25 辆辆 26-30 26-30 辆辆 31-35 31-35 辆辆 35-40 35-40 辆辆 频率频率 10% 10% 20% 20% 25% 25% 20% 20% 15% 15% 5% 5% 5% 5% 频数累计频数累计 10% 10% 30% 30% 55% 55% 75% 75% 90% 90% 95% 95% 100% 100% 设企业配备车辆数设企业配备车辆数 X X 辆，而必要车辆数为辆，而必要车辆数为 Y Y，问题是，问题是X X为多少为多少时，才能使车辆费用达到极小。时，才能使车辆费用达到极小。 1.1.当当 Y Y X X 时，即必要车辆数比配
25、置的车辆数少的情况下，时，即必要车辆数比配置的车辆数少的情况下，所需费用等于运行费与闲置费之和，即：所需费用等于运行费与闲置费之和，即：C CYCYC1 1(XY)C(XY)C2 2。设设P(X)P(X)为必要车辆数对应的概率，则目标费用为为必要车辆数对应的概率，则目标费用为: : F(X1) YC1(XY)C2 2. 2.当当 Y X Y X 时，即必要车辆数比配置车辆数多的情况下，所时，即必要车辆数比配置车辆数多的情况下，所需费用等于运行费与租车费之和，即：需费用等于运行费与租车费之和，即：C CXCXC1 1(YX)C(YX)C3 3。 设设P(X)P(X)为必要车辆数对应的概率，则目标
26、费用为：为必要车辆数对应的概率，则目标费用为： F(X F(X2 2) ) XC XC1 1(YX)C(YX)C3 3 1)(XYYPXYYP1)(车辆总费用应该是：车辆总费用应该是：F(X)=F(XF(X)=F(X1 1)+F(X)+F(X2 2) ) YCYC1 1(XY)C(XY)C2 2+ XC+ XC1 1(YX)C(YX)C3 3 XYYP1)(1)(XYYP又有：又有： 1 ，代入上式，得到：，代入上式，得到：XYYP1)(1)(XYYPF(X)= F(X)= YCYC1 1(XY)C(XY)C2 2+1- XC+1- XC1 1(YX)C(YX)C3 3 XYYP1)(XYYP
27、1)(然后，利用微分法求极值，得到以下结果：然后，利用微分法求极值，得到以下结果：XYXYXYYPCYPCCCYPCdxXFdXF13113112)()()()()( 按频率累计数按频率累计数62.5%与表与表4-2对照，可知对照，可知X取值范围在取值范围在 21与与25 之间。之间。5 .225 . 121%20%55%5 .62)2125(21X 取取x22（台）（台）令令 =0 ，则得到：，则得到：成立时车辆总费用最小。成立时车辆总费用最小。%5 .62)(132131CCCCCYPXY)(XF 可进一步用插值方法求得：可进一步用插值方法求得： 车辆（台）车辆（台） 1010辆辆 以下以
28、下 10-15 10-15 辆辆 16-20 16-20 辆辆 21-25 21-25 辆辆 26-30 26-30 辆辆 31-35 31-35 辆辆 35-40 35-40 辆辆 频率频率 10% 10% 20% 20% 25% 25% 20%20% 15% 15% 5% 5% 5% 5% 频数累计频数累计 10% 10% 30% 30% 55% 55% 75%75% 90% 90% 95% 95% 100% 100% 1 1、某工厂的产品要运往销售地，有两种方案可供选、某工厂的产品要运往销售地，有两种方案可供选择，即自运和外运。择，即自运和外运。 如果自己运输，需要添置运输装卸设备，每年
29、将增如果自己运输，需要添置运输装卸设备，每年将增加设备固定成本加设备固定成本5050万元，此外，运输每件产品的直接万元，此外，运输每件产品的直接成本为成本为4040元。元。 如果外运，即委托专业运输公司运输，每件要支付如果外运，即委托专业运输公司运输，每件要支付10001000元。试分析两种方案的选择原则。元。试分析两种方案的选择原则。 课堂作业课堂作业:2 2、按某企业的统计数字表明，必要车辆的数量有、按某企业的统计数字表明，必要车辆的数量有一定分布，如表一定分布，如表4-54-5所示。每台车辆每日费用如下：所示。每台车辆每日费用如下： 自备车辆使用费用：自备车辆使用费用：C C1 1 =
30、1000 = 1000 元元 自备车辆闲置费用：自备车辆闲置费用：C C2 2 = 500 = 500 元元 租用车辆费用：租用车辆费用：C C3 3 = 3000 = 3000 元元车辆（台）车辆（台） 5辆辆 以下以下 5-10 辆辆 11-15 辆辆 16-20 辆辆 21-25 辆辆 26-30 辆辆 频率频率 10% 15% 20% 25% 20% 10% 频数累计频数累计 10% 25% 45% 70% 90% 100% 试分析配备车辆数量，使车辆费用达到极小。试分析配备车辆数量，使车辆费用达到极小。表表4-5 必要车辆分布情况必要车辆分布情况%80)(132131CCCCCYPX
31、Y23221%20%70%80)2125(21X4.4 4.4 运输路线的规划运输路线的规划图论方法在运输线路规划中的应用图论方法在运输线路规划中的应用一、邮路问题及其求解方法一、邮路问题及其求解方法二、最小连通问题及其求解方法二、最小连通问题及其求解方法三、应用实例三、应用实例输油管道铺设输油管道铺设一、邮路问题（一笔划问题）及其求解方法一、邮路问题（一笔划问题）及其求解方法问题表述：问题表述：某邮递员每天要某邮递员每天要走遍他们负责的投递地段走遍他们负责的投递地段。应该如。应该如何安排路线，才能使所走的距离最短？何安排路线，才能使所走的距离最短？有关概念：有关概念：奇点奇点从某一点出发点线
32、条有奇数条。从某一点出发点线条有奇数条。偶点偶点从某一点出发点线条有偶数条。从某一点出发点线条有偶数条。ABCDEGHIJKNML1111222211322122图中红色的字母表示的是奇点。图中红色的字母表示的是奇点。图图1求解步骤：求解步骤：1、在线性图中，添加弧（即双线条），使得到的新图、在线性图中，添加弧（即双线条），使得到的新图上没有奇点，如图上没有奇点，如图2所示。所示。（注意：如果邮递员走遍所有的路段，则路线图上所有（注意：如果邮递员走遍所有的路段，则路线图上所有的点都必须变成偶点，每一个点至少有一进一出。）的点都必须变成偶点，每一个点至少有一进一出。）ABCDEGHIJKNML1
33、111222211322122图图22、调整添弧，使每个圈的添弧总长度不大于圈总长度、调整添弧，使每个圈的添弧总长度不大于圈总长度的一半。的一半。ABCDEGHIJKNML1111222211322122图图3总长度为总长度为6，而添弧总长度，而添弧总长度为为5，所以去掉原来的添弧，所以去掉原来的添弧B-H,H-I和和C-I,在该圈未在该圈未添弧的路段添弧的路段B-C上添弧。上添弧。总长度为总长度为8，而添弧总长度，而添弧总长度为为5，所以去掉原来的添弧，所以去掉原来的添弧I-K,I-M,在该圈未添弧的在该圈未添弧的路段路段K-N,M-N上添弧。上添弧。ABCDEGHIJKNML1111222
34、211322122图图4ABCDEGHIJKNML1111222211322122图图53、最优解：在图、最优解：在图5中，所有的圈的添弧部分的长度都不超过中，所有的圈的添弧部分的长度都不超过整圈长度的一半，所以它构成一个最优解。整圈长度的一半，所以它构成一个最优解。 设设L点为邮局，则可以一笔画出邮递员送信的最短路点为邮局，则可以一笔画出邮递员送信的最短路径如图径如图6所示。所示。ABCDEGHIJKNML1111222211322122图图6二、最小连通问题及其求解方法二、最小连通问题及其求解方法 问题表述：有问题表述：有N N个点，它们之间的距离为已知，个点，它们之间的距离为已知，如何把
35、各点连接成一个连通图，使其连线的总长度如何把各点连接成一个连通图，使其连线的总长度最短？最短？ 求解步骤：求解步骤： 第一步：在图的边集合中取一条边第一步：在图的边集合中取一条边e e1 1, ,使其长度是所有使其长度是所有边中长度最小者。边中长度最小者。 第二步：如果选好第二步：如果选好e e1 1，e e2 2，e ek k，则再从剩余的边集，则再从剩余的边集合中选取边合中选取边e ek k1 1，满足：，满足：使使e e1 1，e e2 2，e ek k， e ek k1 1组成组成的图的图不含圈不含圈； e ek k1 1在剩余的边集合中是长度最短者在剩余的边集合中是长度最短者。直至选
36、取的边数为直至选取的边数为N-1N-1时为止。时为止。图图7图中共图中共1313条边，边长最短者为条边，边长最短者为1 1，首先选取为，首先选取为e e1 1，如图，如图7 7中中的粗线段。的粗线段。63233321244686323332124468第二步：在剩余的边长中，最小者为第二步：在剩余的边长中，最小者为2 2，有三条，依次选，有三条，依次选取之，由于这三条与前面的几条均不构成圈，因此都能选取之，由于这三条与前面的几条均不构成圈，因此都能选取，见图取，见图8 8。图图86323332124468第三步：在剩余的边长中，长度为第三步：在剩余的边长中，长度为3 3的边有四条，能够选的边有
37、四条，能够选取其中两条。取其中两条。图图9能构成能构成圈，因圈，因此不能此不能选取。选取。6323332124468第四步：应该选取第四步：应该选取8 81 17 7条边，还剩下一条边需要选取。条边，还剩下一条边需要选取。剩下的最短的边是长度为剩下的最短的边是长度为4 4的边有两条，只有其中一条能的边有两条，只有其中一条能够选取。够选取。图图10能构成圈，因能构成圈，因此不能选取。此不能选取。6323332124468图图10连接线的总长度为：连接线的总长度为：L313224217三、应用实例三、应用实例输油管道铺设输油管道铺设 某东海海域有某东海海域有8 8口油田，相互之间的距离如表所示。已
38、知口油田，相互之间的距离如表所示。已知1 1号井离海岸最近，为号井离海岸最近，为5 5海里。试问从海岸经海里。试问从海岸经1 1号井铺设输油号井铺设输油管将各油田连接起来，应如何铺设才能使输油管线长度最管将各油田连接起来，应如何铺设才能使输油管线长度最短？为便于计量和检修，油管只允许在各井位处分叉。短？为便于计量和检修，油管只允许在各井位处分叉。 这是一个最短连接问题。这是一个最短连接问题。2345678114209718201529181226231132617251910471615959118661075第第1 1步步第第2 2步步第第3 3步步第第3 3步步第第4 4步步第第5 5步步
39、第第6 6步步第一步：在距离表中寻找最小值为第一步：在距离表中寻找最小值为5 5，对应的节点为，对应的节点为7 7与与8 8，将它们连接起来。，将它们连接起来。第二步：在距离表的剩余数值中寻找最小值为第二步：在距离表的剩余数值中寻找最小值为6 6，对应的节点为，对应的节点为7 7与与6 6，将它们连接起来。，将它们连接起来。第三步：在距离表的剩余数值中寻找最小值为第三步：在距离表的剩余数值中寻找最小值为7 7，对应的节点为，对应的节点为1 1与与5 5，4 4与与5 5，将它们连接起，将它们连接起来。来。第四步：在距离表的剩余数值中寻找最小值为第四步：在距离表的剩余数值中寻找最小值为8 8，对应的节点为，对应的节点为5 5与与8 8，将它们连接起来。，将它们连接起来。第五步：在距离表的剩余数值中寻找最小值为第五步：在距离表的剩余数值中寻找最小值为9 9，对应的节点为，对应的节点为2 2与与3 3，5 5与与6 6，4 4与与8 8，1 1与与4 4 ，将将2 2与与3 3连接起来。连接起来。第六步：在距离表的剩余数值中寻找最小值为第六步：在距离表的剩余数值中寻找最小值为1010，对应的节点为，对应的节点为3 3与与8 8 ，将它们连接起来。，将它们连接起来。
