图论模型的LINGO算法

优化建模图论与网络模型优化建模最短路问题(ShortestPathProblems)和最大流问题(MaxiumumFlowProblems)是图论另一类与优化有关的问题，对于这两在问题，实际上，图论中已有解决的方法，如最短路问题的求解方法有Dijkstra算法，最大流问题的求解方法有标号算法。这里主要讨论的是如何用LINGO软件来求解最短路和最大流问题，对于LINDO软件的求解方法，作者可以根据模型自己设计相应的程序，作为LINDO软件的训练和问题的练习.最短路问题和最大流问题优化建模§7.2.1最短路问题例7.7（最短路问题）在图7-3中，用点表示城市，现有共7个城市.点与点之间的连线表示城市间有道路相连.连线旁的数字表示道路的长度.现计划从城市到城市铺设一条天然气管道，请设计出最小价格管道铺设方案.12123,,,,,,ABBCCCDAD例7.7的本质是求从城市到城市的一条最短路.AD优化建模1.最短路问题的数学表达式假设有向图有n个顶点，现需要求从顶点1到顶点n的最短路.设0-1决策变量为xij,当xij=1,说明弧(i,j)位于顶点1至顶点j的最短路上；否则xij=0.其数学规划表达式为(,)11(,)(,)min;(14)1,1,..1,,;(15)0,1,.0,(,).ijijijEnnijjijjijEjiEijxistxxininxijE(16)优化建模2.最短路问题的求解过程前面我们接触到了最短路问题的求解，当时的求解方法是按照Dijkstra算法设计的，下面介绍的方法是按照规划问题(14)-(15)设计的.例7.8(继例7.7)求例7.7中，从城市A到城市D的最短路.解：写出相应的LINGO程序，程序名:exam0708.lg4.MODEL:1]!Wehaveanetworkof7cities.Wewanttofind2]thelengthoftheshortestroutefromcity1tocity7;3]优化建模4]sets:5]!Hereisourprimitivesetofsevencities;6]cities/A,B1,B2,C1,C2,C3,D/;7]8]!TheDerivedsetroadsliststheroadsthat9]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;END优化建模在上述程序中，21]句中的n=@size(cities)是计算集cities的个数，这里的计算结果是,这样编写方法目的在于提高程序的通用性.22]句表示目标函数(14),即求道路的最小权值.23],24]句表示约束(15)中的情况，即最短路中中间点的约束条件.25]句表示约束中的情况，即最短路中起点的约束.7n1,iin1i约束(15)中的情况，也就是最短路中终点的情况，没有列在程序中，因为终点的约束方程与前个方程相关.当然，如果你将此方程列入到LINGO程序中，计算时也不会出现任何问题，因为LINGOin优化建模软件可以自动删除描述线性规划可行解中的多余方程.LINGO软件计算结果（仅保留非零变量）如下Globaloptimalsolutionfoundatiteration:0Objectivevalue:6.000000VariableValueReducedCostX(A,B1)1.0000000.000000X(B1,C1)1.0000000.000000X(C1,D)1.0000000.000000即最短路是,最短路长为6个单位.11ABCD优化建模例7.9(设备更新问题)张先生打算购买一辆新轿车，轿车的售价是12万元人民币.轿车购买后，每年的各种保险费养护费等费用由表7-5所示.如果在5年之内，张先生将轿车售出，并再购买新年.5年之内的二手车销售价由表7-6所示.请你帮助张先生设计一种购买轿车的方案，使5年内用车的总费用最少.表7-5轿车的维护费车龄/年01234费用/万元245912优化建模表7-6二手车的售价车龄/年12345售价/万元76210分析：设备更新问题是动态规划的一类问题（事实上，最短路问题也是动态规划的一类问题）,这里借助于最短路方法解决设备更新问题.解：用6个点（1，2，3，4，5，6）表示各年的开始，各点之间的边从边表示左端点开始年至表示右端点结束所花的费用，这样构成购车消费的网络图，如图图7.4所示.优化建模记表示第年开始到年结束购车的总销费,即ijci1j1ijcijij在第年到第年结束轿车的维护费用+在年开始新车的购买费用-在第年开始二手的销售人优化建模由此得到12131415162324252634353621277,2412612,24512121,249512131,2495121044,21277,2412612,24512121,249512131,21277,2412612,245121cccccccccccc45465621,21277,2412612,21277.ccc优化建模写出相应的LINGO程序，程序名：exam0709.lg4MODEL:1]sets:2]nodes/1..6/;3]arcs(nodes,nodes)|&1#lt#&2:c,x;4]endsets5]data:6]c=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;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万.13561346例7.10（无向图的最短路问题）求图7-5中到的最短路.1v11v分析：不论是例7.7、例7.9还是第三章的例3.5处理的问题均属于有向图的最短路问题，本例是处理无向图的最短路问题，在处理方式上与有向图的最短路有一些差别.优化建模解：对于无向图的最短路问题，可以这样理解，从点到点和点到点的边看成有向弧，其他各条边均看成有不同方向的双弧，因此，可以按照前面介绍有向图的最短路问题来编程序，但按照这种方法编写LINGO程序相当边（弧）增加了一倍.这里选择邻接矩阵和赋权矩阵的方法编写LINGO程序.1viviv11v优化建模写出相应的LINGO程序，程序名：exam0710.lg4MODEL:1]sets:2]cities/1..11/;3]roads(cities,cities):p,w,x;4]endsets5]data:6]p=011100000007]001010000008]010111100009]0010001000010]01100101100优化建模11]0010101010012]0011010011013]0000100010114]0000111101115]0000001010116]00000000000;17]w=0281000000018]2060100000019]8607512000020]1070009000021]0150030290022]00103040600优化建模23]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.其它的处理方法基本上与有向图相同.P1v234,,vvv8910,,vvv11vWP用LINGO软件求解，得到（仅保留非零变量）Globaloptimalsolutionfoundatiteration:20Objectivevalue:13.00000VariableValueReducedCost优化建模X(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即最短路径为1256371011,最短路长度.为13优化建模§7.2.2最大流问题例7.11（最大流问题）现需要将城市s的石油通过管道运送到城市t，中间有4个中转站和,城市与中转站的连接以及管道的容量如图7-6所示，求从城市s到城市t的最大流.123,,vvv4v优化建模图7-6给出的有一个源和一个汇的网络.网络中每一条边有一个容量,除此之外,对边还有一个通过边的流(Flow),记为.显然,边上的流量不会超过该边上的容量,即G(,)uv(,)cuv(,)uv(,)fuv(,)uv(,)fuv(,)cuv0(,)(,)(17)fuvcuv优化建模称满足不等式（17）的网络是相容的.对于所有中间顶点,流入的总量应等于流出的总量,即:G(,)cuv(,)(,)(18)vVvVfuvfvu一个网络的流量(Valueofflow)值定义为从源流出的总流量,即Gs()(,)(19)vVVffsv由式(18)和(19)式可以看出,的流量值也为流入汇的总流量,即:ft优化建模()(,)(20)vVVffvt