Lingo在图论中的应用

LINGO在图论中的应用一、最短路问题AGFEDCB24123133134目标函数是最短路上的各条弧的长度之和(总里程)最小，于是最短路问题可以用如下0－1规划来描述：式中表示全体边的集合

。0－1规划法建模对于上例，编写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为0－1型决策变量;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(且i≠j)：xij=1表示路线从i到j，即边i-j在旅行路线中，而xij＝0那么表示不走i-j路线目标函数首先必须满足约束条件：对每个城市访问一次且仅一次。从城市i出发一次(到其它城市去),表示为引入0-1整数变量xij(且i≠j)：xij=1表示路线从i到j，xij＝0那么表示不走i-j路线目标函数首先必须满足约束条件：对每个城市访问一次且仅一次。从城市i出发一次(到其它城市去),表示为从某个城市到达j一次且仅一次，表示为：以上建立的模型类似于指派问题的模型，对TSP问题只是必要条件，并不充分。例如，用图示路线连接六个城市，满足以上两个约束条件，但这样的路线出现了两个子回路，两者之间不通，不构成整体巡回路线。为此需要考虑增加充分的约束条件以防止产生子巡回。下面介绍一种方法：增加变量ui,i=2,3,…,n，〔它的大小可以取整数：例如从起点出发所到达的城市u=2,依此类推〕。312456附加约束条件：ui-uj+nxij≤n-1,i=1,…,n，j=2,…,n，且i≠j。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为0\1变量;end计算结果：目标函数值：6610路线：1-3-6-2-5-4-12.方法二：对城市排序，找出最优排序在现实中的城市交通图中，有些城市之间有直接道路，有些那么没有，如果两点之间没有直接的通路，那么两点之间的距离取最短路〔经过其它点〕，即用任意两点之间的最短路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，那么走过的里程为：Cij·Xki·Xk+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;ENDSETSDATA: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提供两种求解方法，一种是“GlobalSolver”〔称为全局优化求解器〕，另一种是“MultistartSolver”〔称为多起点算法〕，全局优化求解器优点是确保找到全局最优解，缺点是有时需要较长运行时间。多起点算法的优点是节省运行时间，但不能保证找到的解就是全局最优解，多设置起点数往往找到的解就是全局最优解。点击菜单“Options”，再翻开全局优化求解器“GlobalSolver”选项，可以选或不选“Glob