网络优化建模PPT课件

1、1.问题的一般题法： 设有一项工程，可分为若干道工序，已知各工序间的先后关系以及各工序所需时间t。问：（1）工程完工期T？（2）工程的关键工序有哪些？（3）若工序时间T具有随机性，则期望完工期TE=? 完工期为某天的可能性多大？（4）费用优化和资源平衡。第1页/共37页 例 甲、乙两工程师从早上六时起床到上班前有一系列活动要做。对于同样的活动过程，有人忙乱不堪，甚至迟到，有人则又快又好，关键在于一个科学的活动实施计划。甲出门上班穿衣刷牙洗脸做稀饭热馒头吃早饭收拾房间整理出门上班穿衣洗脸刷牙收拾房间整理吃早饭做稀饭热馒头乙第2页/共37页 例例2 2 大型工程实施（三峡工程、南水北调工程、人造卫

2、星工程、宇航工程等）有如下大型工程实施（三峡工程、南水北调工程、人造卫星工程、宇航工程等）有如下活动：活动：1 1 产品设计、仿真、试制、中试产品设计、仿真、试制、中试2 2 原材料设备定货、采购、运输、入库原材料设备定货、采购、运输、入库3 3 厂房、设备施工建筑、安装厂房、设备施工建筑、安装4 4 产品计划、生产、销售、安装、调试、产品计划、生产、销售、安装、调试、维护维护参与单位涉及国家各部门、各行业、事业单参与单位涉及国家各部门、各行业、事业单位，为高速度、低成本、高质量，并在规定位，为高速度、低成本、高质量，并在规定期限内完成该工程项目，其关键在：期限内完成该工程项目，其关键在：1

3、1 抓好科学技术抓好科学技术2 2 抓好项目管理，组织协调好各单位、各抓好项目管理，组织协调好各单位、各任务、各工序的完成。任务、各工序的完成。第3页/共37页 例例3 3 三军联合作战演习三军联合作战演习u空军夺取制空权，对敌实施地面攻击，运送空降兵空军夺取制空权，对敌实施地面攻击，运送空降兵u海军舰艇护卫，运送陆军、海军陆战队登陆夺取滩头阵地海军舰艇护卫，运送陆军、海军陆战队登陆夺取滩头阵地u登陆完成后的巩固阵地与纵深发展登陆完成后的巩固阵地与纵深发展u电子对抗部队实施情报收集分析与电子对抗电子对抗部队实施情报收集分析与电子对抗 参与兵种：海军航空兵、海军陆战队、水面舰艇部队、空军歼击机、

4、攻击机、轰炸机、电参与兵种：海军航空兵、海军陆战队、水面舰艇部队、空军歼击机、攻击机、轰炸机、电子对抗机各团、大队，坦克、炮兵、步兵、防化兵、通讯兵、侦察兵、导弹部队等。子对抗机各团、大队，坦克、炮兵、步兵、防化兵、通讯兵、侦察兵、导弹部队等。 需迅速订好科学的作战演习计划，以便对作战演习过程演习过程进行有效的管理与控制。需迅速订好科学的作战演习计划，以便对作战演习过程演习过程进行有效的管理与控制。第4页/共37页2.解法关键路径法（CPM方法）计划评审法（PERT方法）l相同点：l不同点：PERT法：注重于对工程安排的评价与审查。CPM方法：注重于时间、成本和资源的优化；均是用网络表示工程项

5、目，以确定关键路线。第5页/共37页 计划评审方法（Program Evaluation and Review Technique, 简写为PERT）和关键路线法（Critial PathMethod, 简写为CPM）是网络分析的重要组成部分，它广泛用系统分析和项目管理.计划评审与关键路线方法是在20世纪50年代提出并发展起来的，1956年，美国杜邦公司为了协调企业不同业务部门的系统规划，提出了关键路线法.1958年，美国海军武装部在研制“北极星”导弹计划时，由于导弹的研制系统过于庞大、复杂，为找到一种有效的管理方法，设计了计划评审方法.由于PERT与CPM即有着相同的目标应用，又有很多相同的

6、术语，这两种方法已合并为一种方法，在国外称为PERT/CPM，在国内称为统筹方法(Scheduling Method).第6页/共37页2.1 计划网络图的绘制第7页/共37页1. 计划网络图的概念 定义1 称任何消耗时间或资源的行动为作业.称作业的开始或结束为事件，事件本身不消耗资源. 在计划网络图中通常用圆圈表示事件，用箭线表示事件，如图7-12所示，1, 2, 3表示事件，A, B表示作业.由这种方法画出的网络图称为计划网络图.第8页/共37页定义2 在计划网络图中，称从是初始事件到最终事件的由各项作业连贯组成的一条路为路线。具有累计作业时间最长的路线称为关键路线。由此看来，一般网络图是

7、求相应的图中的关键路线。2. 建立计划网络图应注意的问题(1) 任何作业在网络中用唯一的箭线表示，任何作业其终点事件的编号必须大于其起点事件.1221第9页/共37页 (2) 两个事件之间只能画一条箭线，表示一项作业.对于具有相同开始和结束事件的两项以上作业，要引进虚事件和虚作业. (4) 计划网络图不允许出现回路12ab46a12b46回路123ac40b6123a/222b6a/2第10页/共37页 (3) 任何计划网络图应有唯一的最初事件和唯一的最终事件. (5) 计划网络图的画法一般是从左到右，从上到下，尽量作到清晰美观，避免箭头交叉.第11页/共37页 例1 某公司研制新产品的部分工

