第六章-运筹学图与网络优化PPT课件

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