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

实验１、用Lingo求解最短路、最小树问题(1)最短路问题假设有向图有n个顶点。现需要求从顶点V1到顶点Vn的最短路。设决策变量为ijx，当1ijx，说明弧(Vi,Vj)位于顶点V1到顶点Vn的最短路上;否则0ijx，则求V1到Vn的最短路的数学模型为：(P1)EVVxniniixxtsxwjiijnEVVjjinEVVjijEVVijijijjiji),(,0,1,0,11,1..min),(1),(1),(其中E为有向图的所有弧的集合,ijw为弧(Vi,Vj)的权.例题1-1在下图中,用点表示城市,现有A，B1，B2，C1，C2，C3，D共7个城市，点与点之间的连线表示城市间有道路相连，连线旁的数字表示道路的长度。现计划从城市A到称市D铺设一条天然气管道，请设计出最小价格管道铺设方案。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;EVVxniniixxtsxwjiijnEVVjjinEVVjijEVVijijijjiji),(,0,1,0,11,1..min),(1),(1),((2)最小生成树问题设无向图是连通的，且互不包有圈，则称该图为树。如果有向图中任何一点都可由某一个顶点V1到达，则称1V为图G的根。如果有向图G有根。且关于它的基础图是树，则称G为有向树。若'G是包含G的全部顶点的子图，它又是树，则称'G的生成树。若图(,)GVE是一个连通赋权图，T是G的一颗生成树，T的每条边所赋权的和称为树T的权，称具有最小权的生成树为G的最小生成树。v6v3v4v2v5v1例1-2假设某电力公司在7个村庄之间架设电线，各村庄之间的距离如下图所示，试求出使电线总长度最小的架线方案。解：节点1表示树根，点i与j的距离用ijc表示，当两个节点之间没有线路相通时，两点之间的距离用很大的数M表示。引入0-1变量ijx：)(1jixij表示从i到j的边在架设线路中，)(0jixij表示该边不在线路中，则架线方案可以归结为求上述赋权图的最小生成树。数学模型可表示为[5]：111121min1,2,3,...,,1,..0,11,2,3,...,.(2)(1)(3),1,...,,2,...,,nnijijijnijinjjijkkjkjjkzcxxjnijxstuuninuuxnxnxknjnjk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););111121min1,2,3,...,,1,..0,11,2,3,...,.(2)(1)(3),1,...,,2,...,,nnijijijnijinjjijkkjkjjkzcxxjnijxstuuninuuxnxnxknjnjkVariableValueReducedCostN7.0000000.000000U(2)1.0000000.000000U(3)2.0000000.000000U(4)2.0000000.000000U(5)3.0000000.000000U(6)4.0000000.000000U(7)5.0000000.000000X(1,2)1.0000003.000000X(2,3)1.0000003.000000X(2,4)1.0000002.000000X(4,5)1.0000002.000000X(5,6)1.0000001.000000X(6,7)1.0000002.000000从上述求解报告得到最优架设线路为1-2-3，2-4-5-6-7，总长度为13。例题某公司有一台已使用一年的设备,每年年底,公司就要考虑下一年度是购买新设备还是继续使用这台旧设备.若购买新设备,就要支出一笔购置费;若继续使用旧设备,则要支付维修费,而且随着使用年限的延长而增加.已知这种设备每年年初的购置价格,见下表1,而第一年开始使用的有一年役龄的老设备其净值为8,不同使用年限的维修费用见下表2,试制定一个5年内设备的使用或更新计划,使5年内设备的使用维修费和设备购置费的总支出最小(化为最短路问题或建立优化模型求解)年份2345年初价格11121213使用年限0-11-22-33-44-55-6年维修费用23581218注：第一年使用净值为8的老设备(相当于第一年购买费为8)，113812w1653813w17321235w年份2345年初价格11121213使用年限0-11-22-33-44-55-6年维修费用23581218第一年开始使用的有一年役龄的老设备其净值为8,令：v1：表示第一年开始使用的有一年役龄的老设备其净值为8;Vi:第i年初购买一台新设备；(Vi,Vj)表示第I年初购买一新设备一直使用到第j-1年底。Wij表示第I年初的购买费及使用到第j-1年底的维修费之和；问题转化为从v1到v6(第5年底)的最短路。注：第一年使用净值为8的老设备(相当于第一年购买费为8)，EVVxniniixxtsxwjiijnEVVjjinEVVjijEVVijijijjiji),(,0,1,0,11,1..min),(1),(1),(sets:nodes/v1,v2,v3,v4,v5,v6/;lines(nodes,nodes)/v1,v2v1,v3v1,v4v1,v5v1,v6v2,v3v2,v4v2,v5v2,v6v3,v4v3,v5v3,v6v4,v5v4,v6v5,v6/:w,x;endsetsdata:w=111624265413162129141722141715;enddatan=@size(nodes);min=@sum(lines:w*x);@for(nodes(i)|i#ne#1#and#i#ne#n:@sum(lines(i,j):x(i,j))=@sum(lines(j,i):x(j,i)));@sum(lines(i,j)|i#eq#1:x(i,j))=1;@sum(lines(i,j)|j#eq#6:x(i,j))=1;EVVxniniixxtsxwjiijnEVVjjinEVVjijEVVijijijjiji),(,0,1,0,11,1..min),(1),(1),(Globaloptimalsolutionfound.Objectivevalue:38.00000Totalsolveriterations:0VariableValueReducedCostN6.0000000.000000X(V1,V2)0.0000000.000000X(V1,V3)1.0000000.000000X(V3,V6)1.0000000.000000由最终的输出结果知最优方案为：v1-v3-v6，最短路长为38,即第一年使用已有1年役龄的旧设备,一直使用到第3年初购买新设备,然后一直使用到第5年底.5年内设备的维修费用和设备的购买费用最少为38.