实验4Lingo求解最短路最小树问题.ppt

实验1、用Lingo求解最短路、
最小树问题
sets:
cities/A, B1, B2, C1, C2, C3, D/;
roads(cities, cities)/
A,B1 A,B2 B1,C1 B1,C2 B1,C3 B2,C1 B2,C2 B2,C3
C1,D C2,D C3,D/: w, x;
endsets
data:
w = 2 4 3 3 1 2 3 1 1 3 4;
enddata
n=***@size(cities);
min=***@sum(roads: w*x);
***@for(cities(i) | i #ne# 1 #and# i #ne# n:
***@sum(roads(i,j): x(i,j)) = ***@sum(roads(j,i): x(j,i)));
***@sum(roads(i,j)|i #eq# 1 : x(i,j))=1;
v6
v3
v4
v2
v5
v1
例1-2 假设某电力公司在7个村庄之间架设电线,
各村庄之间的距离如下图所示,试求出使电线总长度最小的架线方案。
model:
sets:
city /1..7/:u;
link(city,city):dist,x;
endsets
n=***@size(city);
data:
dist=0 3 4 7 100 100 100
3 0 3 2 4 100 100
4 3 0 100 5 7 100
7 2 100 0 2 100 6
100 4 5 2 0 1 4
100 100 7 100 1 0 2
100 100 100 6 4 2 0;
enddata
min=***@sum(link:dist*x);
u(1)=0;
***@for(link:***@bin(x));
***@for(city(k)|k #GT# 1:***@sum(city(i)|i #ne# k:x(i,k))=1;
***@for(city(j)|j #gt# 1 # and # j #ne# k:u(j)>=u(k)+x(k,j)-(n-2)*(1-x(k,j))+(n-3)*x(j,k);););
***@sum(city(j)|j # GT # 1:x(1,j))>=1;
***@for(city(k)|k #gt# 1:u(k)>=1;u(k)<=n-1-(n-2)*x(1,k););
Variable Value Reduced Cost
N
U( 2)
U( 3)
U( 4)
U( 5)
U( 6)
U( 7)

X( 1, 2)
X( 2, 3)
X( 2, 4)
X( 4, 5)
X( 5, 6)
X( 6, 7)
从上述求解报告得到最优架设线路
为1-2-3,2-4-5-6-7,总长度为13。