《第六章运筹学图与网络优化ppt课件.ppt》由会员分享，可在线阅读，更多相关《第六章运筹学图与网络优化ppt课件.ppt（59页珍藏版）》请在三一办公上搜索。
1、第六章 图与网络优化,第六章 图与网络优化,第1节 图的基本概念第2节 树第3节 最短路问题第4节 网络最大流问题,第1节 图的基本概念,例1：我国北京、上海等十个城市间的铁路交通图如下图所示：,第1节 图的基本概念,例2：有甲、乙、丙、丁、戊五个球队，他们之间的比赛情况如下图所示：,第1节 图的基本概念,一、图的基本概念图：由一些点及一些点之间的连线组成。边：两点之间不带箭头的连线。弧：两点之间带箭头的连线。无向图：由点及边组成。有向图：由点及弧组成。,第1节 图的基本概念,图例：,第1节 图的基本概念,二、无向图的基本概念端点：两个点vi，vj属于V，边vi，vj属于E，称vi，vj是边的
2、端点。关连边：边vi，vj是点vi及点vj的关连边。环：边的两个端点相同。多重边：两个点之间多于一条的边。简单图：不含环和多重边的无向图。多重图：不含环，但含有多重边的无向图。,第1节 图的基本概念,次：以点vi为端点的边的个数。悬挂点：次为1的点。悬挂边：连结悬挂点的边。奇点：次为奇数的点。偶点：次为偶数的点。孤立点：次为零的点。,第1节 图的基本概念,图例：,不连通图,第1节 图的基本概念,三、无向图的基本性质任何无向图中，顶点次数的总和等于边数的2倍。任何无向图中，次为奇数的顶点必为偶数个。,第1节 图的基本概念,四、有向图的基本概念基础图：去掉有向图中所有弧上的箭头得到的无向图。始点、
3、终点：弧(vi，vj)中，称vi为弧的始点，vj为弧的终点。,第1节 图的基本概念,五、图的综合概念（一）无向图链：圈：,第1节 图的基本概念,初等链：链中没有重复的点。初等圈：圈中没有重复的点。简单链：链中没有重复的边。简单圈：圈中没有重复的边。,第1节 图的基本概念,图例：问：（v1，v2， v3， v4， v5， v3， v6， v7）？（v1， v2， v3， v6， v7）？（v1， v2， v3， v4， v1）？（v4， v1， v2， v3， v5， v7， v6， v3， v4）？（v1， v2， v3， v5， v4， v3， v4， v1）？,第1节 图的基本概念,（二）
4、有向图链：路：,第1节 图的基本概念,回路：初等路：路中没有重复的点。初等回路：回路中没有重复的点。,第1节 图的基本概念,图例：问： （v3，a3， v2， a5， v4， a6， v5， a8， v3）？（v1， a2， v3， a4， v4，a7， v6）？（v1， a2， v3， a8， v5，a10， v6）？（v1，a2， v3， a4， v4， a6， v5， a8， v3）？,第2节 树,一、树的概念连通图：无向图中任意两点间至少有一条链相连。（不连通图）连通分图：不连通图中每个连通的部分。树：连通且不含圈的无向图。,第2节 树,二、树的性质任何树中必然存在次为1的点。（1）树
5、中次为1的点称为树叶（2）树中次大于1的点称为分枝点树的点有n个，则该树的边必有（n-1）条。任何具有n个点、（n-1）条边的连通图必是树。树中任意两点之间有且只有唯一一条链。从一个树中去掉任一条边，则余下的图必是不连通图。在树中不相邻的两个点之间添上一条边，则必得到一个圈；反之再从该圈中任意去掉一条边，则必得到一个树。,第2节 树,图例：,第2节 树,三、支撑树支撑子图：支撑树：如果图G的支撑子图是一个树T，则称树T是图G的一个支撑树。支撑树的性质：图G有支撑树的充分必要条件是图G是连通图。,第2节 树,图例：,支撑子图,第2节 树,四、最小支撑树赋权图：最小支撑树：,第2节 树,最小支撑树
6、的求解方法方法一：避圈法基本做法：首先选一条最小权的边，以后每一步中，总从未被选取的边中选一条权最小的边，并使之与已选取的边不构成圈（每一步中，如果有两条或两条以上最小权的边，则任选一条）。,第2节 树,例3：某工厂内联结六个车间的道路网如下图所示。已知每条道路的长，要求沿道路架设联结六个车间的电话线网，使电话线的总长最小。,第2节 树,方法二：破圈法基本做法：任取一个圈，从圈中去掉一条权最大的边，（如果有两条或两条以上最大权的边，则任去一条），在余下图中重复这个步骤，一直到得到一个不含圈的图为止。,破圈法求解例3,习题6-1,习题6-1：分别用避圈法和破圈法求下述图的最小支撑树。1、 2、,
7、第3节 最短路问题,一、最短路的含义,第3节 最短路问题,例4：某单行线交通网如下图所示，每弧旁的数字表示通过这条单行线所需要的费用。现在某人要从v1出发，通过这个交通网到v8去，求使总费用最小的旅行路线。,第3节 最短路问题,二、最短路问题的求解方法（一）Dijkstra方法适用条件：无负权（ij0）的最短路问题基本思路：,第3节 最短路问题,基本解法：标号采用两种标号：T(Temporary)标号和P(Permanent)标号，T标号为临时标号，P标号为固定标号。给vi点一个P标号时，表示从vs到vi的最短路权，vi点的标号不再改变；给vi点一个T标号时，表示从vs到vi的最短路权的上界，
8、凡没有得到P标号的点都有T标号。方法的每一步就是把某一点的T标号改为P标号，当终点vt点得到P标号时，计算结束。,第3节 最短路问题,具体步骤：第一，给vs标上P标号P(vs)=0，其余各点为T标号，T(vj)=+。第二，若vi是刚标上P标号的点，选取所有与vi有关联的弧( vi，vj )中的vj点，且vj点为T标号，去修改vj点的T标号： 。第三，比较所有具有T标号的点，把最小的T标号值所对应的点改为P标号，即 （如果存在两个或两个以上的最小T标号，则同时改为P标号），若所有点都获得P标号，停止计算（除去从vs到vj之间无路可走，即T(vj)=+=P(vj)）；否则转入第二。,Dijkstr
9、a方法求解例4,第3节 最短路问题,例5：用Dijkstra方法求解下图中从v1到v8的最短路。,习题6-2,习题6-2：用Dijkstra方法求解下列各图从v1到v7的最短路。1、,习题6-2,2、,第3节 最短路问题,（二）赋权无向图的最短路问题的求解方法赋权无向图G=(V，E)，边vi，vj表示既可以从vi到达vj，也可以从vj到达vi，所以边vi，vj可以看作是两条弧(vi，vj)和(vj，vi)，且它们具有相同的权ij。,第3节 最短路问题,例6：计算下图所示赋权无向图中v1到v7的最短路 。,第3节 最短路问题,小结对于赋权无向图G=(V，E)，从始点vs到各个点的最短路，即为最短
10、链Dijkstra方法不仅适用于赋权有向图D，也适用于赋权无向图GDijkstra方法直接给出某点（设为vs）到其他所有点的最短路；不能直接给出赋权图上任意两点间的最短路Dijkstra方法只适用于全部权为非负情况，如果某权为负，则算法失效。,第3节 最短路问题,例7：求下图中从vs到v1的最短路。,权为负数,习题6-3,习题6-3：用Dijkstra方法求解下图从v1到v9的最短路。,第3节 最短路问题,三、最短路问题的应用设备更新问题,第3节 最短路问题,例10：某工厂使用一台设备，每年年初工厂都要作出决定，如果继续使用旧的，要付维修费；若购买一台新设备，要付购买费。试制定一个5年的更新计
11、划，使总支出最少。已知设备在各年的购买费，及不同机器役龄时的维修费如下表所示：,第3节 最短路问题,例10：解：转化为最短路问题点vi表示第i年年初购进一台新设备弧（vi，vj）表示第i年年初购进的设备一直使用到第j年年初权ij表示第i年年初购进设备，一直使用到第j年年初所需支付的购买、维修的全部费用,第3节 最短路问题,最短路问题图示：,第4节 网络最大流问题,例11：已知联结某产品产地v1和销地v6的交通网，如下图所示。每一弧(vi，vj)代表从vi到vj的运输线，产品经过这条弧由vi输送到vj，弧旁的数字表示这条运输线的最大通过能力。产品经过交通网从v1输送到v6。要求制定一个运输方案，
12、使从v1运输到v6的产品数量最多。,网络,流量最大,习题6-4,第4节 网络最大流问题,一、基本概念和性质发点、收点、中间点、容量、网络：有向图D=(V，A)，D的每条弧(vi，vj)上有非负数cij称为弧的容量，在V中指定一点称为发点（记为vs），另一点称为收点（记为vt），其余点称为中间点，这样的D称为一个网络，记作D=(V，A，C)。流、流量：定义在网络D中的弧集合A上的一个函数f=fij称为流，称fij为弧(vi，vj)上的流量。流的性质：每个弧上的流量不超过该弧的容量。中间点的净输出量为零。,第4节 网络最大流问题,可行流：满足下述条件的流f称为可行流，记作v(f)。（1）容量限制条
13、件：对网络D中每条弧(vi，vj)，有0fijcij（2）平衡条件：中间点每条弧vi：流出量与流入量相等发点vs、收点vt：从点vs流出的量等于点vt流入的量可行流的性质：可行流总是存在的。零流：网络D中所有弧的流量fij=0的可行流。,第4节 网络最大流问题,可行流,第4节 网络最大流问题,最大流问题：在网络D中，求流量最大的可行流，记作v(f)。饱和弧、非饱和弧、零流弧、非零流弧：（1）饱和弧：网络D中fij=cij的弧（2）非饱和弧：网络D中fijcij的弧（3）零流弧：网络D中fij=0的弧（4）非零流弧：网络D中fij0的弧,第4节 网络最大流问题,链：网络D中联结发点vs和收点vt
14、的一条链，定义链的方向是从vs到vt。（1）前向弧+：弧的方向与链的方向一致（2）后向弧-：弧的方向与链的方向相反增广链：f是一个可行流，是从vs到vt的一条链，若满足则称为从vs到vt关于f的增广链。增广链的实际意义：沿着链从vs到vt输送的流还有潜力可挖，即可以把流量提高。定理：可行流f是最大流的充分必要条件是不存在从vs到vt关于f的增广链。,第4节 网络最大流问题,根据例11所描述的问题：找出链（v1，v2，v3，v4，v5，v6）的前向弧和后向弧。,链,第4节 网络最大流问题,根据例11所描述的问题：给出一个运输方案，如下图所示。试说明链（v1，v2，v3，v4，v5，v6）是否为增
15、广链？,增广链,第4节 网络最大流问题,二、求解方法标号法解题过程：从一个可行流f出发，（1）标号过程：通过标号寻找增广链（2）调整过程：沿增广链调整f以增加流量基本解法：标号点：用vj（，）表示表示vj点标号是从哪一点得到的，用vi表示表示vj点与之间的关系，用+或-表示,第4节 网络最大流问题,具体步骤（一）标号过程第一，给vs标上（0，+），则vs是标号未检查点，其余各点都是未标号点。第二，取标号未检查点vi，对所有未标号点vj有：1）若在弧（vi，vj）上，fijcij，则给vj标上（vi，+）；2）若在弧（vk，vi）上，fki0，则给vk标上（vi，-）。则vj（vk）成为标号未检
16、查点，而vi成为标号已检查点，在vi标号下面划一横线重复1）2），直至vt被标上号，则得到一条从vs到vt的增广链，转入调整过程。第三，若所有标号都已检查过，而标号过程进行不下去时，则停止计算，此时获得的可行流为最大流f 。,第4节 网络最大流问题,（二）调整过程第一，按照vt及其它各点标号的第一个部分反向追踪，找出增广链。第二，则获得新的可行流，重复标号过程调整过程，直至得出最大流f，其流量v(f)=发点vs的流出量收点vt的流入量。,第4节 网络最大流问题,例12：求下图所示网络中的最大流，弧旁的数字是（cij，fij）。,第4节 网络最大流问题,例13：求下图所示网络从vs到vt的最大流，弧旁的数字是（cij，fij）。,第4节 网络最大流问题,小结在计算过程中，应注意采用“先标号的先检查”的原则，从而保证以尽可能少的调整次数求得网络最大流。,习题6-4,习题6-4：用标号法求下图所示网络从v1到v6的最大流，弧旁的数字是（cij，fij）。,
