图论与网络优化模型课件.ppt

《图论与网络优化模型课件.ppt》由会员分享，可在线阅读，更多相关《图论与网络优化模型课件.ppt（74页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七章第七章 图论与网络优化模型图论与网络优化模型 7.1 图论基本概念与最小生成树图论基本概念与最小生成树7.2 最短路问题最短路问题7.3 网络最大流网络最大流7.4 二分图与锁具装箱问题二分图与锁具装箱问题y实际背景实际背景 例例1（公路连接问题）某一地区有若干个主要城市，现准备修（公路连接问题）某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中一个城市都可建高速公路把这些城市连接起来，使得从其中一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么如何决定在哪任

2、意两个城市之间修建高速公路的成本，那么如何决定在哪些城市间修建高速公路总成本最小？些城市间修建高速公路总成本最小？例例2（最短路问题）一名货车司机奉命在最短的时间内将一车（最短路问题）一名货车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货车此有多种行车路线，这名司机应选择哪条线路呢？假设货车的运行速度是恒定的，那么这个问题相当于需要找到一条从的运行速度是恒定的，那么这个问题相当于需要找到一条从甲地到乙地的最短路。甲地到乙地的最短路。例例3（运输问题）某种原材料

3、有（运输问题）某种原材料有M个产地，现在需要将原材料个产地，现在需要将原材料从产地运往从产地运往N个使用工厂。假定个使用工厂。假定M个产地的产量和个产地的产量和N个工厂的个工厂的需求量已知，单位产品从任一产地到任一工厂的运费已知，需求量已知，单位产品从任一产地到任一工厂的运费已知，那么，如何安排运输方案可以使总运输成本最低？那么，如何安排运输方案可以使总运输成本最低？实际背景实际背景 例例4（指派问题）一家公司经理准备安排（指派问题）一家公司经理准备安排n名员工去完成名员工去完成n项任项任务，每人一项。由于各员工的特点不同，不同的员工去完成务，每人一项。由于各员工的特点不同，不同的员工去完成同

4、一项任务时所获得的收益不同，如何分配工作方案使总回同一项任务时所获得的收益不同，如何分配工作方案使总回报最大？报最大？例例5（中国邮递员问题）一名邮递员负责投递某个街区的邮件。（中国邮递员问题）一名邮递员负责投递某个街区的邮件。如何为他设计一条最短的投递路线？即从邮局出发，经过投如何为他设计一条最短的投递路线？即从邮局出发，经过投递区内每条街道至少一次，最后返回邮局。递区内每条街道至少一次，最后返回邮局。例例6（旅行商问题）一名推销员准备前往若干城市推销产品。（旅行商问题）一名推销员准备前往若干城市推销产品。如何为他设计一条最短的旅行路线？即从驻地出发，经过每如何为他设计一条最短的旅行路线？即

5、从驻地出发，经过每个城市恰好一次，最后返回驻地。个城市恰好一次，最后返回驻地。实际背景实际背景 共同特点：共同特点：（1）它们的目的都是从若干可能的安排或方案中寻求某种意）它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为义下的最优安排或方案，数学上把这种问题称为优化问题优化问题。（2）它们都易于用图形的形式直观的描述和表达，数学上把）它们都易于用图形的形式直观的描述和表达，数学上把这种与图相关的结构称为网络，与图和网络相关的优化问题这种与图相关的结构称为网络，与图和网络相关的优化问题称为称为网络优化网络优化。哥尼斯堡七桥问题哥尼斯堡七桥问题 在无孤立结

6、点的图在无孤立结点的图G中中,若存在若存在一条回路一条回路,它经过图中它经过图中每条边一次且仅一次每条边一次且仅一次,称此回路为称此回路为欧拉回路欧拉回路.无向图无向图G具有欧拉回路具有欧拉回路,当且仅当当且仅当G是连通的是连通的,且所有且所有结点的度都是偶数结点的度都是偶数.图论基本概念与最小生成树图论基本概念与最小生成树一、一、图图 的的 概概 念念1 1、图的定义、图的定义2 2、顶点的次数、顶点的次数 3 3、子图、子图二、二、图图 的的 矩矩 阵阵 表表 示示1 1、关联矩阵关联矩阵2 2、邻接矩阵邻接矩阵三、三、最最 小小 生生 成成 树树定义定义有序二元组有序二元组G=(V,E)

