数学建模---第十章-网络规划课件

第十章第十章 网络规划网络规划组合优化理论组合优化理论 Combinatorial Optimization Theory第十第十章章 网络规划网络规划 我们生活在一个网络世界中，从某种意义上说现我们生活在一个网络世界中，从某种意义上说现代社会是一个由计算机信息网络、电话通讯网络、运代社会是一个由计算机信息网络、电话通讯网络、运输服务网络、能源和物质分派网络等各种网络所组成输服务网络、能源和物质分派网络等各种网络所组成的复杂的网络系统的复杂的网络系统.网络规划就是研究如何有效地计网络规划就是研究如何有效地计划、管理和控制这个网络系统，使之发挥最大的社会划、管理和控制这个网络系统，使之发挥最大的社会和经济效益和经济效益.由于图的结构的直观性，运用图论的方法更有助由于图的结构的直观性，运用图论的方法更有助于我们分析问题、描述问题、解决问题于我们分析问题、描述问题、解决问题.网络规划是运筹学（组合优化）的一个经典又重网络规划是运筹学（组合优化）的一个经典又重要分支，所研究的问题涉及经济管理、工业工程、交要分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等通运输、计算机科学与信息技术、通讯与网络技术等诸多领域诸多领域 .第十章第十章 网络规划网络规划1 最小生成树问题最小生成树问题2 最短路问题最短路问题3 最大流问题最大流问题4 中国邮递员问题中国邮递员问题0 图的基本概念图的基本概念第十第十章章 网络规划网络规划0 图的基本概念图的基本概念Example 1七桥问题七桥问题 18世纪的德国有个哥尼斯堡城，在流贯全城的普世纪的德国有个哥尼斯堡城，在流贯全城的普雷尔河两岸和河中两个岛之间架设了七座桥，把河的雷尔河两岸和河中两个岛之间架设了七座桥，把河的两岸和两岛连接起来，能否有这样一种走法，它通过两岸和两岛连接起来，能否有这样一种走法，它通过每座桥一次且仅一次每座桥一次且仅一次.该问题由该问题由Euler在在1736年解决年解决ABCD 则七桥问题就成为无向图中是否存在通过每一边则七桥问题就成为无向图中是否存在通过每一边一次且仅一次的路（即一笔画）问题一次且仅一次的路（即一笔画）问题 .0 0 图的基本概念图的基本概念图的基本概念图的基本概念Example 2人、狼、羊、菜渡河问题人、狼、羊、菜渡河问题 一一个摆渡人希望用一条小船把一只狼、一头羊和个摆渡人希望用一条小船把一只狼、一头羊和一篮白菜一篮白菜 从一条河的南岸渡到北岸去，而船小只能容从一条河的南岸渡到北岸去，而船小只能容纳纳人、狼、羊、菜人、狼、羊、菜中中的两个，决不能在无人看守的情的两个，决不能在无人看守的情况下，留下狼和羊在一起或羊和白菜在一起，应怎样况下，留下狼和羊在一起或羊和白菜在一起，应怎样渡河才能将狼、羊、白菜都运过河？渡河才能将狼、羊、白菜都运过河？状态转移问题状态转移问题人人 狼狼 羊羊 菜菜F W G C 考虑渡河过程中河南岸的变化情况，最初的状态考虑渡河过程中河南岸的变化情况，最初的状态是人、狼、羊、菜，最终状态成空状态，中间的状态是人、狼、羊、菜，最终状态成空状态，中间的状态为人、狼、羊、菜的不同组合为人、狼、羊、菜的不同组合.共有共有 16 种状态种状态，但有但有 6 种状态是不允许的，如狼、羊、菜等种状态是不允许的，如狼、羊、菜等.FWGCFWGOFWCFGCFGWCWGC 则渡河问题归结为寻找从顶点则渡河问题归结为寻找从顶点“FWGC”到顶到顶点点“O”的路线的路线.第十第十章章 网络规划网络规划Definition 图：图：有序三元组有序三元组 G=(V，E，R)称为一个图，其中称为一个图，其中GraphVertexEdge V=v1，v2,，vn 是有穷非空集，称为顶点集是有穷非空集，称为顶点集；E 称为边集，其中的元素叫做边；称为边集，其中的元素叫做边；R 是从边集是从边集 E 到到 V 中的有序或无序的元素偶对应中的有序或无序的元素偶对应 的集合的映射，称为关联函数的集合的映射，称为关联函数.关系关系Relation无向图：无向图：在图在图 G=(V，E)中，中，图简记为图简记为G=（V，E）与与 V 中的无序偶对应的边中的无序偶对应的边 e,称称为图为图 G 的无向边，每条边都是的无向边，每条边都是无向边的图，称为无向边的图，称为无向图无向图.v1v3v4v5v2e1e8e7e6e5e4e3e20 0 图的基本概念图的基本概念图的基本概念图的基本概念 E 中任一条边中任一条边 e 若连接顶点若连接顶点 u 和和 v，则记为，则记为 e=(u，v),并称并称 u 与与 v 为无向边的两个为无向边的两个端点端点；边；边 e 与与顶点顶点 u 及及 v 关联关联，顶点，顶点 u 与顶点与顶点 v 相邻相邻.与同一个顶与同一个顶点关联的若干条边称为是点关联的若干条边称为是相邻相邻的的.若若 e=(vi,vj)简记为简记为 eij自环：自环：两个端点重合为一个顶点的边两个端点重合为一个顶点的边；平行边：平行边：关联于同一对顶点的两条边关联于同一对顶点的两条边；没有自环和平行边的图；没有自环和平行边的图；简单图：简单图：完备图：完备图：任两个顶点之间恰有一条边相关联任两个顶点之间恰有一条边相关联；v1v3v4v2e1e5e6e2e4e3子图：子图：设设 G=(V,E)，G1=(V1,E1)都是图，且都是图，且V1 V,E1 E,则称图则称图 G1 为图为图 G 的子图；的子图；v1v3v4v2e1e3e4e2e5e6v1v3v4v2e1e3e4e2e5e6Note:是图是图第十第十章章 网络规划网络规划生成生成(支撑支撑)子图：子图：若图若图 G1 是图是图 G 的子图，且的子图，且 V1=V，则称则称 G1 是是 G 的生成子图；的生成子图；链（道路）：链（道路）：图图 G 中一个由顶点和边交错而成的非空中一个由顶点和边交错而成的非空有限序列：有限序列：W=v0e1v1e2ekvk，ei E，i=1,2,k，vj V，j=0,1,2,k,且且 ei=(vi-1，vi),则称则称 W 是是 G的的一一条链（道路）；条链（道路）；v0、vk 称为称为 W 的的起终点起终点，k为为路长路长；初等链：初等链：各顶点相异的链；各顶点相异的链；回路：回路：起点与终点重合的链；起点与终点重合的链；圈：圈：起点与终点重合的初等链；起点与终点重合的初等链；0 0 图的基本概念图的基本概念图的基本概念图的基本概念连通图：连通图：图图 G 中任意两点中任意两点 u 和和 v 存在一条链存在一条链；线度：线度：与顶点与顶点 v 关联的边数关联的边数(环算两次环算两次)称为称为 v 的线度的线度;记为记为 d(v).v1v3v4v5v2e1e8e7e6e5e4e3e2d(v2)=3，d(v3)=4割边：割边：若去掉边若去掉边 e 将使连通图将使连通图 G 不再连通，则称不再连通，则称 e 为为 G 的割边；的割边；有向图：有向图：在图在图 G=(V，E)中，与中，与 V 中的有序偶对应中的有序偶对应 的边的边 e,称为图称为图 G 的有向边（弧），每条边都的有向边（弧），每条边都是是 有向边的图，称为有向边的图，称为有向图有向图.记为记为 G=(，)Arc对有向图有类似无向图的概念，如对有向图有类似无向图的概念，如 d+(vi)，d-(vi).赋赋(加加)权图权图：图图 G 的每条边的每条边 e=(vi，vj)与一实数与一实数 w(e)=wij 对应对应.w(e)=wij 称为边称为边 e 的权的权.割集割集：边的集合，从连通图：边的集合，从连通图 G 中移去这些边，则中移去这些边，则 G 不连通，且不存在这些边的真子集使图不连通不连通，且不存在这些边的真子集使图不连通.记为记为v1v3v4v5v2e1e8e7e6e5e4e3e2S 为一个连通分支的顶点集为一个连通分支的顶点集.图的矩阵表示：图的矩阵表示：第十第十章章 网络规划网络规划关联矩阵：关联矩阵：对无向图对无向图 G=(V,E)，其中，其中 V=v1,vn,E=e1,e2,em .构造构造 nm 矩阵矩阵 A=(aij)nm 其中其中则称矩阵则称矩阵 A 是图是图 G 的关联矩阵的关联矩阵.v1v3v4v5v2e1e8e7e6e5e4e3e2v50 0 图的基本概念图的基本概念图的基本概念图的基本概念邻接矩阵：邻接矩阵：对无向图对无向图 G=(V,E)，其中，其中 V=v1,vn,构造构造 nn 矩阵矩阵 B=(bij)nn 其中其中则称矩阵则称矩阵 B 是图是图 G 的邻接矩阵的邻接矩阵.v1v3v4v5v2e1e8e7e6e5e4e3e2对称矩阵对称矩阵对有向图可类似定义关联矩阵、邻接矩阵对有向图可类似定义关联矩阵、邻接矩阵.Go back1 最小生成树问题最小生成树问题第十第十章章 网络规划网络规划Definition 10.1 一个无圈且连通的无向图一个无圈且连通的无向图 G 称为称为树树.不连通不连通,称为称为森林森林树通常记为树通常记为 T.v1v3v4v5v2e1e5e4e3e2v5如如 群试问题群试问题(Group Testing)设有设有 25 枚硬币，已知其中枚硬币，已知其中一枚是假的且偏轻，问如何用一枚是假的且偏轻，问如何用天平称最少的次数找到假币？天平称最少的次数找到假币？结论结论：3 k 个硬币，只需称个硬币，只需称 k 次即可次即可.不知道假硬币是偏轻还是偏重，如何？不知道假硬币是偏轻还是偏重，如何？如如 12 枚枚一、树、生成树一、树、生成树1 1 最小生成树问题最小生成树问题最小生成树问题最小生成树问题关于树有以下性质：关于树有以下性质：v1v3v4v5v2e1e5e4e3e2v53、在树在树 T 中，任意两顶点间有且仅有一条道路中，任意两顶点间有且仅有一条道路；1、在树在树 T 中，任意两个不相邻中，任意两个不相邻 顶点加上一条边，则恰好得到顶点加上一条边，则恰好得到 一个圈；一个圈；2、在树在树 T 中，去掉任意一条边中，去掉任意一条边,则树为不连通的；则树为不连通的；4、在树、在树 T 中，顶点数比边数多中，顶点数比边数多 1.如果树如果树 T 是图是图 G 的生成的生成 子图，则称子图，则称 T 是是 G 的一棵生成（支撑）树的一棵生成（支撑）树.Definition 10.2第十第十章章 网络规划网络规划Note:图图 G 的生成树一般不是唯一的的生成树一般不是唯一的.v1v3v2v4v1v3v2v4v1v3v2v4v1v3v2v4v1v3v2v4v1v3v2v4 共有多少？共有多少？16 棵棵1 1 最小生成树问题最小生成树问题最小生成树问题最小生成树问题Example 3 拟建造一个连接若干城镇的通讯网络，拟建造一个连接若干城镇的通讯网络，已知城镇已知城镇 vi，vj 之间直接拉线的造价为之间直接拉线的造价为 cij，试设计一，试设计一个总造价最小的通讯网络个总造价最小的通讯网络.如如 7 个城镇个城镇：v3v2v7v6v4v5v1112223344567 显然，该通讯网络必须包显然，该通讯网络必须包含所有顶点，连通、无圈，且含所有顶点，连通、无圈，且权和最小权和最小.生成子图生成子图生成树生成树最小生成树最小生成树Definition 10.3二、最小生成树二、最小生成树 若若 T 为为 G 的生成树，的生成树，T 中中的边的边 e 记为记为 eT，则，则T 的权的权 若若 T*为为 G 的生成树，且有的生成树，且有则称则称T*为为 G 的最小生成树的最小生成树.第十第十章章 网络规划网络规划Theorem 10.1 若若 T*是图是图 G 的生成树，则它是最小生的生成树，则它是最小生成树的充要条件是对成树的充要条件是对 T*外外 G 的每一条边的每一条边 加入加入 T*中中后形成的圈中，该边权最大后形成的圈中，该边权最大.Proof Theorem 10.2 若若 T*是图是图 G 的生成树，则它是最小生的生成树，则它是最小生成树的充要条件是对成树的充要条件是对 T*中的任何一条边中的任何一条边,将该边从将该边从T*中删去后形成的割集中，该边权最小中删去后形成的割集中，该边权最小.证略证略v1v3v4v5v228641233圈圈最优条件最优条件割割最优条件最优条件Theorem 10.1 的证明的证明Proof:反证法反证法 设设 T*是最小生成树，对是最小生成树，对T*外外G 的任一条边的任一条边 e，加入，加入 T*中后形成的圈中，如果该边中后形成的圈中，如果该边的权不是最大，设最大边为的权不是最大，设最大边为 e*.此时，此时，T*+e e*也也是是生成树，但它的权比生成树，但它的权比 T*更小，这与更小，这与 T*是最小生成树是最小生成树矛盾矛盾.设设 T*是生成树并满足定理条件，但不是最小的是生成树并满足定理条件，但不是最小的.设最小生成树为设最小生成树为 T0，则则 T*中至少有一条边中至少有一条边(i,j)T0,将将(i,j)加入加入 T0 后必产生一个圈，且圈上至少有一条后必产生一个圈，且圈上至少有一条边边(k,l)T*,由定理条件由定理条件 wijwkl,又又T0为最小生成树为最小生成树,所以所以,wijwkl,于是于是 wij=wkl .因此因此,T0+(i,j)(k,l)也也是最小生成树，并与是最小生成树，并与T*有更多的公共边，重复该过程有更多的公共边，重复该过程,最后，可以将最后，可以将 T0变为变为T*，因此，因此，T*是最小生成树是最小生成树.1 1 最小生成树问题最小生成树问题最小生成树问题最小生成树问题三、求最小生成树的算法三、求最小生成树的算法 求最小生成树的方法很多且很简单，理论基础主要求最小生成树的方法很多且很简单，理论基础主要是定理是定理 10.1（圈最优条件）、定理（圈最优条件）、定理 10.2（割最优条件）（割最优条件）.A、避圈法避圈法 1、Kruskal 算法（逐边生成）算法（逐边生成）2、Prim 算法算法 （逐点生成）（逐点生成）B、破圈法破圈法 1、Kruskal 算法算法（1956年）年）Step 0 把把 G 的边按权由小到大的顺序排列，即的边按权由小到大的顺序排列，即w(e1)w(em);令令 i=1，j=0，T=.Step 1 判断判断 Tei 是否含圈是否含圈,Y 转转Step 2,N 转转Step 3.Step 2 令令 i=i+1.若若 im 转转 Step 1;否则结束，此时否则结束，此时 G 不连通，所以没有最小生成树不连通，所以没有最小生成树.Step 3令令 T=Tei，j=j+1.若若 j=n-1，结束，结束，T 是是最最小生成树；否则，转小生成树；否则，转 Strp 2.第十第十章章 网络规划网络规划Example 4v3v2v7v6v4v5v1112223344567用用 Kruskal 算法求算法求右图的最小生成树右图的最小生成树.Solution:首先，对所有边按权首先，对所有边按权由小到大顺序排列由小到大顺序排列：(2,7)，(2,3).(1,7)，(4,5)，(5,7)，(1,6)，(4,7)，(1,2)，(3,7)，(3,4)(6,7)，(5,6)然后，按顺序将这些边加入然后，按顺序将这些边加入 T 中，中，如图，得到最小生成树如图，得到最小生成树 T*，w(T*)=14如何判断如何判断Tei 含圈？含圈？通过增加一个标号通过增加一个标号 给每个顶点一个互不相同的标号，不妨为顶点的下标给每个顶点一个互不相同的标号，不妨为顶点的下标.当加入一条边时当加入一条边时,判断两个顶点的标号判断两个顶点的标号,若相同若相同,则产生圈；否则产生圈；否则，将与标号大的相同的标号均改为与标号小的相同的标号则，将与标号大的相同的标号均改为与标号小的相同的标号.32764511122233445676 551 1 最小生成树问题最小生成树问题最小生成树问题最小生成树问题 在算法进行过程中，在算法进行过程中，T 始终不含圈始终不含圈.因此算法结因此算法结束束时，若时，若 T 含含 n-1 条边，则条边，则 T 为生成树；否则，原图不为生成树；否则，原图不连通，不存在生成树连通，不存在生成树.由于边已按权由小到大排序，而不加入由于边已按权由小到大排序，而不加入 T 的边，的边，必为产生圈中的最大权边，由定理必为产生圈中的最大权边，由定理 10.1 知，知，T 为生成为生成树则必为最小生成树树则必为最小生成树.这说明这说明Kruskal 算法的正确性算法的正确性.该算法始终试图把权尽可能小的边加到该算法始终试图把权尽可能小的边加到 T 中，仅中，仅当加入后使当加入后使 T 不是树才放弃，对边的选取，不必瞻前不是树才放弃，对边的选取，不必瞻前顾后，只看眼前利益顾后，只看眼前利益.这就是简单且重要的这就是简单且重要的贪婪算法贪婪算法（Greedy）.第十第十章章 网络规划网络规划2、Prim 算法算法（1957年）年）Step 0Step 1Step 2令令 S=Sv2，E0=E0 e*,转转 Strp 1.设设 v 为为 G 的任一顶点，令的任一顶点，令 S=v，E0=若若 S=V，结束，结束，T=(S,E0)为最小生成树；为最小生成树；否则否则 转转 Step 2.若若 ，则，则 G 不连通，结束；不连通，结束；否则，设否则，设 ,其中其中 v3v2v7v6v4v5v1112223344567Prim 算法的正确性由定理算法的正确性由定理10.2 不难得到不难得到.1 1 最小生成树问题最小生成树问题最小生成树问题最小生成树问题3、破圈法破圈法（1967年）年）v3v2v7v6v4v5v1112223344567四、应用举例四、应用举例 最小生成树的理论和计算，最小生成树的理论和计算，在很多工程或技术领域中得到应用在很多工程或技术领域中得到应用.如要在若干城市之间架设通讯线路、铺设公路铁路或如要在若干城市之间架设通讯线路、铺设公路铁路或各种管道，要求总的线路长度最短，材料最省，成本各种管道，要求总的线路长度最短，材料最省，成本最低等最低等.在实际的应用中，又提出了最小生成树问题的各在实际的应用中，又提出了最小生成树问题的各种推广，其中较典型的问题多是在可行解的结构上增种推广，其中较典型的问题多是在可行解的结构上增加一些约束加一些约束.第十第十章章 网络规划网络规划1、最大生成树问题最大生成树问题v3v2v7v6v4v5v1112223344567在最小生成树上，在最小生成树上，v1至至v4路的特点路的特点Example 5 设某工厂运输一很重的设备，需由设备库设某工厂运输一很重的设备，需由设备库 v1 运至施工现场运至施工现场 v4，中间需经过一些桥梁（如图），中间需经过一些桥梁（如图），已知这些桥梁的坚固程度不同，经专家测定其安全系已知这些桥梁的坚固程度不同，经专家测定其安全系数如示，试问应如何安排运输路线最安全？数如示，试问应如何安排运输路线最安全？最大值最小最大值最小v6v5v4施工现场施工现场v3v2v1设备库设备库0.40.40.80.30.30.80.50.20.3Solution:v6v5v4v3v1v20.80.30.40.40.80.50.30.30.2 最大生成树上的路是最小者最大最大生成树上的路是最小者最大.先求得最大生成树，如图先求得最大生成树，如图所以，所以，v1至至v4的最安全的路线为的最安全的路线为 v1 v6 v5 v3 v4最不安全处最安全最不安全处最安全最不安全处系数为最不安全处系数为 0.41 1 最小生成树问题最小生成树问题最小生成树问题最小生成树问题2、容量约束最小生成树问题容量约束最小生成树问题 在远程信息处理网络的设计中涉及这样的问题：在远程信息处理网络的设计中涉及这样的问题：已给一个无向图已给一个无向图 G=(V，E),每条边每条边(vi,vj)具有费具有费用用 w(vi,vj)以及容量以及容量 c(vi,vj)，一个顶点为信息接收，一个顶点为信息接收站站.寻求一个生成树，使所有信息沿树的边送到接收寻求一个生成树，使所有信息沿树的边送到接收站，满足容量约束，即每边上所传的信息量不超过容站，满足容量约束，即每边上所传的信息量不超过容量费用最且小量费用最且小.称为容量约束的最小生成树问题，是称为容量约束的最小生成树问题，是 NP-C问题问题.第十第十章章 网络规划网络规划3、度数约束最小生成树问题度数约束最小生成树问题 生成树在计算机和通讯网络中有许多应用，其中生成树在计算机和通讯网络中有许多应用，其中的大多数问题对某些顶点的度数有限制的大多数问题对某些顶点的度数有限制.如一个顶点如一个顶点代表一个中央计算设备，其他顶点代表终端，它们必代表一个中央计算设备，其他顶点代表终端，它们必须靠电缆与中央设备连接，若现在中央机的度数为须靠电缆与中央设备连接，若现在中央机的度数为 b,这可保证计算机的负荷分散在这可保证计算机的负荷分散在 b 个端口，求中央机度个端口，求中央机度数为数为 b 的最小生成树，使所用电缆尽可能少的最小生成树，使所用电缆尽可能少.若只有一个顶点受约束，是一个若只有一个顶点受约束，是一个 P 问题问题.1 1 最小生成树问题最小生成树问题最小生成树问题最小生成树问题1、Steiner 树树（在欧氏距离下）（在欧氏距离下）补充：补充：Example 6 假设电话刚发明，邮电部的第一个任务假设电话刚发明，邮电部的第一个任务是要使北京、上海、兰州三个城市间有线路相通是要使北京、上海、兰州三个城市间有线路相通.你你是总工程师，如何设计路线呢？是总工程师，如何设计路线呢？当然线路越短越好，由最小生成树：当然线路越短越好，由最小生成树：北京北京兰州、兰州、北京北京上海上海 为最佳为最佳.北京北京兰州兰州上海上海真的没办法更短了吗？真的没办法更短了吗？郑州郑州 但你的发现并没有使举世的科学家震动，因为这一但你的发现并没有使举世的科学家震动，因为这一事实早已被无数的数学书籍记载，这就是事实早已被无数的数学书籍记载，这就是 Steiner 树树.你发现：你发现：北京北京郑州、上海郑州、上海郑州、兰州郑州、兰州郑州郑州 也满足也满足要求且总长度比最小生成树更短要求且总长度比最小生成树更短.通过增加一些点（通过增加一些点（Steiner 点）使保存原来的所点）使保存原来的所有有点且连通，而总长度最短点且连通，而总长度最短.第十第十章章 网络规划网络规划v4v3v2v1如右图：最小生成树如右图：最小生成树 z min=31111但加上但加上 v5，则，则 z min=2 =2.828问题：问题：1、对于怎样放置的对于怎样放置的 n 个点，需要引进个点，需要引进 S 点；点；v1v3v2如：如：是不需要加点的是不需要加点的.2、如何确定如何确定 S 点的位置点的位置；3、引进几个引进几个 S 点最佳点最佳.n=1、2 是平凡的是平凡的.n=3 已解决，一般是已解决，一般是 NP-C 的的.Theorem 10.3 设有设有 A、B、C 三点，若三点，若ABC 的任一的任一内角都小于内角都小于 120o，则必存在内部一点，则必存在内部一点 P 使使 PA、PB、PC 的两两夹角均是的两两夹角均是 120o，且此时，且此时 PA+PB+PC ABC 的任两边之和的任两边之和.不可能有另一点不可能有另一点 D 比比 P 的效的效果果更好更好.v5而当而当A 120o 则则 z min=AB+AC1 1 最小生成树问题最小生成树问题最小生成树问题最小生成树问题Theorem 10.4三个点时，如何确定三个点时，如何确定S-点位置点位置ABCS120o120oD 能否再加点，能否再加点，使之更短呢？使之更短呢？对于对于 n 个点个点的网络，至多可加入的网络，至多可加入 n 2 个个 Steiner 点点.v4v3v2v11111v5最小生成树最小生成树 z min=3但加上但加上 v5，则，则 z min=2 =2.828120o120o此时此时，z min=1+=2.732问：问：Steiner 树能使总长树能使总长度比最小生成树减少的度比最小生成树减少的最大比例是多少？最大比例是多少？1968年两位美国数学家提出该比例为年两位美国数学家提出该比例为 13.4%的猜想，上世纪的猜想，上世纪90年代初，被中国年代初，被中国青年数学家堵丁柱解决，且方法很有价值青年数学家堵丁柱解决，且方法很有价值.第十第十章章 网络规划网络规划2、拟阵拟阵 （Matroid）问：怎样的结构的组合问：怎样的结构的组合优化问题可用优化问题可用 Greedy 算法得到最优解？算法得到最优解？Definition 10.4 子集系统子集系统 S=(E,l)是由有限集是由有限集 E 及及 E 的一个子集族的一个子集族 l 组成，在集合的包含关系下，组成，在集合的包含关系下，l 是封是封闭的闭的.l 中的成员，称为独立集中的成员，称为独立集.即若即若参照参照：E 为图为图 G 的边的集合，的边的集合，l 是是E 的无圈子集的无圈子集.关于子集系统关于子集系统 S=(E,l)的组合优化问题是对每一的组合优化问题是对每一个个 e E 给定一个权给定一个权 w(e)0，求一个最大独立集，求一个最大独立集，使其权和最大（小）使其权和最大（小）.Definition 10.5 设设 S=(E,l)是一子集系统，如果对是一子集系统，如果对 S的任意两个极大独立集的任意两个极大独立集 则称则称 S 是拟是拟阵阵.显然，对显然，对G=(E,V),S=(E,l),l 是无圈子图，则是无圈子图，则 S 是拟阵是拟阵.1 1 最小生成树问题最小生成树问题最小生成树问题最小生成树问题Theorem 10.5 S 是拟阵，则关于是拟阵，则关于 S 的组合优化问题的组合优化问题中每个例子，都可用中每个例子，都可用 Greedy 算法得到最优解算法得到最优解.婚姻问题婚姻问题(matching)可以看成一个子集系统可以看成一个子集系统 S=(E,l),l 所有匹配，但不是拟阵所有匹配，但不是拟阵.x3x1x2y2y1y3我们还学过其他我们还学过其他拟阵结构吗？拟阵结构吗？S=(E,l),E 一组向量一组向量 l 所有线性无关所有线性无关子子集，它是拟阵集，它是拟阵.因为线性无关组的子集因为线性无关组的子集仍线性无关；极大线性无关仍线性无关；极大线性无关组的所含向量个数相同组的所含向量个数相同 .则对每个向量加权，要求一个极大则对每个向量加权，要求一个极大线性无关组，使其权和最大（小），可线性无关组，使其权和最大（小），可用用 Greedy 算法算法.Go back第十第十章章 网络规划网络规划2 最短路问题最短路问题 最短路问题是网络优化中的一个相对基本而又非最短路问题是网络优化中的一个相对基本而又非常重要的课题常重要的课题.许多网络优化问题或者可以化为最短许多网络优化问题或者可以化为最短路问题，或者可用最短路的算法作为其子程序路问题，或者可用最短路的算法作为其子程序.如：如：通讯网络中的最可靠路问题、物资的运输路线、各种通讯网络中的最可靠路问题、物资的运输路线、各种工艺路线的安排、厂区及货场的布局、管道线网的铺工艺路线的安排、厂区及货场的布局、管道线网的铺设以及设备的更新等问题都可化为最短路问题；而网设以及设备的更新等问题都可化为最短路问题；而网络流问题和中国邮递员问题都要用最短路算法作为子络流问题和中国邮递员问题都要用最短路算法作为子程序程序 .2 2 最短路问题最短路问题最短路问题最短路问题 设有向网络设有向网络 D=(V,A,w)，其中弧，其中弧(vi,vj)A对对应的权应的权 wij 又称为弧长或费用，对于其中的两个顶点又称为弧长或费用，对于其中的两个顶点 v1、vt V,以以v1为起点为起点 vt 为终点的有向路称为为终点的有向路称为 v1 vt 有向路有向路 P,其所经过的所有弧上的权之和为该有向路其所经过的所有弧上的权之和为该有向路的的权权 所有所有 v1 vt 有向路中权和最小的一条称为有向路中权和最小的一条称为 v1 vt 最短路最短路 P*.求最短路的方法的基本思想很朴素求最短路的方法的基本思想很朴素：设设 v1 vl 的最短路是的最短路是 v1 vi vk vl,则则 v1 vk 的最短路是的最短路是 v1 vi vk 第十第十章章 网络规划网络规划Example 7 利用前述思想求如利用前述思想求如下网络中，下网络中，v1 至至 v4 的的最短路最短路.Solution:v1v2v3v4v5v6362423311从从 v1 逐步向外生长逐步向外生长 目前目前 v1 可达可达 v2、v3 路长分路长分别为别为6、3，这时求得了这时求得了v1至至 v3 的最短路，长度为的最短路，长度为 3.v1不可能通过其他顶不可能通过其他顶点到达点到达v3 距离更短，距离更短，因为因为 wij 0 再求再求 v1或通过或通过 v3 可达的所有路的最短距离，可达的所有路的最短距离，v1 v2;v1 v3 v2;v1 v3 v4 路长分别为路长分别为6、5、7.这时求这时求得了得了 v1 至至v2的最短路，路长为的最短路，路长为 5.再求再求 v1 v3 v2 v4;v1 v3 v2 v5;v1 v3 v4 路长分别为路长分别为 7、6、7.这时得这时得 v1 至至v2的最短路的最短路,路长为路长为 5.这时求得这时求得 v1至至v4 的最短路的最短路，路长为，路长为 6.介绍了基本思想和方法，但有两个需弥补的地方：介绍了基本思想和方法，但有两个需弥补的地方：1、计算量大、计算量大 O(n3);2、如何记录最短路的走法、如何记录最短路的走法.一、正费用网络一、正费用网络(wij0)2 2 最短路问题最短路问题最短路问题最短路问题 1959年，年，Dijkstra 提出通过提出通过标号标号解决了上述问题解决了上述问题.这是网络规划中这是网络规划中常用手段常用手段该算法是目前公认的求正费用网络最短路的较好的算法该算法是目前公认的求正费用网络最短路的较好的算法之一之一.基本如前（逐点生成），但在执行过程中，对基本如前（逐点生成），但在执行过程中，对未未达到最短路的顶点，记录目前达到最短路的顶点，记录目前 v1 至该点的最短路长度至该点的最短路长度.一旦有新的顶点被确定已达最短，则下一步其余（对未一旦有新的顶点被确定已达最短，则下一步其余（对未达到最短路的顶点）的顶点只需与它比较，来确定新的达到最短路的顶点）的顶点只需与它比较，来确定新的目前目前 v1至这些点的最短路长度至这些点的最短路长度.ui 表示表示 v1 至至vi 的最短路长度；（是永久性的）的最短路长度；（是永久性的）t(vi)表示目前表示目前 v1 至至vi 的最短路长度；（是临时性的）的最短路长度；（是临时性的）l(vi)表示表示v1 至至vi 的目前最短路上的目前最短路上 vi 的前一个顶点的下标的前一个顶点的下标如：如：l(vi)=j 即即 v1 vj vi第十第十章章 网络规划网络规划Dijkstr 算法算法（求（求v1至个顶点或至至个顶点或至vh 的最短路）的最短路）Step 0令令 i=1,Si=v1,u1=0,l(v1)=0,对每个对每个 令令 t1(vj)=M,l1(vj)=M (M 为充分大的正数为充分大的正数)，k=1Step 1如果如果 Si=V(或或 k=h 即即 v1至至vh的最短路的最短路)结束结束否则否则,转转 Step 2Step 2 对每条从对每条从 vk 出发的弧出发的弧(vk,vj)A,ti+1(vj)=min ti(vj),uk+wkj 若若 ti+1(vj)=ti(vj)，则，则 li+1(vj)=li(vj),否则否则 li+1(vj)=kStep 3令令如果如果 ti+1(vji)M则则 令令 Si+1=Si vji,k=ji,i=i+1 转转 Step 2 否则否则 结结束束.当算法结束时，如果当算法结束时，如果 vj Si,则则 v1 可达可达 vj,uj 表表示示 v1至至vj 的最短路的长度，且通过的最短路的长度，且通过 l(vj)，可得其最短，可得其最短路路.如果如果 ,则则vi至至vj 不存在路不存在路.2 2 最短路问题最短路问题最短路问题最短路问题Example 8 用用 Dijkstra 算法求如下网络中，算法求如下网络中，v1 至各顶至各顶点的最短路点的最短路.v1v2v3v4v5v61624253117Solution:i=1,令令 S1=v1u1=0,l(v1)=0 ,t1(v2)=t1(v3)=t1(v4)=t1(v5)=t1(v6)=Ml1(v2)=l1(v3)=l1(v4)=l1(v5)=l1(v6)=Mk=1t2(v2)=min M,u1+6 =6 l2(v2)=1t2(v3)=min M,u1+3 =3 l2(v3)=1t2(v4)=min M,u1+M =M l2(v4)=Mt2(v5),t2(v6)均不均不变变.所以，所以，则则 u2=t2(v3)=3,l(v3)=1,S=v1,v3k=2,i=2 Go on过程可由如下表格给出，打过程可由如下表格给出，打“*”者为者为 uj.v1v2v3v4v5v6 10*0M MM MM MM MM M 26 13*1M MM MM M 36 14*3M M10 3 45*46 49 4 56*49 4 67*5ti(vj)li(vj)ivj第十第十章章 网络规划网络规划二、一般费用网络二、一般费用网络 对于对于 wij0 的情形，的情形，Dijkstra 算法是行不通的算法是行不通的.如图如图:v1v2v3-221v1v2v3-22-1 在没有负圈的情况下，在没有负圈的情况下，v1 至多通过至多通过 n-2 顶点到达顶点到达 vj,与与 wij0 不同，可逐点进入不同，可逐点进入 Si，但在这里，目前是最，但在这里，目前是最短的但完全可能通过其它点会更短短的但完全可能通过其它点会更短.但求最短路方法的基本思想还是成立的但求最短路方法的基本思想还是成立的：设设 v1 vl 的最短路是的最短路是 v1 vi vk vl,则则 v1 vk 的最短路是的最短路是 v1 vi vk 2 2 最短路问题最短路问题最短路问题最短路问题 想法是这样，从步数着手，一步可达、两步、三想法是这样，从步数着手，一步可达、两步、三步，步，至多，至多 n-1 步步.即如下递推公式：即如下递推公式：其中其中 表示表示 t 步内步内 v1 至至 vj 的最短路长度的最短路长度.为加快速度，可用为加快速度，可用已计算的已计算的 替换替换.当进行到某一步，如第当进行到某一步，如第 k 步，对所有的步，对所有的 j=2,3,n 有有则则如果如果 当当 k n-1,仍不出现仍不出现则网络中含有负圈则网络中含有负圈.这算法是由这算法是由 Ford 1956年给出年给出.第十第十章章 网络规划网络规划 ExampleExample 9 9（道路矩阵）（道路矩阵）（道路矩阵）（道路矩阵）设某小航空公司在设某小航空公司在设某小航空公司在设某小航空公司在 4 4 城市间城市间城市间城市间的航行运行图如右图，某记者从的航行运行图如右图，某记者从的航行运行图如右图，某记者从的航行运行图如右图，某记者从城市城市城市城市 d d 出发，出发，出发，出发，（1 1）有几条经有几条经有几条经有几条经 3 3 次航行到达城市次航行到达城市次航行到达城市次航行到达城市 c c 的线路；的线路；的线路；的线路；（2 2）有几条经有几条经有几条经有几条经 4 4 次航行回到城市次航行回到城市次航行回到城市次航行回到城市 d d 的线路的线路的线路的线路；SolutionSolution:考察图的邻接矩阵的幂考察图的邻接矩阵的幂考察图的邻接矩阵的幂考察图的邻接矩阵的幂表明从表明从表明从表明从c c出发经两次航行到达出发经两次航行到达出发经两次航行到达出发经两次航行到达b b的线路有两条的线路有两条的线路有两条的线路有两条 所以，所以，所以，所以，2 2 最短路问题最短路问题最短路问题最短路问题 一般地，一般地，的值表示从城市的值表示从城市 i 到城市到城市 j 经两次航经两次航行到达行到达 j 的线路数；若记的线路数；若记 ，则，则 =从城市从城市 i 到城市到城市 j 经经 k 次航行到达次航行到达 j 的线路数的线路数.于是，从于是，从 d 出发经出发经 3 次航行到达次航行到达 c 的线路数为的线路数为 条，条，从从 d 出发经出发经 4 次航行回到次航行回到 d 的线路数为的线路数为 条条 =从顶点从顶点 i 到顶点到顶点 j 经少于经少于 k+1步到达步到达 j 的道路数的道路数 第十第十章章 网络规划网络规划 ExampleExample 10 10 用用 Ford 算法求如下网络中算法求如下网络中 v1至各顶点至各顶点的最短路的最短路.v1v2v3v4v5v6-26-182-5311v7v821-5-3-3-17-1SolutionSolution:得邻接矩阵得邻接矩阵定义定义 Ai*Bj=2 2 最短路问题最短路问题最短路问题最短路问题v1v2v3v4v5v6-2682-5311v7v821-5-3-3-17-1v1v2v3v4v5v6v7v8t=10-1-23mmmmt=2t=3t=4定义定义 Ai*Bj=0-5-2-71-15m0-5-2-76-1-5-30-5-2-76-1-5-3 当当 t=3 和和 t=4v1 至各顶点路长不至各顶点路长不变（步数增加也不变（步数增加也不会变）会变）.此时，已此时，已得得所求所求.-1第十第十章章 网络规划网络规划 求网络中所有顶点之间的最短路求网络中所有顶点之间的最短路.当然，可以通过当然，可以通过 n 次调用次调用 Ford算法来完成，但计算法来完成，但计算量为算量为 O(n2m).1962年年 Floyd-Warshall 提出的算法计提出的算法计算量为算量为 O(n3).算法可用如下递推公式表示算法可用如下递推公式表示：2 2 最短路问题最短路问题最短路问题最短路问题Floyd-Warshall 算法算法Step 0t=0,对于所有顶点对于所有顶点 vi,vj令令Step 1对于所有顶点对于所有顶点 vi,vj若若令令否则否则,令令Step 2如果如果 t=n,则结束则结束;否则否则 令令 t=t+1 转转Step 1.第十第十章章 网络规划网络规划 ExampleExample 11 11SolutionSolution:用用 Floyd-Warshall 算法求如下网络中所算法求如下网络中所有顶点之间的最短路有顶点之间的最短路.v1v2v3v464-73105-3-36记最短路长度记最短路长度矩阵为矩阵为 U,最短路矩阵为最短路矩阵为 P初始值为初始值为第一次迭代后得到第一次迭代后得到第二次迭代后得到第二次迭代后得到2 2 最短路问题最短路问题最短路问题最短路问题第三次迭代后得到第三次迭代后得到第四次迭代后得到第四次迭代后得到 终终 点点 v1 v2 v3 v4 起起 点点 v1 (v1,v2)(v1,v3)(v1,v3)(v3,v4)v2 (v2,v1)(v2,v3)(v2,v3)(v3,v4)v3(v3,v4)(v4,v2)(v2,v1)(v3,v4)(v4,v2)(v3,v4)v4 (v4,v2)(v2,v1)(v4,v2)(v4,v2)(v2,v3)最短路长度可直接由最短路长度可直接由U(5)得到得到,根据根据 P(5)最最后得到的最短路为后得到的最短路为第十第十章章 网络规划网络规划三、应用举例三、应用举例 选址问题选址问题或设点问题是指为一个或几个服务设施或设点问题是指为一个或几个服务设施在一定区域内选定它的位置在一定区域内选定它的位置,使某一指标达到最优使某一指标达到最优.选址问题的数学模型依赖于设施可能的区域和评选址问题的数学模型依赖于设施可能的区域和评判位置优劣的标准判位置优劣的标准,有许多不同种类的选址问题有许多不同种类的选址问题.(1)中心问题中心问题 对一些紧急服务型的设施对一些紧急服务型的设施(如急救中心、消防站如急救中心、消防站等等)，要求距网络中最远的被服务点距离尽可能小，要求距网络中最远的被服务点距离尽可能小.可以在点上、边可以在点上、边上、区域内上、区域内2 2 最短路问题最短路问题最短路问题最短路问题Example 12 现准备在现准备在 v1,v2,v7 七个居民点中设七个居民点中设置置医院医院.各点之间的距离如图各点之间的距离如图,问设一个医院在哪个居民问设一个医院在哪个居民点点,可使最大服务距离为最小可使最大服务距离为最小;若设两个若设两个,问应设在哪问应设在哪两两个居民点个居民点?v1v2v3v4v5v662.531.81.5v721.534SolutionSolution:求出任意两点的最短路求出任意两点的最短路长度长度,得矩阵得矩阵 D=(dij):称称 l(vi)为为vi 的的最大服务距离最大服务距离 l(vi)取取 min l(v1),l(v2),l(v7)=4.8=l(v6)所以所以,若设一个医院若设一个医院,则设在居民点则设在居民点 v6 处最好处最好.第十第十章章 网络规划网络规划v1v2v3v4v5v662.531.81.5v721.534考察设置两个医院考察设置两个医院 若设在若设在 v3,v6 那么对那么对 v1 来说来说,居居民可以到民可以到 v3 处看病处看病,也可以在也可以在 v6处看处看病病,由由 d 知知 d13=5 及及 d16=4.5,则则v1 的居民自然选择的居民自然选择 v6 处看病处看病,其服务距其服务距离为离为 4.5.依次找出居民点依次找出居民点 v2,v7 的服务距离的服务距离,得得:点点 vjv1v2v3v4v5v6v7 d(vj,v3)5 2 0 4 62.5 4 d(vj,v6)4.5 1.5 2.5 1.8 4.8 01.5服务距离服务距离4.5 1.5 01.8 4.8 01.5 则设在则设在 v3,v6 的的最最大服务距离为大服务距离为 4.8(记记 l(v3,v6).求出任意对顶点的最大服务距离求出任意对顶点的最大服务距离 l(vi,vj)由矩阵由矩阵 L 可知可知 l(v2,v4)=l(v2,v5)=3 为最小为最小,故故 医院设在医院设在 v2 及及 v4 或或 v2 及及 v5.2 2 最短路问题最短路问题最短路问题最短路问题(2)重心问题重心问题 对一些服务型的设施对一些服务型的设施(如邮局、学校、图书馆如邮局、学校、图书馆等等)，要求设施到所有服务对象点的距离加权和最小，要求设施到所有服务对象点的距离加权和最小.v1v2v3v4v5v662.531.81.5v721.534Example 13 现准备在现准备在 v1,v2,v7 七个七个居民点中设置超市居民点中设置超市.各点之间的距离各点之间的距离如图如图,问超市设在哪个居民点问超市设在哪个居民点,可使全可使全体被服务对象来往的加权和最小体被服务对象来往的加权和最小?q(vi)表示表示 vi 居民数居民数.SolutionSolution:1、求距离矩阵求距离矩阵 D=(dij);2、计算各顶点作为超市的加权和计算各顶点作为超市的加权和 ；3、求求 vk 使使vk 称为图称为图 G 的的重心重心 或或 中位点中位点第十第十章章 网络规划网络规划Example 14设备更新问题设备更新问题 某企业使用一种设备，在每年年初企业要决定是否某企业使用一种设备，在每年年初企业要决定是否更行，若购置新设备，需支付购置费及使用费，若继续更行，若购置新设备，需支付购置费及使用费，若继续使用旧设备，则需支付更多的使用费，问题是在保证有使用旧设备，则需支付更多的使用费，问题是在保证有一台设备在运行下，使得总的支付费用最少一台设备在运行下，使得总的支付费用最少.以下是一个五年计划情况：以下是一个五年计划情况：年年 1 2 3 4 5购置费购置费1111121213 年年0-11-22-33-44-5使用费使用费 5 6 81118SolutionSolution:v1v2v3v4v5v659 vi 表示第表示第 i 年初，年初，v6 为第五年末为第五年末.(vi,vj)表示第表示第 i 年初购一台设备使年初购一台设备使用至第用至第 j-1 年末年末.4130221616223041172331172318问题转化为求问题转化为求 v1至至v6的最短路的最短路.最优方案：第最优方案：第 1、3 年年初各购一台新设备年年初各购一台新设备 或或 第第 1、4 年年初各购一台新设备，总费用年年初各购一台新设备，总费用53.Go back第十第十章章 网络规划网络规划3 最大流问题最大流问题 最大流问题是以网络中的流为研究对象，所谓网络最大流问题是以网络中的流为研究对象，所谓网络中的流其意义类似于在网络中将一些中的流其意义类似于在网络中将一些“物质物质”从一个顶从一个顶点点沿弧发送到另一个顶点沿弧发送到另一个顶点.许多系统包含了流量问题，许多系统包含了流量问题，如：交通系统有车辆流、金融系统有现金流、供水（供如：交通系统有车辆流、金融系统有现金流、供水（供气）系统有水（气）流、控制系统有信息流、通讯系统气）系统有水（气）流、控制系统有信息流、通讯系统中有电话通话流中有电话通话流 等等等等.最大流问题主要是确定这类系最大流问题主要是确定这类系统统网络所能承受的最大流量以及如何达到这个最大流量网络所能承受的最大流量以及如何达到这个最大流量.3 3 最大流问题最大流问题最大流问题最大流问题一、基本概念与定理一、基本概念与定理Definition 10.6 给一个有向图给一个有向图 D=(V,A)，在在 V 中指定了一点称为发点中指定了一点称为发点(源源),记为记为 vs(没有入弧没有入弧)，另一个点称为收点另一个点称为收点(汇汇),记为记为 vt(没有出弧没有出弧)，其余的其余的点点称为中间点称为中间点.对于每一条弧对于每一条弧(vi,vj)A，对应有一个，对应有一个 c(vi,vj)0(简记为简记为 cij)，称为弧的容量，称为弧的容量.则称则称 D 为一为一个网络个网络 记作记作 D=(V,A,C).v1v2v3v4v5vsvt12364421326107 在弧集在弧集 A 上定义一个非负函数上定义一个非负函数f=f(vi,vj)，f(vi,vj)为弧为弧(vi,vj)上的流量，简记上的流量，简记 fij.称称 f 是网络上的流是网络上的流.14134104113825显然，这不可显然，这不可行行Definition 10.7 vs1vt1vsvskvs2vt2vthvtmmmmmm本节的本节的 m 是指是指足够大的整数足够大的整数第十第十章章 网络规划网络规划v1v2v3v4v5vsvt1236442132610714134104113825满足满足a、容量限制条件容量限制条件：对每一弧对每一弧(vi,vj)A 0 fijcijb、平衡条件平衡条件：对于中间点：对每个对于中间点：对每个 i(is,t)有有Definition 10.8的流的流 f，称为可行流，称为可行流.称为称为 f 的流值的流值.用用(cij,fij)表示弧表示弧(vi,vj)的容量和流量的容量和流量.(12,5)(3,3)(6,4)(2,2)(4,2)(3,1)(6,3)(2,1)(1,1)(7,3)(10,5)(4,2)可验证，这是一个可行流可验证，这是一个可行流，v(f)=9.任何网络可行流总是存在的，如任何网络可行流总是存在的，如 fij=0 对任意对任意(vi,vj)A.3 3 最大流问题最大流问题最大流问题最大流问题最大流问题最大流问题：这是一个特殊的线性规划问题，可用单纯形法这是一个特殊的线性规划问题，可用单纯形法解，但在图上可提出更简洁、直观的方法解，但在图上可提出更简洁、直观的方法.Definiti