交通运输系统工程 课件 第7章 运输系统网络优化

交通运输系统工程第1章系统概述1.1

系统的概念、特性及分类1.2

系统思想的形成与发展1.3

系统科学的学科体系第2章系统工程理论2.1

系统工程的概念、研究内容及特点2.2

系统工程发展概况2.3

系统工程方法论2.4

系统工程的理论基础第3章交通运输系统3.1

交通运输的概念及分类3.2

交通运输系统的组成与特点3.3

交通运输系统工程的研究内容3.4

我国交通运输的现状及发展前景第4章运输系统分析4.1系统分析的基础理论4.2系统的特性分析4.3系统结构模型化技术第5章系统模型与仿真5.1系统建模及仿真概述5.2系统动力学的建模5.3系统动力学仿真计算5.4延迟第6章运输系统预测6.1系统预测基本概念6.2定性预测方法6.3定量预测方法第7章运输系统网络优化7.1运输网络的最短路和最大流7.2网络图的组成及绘制7.3网络图时间参数7.4网络图优化分析第8章运输系统综合评价8.1运输系统综合评价概述8.2运输系统的经济评价8.3常用的系统综合评价方法第9章运输系统决策9.1运输系统决策分析概述9.2不确定型运输系统决策分析9.3风险型运输系统决策分析9.4信息的价值9.5效用理论及其应用第10章神经网络与遗传算法10.1神经网络概述10.2遗传算法第11章运输系统工程应用案例11.1地铁换乘枢纽的拥挤评价11.2道路交通检测数据的联合卡尔曼滤波11.3城市轨道交通定价模型7.1运输网络的最短路和最大流

第7章

运输系统网络优化

7.2网络图的组成及绘制7.3网络图时间参数7.4网络图优化分析交通运输与教育平台

交通运输与教育平台

交通运输与教育平台

交通运输与教育平台

交通运输与教育平台7.1.1最短路问题

【例7-1

】图7-2所示为某地八个地点的公路交通网络。现需要从地点1运输一批货物至地点8。问如何选择路径，才能使总的运费最小，各弧线的权代表运输费用。图7-2某地八个地点的公路交通网络交通运输与教育平台7.1.1最短路问题

a)初始标号交通运输与教育平台7.1.1最短路问题

b)第二次标号交通运输与教育平台7.1.1最短路问题

c)第三次标号交通运输与教育平台7.1.1最短路问题

d)第四次标号交通运输与教育平台7.1.1最短路问题

e)第五次标号交通运输与教育平台7.1.1最短路问题

f)第六次标号交通运输与教育平台7.1.1最短路问题

g)第七次标号交通运输与教育平台7.1.1最短路问题

h)第八次标号交通运输与教育平台

交通运输与教育平台

交通运输与教育平台

交通运输与教育平台

交通运输与教育平台

交通运输与教育平台

交通运输与教育平台

交通运输与教育平台

交通运输与教育平台7.1.2

最大流问题

7.1.2.3求网络最大流的标号算法【例7-2】在如图7-4所示的有向图中，1是发点，6是收点，求最大流。图7-4网络图的最大流交通运输与教育平台7.1.2

最大流问题

7.1.2.3求网络最大流的标号算法首先设初始流为零流。图解法如图7-5所示：a)第一次标号交通运输与教育平台7.1.2

最大流问题

7.1.2.3求网络最大流的标号算法b)第二次标号交通运输与教育平台7.1.2最大流问题

7.1.2.3求网络最大流的标号算法c)第三次标号交通运输与教育平台7.1.2

最大流问题

7.1.2.3求网络最大流的标号算法图7-5网络最大流的求解过程

d)第四次标号7.1运输网络的最短路和最大流

第7章

运输系统网络优化

