实验 Lingo求解最短路最小树问题经典课件.ppt

实验4Lingo求解最短路最小树问题sets:cities/A,B1,B2,C1,C2,C3,D/;roads(cities,cities)/A,B1A,B2B1,C1B1,C2B1,C3B2,C1B2,C2B2,C3C1,DC2,DC3,D/:w,x;endsetsdata:w=24331231134;enddatan=***@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;v6v3v4v2v5v1例1-2假设某电力公司在7个村庄之间架设电线,各村庄之间的距离如下图所示,试求出使电线总长度最小的架线方案。model:sets:city/1..7/:u;link(city,city):dist,x;endsetsn=***@size(city);data:dist=034710010010030324100100430100571007210002100610045201410010071001021001001006420;enddatamin=***@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););(2)(3)(4)(5)(6)(7)(1,2)(2,3)(2,4)(4,5)(5,6)(6,7)-2-3,2-4-5-6-7,总长度为13。