图与网络模型

欢迎各位同学学习第八讲内容导航

1

运输问题与指派问题2

最短路问题和最大流问题3

最优连线问题与旅行商问题习题第八讲图与网络模型1

运输问题与指派问题本节内容导航1.1

运输问题1.2

指派问题§1.1运输问题

运输问题(TransportationProblem)是图论与网络中的一个重要问题，也是一个典型的线性规划问题.例1（运输问题）返回导航

例1

就是典型的运输问题，图1给出了个产地，个销地运输问题的图形.关于它的求解方法有两类，一类是按照图论的方法求解，另一类是化成线性规划问题.这里介绍第二类方法，即用LINGO软件求解运输问题.图1:个产地,个销售地运输问题的图形2.运输问题的数学表达式第个产地的运出量应小于或等于该地的生产量，即：第个销地的运入量应等于该地的需求量，即：对例1，设xij

代表从第i个产地调运给第j

个销地的物资数量。cij表示相应的运费，则目标函数为因此，运输问题的数学表达式为:称具有形如式

的线性规划问题为运输问题.

3.运输问题的求解过程为了便于讨论，以一个运输问题实例的求解过程来介绍如何用LINGO软件求解运输问题模型.

例2(继例1)设

即为有3个产地和4个销地的运输问题，其产量、销量及单位运费如表1所示.试求总运费最少的运输方案，以及总运费.下面写出求解该问题的LINGO程序，并在程序中用到在第三章介绍的集与数据段，以及相关的循环函数.

写出相应的LINGO程序，程序名：exam0801.lg4MODEL:1]!3Warehouse,4CustomerTransportationProblem;2]sets:3]Warehouse/1..3/:a;4]Customer/1..4/:b;

5]Routes(Warehouse,Customer):c,x;6]endsets7]!Herearetheparameters;8]data:9]a=30,25,2110]b=15,17,22,12;11]c=6,2,6,7,12]4,9,5,3,13]8,8,1,5;14]enddata15]!Theobjective;16][OBJ]min=@sum(Routes:c*x);

17]!Thesupplyconstraints;18]@for(Warehouse(i):[SUP]19]@sum(Customer(j):x(i,j))<=a(i));20]!Thedemandconstraints;21]@for(Customer(j):[DEM]22]@sum(Warehouse(i):x(i,j))=b(j));END

在上述程序中，第16]表示运输问题中目标函数(7.1).第18]

19]行表示约束条件(7.2),第21]22]行表示约束条件(7.3).

下面列出LINGO软件的求解结果（仅保留非零变量）Globaloptimalsolutionfoundatiteration:6Objectivevalue:161.0000VariableValueReducedCostX(1,1)2.0000000.000000X(1,2)17.000000.000000X(1,3)1.0000000.000000X(2,1)13.000000.000000X(2,4)12.000000.000000X(3,3)21.000000.000000RowSlackorSurplusDualPriceOBJ161.0000-1.000000SUP(1)10.000000.000000§1.2指派问题

例3（指派问题）设有n个人,计划作n项工作,其中表示第i个人做第j项工作的收益,现求一种指派方式，使得每个人完成一项工作，使总收益最大.

例3就是指派问题(AssignmentProblem).指派问题也是图论中的重要问题，有相应的求解方法，如匈牙利算法.从问题的形式来看，指派问题是运输问题的特例，也可以看成0-1规划问题.返回导航1.指派问题的数学表达式

设变量为,当第个人作第项工作时，,否则.因此，相应的线性规划问题为

2.指派问题的求解过程

下面用一个具体的例子来说明指派问题

例4（继例3）考虑例3中的情况,即6个人做6项工作的最优指派问题，其收益矩阵如表2所示.

下面用LINGO程序再求解此问题，程序中仍然用到集、数据段和循环函数.

写出相应的LINGO程序，程序名exam0804.lg4.MODEL:1]!AssignmentProblemModel;2]sets:3]Flight/1..6/;4]Assign(Flight,Flight):c,x;

5]endsets6]!Hereisincomematrix;7]data:8]c=2015165479]171533128610]9121816301311]1281127191412]-9971021103213]-99-99-9961113;14]enddata15]

16]!Maximizevalveofassignments;

17]max=@sum(Assign:c*x);

18]@for(Flight(i):19]!Eachimustbeassignedtosomej;20]@sum(Flight(j):x(i,j))=1;21]!EachImustreceiveanassignment;22]@sum(Flight(j):x(j,i))=1;23]);END

