优 化 建 模图论与网络模型优 化 建 模最短路问题(Shortest Path Problems)和最大流问 题(Maxiumum Flow Problems)是图论另一类与优化 有关的问题，对于这两在问题，实际上，图论中已有 解决的方法，如最短路问题的求解方法有Dijkstra算 法，最大流问题的求解方法有标号算法这里主要讨 论的是如何用LINGO软件来求解最短路和最大流问 题，对于LINDO软件的求解方法，作者可以根据模 型自己设计相应的程序，作为LINDO软件的训练和 问题的练习.最短路问题和最大流问题优 化 建 模§7.2.1 最短路问题例7.7 （最短路问题） 在图 7-3中，用点表示城市 ，现有 共7个城市.点与点之间的连线表 示城市间有道路相连.连线旁的数字表示道路的长度. 现计划从城市 到城市 铺设一条天然气管道，请设 计出最小价格管道铺设方案. 例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到城市D的 最短路. 解：写出相应的LINGO程序，程序名: exam0708.lg4. MODEL:1]! We have a network of 7 cities. We want to find2] the length of the shortest route from city 1 to city 7;3]优 化 建 模4]sets:5] ! Here is our primitive set of seven cities;6] cities/A, B1, B2, C1, C2, C3, D/;7]8] ! The Derived set “roads“ lists the roads that9] exist between the cities;10] roads(cities, cities)/11] A,B1 A,B2 B1,C1 B1,C2 B1,C3 B2,C1 B2,C2 B2,C312] C1,D C2,D C3,D/: w, x;13]endsets14]15]data:16] ! Here are the distances that correspond优 化 建 模17] !to above links;18] w = 2 4 3 3 1 2 3 1 1 3 4;19]enddata20]21]n=@size(cities); ! The number of cities;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]句表示约束中 的情况，即最短路中 起点的约束.约束(15)中 的情况，也就是最短路中终点的情况，没有列在程序中，因为终点的约束方程与前 个方程相关.当然，如果你将此方程列入到LINGO 程序中，计算时也不会出现任何问题，因为LINGO 优 化 建 模软件可以自动删除描述线性规划可行解中的多 余方程. LINGO软件计算结果（仅保留非零变量）如下Global optimal solution found at iteration: 0Objective value: 6.000000Variable Value Reduced CostX( A, B1) 1.000000 0.000000X( B1, C1) 1.000000 0.000000X( C1, D) 1.000000 0.000000即最短路是 , 最短路长为6个单位.优 化 建 模例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所示.优 化 建 模记 表示第 年开始到 年结束购车的 总销费, 即优 化 建 模由此得到优 化 建 模写出相应的LINGO程序，程序名： exam0709.lg4MODEL:1]sets:2] nodes/16/;3] arcs(nodes, nodes)|4]endsets5]data:6] c= 7 12 21 31 447] 7 12 21 318] 7 12 219] 7 1210] 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]句中3] roads(cities, cities): p, w, x;4]endsets5]data:6] p = 0 1 1 1 0 0 0 0 0 0 07] 0 0 1 0 1 0 0 0 0 0 08] 0 1 0 1 1 1 1 0 0 0 09] 0 0 1 0 0 0 1 0 0 0 010] 0 1 1 0 0 1 0 1 1 0 0优 化 建 模11] 0 0 1 0 1 0 1 0 1 0 012] 0 0 1 1 0 1 0 0 1 1 013] 0 0 0 0 1 0 0 0 1 0 114] 0 0 0 0 1 1 1 1 0 1 115] 0 0 0 0 0 0 1 0 1 0 116] 0 0 0 0 0 0 0 0 0 0 0;17] w = 0 2 8 1 0 0 0 0 0 0 018] 2 0 6 0 1 0 0 0 0 0 019] 8 6 0 7 5 1 2 0 0 0 020] 1 0 7 0 0 0 9 0 0 0 021] 0 1 5 0 0 3 0 2 9 0 022] 0 0 1 0 3 0 4 0 6 0 0优 化 建 模23] 0 0 2 9 0 4 0 0 3 1 024] 0 0 0 0 2 0 0 0 7 0 925] 0 0 0 0 9 6 3 7 0 1 226] 0 0 0 0 0 0 1 0 1 0 427] 0 0 0 0 0 0 0 9 2 4 0;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软件求解，得到（仅保留非零变量）Global optimal solution found at iteration: 2 0Objective value: 13.00000 Variable Value Reduced Cost优 化 建 模X( 1, 2) 1.000000 0.000000X( 2, 5) 1.000000 0.000000X( 3, 7) 1.000000 0.000000X( 5, 6) 1.000000 0.000000X( 6, 3) 1.000000 0.000000X( 7, 10) 1.000000 0.000000X( 9, 11) 1.000000 0.000000X( 10, 9) 1.000000 0.000000即最短路径为, 最短路长度.为13优 化 建 模 § 7.2.2 最大流问题例7.11（最大流问题） 现需要将城市s 的石油通过管道运送到城市t，中间有4个中 转站 和 , 城市与中转站的连接以 及管道的容量如图7-6所示，求从城市s到城 市t的最大流.优 化 建 模图7-6给出的有一个源和一个汇的网络.网络 中每一条边 有一个容量 , 除此之外 ,对边 还有一个通过边的流(Flow), 记为 .显然, 边 上的流量 不会超过该边上的容量,。