最优运输问题数学模型.doc

ata: t=5 10 11 4 4 0 15d 21 25 35 0 20 15; enddata min=x(8)-x(1); @for(x2=5 ，作业E的开工时间是第5天； x3 =10 ，则作业D的开工时间是第 10 天；等等。每个作业只要按规定的时间开工，整个项目的最短工期为51 天。 尽管上述 LINGO 程序给出相应的开工时间和整个项目的最短工期，但统筹方法中 许多有用的信息并没有得到，如项目的关键路径、每个作业的最早开工时间、最迟开工 时间等。 例 21（续例20）求例20 中每个作业的最早开工时间、最迟开工时间和作业的关 键路径。 解 为了得到每个作业的最早开工时间、作业的关键路线等，将目标函数改为 Σxi,即作业的开始时间尽量早，这样就可以得到作业的最早开工时间。再引进作业 对应弧上的松弛变量 s ij，且s = xj ? xi ? tij ，(i, j)∈ A，这样就可以得到作业的最迟 开工时间，记yi 表示事件i 的最迟开工时间。当最早开工时间与最迟开工时间相同时， 就得到项目的关键路径。 编写 LINGO 程序如下：operate(i,j):x(j)x(i)+t(i,j)); end 计算结果给出了各个项目的开工时间，如x1 = 0，则作业A, B,C的开工时间均是 第0 天； model: sets: events/1..8/:x,z; operate(events,events)/1 2,1 3,1 4,2 5,3 4,3 5,4 6,5 6, 5 7,5 8,6 7,6 8,7 8/:s,t,m,c,y; endsets data: t=5 10 11 4 4 0 15 21 25 35 0 20 15; m=5 8 8 3 4 0 15 16 22 30 0 16 12; c=0 700 400 450 0 0 0 600 300 500 0 500 400; d=49; @text(txt2.txt)=x,z; enddata min=mincost+sumx; mincost=@sum(operate:c*y); sumx=@sum(events:x); @for(operate(i,j):s(i,j)=x(j)-x(i)+y(i,j)-t(i,j)); n=@size(events); x(1)=0; x(n)d; @for(operate:@bnd(0,y,t-m)); z(n)=x(n); @for(events(i)|i#lt#n:z(i)=@min(operate(i,j):z(j)-t(i,j)+y(i,j))); end 最迟开工时间的分析需要用到松弛变量 sij ，当 0 ij s 时，说明还有剩余时间，对 应作业的工期可以推迟sij。例如，s78 = 1，作业（7，8）（J ）的开工时间可以推迟1 天，即开工时间为36。再如2 s 46= ，作业（4，6）（F ）可以推迟2 天开始， s14 =3 ， 作业（1，4）（C ）可以推迟3 天开始，但由于作业（4，6）（ F ）已能够推迟2 天， 所以，作业（1，4）（C ）最多可推迟5 天。 由此，可以得到所有作业的最早开工时间和最迟开工时间，如下表所示，方括号 中第1 个数字是最早开工时间，第2 个数字是最迟开工时间。 表10 作业数据 作业(i, j) 开工时间 计划完成时间（天） 作业(i, j) 开工时间 计划完成时间（天） 从上表可以看出，当最早开工时间与最迟开工时间相同时，对应的作业在关键路 线上，因此可以画出计划网络图中的关键路线，如图11 粗线所示。关键路线为1→3→ 5→6→8。 图 11 带有关键路线的计划网络图 9.3.4 将关键路线看成最长路 如果将关键路线看成最长路，则可以按照求最短路的方法（将求极小改为求极大） 求出关键路线。 设 ij x 为0-1 变量，当作业(i, j)位于关键路线上取1，否则取0。数学规划问题写 成： 例22 用最长路的方法，求解例20。 解 按上述数学规划问题写出相应的LINGO 程序。 model: sets:events/1..8/:d; operate(events,events)/1 2,1 3,1 4,2 5,3 4,3 5,4 6,5 6, 5 7,5 8,6 7,6 8,7 8/:t,x; endsets data: t=5 10 11 4 4 0 15 21 25 35 0 20 15; d=1 0 0 0 0 0 0 -1; enddata max=@sum(operate:t*x); @for(events(i):@sum(operate(i,j):x(i,j))-@sum(operate(j,i):x(j,i))=d(i)); end 求短