LINGO在图论中的应用.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,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,个点,P,i,(,i,=1,2,.,n,),组成集合,P,i,，集合中任一点,P,i,到另一点,P,j,的距离用,W,ij,表示，如果,P,i,到,P,j,没有弧联结,(,无通路,),，,则规定,W,ij,=+,，又规定，,W,ii,=0(i=1,2,.,n,),，,指定一个终点,P,N,，,要求从,P,i,点出发到,P,N,的最短路线,。,可以用,动态规划,的,方法来,求最短路问题，下面举例说明其算法原理,。,2.,算法原理,举例：,图,中,A,B,.,G,表示,7,个城市，连线表示城市之间有道路相通，连线旁的数字表示道路的长度,W,ij,，,现要从城市,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,的里程分别为：,W,BD,+,f,(D)=3+1=4,W,BE,+,f,(E)=3+3=6,W,BF,+,f,(F)=1+4=5,故,B,到,G,的最短路是上述三者的最小值,(4),，可以写成,f,(B)=,minW,Bj,+f(j,)=4,，,j,是上一步考察过的三个点,D,E,F,；,同理,f(C)=,minW,Cj,+,f,(j,),，,而,W,CD,+,f,(D)=2+1=3,W,CE,+,f,(E)=3+3=6,W,CF,+,f,(F)=1+4=5,故,F(C)=3,；,第一阶段，出发点只有一个,A,，从,A,出发分别经过,B,C,至终点,G,的里程分别为：,W,AB,+,f,(B)=2+4=6,W,AC,+,f,(C)=4+3=7,故,A,到,G,的最短路是上述两者的最小值,6,，可以写成,f,(A)=,minW,Aj,+,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,B A,C,B,D B,E B,F,C,D C,E C,F,D,G,E,G,F,G/:W,P;,!,定义哪些城市之间有路相联，,W,为里程，,P,用来存放最短路的路径,;,endsets,data:,W=2 4 3 3 1 2 3 1 1 3 4;,enddata,N=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)6,FL(B)4,FL(C)3,FL(D)1,FL(E)3,FL(F)4,FL(G)0,最短路线为,A B D G,以上计算程序是通用程序，对其它图，只需在此程序基础上对数据作一些修改即可。,程序中的语句,roads(cities,cities,)/A,B A,C B,D B,E B,F C,D C,E C,F D,G E,G F,G/:W,P;,定义的集合称为稀疏集合，本例中,cities,有,7,个成员，但是并非每个城市到其它,6,个城市都有路相通，只有部分城市之间有路，故定义衍生集合,roads,时用列举法列出有路相通的每对城市,。,2,0,1,规划法,用,0,1,规划法也能求解最短路问题，其思路如下,设起点为,1,，终点为,n,引入,0,1,型决策变量,X,ij,，如果弧,(,i,j,),在最短路上，则,X,ij,=1,，否则,X,ij,=0,对于除了起点,1,和终点,n,以外的任意一个顶点,i,，如果，说明从,i,出发的所有弧中必然有一条弧在最短路上，也就是说最短路经过该顶点，此时所有从其它顶点到达该顶点的弧中必然也有一条弧在最短路上，因而必有：,如果 ，说明最短路不经过顶点,i,，故必有,两种情况可以合并写成：,对于起点,1,，则必然满足：,对于终点,n,，则必有：,目标函数是最短路上的各条弧的长度之和,(,总里程,),最小，于是最短路问题可以用如下,0,1,规划来描述：,式中 表示全体边的集合,。,对于上例，编写,LINGO,程序如下：,model:,sets:,cities/A,B,C,D,E,F,G/;!,定义,7,个城市,;,roads(cities,cities,)/,A,B A,C B,D B,E B,F C,D C,E C,F,D,G E,G F,G/:W,X;,!,定义哪些城市之间有路相联，,W,为里程，,X,为,0,1,型决策变量,;,endsets,data:,W=2 4 3 3 1 2 3 1 1 3 4;,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,会自动删除多余的方程,该方法与前面的方法相比，灵活性稍差，它一次只能求出指定起点到指定终点的最短路，如果更改起点，则必须改动程序然后重新求解,三、旅行售货商模型,旅行售货商问题,(,又称货郎担问题，,Traveling Salesman Problem,简称,TSP,模型），是运筹学的一个著名命题。,模型：,有一个推销商，从某个城市出发，要遍访若干城市各一次且仅一次，最后返回出发城市。已知从城市,i,到,j,的旅费为,C,ij,，,问他应按怎样的次序访问这些城市，使得总旅费最少？,称能到每个城市一次且仅一次的路线为一个巡回,(,圈,),。,TSP,是典型的组合优化问题，也是公认的,NP,完全难题。,不算出发地。,n,个城市有,(n-1)!,种排列方法，每一种旅行路线是排列中的一种，当,n,变大时，计算量呈指数增长，穷举法所费时间是难以承受的。,为此，多年以来有许多人研究了一些近似算法。,我们把,TSP,问题转化为,0-1,规划，然后用,LINGO,来求解。,1.,方法一：判断各边是否包含在旅行路线中,引入,0-1,整数变量,x,ij,(,且,i,j,),：,x,ij,=1,表示路线从,i,到,j,，即边,i-j,在旅行路线中，而,x,ij,0,则表示不走,i-j,路线,目标函数,首先必须满足约束条件：对每个城市访问一次且仅一次。从城市,i,出发一次,(,到其它城市去,),表示为,引入,0-1,整数变量,x,ij,(,且,i,j,),：,x,ij,=1,表示路线从,i,到,j,，,x,ij,0,则表示不走,i-j,路线,目标函数,首先必须满足约束条件：对每个城市访问一次且仅一次。从城市,i,出发一次,(,到其它城市去,),表示为,从某个城市到达,j,一次且仅一次，表示为：,以上建立的模型类似于指派问题的模型，对,TSP,问题只是必要条件，并不充分。,例如，用图示路线连接六个城市，满足以上两个约束条件，但这样的路线出现了两个子回路，两者之间不通，不构成整体巡回路线。,为此需要考虑增加,充分的约束条件以避免产生子巡回。,下面介绍一种方法：,增加变量,u,i,i,=2,3,n,，（,它的大小可以取整数：例如从起点出发所达到的城市,u=2,依此类推）。,3,1,2,4,5,6,附加约束条件：,u,i,-,u,j,+,nx,ij,n,-1,i,=1,n,，,j,=2,n,，,且,i,j,。,下面,证明：,(1),任何含子巡回的路线都,必然,不满足该约束条件,（不管,u,i,如何取值）,；,(2),全部,不含子巡回的整体,巡回,路线,都,可以,满足该约束条件,（只要,u,i,取适当值）,。,用反证法证明,(1),假设存在子巡回，则至少有两个子巡回。那么（必然）至少有一个子巡回中不含起点城市,1,，如上图中的,4,5,6,4,，则必有,u,4,-u,5,+n,n-1,，,u,5,-u,6,+n,n-1,，,u,6,-u,4,+n,n-1,，,把这三个不等式加起来得到,n,n-1,，不可能，故假设不能成立。而对整体,巡回,，因为附加约束中,j,2,不包含起点城市,1,，故不会发生矛盾。,对于整体,巡回,路线，只要,u,i,取适当值，,都,可以,满足该约束条件,：,(),对于,总巡回上的边,，,x,ij,=1,u,i,可取访问城市,i,的顺序数，,则必有,u,i,-u,j,-1,，,约束条件,u,i,-u,j,+nx,ij,n-1,变成：,-1+n n-1,，,必然成立。,(),对于,非总巡回上的边,，因为,x,ij,=0,，,约束条件,u,i,-u,j,+nx,ij,n-1,变成,-1,n-1,，,肯定成立。,综上所述，该约束条件只限止子巡回，不影响其它，于是,TSP,问题,转化成了一个混合整数线性规划问题,。,TSP,问题可以表示为规划：,TSP,问题的,LINGO,模型,!,旅行售货员问题,;,model:,sets:,city/1.6/:u;!,定义,6,个城市,;,link(city,city):,dist,!,距离矩阵,;,x;!,决策变量,;,endsets,n=size(city);,data:!,距离矩阵,;,dist=0 702 454 842 2396 1196,702 0 324 1093 2136 764,454 324 0 1137 2180 798,842 1093 1137 0 1616 1857,2396 2136 2180 1616 0 2900,1196 764 798 1857 2900 0;,!,这里可改为你要解决的问题的数据,;,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.,方法二：对城市排序，找出最优排序,在现实中的城市交通图中，有些城市之间有直接道路，有些则没有，如果两点之间没有直接的通路，则两点之间的距离取最短路（经过其它点），即用任意两点之间的最短路,C,ij,作为图的距离矩阵，于是该图可以看成是一个完全图（即任意一对顶点都有一条边相连的图），此时形式上的环形巡回路线实际上个别点有可能不止经过一次。,设某个城市为旅行的出发地和终点（相当于总部所在地），旅行者从该城市出发到其它,n,个城市各一次且仅一次，最后回到出发地。我们把行进路线分成,n,步，每一步到一个城市（第,n+1,步返回出发地），于是一条旅行路线就相当于,n,个城市的一种排列，,n,个城市共有,n!,种排列方式。排序不同则总里程（或费用）可能不同，总里程（或总费用）最小的排序就是我们要寻找的最优路线。,引入,0-1,型决策变量,X,kj,，下标,k,表示旅行的步数，下标,j,表示到达哪一个城市，,X,kj,=1,表示旅行者第,k,个目的地（到达点）是城市,j,，,X,kj,=0,则表示否。用,l,j,表示总部到各城市的距离，用,C,ij,表示城市,i,与城市,j,之间的最短路。,从出发地到第,1,个点的路程为,从最后一个点返回出发地的里程为,假设在第,k,步邮车达到城市,i,，在第,k,+1,步达到支局,j,，即,X,ki,=X,k,+1,j,=1,，则走过的里程为：,C,ij,X,ki,X,k,+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,98,15,0,29,32,49,68,71,60,78,83,44,29,0,20,37,53,42,31,49,54,47,32,20,0,17,36,42,39,60,57,64,49,37,17,0,19,37,37,58,55,83,68,53,36,19,0,18,35,56,47,86,71,42,42,37,18,0,24,38,29,75,60,31,39,37,35,24,0,21,26,93,78,49,60,58,56,38,21,0,29,98,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,提供两种求解方法，一种是“,Global Solver”,（称为全局优化求解器），另一种是“,Multistart,Solver”,（称为多起点算法），全局优化求解器优点是确保找到全局最优解，缺点是有时需要较长运行时间。多起点算法的优点是节省运行时间，但不能保证找到的解就是全局最优解，多设置起点数往往找到的解就是全局最优解。,点击菜单“,Options”,，再打开全局优化求解器“,Global Solver”,选项，可以选或不选“,Global Solver”,，当选择多起点算法“,Multistart,Solver”,时，需要设置起点数，若选择“,Solver Decides”,表示由,LINGO,决定。,对以上程序，我们选择“,Global Solver”,，点击菜单“,Options”,，在全局优化求解器“,Global Solver”,选项框内打“,”，再点击“确定”。,运行以上程序，费时,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,型决策变量,X,kj,Y,kj,Z,kj,，分别表示,3,辆邮车第,k,步到达支局,j,，下标,k,表示邮车行走的步数，下标,j,表示到达哪一个支局，当决策变量,X,kj,Y,kj,Z,kj,等于,1,时分别表示某邮车第,k,个装卸点是支局,j,，等于,0,时表示否。设各邮车管辖的支局数量分别为,m,1,m,2,m,3,，,则,m,1,+,m,2,+,m,3,=16,。,约束条件有以下,3,条：,(1),任何一辆车在任何一步到达一个支局,，即,(2),任何一个支局必须有一辆邮车到达一次且只需要一次，即,(3),在邮车行进的任何路段上，装载的邮件不超过,65,袋。,设寄达各支局的邮件量为,P,j,，各支局收寄的邮件量为,Q,j,。,装载量是动态变化的，以第,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=27 36 17 11 24 31 44 40 30 20 25 21,21,18 27 36;,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=0 31 27 38 51 58 71 67 57 47 52 48 21 41 52 61,31 0 19 33 27 32 45 64 53 47 61 57 52 48 56 63,27 19 0 14 27 34 47 49 39 29 42 38,38,29 38 44,38 33 14 0 13 20 33 35 25 15 33 32,32,15 24 30,51 27,27,13 0 9 21 37 26,26,43 45,45,28 29 38,58 32 34 20 9 0 13 32,32,35 47 52,52,35 33 42,71 45 47 33 21 13 0 19 30 39 50 65,65,48 44 40,67 64 49 35 37 32 19 0 11 20 31 54 61 34 25 21,57 53 39 25 26 32 30 11 0 10 20 43 51 24 14 13,47,47,29 15 26 35 39 20 10 0 18 36 41 14 9 18,52 61 42 33 43 47 50 31 20 18 0 23 46 25 14 23,48 57 38 32 45 52 65 54 43 36 23 0 27 22 33 42,21 52 38 32 45 52 65 61 51 41 46 27 0 39 48 57,41 48 29 15 28 35 48 34 24 14 25 22 39 0 11 20,52 56 38 24 29 33 44 25 14 9 14 33 48 11 0 9,61 63 44 30 38 42 40 21 13 18 23 42 57 20 9 0;,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)=65);,FOR(STEPZ(N):WZ(N)1,，,(2),如果线路从,j,到,k,，,则,u,k,=u,j,+1,，,且避免来回重复和圈，约束条件为,:,u,j,u,k,+x,kj,-(n-2)(1-x,kj,)+(n-3)x,jk,，,1kn,，,2jn,jk,；,最优连线,(,最小生成树,),转化为混合整数规划：,编写,LINGO,程序如下：,MODEL:,sets:,city/1.7/:u;!,定义,7,个城市,;,link(city,city):dist,x;,!,距离矩阵和决策变量,;,endsets,n=size(city);,data:,!dist,是距离矩阵,;,dist=0 3 4 7 100,100,100,3 0 3 2 4 100,100,4 3 0 100 5 7 100,7 2 100 0 2 100 6,100 4 5 2 0 1 4,100,100,7 100 1 0 2,100,100,100,6 4 2 0;,!,这里可改为你要解决的问题的数据,;,enddata,min=sum(link:dist*x);!,目标函数,;,U(1)=0;,for(link:bin(x);!,定义,X,为,01,变量,;,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););,end,计算结果：目标函数值,(,最优连线的长度,),为,13,，最优连线的构成如图所示,4,1,2,3,5,6,7,五、最大流问题,1,问题的描述,设有一批物资，要从,A,市通过公路网络（内含一些中转站）运往,B,市，已知每段公路的运输能力有限制（流量限制），问应如何安排运输方案，才能使总运量最大？这就是网络最大流问题,例：下图是从发货地到目的地的有向运输网络，称点为发点（源），点为收点（汇），有向边（弧）旁边的数字是该弧的流量（运输能力）限制，求的最大流,2,、数学模型,对每一条弧,(,顶点,i,到,j,),，定义,f,(,i,j,),为该弧上从顶点,i,到顶点,j,的流量，用,C,ij,表示其上的流量限制则对任意一个中转点，流进与流出相等，但顶点只有流出，顶点只有流进，并且两者大小相等,(,方向相反,),，如果我们在图上虚拟一条从的弧，其流量不受限制，并假设从流到的总量又从该虚拟弧上返回，整个网络系统构成一个封闭的不停流动的回路，则对任意顶点都满足流进等于流出,目标函数是,max f(n,1),，,n,是收点，,1,是发点,.,约束条件有两条：,(1),对每个顶点，流进等于流出，即,等式左边的求和是对所有以顶点,i,为终点的边进行，右边的求和是对所有以顶点,i,为起点的边进行,(2),对每条弧，流量不超过其限制值，即,完整的模型为：,编写,LINGO,程序如下：,MODEL:,SETS:,CHSH/1.6/;,LINKS(CHSH,CHSH)/1,2 1,3 2,4 2,5 3,4 3,5 4,6 5,6 6,1/:C,F;,!,该集合列出有弧相连的顶点对，与每一条弧一一对应，,6,1,是虚拟弧,;,ENDSETS,DATA:,C=16,20,10,10,6,6,10,16,1000;,!,虚拟弧上的流量不受限制,(,很大的数,);,ENDDATA,MAX=F(6,1);!,目标函数,;,FOR(LINKS(I,J):F(I,J)=C(I,J);!,流量限制,;,FOR(CHSH(I):SUM(LINKS(J,I):F(J,I)=SUM(LINKS(I,J):F(I,J);,!,每个顶点的流进等于流出,;,END,求解得到结果，最大流为,26,，运输方案,:,弧,1-2,1-3,2-4,2-5,3-4,3-5,4-6,5-6,虚拟弧,6-1,流量,14,12,4,10,6,6,10,16,14,六、最小费用最大流,上一节介绍了网络最大流问题及其求解方法，它不涉及费用问题，有时在实际问题中，网络中各条弧,(,边,),上的运输费用,(,单价,),不相同，因而在满足最大流的情况下,(,运输方案不唯一,),，要求费用最小的最大流，称为最小费用最大流问题下面看一个具体实例,例：图示网络的每一条弧上括号内有两个数字，前一个数字代表该弧上的最大流量，后一个数字是单位运费用,u,ij,表示弧,(,i,j,),上的最大流量，用,c,ij,表示运输单价。,3,5,1,2,4,6,先用求最大流的方法求出该网络从顶点,1,到顶点,6,的最大流为,14,，运输方案如下表所示：,最小费用是在满足最大流情况下找出费用最小的运输方案，故下一步是把求出的最大流作为约束条件，即把,f(6,1)=14,作为约束条件，目标函数改成,弧,1-2,1-3,2-3,2-4,3-5,4-3,4-6,5-4,5-6,6-1,流量,7,7,2,5,9,0,5,0,9,14,编写,LINGO,程序如下：,MODEL:,SETS:,CHSH/1.6/;,LINKS(CHSH,CHSH)/1,2 1,3 2,3 2,4 3,5 4,3 4,6 5,4 5,6 6,1/:C,U,F;,!6,1,是虚拟弧，,U,为流量限制，,C,为费用，,F,为实际流量,;,ENDSETS,DATA:,U=8,7,5,9,9,2,5,6,10,15;,C=2,8,5,2,3,1,6,4,7,8,;,ENDDATA,N=SIZE(CHSH);,F(6,1)=14;!,把上一步求出的最大流作为约束条件,;,MIN=SUM(LINKS(I,J)|I#LT#N:C(I,J)*F(I,J);,FOR(LINKS(I,J):F(I,J)=U(I,J);,FOR(CHSH(I):SUM(LINKS(J,I):F(J,I)=SUM(LINKS(I,J):F(I,J);,END,运行该程序，得到最小费用为,205,，最小费用下的最大流运输方案如下表所示,注：满足最大流时的运输方案可以有多种，表中所列方案是费用最小的方案。,弧,1-2,1-3,2-3,2-4,3-5,4-3,4-6,5-4,5-6,虚拟弧,6-1,流量,8,6,1,7,9,2,5,0,9,14,