网络优化建模

1、 网络计划图的绘制网络计划图的绘制 时间参数计算与关键路线确定时间参数计算与关键路线确定 网络图的调整及优化网络图的调整及优化 网络计划（工程计划问题）网络计划（工程计划问题）1.问题的一般题法：问题的一般题法： 设有一项工程，可分为若干道工序，已知各工序间设有一项工程，可分为若干道工序，已知各工序间的先后关系以及各工序所需时间的先后关系以及各工序所需时间t。问：（1）工程完工期T？（2）工程的关键工序有哪些？（3）若工序时间T具有随机性，则期望完工期TE=? 完工期为某天的可能性多大？（4）费用优化和资源平衡。 例例 甲、乙两工程师从早上六时起床到上甲、乙两工程师从早上六时起床到上班前有一系

2、列活动要做。对于同样的活班前有一系列活动要做。对于同样的活动过程，有人忙乱不堪，甚至迟到，有动过程，有人忙乱不堪，甚至迟到，有人则又快又好，关键在于一个科学的活人则又快又好，关键在于一个科学的活动实施计划。动实施计划。甲出门上班穿衣刷牙洗脸做稀饭热馒头吃早饭收拾房间整理出门上班穿衣洗脸刷牙收拾房间整理吃早饭做稀饭热馒头乙 例例2 2 大型工程实施（三峡工程、南水北调工程、大型工程实施（三峡工程、南水北调工程、人造卫星工程、宇航工程等）有如下活动：人造卫星工程、宇航工程等）有如下活动：1 1 产品设计、仿真、试制、中试产品设计、仿真、试制、中试2 2 原材料设备定货、采购、运输、入库原材料设备定

3、货、采购、运输、入库3 3 厂房、设备施工建筑、安装厂房、设备施工建筑、安装4 4 产品计划、生产、销售、安装、调试、维产品计划、生产、销售、安装、调试、维护护参与单位涉及国家各部门、各行业、事业单位，参与单位涉及国家各部门、各行业、事业单位，为高速度、低成本、高质量，并在规定期限内为高速度、低成本、高质量，并在规定期限内完成该工程项目，其关键在：完成该工程项目，其关键在：1 1 抓好科学技术抓好科学技术2 2 抓好项目管理，组织协调好各单位、各任抓好项目管理，组织协调好各单位、各任务、各工序的完成。务、各工序的完成。 例例3 3 三军联合作战演习三军联合作战演习u空军夺取制空权，对敌实施地面

4、攻击，运送空降兵空军夺取制空权，对敌实施地面攻击，运送空降兵u海军舰艇护卫，运送陆军、海军陆战队登陆夺取滩海军舰艇护卫，运送陆军、海军陆战队登陆夺取滩头阵地头阵地u登陆完成后的巩固阵地与纵深发展登陆完成后的巩固阵地与纵深发展u电子对抗部队实施情报收集分析与电子对抗电子对抗部队实施情报收集分析与电子对抗 参与兵种：海军航空兵、海军陆战队、水面舰艇参与兵种：海军航空兵、海军陆战队、水面舰艇部队、空军歼击机、攻击机、轰炸机、电子对抗部队、空军歼击机、攻击机、轰炸机、电子对抗机各团、大队，坦克、炮兵、步兵、防化兵、通机各团、大队，坦克、炮兵、步兵、防化兵、通讯兵、侦察兵、导弹部队等。讯兵、侦察兵、导弹

5、部队等。 需迅速订好科学的作战演习计划，以便对作战演需迅速订好科学的作战演习计划，以便对作战演习过程演习过程进行有效的管理与控制。习过程演习过程进行有效的管理与控制。2.解法解法关键路径法（CPM方法）计划评审法（PERT方法）l相同点：l不同点：PERT法：注重于对工程安排的评价与审查。CPM方法：注重于时间、成本和资源的优化；均是用网络表示工程项目，以确定关键路线。 计划评审方法计划评审方法（Program Evaluation and Review Technique, 简写为简写为PERT）和）和关键路线法关键路线法（Critial PathMethod, 简写为简写为CPM）是网络分

6、析的）是网络分析的重要组成部分，它广泛用系统分析和项目管理重要组成部分，它广泛用系统分析和项目管理.计划计划评审与关键路线方法是在评审与关键路线方法是在20世纪世纪50年代提出并发展年代提出并发展起来的，起来的，1956年，美国杜邦公司为了协调企业不同年，美国杜邦公司为了协调企业不同业务部门的系统规划，提出了关键路线法业务部门的系统规划，提出了关键路线法.1958年，年，美国海军武装部在研制美国海军武装部在研制“北极星北极星”导弹计划时，由于导弹计划时，由于导弹的研制系统过于庞大、复杂，为找到一种有效的导弹的研制系统过于庞大、复杂，为找到一种有效的管理方法，设计了计划评审方法管理方法，设计了计