7、G=(V,E)称为一个图称为一个图.11 是有穷非空集，称为是有穷非空集，称为顶点集顶点集 其中的元素叫图其中的元素叫图G G的顶点。的顶点。2 E E称为边集，其中的元素称为图称为边集，其中的元素称为图G G的边。的边。例例设设G=(V,E),G=(V,E),其中其中G G 的图解如图的图解如图定义定义定义定义关联矩阵关联矩阵注：假设图为简单图邻接矩阵邻接矩阵注：假设图为简单图树的等价定义树的等价定义无回路的连通图无回路的连通图.无回路且无回路且=v-1 其中其中是是T的边数的边数,v是是T的结点数的结点数.连通的且连通的且=v-1.无回路但添加一条新边则得到一条仅有的回路无回路但添加一条新

8、边则得到一条仅有的回路.连通的连通的,但删去任一条边但删去任一条边,T便不连通便不连通.每对结点之间有一条且仅有一条路每对结点之间有一条且仅有一条路.如果图如果图G的生成子图是树的生成子图是树,则称此树为则称此树为G的的生成生成树树.例：某地要建例：某地要建5个工厂，拟修筑道路连接这个工厂，拟修筑道路连接这5处。经勘测处。经勘测其道路可依下图的无向边铺设。为使这其道路可依下图的无向边铺设。为使这5处都有道路处都有道路相通，问至少要铺设几条路？怎样铺设？相通，问至少要铺设几条路？怎样铺设？最小生成树（最小生成树（Kruskal（克鲁斯克尔）（克鲁斯克尔）算法）算法）设图设图G有有n个结点，以下算

9、法产生的是最小生成树个结点，以下算法产生的是最小生成树1）选取最小权边）选取最小权边e1，置边数，置边数i1；2）i=n-1结束，否则转入结束，否则转入3）；）；3）设已选择边为）设已选择边为e1,e2,ei,在在G中选取不同于中选取不同于e1,e2,ei的边的边ei+1，使，使e1,e2,ei,ei+1中无回路中无回路且且ei+1是满足此条件的最小边；是满足此条件的最小边；4）ii1,转入转入2）。）。注意：最小生成树不唯一，但不同的最小生成树的边权之和注意：最小生成树不唯一，但不同的最小生成树的边权之和是唯一的是唯一的边按升序排序边按升序排序:边边(vi,vj)记成记成eij边权边权e28

10、e34e23e38e17e24e45e57e16e78e56e35e46e67e58e12e181 1 2 2 2 3 3 3 4 4 4 5 6 6 7 7 8v1 v5 v4v2 v3v8 v6v7 12213772486653443v1 v5 v4v2 v3v8 v6v7 1212433 TO MATLAB(kruskal.m)验证：验证：P95例例11最短路问题及其算法最短路问题及其算法一、基本概念一、基本概念二、固定起点的最短路二、固定起点的最短路三、每对顶点之间的最短路三、每对顶点之间的最短路基基 本本 概概 念念固定起点的最短路固定起点的最短路最短路是一条最短路是一条路径路径 假

11、设在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树 因此,可采用树生长的过程来求指定顶点到其余顶点的最短路算法步骤：算法步骤：TO MATLAB(dijkstra.m)u1u2u3u4u5u6u7u8验证：验证：P97例例1每对顶点之间的最短路每对顶点之间的最短路1 1、求距离矩阵的方法、求距离矩阵的方法2 2、求路径矩阵的方法、求路径矩阵的方法3 3、查找最短路路径的方法、查找最短路路径的方法（一）算法的基本思想（一）算法的基本思想（二）算法原理（二）算法原理（三）算法步骤（三）算法步骤算法的基本思想算法的基本思想算法原理算法原理 求距离矩阵的方法求距离矩阵

