数据挖掘--网络分析

1、燕山大学经济管理学院燕山大学经济管理学院运筹学课程教学课题组编制运筹学课程教学课题组编制2第八章第八章网络计划网络计划一、网络计划原理一、网络计划原理 1. 概念概念：以网络图的形式制定计划，求：以网络图的形式制定计划，求得计划的最优方案。并据以组织和计划生得计划的最优方案。并据以组织和计划生产，达到预定目标的一种科学的管理方法。产，达到预定目标的一种科学的管理方法。 2. 原理原理：利用网络图表达计划任务的进：利用网络图表达计划任务的进度安排及各项工作之间的相互关系，并进度安排及各项工作之间的相互关系，并进行网络分析。通过相应的网络时间值的计行网络分析。通过相应的网络时间值的计算，找出影响全

2、局的算，找出影响全局的关键工作关键工作和和关键线路关键线路，利用时间差，不断改善网络计划，求得工利用时间差，不断改善网络计划，求得工期、成本、资源的优化方案。期、成本、资源的优化方案。二、网络图的绘制二、网络图的绘制 1. 网络图的构成网络图的构成 （1）作业：）作业：代号或工作名称代号或工作名称需要的资源或时间需要的资源或时间ji C 37846（2） 事项：事项：i （3） 线路：从始点事项开始，顺箭线方线路：从始点事项开始，顺箭线方向连续不断的到达终点事项的一条通道。向连续不断的到达终点事项的一条通道。2. 绘制网络图需注意：绘制网络图需注意：（1）只有一个源，一个汇）只有一个源，一个汇

3、1675342ABCDEF2. 绘制网络图需注意：绘制网络图需注意：（1）只有一个源，一个汇）只有一个源，一个汇17532ABCDEF（2）箭线方向一律由左向右，不得反向）箭线方向一律由左向右，不得反向（3）节点保证）节点保证 ijj i（4）编号不准相同，可以连续编，也可以）编号不准相同，可以连续编，也可以不连续编。不连续编。（5）各作业之间有先后平行关系，但不）各作业之间有先后平行关系，但不允许有回路。允许有回路。1243ABDC15432ABCD（6）箭线首尾必须有结点）箭线首尾必须有结点（7）进入一个节点的箭线有多条，但相邻的）进入一个节点的箭线有多条，但相邻的两个节点之间只能由一条箭

4、线。若相邻两结两个节点之间只能由一条箭线。若相邻两结点间有多条箭线，除一条外，其余用虚箭线点间有多条箭线，除一条外，其余用虚箭线予以分开。予以分开。 （8）网络图中不允许由双向箭线，无箭头）网络图中不允许由双向箭线，无箭头箭线。箭线。（9）应尽量减少交叉和不必要的需箭线。）应尽量减少交叉和不必要的需箭线。3. 绘制网络图举例绘制网络图举例 例例1：作业作业代号代号ABDECFG后续后续作业作业BCDEFGFG-123456ABCDEFG作业作业代号代号ABDECFG后续后续作业作业BCDEFGFG-3. 绘制网络图举例绘制网络图举例 例例2：代码代码ABCDEFG紧前工作紧前工作-ACBCDE

5、F代码代码ABCDEFG紧前工作紧前工作-ACBCDEF142AB3567CDEFG28312443一、工作时间一、工作时间t ( i , j )的确定的确定ijt ( i , j )确定型确定型 t ( i , j )概率型概率型 t ( i , j )=(a+4m+b)/6 a 最乐观时间最乐观时间 m 最大可能时间最大可能时间 b 最悲观时间最悲观时间第二节第二节 网络时间值的计算网络时间值的计算二、二、 事项时间参数计算事项时间参数计算( (已知已知 t（i , j） ) 1. 1. 事项最早时间事项最早时间: : 表示以它为始点的各工作最早可能开始时间，表示以它为始点的各工作最早可能

6、开始时间，也表示以它为终点的各工作最早可能结束时间。也表示以它为终点的各工作最早可能结束时间。tE(i)tE(1)=0tE(n)=总最早完工工期总最早完工工期142AB3567CDEFG28312443025817212424211717520作业最迟开始时间作业最迟开始时间5 175 172 52 50 89 170 20 221 2421 2417 2117 218 1217 21作业最迟开始时间作业最迟开始时间tLS(i, j) = tLF(i, j) -tijjk1ik2t ijt j k2t jk1tLS(j , kl)tLS(j,k2)tES(i, j)tEF(i, j)tLS(i

7、, j)tLF(i, j)tLS(i, j)=mintLS(j,k)-tjk (5) 作业总时差作业总时差: 在不影响总工期的前提下，某工作可以在不影响总工期的前提下，某工作可以延迟其开始时间的最大幅度。延迟其开始时间的最大幅度。 R(i, j)作业总时差作业总时差R(i, j)=tLS(i, j)-tES(i, j)=tLF(i, j)-tEF(i, j)tES(i, j)tEF(i, j)tLS(i, j)tLF(i, j)ij作业总时差作业总时差142AB3567CDEFG283124430258172124242117175205 175 172 52 50 89 170 20 221

8、 2421 2417 2117 218 1217 210000099 (6) 作业单时差：作业单时差： 不影响紧后工作最早开始时间的条不影响紧后工作最早开始时间的条件下，此工作可以延迟开始时间的最大幅件下，此工作可以延迟开始时间的最大幅度度。r(i, j)=tES(j, k)-tEF(i, j) = tES(j, k)-(tES(i, j)+tij)tES(i, j)tEF(i, j)tLS(i, j)tLF(i, j)ij jktES(j, k) tEF(j, k)tLS(j, k)tLF(j, k)tE (j)tL (j)142AB3567CDEFG28312443025817212424

9、2117175205 175 172 52 50 89 170 20 221 2421 2417 2117 218 1217 210作业单时差作业单时差142AB3567CDEFG283124430258172124242117175205 175 172 52 50 89 170 20 221 2421 2417 2117 218 1217 210000009作业单时差作业单时差四、关键线路与工期四、关键线路与工期 关键线路：总时差为关键线路：总时差为0的工作链。的工作链。 工期：关键线路上各项活动作业时工期：关键线路上各项活动作业时间之和。间之和。142AB3567CDEFG2831244

10、30258172124242117175205 175 172 52 50 89 170 20 221 2421 2417 2117 218 2117 210000099142AB3567CDEFG283124430258172124242117175205 175 172 52 50 89 170 20 221 2421 2417 2117 218 2117 21000009912598763452323124001第三节第三节 网络计划的其它问题网络计划的其它问题一、网络计划的优化一、网络计划的优化1. 将串联工作改变为平行工作或交叉工作将串联工作改变为平行工作或交叉工作2. 利用时差利用时差3. 有限资源的合理分配有限资源的合理分配142AB3567CDEFG283124430258172124242117175202498122124. 时间时间-费用优化费用优化两