7、划评审方法.由于由于PERT与与CPM即有着相同的目标应用，又有很多相同的术语，这两即有着相同的目标应用，又有很多相同的术语，这两种方法已合并为一种方法，在国外称为种方法已合并为一种方法，在国外称为PERT/CPM，在国内称为统筹方法在国内称为统筹方法(Scheduling Method).2.1 计划网络图的绘计划网络图的绘制制1. 计划网络图的概念计划网络图的概念 定义定义1 称任何消耗时间或资源的行动为作称任何消耗时间或资源的行动为作业业.称作业的开始或结束为事件，事件本身不消耗称作业的开始或结束为事件，事件本身不消耗资源资源. 在计划网络图中通常用圆圈表示事件，用箭在计划网络图中通常用

8、圆圈表示事件，用箭线表示事件，如图线表示事件，如图7-12所示，所示，1, 2, 3表示事件，表示事件，A, B表示作业表示作业.由这种方法画出的网络图称为计划由这种方法画出的网络图称为计划网络图网络图.定义定义2 在计划网络图中，称从是初始事在计划网络图中，称从是初始事件到最终事件的由各项作业连贯组成的一条路为件到最终事件的由各项作业连贯组成的一条路为路线。具有累计作业时间最长的路线称为关键路路线。具有累计作业时间最长的路线称为关键路线。线。由此看来，一般网络图是求相应的图中的关由此看来，一般网络图是求相应的图中的关键路线。键路线。2. 建立计划网络图应注意的问题建立计划网络图应注意的问题(

9、1) 任何作业在网络中用唯一的箭线表示，任何作业任何作业在网络中用唯一的箭线表示，任何作业其终点事件的编号必须大于其起点事件其终点事件的编号必须大于其起点事件.1221 (2) 两个事件之间只能画一条箭线，表示一两个事件之间只能画一条箭线，表示一项作业项作业.对于具有相同开始和结束事件的两项以上对于具有相同开始和结束事件的两项以上作业，要引进虚事件和虚作业作业，要引进虚事件和虚作业. (4) 计划网络图不允许出现回路计划网络图不允许出现回路12ab46a12b46回路回路123ac40b6123a/222b6a/2 (3) 任何计划网络图应有唯一的最初事件和任何计划网络图应有唯一的最初事件和唯

10、一的最终事件唯一的最终事件. (5) 计划网络图的画法一般是从左到右，从计划网络图的画法一般是从左到右，从上到下，尽量作到清晰美观，避免箭头交上到下，尽量作到清晰美观，避免箭头交叉叉. 例1 某公司研制新产品的部分工序明细表如下，试画出统筹图。（反向搜索法）（反向搜索法）工序代号 工序名称（或内容）工序长度紧前工序a产品设计与工艺设计60-b外购配套零件15ac外购生产原料13ad自制主件38ce主配件可靠性试验8b, d12453abced601513388分支时候尽量向一起努力分支时候尽量向一起努力 例5 某工程项目作业明细表如下 ，（1）绘制计划网络图 ；（2）求关键路线与路长；（3）求

11、关键工序序号序号工序代号工序代号所需时间所需时间紧前工序紧前工序1a60-2b15a3c13a4d38c5e8b、d6f10d7g16d8h5e、f、g 解：若已知紧后工序之作业明细表，故用正象（顺向）搜索法，已知紧前工序之作业明细表，故可采用反向搜索法。 （f g h）1253476abedghfc1254376abedghfc860151338810165例3 某工厂进行技术改造的工作表如下：工序代号工序名称紧前工序工作时间（周）A拆迁/2B工程设计/3C土建工程设计B2.5D采购设备B6E厂房土建C，A20F设备安装D，E4G设备调试F21A(2)3B(3)2C（2.5）4D（6）E（2

12、0）5F（4）6G（2）2.2 建立相应的规划建立相应的规划问题方法问题方法1 例例 某项目工程由某项目工程由11项作业组成（分别用代号项作业组成（分别用代号A, B, , J, K表示），其计划完成时间及作业间相互表示），其计划完成时间及作业间相互关系如表关系如表7-8所示，求完成该项目的最短时间所示，求完成该项目的最短时间.2. 写出相应的规划问题写出相应的规划问题 设是事件的开始时间，设是事件的开始时间， 为最初事件，为为最初事件，为最终事件最终事件.希望总的工期最短，即极小化希望总的工期最短，即极小化 .设设是作业是作业 的计划时间，因此，对于事件的计划时间，因此，对于事件 与事件与事