程序中第12]

13]行中的-99意义与LINDO程序中的意义相同，当某人无法做某项工作时，取一个数值较大的负值.LINGO软件计算结果如下（只列出非零变量）:Globaloptimalsolutionfoundatiteration:0Objectivevalue:135.0000VariableValueReducedCostX(1,1)1.0000000.000000X(2,3)1.0000000.000000X(3,2)1.0000000.000000X(4,4)1.0000000.000000X(5,6)1.0000000.000000X(6,5)1.0000000.000000

即第1个人做第1项工作，第2个人做第3项工作,第3个人做第2项工作，第4个人做第4项工作，第5个人做第6项工作，第6个人做第5项工作.总效益值为135.2最短路问题和最大流问题本节内容导航

本节概述

2.1最短路问题

2.2最大流问题

2.3

最小费与最大流问题

本节内容概述

最短路问题(ShortestPathProblems)和最大流问题(MaxiumumFlowProblems)是图论另一类与优化有关的问题，对于这两在问题，实际上，图论中已有解决的方法，如最短路问题的求解方法有Dijkstra算法，最大流问题的求解方法有标号算法.这里主要讨论的是如何用LINGO软件来求解最短路和最大流问题§2.1最短路问题

例5

（最短路问题）在图7-3中，用点表示城市，现有共7个城市.点与点之间的连线表示城市间有道路相连.连线旁的数字表示道路的长度.现计划从城市

到城市

铺设一条天然气管道，请设计出最小价格管道铺设方案.

例5的本质是求从城市到城市的一条最短路.下面我们主要就线性规划建模求解来分析返回导航2.最短路问题的数学表达式

假设图有个顶点，现需要求从顶点1到顶点的最短路.设决策变量为,当,说明弧在定点1到n的路上；否则.目标函数为寻找一条节点1到节点n的通路，使其上权值和最小，故目标函数为(1)对节点1恰有一条路径出去，缺不能有路径回来，故有(2)对节点n恰有一条路径到达，缺不能有路径出去，故有(3)对其余节点进去和出去的路径一样多，故有(4)对不通的路径不取，故有故总的线性规划模型为

3.最短路问题的求解过程

例6(继例5)求例5中，从城市A到城市D的最短路.

解：写出相应的LINGO程序，程序名:exam0806.lg4.MODEL:1]!Wehaveanetworkof7cities.Wewanttofind2]thelengthoftheshortestroutefromcity1tocity7;3]4]sets:5]!Hereisourprimitivesetofsevencities;6]cities/A,B1,B2,C1,C2,C3,D/;7]8]!TheDerivedset"roads"liststheroadsthat9]existbetweenthecities;10]roads(cities,cities)/11]A,B1A,B2B1,C1B1,C2B1,C3B2,C1B2,C2B2,C312]C1,DC2,DC3,D/:w,x;13]endsets14]15]data:16]!Herearethedistancesthatcorrespond

17]toabovelinks;18]w=24331231134;19]enddata20]21]n=@size(cities);!Thenumberofcities;22]min=@sum(roads:w*x);23]@for(cities(i)|i#ne#1#and#i#ne#n:24]@sum(roads(i,j):x(i,j))=@sum(roads(j,i):x(j,i)));25]@sum(roads(i,j)|i#eq#1:x(i,j))=1;

26]@FOR(roads(i,j):@bin(x(i,j)));END

在上述程序中，21]句中的n=@size(cities)是计算集cities的个数，这里的计算结果是,这样编写方法目的在于提高程序的通用性.22]句表示目标函数(14),即求道路的最小权值.23],24]句表示约束(15)中的情况，即最短路中中间点的约束条件.25]句表示约束中的情况，即最短路中起点的约束.

约束(15)中的情况，也就是最短路中终点的情况，没有列在程序中，因为终点的约束方程与前个方程相关.当然，如果你将此方程列入到LINGO程序中，计算时也不会出现任何问题，因为LINGO

软件可以自动删除描述线性规划可行解中的多余方程.

LINGO软件计算结果（仅保留非零变量）如下Globaloptimalsolutionfoundatiteration:0Objectivevalue:6.000000VariableValueReducedCost

X(A,B1)1.0000000.000000X(B1,C1)1.0000000.000000X(C1,D)1.0000000.000000

即最短路是,最短路长为6个单位.