7.2网络图的组成及绘制7.3网络图时间参数7.4网络图优化分析7.2.1网络图的组成7.2.1.1工序工序也称为活动或工作，是一项工程当中需要消耗时间或资源才能完成的事情。7.2.1.2事件事件也称为节点，表示工序开始或结束的状态。7.2.1.3线路从网络图的起始节点开始，沿着箭头方向顺序通过一系列箭线与节点，最后到达终点的通路称为一条线路。7.2.1.4紧前工序和紧后工序某工序开始之前必须先期完成的工序称为该工序的紧前工序，而某工序完成之后必须紧接着开始的工序称为该工序的紧后工序。7.2.2双代号网络图的绘制（1）虚工序的处理。为满足网络图的绘制规则，有时候需要引入虚工序。在网络图中用虚箭头表示。虚工序没有任何具体的内容，也没有时间消耗，只表示工序之间的衔接关系。（2）双代号网络图的绘制。①起始节点绘制。绘制没有紧前工作的工作箭线，使它们具有相同的开始节点，以保证网络图只有一个起始节点。②其他箭线绘制。依次绘制其他工作箭线。③终点绘制。合并那些没有紧后工序的工序箭线的箭头节点，以保证网络图只有一个终点节点(多目标网络计划除外)。④节点编号。网络图的节点编号在满足前述要求的前提下，既可采用连续的编号方法，也可采用不连续的编号方法。7.2.2.1绘图方法【例7-3】已知各工序之间的逻辑关系见表7-1，绘制其双代号网络图。7.2.2双代号网络图的绘制7.2.2.1绘图方法表7-1工序之间的逻辑关系解：(1)绘制初始节点、工序箭线A及工序箭线B。(2)按前述虚工序处理的情况①绘制虚工序箭线及工序箭线C。(3)绘制工序箭线D后，将工序箭线C和D的箭头节点合并，以保证网络图只有一个终点节点。(4)当确认给定的逻辑关系表达正确后，再进行节点编号。7.2.2双代号网络图的绘制7.2.2.1绘图方法7.2.2双代号网络图的绘制7.2.2.1绘图方法a）第一步b）第二步c）第三步图7-7双代号网络图的绘制过程【例7-4】已知各工序之间的逻辑关系见表7-2，绘制其双代号网络图。7.2.2双代号网络图的绘制7.2.2.1绘图方法表7-2工序之间的逻辑关系解：（1）绘制初始节点、工序箭线A、工序箭线B及工序箭线C。（2）按前述虚工序处理的情况③绘制虚工序箭线及工序箭线D。（3）按前述虚工序处理的情况①绘制工序箭线E。（4）按前述虚工序处理的情况②绘制虚工序箭线及工序箭线G。当确认给定的逻辑关系表达正确后，再进行节点编号。7.2.2.1绘图方法7.2.2双代号网络图的绘制图7-8

【例题7-4】双代号网络图的绘制过程7.2.2.1绘图方法7.2.2双代号网络图的绘制a）第一步b）第二步c）第三步d）第四步（1）起终节点唯一；（2）按照已定的逻辑关系绘制；（3）无回路规则；（4）箭线绘制规范。①网络图中严禁出现双向箭线和无箭头的连线。②网络图中严禁出现没有箭尾节点的箭线和没有箭头节点的箭线。③严禁在箭线上引入或引出箭线。④应尽量避免工序箭线的交叉。7.2.2.2绘图规则及注意事项7.2.2双代号网络图的绘制7.1运输网络的最短路和最大流

第7章

运输系统网络优化

7.2网络图的组成及绘制7.3网络图时间参数7.4网络图优化分析（1）确定关键线路。关键线路就是网络图中最重要、耗时最长的线路。（2）确定非关键线路上的机动时间（或称富裕时间）。网络图中，不是关键线路的线路称非关键线路。（3）时间参数的计算是网络计划调整和优化的前提。通过时间参数的计算，可据以采用各种办法不断改进网络计划，使其达到在既定条件下的最好状态。7.3.1计算时间参数的目的

7.3.2.1事件时间参数的计算7.3.2网络图时间参数的计算

7.3.2.1事件时间参数的计算7.3.2网络图时间参数的计算表示一个事件可以推迟多少时间完成不至于影响整个工期。（3）事件的时差。7.3.2.1事件时间参数的计算7.3.2网络图时间参数的计算或时差为零的事件组成的线路，其总时间等于总工期，则其为关键线路。【例题7-5】某物流企业需要修建一仓库，该工程由8项工序组成，有关资料见表7-4，单位为天，绘制网络图，计算事件时间参数，求解关键线路。7.3.2.1事件时间参数的计算7.3.2网络图时间参数的计算

修建仓库工程的工序、工序间关系及作业时间表

表7-4解：（1）网络图如图7-13所示。7.3.2.1事件时间参数的计算7.3.2网络图时间参数的计算图7-13【例题7-5】的网络图（2）事件的时间参数。（3）关键线路。按照前面的方法计算可得事件的最早开始时间为事件的最迟结束时间为事件的时差为7.3.2.1事件时间参数的计算7.3.2网络图时间参数的计算

根据关键线路的定义可知，1-3-4-6为关键线路，即B-E-G。

7.3.2.2工序时间参数的计算7.3.2网络图时间参数的计算

7.3.2.2工序时间参数的计算7.3.2网络图时间参数的计算

7.3.2.2工序时间参数的计算7.3.2网络图时间参数的计算

【例题7-6】某施工队维修一段公路，该工程由9项工序组成，有关资料见表7-5，单位为天。请绘制网络图，计算工序的时间参数，求解关键线路。7.3.2网络图时间参数的计算

维修公路工程的工序、工序间关系及作业时间表

表7-5解：（1）绘制网络图如图7-14所示

。7.3.2网络图时间参数的计算图7-14【例题7-6】的网络图（2）计算工序的时间参数。

（3）关键线路。关键线路为：A-B-D-G。7.3.2网络图时间参数的计算7.1运输网络的最短路和最大流

第7章

运输系统网络优化

