《LINGO在图论中的应用课件》由会员分享，可在线阅读，更多相关《LINGO在图论中的应用课件（84页珍藏版）》请在金锄头文库上搜索。
1、第2章 LINGO在图论和网络模型中的应用LINGO在图论中的应用图图是是一一种种直直观观形形象象地地描描述述已已知知信信息息的的方方式式，它它使使事事物物之之间间的的关关系系简简洁洁明明了了，是是分分析析问问题题的的有有用用工工具具，很很多多实实际际问问题题可可以以用用图来描述。图来描述。LINGO在图论中的应用一、图的基本概念图的基本概念 图图论论是是以以图图为为研研究究对对象象的的数数学学分分支支，在在图图论论中中，图由一些点和点之间的连线所组成图由一些点和点之间的连线所组成 称称图图中中的的点点为为顶顶点点（节节点点），称称连连接接顶顶点点的的没没有有方方向向的的线线段段为为边边，称称
2、有有方方向向的的线线段段为为弧弧所所有有线线段段都都没没有有方方向向的的图图称称为为无无向向图图，所所有有线线段段都都有有方方向向的的图图称称为为有有向向图图，既既有有边边也也有有弧弧的的图图称称为为混混合图合图 点点与与边边相相连连接接称称为为关关联联，与与边边e关关联联的的顶顶点点称称为为该该边边的的端端点点，与与同同一一条条边边关关联联的的两两个个顶顶点点称称为为相邻顶点，与同一个顶点关联的边称为相邻边相邻顶点，与同一个顶点关联的边称为相邻边LINGO在图论中的应用具具有有相相同同顶顶点点的的边边称称为为平平行行边边，两两个个端端点点重重合合的的边边称称为为环环在在无无向向图图中中，没没
3、有有环环和和平平行行边边的的图图称称为为简简单单图图，任任意意一一对对顶顶点点都都有有一一条条边边相相连连的的简简单单图图称称为为完完全全图图任任意意两两个个顶顶点点之之间间有有且且只只有有一一条条弧弧相相连的有向图称为竞赛图连的有向图称为竞赛图在在图图中中，两两个个顶顶点点u和和v之之间间由由顶顶点点和和边边构构成成的的交交错错序序列列（使使u和和v相相通通）称称为为链链（通通道道），没没有有重重复复边边的的通通道道称称为为迹迹，起起点点与与终终点点重重合合的的通通道道称称为为闭闭通通道道，不不重重合合的的称称为为开开通通道道，没没有有重重复复顶顶点点（必必然然边边也也不不重重复复）的的开开
4、通通道道称称为为路路，起起点点与与终终点点重重合合的的路路称称为为圈圈（回回路路）如如果果顶顶点点u和和v之之间间存存在在通通道道，称称u和和v是是连连通通的的，任任意意两两个个顶顶点点都都连连通通的的图图称称为为连连通图通图 LINGO在图论中的应用无圈的连通图称为树，如果一棵树无圈的连通图称为树，如果一棵树T包含了图包含了图G的所有顶点，称的所有顶点，称T为为G的生成树的生成树如果图如果图G的每条边的每条边e都对应一个实数都对应一个实数C(e)，称，称C(e)为该边为该边e的权，称图的权，称图G为赋权图通常称赋权的为赋权图通常称赋权的有向图为网络有向图为网络LINGO在图论中的应用二、最短
5、路问题1.1.动态规划法动态规划法(1)(1)问题的描述问题的描述给给定定N个个点点Pi(i=1,2,.,n)组组成成集集合合Pi，集集合合中中任任一一点点Pi到到另另一一点点Pj的的距距离离用用Wij表表示示，如如果果Pi到到Pj没没有有弧弧联联结结(无无通通路路)，则则规规定定Wij=+，又又规规定定，Wii=0 (i=1,2,.,n)，指指定定一一个个终终点点PN，要要求求从从Pi点点出出发发到到PN的最短路的最短路线线。可可以以用用动动态态规规划划的的方方法法来来求求最最短短路路问问题题，下下面面举例说明其算法原理举例说明其算法原理。LINGO在图论中的应用2.2.算法原理算法原理举例
6、：举例：图图中中A,B,.,G表表示示7个个城城市市，连连线线表表示示城城市市之之间间有有道道路路相相通通，连连线线旁旁的的数数字字表表示示道道路路的的长长度度Wij，现要从城市现要从城市A到到G找出一条最短路线。找出一条最短路线。该该问问题题有有三三个个阶阶段段，第第一一阶阶段段从从A到到B或或C，第第二二阶阶段段到到D,E或或F，第第三三阶阶段段到到终终点点G，我我们们从从终终点点向前倒过来找。向前倒过来找。AGFEDCB24123133134LINGO在图论中的应用第第三三阶阶段段，从从D,E,F到到G的的最最短短路路分分别别为为1,3,4，记记为为f(D)=1,f(E)=3,f(F)=
7、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；L
8、INGO在图论中的应用第第一一阶阶段段，出出发发点点只只有有一一个个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相联相联,上一步考察过，上一步
9、考察过，且与终点相通、且与终点相通、f(j)为已知的点。为已知的点。LINGO在图论中的应用编写编写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用用来存放最短路的路径来存放最短路的路径;endsetsLINGO在图论中的应用data: W=2 4 3 3 1 2 3 1 1 3 4;endd
10、ata 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 F值值; ; !显显然然，如如果果P(i,j)=1,P(i,j)=1,则则点点i i到到点点n n的的最最短短路路径径的的第第一一步步是是i i - - j j，否否则则就就不不是是。由由此此，我我们们就就可可方方便便的的确确定出最短路径定出最短路径; for(roads(i,j): P(i,j)=if(FL(i) #eq# W(i,j)+FL(j),1,
11、0);endLINGO在图论中的应用部分计算结果：部分计算结果：FL(A) 6FL(A) 6FL(B) 4FL(B) 4FL(C) 3FL(C) 3FL(D) 1FL(D) 1FL(E) 3FL(E) 3FL(F) 4FL(F) 4FL(G) 0FL(G) 0最短路线为最短路线为 A B D G A B D G以以上上计计算算程程序序是是通通用用程程序序，对对其其它它图图，只只需需在在此程序基础上对数据作一些修改即可。此程序基础上对数据作一些修改即可。LINGO在图论中的应用程程序序中中的的语语句句roads(cities,cities)/ A,B A,C B,D B,E B,F C,D C,
12、E C,F D,G E,G F,G/: W, P; 定定义义的的集集合合称称为为稀稀疏疏集集合合，本本例例中中cities有有7个个成成员员，但但是是并并非非每每个个城城市市到到其其它它6个个城城市市都都有有路路相相通通，只只有有部部分分城城市市之之间间有有路路，故故定定义义衍衍生生集集合合roads时时用用列列举法列出有路相通的每对城市举法列出有路相通的每对城市 。LINGO在图论中的应用2 20 01 1规划法规划法用用01规规划划法法也也能能求求解解最最短短路路问问题题，其其思思路路如如下下设设起起点点为为1，终终点点为为n引引入入01型型决决策策变变量量Xij，如果弧，如果弧(i ,
13、j)在最短路上，则在最短路上，则Xij=1，否则，否则Xij=0对对于于除除了了起起点点1和和终终点点n以以外外的的任任意意一一个个顶顶点点i，如如果果， 说说明明从从i出出发发的的所所有有弧弧中中必必然然有有一一条条弧弧在在最最短短路路上上，也也就就是是说说最最短短路路经经过过该该顶顶点点，此此时时所所有有从从其其它它顶顶点点到到达达该该顶顶点点的的弧弧中中必必然然也也有有一一条条弧弧在在最最短路上，因而必有：短路上，因而必有：LINGO在图论中的应用如如果果 ，说说明明最最短短路路不不经经过过顶顶点点i，故故必有必有两种情况可以合并写成两种情况可以合并写成 ：对于起点对于起点1，则必然满足
14、：，则必然满足：对于终点对于终点n，则必有：，则必有：LINGO在图论中的应用目目标标函函数数是是最最短短路路上上的的各各条条弧弧的的长长度度之之和和(总总里里程程)最最小小，于于是是最最短短路路问问题题可可以以用用如如下下01规规划划来来描述：描述：式中式中 表示全体边的集合表示全体边的集合 。LINGO在图论中的应用对于上例，编写对于上例，编写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
15、F,G/: W, X;!定定义义哪哪些些城城市市之之间间有有路路相相联联，W为为里里程程，X为为01型型决策变量决策变量;endsetsdata: W=2 4 3 3 1 2 3 1 1 3 4;enddataLINGO在图论中的应用 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:
16、X(i,j)=1; endLINGO在图论中的应用 计计算算结结果果与与动动态态规规划划法法相相同同程程序序中中的的最最后后一一个个约约束束方方程程可可以以去去掉掉，因因为为有有了了前前面面两两个个约约束束条条件件(共共n-1个个约约束束方方程程)可可以以导导出出最最后后一一个个约约束束方方程程，即即终终点点的的约约束束方方程程与与前前面面n-1个个约约束束方方程程线线性性相相关关保保留留该该约约束束方方程程，LINGO求求解解时时也也不不会会产产生生任任何问题，因为何问题，因为LINGO会自动删除多余的方程会自动删除多余的方程该该方方法法与与前前面面的的方方法法相相比比，灵灵活活性性稍稍差差
17、，它它一一次次只只能能求求出出指指定定起起点点到到指指定定终终点点的的最最短短路路，如如果果更更改起点，则必须改动程序然后重新求解改起点，则必须改动程序然后重新求解LINGO在图论中的应用三、 旅行售货商模型旅旅行行售售货货商商问问题题( (又又称称货货郎郎担担问问题题，Traveling Traveling Salesman Salesman ProblemProblem 简简称称TSPTSP模模型型），是运筹学的一个著名命题。，是运筹学的一个著名命题。模模型型：有有一一个个推推销销商商，从从某某个个城城市市出出发发，要要遍遍访访若若干干城城市市各各一一次次且且仅仅一一次次 ，最最后后返返回
18、回出出发发城城市市。已已知知从从城城市市i i到到j j的的旅旅费费为为C Cijij，问问他他应应按按怎怎样样的的次次序序访访问问这这些些城城市市，使使得得总旅费最少？总旅费最少？称称能能到到每每个个城城市市一一次次且且仅仅一一次次的的路路线线为为一一个巡回个巡回( (圈圈) )。LINGO在图论中的应用TSPTSP是是典典型型的的组组合合优优化化问问题题，也也是是公公认认的的NPNP完全难题。完全难题。不不算算出出发发地地。n n个个城城市市有有(n-1)!(n-1)!种种排排列列方方法法，每每一一种种旅旅行行路路线线是是排排列列中中的的一一种种，当当n n变变大大时时，计计算算量量呈呈指
19、指数数增增长长，穷穷举举法法所所费费时间是难以承受的。时间是难以承受的。为为此此，多多年年以以来来有有许许多多人人研研究究了了一一些些近近似算法。似算法。我我们们把把TSPTSP问问题题转转化化为为0-10-1规规划划，然然后后用用LINGOLINGO来求解。来求解。LINGO在图论中的应用1. 方法一：判断各边是否包含在旅行路线中方法一：判断各边是否包含在旅行路线中引引入入0-1整整数数变变量量xij(且且ij)：xij=1表表示示路路线线从从i到到j，即即边边i-j在在旅旅行行路路线线中中，而而xij0则则表表示示不不走走i-j路线路线目标函数目标函数首首先先必必须须满满足足约约束束条条件
20、件：对对每每个个城城市市访访问问一一次次且且仅仅一一次次。从从城城市市i出出发发一一次次(到到其其它它城城市市去去),表示为表示为LINGO在图论中的应用引引入入0-1整整数数变变量量xij(且且ij)：xij=1表表示示路路线线从从i到到j，xij0则表示不走则表示不走i-j路线路线目标函数目标函数首首先先必必须须满满足足约约束束条条件件：对对每每个个城城市市访访问问一一次次且且仅仅一一次次。从从城城市市i出出发发一一次次(到到其其它它城城市市去去),表表示示为为从某个城市到达从某个城市到达j一次且仅一次，表示为：一次且仅一次，表示为：以以上上建建立立的的模模型型类类似似于于指指派派问问题题
21、的的模模型型，对对TSP问题只是必要条件，并不充分。问题只是必要条件，并不充分。LINGO在图论中的应用例例如如，用用图图示示路路线线连连接接六六个个城城市市，满满足足以以上上两两个个约约束束条条件件，但但这这样样的的路路线线出出现现了了两两个个子子回回路，两者之间不通，不构成整体巡回路线。路，两者之间不通，不构成整体巡回路线。为为此此需需要要考考虑虑增增加加充充分分的的约约束束条条件件以以避避免免产产生子巡回。生子巡回。下面介绍一种方法：下面介绍一种方法：增增加加变变量量u ui i,i=2,3,n,i=2,3,n，（它它的的大大小小可可以以取取整整数数：例例如如从从起起点点出出发发所所达达
22、到到的的城城市市u=2,u=2,依依此此类推）。类推）。312456LINGO在图论中的应用附加约束条件：附加约束条件：ui-uj+nxijn-1,i=1,n，j=2,n，且且ij 。下下面面证证明明：(1)任任何何含含子子巡巡回回的的路路线线都都必必然然不不满满足足该约该约束条件束条件（不管（不管ui如何取值）如何取值）；(2)全全部部不不含含子子巡巡回回的的整整体体巡巡回回路路线线都都可可以以满满足足该约该约束条件束条件（只要（只要ui取适当值）取适当值）。用用反反证证法法证证明明(1),假假设设存存在在子子巡巡回回，则则至至少少有有两两个个子子巡巡回回。那那么么（必必然然）至至少少有有一
23、一个个子子巡巡回回中中不不含起点城市含起点城市1，如上图中的，如上图中的4564，则必有，则必有 u4-u5+nn-1，u5-u6+nn-1，u6-u4+nn-1，把把这这三三个个不不等等式式加加起起来来得得到到nn-1，不不可可能能，故故假假设设不不能能成成立立。而而对对整整体体巡巡回回，因因为为附附加加约约束束中中j2,不包含起点城市不包含起点城市1，故不会发生矛盾。，故不会发生矛盾。LINGO在图论中的应用对对于于整整体体巡巡回回路路线线，只只要要u ui i取取适适当当值值，都都可可以以满满足足该约该约束条件束条件：()()对对于于总总巡巡回回上上的的边边，x xijij=1, =1,
24、 u ui i可可取取访访问问城城市市i i的的 顺顺 序序 数数 ， 则则 必必 有有 u ui i-u-uj j -1-1， 约约 束束 条条 件件 u ui i- -u uj j+nx+nxijijn-1n-1变成：变成：-1+n n-1-1+n n-1，必然成立。，必然成立。()()对对于于非非总总巡巡回回上上的的边边，因因为为x xijij=0 =0 ，约约束束条条件件u ui i-u-uj j+nx+nxijijn-1n-1变成变成-1-1n-1n-1，肯定成立。，肯定成立。综综上上所所述述，该该约约束束条条件件只只限限止止子子巡巡回回，不不影影响响其其它它，于于是是TSPTSP问
25、问题题转转化化成成了了一一个个混混合合整整数数线线性性规规划划问题问题。LINGO在图论中的应用TSPTSP问题可以表示为规划：问题可以表示为规划：LINGO在图论中的应用TSP问题的问题的LINGO模型模型!旅行售货员问题旅行售货员问题;model:sets: city / 1.6/: u;! 定义定义6 6个城市个城市; ; link( city, city): dist, ! 距离矩阵距离矩阵; x; !决策变量决策变量; ;endsets n = size( city);LINGO在图论中的应用data: !距离矩阵距离矩阵; dist =0 702 454 842 2396 1196
26、 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); LINGO在图论中的应用 FOR( city( K): !进入城市进入城市K;K; sum( city( I)| I #ne# K: x( I, K) = 1; !离开城市离开城市K;
27、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变量变量;endLINGO在图论中的应用计算结果：计算结果：目
28、标函数值：目标函数值：6610路线：路线：1-3-6-2-5-4-11-3-6-2-5-4-1LINGO在图论中的应用2. 方法二：对城市排序，找出最优排序方法二：对城市排序，找出最优排序在在现现实实中中的的城城市市交交通通图图中中，有有些些城城市市之之间间有有直直接接道道路路，有有些些则则没没有有，如如果果两两点点之之间间没没有有直直接接的的通通路路，则则两两点点之之间间的的距距离离取取最最短短路路（经经过过其其它它点点），即即用用任任意意两两点点之之间间的的最最短短路路Cij作作为为图图的的距距离离矩矩阵阵，于于是是该该图图可可以以看看成成是是一一个个完完全全图图（即即任任意意一一对对顶顶
29、点点都都有有一一条条边边相相连连的的图图），此此时时形形式式上上的的环环形形巡巡回回路路线线实实际际上上个个别别点点有有可可能不止经过一次。能不止经过一次。LINGO在图论中的应用设设某某个个城城市市为为旅旅行行的的出出发发地地和和终终点点（相相当当于于总总部部所所在在地地），旅旅行行者者从从该该城城市市出出发发到到其其它它n个个城城市市各各一一次次且且仅仅一一次次，最最后后回回到到出出发发地地。我我们们把把行行进进路路线线分分成成n步步，每每一一步步到到一一个个城城市市（第第n+1步步返返回回出出发发地地），于于是是一一条条旅旅行行路路线线就就相相当当于于n个个城城市市的的一一种种排排列列，
30、n个个城城市市共共有有n!种种排排列列方方式式。排排序序不不同同则则总总里里程程（或或费费用用）可可能能不不同同，总总里里程程（或或总总费费用用）最最小小的的排排序序就就是是我我们们要要寻寻找的最优路线。找的最优路线。LINGO在图论中的应用引引入入0-1型型决决策策变变量量Xkj，下下标标k表表示示旅旅行行的的步步数数，下下标标j表表示示到到达达哪哪一一个个城城市市，Xkj=1表表示示旅旅行行者者第第k个个目目的的地地（到到达达点点）是是城城市市j，Xkj=0则则表表示示否否。用用lj表表示示总总部部到到各各城城市市的的距距离离，用用Cij表表示示城市城市i与城市与城市j之间的最短路。之间的
31、最短路。从出发地到第从出发地到第1个点的路程为个点的路程为从最后一个点返回出发地的里程为从最后一个点返回出发地的里程为 LINGO在图论中的应用假假设设在在第第k步步邮邮车车达达到到城城市市i，在在第第k+1步步达达到到支局支局j，即，即Xki=Xk+1,j=1，则走过的里程为：，则走过的里程为： CijXkiXk+1,j从第从第1点到第点到第n点走过的总里程为点走过的总里程为目标函数为目标函数为LINGO在图论中的应用约束条件有以下约束条件有以下2条：条：(1) 每一步到达一个城市，即每一步到达一个城市，即(2) 每一个城市必须到一次且只需一次，即每一个城市必须到一次且只需一次，即LINGO
32、在图论中的应用综综上上所所述述，可可以以把把TSP问问题题转转化化成成如如下下非非线线性性0-1 规划规划LINGO在图论中的应用以上规划种允许包含其它约束条件。以上规划种允许包含其它约束条件。用用LINGO可以求解该规划，举例如下。可以求解该规划，举例如下。某某县县邮邮局局和和10个个乡乡镇镇支支局局组组成成该该县县的的邮邮政政运运输输网网络络，已已知知县县局局到到各各支支局局的的距距离离和和支支局局之之间间的的距距离离矩矩阵阵（数数据据在在程程序序中中）。用用一一辆辆邮邮车车完完成成邮邮件件运运输输任任务务，邮邮车车从从县县局局出出发发到到各各支支局局去去一一次次且且只只需需一一次次，最最
33、后后回回到到县县局局，求求总总路路程程最最短的行驶路线。短的行驶路线。LINGO在图论中的应用编写编写LINGO程序如下：程序如下：MODEL:SETS: CITY/1.10/: JL; STEP/1.10/; LINE( STEP, CITY): X; LINKS(CITY,CITY):C;ENDSETSLINGO在图论中的应用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
34、,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;ENDDATALINGO在图论中的应用FOR( LINE : BIN( X); M1=SIZE(STEP); FOR(CITY(I): SUM(STEP(N): X(N,I) = 1);FOR(STEP(
35、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;ENDLINGO在图论中的应用在程序运行前需要对在程序运行前需要对LINGO的参数作必要的设置。的参数作必要的设置。对对于于非非线线性性规规划划，LINGO提提供供两两种种求求解解方方法法，一一种种是是“Global Solver”（称称为为全全局局优优化化求求解解器器），另另一一种种是是“Multistart Solver”（称称
36、为为多多起起点点算算法法），全全局局优优化化求求解解器器优优点点是是确确保保找找到到全全局局最最优优解解，缺缺点点是是有有时时需需要要较较长长运运行行时时间间。多多起起点点算算法法的的优优点点是是节节省省运运行行时时间间，但但不不能能保保证证找找到到的的解解就就是是全全局局最最优优解解，多多设设置置起起点点数数往往找到的解就是全局最优解。往往找到的解就是全局最优解。点点击击菜菜单单“Options”，再再打打开开全全局局优优化化求求解解器器“Global Solver”选选 项项 ， 可可 以以 选选 或或 不不 选选 “Global Solver”，当当选选择择多多起起点点算算法法“Mult
37、istart Solver”时时，需需要要设设置置起起点点数数，若若选选择择“Solver Decides”表表示示由由LINGO决定。决定。LINGO在图论中的应用对对以以上上程程序序，我我们们选选择择“Global Solver”，点点击击菜菜单单“Options”，在在全全局局优优化化求求解解器器“Global Solver”选选项框内打项框内打“”，再点击，再点击“确定确定”。运行以上程序，费时运行以上程序，费时4分多钟，得到最优解：分多钟，得到最优解：目标函数值（总路程）目标函数值（总路程）260公里公里邮车的行驶路线为：邮车的行驶路线为：县局县局891076541238910765
38、4123县局县局LINGO在图论中的应用3. 多旅行商问题多旅行商问题在在现现实实中中问问题题中中，有有时时候候不不是是由由一一人人走走遍遍所所有有点点，而而是是由由几几个个人人分分工工合合作作，每每个个人人只只到到其其中中部部分分城城市市，每每个个点点都都有有人人来来过过一一次次且且只只需需一一次次，事事先先不不指指定定谁谁到到哪哪些些点点，求求出出使使总总路路程程最最小的旅行规划（每个人的行走路线）。小的旅行规划（每个人的行走路线）。例例如如邮邮路路规规划划中中，为为了了在在允允许许的的时时间间内内完完成成邮邮件件运运输输任任务务，县县局局的的邮邮车车往往往往不不止止1辆辆，而而是是用用若
39、若干干辆辆邮邮车车分分工工运运输输，只只要要保保证证每每个个支支局局有有邮邮车车来来过过即即可可，为为了了节节省省行行驶驶费费用用，需需要要规规划划几辆邮车的最佳路线。这就是多旅行商问题。几辆邮车的最佳路线。这就是多旅行商问题。LINGO在图论中的应用多多旅旅行行商商问问题题的的提提法法如如下下：有有n+1个个城城市市，相相互互间间的的路路程程（或或旅旅行行费费用用）为为已已知知，有有k个个旅旅行行商商都都从从总总部部所所在在城城市市出出发发，赴赴其其它它城城市市旅旅行行推推销销，分分工工遍遍历历其其余余n个个城城市市，即即每每个个城城市市各各有有任任意意一一名名旅旅行行商商来来过过一一次次且
40、且仅仅一一次次，最最后后都都回回到到出发地，目标是总路程最短或总费用最省。出发地，目标是总路程最短或总费用最省。多多旅旅行行商商问问题题在在物物流流配配送送、邮邮路路优优化化等等方方面面具具有有较较高高的的实实用用价价值值，而而在在现现实实问问题题中中，研研究究对对象象往往往往不不是是单单纯纯的的旅旅行行商商问问题题，而而要要考考虑虑各各种种约约束束条条件件，例例如如时时间间约约束束、载载重重量量约约束束等等等等。研研究究这这一一类类带带约约束束条条件件的的多多旅旅行行商商问问题题具具有有很很强的现实意义。强的现实意义。 LINGO在图论中的应用在在现现实实的的多多旅旅行行商商问问题题中中，往
41、往往往带带有有约约束束条条件，例如时间约束、载重量约束等等。件，例如时间约束、载重量约束等等。带带约约束束条条件件的的多多旅旅行行商商问问题题具具有有广广泛泛现现实实意意义义，且且是是极极具具挑挑战战性性的的难难题题，我我们们仍仍然然把把它它转转化为化为0-1非线性规划并编成非线性规划并编成LINGO程序来求解。程序来求解。实例实例某某县县邮邮政政局局管管辖辖16个个支支局局，已已知知县县局局到到各各支支局局的的距距离离以以及及16个个支支局局之之间间的的距距离离矩矩阵阵。寄寄达达各支局和各支局收寄的邮件各支局和各支局收寄的邮件(袋袋)如下表所示：如下表所示：LINGO在图论中的应用县邮局和各
42、支局分布图县邮局和各支局分布图LINGO在图论中的应用每每一一辆辆邮邮车车最最多多装装载载65袋袋邮邮件件，邮邮车车的的运运行行成成本本为为3元元/ /公公里里。试试用用最最少少邮邮车车，并并规规划划邮邮车车的行驶路线使总费用最省。的行驶路线使总费用最省。分析分析：首首先先考考虑虑最最少少邮邮车车数数量量，由由题题目目所所给给表表中中数数据据，寄寄达达16个个支支局局的的邮邮件件总总数数为为176袋袋，从从各各支支局局收收寄寄的的邮邮件件总总数数为为170袋袋，每每一一辆辆邮邮车车最最多多容容纳纳65袋袋邮邮件件，至至少少需需要要176/652.7辆辆邮邮车车，由由于于邮邮车车数数量量为为整整
43、数数，故故最最少少需需要要3辆辆邮邮车车。如如果果3辆辆邮邮车车能能够够完完成成邮邮件件运运输输任任务务，则则3辆辆车车就就是是邮邮车数量的最优解。车数量的最优解。 LINGO在图论中的应用运运输输费费用用与与行行驶驶里里程程成成正正比比，总总里里程程最最短短对对应应总总费费用用最最省省。把把16个个支支局局放放在在一一起起作作为为一一个个整整体体考考虑虑，找找出出3条条邮邮路路，每每条条邮邮路路都都从从县县局局出出发发，到到若若干干支支局局进进行行卸卸装装，最最后后回回到到县县局局。各各邮邮车车路路过过的的支支局局数数量量未未知知，合合理理安安排排各各邮邮车车的的行行驶驶路路线线，由由3辆辆
44、邮邮车车分分别别承承包包运运输输，在在满满足足运运载载量量约约束束前前提提下下，把把3条条巡巡回回路路线线的的总总里里程程最最小小作作为为优优化化的的目目标标。该该问问题题相相当当于于附附带带约约束束条条件件的多旅行商模型。的多旅行商模型。LINGO在图论中的应用引引入入0-1型型决决策策变变量量Xkj,Ykj,Zkj，分分别别表表示示3辆辆邮邮车车第第k步步到到达达支支局局j，下下标标k表表示示邮邮车车行行走走的的步步数数，下下标标j表表示示到到达达哪哪一一个个支支局局，当当决决策策变变量量Xkj,Ykj,Zkj等等于于1时时分分别别表表示示某某邮邮车车第第k个个装装卸卸点点是是支支局局j，
45、等等于于0时时表表示示否否。设设各各邮邮车车管管辖辖的的支支局局数数量量分分别别为为m1,m2,m3，则则m1+m2+m3=16。约束条件有以下约束条件有以下3条：条：(1) 任何一辆车在任何一步到达一个支局任何一辆车在任何一步到达一个支局 ，即，即LINGO在图论中的应用(2) 任任何何一一个个支支局局必必须须有有一一辆辆邮邮车车到到达达一一次次且只需要一次，即且只需要一次，即 (3) 在在邮邮车车行行进进的的任任何何路路段段上上，装装载载的的邮邮件件不超过不超过65袋。袋。 设设寄寄达达各各支支局局的的邮邮件件量量为为Pj，各各支支局局收收寄寄的的邮邮件件量量为为Qj。 装装载载量量是是动
46、动态态变变化化的的，以以第第1辆辆邮邮车为例，出发时的装载量为车为例，出发时的装载量为LINGO在图论中的应用到第到第1个支局卸装以后，装载量变为个支局卸装以后，装载量变为在行驶过程中，装载量的递推公式为在行驶过程中，装载量的递推公式为约束条件为约束条件为LINGO在图论中的应用综综上上所所述述，建建立立多多旅旅行行商商问问题题的的0-1规规划划模模型型如下：如下：LINGO在图论中的应用装载量的计算公式为：装载量的计算公式为：LINGO在图论中的应用编写编写LINGO程序如下：程序如下：MODEL:SETS: STATION/1.16/: JL,P,Q; STEPX/1.6/:WX; STE
47、PY/1.5/:WY; STEPZ/1.5/:WZ; LINEX( STEPX, STATION): X; LINEY( STEPY, STATION): Y; LINEZ( STEPZ, STATION): Z; LINKS(STATION,STATION):C;ENDSETSLINGO在图论中的应用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;
48、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
49、 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 LINGO在图论中的应用 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
50、 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;ENDDATALINGO在图论中的应用FOR( LINEX : BIN( X); FOR( LINEY : BIN( Y); FOR( LINEZ : BIN( Z);M1=SIZE(STEPX); M2=SIZE(STEPY);M3=SIZE(STEPZ); FOR(STA
51、TION(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);LINGO在图论中的应用WX0=SUM(STATION(I):P*SUM(STEPX(N):X(N,I); WY0=SUM(STATION(I):P*SUM(STEPY(N):Y(N,I); WZ0=SUM(STATI
52、ON(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
53、(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); LINGO在图论中的应用FOR(STEPZ(N):WZ(N)1，(2) 如如果果线线路路从从j到到k，则则uk=uj+1，且且避避免免来来回回重重复和圈，约束条件为复和圈，约束条件为:ujuk+xkj-(n-2)(1-xkj)+(n-3)xjk，1kn， 2jn jk；LINGO在图论中的应用最优连线最优连线( (最小生成树最小生成树) )
54、 转化为混合整数规划：转化为混合整数规划：LINGO在图论中的应用编写编写LINGO程序如下：程序如下：MODEL:sets: city / 1.7/: u;! 定义定义7个城市个城市; link( city, city): dist, x; !距离矩阵和决策变量距离矩阵和决策变量;endsets n = size( city);data: !dist是距离矩阵是距离矩阵;LINGO在图论中的应用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
55、100 7 100 1 0 2100 100 100 6 4 2 0;!这里可改为你要解决的问题的数据这里可改为你要解决的问题的数据;enddataLINGO在图论中的应用 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)
56、+(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););endLINGO在图论中的应用计算结果：目标函数值计算结果：目标函数值(最优连线的长度最优连线的长度)为为13，最优连线的构成如图所示最优连线的构成如图所示4123567LINGO在图论中的应用五、最大流问题五、最大流问题1问题的描述问题的描述设设有有一一批批物物资资，要要从从A市市通通过过公公路路网网络络（内内含含一一些些中中转转站站）运运往往B市市，已已知知每每段段
57、公公路路的的运运输输能能力力有有限限制制（流流量量限限制制），问问应应如如何何安安排排运运输输方方案案，才才能能使使总总运运量量最最大大？这这就就是是网网络络最最大大流流问题问题例例：下下图图是是从从发发货货地地到到目目的的地地的的有有向向运运输输网网络络，称称点点为为发发点点（源源），点点为为收收点点（汇汇），有有向向边边（弧弧）旁旁边边的的数数字字是是该该弧弧的的流流量量（运运输能力）限制，求输能力）限制，求的最大流的最大流LINGO在图论中的应用2、数学模型、数学模型 对对每每一一条条弧弧(顶顶点点i到到j)，定定义义f(i,j)为为该该弧弧上上从从顶顶点点i到到顶顶点点j的的流流量量，
58、用用Cij表表示示其其上上的的流流量量限限制制则则对对任任意意一一个个中中转转点点，流流进进与与流流出出相相等等，但但顶顶点点只只有有流流出出，顶顶点点只只有有流流进进，并并且且两两者者大大小小相相等等(方方向向相相反反)，如如果果我我们们在在图图上上虚虚拟拟一一条条从从的的弧弧，其其流流量量不不受受限限制制，并并假假设设从从流流到到的的总总量量又又从从该该虚虚拟拟弧弧上上返返回回，整整个个网网络络系系统统构构成成一一个个封封闭闭的的不不停停流流动动的的回回路路，则对任意顶点都满足流进等于流出则对任意顶点都满足流进等于流出 LINGO在图论中的应用目目标标函函数数是是max f(n,1)，n是
59、是收收点点，1是是发发点点.约束条件有两条：约束条件有两条：(1)对每个顶点，流进等于流出，即对每个顶点，流进等于流出，即等等式式左左边边的的求求和和是是对对所所有有以以顶顶点点i为为终终点点的的边边进进行行，右右边边的的求求和和是是对对所所有有以以顶顶点点i为为起起点点的的边边进行进行(2)对每条弧，流量不超过其限制值，即对每条弧，流量不超过其限制值，即 LINGO在图论中的应用完整的模型为：完整的模型为：LINGO在图论中的应用编写编写LINGO程序如下：程序如下：MODEL: SETS: CHSH/1.6/;LINKS(CHSH,CHSH)/1,2 1,3 2,4 2,5 3,4 3,5
60、 4,6 5,6 6,1/:C,F;!该集合列出有弧相连的顶点对，与每一条弧一该集合列出有弧相连的顶点对，与每一条弧一一对应，一对应，6,1是虚拟弧是虚拟弧; ENDSETS DATA:C=16,20,10,10,6,6,10,16,1000;!虚拟弧上的流量不受限制虚拟弧上的流量不受限制(很大的数很大的数); ENDDATALINGO在图论中的应用 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); !每个
61、顶点的流进等于流出每个顶点的流进等于流出;END求解得到结果，最大流为求解得到结果，最大流为26，运输方案，运输方案: 弧1-2 1-3 2-4 2-5 3-4 3-5 4-6 5-6 虚拟弧6-1流量141241066101614LINGO在图论中的应用六、最小费用最大流六、最小费用最大流 上上一一节节介介绍绍了了网网络络最最大大流流问问题题及及其其求求解解方方法法，它它不不涉涉及及费费用用问问题题，有有时时在在实实际际问问题题中中，网网络络中中各各条条弧弧(边边)上上的的运运输输费费用用(单单价价)不不相相同同，因因而而在在满满足足最最大大流流的的情情况况下下(运运输输方方案案不不唯唯一一
62、)，要要求求费费用用最最小小的的最最大大流流，称称为为最最小小费费用用最最大大流流问问题下面看一个具体实例题下面看一个具体实例 LINGO在图论中的应用例例：图图示示网网络络的的每每一一条条弧弧上上括括号号内内有有两两个个数数字字，前前一一个个数数字字代代表表该该弧弧上上的的最最大大流流量量，后后一一个个数数字字是是单单位位运运费费用用uij表表示示弧弧(i,j)上上的最大流量，用的最大流量，用cij表示运输单价。表示运输单价。 351246LINGO在图论中的应用先先用用求求最最大大流流的的方方法法求求出出该该网网络络从从顶顶点点1到到顶点顶点6的最大流为的最大流为14，运输方案如下表所示：
63、，运输方案如下表所示：最最小小费费用用是是在在满满足足最最大大流流情情况况下下找找出出费费用用最最小小的的运运输输方方案案，故故下下一一步步是是把把求求出出的的最最大大流流作作为为约约束束条条件件，即即把把f(6,1)=14作作为为约约束束条条件件，目目标函数改成标函数改成弧1-2 1-3 2-3 2-4 3-5 4-3 4-6 5-4 5-66-1流量77259050914LINGO在图论中的应用编写编写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
64、/: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 ;LINGO在图论中的应用 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);ENDLINGO在图论中的应用运运行行该该程程序序，得得到到最最小小费费用用为为205，最最小小费费用用下的最大流运输方案如下表所示下的最大流运输方案如下表所示注注：满满足足最最大大流流时时的的运运输输方方案案可可以以有有多多种种，表中所列方案是费用最小的方案。表中所列方案是费用最小的方案。 弧1-21-32-32-43-54-34-65-45-6虚拟弧6-1流量86179250914LINGO在图论中的应用
