《运筹学研究生辅导课件》第三章图与网络理论2011.ppt

二、工序时间不确定的工程计划网络问题  （计划评审技术PERT） vs vt v4 v2 v3 v1 (15,11) (9,9) (3,0) (5,4) (6,5) (7,7) (10,9) (11,11) (4,4) (0,+∞) (vs,4) （3）检查与vs ，v1相邻的顶点v2，v3 ，v4 ，都不满足标号条件，所以标号过程结束，这时vt没有得到标号，由此可知不存在从vs到vt的增广链，所以图中的可行流就是最大流，其流量W=fs1+ fs2=11+9=20。 vs vt v4 v2 v3 v1 (15,11) (9,9) (3,0) (5,4) (6,5) (7,7) (10,9) (11,11) (4,4) (0,+∞) (vs,4) 用标号法在求得最大流的同时，可得到一个最小割集，从图可知，标号点的集合为S={vs ,v1}，此时割集为 ， 例11　用标号法求图7.26中从vs到vt的最大流。 v3 vs vt v5 v2 v4 v1 (13,7) (9,9) (4,4) (5,2) (5,5) (5,5) (10,5) (9,7) (6,6) (5,0) (4,0) (4,4) 图7.26 v3 vs vt v5 v2 v4 v1 (13,7) (9,9) (4,4) (5,2) (5,5) (5,5) (10,5) (9,7) (6,6) (5,0) (4,0) (4,4) 图7.26 解 (0,+∞) (vs,6) (v1,4) (v2,4) (v3,4) (v5,4) v3 vs vt v5 v2 v4 v1 (13,11) (9,9) (4,0) (5,2) (5,5) (5,5) (10,9) (9,7) (6,6) (5,4) (4,4) (4,4) 图7.26 (0,+∞) (vs,6) 最大流为W=fs1+ fs2=11+9=20。 最小割集为 网络计划技术 网络计划技术也称统筹法，它是综合运用计划评审方法和关键路线法的一种比较先进的计划管理方法。计划评审方法和关键路线法都是五十年代发展起来的计划管理方法。计划评审方法主要应用于研究与开发项目，对它进行核算、评价，然后选定最优计划方案。关键路线法主要应用于以往在类似工程中已取得一定经验的复杂工程项目，对它的进度、工期、资源及成本进行优化。 网络计划技术的基本原理是：从需要管理的工程项目的总进度着眼，对工程项目中各项工作所需要的时间因素，按照工作的先后顺序和相互关系作出网络图，以反映工程的全貌。然后进行时间参数计算，找出计划中的关键工作和关键路线，对工程的各项工作所需的人、财、物，通过改善网络计划作出合理安排，得到最优方案。在计划的实施过程中，进行有效的监督与控制，以保证工程项目按计划顺利完成。 网络计划技术的应用范围很广，特别适用于生产技术复杂，工作项目繁多，且联系紧密的一些跨部门的工作计划。例如新产品试制，大型工程项目，设备维修等计划。 第一节 网络图 网络图又称箭线圈，由带箭头的线和结点组成，它是计划项目的各个组成部分内在逻辑关系的综合反映，是进行计划和计算的基础。 下面我们通过一个实例说明网络图的一些概念和绘制方法。设要研制一种机器设备，其各个工序与所需时间及它们之间的相互关系如表8.1所示。 60 45 10 20 20 18 30 15 25 35 - a a a a c d d,e g b,f,h,k a b c d e f g h k i 产品设计 外购配套件 下料锻件 工装制造1 木模、铸件 机械加工1 工装制造2 机械加工2 机械加工3 装配调试 所需时间（天） 紧前工序 工序代号 工序 表8.1 在网络图中，箭线代表工序。工序是指为了完成工程项目，在工艺技术和组织管理上相对独立的工作或活动。一项工程由若干个工序组成。工序需要一定的人力、物力等资源和时间。结点表示一个事项。事项是一个或若干个工序的开始或结束，是相邻工序在时间上的分界点。结点用圆圈和里面的数字表示，数字表示结点的编号。 一、 绘制网络图的规则 例如，根据表8.1可以绘制出机器设备研制过程的网络图如图8.1所示。网络图是由箭线，结点和线路三部分组成。把表示各个工序的箭线按照工序先后顺序及逻辑关系，由左至右排列，画成网络图，再给结点统一编号，结点1表示整个计划的开始，网络图中最大的数码结点表示计划结束。结点编号可不连续，但对于一个工序来讲，其开始所对应结点的编号要小于结束所对应结点的编号。箭线的方向表示工序前进方向，从箭尾到箭头表示一个工序的开始到结束的过程。 e 40 d 20 c