资源描述：
《图论模型的LINGO算法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、图论与网络模型最短路问题(ShortestPathProblems)和最大流问题(MaxiumumFlowProblems)是图论另一类与优化有关的问题，对于这两在问题，实际上，图论中已有解决的方法，如最短路问题的求解方法有Dijkstra算法，最大流问题的求解方法有标号算法。这里主要讨论的是如何用LINGO软件来求解最短路和最大流问题，对于LINDO软件的求解方法，作者可以根据模型自己设计相应的程序，作为LINDO软件的训练和问题的练习.最短路问题和最大流问题§7.2.1最短路问题例7.7（最短路问题）在图7-3中，用点表示城市，现有共7个城市.点与点之间的连线
2、表示城市间有道路相连.连线旁的数字表示道路的长度.现计划从城市到城市铺设一条天然气管道，请设计出最小价格管道铺设方案.例7.7的本质是求从城市到城市的一条最短路.1.最短路问题的数学表达式假设有向图有n个顶点，现需要求从顶点1到顶点n的最短路.设0-1决策变量为xij,当xij=1,说明弧(i,j)位于顶点1至顶点j的最短路上；否则xij=0.其数学规划表达式为2.最短路问题的求解过程前面我们接触到了最短路问题的求解，当时的求解方法是按照Dijkstra算法设计的，下面介绍的方法是按照规划问题(14)-(15)设计的.例7.8(继例7.7)求例7.7中，从城市A到
3、城市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]!TheDerivedset"roads"liststheroadsthat9]existbetweenthecities;10]roads(cit
4、ies,cities)/11]A,B1A,B2B1,C1B1,C2B1,C3B2,C1B2,C2B2,C312]C1,DC2,DC3,D/:w,x;13]endsets14]15]data:16]!Herearethedistancesthatcorrespond17]!toabovelinks;18]w=24331231134;19]enddata20]21]n=@size(cities);!Thenumberofcities;22]min=@sum(roads:w*x);23]@for(cities(i)
5、i#ne#1#and#i#ne#n:24]@sum(r
6、oads(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的个数，这里的计算结果是,这样编写方法目的在于提高程序的通用性.22]句表示目标函数(14),即求道路的最小权值.23],24]句表示约束(15)中的情况，即最短路中中间点的约束条件.25]句表示约束中的情况，即最短路中起点的约束.约束(15)中的情况，也就是最短路中终点的情况，没有列在程序中，因为终点的约束方程与前个方程相关.
8、当然，如果你将此方程列入到LINGO程序中，计算时也不会出现任何问题，因为LINGO软件可以自动删除描述线性规划可行解中的多余方程.LINGO软件计算结果（仅保留非零变量）如下Globaloptimalsolutionfoundatiteration:0Objectivevalue:6.000000VariableValueReducedCostX(A,B1)1.0000000.000000X(B1,C1)1.0000000.000000X(C1,D)1.0000000.000000即最短路是,最短路长为6个单位.例7.9(设备更新问题)张先生打算购买一辆新轿车，
9、轿车的售价是12万元人民币.轿车购买后，每年的各种保险费养护费等费用由表7-5所示.如果在5年之内，张先生将轿车售出，并再购买新年.5年之内的二手车销售价由表7-6所示.请你帮助张先生设计一种购买轿车的方案，使5年内用车的总费用最少.表7-5轿车的维护费车龄/年01234费用/万元245912表7-6二手车的售价车龄/年12345售价/万元76210分析：设备更新问题是动态规划的一类问题（事实上，最短路问题也是动态规划的一类问题）,这里借助于最短路方法解决设备更新问题.解：用6个点（1，2，3，4，5，6）表示各年的开始，各点之间的边从边表示左端点开始年至表示右端
10、点结束所花