例7(设备更新问题)张先生打算购买一辆新轿车，轿车的售价是12万元人民币.轿车购买后，每年的各种保险费养护费等费用由表5所示.如果在5年之内，张先生将轿车售出，并再购买新年.5年之内的二手车销售价由表6所示.请你帮助张先生设计一种购买轿车的方案，使5年内用车的总费用最少.

表5轿车的维护费车龄/年01234费用/万元245912表6二手车的售价车龄/年12345售价/万元76210

分析：设备更新问题是动态规划的一类问题（事实上，最短路问题也是动态规划的一类问题）,这里借助于最短路方法解决设备更新问题.

解：用6个点（1，2，3，4，5，6）表示各年的开始，各点之间的边从边表示左端点开始年至表示右端点结束所花的费用，这样构成购车消费的网络图，如图图4所示.

记表示第年开始到年结束购车的总销费,即由此得到写出相应的LINGO程序，程序名：exam0807.lg4MODEL:1]sets:2]nodes/1..6/;3]arcs(nodes,nodes)|&1#lt#&2:c,x;4]endsets5]data:6]w=7122131447]71221318]712219]71210]7;11]enddata12]n=@size(nodes);13]min=@sum(arcs:c*x);14]@for(nodes(i)|i#ne#1#and#i#ne#n:15]@sum(arcs(i,j):x(i,j))=@sum(arcs(j,i):x(j,i)));16]@sum(arcs(i,j)|i#eq#1:x(i,j))=1;

17]@FOR(arcs(i,j):@bin(x(i,j)));END

程序中的第3]句中&1#1t#&2是逻辑运算语句，表示所说明的变量只有行小于列的部分，因此所说明的矩阵是上三角阵.LINGO软件的计算结果（仅保留非零变量）如下

Globaloptimalsolutionfoundatiteration:0Objectivevalue:31.00000VariableValueReducedCostX(1,2)1.0000000.000000X(2,4)1.0000000.000000X(4,6)1.0000000.000000即第1年初购买轿车，第2年初卖掉，再购买新车，到第4年初卖掉，再购买新车使用到第5年末，总费用31万元.

当然，上述方案不是唯一的，例如还有和,但无论何种方案，总费用均是31万.某单位使用一台设备，在每年年初，领导都要决定是购置新设备代替原来的旧设备，还是继续使用旧设备。若购置新设备，需要支付一定的购置费用；若继续使用旧设备，则需支付一定的维修费用。设该种设备在每年年初的价格如下表所示，使用不同时间（年）的设备所需要的年维修费用如下表所示。试制定一个五年之内的设备更新计划，使总费用最少？第i年12345价格（万元）1112131213使用年数xx≤11<x≤22<x≤33<x≤44<x≤5维修费用（万元／年）5681118例8，思考(设备更新)：解用点vi表示“第i年年初购进一台新设备”这种状态i=1,2,…,5，用v6表示第5年底的状态。对每个i=1,2,…,5，从vi到vi＋1,…,v6各画一条弧，弧(vi,vj)表示在第

i年初购进一台设备一直使用到第

j年初（即第

j-1年底）。弧(vi,vj)的权为在第

i年初购进一台新设备一直使用到第

j-1年年底所发生的总费用。例如(v1,v4)表示第1年年初购进一台新设备，一直使用到第3年底。第i年12345价格（万元）1112131213使用年数xx≤11<x≤22<x≤33<x≤44<x≤5维修费用(万元／年)5681118第1年年初购进一台新设备，需支付11万元，一直使用到第3年底，需维修费5+6+8=19万元，故该弧的权为30。第i年12345价格（万元）1112131213使用年数xx≤11<x≤22<x≤33<x≤44<x≤5维修费用（万元／年）5681118用Dijkstra算法求解，最短路线为(v1,v4,v6)，总费用为53万元。这样就可得到一个赋权有向网络。所求问题等价于寻找从v1到v6的最短路问题。Lingo求解VariableValueF(1)53.00000F(2)42.00000F(3)32.00000F(4)23.00000F(5)18.00000F(6)0.000000

P(1,4)1.000000P(2,6)1.000000P(3,6)1.000000

P(4,6)1.000000P(5,6)1.000000

例9（无向图的最短路问题）求图5中到的最短路.

分析：不论是例7、例8均属于有向图的最短路问题，本例是处理无向图的最短路问题，在处理方式上与有向图的最短路有一些差别.

