Lingo超经典案例大全 三（每日一资料）

百年孤独

四、路径最短问题：

如上图，求从S到T的最短路径。设d(x,y):城市x与城市y之间的直线距离;L(x):城市S到城市x的最优行驶路线的路长。模型为：
min {L(x)+d(x,y)}
L(S)=0

model:
sets:
city/S,A1,A2,A3,B1,B2,C1,C2,T/;
road(city,city)/S,A1 S,A2 S,A3 A1,B1 A1,B2 A2,B1 A2,B2 A3,B1 A3,B2 B1,C1 B1,C2 B2,C1 B2,C2 C1,T C2,T/:d;
endsets
data:
d=6 3 3
6 5 8 6 7 4
6 7 8 9
5 6;
L=0,6,3,3,,,,,;
enddata
@for(city(j)|j#gt#@index(city,S)(j)=@min(road(i,j)(i)+d(i,j)));
end
求得最短路径为20.

五、指派问题(0-1规划问题）：

四个人完成4项任务所用的时间如下，问如何指派任务使得完成所有任务的时间最短？
        任务   t1    t2    t3    t4
人员
m1              2     15    13    4

m2             10     4    14    15   

m3             9      14    16    13

m4             7      8     11     9

c_ij:表示第i个人完成第j项任务所用的时间；
决策变量x_ij:若第i个人选择第j项任务则x_ij=1;否则，x_ij=0；
模型为：

model:
sets:
task/1..4/:t;
man/1..4/:m;
link(man,task):c,x;
endsets
data:
c=2 15 13 4
10 4 14 15
9 14 16 13
7 8 11 9;
enddata
[obj]min=@sum(link:c*x);
@for(task(j)sum(man(i):x(i,j))=1);
@for(man(i)sum(task(j):x(i,j))=1);
@for(linkbin(x));
end
求得：最优指派为：m1--t4,m2--t2,m3--t1,m4--t3
最优值为:28。