最优运输问题数学模型

来源：尔游网

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)@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。数学规划问题写成：

max(ij)Atxijij

例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 求短

工期。得工期需要 51 天，关键路线为1→3→5→6→8。 9.4 关键路线与计划网络的优化

例 23（关键路线与计划网络的优化）假设例 20 中所列的工程要求在49 天内完成。为提前完成工程，有些作业需要加快进度，缩短工期，而加快进度需要额外增加费用。下表列出例20 中可缩短工期的所有作业和缩短一天工期额外增加的费用。现在的问题是，如何安排作业才能使额外增加的总费用最少。表 11 工程作业数据

例 23 所涉及的问题就是计划网络的优化问题，这时需要压缩关键路径来减少最 9.4.1 计划网络优化的数学表达式

设 xi 是事件i 的开始时间， tij 是作业(i, j)的计划时间， m ij是完成作业(i, j)的最短时间， yij 是作业(i, j)可能减少的时间， cij 是作业(i, j)缩短一天增加的费用.

且 oyijtijmij

设d 是要求完成的天数，1为最初事件，n为最终事件，所以有x x d n − ≤ 1 。而问题的总目标是使额外增加的费用最小，即目标函数为规划问题：

mincijyij。由此得到相应的数学

(ij)As.t.xjxiyijtij,(i,j)A,i,jv

xnx1doyijtijmij,

(i,j)A,i,jV9.4.2 计划网络优化的求解

用 LINGO 软件求解例23，程序如下： model: sets:

events/1..8/:x;

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,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; enddata

min=@sum(operate:c*y);

@for(operate(i,j):x(j)-x(i)+y(i,j)>t(i,j)); n=@size(events); x(n)-x(1)@for(operate:@bnd(0,y,t-m)); end

作业(1,3)(B)）压缩1 天的工期，作业(6,8)(K)压缩1天工期，这样可以在49天完工，需要多花费1200 元。

如果需要知道压缩工期后的关键路径，则需要稍复杂一点的计算。

例 24 （续例23）用 LINGO 软件求解例23，并求出相应的关键路径、各作业的最早开工时间和最迟开工时间。

解为了得到作业的最早开工时间，仍在目标函数中加入Σ ∈V i xi ，记zi 表示事件i 的最迟开工时间，其它处理方法与前面相同。

写出相应的 LINGO 程序如下： 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)@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

计算出所有作业的最早开工时间和最迟开工时间，见表 12

当最早开工时间与最迟开工时间相同时，对应的作业就在关键路线上，图12 中的粗线表示优化后的关键路线。从图5-10 可以看到，关键路线不止一条。

9.5 完成作业期望和实现事件的概率

在例 20 中，每项作业完成的时间均看成固定的，但在实际应用中，每一工作的完成会受到一些意外因素的干扰，一般不可能是完全确定的，往往只能凭借经验和过去完成类似工作需要的时间进行估计。通常情况下，对完成一项作业可以给出三个时间上的估计值：最乐观值的估计值（ a ），最悲观的估计值（b ）和最可能的估计值（m ）。设 ij t 是完成作业(i, j)的实际时间（是一随机变量），通常用下面的方法计算相应的数学期望和方差。

(tij)(aij4mijbij)/6var(tij)T(bijaij)^236(13)(14)

ij(ij)关键路线t(16)

由中心极限定理，可以假设T 服从正态分布，并且期望值和方差满足

S2var(T)(ij)关键路线var(t)ij （17）

设规定的工期为 d ，则在规定的工期内完成整个项目的概率为

dTPTd()S@psn(x)是LINGO 软件提供的标准正态分布函数，即

(18)

pan(x)(x)x1t2/2edt

2

例 25 已知例20 中各项作业完成的三个估计时间如下表所示。如果规定时间为52

天，求在规定时间内完成全部作业的概率。进一步，如果完成全部作业的概率大于等于 95％，那么工期至少需要多少天？

表13 作业数据

解对于这个问题采用最长路的编写方法。