解：对于无向图的最短路问题，可以这样理解，从点到点和点到点的边看成有向弧，其他各条边均看成有不同方向的双弧，因此，可以按照前面介绍有向图的最短路问题来编程序，但按照这种方法编写LINGO程序相当边（弧）增加了一倍.这里选择邻接矩阵和赋权矩阵的方法编写LINGO程序.写出相应的LINGO程序，程序名：exam0809.lg4MODEL:1]sets:2]cities/1..11/;3]roads(cities,cities):p,w,x;4]endsets5]data:6]p=011100000007]001010000008]010111100009]0010001000010]0110010110011]0010101010012]0011010011013]0000100010114]0000111101115]0000001010116]00000000000;17]w=0281000000018]2060100000019]8607512000020]1070009000021]0150030290022]0010304060023]0029040031024]0000200070925]0000963701226]0000001010427]00000009240;28]enddata29]n=@size(cities);30]min=@sum(roads:w*x);31]@for(cities(i)|i#ne#1#and#i#ne#n:32]@sum(cities(j):p(i,j)*x(i,j))33]=@sum(cities(j):p(j,i)*x(j,i)));

34]@sum(cities(j):p(1,j)*x(1,j))=1;END

在上述程序中，第6]行到第16]行给出了图的邻接矩阵，到和到的边按单向计算，其余边双向计算.第17]行到第27]行给出了图的赋权矩阵,注意：由于有了邻接矩阵，两点无道路连接时，权值可以定义为0.其它的处理方法基本上与有向图相同.用LINGO软件求解，得到（仅保留非零变量）

Globaloptimalsolutionfoundatiteration:20Objectivevalue:13.00000

VariableValueReducedCostX(1,2)1.0000000.000000X(2,5)1.0000000.000000X(3,7)1.0000000.000000X(5,6)1.0000000.000000X(6,3)1.0000000.000000X(7,10)1.0000000.000000X(9,11)1.0000000.000000X(10,9)1.0000000.000000

即最短路径为,最短路长度.为13§

2.2最大流问题

例11（最大流问题）现需要将城市s的石油通过管道运送到城市t，中间有4个中转站和,城市与中转站的连接以及管道的容量如图6所示，求从城市s到城市t的最大流.返回导航

图6给出的有一个源和一个汇的网络.

网络中每一条边有一个容量,除此之外,

对边还有一个通过边的流(Flow),记为.

显然,边上的流量不会超过该边上的容量

,即称满足不等式（17）的网络是相容的.

对于所有中间顶点,流入的总量应等于流出的总量,即:

一个网络

的流量(Valueofflow)值定义为从源流出的总流量,即

由式(18)和(19)式可以看出,的流量值也为流入汇的总流量,即:

称满足式(21)的网络为守恒的.

定义6如果流满足不等式(17)和式(21),则称流是可行的.如果存在可行流,使得对所有的可行流均有则称为最大流(MaximumFlow).

2.最大流问题的数学规划表示形式通过上述推导得到最大流的数学规划表达式3.最大流问题的求解方法

下面用例子说明，如何用LINGO软件求解最大流问题.

例12

（继例7.11）用LINGO软件求解例11.

解：写出相应的LINGO程序，程序名:0812.lg4.MODEL:1]sets:2]nodes/s,1,2,3,4,t/;3]arcs(nodes,nodes)/4]s,1s,21,21,32,43,23,t4,34,t/:c,f;5]endsetsMODEL:1]sets:2]nodes/s,1,2,3,4,t/;3]arcs(nodes,nodes)/4]s,1s,21,21,32,43,23,t4,34,t/:c,f;5]endsets6]data:7]c=8759925610;8]enddata9]max=flow;

程序的第10]到12]行表示约束(23),第13]行表示有界约束(24).LINGO软件的计算结果（只保留流值）如下:Globaloptimalsolutionfoundatiteration:6Objectivevalue:14.00000VariableValueReducedCostFLOW14.000000.000000F(S,1)7.0000000.000000F(S,2)7.0000000.000000F(1,2)2.0000000.000000F(1,3)5.0000000.000000F(2,4)9.000000-1.000000

F(3,2)0.0000000.000000F(3,T)5.000000-1.000000F(4,3)0.0000001.000000F(4,T)9.0000000.000000

因此，该网络的最大流为14，F的值对应弧上的流，如图7-7所示,其中网络中的第一个数为容量，第二个数为流量.