8、序明细表如下，试画出统筹图。（反向搜索法）工序代号 工序名称（或内容）工序长度紧前工序a产品设计与工艺设计60-b外购配套零件15ac外购生产原料13ad自制主件38ce主配件可靠性试验8b, d12453abced601513388分支时候尽量向一起努力第12页/共37页 例5 某工程项目作业明细表如下 ，（1）绘制计划网络图 ；（2）求关键路线与路长；（3）求关键工序序号序号工序代号工序代号所需时间所需时间紧前工序紧前工序1a60-2b15a3c13a4d38c5e8b、d6f10d7g16d8h5e、f、g第13页/共37页 解：若已知紧后工序之作业明细表，故用正象（顺向）搜索法，已知紧

9、前工序之作业明细表，故可采用反向搜索法。 （f g h）1253476abedghfc1254376abedghfc860151338810165第14页/共37页例3 某工厂进行技术改造的工作表如下：工序代号工序名称紧前工序工作时间（周）A拆迁/2B工程设计/3C土建工程设计B2.5D采购设备B6E厂房土建C，A20F设备安装D，E4G设备调试F2第15页/共37页1A(2)3B(3)2C（2.5）4D（6）E（20）5F（4）6G（2）第16页/共37页2.2 建立相应的规划问题方法1第17页/共37页 例 某项目工程由11项作业组成（分别用代号A, B, , J, K表示），其计划完成时

10、间及作业间相互关系如表7-8所示，求完成该项目的最短时间.第18页/共37页第19页/共37页2. 写出相应的规划问题 设是事件的开始时间， 为最初事件，为最终事件.希望总的工期最短，即极小化 .设是作业 的计划时间，因此，对于事件 与事件 有不等式： ixi11nxxijt( , )i jijjiijxxt由此得到相应的数学规划问题第20页/共37页 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

11、) x6 - x5 = 21第21页/共37页 10) x7 - x5 = 25 11) x8 - x5 = 35 12) x7 - x6 = 0 13) x8 - x6 = 20 14) x8 - x7 = 15第22页/共37页Objective value: 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.

12、000000 X4 14.00000 0.000000 X5 10.00000 0.000000 X6 31.00000 0.000000 X7 35.00000 0.000000第23页/共37页 计算结果给出了各个项目的开工时间，如计算结果给出了各个项目的开工时间，如 , 则则作业作业A、B、C的开工时间均是第的开工时间均是第0天天; 作业作业E的开的开工时间是第工时间是第5天天; 则作业则作业D的开工时间是第的开工时间是第10天天; 等等等等.每个作业只要按规定的时间开工，整个项每个作业只要按规定的时间开工，整个项目的最短工期为目的最短工期为51天天.10 x 25,x 310,x 第2

13、4页/共37页 尽管上述尽管上述LINgo程序给出相应的开工时间和整个程序给出相应的开工时间和整个项目的最短工期，但统筹方法中许多有用的信息并没项目的最短工期，但统筹方法中许多有用的信息并没有得到，如项目的关键路径、每个作业的最早开工时有得到，如项目的关键路径、每个作业的最早开工时间、最迟开工时间等间、最迟开工时间等.因此，我们希望将程序编写的因此，我们希望将程序编写的稍微复杂一些，为我们提供更多的信息稍微复杂一些，为我们提供更多的信息.第25页/共37页编写相应的Lingo程序，程序名： exam0721.lg4MODEL: 1sets: 2 events/1.8/: x; 3 operat

14、e(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; 9enddata 10min=sum(events : x); 11for(operate(i,j): s(i,j)=x(j)-x(i)-t(i,j); END第26页/共37页计算得到（只列出非零解）: Variable Value Reduced Cost X( 2) 5.000000 0.000000 X( 3

15、) 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( 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.00000

16、0第27页/共37页 由此，可以得到所有作业的最早开工时间和最迟开工时间，如表7-9所示，方括号中第1个数字是最早开工时间，第2个数字是最迟开工时间.第28页/共37页第29页/共37页 从上述表可以看出，当最早开工时间与最迟开工时间相同时，对应的作业在关键路线上，因此可以画出计划网络图中的关键路线，如图7-14粗线所示.关键路线为 13568.第30页/共37页2.3 建立相应的规划问题方法2第31页/共37页将关键路线看成最长路 如果将关键路线看成最长路，则可以按照求最短路的方法（将求极小改为求极大）求出关键路线 .设为 变量，当作业 位于关键路线上取1;否则取0. 数学规划问题写成:ij

17、x0 1( , )i j第32页/共37页例 用最长路的方法求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,5 3,5 4,6 5,6 5,8 5,7 6,7 7,8 6,8 5 /: t, x; 6endsets 7data:第33页/共37页 8 t = 5 10 11 4 4 0 15 21 35 25 0 15 20; 9 d = 1 0 0 0 0 0 0 -1; 10enddata 11max=sum(operate : t*x); 12for(events(i): 13 sum(operate(i,j): x(i,j) - sum(operate(j,i): x(j,i) 14 =d(i); 15); END第34页/共37页计算得到（只列出非零解):Objective value: 51.00000 Variable