按公式（13）和公式（14）计算出各作业的期望值与方差，再由期望时间计算出关键路线。从而由公式（16）和公式（17）得到关键路线的期望与方差的估计值，再利用分布函数@psn(x)，计算出完成作业的概率与完成整个项目的时间。写出相应的 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/:a,m,b,et,dt,x; endsets data:

a=3 8 8 3 2 0 8 18 18 26 0 11 12; m= 5 9 11 4 4 0 16 20 25 33 0 21 15; b=7 16 14 5 6 0 18 28 32 52 0 25 18; d=1 0 0 0 0 0 0 -1; limit=52; enddata

@for(operate:et=(a+4*m+b)/6;dt=(b-a)^2/36); max=tbar;

tbar=@sum(operate:et*x);

@for(events(i):@sum(operate(i,j):x(i,j))-@sum(operate(j,i):x(j,i))=d(i)); s^2=@sum(operate:dt*x); p=@psn((limit-tbar)/s); @psn((days-tbar)/s)=0.95; end

求得关键路线的时间期望为 51 天，标准差为3.16，在52 天完成全部作业的概率为 62.4%，如果完成全部作业的概率大于等于95％，那么工期至少需要56.2 天。

§10 钢管订购和运输 10.1 问题描述

要铺设一条 1 2 15 A → A →L→ A 的输送天然气的主管道, 如图14 所示。经筛选

后可以生产这种主管道钢管的钢厂有1 2 7 S , S ,LS 。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。

图14

为方便计，1km 主管道钢管称为1 单位钢管。

一个钢厂如果承担制造这种钢管，至少需要生产500 个单位。钢厂i S 在指定期限内能生产该钢管的最大数量为i s 个单位，钢管出厂销价1 单位钢管为i p 万元，见表14； 1 单位钢管的铁路运价见表15。

1000km 以上每增加1 至100km 运价增加5 万元。公路运输费用为1 单位钢管每公里0.1 万元（不足整公里部分按整公里计算）。钢管可由铁路、公路运往铺设地点（不只是运到点1 2 15 A , A ,L, A ，而是管道全线）。

（1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。（2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。

（3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网

络，请就这种更一般的情形给出一种解决办法，并对图15 按（1）的要求给出模型和结果。

图15

10.2 模型的建立与求解

记第i 个钢厂的最大供应量为i s ，从第i 个钢厂到铺设节点j 的订购和运输费用为

ij c ；用j l 表示管道第j 段需要铺设的钢管量。ij x 是从钢厂i 运到节点j 的钢管量， j y 是

从节点j 向左铺设的钢管量， j z 是从节点j 向右铺设的钢管量。

根据题中所给数据，我们可以先计算出从供应点i S 到需求点j A 的最小购运费ij c （即出厂售价与运输费用之和），再根据ij c 求解总费用，总费用应包括：订购费用（已包含在ij c 中），运输费用（由各厂i S 经铁路、公路至各点j A ， i = 1,2,L,7 ,

j = 1,2,L,15），铺设管道( 1,2, ,14) 1 = L + A A j j j 的运费。分析题目可以知道约束条件应包括：

钢厂产量约束：上限和下限（如果生产的话）；运量约束:xij 对i求和等于zj 加yj ；yj1与zj之和等于AjAj1段的长度lj. 由Aj向AjAj1段铺设管道的运输总路程为1yjyj(yj1)/2；由 Aj 向AjAj1段铺设管道的运输总路程为1zjzj(zj1)/2. 根据以上条件可以建立模型如下：