13、件 有不等式：有不等式： ixi11nxxijt( , )i jijjiijxxt由此得到相应的数学规划问由此得到相应的数学规划问题题 Min= x8 - x1 2) x2 - x1 = 5 3) x3 - x1 = 10 4) x4 - x1 = 11 5) x5 - x2 = 4 6) x4 - x3 = 4 7) x5 - x3 = 0 8) x6 - x4 = 15 9) x6 - x5 = 21 10) x7 - x5 = 25 11) x8 - x5 = 35 12) x7 - x6 = 0 13) x8 - x6 = 20 14) x8 - x7 = 15Objective va

14、lue: 51.00000 Infeasibilities: 0.000000 Total solver iterations: 1 Variable Value Reduced Cost X8 51.00000 0.000000 X1 0.000000 0.000000 X2 5.000000 0.000000 X3 10.00000 0.000000 X4 14.00000 0.000000 X5 10.00000 0.000000 X6 31.00000 0.000000 X7 35.00000 0.000000 计算结果给出了各个项目的开工时间，如计算结果给出了各个项目的开工时间，如

15、, 则则作业作业A、B、C的开工时间均是第的开工时间均是第0天天; 作业作业E的开的开工时间是第工时间是第5天天; 则作业则作业D的开工时间是第的开工时间是第10天天; 等等等等.每个作业只要按规定的时间开工，整个项每个作业只要按规定的时间开工，整个项目的最短工期为目的最短工期为51天天.10 x 25,x 310,x 尽管上述尽管上述LINgo程序给出相应的开工时间和整个程序给出相应的开工时间和整个项目的最短工期，但统筹方法中许多有用的信息并没项目的最短工期，但统筹方法中许多有用的信息并没有得到，如项目的关键路径、每个作业的最早开工时有得到，如项目的关键路径、每个作业的最早开工时间、最迟开工

16、时间等间、最迟开工时间等.因此，我们希望将程序编写的因此，我们希望将程序编写的稍微复杂一些，为我们提供更多的信息稍微复杂一些，为我们提供更多的信息.编写相应的编写相应的Lingo程序，程序名：程序，程序名： exam0721.lg4MODEL: 1sets: 2 events/1.8/: x; 3 operate(events, events)/ 4 1,2 1,3 1,4 3,4 2,5 3,5 4,6 5,6 5,8 5,7 6,7 7,8 6,8 5 /: s, t; 6endsets 7data: 8 t = 5 10 11 4 4 0 15 21 35 25 0 15 20; 9en

17、ddata 10min=sum(events : x); 11for(operate(i,j): s(i,j)=x(j)-x(i)-t(i,j); END计算得到（只列出非零解）计算得到（只列出非零解）: Variable Value Reduced Cost X( 2) 5.000000 0.000000 X( 3) 10.00000 0.000000 X( 4) 14.00000 0.000000 X( 5) 10.00000 0.000000 X( 6) 31.00000 0.000000 X( 7) 35.00000 0.000000 X( 8) 51.00000 0.000000 S

18、( 1, 4) 3.000000 0.000000 S( 2, 5) 1.000000 0.000000 S( 4, 6) 2.000000 0.000000 S( 5, 8) 6.000000 0.000000 S( 6, 7) 4.000000 0.000000 S( 7, 8) 1.000000 0.000000 由此，可以得到所有作业的最早开工时间和最迟由此，可以得到所有作业的最早开工时间和最迟开工时间，如表开工时间，如表7-9所示，方括号中第所示，方括号中第1个数字是最早个数字是最早开工时间，第开工时间，第2个数字是最迟开工时间个数字是最迟开工时间. 从上述表可以看出，当最早开工时间

19、与最迟开从上述表可以看出，当最早开工时间与最迟开工时间相同时，对应的作业在关键路线上，因此可工时间相同时，对应的作业在关键路线上，因此可以画出计划网络图中的关键路线，如图以画出计划网络图中的关键路线，如图7-14粗线所粗线所示示.关键路线为关键路线为 13568.2.3 建立相应的规划建立相应的规划问题方法问题方法2将关键路线看成最长路将关键路线看成最长路 如果将关键路线看成最长路，则可以按照求最短如果将关键路线看成最长路，则可以按照求最短路的方法（将求极小改为求极大）求出关键路线路的方法（将求极小改为求极大）求出关键路线 .设为设为 变量，当作业变量，当作业 位于关键路线上取位于关键路线上取1;否否则取则取0. 数学规划问题写成数学规划问题写成:ijx0 1( , )i j例例 用最长路的方法求用最长路的方法求jie. 解：解： 按数学规划按数学规划(7.40)-(7.42)写出相应的写出相应的INGO程序，程序名：程序，程序名：exam0722.lg4.MODEL: 1sets: 2 events/1.8/: d; 3 operate(events, events)/ 4 1,2 1,3 1,4 3,4 2,