7.2网络图的组成及绘制7.3网络图时间参数7.4网络图优化分析7.4.1工程进度的优化在资源条件允许的条件下，应尽量压缩关键工作的持续时间，缩短工程进度，以提高经济效益。这里通常可供选择的技术、组织措施是：（1）检查工作流程，去掉多余环节；（2）检查各工序工期，改变关键线路上的工作组织；（3）把串联工序改为平行工序或交叉工序；（4）调整或增加资源（人力、物力、财力）到关键线路上的关键工序上去；（5）采取技术措施(如采用机械化、改进工艺、采用先进技术)和组织措施（如合理组织流程，实现流程优化）；（6）利用时差，从非关键工序上抽调部分人力、物力集中于关键工序，缩短关键工序的时间。【例7-7】新建铁路线某个区间内的线路有关资料见表7-7，每天可以安排的人员数只有10人，要求工程15天完成，应如何安排工程进度才能在现有人力资源下按期完成任务？

新建铁路线工程资料表

表7-77.4.1工程进度的优化

解：（1）绘制网络图并求关键线路如图7-15所示。图7-15例题【7-7】的网络图7.4.1工程进度的优化关键线路为1-2-4-5，即B-D-E，关键线路的路长为19天，不能满足工期的要求。（2）分析每天对人员的需求。

可知在前4天，由于A、B、C三项工作同时进行，需要人员11人，超过了所能提供的人力资源。（3）计划调整。基本思路是从非关键线路抽调人力。分析可做如下调整：①从非关键工作A上抽调2名，1名支持工作B，1名支持工作D，这样A的时间将延长至8天，工作B和D都缩短为4天。②从非关键工作F上抽调人员2名，支援工作E，这样F的工作将延长至3天，而工作E的时间将缩短为7天。按照这样的调整，重新绘制网络图，工期和人员都满足要求。7.4.1工程进度的优化工程的成本是由直接成本、间接成本、赶工成本等构成的。直接成本由材料费、人工费、机械费等构成。由于所采用的施工方案不同，它的成本差异很大。间接成本包括施工组织和经营管理的全部费用。赶工成本是在考虑工程总成本时，考虑可能因拖延工期而罚款的损失或提前竣工而获得的奖励，甚至也应考虑因提前投产而获得的收益。对于企业来说，不论缩短工期或延长工期，都要衡量利弊。要缩短工期，就要采取措施，会引起直接成本的增加。但由于工期缩短，会带来管理费用、工资费用的减少，以及提早投产带来的经济效益。7.4.2成本优化所谓网络图的成本优化，就是研究如何以最低的成本来缩短整个工期的问题，即缩短工期，又使得总费用增加最少。最低成本日程：使得工程费用最低的完工时间。寻找最低成本日程，一方面要尽量缩短关键工作的工作时间，另一方面要想办法缩短单位赶工费用最低的关键工作的工作时间。一项工程的总费用＝直接费用＋间接费用＋赶工费用成本斜率＝（赶工成本－正常成本）/（正常时间－赶工时间）7.4.2成本优化

【例7-8】修建某段高速公路，工程资料见表7-8，间接成本为500元/d，试求该工程的最低成本日程。

修建高速公路工程资料

表7-87.4.2成本优化

解：（1）绘制网络图并求关键线路如图7-16所示。图7-16【例题7-8】的网络图（2）成本优化。总成本＝直接成本＋间接成本＋赶工成本＝（24＋20＋22＋18＋14＋16＋24）＋50×5＋0＝388（百元）7.4.2成本优化由网络图可知关键线路为1-2-3-4-5-7，即A-B-E-G，工期为50d。工序A、B、C、D、E、F、G的成本斜率分别为：2，3，3，6，4，5，2。在关键工序中，A、G的成本斜率最小，A可赶工3天。分析可知，G只能赶工1天，此时增加一条关键线路，1-2-3-6-7，即A-B-D-F。赶工后工期变为46天。此时，总成本＝（24＋20＋22＋18＋14＋16＋24）＋46×5＋2×3＋2×1＝376（百元）再要降低成本，必须同时考虑两条关键线路，并且只有工序C为非关键工作。分析可知：B可赶工2d，且关键线路不变，工期变为44d。总成本＝（24＋20＋22＋18＋14＋16＋24）＋44×5＋2×3＋2×1＋3×2＝372（百元）工序Ｄ成本斜率大于每天的间接成本，赶工将使成本增加，不可行。7.4.2成本优化

此时是否还存在赶工方案呢？要赶工必须同时考虑两条关键线路，分析有三种方案见表7-9。赶工方案

表7-9由以上分析可知，平均每天的赶工成本均大于间接费用，故以上三个方案都不可行。7.4.2成本优化

所以，最低成本日程为44d，工程成本为372百元。调整后的网络图如图7-17所示。图7-17优化后的网络图7.4.2成本优化在资源计划安排时有以下两种情况。一种情况是网络计划需要的资源受到限制，如果不增加资源数量，有时会使工期延长，