IE10_OR19CH6(3)andCH7网络计划1

第1页西南科技大学制造科学与工程学院工业工程与设计系石宇强运筹学第19讲目录§6.5最小费用流问题(举例）图与网络分析（小结）CH7网络计划§7.1网络图的表示法§7.2网络时间与关键路线§7.3网络进度的优化第2页西南科技大学制造科学与工程学院工业工程系石宇强运筹学例２P267例16求v为10的最小费用流svtv1v2v3v)4,10()1,8()1,7()3,10()2,5()2,4()6,2(svtv1v2v3v)4,10()1,8()1,7()3,10()2,5()2,4()6,2(svtv1v2v3v4113226)()()0(fLb(容量,单位费用)(单位费用)svtv1v2v3v)0,10()5,8()5,7()0,10()5,5()0,4()0,2(此时，网络流量为=5≺10，此流的费用为：)1()(fc)()1(fW20152515)()1(fDsvtv1v2v3v)4,10()1,8()1,7()3,10()2,5()2,4()6,2()(a(容量,单位费用)(容量,流量)svtv1v2v3v411322611)()()1(fLd)0()1(svtv1v2v3v)0,10()5,8()5,7()0,10()5,5()0,4()0,2()1()(fc(容量,流量)(单位费用)svtv1v2v3v)2,10()5,8()7,7()0,10()5,5()0,4()0,2(此时，网络流量为=7≺10，此流的费用为：)()1(fW3017251542)()2(fDsvtv1v2v3v)4,10()1,8()1,7()3,10()2,5()2,4()6,2()(a)2()(fe(容量,单位费用)(容量,流量)svtv1v2v3v)2,10()5,8()7,7()0,10()5,5()0,4()0,2()2()(fesvtv2v3v41322611)()()2(fLf)0()1(41v(容量,流量)(单位费用)此时，网络流量为=10，最小费用为：)()3(fW48231733251842)()3(fDsvtv1v2v3v)4,10()1,8()1,7()3,10()2,5()2,4()6,2()(a)3()(fgsvtv1v2v3v)2,10()8,8()7,7()3,10()5,5()3,4()0,2(第9页西南科技大学制造科学与工程学院工业工程与设计系石宇强运筹学图与网络分析（小结）最小生成树(Minimum-Spanningtreeproblems)最短路径问题(Shortestpathproblems)最大流问题(Maximumflowproblems)最小费用最大流(Minimum-costnetworkflowproblems)(MNCFPS)第10页西南科技大学制造科学与工程学院工业工程与设计系石宇强运筹学图与网络分析（小结）(1)最小生成树(Minimum-Spanningtreeproblems)避圈法（Kruskal,1956）、破圈法(管梅谷，1975)。方法一(破圈法)任取一个圈，从圈中去掉一条权最大的边。在余下的图中，重复这个步骤，一直到一个不含圈的图为止，这时的图便是最小树。第11页西南科技大学制造科学与工程学院工业工程与设计系石宇强运筹学方法二(避圈法)开始选一条最小权的边，以后每一步中，总从未被选取的边中选一条权最小的边，并使之与已选取的边不构成圈。第12页西南科技大学制造科学与工程学院工业工程与设计系石宇强运筹学避圈法是一种选边的过程，其步骤如下：1.从网络D中任选一点vi，找出与vi相关联的权最小的边[vi，vj]，得第二个顶点vj；2.把顶点集V分为互补的两部分V1,1，其中V集；不与已选边相关联的点，，与已选边相关联的点集，11VV其中权最小的；挑选其中考虑所有这样的边,,],,[3.11VvVvvv。即，直至全部顶点属于重复)(34.11VV第13页西南科技大学制造科学与工程学院工业工程与设计系石宇强运筹学图与网络分析（小结）(2)最短路径问题(Shortestpathproblems)一、Dijkstra算法（从某一点到其它点的最短路问题）二、逐次逼近算法（有负权边的从某一点到其它点的最短路问题）三、Floyd算法（任意两点间的最短距离）第14页西南科技大学制造科学与工程学院工业工程与设计系石宇强运筹学三、任意两点间的最短距离Floyd算法即矩阵方法●首先建立网络中任意二顶点Vi和Vj间的“条件最短路长”矩阵，即指从Vi到Vj仅考虑可经过某些中间点.由于在达到最后一步之前未考虑经过所有各点的可能性，因而这时求出的最短路长不一定是真正最短路长。●然后设计一种迭代规则，逐步考虑当各个点进入路径时对最短路长的影响，修改条件最短路长矩阵，使其中的元素始终为这时的最短路长。当网络中所有的点均考虑过后，即可得到各点对间真正的最短路长矩阵。第15页西南科技大学制造科学与工程学院工业工程与设计系石宇强运筹学第一步迭代考虑把顶点V1作为中间点，即将路Vi—V1—Vj与路Vi—Vj的路长进行比较，若前者小于后者，则令新条件最短路长矩阵D1的元素dij（1）=wi1+w1j，否则，取dij（1）=dij（0）=wij。第二步迭代在第一步迭代结果的基础上进行，即考虑顶点V2进入线路时最短路长的变化，并以此修改矩阵D1中的元素。如此继续，当考虑完所有顶点时，最后得到的最短路长矩阵Dp，其中的元素dij（p）即为Vi到Vj的真正最短路长。设网络中有p个顶点。开始时的条件最短路长矩阵D0=（dij（0））p*p中的元素dij（0）为Vi到Vj直接距离。第16页西南科技大学制造科学与工程学院工业工程与设计系石宇强运筹学图与网络分析（小结）(3)最大流问题(Maximumflowproblems)第17页西南科技大学制造科学与工程学院工业工程与设计系石宇强运筹学图与网络分析（小结）(4)最小费用最大流(Minimum-costnetworkflowproblems)(MNCFPS)特例:运输(transportation)、指派(Assignment)、转运(transhipment)、最大流(maximumflowproblems)等问题。第18页西南科技大学制造科学与工程学院工业工程与设计系石宇强运筹学图与网络分析（小结）例：工厂B1、B2、B3需要从A1、A2、A3供应原料，工厂B2不能缺货，工厂B1和B3缺货要造成损失，单位运价、材料供应量和需求量如下表所示，试确定使总费用最低的原料分配方案。供应地工厂A1A2A3需要量缺货损失B132－81B223414不允许缺货B3－42102可供量1097第19页西南科技大学制造科学与工程学院工业工程与设计系石宇强运筹学CH7网络计划网络分析方法是五十年代中期发展起来的一种科学计划管理技术，是运筹学的组成部分，也是系统工程中一种重要方法。网络分析方法在国外称为计划评审技术（PERT）和关键路径法（CPM）国内称为统筹方法。第20页西南科技大学制造科学与工程学院工业工程与设计系石宇强运筹学PERT与CPM的特点：CPM属于肯定型，工作时间采用“一个估计值”（最可能时间），它适用于工程建设项目，它往往兼顾时间和费用两大因素，力求用最低费用去确定工期，在时间和费用两个方面作出决择。PERT属于非肯定型，工作时间采用“三个估计值”（最乐观时间、最可能时间、最悲观时间）适用于科研项目和一次性计划，它着重考虑时间因素，主要用于控制进度。第21页西南科技大学制造科学与工程学院工业工程与设计系石宇强运筹学一.传统的工程进度计划图表1.甘特图（横道图）ID12345拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟99-7-599-7-1299-7-2299-7-1399-7-3099-7-2399-8-299-7-31345678910111213141516171819202122232425262799-JulTaskName§7.1网络图的表示法一.传统的工程进度计划图表1.甘特图（横道图）ID12345拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟拟99-7-599-7-1299-7-2299-7-1399-7-3099-7-2399-8-299-7-31345678910111213141516171819202122232425262799-JulTaskNameCPM关键线路法CriticalPathMethodPERT计划评审技术ProgramEvaluationandReviewTechniqueGERT图示评审技术GraphicEvaluationandReviewTechniqueVERT风险评审技术VentureEvaluationandReviewTechnique华罗庚：统筹法•网络计划图表是本世纪五十年代末期发展起来的一种工程项目进度计划的新形式和新技术。二、网络计划图表三、网络图表示法工作：至少消耗时间或多数情况下消耗资源的一种活动事件：工作的开始或结束。计划项目：工作的集合A和事件的集合E构成的P=[A，E]工作要消耗时间，可看成沿某一方向前进，具有方向性每一工作需赋时间和各种资源的权，有向网络。工作在网络图中有两种表示法：单代号法—以节点表示工作双代号法—以弧表示工作第24页西南科技大学制造科学与工程学院工业工程系石宇强运筹学双代号网络图的绘制（一）绘图的基本规则1．必须正确表达已定的逻辑关系。第25页西南科技大学制造科学与工程学院工业工程系石宇强运筹学ABABCABCABCACB序号工作之间的逻辑关系网络图中的表示方法说明1A工作完成后进行B工作A工作制约着B工作的开始，B工作依赖着A工作2A、B、C三项工作同时开始A、B、C三项工作称为平行工作3A、B、C三项工作同时结束A、B、C三项工作称为平行工作4有A、B、C三项工作。只有A完成后，B、C才能开始A工作制约着B、C工作的开始，B、C为平行工作5有A、B、C三项工作。C工作只有在A、B完成后才能开始C工作依赖着A、B工作，A、B为平行工作双代号网络图中各工作逻辑关系的表示方法1第26页西南科技大学制造科学与工程学院工业工程系石宇强运筹学BACDACBDiDA1B1A2A3B2B3ADBCE6有A、B、C、D四项工作。只有当A、B完成后，C、D才能开始通过中间节点i正确地表达了A、B、C、D工作之间的关系7有A、B、C、D四项工作。A完成后C才能开始，A、B完成后D才能开始D与A之间引人了逻辑连接（虚工作），从而正确地表达了它们之间的制约关系8有A、B、C、D、E五项工作。A、B完成后C才能开始，B、D完成后E才能开始虚工作i-j反映出C工作受到B工作的制约；虚工作i-k反映出E工作受到B工作的制约9有A、B、C、D、E五项工作。A、B、C完成后D才能开始，B、C完成后E才能开始虚工作反映出D工作受到B、C工作的制约10A、B两项工作分三个施工段，平行施工每个工种工程建立专业工作队，在每个施工段上进行流水作业，虚工作表达了工种间的工作面关系ACBEijk第27页西南科技大学制造科学与工程学院工业工程系石宇强运筹学2．网络图中，只能有一个起点节点；在不分期完成任务的网络计划（单目标网络计划）中，应只有一个终点节点；而其他节点均应是中间节点。3．网络图中严禁出现循环回路123AC5B2D4E5G3F56451图有循环回路错误的网络图第28页西南科技大学制造科学与工程学院工业工程系石宇强运筹学4.网络图中不允许出现相同编号的工作相同编号工作示意图（b）正确砌隔墙345埋电线管（a）错误34埋电线管砌隔墙（c）正确砌隔墙345埋电线管第29页西南科技大学制造科学与工程学院工业工程系石宇强运筹学5.不允许出现无开始节点或无完成节点的工作6.在节点之间，严