在上面的程序中，采用稀疏集的编写方法，下面介绍的程序编写方法是利用邻接矩阵，这样可以不使用稀疏集的编写方法，更便于推广到复杂网络.MODEL:1]sets:2]nodes/s,1,2,3,4,t/;3]arcs(nodes,nodes):p,c,f;4]endsets5]data:6]p=0110007]0011008]0000109]00100110]00010111]000000;

12]c=08700013]00590014]00009015]00200516]000601017]000000;18]enddata19]max=flow;20]@for(nodes(i)|i#ne#1#and#i#ne#@size(nodes):21]@sum(nodes(j):p(i,j)*f(i,j))22]=@sum(nodes(j):p(j,i)*f(j,i)));23]@sum(nodes(i):p(1,i)*f(1,i))=flow;24]@for(arcs:@bnd(0,f,c));END在上述程序中，由于使用了邻接矩阵，当两点之间无弧时，定义弧容量为零.计算结果与前面程序的结果完全相同，这里就不再列出了.§

2.3最小费用最大流问题

例13（最小费用最大流问题）（续例11）由于输油管道的长短不一，或地质等原因，使每条管道上运输费用也不相同，因此，除考虑输油管道的最大流外，还需要考虑输油管道输送最大流的最小费用，图8所示是带有运费的网络，其中第1个数字是网络的容量，第2个数字是网络的单位运费.返回导航

例13所提出的问题就是最小费用最大流问题(Minimum-costmaximumflow)，即考虑网络在最大流情况下的最小费用.例12虽然给出了例11最大流一组方案，但它是不是关于费用的最优方案呢？这还需要进一步讨论.1.最小费用流的数学表达式

min

s.t.

其中

当为网络的最大流进，数学规划表示的就是最小费用最大流问题.2.最小费用流的求解过程

例14（继例13）用LINGO软件求解例13.

解：按照最小费用流的数学规划写出相应的LINGO程序，程序名：exam0814.lg4.MODEL:1]sets:2]nodes/s,1,2,3,4,t/:d;3]arcs(nodes,nodes)/4]s,1s,21,21,32,43,23,t4,34,t/:c,u,f;5]endsets6]data:7]d=140000-14;

8]c=285231647;

9]u=8759925610;10]enddata11]min=@sum(arcs:c*f);

12]@for(nodes(i)|i#ne#1#and#i#ne#@size(nodes):13]@sum(arcs(i,j):f(i,j))-@sum(arcs(j,i):f(j,i))=d(i));14]@sum(arcs(i,j)|i#eq#1:f(i,j))=d(1);15]@for(arcs:@bnd(0,f,u));END

程序的第11]行是目标函数(25),第12],13],14]行是约束条件(26),第15]行是约束的上下界(27).LINGO软件的计算结果（仅保留流值)如下:Globaloptimalsolutionfoundatiteration:3Objectivevalue:205.0000VariableValueReducedCostF(S,1)8.000000-1.000000F(S,2)6.0000000.000000F(1,2)1.0000000.000000F(1,3)7.0000000.000000F(2,4)9.0000000.000000F(3,2)2.000000-2.000000F(3,T)5.000000-7.000000F(4,T)9.0000000.000000因此，最大流的最小费用是205单位.而原最大流费用为210单位，原方案并不是最优的.3最优连线问题与旅行商问题本节内容导航

本节概述

3.1最优连线问题

3.2旅行商问题

本节内容概述

最优连线问题也是最小生成树问题(MinimumSpaningTreeProblem)是求网络中长度最小的生成树,旅行商问题(TravelingSalesmanProblem)也称货郎担问题，是求最优的Hamilton圈(HamiltonianCycle).这两个问题是图论或组合优化中十分重要的问题，有着各自的解决方法，例如，求解最小生成树问题常用“破圈法”或“贪心法”.但旅行商问题目前没有有效的算法求解，属于NP完全问题.当最小生成树问题或旅行商问题顶点的个数较大时，目前比较有效的方法是遗传算法.

本节介绍如何用LINGO软件求解最小生成树问题和旅行商问题，其基本思想是将所求问题化为0--1整数规划，因此当所求问题的顶点数较大时，计算速度可能会比较慢.返回导航

例15（最优连线问题）我国西部的SV地区共有1个城市（标记为1）和9个乡镇（标记为2--10）组成，该地区不久将用上天然气，其中城市1含有井源.现要设计一供气系统，使得从城市1到每个乡镇（2--10）都有一条管道相边，并且铺设的管子的量尽可能的少.图9给出了SV地区的地理位置图，表给出了城镇之间的距离.§3.1最优连线问题返回导航例15就是最优连线问题，实际上是求连接各城镇之间的最小生成树问题.Kruskal在1956年给出求最优生成树的一个算法（称Kruskal算法），该方法是“避圈法”的推广.

