资源描述：
《图论与网络流问题的lingo求解技巧》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、图论与网络流问题的LINGO求解技巧我们介绍使用LINGO求解图论与网络问题中的一些典型问题。如最短路问题、最大流问题、关键路径问题、最优树问题，以及TSP问题。这里主要介绍使用LINGO求解的方法，重在应用和解决问题。1最短路问题的Lingo求解设图共有个节点，其赋权图的邻接矩阵为nw.w=p表示节点i到j的权值为p.nn×ij当为有向图时，ww=；当为无向图时，w和w分别由图得到，通常不一样。当w=0，jiijijjiij表示节点i与节点j不连通。令w=0。假设图的所有权值w≥0iiij现求节点a到节点
2、b的最短路，其线性规划模型为：模型一、⎧1节点与节点连通ij决策变量：设x=⎨ij⎩0节点与节点不连通ij目标函数为寻找一条节点到节点的通路，使其上权值和最小，故目标函数为：abnnminZ=∑∑wxij.ijij==111.对节点恰有一条路出去，却不能有路回来，故有：ann∑xaj=1且∑xka=0j=1k=1ja≠ka≠2.对节点恰有一条路到达，却不能有路出去，故有：bnn∑xkb=1且∑xbj=0k=1j=1kb≠jb≠3.对除起始点a和目标点之外，其它点进入和出去的路是一样多（可都为b0），则：nn
3、∑∑xki=≠xiaij,bkj==114.对不通的路不取，约束为：x≤=wi,1j,2,Lnijij总的线性规划模型为：nnminZw=∑∑ij.xijij==11nn⎧⎪∑∑xki=≠xiaij,bkj==11⎪⎪n⎪∑xaj=1⎪j=1ja≠⎪n⎪⎪∑xka=0k=1⎪ka≠⎪n⎪st..⎨∑xkb=1⎪k=1ka≠⎪n⎪⎪∑xbj=0j=1⎪ja≠⎪x≤=wi,1j,2,,Ln⎪ijij⎪x=01或⎪ij⎪⎪⎩示例演示。例1现有11个点的无向图见图14.1，求点1到点11的最短路。图14.1无向图最
4、短路示意图其Lingo实现程序为：!最短路程序;model:sets:point/1..11/;road(point,point):W,X;endsetsdata:W=0,2,8,1,0,0,0,0,0,0,0,2,0,6,0,1,0,0,0,0,0,0,8,6,0,7,5,1,2,0,0,0,0,1,0,7,0,0,0,9,0,0,0,0,0,1,5,0,0,3,0,2,9,0,0,0,0,1,0,3,0,4,0,6,0,0,0,0,2,9,0,4,0,0,3,1,0,0,0,0,0,2,0,0,0,7,
5、0,9,0,0,0,0,9,6,3,7,0,1,2,0,0,0,0,0,0,1,0,1,0,4,0,0,0,0,0,0,0,9,2,4,0;enddatamin=@sum(road(i,j):w(i,j)*x(i,j));!最短路;@for(point(i)
6、i#ne#1#and#i#ne#11:@sum(point(k):x(k,i))=@sum(point(j):x(i,j)));@sum(point(j)
7、j#ne#1:x(1,j))=1;!起始点要出去;@sum(point(k)
8、k#ne#1:x(
9、k,1))=0;!不能回到起始点;@sum(point(k)
10、k#ne#11:x(k,11))=1;!要到达目标点;@sum(point(j)
11、j#ne#11:x(11,j))=0;!目标点不能出去;@for(road(i,j):x(i,j)<=W(i,j));!不能到达的路不考虑;@for(road(i,j):@bin(x(i,j)));end结果为minZ=13x(1,2)=1x(2,5)=1;x(5,6)=1x(6,3)=1x(3,7)=1x(7,10)=1x(10,9)=1x(9,11)=1故路径为
12、1Æ2Æ5Æ6Æ3Æ7Æ10Æ9Æ11模型二:不必考虑起始点不回去，结束点不出去，统一考虑所有中间点不出现圈，添加约束为：uunxn−+≤−.1ijijnnminZw=∑∑ij.xijij==11nn⎧⎪∑∑xxiki=≠ija,bkj==11⎪⎪n⎪∑xaj=1⎪j=1总模型为：ja≠⎪⎪nst..⎨∑x=1kb⎪k=1⎪ka≠⎪uunxn−+≤−.1ij,=1,2,L,n⎪ijij⎪xwij≤=,1,2,,Lnijij⎪⎪x=01或⎩ij上面程序为：!最短路程序;model:sets:point/1..
13、11/:u;road(point,point):W,X;endsetsdata:W=0,2,8,1,0,0,0,0,0,0,0,2,0,6,0,1,0,0,0,0,0,0,8,6,0,7,5,1,2,0,0,0,0,1,0,7,0,0,0,9,0,0,0,0,0,1,5,0,0,3,0,2,9,0,0,0,0,1,0,3,0,4,0,6,0,0,0,0,2,9,0,4,0,0,3,1,0,0,0,0,0,2,0,
