运筹学第十一章网络计划山东大学期末考试知识点复习

山东大学期末考试知识点复习第十一章网络计划1．网络图相关概念网络图是由节点(点)、弧及权所构成的有向图，即有向的赋权图。(1)节点表示一个事项(事件)。它是一个或若干个工序的开始或结束是相邻工序的时间上的分界点。结点用圆圈和里面的数字表示，数字表示结点的编号，如①，②，…等。(2)弧表示一个工序，工序需要一定的人力、物力等资源和时间，弧用箭线“→”表示。(3)权表示为完成某个工序所需要的时间或资源等数据，通常标注在箭线下面或其他合适的位置上。在网络图中，用一条弧和两个结点表示一个确定的工序。例如，②⑦表示一个确定的工序b。2．绘制网络图应遵循的原则(1)方向、时序与节点编号。网络图是有向图，按照工艺流程的顺序，规定工序从左向右排列，网络图中的各个节点都有一个时间，一般按各个节点的时间顺序编号。(2)紧前工序与紧后工序。如只有在a工序结束后，b工序才能开始，则a工序是b工序的紧前工序，b工序是a工序的紧后工序。(3)虚工序。为了用来表达相邻工序之间的衔接关系，是实际上并不存在而虚设的工序。用虚箭线i→j表示，虚工序不需要人力、物力等资源和时间。(4)相邻的两个节点之间只能有一条弧。(5)网络图中不能有缺口和回路。(6)平行作业。某些工序可以同时进行，即可采用平行作业的方式。(7)交叉作业。平行作业，或在几个工序结束后完工，用一个始点，一个终点表示。若这些工序不能用一个始点或一个终点表示时，可用虚工序把它们与始点与终点连接起来。对需要较长时间才能完成的一些工序，在工艺流程与生产组织条件允许的情况下，可以不必等待工序全部结束后再转人其紧后工序，而是分期分批的转入，这种方式称为交叉作业。(8)始点和终点。为表示工程的开始和结束，在网络图中只能有一个始点和一个终点。当工程开始时有几个工序平行作业，或在几个工序结束后完工，用一个始点，一个终点表示。若这些工序不能用一个始点或一个终点表示时，可用虚工序把它们与始点与终点连接起来。(9)网络图的分解与综合。根据综合程度高网络图的要求，制作本部门综合程度低的网络图(子网络)，将母网络分解为若干个子网络，称为网络的分解。而将若干个子网络综合为一个母网络，则称为网络图的综合。(10)网络图的布局。网络图中，尽可能将关键路线布置在中心位置，并尽量将联系紧密的工作布置在相近的位置。为使网络图清楚和便于在图上填写有关的时间数据与其它数据，弧线尽量用水平线或具有一段水平的折线。3．时间参数(1)对节点。节点的最早开始时间TE(j)TE(j)=max{TE(i)+Di-j}，j=2，3，…，n节点的最迟完成时间TL(j)TL(i)=min{TL(j)-Di-j}，i=n-1，n-2，…，1(2)对作业。①对作业的最早开始时间ESi-j作业(i，j)的最早开始时间显然等于箭尾结点i的最早开始时间，将这一参数值填入作业线下所画的“口”符号中，即ESi-j=TE(i)②作业的最早完成时间EFi-j在正常情况下，作业(i，j)若能在最早开始时间开始，就有一个最早完成时间，该最早完成时间为箭尾结点的最早时间加上作业(i，j)所需的工时，即EFi-j=TE(i)+Di-j=ESi-j+Di-j③作业的最迟完成时间LFi-j作业的最迟完成时间等于箭头结点j的最迟完成时间，即LFi-j=TL(j)④作业的最迟开始时间LSi-j在正常情况下，作业(i，j)完成的最迟是因为开工迟，所以对应于最迟完成时间LFi-j就有一个最迟开始时间LSi-j，它等于作业(i，j)的箭头结点j的最迟时间减去作业自身所消耗的工时，即LSi-j=TL(j)-Di-j=LFi-j-Di-j这一参数填入作业线下所画的“△”符号中。4．网络的优化(1)工期优化。①采取技术措施，缩短工程完工时间；②采取组织措施，充分利用非关键工序的总时差，合理调配技术力量及人、财、物等资源，缩短关键工序的作业时间。(2)资源优化。①优先安排关键工序所需要的资源；②利用非关键工序的总时差，错开各工序的开始时间，拉平资源需要量的高峰；③在资源受到限制或考虑综合经济效益的条件下