0.115 mincijxij(zj(zj1)yj(yj1) (20) 2j1i1j1 s.t.715x0[500,s]ijij1ij15i1,2,7 (21)

xi17zjyjj1,2,15 (22)

yj1zjlj xij0,zj0,yj0j1,2,14 (23) i1,2,,7,j1,2,,15 (24)

10.2.3 Lingo 程序

使用计算机求解上述数学规划时，需要对约束条件（20）进行处理.我们引进0 −1 变量fi1,钢厂i生产

0，钢厂i不生产15把约束条件（20）转化为

500fixj1ijsifi,i1,2,7 (26)

利用 Lingo 求得总费用的最小值为127.8632 亿.Lingo 程序如下： model: sets:

!nodes 表示节点集合;

nodes /S1,S2,S3,S4,S5,S6,S7,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12,A13,A14,A15, B1,B2,B3,B4,B5,B6,B7,B8,B9,B10,B11,B12,B13,B14,B15,B16,B17/; !c1(i,j)表示节点i 到j 铁路运输的最小运价（万元）,c2(i,j)表示节点i 到j 公路运输的费用邻接矩阵，c(i,j)表示节点i 到j 的最小运价，path 标志最短路径上走过的顶点; link(nodes, nodes): w, c1,c2,c,path1,path; supply/S1..S7/:S,P,f;

need/A1..A15/:b,y,z; !y 表示每一点往左铺的量，z 表示往右铺的量; linkf(supply, need):cf,X; endsets data:

S=800 800 1000 2000 2000 2000 3000; P=160 155 155 160 155 150 160;

b=104,301,750,606,194,205,201,680,480,300,220,210,420,500,0; path1=0; path=0; w=0; c2=0;

! 以下是格式化输出计算的中间结果和最终结果;

@text(MiddleCost.txt)=@writefor(supply(i): @writefor(need(j): @format(cf(i,j),' 6.1f' )),

@newline(1));

@text(Train_path.txt)=@writefor(nodes(i):@writefor(nodes(j):@format(path1(i,j),'5.0f')), @newline(1));

@text(Final_path.txt)=@writefor(nodes(i):@writefor(nodes(j):@format(path(i,j),'5.0f')),

@newline(1));

@text(FinalResult.txt)=@writefor(supply(i):@writefor(need(j):@format(x(i,j),'5.0f')),

@newline(1) );

@text(FinalResult.txt)=@write(@newline(1));

@text(FinalResult.txt)=@writefor(need:@format(y,'5.0f') ); @text(FinalResult.txt)=@write(@newline(2));

@text(FinalResult.txt)=@writefor(need:@format(z,'5.0f') ); enddata calc:

!输入铁路距离邻接矩阵的上三角元素;

w(1,29)=20;w(1,30)=202;w(2,30)=1200;w(3,31)=690;w(4,34)=690;w(5,33)=462; w(6,38)=70;w(7,39)=30;w(23,25)=450;w(24,25)=80;w(25,27)=1150;w(26,28)=306; w(27,30)=1100;w(28,29)=195;w(30,31)=720;w(31,32)=520;w(32,34)=170;w(33,34)=88; w(34,36)=160;w(35,36)=70;w(36,37)=320;w(37,38)=160;w(38,39)=290;

@for(link(i,j): w(i,j) = w(i, j)+w(j,i) ); !输入铁路距离邻接矩阵的下三角元素; @for(link(i,j)|i#ne#j: w(i,j)=@if(w(i,j) #eq# 0, 20000,w(i,j))); ! 无铁路连接，元素为充分大的数;

!以下就是最短路计算公式（Floyd-Warshall 算法）;

@for(nodes(k):@for(nodes(i):@for(nodes(j):tm=@smin(w(i,j),w(i,k)+w(k,j)); path1(i,j)=@if(w(i,j)#gt# tm,k,path1(i,j));w(i,j)=tm))); !以下就是按最短路w 查找相应运费C1 的计算公式; @for(link|w#eq#0: C1=0);

@for(link|w#gt#1000: C1= 60+5*@floor(w/100-10)+@if(@mod(w,100)#eq#0,0,5) ); !输入公路距离邻接矩阵的上三角元素;

c2(1,14)=31;c2(6,21)=110;c2(7,22)=20;c2(8,9)=104;c2(9,10)=301;c2(9,23)=3;

c2(10,11)=750;c2(10,24)=2;c2(11,12)=606;c2(11,27)=600;c2(12,13)=194;c2(12,26)=10;

c2(13,14)=205;c2(13,28)=5;c2(14,15)=201;c2(14,29)=10;c2(15,16)=680;c2(15,30)=12;

c2(16,17)=480;c2(16,31)=42;c2(17,18)=300;c2(17,32)=70;c2(18,19)=220;c2(18,33)=10;

c2(19,20)=210;c2(19,35)=10;c2(20,21)=420;c2(20,37)=62;c2(21,22)=500;c2(21,38)=30;

c2(22,39)=20;

@for(link(i,j): c2(i,j) = c2(i,j)+c2(j,i)); !输入公路距离邻接矩阵的下三角元素; @for(link(i,j):c2(i,j)=0.1*c2(i,j)); ! 距离转化成费用;

@for(link(i,j)|i#ne#j: c2(i,j) =@if(c2(i,j)#eq#0,10000,c2(i,j) )); !无公路连接，元素为充分大的数;

@for(link: C= @if(C1#le#C2,C1,C2)); ! C1 和C2 矩阵对应元素取最小;

@for(nodes(k):@for(nodes(i):@for(nodes(j):tm=@smin(C(i,j),C(i,k)+C(k,j)); path(i,j)=@if(C(i,j)#gt# tm,k,path(i,j));C(i,j)=tm)));

@for(link(i,j)|i #le# 7 #and# j#ge#8 #and# j#le# 22:cf(i,j-7)=c(i,j)); !提取下面二次规划模型需要的7×15 矩阵; endcalc

[obj]min=@sum(linkf(i,j):(cf(i,j)+p(i))*x(i,j))+0.05*@sum(need(j):y(j)^2+y(j)+z(j)^2+z(j)); ! 约束;

@for(supply(i):[con1]@sum(need(j):x(i,j))<= S(i)*f(i)); @for(supply(i):[con2]@sum(need(j):x(i,j)) >= 500*f(i)); @for(need(j):[con3] @sum(supply(i):x(i,j))=y(j)+z(j)); @for(need(j)|j#NE#15:[con4] z(j)+y(j+1)=b(j)); y(1)=0; z(15)=0;

@for(supply: @bin(f)); @for(need: @gin(y)); end

10.3 管道为树形图时的模型

当管道为树形图时，建立与上面类似的非线性规划模型 mincxi1j1721ijij0.052121j1(jk)E(y2jkyjk) (27)

s.t.500fi7xijsifi,i1,2,,7 (28)

j1

xi1ij(jk)Eyjk,j1,2,,21 (29)

yjkykjljk,xij,yjk0 (30)

其中( jk )是连接Aj,Ak的边，E 是树形图的边集，ljk是从Aj到Ak的长度, yjk是由Aj 沿( jk )铺设的钢管数量.

用 Lingo 求解得最小费用为140.6631 亿元。Lingo 程序如下： model: sets:

! nodes 表示节点集合;

nodes/S1,S2,S3,S4,S5,S6,S7,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12,A13,A14,A15,A16,A17,A18,A19,A20,B1,B2,B3,B4,B5,B6,B7,B8,B9,B10,B11,B12/; !c1(i,j)表示节点i 到j 铁路运输的最小单位运价（万元）,c2(i,j)表示节点i 到j 公路运输的邻接权重矩阵，c(i,j)表示节点i 到j 的最小单位运价，path 标志最短路径上走过的顶点;

link(nodes, nodes): w, c1,c2,c,path1,path; supply/S1..S7/:s,p,f;

need/A1..A21/:b,y,z;!y 表示每一点往节点编号小的方向铺设量，z 表示往节点编号大的方向铺设量;

linkf(supply, need):cf,x;

special/1..3/:sx; ! 铺设节点9，11，17 往最大编号节点方向的铺设量; endsets data:

s=800 800 1000 2000 2000 2000 3000; p=160 155 155 160 155 150 160;

b=104,301,750,606,194,205,201,680,480,300,220,210,420,500,42,10,130,190,260,100,0;

path1=0; path=0; w=0; c2=0;

! 以下是格式化输出计算的中间结果和最终结果;

@text(MiddleCost.txt)=@writefor(supply(i): @writefor(need(j): @format(cf(i,j),' 6.1f' )), @newline(1));

@text(Train_path.txt)=@writefor(nodes(i):@writefor(nodes(j):@format(path1(i,j),'5.0f')), @newline(1));

@text(Final_path.txt)=@writefor(nodes(i):@writefor(nodes(j):@format(path(i,j),'5.0f')),

@newline(1));

@text(FinalResult.txt)=@writefor(supply(i):@writefor(need(j):@format(x(i,j),'5.0f')),

@newline(1) );

@text(FinalResult.txt)=@write(@newline(1));

@text(FinalResult.txt)=@writefor(need:@format(y,'5.0f')); @text(FinalResult.txt)=@write(@newline(2));

@text(FinalResult.txt)=@writefor(need:@format(z,'5.0f')); enddata calc:

!输入铁路距离邻接矩阵的上三角元素;

w(28,30)=450;w(29,30)=80;w(30,32)=1150;w(31,33)=306;w(33,34)=195;w(1,34)=20; w(1,35)=202;w(32,35)=1100;w(2,35)=1200;w(23,35)=720;w(3,23)=690;w(23,36)=520;

w(36,37)=170;w(4,37)=690;w(5,24)=462;w(24,37)=88;w(25,37)=160;w(25,26)=70; w(25,27)=320;w(27,38)=160;w(6,38)=70;w(38,39)=290;w(7,39)=30;

@for(link(i,j): w(i,j) = w(i, j)+w(j,i) );!输入铁路距离邻接矩阵的下三角元素; @for(link(i,j)|i#ne#j: w(i,j)=@if(w(i,j) #eq# 0, 20000,w(i,j))); ! 无铁路连接，元素为充分大的数;

!以下就是最短路计算公式（Floyd-Warshall 算法）;

@for(link|w#gt#1000: C1= 60+5*@floor(w/100-10)+@if(@mod(w,100)#eq#0,0,5) ); !输入公路距离邻接矩阵的上三角元素;

c2(8,9)=104;c2(9,10)=301;c2(10,11)=750;c2(11,12)=606;c2(12,13)=194;c2(13,14)=205;

c2(14,15)=201;c2(15,16)=680;c2(16,17)=480;c2(16,23)=42;c2(17,18)=300;c2(18,19)=220;

c2(18,24)=10;c2(19,20)=210;c2(20,21)=420;c2(21,22)=500;c2(24,25)=130;c2(24,26)=190;

c2(26,27)=260;c2(6,27)=100;c2(9,28)=3;c2(10,29)=2;c2(11,32)=600;c2(12,31)=10; c2(13,33)=5;c2(14,34)=10;c2(1,14)=31;c2(15,35)=12;c2(17,36)=70;c2(19,26)=10; c2(20,27)=62;c2(6,21)=110;c2(21,38)=30;c2(22,39)=20;c2(7,22)=20;

@for(link(i,j): c2(i,j) = c2(i,j)+c2(j,i)); !输入公路距离邻接矩阵的下三角元素; @for(link(i,j):c2(i,j)=0.1*c2(i,j)); ! 距离转化成费用;

@for(link(i,j)|i#ne#j: c2(i,j) =@if(c2(i,j)#eq#0,10000,c2(i,j) )); ! 距离转化成费用;

@for(link: C= @if(C1#le#C2,C1,C2)); !邻接矩阵的对角线元素变为0;

@for(nodes(k):@for(nodes(i):@for(nodes(j):tm=@smin(C(i,j),C(i,k)+C(k,j)); path(i,j)=@if(C(i,j)#gt# tm,k,path(i,j));C(i,j)=tm)));

@for(link(i,j)|i #le# 7 #and# j#ge#8 #and# j#le# 27:cf(i,j-7)=c(i,j)); !提取下面二次规划模型需要的7×21 矩阵; @for(supply(i):cf(i,21)=c(i,6)); endcalc

[obj]min=@sum(linkf(i,j):(cf(i,j)+p(i))*x(i,j))+0.05*@sum(need(j):y(j)^2+y(j)+z(j)^2+z(j))+0.05*@sum(special:sx^2+sx);! 约束;

@for(supply(i):[con1]@sum(need(j):x(i,j))<= s(i)*f(i)); @for(supply(i):[con2]@sum(need(j):x(i,j)) >= 500*f(i)); @for(need(j)|j#ne#9#and#j#ne#11#and#j#ne#17:[con3] @sum(supply(i):x(i,j))=y(j)+z(j));

y(9)+z(9)+sx(1)=@sum(supply(i):x(i,9)); y(11)+z(11)+sx(2)=@sum(supply(i):x(i,11)); y(17)+z(17)+sx(3)=@sum(supply(i):x(i,17)); @for(need(j)|j #le# 14:(z(j)+y(j+1))=b(j));

@for(need(j)|j#ge#19 #and# j#le#20:z(j)+y(j+1)=b(j));

sx(1)+y(16)=42; sx(2)+y(17)=10; sx(3)+y(19)=190; z(17)+y(18)=130; y(1)+z(15)+z(16)+z(18)+z(21)=0;

@for(supply: @bin(f)); @for(need: @gin(y)); end

习题五

1. 一只狼、一头山羊和一箩卷心菜在河的同侧.一个摆渡人要将它们运过河去，

但由于船小，他一次只能运三者之一过河.显然，不管是狼和山羊，还是山羊和卷心菜，都不能在无人监视的情况下留在一起.问摆渡人应怎样把它们运过河去？ 2. 北京（Pe）、东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa)各城市之间的航线距离如表16.

表16 六城市间的航线距离

L M N Pa Pe T L 56 35 21 51 60 M 56 21 57 78 70 N 35 21 36 68 68 Pa 21 57 36 51 61 Pe 51 78 68 51 13 T 60 70 68 31 13

由上述交通网络的数据确定最小生成树.

3. 某台机器可连续工作4 年，也可于每年末卖掉，换一台新的.已知于各年初购置一台新机器的价格及不同役龄机器年末的的处理价如表17 所示,又新机器第一年运行及维修费为0.3 万元，使用1-3 年后机器每年的运行及维修费用分别为0.8，1.5，2.0 万元.试确定该机器的最优更新策略，使4 年内用于更换、购买及运行维修的总费用为最省.

表 17

j 年初购置价使用了 j 年的机器处理价第一年 2.5 2.0 第二年 2.6 1.6 第三年 2.8 1.3 第四年 3.1 1.1 4. 某产品从仓库运往市场销售.已知各仓库的可供量、各市场需求量及从i 仓库至j 市场的路径的运输能力如表18 所示（表中数字0 代表无路可通），试求从仓库可运往市场的最大流量，各市场需求能否满足？

表 18

产地销地销地 A B 销量 1 2 3 产量 20 30 4 24 22 5 5 20 6 8 7 7. 求图16 所示网络的最小费用最大流，弧旁数字为(cij,uij).

8. 某公司计划推出一种新型产品，需要完成的作业由表20 所示. 表 20

（1）画出产品的计划网络图；

（2）求完成新产品的最短时间，列出各项作业的最早开始时间、最迟开始时间和计划网络的关键路线；

（3）假定公司计划在17 周内推出该产品，各项作业的最短时间和缩短1 周的费用如上表所示，求产品在17 周内上市的最小费用；

（4）如果各项作业的完成时间并不能完全确定，而是根据以往的经验估计出来的，其估计值如表21 所示.试计算出产品在21 周内上市的概率和以95％的概率完成新产品上市所需的周数.

表 21 作业最乐观的估计最可能的估计 A 2 6 B 4 5 C 2 3 D 1 2 E 1 3 F 3 4 G 2 4 H 1 2 最悲观的估计 10 6 4 3 5 5 6 4

9．已知下列网络图有关数据如表22，设间接费用为15 元/天，求最低成本日程. 表 22 工作代号正常时间特急时间

①→② ②→③ ②→④ ③→④ ③→⑤ ④→⑥ ④→⑦ ⑤→⑧ ⑥→⑧ ⑦→⑧ 工时（d） 6 9 3 0 7 8 2 1 4 5 费用（元） 100 200 80 0 150 250 120 100 180 130 工时（d） 4 5 2 0 5 3 1 1 3 2 费用（元） 120 280 110 0 180 375 170 100 200 220

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文