资源描述：
《图与网络优化模型》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第十章图与网络优化模型在图论中通常用V表示点，E表示边（无向），A表示弧（有向），G表示图，点和边构成的图称为无向图，G=（V，E），点和弧构成的图称为有向图,G=(V,A)。对图G的边（或弧）标上权数，称为赋权图。10．1最短路问题求1到7的最短路。本图是个有向图，弧上的数字不妨理解为距离。目前用于求解最短路的算法有多种，如：动态规划法，Dijkstra算法，0-1规划方法等。下面只介绍0-1规划法设1为起点，7为终点。引入表示：若弧(i,j)在最短路上,,否则，Z为目标函数上各弧的路程之和。起点1必定有一条弧出发,所以终点n必定有一条弧到达,所以其它点有两种情况：
2、(1)该点不在最短路上，即无进线弧，也无出线弧。满足：，且(2)该点在最短路上，即有进线弧，也有出线弧。满足：，且改写上述两个等式为：model:sets:city/1..7/;!定义7个城市;links(city,city):dist,x;!定义各城市之间的距离表(若城市i到城市j无路,用一个大数表示),决策变量;endsetsdata:dist=021010001000100010001000073100010001000100010000100041000100010001000100001000100081000100051000037100010001000
3、100010000121000100010004100030;enddatan=@size(city);min=@sum(links:dist*x);@sum(city(i):x(1,i))=1;@sum(city(i):x(i,n))=1;@for(city(i)
4、i#gt#1#and#i#lt#n:@sum(city(j):x(i,j))=@sum(city(j):x(j,i)));@for(city(i):x(i,i)=0);@for(links:@bin(x));end10.2旅行售货员TSP模型有一个旅行推销员，从某个城市出发，要遍访若干城市各一次且仅一次，
5、最后返回原来出发城市。已知从城市I到城市J的旅费为，问如何安排旅行路线使总旅费最小？分析：巡回---能到每个城市一次，且仅一次的一条线路称为一个巡回。子巡回---从一个起点出发,到若干(不是全部)城市一次,且仅一次,又回到起点的一条线路称为一个子巡回.定理1:含有一个子巡回,必定至少有两个子巡回.定理2:TSP模型的一条最优巡回,必定不含子巡回.证明:如果含有子巡回,则必存在一个子巡回有这种情况:有一个城市要经过二次,才能回到起点城市.如何用数学表达式来描述子巡回与总体巡回的区别呢?显然,有子巡回的线路必然有一个城市(这个城市却不是起点城市)要经过二次,而不含子巡回的
6、线路只有起点城市才经过二次.假设有一条线路:没有子巡回的情形:有子巡回的情形:引入变量,对上述线路上的各城市按序给予编号,,每个城市只编一次号.没有子巡回的情形:-1,-1,-1,...,-1,-1有子巡回的情形:-1,-1,-1,...,m,...,-1,-1m不等于-1.定理3:设表示是否从城市I到城市J,约束条件:则:(1)任何含有子巡回的路线必然不满足上述约束条件(不管如何取值)(2)不含子巡回的线路都可以满足上述约束条件.(只要取适当值)TSP模型如下:具体例子:已知六个城市之间的路程如下表:ABCDEFA070245423961196842B0324109
7、32136764C011372180798D016161857E02900F0求一条TSP线路?model:sets:CITY/1..6/:u;!定义六个城市,u是TSP线路的编号;LINKS(CITY,CITY):dist,x;!dist距离列表,x为决策变量;endsetsdata:!u=0,1,2,3,4,5;dist=070245484223961196702032410932136764454324011372180798842109311370161618572396213621801616029001196764798185729000;enddatan
8、=@size(city);Min=@sum(links:dist*x);@for(links:@bin(x));!x为0-1变量;@for(city(i):@sum(city(j)
9、i#ne#j:x(i,j))=1);@for(city(i):@sum(city(j)
10、i#ne#j:x(j,i))=1);@for(city(i):@for(city(j)
11、j#GT#1#and#i#ne#j:u(I)-U(j)+n*x(i,j)<=n-1););@for(city(i):u(i)<=n-1);end10.3最小生成树和最优连线(minimalspann
