资源描述：
《最短路问题和最大流问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、7.2最短路问题和最大流问题本节内容导航本节概述7.2.1最短路问题7.2.2最大流问题7.2.3最小费与最大流问题本节内容概述最短路问题(ShortestPathProblems)和最大流问题(MaxiumumFlowProblems)是图论另一类与优化有关的问题，对于这两在问题，实际上，图论中已有解决的方法，如最短路问题的求解方法有Dijkstra算法，最大流问题的求解方法有标号算法.这里主要讨论的是如何用LINGO软件来求解最短路和最大流问题，对于LINDO软件的求解方法，作者可以根据模型自己设计相应的程序，作为LINDO软件的训练和问题的练习.返回导航§7.2.1最短路问题例7.
2、7（最短路问题）在图7-3中，用点表示城市，现有共7个城市.点与点之间的连线表示城市间有道路相连.连线旁的数字表示道路的长度.现计划从城市到城市铺设一条天然气管道，请设计出最小价格管道铺设方案.例7.7的本质是求从城市到城市的一条最短路.为便于讨论，下面给出有关概念的明确定义.返回导航1.图的基本概念定义7.2(子图与赋权图)定义7.3(迹和路以及圈)定义7.4（邻接矩阵和赋权矩阵）如果,则称与邻接,具有个顶点的图的邻接矩阵(AdjacencyMatrix)是一个阶矩阵,其分量为个顶点的赋权图的赋权矩阵是一个阶矩阵其分量为定理7.1如果存在到的途径,则一定存在到的路.如果图的顶点个数为,
3、则这个路的长度小于等于.2.最短路问题的数学表达式假设图有n个顶点，现需要求从顶点1到顶点的最短路.设决策变量为,当,说明弧位于顶点1至顶点的路上；否则.其数学规划表达式为3.最短路问题的求解过程在第三章中（例3.5）我们接触到了最短路问题的求解，当时的求解方法是按照Dijkstra算法设计的，下面介绍的方法是按照规划问题设计的.例7.8(继例7.7)求例7.7中，从城市A到城市D的最短路.解：写出相应的LINGO程序，程序名:exam0708.lg4.MODEL:1]!Wehaveanetworkof7cities.Wewanttofind2]thelengthoftheshortes
4、troutefromcity1tocity7;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]!Herearethedistancesth
5、atcorrespond17]toabovelinks;18]w=24331231134;19]enddata20]21]n=@size(cities);!Thenumberofcities;22]min=@sum(roads:w*x);23]@for(cities(i)
6、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)
7、i#eq#1:x(i,j))=1;END在上述程序中，21]句中的n=@size(cities)是计算集cities的个数，这里的计算结果是,
8、这样编写方法目的在于提高程序的通用性.22]句表示目标函数(14),即求道路的最小权值.23],24]句表示约束(15)中的情况，即最短路中中间点的约束条件.25]句表示约束中的情况，即最短路中起点的约束.约束(15)中的情况，也就是最短路中终点的情况，没有列在程序中，因为终点的约束方程与前个方程相关.当然，如果你将此方程列入到LINGO程序中，计算时也不会出现任何问题，因为LINGO软件可以自动删除描述线性规划可行解中的多余方程.LINGO软件计算结果（仅保留非零变量）如下Globaloptimalsolutionfoundatiteration:0Objectivevalue:6.0
9、00000VariableValueReducedCostX(A,B1)1.0000000.000000X(B1,C1)1.0000000.000000X(C1,D)1.0000000.000000即最短路是,最短路长为6个单位.例7.9(设备更新问题)张先生打算购买一辆新轿车，轿车的售价是12万元人民币.轿车购买后，每年的各种保险费养护费等费用由表7-5所示.如果在5年之内，张先生将轿车售出，并再购买新年.5年之内的二手车销售价由
