工期安排问题

1. 问题重述：花最短的时间完成所有的活动（假设有足够的工人和金钱支持多个活动同时进行）。约束条件：相应的活动必须到达起始节点才能开始。

根据**可以得出流程图，其中字母表示活动，括号内数字表示完成该活动的天数。

设一个活动的工期为xi天，等待开工为ｙi天，即一个活动完成需要ti=（xi+ｙi）天，所以完成该项目的最短时间为最后一个活动完成的时间max（ti）。而每个活动的完成时间都是确定的，所以只需求出最短的等待时间yi天，也就是到达各自的开始起点的时间最短。

如果都以节点9为终点（即k活动完成），从节点1出发共有5条路；分别是：

设活动终止的节点为横坐标，完成活动时间加上等待时间为纵坐标（5条路各自独立）

即①a(2,2) d(5,6) g(7,12) j(8,13) k(9,15)

②a(2,2) b(3,4) e(6,6) i(7,11) j(8,12) k(9,14)

③a(2,2) b(3,4) e(6,6) h(8,8) k(9,10)

④a(2,2) c(4,5) f(6,8) i(7,13) j(8,14) k(9,16)

⑤a(2,2) c(4,5) f(6,8) h(8,10) k(9,12)

> x1=[2,5,7,8,9];y1=[2,6,12,13,15];

x2=[2,3,6,7,8,9];y2=[2,4,6,11,12,14];

x3=[2,3,6,8,9];y3=[2,4,6,8,10];

x4=[2,4,6,7,8,9];y4=[2,5,8,13,14,16];

x5=[2,4,6,8,9];y5=[2,5,8,10,12];

plot(x1,y1,'r*')

hold on

> plot(x1,y1,'r*')

> plot(x2,y2,'b*')

> plot(x3,y3,'g*')

> plot(x4,y4,'k*')

> plot(x5,y5,'y*')

> grid on

> title('各个活动完成时间')

完成最后一个活动需要12天。

即完成该项目最短需要12天。

先从1节点出发完成a（2天）活动，接着从2节点出发b、c和d同时进行；当完成d（4天）时，b+e(4天)也完成了，f（1天）完成了三分之一；紧接着从5节点和6节点同时出发，完成g（6天）、i+j（6天）、h+k（4天）；当其他活动进行的同时f也完成了剩余的三分之一。即t总=2+4+6=12天。

2根据题1可得出完成所有活动的时间表（同一行活动是从左往右依次进行，同一列活动各自独立进行）

根据**可知加快a活动，或者加快g活动和i活动可以使项目提前完成。