运筹与优化+10.ppt

第十讲图论与网络模型 凯里学院文化素质选修课教案 欢迎各位参加运筹与优化的学习 凯里学院理学院潘东云2010年3月1日 本章内容概述本章介绍图论与网络 GraphTheoryandNetwork 的有关优化问题模型 在这里 我们并不打算全面系统介绍图论与网络的知识 而着重介绍与LINDO LINGO软件有关的组合优化模型和相应的求解过程 如果读者打算深入地了解图论与网络的更全面的知识 请参阅图论或运筹学中的有关书籍 LINDO软件和LINGO软件可以求解一些著名的组合优化问题 这包括最短路问题 最大流问题 运输和转运问题 最优匹配和最优指派问题 最优连线或最小生成树问题 旅行商问题 关键路线法与计划评审方法等 10 1运输问题与转运问题 本节内容导航10 1 1运输问题10 1 2指派问题10 1 3转运问题 10 1 1运输问题运输问题 TransportationProblem 是图论与网络中的一个重要问题 也是一个典型的线性规划问题 例10 1 运输问题 返回导航 例10 1就是典型的运输问题 图7 1给出了个产地 个销地运输问题的图形 关于它的求解方法有两类 一类是按照图论的方法求解 另一类是化成线性规划问题 这里介绍第二类方法 即用LINDO或LINGO软件求解运输问题 但为便于后面的叙述 先给出图论中有关图的部分定义 图10 1 个产地 个销售地运输问题的图形 1 图的基本定义从直观上看 所谓图是由点和边组成的图形 如图10 1所示 下面我们给出图的定义 注 通常有向图的边称为弧 由弧构成的集记为因此 有向图记为 而无向图记为 为方便起见 在后面的论述中 有时也用表示有向图 在无向图中 每条至多有一条边的图称为简单图 SimpleGraph 若每一对不同的顶点都有一条边相连的简单图称为完全图 CompleteGraph 若一个图中的顶点集可以分解为两个子集和 使得任何一条边都有一个端点在中 另一个端点在中 这种图称为二部图或偶图 BipartiteGraph 运输问题所构成的图7 1是偶图 2 运输问题的数学表达式 第个产地的运出量应小于或等于该地的生产量 即 第个销地的运入量应等于该地的需求量 即 因此 运输问题的数学表达式为 称具有形如式的线性规划问题为运输问题 3 运输问题的求解过程为了便于讨论 以一个运输问题实例的求解过程来介绍如何用LINDO或LINGO软件求解运输问题模型 例7 2 继例7 1 设即为有3个产地和4个销地的运输问题 其产量 销量及单位运费如表7 1所示 试求总运费最少的运输方案 以及总运费 解 从前面的分析来看 运输问题属于线性规划问题 因此 不论是LINDO软件或LINGO软件都可以对该问题求解 为了便于比较两种软件的优缺点 以及各自的特点 我们用两种软件分别求解该运输问题 首先写出LINDO软件的模型 程序 程序名 exam0702 ltx 3Warehouse 4CustomerTransportationProblem Theobjectivemin6x11 2x12 6x13 7x14 4x21 9x22 5x23 3x24 8x31 8x32 x33 5x34subjectto Thesupplyconstraints2 x11 x12 x13 x14 303 x21 x22 x23 x24 254 x31 x32 x33 x34 21 Thedemandconstraints5 x11 x21 x31 156 x12 x22 x32 177 x13 x23 x33 228 x14 x24 x34 12end LINDO软件的计算结果如下 LPOPTIMUMFOUNDATSTEP6OBJECTIVEFUNCTIONVALUE1 161 0000VARIABLEVALUEREDUCEDCOSTX112 0000000 000000X1217 0000000 000000X131 0000000 000000X140 0000002 000000X2113 0000000 000000X220 0000009 000000X230 0000001 000000 X2412 0000000 000000X310 0000007 000000X320 00000011 000000X3321 0000000 000000X340 0000005 000000ROWSLACKORSURPLUSDUALPRICES2 10 0000000 0000003 0 0000002 0000004 0 0000005 0000005 0 000000 6 0000006 0 000000 2 0000007 0 000000 6 0000008 0 000000 5 000000NO ITERATIONS 6 事实上 我们关心更多的是那些非零变量 因此 可选择LINDO中的命令 具体方法见第二章的2 3节 只列出非零变量 OBJECTIVEFUNCTIONVALUE1 161 0000VARIABLEVALUEREDUCEDCOSTX112 0000000 000000X1217 0000000 000000 X131 0000000 000000X2113 0000000 000000X2412 0000000 000000X3321 0000000 000000ROWSLACKORSURPLUSDUALPRICES3 0 0000002 0000004 0 0000005 0000005 0 000000 6 0000006 0 000000 2 0000007 0 000000 6 0000008 0 000000 5 000000NO ITERATIONS 6 LINDO软件虽然给出最优解 但上述模型还存在着缺点 例如 上述方法不便于推广的一般情况 特别是当产地和销地的个数较多时 情况更为突出 下面写出求解该问题的LINGO程序 并在程序中用到在第三章介绍的集与数据段 以及相关的循环函数 写出相应的LINGO程序 程序名 exam0702 lg4 MODEL 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 从上述求解过程来看 两种软件的计算结果是相同的 但由于LINGO软件中采用集 数据段和循环函数的编写方式 因此更便于程序推广到一般形式使用 例如 只需修改运输问题中产地和销地的个数 以及参数a b c的值 就可以求解任何运输问题 所以 从程序通用性的角度来看 推荐大家采用LINGO软件来求解运输问题 7 1 2指派问题 例7 3 指派问题 设有n个人 计划作n项工作 其中表示第i个人做第j项工作的收益 现求一种指派方式 使得每个人完成一项工作 使总收益最大 例7 3就是指派问题 AssignmentProblem 指派问题也是图论中的重要问题 有相应的求解方法 如匈牙利算法 从问题的形式来看 指派问题是运输问题的特例 也可以看成0 1规划问题 返回导航 1 指派问题的数学表达式 设变量为 当第个人作第项工作时 否则 因此 相应的线性规划问题为 2 指派问题的求解过程分别用LINDO软件和LINGO软件求解指派问题 并对两种软件的求解方法与各自的优缺点进行比较 例7 4 继例7 3 考虑例7 3中的情况 即6个人做6项工作的最优指派问题 其收益矩阵如表7 2所示 Assignmentmodel Maximizevalveofassignmentsmax20 x11 15x12 16x13 5x14 4x15 7x16 17x21 15x22 33x23 12x24 8x25 6x26 9x31 12x32 18x33 16x34 30 x35 13x36 12x41 8x42 11x43 27x44 19x45 14x46 99x51 7x52 10 x53 21x54 10 x55 32x56 99x61 99x62 99x63 6x64 11x65 13x66subjectto 解 与运输问题一样 先用LINDO软件求解 给出LINGO程序 程序名exam0704 ltx Eachpersonmustbeassignedtosomejobx11 x12 x13 x14 x15 x16 1x21 x22 x23 x24 x25 x26 1x31 x32 x33 x34 x35 x36 1x41 x42 x43 x44 x45 x46 1x51 x52 x53 x54 x55 x56 1x61 x62 x63 x64 x65 x66 1 Eachjobmustreceiveanassignmentx11 x21 x31 x41 x51 x61 1x12 x22 x32 x42 x52 x62 1x13 x23 x33 x43 x53 x63 1x14 x24 x34 x44 x54 x64 1x15 x25 x35 x45 x55 x65 1x16 x26 x36 x46 x56 x66 1end 在上述程序中 x51 x61 x62 x63前的系数均为 99 这是因为某人无法做某项工作可以某人做该项工作的收益是 在计算中通常取一个较大的负数就可以 上述程序也没有说明决策变量是0 1型变量 这是因为对于此类问题线性规划理论已保证了变量的取值只可能是0或1 LINDO软件给出的计算结果如下 只列出非零变量 OBJECTIVEFUNCTIONVALUE1 135 0000VARIABLEVALUEREDUCEDCOSTX111 0000000 000000X231 0000000 000000X321 0000000 000000X441 0000000 000000X561 0000000 000000X651 0000000 000000ROWSLACKORSURPLUSDUALPRICES 2 0 0000003 0000003 0 00000015 0000005 0 000000 4 0000007 0 000000 19 0000008 0 00000017 0000009 0 00000012 00000010 0 00000018 00000011 0 00000031 00000012 0 00000030 00000013 0 00000032 000000NO ITERATIONS 20 即第1个人做第1项工作 第2个人做第3项工作 第3个人做第2项工作 第4个人做第4项工作 第5个人做第6项工作 第6个人做第5项工作 总效益值为135 下面用LINGO程序再求解此问题 程序中仍然用到集 数据段和循环函数 写出相应的LINGO程序 程序名exam0704 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 从上述两个例子 可以看出LINGO软件在处理问题方面要大优于LINDO软件 而且便于推广 只是在编程方面 LINGO程序的编写稍复杂一些 在后面的问题求解中 绝大多数的求解方法是采用LINGO软件计算 对于指派问题 也可以考虑人数不工作数不相等的情况 和考虑支付最小的情况 第一章的例1 5 混合泳接力队员选拔问题 就是属于这一类情况 例7 5 继例1 5 用LINGO软件求解例1 5 解 在第二章的例2 7给出了该问题的LINDO软件求解方法 这里给出LINGO软件的求解方法 读者可根据问题的求解过程来考查两种软件求解问题的方法 以及每种软件各自的特点 为了便于编写程序 将5名队员的4种泳姿的百米平均成绩重新列在表7 3中 按第1章所列的规划问题 第 章中的式 1 25 式 1 28 写出相应的LINGO程序 程序名 exam0705 lg4 MODEL 1 5personsand4jobsAssignmentProblem 2 sets 3 Person 1 5 4 Job 1 4 5 Assign Person Job c x 6 endsets7 Herearetheparameters 8 data 9 c 66 8 75 6 87 58 6 10 57 2 66 66 4 53 11 78 67 8 84 6 59 4 12 70 74 2 69 6 57 2 13 67 4 71 83 8 62 4 14 enddata15 Theobjective 16 OBJ min sum Assign c x 17 Thesupplyconstraints 18 for Person i SUP 19 sum Job j x i j 1 20 Thedemandconstraints 21 for Job j DEM 22 sum Person i x i j 1 END该程序同样没有限制是0 1型变量 下面列出LINGO软件计算结果 仅保留非零变量 Globaloptimalsolutionfoundatiteration 9Objectivevalue 253 2000VariableValueReducedCostX 1 4 1 0000000 000000X 2 1 1 0000000 000000X 3 2 1 0000000 000000X 4 3 1 0000000 000000RowSlackorSurplusDualPriceOBJ253 2000 1 000000SUP 5 1 0000000 000000 即甲游自由泳 乙游蝶泳 丙游仰泳 丁游蛙泳 没有被选拔上 平均成绩为 4 13 2 7 1 3转运问题 所谓转运问题 TransshipmentProblem 实质上是运输问题的一种 其区别就在于不是将工厂生产出的产品直接送的顾客手中 而是要经过某些中间环节 如仓库 配送中心等 图7 2表示的是3水平分配 即有一个中间环节 的转运问题 返回导航 1 转运问题的数学表达式 1 转运问题的求解方法 以一个例子为例 给出求解转运问题的两种求解方法 例7 6 转运问题 设有两个工厂A B 产量分别为9 8个单位 四个顾客1 2 3 4 需求量分别为3 5 4 5 和三个仓库x y z 其中工厂到仓库 仓库到顾客的运费单价分别由表7 4所示 试求总运费最少的运输方案 以及总运费 表7 4工厂到仓库 仓库到顾客的运费单价 说明 其中 表示两地无道路通行 解 写出相应的LINGO程序 程序名 exam0706a lg4 MODEL 1 2plants 3warehousesand4customers2 TransshipmentProblem 3 sets 4 Plant A B produce 5 Warhouse x y z 6 Customer 1 4 require 7 LinkI Plant Warhouse cI xI 8 LinkII Warhouse Customer cII xII 9 endsets10 Herearetheparameters 11 data 12 produce 9 8 13 require 3 5 4 5 14 cI 1 2 100 15 3 1 2 16 cII 5 7 100 100 17 9 6 7 100 18 100 8 7 4 19 enddata20 Theobjective 21 OBJ min sum LinkI cI xI sum LinkII cII xII 22 Thesupplyconstraints 23 for Plant i SUP 24 sum Warhouse j xI i j produce i 25 Thewarhouseconstraints 26 for Warhouse j MID 27 sum Plant i xI i j sum Customer k xII j k 28 Thedemandconstraints 29 for Customer k DEM 30 sum Warhouse j xII j k require k END 在上述程序中 由14 至15 行定义的cI是工厂到仓库的运费 由16 至18 行定义的cII是仓库到顾客的运费 我们的目标是求最小运费 因此当两点无道路时 认为是运费无穷大 为了便于计算 只要取较大的数值就可以了 这里的取值为100 程序的第21 行表示目标函数 7 9 第23 24 行表示约束条件 7 10 第26 27 行表示约束条件 11 第29 30 行表示约束条件 7 12 LINGO软件的计算结果 仅保留非零变量 如下 Globaloptimalsolutionfoundatiteration 9Objectivevalue 121 0000VariableValueReducedCostXI A X 3 0000000 000000XI A Y 6 0000000 000000XI B Y 3 0000000 000000 XI B Z 5 0000000 000000XII X 1 3 0000000 000000XII Y 2 5 0000000 000000XII Y 3 4 0000000 000000XII Z 4 5 0000000 000000 即工厂A向仓库x y z分别运输3 6 0个单位 工厂B向仓库x y z分别运输0 3 5个单位 仓库x向顾客1运输3个单位 仓库y向顾客2 3分别运输5 4个单位 仓库z向顾客4运输5个单位 总运费为121个单位 如果将转运问题看成运输问题 可以得到另一种程序的编写方法 程序名 exam0706b lg4 MODEL 1 2plants 3warehousesand4customers2 TransshipmentProblem 3 sets 4 Plant A B produce 5 Warhouse x y z 6 Customer 1 4 require 7 Link Plant Warhouse Customer poss cost x 8 endsets9 Herearetheparameters 10 data 11 produce 9 8 12 require 3 5 4 5 13 poss 1 1 0 0 14 1 1 1 0 15 0 0 0 0 16 1 1 0 0 17 1 1 1 0 18 0 1 1 1 19 cost 6 8 0 0 20 11 8 9 0 21 0 0 0 0 22 8 10 0 0 23 10 7 8 0 24 0 10 9 6 25 enddata26 Theobjective 27 OBJ min sum Link poss cost x 28 Thesupplyconstraints 29 for Plant i SUP 30 sum Warhouse j 31 sum Customer k poss i j k x i j k produce i 32 Thedemandconstraints 33 for Customer k DEM 34 sum Plant i 35 sum Warhouse j poss i j k x i j k require k END 排列的 由于引入了参数poss 当两点间无路时 可以定义其长度为0 实际上可以定义成任何数 因为此时poss对应的位置为0 因此 0乘任何数均为0 程序中采用的其他方法基本上与运输问题是相同的 LINGO软件的计算结果 仅保留非零变量 如下 Globaloptimalsolutionfoundatiteration 11Objectivevalue 121 0000VariableValueReducedCostX A X 1 3 0000000 000000X A Y 2 5 0000000 000000X A Y 3 1 0000000 000000X B Y 3 3 0000000 000000X B Z 4 5 0000000 000000 从上述求解过程可以看出 转运问题仍属于线性规划问题 因此也可以用LINDO软件求解 读者可将此问题作为LINDO软件的训练 用LINDO软件求解例7 6 并与LINGO软件的结果相比较 7 2最短路问题和最大流问题 本节内容导航本节概述7 2 1最短路问题7 2 2最大流问题7 2 3最小费与最大流问题 本节内容概述最短路问题 ShortestPathProblems 和最大流问题 MaxiumumFlowProblems 是图论另一类与优化有关的问题 对于这两在问题 实际上 图论中已有解决的方法 如最短路问题的求解方法有Dijkstra算法 最大流问题的求解方法有标号算法 这里主要讨论的是如何用LINGO软件来求解最短路和最大流问题 对于LINDO软件的求解方法 作者可以根据模型自己设计相应的程序 作为LINDO软件的训练和问题的练习 返回导航 7 2 1最短路问题 例7 7 最短路问题 在图7 3中 用点表示城市 现有共7个城市 点与点之间的连线表示城市间有道路相连 连线旁的数字表示道路的长度 现计划从城市到城市铺设一条天然气管道 请设计出最小价格管道铺设方案 例7 7的本质是求从城市到城市的一条最短路 为便于讨论 下面给出有关概念的明确定义 返回导航 1 图的基本概念 定义7 2 子图与赋权图 定义7 3 迹和路以及圈 定义7 4 邻接矩阵和赋权矩阵 如果 则称与邻接 具有个顶点的图的邻接矩阵 AdjacencyMatrix 是一个阶矩阵 其分量为 个顶点的赋权图的赋权矩阵是一个阶矩阵 其分量为 定理7 1如果存在到的途径 则一定存在到的路 如果图的顶点个数为 则这个路的长度小于等于 2 最短路问题的数学表达式 假设图有个顶点 现需要求从顶点1到顶点的最短路 设决策变量为 当 说明弧位于顶点1至顶点的路上 否则 其数学规划表达式为 3 最短路问题的求解过程 在第三章中 例3 5 我们接触到了最短路问题的求解 当时的求解方法是按照Dijkstra算法设计的 下面介绍的方法是按照规划问题设计的 例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 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 END 在上述程序中 21 句中的n size cities 是计算集cities的个数 这里的计算结果是 这样编写方法目的在于提高程序的通用性 22 句表示目标函数 14 即求道路的最小权值 23 24 句表示约束 15 中的情况 即最短路中中间点的约束条件 25 句表示约束中的情况 即最短路中起点的约束 约束 15 中的情况 也就是最短路中终点的情况 没有列在程序中 因为终点的约束方程与前个方程相关 当然 如果你将此方程列入到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 设备更新问题 张先生打算购买一辆新轿车 轿车的售价是12万元人民币 轿车购买后 每年的各种保险费养护费等费用由表7 5所示 如果在5年之内 张先生将轿车售出 并再购买新年 5年之内的二手车销售价由表7 6所示 请你帮助张先生设计一种购买轿车的方案 使5年内用车的总费用最少 表7 5轿车的维护费 表7 6二手车的售价 分析 设备更新问题是动态规划的一类问题 事实上 最短路问题也是动态规划的一类问题 这里借助于最短路方法解决设备更新问题 解 用6个点 1 2 3 4 5 6 表示各年的开始 各点之间的边从边表示左端点开始年至表示右端点结束所花的费用 这样构成购车消费的网络图 如图图7 4所示 记表示第年开始到年结束购车的总销费 即 由此得到 写出相应的LINGO程序 程序名 exam0709 lg4 MODEL 1 sets 2 nodes 1 6 3 arcs nodes nodes 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万 例7 10 无向图的最短路问题 求图7 5中到的最短路 分析 不论是例7 7 例7 9还是第三章的例3 5处理的问题均属于有向图的最短路问题 本例是处理无向图的最短路问题 在处理方式上与有向图的最短路有一些差别 解 对于无向图的最短路问题 可以这样理解 从点到点和点到点的边看成有向弧 其他各条边均看成有不同方向的双弧 因此 可以按照前面介绍有向图的最短路问题来编程序 但按照这种方法编写LINGO程序相当边 弧 增加了一倍 这里选择邻接矩阵和赋权矩阵的方法编写LINGO程序 写出相应的LINGO程序 程序名 exam0710 lg4 MODEL 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 其它的处理方法基本上与有向图相同 用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 即最短路径为 最短路长度 为13 7 2 2最大流问题 例7 11 最大流问题 现需要将城市s的石油通过管道运送到城市t 中间有4个中转站和 城市与中转站的连接以及管道的容量如图7 6所示 求从城市s到城市t的最大流 返回导航 图7 6给出的有一个源和一个汇的网络 网络中每一条边有一个容量 除此之外 对边还有一个通过边的流 Flow 记为 显然 边上的流量不会超过该边上的容量 即 称满足不等式 17 的网络是相容的 对于所有中间顶点 流入的总量应等于流出的总量 即 一个网络的流量 Valueofflow 值定义为从源流出的总流量 即 由式 18 和 19 式可以看出 的流量值也为流入汇的总流量 即 称满足式 21 的网络为守恒的 定义7 6如果流满足不等式 17 和式 21 则称流是可行的 如果存在可行流 使得对所有的可行流均有 则称为最大流 MaximumFlow 2 最大流问题的数学规划表示形式通过上述推导得到最大流的数学规划表达式 3 最大流问题的求解方法 下面用例子说明 如何用LINGO软件求解最大流问题 例7 12 继例7 11 用LINGO软件求解例7 11 解 写出相应的LINGO程序 程序名 m0712 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 endsets 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 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 000000F 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 在上述程序中 由于使用了邻接矩阵 当两点之间无弧时 定义弧容量为零 计算结果与前面程序的结果完全相同 这里就不再列出了 7 2 3最小费用最大流问题 例7 13 最小费用最大流问题 续例7 11 由于输油管道的长短不一 或地质等原因 使每条管道上运输费用也不相同 因此 除考虑输油管道的最大流外 还需要考虑输油管道输送最大流的最小费用 图7 8所示是带有运费的网络 其中第1个数字是网络的容量 第2个数字是网络的单位运费 返回导航 例7 13所提出的问题就是最小费用最大流问题 Minimum costmaximumflow 即考虑网络在最大流情况下的最小费用 例7 12虽然给出了例7 11最大流一组方案 但它是不是关于费用的最优方案呢 这还需要进一步讨论 1 最小费用流的数学表达式 min s t 其中 当为网络的最大流进 数学规划表示的就是最小费用最大流问题 2 最小费用流的求解过程 例7 14 继例7 13 用LINGO软件求解例7 13 解 按照最小费用流的数学规划写出相应的LINGO程序 程序名 exam0714 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单位 原方案并不是最优的 7 3最优连线问题与旅行商问题 本节内容导航本节概述7 3 1最优连线问题7 3 2旅行商问题 本节内容概述最优连线问题也是最小生成树问题 MinimumSpaningTreeProblem 是求网络中长度最小的生成树 旅行商问题 TravelingSalesmanProblem 也称货郎担问题 是求最优的Hamilton圈 HamiltonianCycle 这两个问题是图论或组合优化中十分重要的问题 有着各自的解决方法 例如 求解最小生成树问题常用 破圈法 或 贪心法 但旅行商问题目前没有有效的算法求解 属于NP完全问题 当最小生成树问题或旅行商问题顶点的个数较大时 目前比较有效的方法是遗传算法 本节介绍如何用LINGO软件求解最小生成树问题和旅行商问题 其基本思想是将所求问题化为0 1整数规划 因此当所求问题的顶点数较大时 计算速度可能会比较慢 关于这两类问题的LINDO软件求解方法 还是留给读者 仿照本节LINGO软件的编程方法 完成相应的程序 返回导航 例7 15 最优连线问题 我国西部的SV地区共有1个城市 标记为1 和9个乡镇 标记为2 10 组成 该地区不久将用上天然气 其中城市1含有井源 现要设计一供气系统 使得从城市1到每个乡镇 2 10 都有一条管道相边 并且铺设的管子的量尽可能的少 图7 9给出了SV地区的地理位置图 表7 7给出了城镇之间的距离 7 3 1最优连线问题 返回导航 例7 15就是最优连线问题 实际上是求连接各城镇之间的最小生成树问题 下面给出图论中树与生成树的有关定义 以及相关的定理 1 树的基本概念定义7 7如果无向图是连通的 且不包含有圈 则称该图为树 Tree 如果有向图中任何一个顶点都可由某一顶点到达 则称为图的根 Root 如果有向图有根 且它的基础图是树 则称是有向树 关于树有如下定理 定理7 2设是有限的无向图 如果顶点度 degreeofavertex 满足 则 有圈 定理7 3每棵树至少有一个顶点的度为1 定理7 4设是连通图 且边数顶点数 则图中至少有一个顶点的度为1 定理7 5设是具有个顶点的无向连通图 是树的必要充分条件是 有条边 2 生成树的基本概念定义7 8若是包含的全部顶点的子图 它又是树 则称是生成树或支撑树 Spanningtree 对于生成树有如下定理 定理7 6如果无向图是有限的 连通的 则在中存在生成树 定义7 9在一个赋权图中 称具有最小权和的生成树为最优生成树或最小生成树 Kruskal在1956年给出求最优生成树的一个算法 称Kruskal算法 该方法是 避圈法 的推广 算法7 1 Kruskal算法 1 选择边 使得尽可能小 2 若已选定边 则从中选取边使得 为无圈图 是满足 的尽可能小的权 3 当 2 不能继续执行时 停止 4 最优连线问题 最小生成树 的数学表达式将最优连线问题写成数学规划的形式还需要一定的技巧 设是两点与之间的距离 或1 1表示连接 0表示不连接 并假设顶点1是生成树的根 则数学表达式为 3 求最优生成树的算法 5 最优连线问题的求解过程 例7 16 继例7 15 已知SV地区各城镇之间距离 见表7 9 求FSV地区 见图7 9 的最优连线 解 按照数学规划问题写出相应的LINGO程序 程序名 exam0716 lg4 MODEL 1 sets 2 cities 1 10