图论与网络流问题的LINGO求解技巧

图论与网络流问题的LINGO求解技巧我们介绍使用LINGO求解图论与网络问题中的一些典型问题。如最短路问题、最大流问题、关键路径问题、最优树问题，以及TSP问题。这里主要介绍使用LINGO求解的方法，重在应用和解决问题。1最短路问题的Lingo求解设图共有个节点，其赋权图的邻接矩阵为nnnw×.ijwp=表示节点i到j的权值为.当为有向图时，pjiwwij=；当为无向图时，和ijwjiw分别由图得到，通常不一样。当，表示节点i与节点0ijw=j不连通。令0iiw=。假设图的所有权值0ijw≥现求节点a到节点b的最短路，其线性规划模型为：模型一、决策变量：设10ijijxij⎧=⎨⎩节点与节点连通节点与节点不连通目标函数为寻找一条节点到节点的通路，使其上权值和最小，故目标函数为：ab11min.nnijijijZwx===∑∑1.对节点恰有一条路出去，却不能有路回来，故有：a11najjjax=≠=∑且10nkakkax=≠=∑2.对节点恰有一条路到达，却不能有路出去，故有：b11nkbkkbx=≠=∑且10nbjjjbx=≠=∑3.对除起始点a和目标点之外，其它点进入和出去的路是一样多（可都为0），则：b11,nnkiijkjxxia===≠∑∑b4.对不通的路不取，约束为：,1,2,ijijxwij≤=Ln总的线性规划模型为：11111111min.,10..10,1,2,,01nnijijijnnkiijkjnajjjankakkankbkkanbjjjaijijijZwxxxiabxxstxxxwijx=====≠=≠=≠=≠=⎧=≠⎪⎪⎪=⎪⎪⎪⎪=⎪⎪⎪⎪=⎨⎪⎪⎪=⎪⎪⎪≤=⎪⎪=⎪⎪⎪⎩∑∑∑∑∑∑∑∑L或n示例演示。例1现有11个点的无向图见图14.1，求点1到点11的最短路。图14.1无向图最短路示意图其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,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)|i#ne#1#and#i#ne#11:@sum(point(k):x(k,i))=@sum(point(j):x(i,j)));@sum(point(j)|j#ne#1:x(1,j))=1;!起始点要出去;@sum(point(k)|k#ne#1:x(k,1))=0;!不能回到起始点;@sum(point(k)|k#ne#11:x(k,11))=1;!要到达目标点;@sum(point(j)|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故路径为1Æ2Æ5Æ6Æ3Æ7Æ10Æ9Æ11模型二:不必考虑起始点不回去，结束点不出去，统一考虑所有中间点不出现圈，添加约束为：.1ijijuunxn−+≤−总模型为：111111min.,1..1.1,1,2,,1,2,,01nnijijijnnkiijkjnajjjankbkkaijijijijijZwxxxiabxstxuunxnijnxwijnx=====≠=≠=⎧=≠⎪⎪⎪=⎪⎪⎪⎪⎨=⎪⎪⎪−+≤−=⎪⎪≤=⎪=⎪⎩∑∑∑∑∑∑LL或,上面程序为：!最短路程序;model:sets:point/1..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,0,0,7,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));!最短路;n=@size(point);@for(point(i)|i#ne#1#and#i#ne#11:@sum(point(k):x(k,i))=@sum(point(j):x(i,j)));@sum(point(j)|j#ne#1:x(1,j))=1;!起始点要出去;@sum(point(k)|k#ne#11:x(k,11))=1;!要到达目标点;@for(road(i,j):u(i)-u(j)+n*x(i,j)=n-1);!不出现圈;@for(road(i,j):x(i,j)=W(i,j));!不能到达的路不考虑;@for(road(i,j):@bin(x(i,j)));end2最大流问题的Lingo求解设有向图共有个节点，其赋权图的容量矩阵为nnnC×.表示节点i到ijcj的允许的最大容量。现求根节点1到节点n的最大流量。其线性规划模型为：决策变量：设ijf表示节点i到节点j的实际流量。目标函数为：maxZflow=1.从节点1流出的就是流量，故有：12njjflowf==∑2.对终点流入的也是流量，故有：11niniflowf−==∑3．中间所有点满足流入与流出相等，约束为：112,3,,1nnkiijkjffin====∑∑L−4．每个节点上的流量不超过容量,,1,2,,ijijfcij≤=Ln总的线性规划模型为：121111max..2,3,,1,,1,2,,njjnininnkiijkjijijZflowflowfflowfstffinfcijn=−====⎧=⎪⎪⎪=⎪⎨⎪⎪==⎪⎪≤=⎩∑∑∑∑LL−示例演示。例2有6个点的有向图见图14.2，求起始点1到终点6的最大流量。图14.2有向图初始网络其Lingo实现程序为：!最大流问题;model:sets:point/1..6/;link(point,point):C,f;endsetsdata:C=0,8,7,0,0,0,0,0,5,9,0,0,0,0,0,0,9,0,0,0,2,0,0,5,0,0,0,6,0,10,0,0,0,0,0,0;enddatamax=flow;n=@size(point);flow=@sum(point(j):f(1,j));!流量为从起始点流出的量;gui=@sum(point(i):f(i,n));!流入终点的量;gui=flow;!中间各点流入与流出的量相等;@for(point(i)|i#ne#1#and#i#ne#n:@sum(point(j):f(i,j))=@sum(point(k):f(k,i)));@for(link(i,j):f(i,j)=c(i,j));end结果为maxZ=14F(1,2)=7F(1,3)=7F(2,3)=2F(2,4)=5F(3,5)=9F(4,6）=5F(5,6）=9结果见图14.3。图14.3计算结果图3关键路线(CPM)问题的Lingo求解计划评审方法(PERT)和关键路线法(CPM)是网络分析的重要部分，在中国又称为统筹方法(schedulemethof)。这里采用最短路的思想利用Lingo求解关键路线。以获得最少完成时间。设有项作业等待完成。作业号分别为1,。每项作业需要完成的时间为。第i项作业的紧前作业有。设虚拟的开始作业为，结束作业为。号作业完成时间为0。无紧前作业的作业号的紧前作业为，结束作业的紧前作业为其后无作业的作业号。n2,,nL(1,2,,itin=L)12,,,ikkkL1n+2n+1n+1n+2n+该图共有个节点，其赋权图的邻接矩阵为2n+(2)(2)nnw+×+.ijiwt=表示作业i完成的时间为。当，表示作业i与作业it0ijw=j无依赖关系。求完成作业的最少时间，就是求从起始点到结束点的最长路，其线性规划模型为：1n+2n+决策变量：设10ijijxij⎧=⎨⎩作业与作业紧连作业与作业不紧连目标函数为寻找一条从起始点到结束点1n+2n+的最长路，使其上权值和最大，故目标函数为：2211max.nnijijijZwx++===∑∑1.对起始点恰有一条路出去，故有：1n+21,111nnjjjnx++=≠+=∑2.对终点恰有一条路到达，故有：2n+2,2121nknkknx++=≠+=∑3.对除起始点1n+和终点之外，其它点进入和出去的路是一样多（可都为0），则：2n+22111,2nnkiijkjxxinn++===≠+∑∑+4.所有中间点不出现圈，添加约束为：.1ijijuunxn−+≤−总模型为：2211221121,112,212min.1,21..1.1,1,2,,,1,201nnijijijnnkiijkjnnjjjnnknkknijijijZwxxxinnxstxuunxnijnnnx++==++==++=≠+++=≠+=⎧=≠++⎪⎪⎪=⎪⎪⎪⎪=⎨⎪⎪−+≤−=++⎪⎪=⎪⎪⎪⎩∑∑∑∑∑∑L或例31991年上海市大学生数学建模竞赛B题第一问：现有14件工件等待在一台机床上加工，某些工件的加工顺序必须安排在另外一些工件完工以后才能开始，第j号工件的加工时间jt及先期必须完工的工件号i由表1给出：表14.4工件加工时间与次序表工件号1234567891011121314jt2028251642123210242040243616前期工件号3,45,7,85,9--10,113,8,943,5,74--4,76,7,145,121,2,6(1)给出一个加工顺序，则确定了每个工件的完工时间（包括等待与加工两个阶段）。试设计一个满足条件的加工顺序，使各个工件的完工时间之和最小。解：这里我们只求出最少完成时间。设开始作业为15,结束作业为16.模型建立与上面相同。Lingo程序为：!关键路线法;model:sets:job/1..16/:u;!初始点定义为15,终点定义为16;line(job,job)/3,14,15,27,28,25,39,315,410,511,53,68,69,64,73,85,87,84,915,104,117,116,127,1214,125,1312,131,142,146,1413,16/:x,t;endsetsdata:t=25,16,42,32,10,42,24,0,20,40,25,10,24,16,25,42,32,16,0,16,32,12,32,16,42,24,20,28,12,36;enddatamax=@sum(line(i,j):x(i,j)*t(i,j));!求最长路线;@sum(line(i,j)|i#eq#15:x(i,j))=1;!初始点一定出去;@sum(line(i,j)|j#eq#16:x(i,j))=1;!终点一定到达;!开始点和终点除外;@for(job(i)|i#ne#15#and#i#ne#16:@sum(line(i,j):x(i,j))=@sum(line(k,i):x(k,i)));n=@si