LINGO在图论中的应用

第2章LINGO在图论和网络模型中的应用,图是一种直观形象地描述已知信息的方式，它使事物之间的关系简洁明了，是分析问题的有用工具，很多实际问题可以用图来描述。,一、图的基本概念,图论是以图为研究对象的数学分支，在图论中，图由一些点和点之间的连线所组成称图中的点为顶点（节点），称连接顶点的没有方向的线段为边，称有方向的线段为弧所有线段都没有方向的图称为无向图，所有线段都有方向的图称为有向图，既有边也有弧的图称为混合图点与边相连接称为关联，与边e关联的顶点称为该边的端点，与同一条边关联的两个顶点称为相邻顶点，与同一个顶点关联的边称为相邻边,具有相同顶点的边称为平行边，两个端点重合的边称为环在无向图中，没有环和平行边的图称为简单图，任意一对顶点都有一条边相连的简单图称为完全图任意两个顶点之间有且只有一条弧相连的有向图称为竞赛图在图中，两个顶点u和v之间由顶点和边构成的交错序列（使u和v相通）称为链（通道），没有重复边的通道称为迹，起点与终点重合的通道称为闭通道，不重合的称为开通道，没有重复顶点（必然边也不重复）的开通道称为路，起点与终点重合的路称为圈（回路）如果顶点u和v之间存在通道，称u和v是连通的，任意两个顶点都连通的图称为连通图,无圈的连通图称为树，如果一棵树T包含了图G的所有顶点，称T为G的生成树如果图G的每条边e都对应一个实数C(e)，称C(e)为该边e的权，称图G为赋权图通常称赋权的有向图为网络,二、最短路问题,1.动态规划法(1)问题的描述给定N个点Pi(i=1,2,.,n)组成集合Pi，集合中任一点Pi到另一点Pj的距离用Wij表示，如果Pi到Pj没有弧联结(无通路)，则规定Wij=+，又规定，Wii=0(i=1,2,.,n)，指定一个终点PN，要求从Pi点出发到PN的最短路线。可以用动态规划的方法来求最短路问题，下面举例说明其算法原理。,2.算法原理举例：图中A,B,.,G表示7个城市，连线表示城市之间有道路相通，连线旁的数字表示道路的长度Wij，现要从城市A到G找出一条最短路线。该问题有三个阶段，第一阶段从A到B或C，第二阶段到D,E或F，第三阶段到终点G，我们从终点向前倒过来找。,A,G,F,E,D,C,B,2,4,1,2,3,1,3,3,1,3,4,第三阶段，从D,E,F到G的最短路分别为1,3,4，记为f(D)=1,f(E)=3,f(F)=4；第二阶段，与D,E,F有连线的出发点为B和C，从B出发分别经过D,E,F，至终点G的里程分别为：WBD+f(D)=3+1=4WBE+f(E)=3+3=6WBF+f(F)=1+4=5故B到G的最短路是上述三者的最小值(4)，可以写成f(B)=minWBj+f(j)=4，j是上一步考察过的三个点D,E,F；同理f(C)=minWCj+f(j)，而WCD+f(D)=2+1=3WCE+f(E)=3+3=6WCF+f(F)=1+4=5故F(C)=3；,第一阶段，出发点只有一个A，从A出发分别经过B,C,至终点G的里程分别为：WAB+f(B)=2+4=6WAC+f(C)=4+3=7故A到G的最短路是上述两者的最小值6，可以写成f(A)=minWAj+f(j)=6，j是上一步考察过的两个点B,C，现在已经到了起点，结束运算，从A到G的最短路为6。上述算法可以简写成N是终点，1是起点，j是与i相联,上一步考察过，且与终点相通、f(j)为已知的点。,编写LINGO程序如下：model:sets:cities/A,B,C,D,E,F,G/:FL;!定义7个城市;roads(cities,cities)/A,BA,CB,DB,EB,FC,DC,EC,FD,GE,GF,G/:W,P;!定义哪些城市之间有路相联，W为里程，P用来存放最短路的路径;endsets,data:W=24331231134;enddataN=SIZE(CITIES);FL(N)=0;!终点的F值为0;for(cities(i)|i#lt#N:FL(i)=min(roads(i,j):W(i,j)+FL(j);!递推计算各城市F值;!显然，如果P(i,j)=1,则点i到点n的最短路径的第一步是i-j，否则就不是。由此，我们就可方便的确定出最短路径;for(roads(i,j):P(i,j)=if(FL(i)#eq#W(i,j)+FL(j),1,0);end,部分计算结果：FL(A)6FL(B)4FL(C)3FL(D)1FL(E)3FL(F)4FL(G)0最短路线为ABDG以上计算程序是通用程序，对其它图，只需在此程序基础上对数据作一些修改即可。,程序中的语句roads(cities,cities)/A,BA,CB,DB,EB,FC,DC,EC,FD,GE,GF,G/:W,P;定义的集合称为稀疏集合，本例中cities有7个成员，但是并非每个城市到其它6个城市都有路相通，只有部分城市之间有路，故定义衍生集合roads时用列举法列出有路相通的每对城市。,201规划法用01规划法也能求解最短路问题，其思路如下设起点为1，终点为n引入01型决策变量Xij，如果弧(i,j)在最短路上，则Xij=1，否则Xij=0对于除了起点1和终点n以外的任意一个顶点i，如果，说明从i出发的所有弧中必然有一条弧在最短路上，也就是说最短路经过该顶点，此时所有从其它顶点到达该顶点的弧中必然也有一条弧在最短路上，因而必有：,如果，说明最短路不经过顶点i，故必有两种情况可以合并写成：对于起点1，则必然满足：对于终点n，则必有：,目标函数是最短路上的各条弧的长度之和(总里程)最小，于是最短路问题可以用如下01规划来描述：式中表示全体边的集合。,对于上例，编写LINGO程序如下：model:sets:cities/A,B,C,D,E,F,G/;!定义7个城市;roads(cities,cities)/A,BA,CB,DB,EB,FC,DC,EC,FD,GE,GF,G/:W,X;!定义哪些城市之间有路相联，W为里程，X为01型决策变量;endsetsdata:W=24331231134;enddata,N=SIZE(CITIES);MIN=SUM(roads:W*X);FOR(cities(i)|i#GT#1#AND#i#LT#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;SUM(roads(i,j)|j#EQ#N:X(i,j)=1;end,计算结果与动态规划法相同程序中的最后一个约束方程可以去掉，因为有了前面两个约束条件(共n-1个约束方程)可以导出最后一个约束方程，即终点的约束方程与前面n-1个约束方程线性相关保留该约束方程，LINGO求解时也不会产生任何问题，因为LINGO会自动删除多余的方程该方法与前面的方法相比，灵活性稍差，它一次只能求出指定起点到指定终点的最短路，如果更改起点，则必须改动程序然后重新求解,三、旅行售货商模型,旅行售货商问题(又称货郎担问题，TravelingSalesmanProblem简称TSP模型），是运筹学的一个著名命题。模型：有一个推销商，从某个城市出发，要遍访若干城市各一次且仅一次，最后返回出发城市。已知从城市i到j的旅费为Cij，问他应按怎样的次序访问这些城市，使得总旅费最少？称能到每个城市一次且仅一次的路线为一个巡回(圈)。,TSP是典型的组合优化问题，也是公认的NP完全难题。不算出发地。n个城市有(n-1)!种排列方法，每一种旅行路线是排列中的一种，当n变大时，计算量呈指数增长，穷举法所费时间是难以承受的。为此，多年以来有许多人研究了一些近似算法。我们把TSP问题转化为0-1规划，然后用LINGO来求解。,1.方法一：判断各边是否包含在旅行路线中引入0-1整数变量xij(且ij)：xij=1表示路线从i到j，即边i-j在旅行路线中，而xij0则表示不走i-j路线目标函数首先必须满足约束条件：对每个城市访问一次且仅一次。从城市i出发一次(到其它城市去),表示为,引入0-1整数变量xij(且ij)：xij=1表示路线从i到j，xij0则表示不走i-j路线目标函数首先必须满足约束条件：对每个城市访问一次且仅一次。从城市i出发一次(到其它城市去),表示为从某个城市到达j一次且仅一次，表示为：以上建立的模型类似于指派问题的模型，对TSP问题只是必要条件，并不充分。,例如，用图示路线连接六个城市，满足以上两个约束条件，但这样的路线出现了两个子回路，两者之间不通，不构成整体巡回路线。为此需要考虑增加充分的约束条件以避免产生子巡回。下面介绍一种方法：增加变量ui,i=2,3,n，（它的大小可以取整数：例如从起点出发所达到的城市u=2,依此类推）。,附加约束条件：ui-uj+nxijn-1,i=1,n，j=2,n，且ij。下面证明：(1)任何含子巡回的路线都必然不满足该约束条件（不管ui如何取值）；(2)全部不含子巡回的整体巡回路线都可以满足该约束条件（只要ui取适当值）。用反证法证明(1),假设存在子巡回，则至少有两个子巡回。那么（必然）至少有一个子巡回中不含起点城市1，如上图中的4564，则必有u4-u5+nn-1，u5-u6+nn-1，u6-u4+nn-1，把这三个不等式加起来得到nn-1，不可能，故假设不能成立。而对整体巡回，因为附加约束中j2,不包含起点城市1，故不会发生矛盾。,对于整体巡回路线，只要ui取适当值，都可以满足该约束条件：()对于总巡回上的边，xij=1,ui可取访问城市i的顺序数，则必有ui-uj-1，约束条件ui-uj+nxijn-1变成：-1+nn-1，必然成立。()对于非总巡回上的边，因为xij=0，约束条件ui-uj+nxijn-1变成-1n-1，肯定成立。综上所述，该约束条件只限止子巡回，不影响其它，于是TSP问题转化成了一个混合整数线性规划问题。,TSP问题可以表示为规划：,TSP问题的LINGO模型!旅行售货员问题;model:sets:city/1.6/:u;!定义6个城市;link(city,city):dist,!距离矩阵;x;!决策变量;endsetsn=size(city);,data:!距离矩阵;dist=070245484223961196702032410932136764454324011372180798842109311370161618572396213621801616029001196764798185729000;!这里可改为你要解决的问题的数据;enddata!目标函数;min=sum(link:dist*x);,FOR(city(K):!进入城市K;sum(city(I)|I#ne#K:x(I,K)=1;!离开城市K;sum(city(J)|J#ne#K:x(K,J)=1;);!保证不出现子圈;for(city(I)|I#gt#1:for(city(J)|J#gt#1#and#I#ne#J:u(I)-u(J)+n*x(I,J)=n-1););!限制u的范围以加速模型的求解，保证所加限制并不排除掉TSP问题的最优解;for(city(I):u(I)=n-1);for(link:bin(x);!定义X为01变量;end,计算结果：目标函数值：6610路线：1-3-6-2-5-4-1,2.方法二：对城市排序，找出最优排序在现实中的城市交通图中，有些城市之间有直接道路，有些则没有，如果两点之间没有直接的通路，则两点之间的距离取最短路（经过其它点），即用任意两点之间的最短路Cij作为图的距离矩阵，于是该图可以看成是一个完全图（即任意一对顶点都有一条边相连的图），此时形式上的环形巡回路线实际上个别点有可能不止经过一次。,设某个城市为旅行的出发地和终点（相当于总部所在地），旅行者从该城市出发到其它n个城市各一次且仅一次，最后回到出发地。我们把行进路线分成n步，每一步到一个城市（第n+1步返回出发地），于是一条旅行路线就相当于n个城市的一种排列，n个城市共有n!种排列方式。排序不同则总里程（或费用）可能不同，总里程（或总费用）最小的排序就是我们要寻找的最优路线。,引入0-1型决策变量Xkj，下标k表示旅行的步数，下标j表示到达哪一个城市，Xkj=1表示旅行者第k个目的地（到达点）是城市j，Xkj=0则表示否。用lj表示总部到各城市的距离，用Cij表示城市i与城市j之间的最短路。从出发地到第1个点的路程为从最后一个点返回出发地的里程为,假设在第k步邮车达到城市i，在第k+1步达到支局j，即Xki=Xk+1,j=1，则走过的里程为：CijXkiXk+1,j从第1点到第n点走过的总里程为目标函数为,约束条件有以下2条：(1)每一步到达一个城市，即(2)每一个城市必须到一次且只需一次，即,综上所述，可以把TSP问题转化成如下非线性0-1规划,以上规划种允许包含其它约束条件。用LINGO可以求解该规划，举例如下。某县邮局和10个乡镇支局组成该县的邮政运输网络，已知县局到各支局的距离和支局之间的距离矩阵（数据在程序中）。用一辆邮车完成邮件运输任务，邮车从县局出发到各支局去一次且只需一次，最后回到县局，求总路程最短的行驶路线。,编写LINGO程序如下：MODEL:SETS:CITY/1.10/:JL;STEP/1.10/;LINE(STEP,CITY):X;LINKS(CITY,CITY):C;ENDSETS,DATA:JL=71,56,27,30,28,26,15,9,30,27;C=0,15,44,47,64,83,86,75,93,9815,0,29,32,49,68,71,60,78,8344,29,0,20,37,53,42,31,49,5447,32,20,0,17,36,42,39,60,5764,49,37,17,0,19,37,37,58,5583,68,53,36,19,0,18,35,56,4786,71,42,42,37,18,0,24,38,2975,60,31,39,37,35,24,0,21,2693,78,49,60,58,56,38,21,0,2998,83,54,57,55,47,29,26,29,0;ENDDATA,FOR(LINE:BIN(X);M1=SIZE(STEP);FOR(CITY(I):SUM(STEP(N):X(N,I)=1);FOR(STEP(N):SUM(CITY(I):X(N,I)=1);L1=SUM(CITY(I):(X(1,I)+X(M1,I)*JL(I);LX=SUM(STEP(N)|N#LT#M1:SUM(LINKS(I,J):C(I,J)*X(N,I)*X(N+1,J);MIN=L1+LX;END,在程序运行前需要对LINGO的参数作必要的设置。对于非线性规划，LINGO提供两种求解方法，一种是“GlobalSolver”（称为全局优化求解器），另一种是“MultistartSolver”（称为多起点算法），全局优化求解器优点是确保找到全局最优解，缺点是有时需要较长运行时间。多起点算法的优点是节省运行时间，但不能保证找到的解就是全局最优解，多设置起点数往往找到的解就是全局最优解。点击菜单“Options”，再打开全局优化求解器“GlobalSolver”选项，可以选或不选“GlobalSolver”，当选择多起点算法“MultistartSolver”时，需要设置起点数，若选择“SolverDecides”表示由LINGO决定。,对以上程序，我们选择“GlobalSolver”，点击菜单“Options”，在全局优化求解器“GlobalSolver”选项框内打“”，再点击“确定”。运行以上程序，费时4分多钟，得到最优解：目标函数值（总路程）260公里邮车的行驶路线为：县局89107654123县局,3.多旅行商问题在现实中问题中，有时候不是由一人走遍所有点，而是由几个人分工合作，每个人只到其中部分城市，每个点都有人来过一次且只需一次，事先不指定谁到哪些点，求出使总路程最小的旅行规划（每个人的行走路线）。例如邮路规划中，为了在允许的时间内完成邮件运输任务，县局的邮车往往不止1辆，而是用若干辆邮车分工运输，只要保证每个支局有邮车来过即可，为了节省行驶费用，需要规划几辆邮车的最佳路线。这就是多旅行商问题。,多旅行商问题的提法如下：有n+1个城市，相互间的路程（或旅行费用）为已知，有k个旅行商都从总部所在城市出发，赴其它城市旅行推销，分工遍历其余n个城市，即每个城市各有任意一名旅行商来过一次且仅一次，最后都回到出发地，目标是总路程最短或总费用最省。多旅行商问题在物流配送、邮路优化等方面具有较高的实用价值，而在现实问题中，研究对象往往不是单纯的旅行商问题，而要考虑各种约束条件，例如时间约束、载重量约束等等。研究这一类带约束条件的多旅行商问题具有很强的现实意义。,在现实的多旅行商问题中，往往带有约束条件，例如时间约束、载重量约束等等。带约束条件的多旅行商问题具有广泛现实意义，且是极具挑战性的难题，我们仍然把它转化为0-1非线性规划并编成LINGO程序来求解。实例某县邮政局管辖16个支局，已知县局到各支局的距离以及16个支局之间的距离矩阵。寄达各支局和各支局收寄的邮件(袋)如下表所示：,县邮局和各支局分布图,每一辆邮车最多装载65袋邮件，邮车的运行成本为3元/公里。试用最少邮车，并规划邮车的行驶路线使总费用最省。分析：首先考虑最少邮车数量，由题目所给表中数据，寄达16个支局的邮件总数为176袋，从各支局收寄的邮件总数为170袋，每一辆邮车最多容纳65袋邮件，至少需要176/652.7辆邮车，由于邮车数量为整数，故最少需要3辆邮车。如果3辆邮车能够完成邮件运输任务，则3辆车就是邮车数量的最优解。,运输费用与行驶里程成正比，总里程最短对应总费用最省。把16个支局放在一起作为一个整体考虑，找出3条邮路，每条邮路都从县局出发，到若干支局进行卸装，最后回到县局。各邮车路过的支局数量未知，合理安排各邮车的行驶路线，由3辆邮车分别承包运输，在满足运载量约束前提下，把3条巡回路线的总里程最小作为优化的目标。该问题相当于附带约束条件的多旅行商模型。,引入0-1型决策变量Xkj,Ykj,Zkj，分别表示3辆邮车第k步到达支局j，下标k表示邮车行走的步数，下标j表示到达哪一个支局，当决策变量Xkj,Ykj,Zkj等于1时分别表示某邮车第k个装卸点是支局j，等于0时表示否。设各邮车管辖的支局数量分别为m1,m2,m3，则m1+m2+m3=16。约束条件有以下3条：(1)任何一辆车在任何一步到达一个支局，即,(2)任何一个支局必须有一辆邮车到达一次且只需要一次，即(3)在邮车行进的任何路段上，装载的邮件不超过65袋。设寄达各支局的邮件量为Pj，各支局收寄的邮件量为Qj。装载量是动态变化的，以第1辆邮车为例，出发时的装载量为,到第1个支局卸装以后，装载量变为在行驶过程中，装载量的递推公式为约束条件为,综上所述，建立多旅行商问题的0-1规划模型如下：,装载量的计算公式为：,编写LINGO程序如下：MODEL:SETS:STATION/1.16/:JL,P,Q;STEPX/1.6/:WX;STEPY/1.5/:WY;STEPZ/1.5/:WZ;LINEX(STEPX,STATION):X;LINEY(STEPY,STATION):Y;LINEZ(STEPZ,STATION):Z;LINKS(STATION,STATION):C;ENDSETS,DATA:JL=27361711243144403020252121182736;P=10,15,6,9,13,6,11,4,13,17,11,2,11,21,13,14;Q=9,14,5,10,9,10,13,9,15,9,6,7,13,15,10,16;C=0312738515871675747524821415261310193327324564534761575248566327190142734474939294238382938443833140132033352515333232152430512727130921372626434545282938583234209013323235475252353342714547332113019303950656548444067644935373219011203154613425215753392526323011010204351241413474729152635392010018364114918,526142334347503120180234625142348573832455265544336230272233422152383245526561514146270394857414829152835483424142522390112052563824293344251491433481109616344303842402113182342572090;ENDDATA,FOR(LINEX:BIN(X);FOR(LINEY:BIN(Y);FOR(LINEZ:BIN(Z);M1=SIZE(STEPX);M2=SIZE(STEPY);M3=SIZE(STEPZ);FOR(STATION(I):SUM(STEPX(N):X(N,I)+SUM(STEPY(N):Y(N,I)+SUM(STEPZ(N):Z(N,I)=1);FOR(STEPX(N):SUM(STATION(I):X(N,I)=1);FOR(STEPY(N):SUM(STATION(I):Y(N,I)=1);FOR(STEPZ(N):SUM(STATION(I):Z(N,I)=1);,WX0=SUM(STATION(I):P*SUM(STEPX(N):X(N,I);WY0=SUM(STATION(I):P*SUM(STEPY(N):Y(N,I);WZ0=SUM(STATION(I):P*SUM(STEPZ(N):Z(N,I);WX(1)=WX0-SUM(STATION(J):(P(J)-Q(J)*X(1,J);WY(1)=WY0-SUM(STATION(J):(P(J)-Q(J)*Y(1,J);WZ(1)=WZ0-SUM(STATION(J):(P(J)-Q(J)*Z(1,J);FOR(STEPX(N)|N#GE#2:WX(N)=WX(N-1)-SUM(STATION(J):(P(J)-Q(J)*X(N,J);FOR(STEPY(N)|N#GE#2:WY(N)=WY(N-1)-SUM(STATION(J):(P(J)-Q(J)*Y(N,J);FOR(STEPZ(N)|N#GE#2:WZ(N)=WZ(N-1)-SUM(STATION(J):(P(J)-Q(J)*Z(N,J);WX0=65;WY0=65;WZ0=65;FOR(STEPX(N):WX(N)=65);FOR(STEPY(N):WY(N)=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););end,计算结果：目标函数值(最优连线的长度)为13，最优连线的构成如图所示,五、最大流问题,1问题的描述设有一批物资，要从A市通过公路网络（内含一些中转站）运往B市，已知每段公路的运输能力有限制（流量限制），问应如何安排运输方案，才能使总运量最大？这就是网络最大流问题例：下图是从发货地到目的地的有向运输网络，称点为发点（源），点为收点（汇），有向边（弧）旁边的数字是该弧的流量（运输能力）限制，求的最大流,2、数学模型,对每一条弧(顶点i到j)，定义f(i,j)为该弧上从顶点i到顶点j的流量，用Cij表示其上的流量限制则对任意一个中转点，流进与流出相等，但顶点只有流出，顶点只有流进，并且两者大小相等(方向相反)，如果我们在图上虚拟一条从的弧，其流量不受限制，并假设从流到的总量又从该虚拟弧上返回，整个网络系统构成一个封闭的不停流动的回路，则对任意顶点都满足流进等于流出,目标函数是maxf(n,1)，n是收点，1是发点.约束条件有两条：(1)对每个顶点，流进等于流出，即等式左边的求和是对所