算法7.1

（Kruskal算法）

(1)选择边,使得尽可能小;(2)若已选定边,则从中选取边使得①为无圈图;②是满足①的尽可能小的权.(3)当(2)不能继续执行时,停止.

3.最优连线问题（最小生成树）的数学表达式将最优连线问题写成数学规划的形式还需要一定的技巧.设是两点与之间的距离，或1（1表示连接，0表示不连接），并假设顶点1是生成树的根.则数学表达式为:2.求最优生成树的算法4.最优连线问题的求解过程

例16

（继例15）已知SV地区各城镇之间距离（见表），求FSV地区（见图9）的最优连线.

解：按照数学规划问题写出相应的LINGO程序，程序名：exam0816.lg4.MODEL:1]sets:2]cities/1..10/:level;!level(i)=thelevelofcity;3]link(cities,cities):4]distance,!Thedistancematrix;5]x;!x(i,j)=1ifweuselinki,j;6]endsets7]data:!Distancematrix,itneednotbesymmetirc;8]distance=08591214121617229]809151681118142210]5907911712121711]91570317107151512]121693081061515

13]14811178091481614]12117101090861115]161812761480111116]1714121515861101017]2222171515161111100;18]enddata19]n=@size(cities);!Themodelsize;20]!Minimizetotaldistanceofthelinks;21]min=@sum(link(i,j)|i#ne#j:distance(i,j)*x(i,j));22]!Theremustbeanarcoutofcity1;23]@sum(cities(i)|i#gt#1:x(1,i))>=1;24]!Forcityi,exceptthebase(city1);25]@for(cities(i)|i#gt#1:26]!Itmustbeentered;27]@sum(cities(j)|j#ne#i:x(j,i))=1;28]!level(j)=levle(i)+1,ifwelinkjandi;29]@for(cities(j)|j#gt#1#and#j#ne#i:30]level(j)>=level(i)+x(i,j)31]-(n-2)*(1-x(i,j))+(n-3)*x(j,i);32]);33]!Thelevelofcityisatleast1butnomoren-1,34]andis1ifitlinkstobase(city1);35]@bnd(1,level(i),999999);36]level(i)<=n-1-(n-2)*x(1,i);37]);38]!Makethex's0/1;39]@for(link:@bin(x));END在上述程序中，利用水平变量(level)来保证所选的边不构成圈.计算结果如下：Globaloptimalsolutionfoundatiteration:34Objectivevalue:60.00000VariableValueReducedCostX(1,2)1.0000008.000000X(1,3)1.0000005.000000X(3,4)1.0000007.000000X(3,7)1.0000007.000000X(4,5)1.0000003.000000X(5,8)1.0000006.000000X(7,9)1.0000006.000000X(9,6)1.0000008.000000X(9,10)1.00000010.00000连接这10个城镇的最小距离为60公里，其连接情况如图10所示.图10SV地区的最优连线§3.2旅行商问题

例17

（旅行商问题）某公司计划在SV地区(见例15）作广告宣传，推销员从城市1出发，经过各个乡镇，再回到城市1，为节约开支，公司希望推销员走过这10个城镇的总距离最少.

解：例17属于旅行商问题，旅行商问题本质上是求最优Hamilton（哈密顿）回路.返回导航旅行商问题的数学表达式

例18（继例17）用LINGO软件求解例17.

解：按照数学规划问题写出相应的LINGO程序，程序名：exam0818.lg4.

MODEL:1]sets:2]cities/1..10/:level;!level(i)=thelevelofcity;3]link(cities,cities):4]distance,!Thedistancematrix;5]x;!x(i,j)=1ifweuselinki,j;6]endsets7]data:!Distancematrix,itneednotbesymmetirc;8]distance=08591214121617229]809151681118142210]5907911712121711]91570317107151512]12169308106151513]14811178091481614]12117101090861115]161812761480111116]1714121515861101017]2222171515161111100;18]enddata19]n=@size(cities);!Themodelsize;20]!Minimizetotaldistanceofthelinks;

21]min=@sum(link(i,j)|i#ne#j:distance(i,j)*x(i,j));22]!Forcityi;23]@for(cities(i):24]!Itmustbeentered;25]@sum(cities(j)|j#ne#i:x(j,i))=1;26]!I