12、的方法算法原理算法原理 求路径矩阵的方法求路径矩阵的方法在建立距离矩阵的同时可建立路径矩阵R 即当vk被插入任何两点间的最短路径时，被记录在R(k)中，依次求 时求得 ，可由 来查找任何点对之间最短路的路径ij算法原理算法原理查找最短路路径的方法查找最短路路径的方法pkp2p1p3q1q2qm则由点i到j的最短路的路径为：算法步骤算法步骤例、求下图任意两点之间的最短路径的长度例、求下图任意两点之间的最短路径的长度 TO MATLAB(road2(floyd)可化为最短路问题的多阶段决策问题可化为最短路问题的多阶段决策问题最短路的应用最短路的应用 选址问题选址问题-中心问题中心问题 TO MAT

13、LAB(road3(floyd)S(v1)=10,S(v2)=7,S(v3)=6,S(v4)=8.5,S(v5)=7,S(v6)=7,S(v7)=8.5S(v3)=6,故应将消防站设在v3处。7.3 7.3 网络流问题网络流问题 1、网络流图网络流图2、最大流问题及其解法最大流问题及其解法3、最小费用问题及其解法、最小费用问题及其解法问题问题1：7种设备要用种设备要用5架飞机运往目的地，每种设备各架飞机运往目的地，每种设备各有有4台，这台，这5架飞机的容量分别为架飞机的容量分别为8，8，5，4，4台，问台，问能否有一种装载法，使同一种类型的设备不会有两台能否有一种装载法，使同一种类型的设备不会

14、有两台在同一架飞机上。在同一架飞机上。问题问题2：设有王二、张三、李四、赵五四人及小提琴、：设有王二、张三、李四、赵五四人及小提琴、大提琴、钢琴和吉他四种乐器，已知四人的特长如下：大提琴、钢琴和吉他四种乐器，已知四人的特长如下：王二擅长拉大提琴和弹钢琴；王二擅长拉大提琴和弹钢琴；张三擅长拉小提琴、大提琴和吉他；张三擅长拉小提琴、大提琴和吉他；李四擅长拉小提琴和大提琴；李四擅长拉小提琴和大提琴；赵五只会弹吉他；赵五只会弹吉他；今假设四人同台演出，每人奏一种乐器，问四人同时今假设四人同台演出，每人奏一种乐器，问四人同时各演奏一种乐器时所有可能的方案。各演奏一种乐器时所有可能的方案。网络流图是满足下

15、列条件的有向赋权图网络流图是满足下列条件的有向赋权图（1 1）有一个发点）有一个发点 和收点和收点（2 2）每条边都有一个容量（权）每条边都有一个容量（权）实际含义是发点可以看作运输问题的起点，收点可以看作运实际含义是发点可以看作运输问题的起点，收点可以看作运输问题的终点，边可以看作运输路线，权数可以看作该线路的输问题的终点，边可以看作运输路线，权数可以看作该线路的运输能力。运输能力。设设 是定义在有向赋权图是定义在有向赋权图 边集边集 上的一上的一个数值函数，满足：个数值函数，满足：（2 2）除过发点和起点外，）除过发点和起点外，（1 1）一、网络流图一、网络流图该定义的实际意义分别为：该定

16、义的实际意义分别为：1 1、每条边的实际流量不超过它的容量。、每条边的实际流量不超过它的容量。2 2、流入和流出每个节点的流量相等。（物质不灭，无损、流入和流出每个节点的流量相等。（物质不灭，无损耗）耗）3 3、从发点流出的流量等于流入收点的流量。、从发点流出的流量等于流入收点的流量。称称 3 3、二、二、最大流问题及其求解方法最大流问题及其求解方法（一）（一）最大流问题最大流问题n最大流问题最大流问题 设设有有向向网网络络N N（V V，A A），在在发发点点V Vs s 有有一一批批货货，要要通通过过网网络络上上的的弧弧运运输输到到收收点点V Vt t 去去，受受运运输输条条件件限限制制，

17、每每条条弧弧a aijij在在单单位位时时间间内内通通过过的的车车辆辆数数不不能能超超过过c cijij 辆辆，分分析析：如如何何组组织织运运输输才才能能使使从从V Vs s到到V Vt t 在在单单位位时时间间内内通通过过的的车车辆辆达到最多？达到最多？上面描述的这类问题，称为最大流问题。上面描述的这类问题，称为最大流问题。n最大流问题广泛地应用在交通运输、供水、油管供油、最大流问题广泛地应用在交通运输、供水、油管供油、邮电通讯，也可以用在生产安排，管理优化等实际问邮电通讯，也可以用在生产安排，管理优化等实际问题上。题上。例例：如如图图1 1中中，有有一一批批物物资资需需要要用用汽汽车车尽尽

18、快快从从发发点点运运到到收收点点，弧弧（i i，j j）上上所所标标的的数数字字表表示示该该条条道道路路在在单单位位时时间间内内最最多多能能通通过过的的车车辆辆数数（单单位位：百百辆辆），问问如如何何调调运运，才才能能使使单位时间里有最多的车辆从单位时间里有最多的车辆从调到调到。425136756385577113223图1 点点出出发发的的车车辆辆数数应应该该与与点点到到达达的的车车辆辆数数相相同同，除除和和以以外外的的各各中中间间点点，进进的的车车辆辆数数应应该该与与离离去去的的车车辆辆数数应该相同。应该相同。x xijij 是通过弧是通过弧(i i，j j)的车辆数。的车辆数。（1）（4

19、）（5）（6）（2）（3）对所有弧（对所有弧（i i，j j），应满足约束），应满足约束 满满足足（1 1）（7 7）的的解解称称为为从从到到的的一一个个可可行行流，流，我我们们的的目目的的：在在所所有有可可行行流流中中求求出出一一个个方方案案，使得这个可行流得到的使得这个可行流得到的 f f 最大。最大。若若从从收收点点到到发发点点连连接接一一条条假假想想弧弧(7(7，1)1)，设设它它的的容量容量c c7171=，那么，那么 对点对点：对点对点：最大流问题的目标为最大流问题的目标为 （7）（8）（9）（10）所所以以，对对于于发发点点为为V Vs s，收收点点为为V Vt t的的网网络络N

20、 N（V V，U U），当当增增加加一一条条约约束束为为c ctsts=的的假假想想弧弧（t t，s s）后后，最最大大流问题就成为：流问题就成为：容量约束：容量约束：平衡条件：平衡条件：目标函数：目标函数：（11）（12）（13）（二）求最大流的方法：弧标号法 尽管最大流问题可以用线性规划模型描述，但是尽管最大流问题可以用线性规划模型描述，但是我们一般并不用求解线性规划的方法求最大流，而是我们一般并不用求解线性规划的方法求最大流，而是用一种更为简便明了的图上作业法用一种更为简便明了的图上作业法弧标号法弧标号法，求，求解上述最大流问题。解上述最大流问题。为了便于弧标号法的计算，首先需要将最大流

21、问为了便于弧标号法的计算，首先需要将最大流问题（譬如图题（譬如图1 1）重新改画成为图）重新改画成为图2 2的形式。的形式。2416357st650230081023730071000055图2 在图在图2 2中，每条弧中，每条弧 上标有两个数字，其中，上标有两个数字，其中，靠近点靠近点 i 的是的是 ，靠近点，靠近点 j j 的是的是 。如。如 表示从表示从到到的最大通过量是的最大通过量是5 5（百辆），从（百辆），从到到的最大通过量是的最大通过量是0 0；表示从表示从到到和从和从到到都可以通过都可以通过2 2（百辆）；等等。（百辆）；等等。2416357st6502300810237300

22、71000055图2 求最大流的基本步骤：求最大流的基本步骤：弧弧标标号号法法求求最最大大流流的的过过程程，就就是是对对图图2 2反反复复地地进行修改的过程，其计算步骤如下：进行修改的过程，其计算步骤如下：步步骤骤1.1.从从发发点点s s到到收收点点t t选选定定一一条条路路，使使这这条条路路通通过过的的所所有有弧弧V Vijij的的前前面面约约束束量量c cijij都都大大于于0 0，如如果果找找不不到到这这样样的的路路，说说明明已已经经求求得得最最大大流流，转转步步骤骤4 4。步步骤骤2.2.在在选选定定的的路路上上，找找到到最最小小的的容容许许量量c cijij定为定为P P。步步骤骤

23、3.3.对对选选定定的的路路上上每每条条弧弧的的容容量量作作以以下下修修改改，对对于于与与路路同同向向的的弧弧，将将c cijij修修改改为为c cijij-P P，对对于于与与路路反反向向的的弧弧，将将c cijij修修改改为为c cijij+P P。修修改改完完毕毕后后再再转入步骤转入步骤1 1。步步骤骤4.4.用用原原图图中中各各条条弧弧上上起起点点与与终终点点数数值值减减去去修修改改后后的的图图中中对对应应点点的的数数值值，得得到到正正负负号号相相反反的的两两个个数数，并并将将从从正正到到负负的的方方向向用用箭箭头头表表示示。这样，就得到一个最大流量图。这样，就得到一个最大流量图。下面

24、，我下面，我们们用弧用弧标标号法求解号法求解图图2中的最大流。中的最大流。第一次修改第一次修改：（1）从从发发点点s到到收收点点t找找一一条条路路，使使得得这这条条路路上上的的所所有有弧弧前前面面的的约约束束量量 。从从图图2 2中中可可以以看看出出，显显然然，就就是是满满足足这这样样的的条条件件的的一一条路。条路。（2）在路中,所以取 。（3）在路中，修改每一条弧的容量：通过第1次修改，得到图3。2416357st05023008162 3130611600055图3返回步骤（1），进行第2次修改。第二次修改第二次修改：选定，在这条路中，由于 ，所以，将 改为2，改为0，改为5，、改为3。修

25、改后的图变为图4。2416357st023203051623133611600055返回步骤（1），继续做第3次修改。图4第三次修改第三次修改：取，在这条，由于 ，所以将 改为0，改为5，改为0，改为4，改为1，改为2，改为3，改为5。修改后的图变为图5。2416357st005003231641135611600055图5返回步骤（1），继续做第4次修改。第四次修改：第四次修改：选定，在这条路中，由于 P=c67=1，所以将c14改为4,c41改为1,c46改为4,c64改为1,c67改为0，c76 改为7。修改后的图为变为图6。2416357st00500323164 1135701611

26、044图6返回步骤（1），继续做第5次修改。第五次修改第五次修改：选定,在这条路中，由于 P=c65 =1，所以将c14和c46均改为3，c65改为0，c57改为2，c41、c64、c56均改为2，c75改为6。修改后的图变为图7。2416357st005003222641136500622033图7 需要注意的是，由图7中可以看出，弧 本来在图2中是无容量可通过的，但经过几次修改，由 变成 ，即此时从到还可通过1（百辆），而从到，可以通过6（百辆）的容量，这说明，修改过程实际上是把计划中从到的通过车辆数减少了。取，在这条路中，由于P=c35=1，所以将 c14和 c46均改为2，c63改为5

27、,c35改为0，c57改为1，c41、c64、c53均改为3，c36改为2，c75改为7。修改后的图变为图8。2416357st005003312640237500533022图8 在图8中，从发点到收点，再也不存在连通的起点容量都大于零的弧了，所以图8为最大流图。转入步骤（4），用原图中各条弧上起点与终点数值减去修改后的图上各点的数值，将得到正负号相反的两个数，将这个数标在弧上，并将从正到负的方向用箭头表示,这样就得到最大流量图。例如原来弧 是 ，现在是 ，相减为5，那边为正，我们就记作 。这样，就得到图9，即最大流量。依这样的调度方式，可以从发点s调运14（百辆）汽车到收点t。(3,6)6

28、373371035542513672图9 最大流量图 图图10最大流最大流fmax的大小是确定的，但最大流的路线可以的大小是确定的，但最大流的路线可以不唯一。在上例中，如果从不同的路开始来修改图，不唯一。在上例中，如果从不同的路开始来修改图，也可能得到另外一个最大流图（图也可能得到另外一个最大流图（图1010）。）。2416357563233177235注意注意验证：验证：P104 例例2应用举例应用举例 一制造商需要把两个车间一制造商需要把两个车间D1,D2生产的同类商品生产的同类商品通过运输网络送到三个销售点通过运输网络送到三个销售点M1,M2,M3去，如图所去，如图所示。设各销售点计划销

29、售量分别为示。设各销售点计划销售量分别为10,8,8，问网络，问网络的运输能力能否满足这一要求？两个车间生产数的运输能力能否满足这一要求？两个车间生产数量多少最为恰当？量多少最为恰当？三、三、最小费用流及其求解方法最小费用流及其求解方法（补充）（补充）（一）最小费用流问题（一）最小费用流问题 如果在考虑网络上流量的同时，还要使得所安排流量的费用或者代价达到最小，就是所谓的最小费用流问题。在上例中，如果单位车辆数通过某一条弧要付出一定的代价，其代价如图11。425136743313324223222图11 代价条件 425136756385577113223图1 约束条件 现在要从发点调动若干车

30、辆到收点去，约束条件为图1，代价条件为图11，要使所花费的代价达到最小，用式子表示，就是要在（1）（7）式的约束条件下，找到一个可行流f的流量（15）使其代价最小，即（16）式中：指单位车辆数通过弧 的代价。（二）求解最小流问题（二）求解最小流问题 求最小求最小费费用流的步用流的步骤骤和求最大流的步和求最大流的步骤骤几乎完全一致，只几乎完全一致，只是在步是在步骤骤（1）中，）中，选选代价和最小的路，即最短路。具体算法代价和最小的路，即最短路。具体算法如下：如下：求求发发点点s到收点到收点t的最小的最小费费用通路用通路P(s,t)，记该记该通路的通路的边边集集合合为为E(P);给给P(s,t)分

31、配最大可能流量分配最大可能流量f0=minc(x,y)|(x,y)E(P),对对所所有的有的(x,y)E(P),令令c(x,y)=c(x,y)-f0;对对E(P)饱和边，将单位饱和边，将单位费用改为费用改为，且当，且当x或或ys或或t时，将饱和边时，将饱和边(x,y)变为反向边变为反向边(y,x),令令 c(y,x)=f0,w(y,x)=-w(x,y)构成新网络。构成新网络。在新网在新网络络中重复中重复，直至从，直至从发发点到收点的流点到收点的流值值等于等于最大流或再找不到最小最大流或再找不到最小费费用通路用通路例：求下图网络中的最小费用流，图中每边上的第一个数字是例：求下图网络中的最小费用流

32、，图中每边上的第一个数字是容量容量c(i,j)=cij,第二个数字是单位费用第二个数字是单位费用w(i,j)解：（解：（1）求）求s到到t的最小费用通路的最小费用通路sbat，单位费用和为，单位费用和为4，最大流，最大流为为11，边，边ba饱和。饱和。（2）在新的网络中求）在新的网络中求s到到t的最小费用通路的最小费用通路sat，单位费用和为，单位费用和为5，最大流为，最大流为3，边，边at饱和。饱和。（3）在新的网络中求）在新的网络中求s到到t的最小费用通路的最小费用通路sbct，单位费用和为，单位费用和为6，最大流为，最大流为5，边，边sb饱和。饱和。（4）在新的网络中求）在新的网络中求s到到t的最小费用通路的最小费用通路sabct，单位费用和为，单位费用和为7，最大流为，最大流为3，边，边ct饱和。饱和。于是，图中的流分布为于是，图中的流分布为最小费用为：最小费用为：41153657311042513675,46,33,38,15,35,37,27,41,21,23,32,22,23,2表1最小费用流的求解过程 将各条路的流量相加，就得到最小费用流，如图12所示。2416357365303351770图12 最小费用流 这个最小费用流的总代价为：小小 结结 重点：重点：1、最短路问题结果分析；、最短路问题结果分析；2、最小费用最大流算法；、最小费用最大流算法；