管理运筹学管理科学方法

1、管理运筹学管理运筹学-管理科学方法管理科学方法中国人民大学出版社谢家平谢家平 编著编著OR:SM2 理解图论中结点、边、链、弧、路径的概念理解图论中结点、边、链、弧、路径的概念 了解树的概念、最小树的求解方法及其应用了解树的概念、最小树的求解方法及其应用 掌握最短路的标号算法及网络选址中的应用掌握最短路的标号算法及网络选址中的应用 理解网络流的概念及其网络瓶颈的识别方法理解网络流的概念及其网络瓶颈的识别方法 正确理解最小费用流的调整改进思路和方法正确理解最小费用流的调整改进思路和方法OR:SM31818世纪，哥尼斯堡城中有一条普雷格尔河，河上有七座桥将河中的世纪，哥尼斯堡城中有一条普雷格尔河，

2、河上有七座桥将河中的两个小岛与河岸连接起来。人们提出了这样的问题：一个散步者能否两个小岛与河岸连接起来。人们提出了这样的问题：一个散步者能否从某地出发，走遍七桥且每座桥恰好经过一次，最后回到原地？从某地出发，走遍七桥且每座桥恰好经过一次，最后回到原地？ 陆地A陆地B岛D岛CAD B C 1736 1736年瑞士数学家欧拉将两岸和小岛抽象为四个点，将桥抽年瑞士数学家欧拉将两岸和小岛抽象为四个点，将桥抽象为七条边，此问题归结为一笔画问题。象为七条边，此问题归结为一笔画问题。OR:SM4第一节第一节 图论的概念图论的概念一、图的内涵一、图的内涵 1 1、图的定义、图的定义 v1 v4v2 v3e1e

3、2e3e4e5e6 v1 v4v2v3 e1e2e3e4e5e6 v1 v2 v3 v4e1e2e3e4e5e6图论的图与一般几何图形或代数函数图形是完全不同的图论的图与一般几何图形或代数函数图形是完全不同的 图论中的图图论中的图:由一些点和连接点的线所组成的由一些点和连接点的线所组成的“图形图形” 点和线的位置是任意的点和线的位置是任意的 线的曲直、长短与实际无关，代表的只是点与点之间的相互关系线的曲直、长短与实际无关，代表的只是点与点之间的相互关系例：例：表示表示苏州苏州v1 、杭州、杭州v2 、上海、上海v3 、南京、南京v4仓储网点之间的物流运输线路关系仓储网点之间的物流运输线路关系

4、OR:SM5第一节第一节 图论的概念图论的概念一、图的内涵一、图的内涵 2 2、图的分类、图的分类 l 不带箭头的连线称为不带箭头的连线称为“边边”，如公路运输线路；，如公路运输线路；l 带箭头的连线称为带箭头的连线称为“弧弧”，如供排水的管道运输线路，如供排水的管道运输线路。1 1、无向图、无向图 由点和边的集合所构成由点和边的集合所构成由点和弧的集合所构成由点和弧的集合所构成 2 2、有向图、有向图 链：链：无向网络中，前后相继点和边无向网络中，前后相继点和边的交替序列称为一条链。的交替序列称为一条链。 圈：圈：闭合的链称为一个圈。闭合的链称为一个圈。 路径：路径：有向网络图中，前后相继并

5、且有向网络图中，前后相继并且方向一致的点弧序列称为一条路径。方向一致的点弧序列称为一条路径。 回路：回路：闭合的路径称为一个回路。闭合的路径称为一个回路。 OR:SM6第二节第二节 最小树问题最小树问题一、最小树的涵义一、最小树的涵义 1 1、树的定义、树的定义 无圈的连通图就是一棵树。无圈的连通图就是一棵树。所谓连通图是指网络中任意两个结点之间都至少有一条链相连。所谓连通图是指网络中任意两个结点之间都至少有一条链相连。2 2、树的性质、树的性质 性质性质1 1 任何树至少有一个悬挂结点。任何树至少有一个悬挂结点。 性质性质2 2 树中任意两点之间有且只有一条链。树中任意两点之间有且只有一条链

6、。 性质性质3 3 树中任意两个不相邻的结点之间增加一条边，则形成唯一的圈。树中任意两个不相邻的结点之间增加一条边，则形成唯一的圈。 性质性质4 4 如果树的结点是如果树的结点是m个，则边的个数为个，则边的个数为m-1个。个。 性质性质5 5 在树中任意去掉一条边，将得到一个不连通图。在树中任意去掉一条边，将得到一个不连通图。 3 3、最小树、最小树把一棵树各边的权数总和，称为该树的树权。把一棵树各边的权数总和，称为该树的树权。权数总和为最小的那棵支撑树，称为最小支撑树，简称最小树。权数总和为最小的那棵支撑树，称为最小支撑树，简称最小树。OR:SM7第二节第二节 最小树问题最小树问题二、最小树

7、的求法二、最小树的求法 1 1、破圈法、破圈法 从无向网络中任选一个圈，去掉圈中权数最大的边，便破一圈；从无向网络中任选一个圈，去掉圈中权数最大的边，便破一圈；如果最大权数的边不止一条，则任选其一去掉。如此反复操作，如果最大权数的边不止一条，则任选其一去掉。如此反复操作，直至网络中不含圈为止。此时的支撑树就是最小树。直至网络中不含圈为止。此时的支撑树就是最小树。 2 2、闭圈法、闭圈法 从无向网络中，开始选取权数最小的一条边，再选权数为次小从无向网络中，开始选取权数最小的一条边，再选权数为次小的一条边；如此进行，总从剩余边中选取权数最小者，但前提的一条边；如此进行，总从剩余边中选取权数最小者，

8、但前提是与已经选择的边不要构成圈；如果最小权数的边不止一条，是与已经选择的边不要构成圈；如果最小权数的边不止一条，则任选一条。则任选一条。OR:SM8第二节第二节 最小树问题最小树问题二、最小树的求法二、最小树的求法 例：一家企业分别要在例：一家企业分别要在6 6间办公室铺设网线接入口，网线的可行间办公室铺设网线接入口，网线的可行走线方式如下图所示，已知办公室之间的走线距离，应如何铺走线方式如下图所示，已知办公室之间的走线距离，应如何铺设网线才能使网线总长为最短？设网线才能使网线总长为最短？ 最短网线总长度为最小树权之和最短网线总长度为最小树权之和2+3+4+6+6=21 v3e28 2 3

9、546 6 6 8v1v4v2v3v5v6OR:SM9第三节第三节 最短路问题最短路问题一、双标号算法一、双标号算法 狄克斯特拉狄克斯特拉(Dijkstra)算法算法u路权：弧路权：弧(vi, vj)的权为的权为wij；路权是路路权是路p中各条弧权之和中各条弧权之和u最短路：在所有从最短路：在所有从vs到到vt 的路的路p中，求一条路权最短的路中，求一条路权最短的路u算法说明：算法说明： 1959年提出，目前公认的最短路算法年提出，目前公认的最短路算法 适合于求解所有弧权适合于求解所有弧权wij 0的最短路问题的最短路问题u算法假设：有向图算法假设：有向图D D是完备图是完备图 图图D中任意两

10、点中任意两点vi , vj 之间，恰有两条弧之间，恰有两条弧(vi , vj)和和(vj , vi) 若若vivj 不存在弧不存在弧, 可设想一条从可设想一条从vi vj 的弧的弧, 权权wij=+； 若若vi vj 有重复的弧，则保留弧权最小的弧有重复的弧，则保留弧权最小的弧OR:SM10第三节第三节 最短路问题最短路问题一、双标号算法一、双标号算法 1 1、标号法的基本思路标号法的基本思路 u基本思路基本思路: : 从始点vs 出发，逐步探寻，给每个点标号； 标号分永久标号P(vk)和临时标号T(vk) 两种：永久标号永久标号P(vk) 是从点是从点 vs vk 的最短路权的最短路权临时标

11、号临时标号T(vk) 是从点是从点 vs vk 最短路权的上界最短路权的上界 算法的每一步从临时标号集中选最小者变为永久标号； 经过逐次改变，就可以得到从点vs 到各点的最短路。 u标号形式：标号形式： 单标号法是对每一点赋予一个路权标号 双标号法是对每一点赋予两个标号：路标、路权OR:SM11第三节第三节 最短路问题最短路问题一、双标号算法一、双标号算法 2 2、标号法的具体步骤、标号法的具体步骤 n首先，给网络始点标上永久标号 ，给从网络始点出发的各弧（一步可达）的结点标上临时标号 。n第二，在所有临时标号中选择路权最小者，则将结点的临时标号变为永久标号，在标号下画横线。n第三，接着考察刚

12、刚获得永久标号的结点 ，修改从结点 出发的各弧的点 的临时标号。 如果 ,则结点的临时标号不变； 反之，就将结点的临时标号变为 ( , ) ，并划去其原有较大的标号。n依此类推，当所有标号都是永久标号，则标号过程结束。 (,0)sv(,)sjv djiijddwivivjviijdwivOR:SM12第三节第三节 最短路问题最短路问题一、双标号算法一、双标号算法 3 3、标号法的算法举例、标号法的算法举例 例：用双标号法求下图网络最短路例：用双标号法求下图网络最短路3947326141287110sv2v1v5v4v6v3vtvOR:SM13第三节第三节 最短路问题最短路问题一、双标号算法一、

13、双标号算法 第一步：第一步：3947326141287110(,0)sv(,3)sv(,9)sv(,10)sv(,)sv (,)sv (,)sv (,)sv svsv2v1v5v4v6v3vtvOR:SM14第三节第三节 最短路问题最短路问题一、双标号算法一、双标号算法 第二步：第二步：3947326141287110(,0)sv(,9)sv(,10)sv(,)sv (,)sv sv2v1v5v4v6v3vtv(,3)sv1( ,5)v1( ,7)vOR:SM15第三节第三节 最短路问题最短路问题一、双标号算法一、双标号算法 第三步：第三步：3947326141287110(,0)sv(,9)

14、sv(,10)sv(,)sv sv2v1v5v4v6v3vtv(,3)sv5(,6)v5(,13)v1( ,5)vOR:SM16第三节第三节 最短路问题最短路问题一、双标号算法一、双标号算法 最终：最终：依此类推，重复上述标号过程。得最短路。依此类推，重复上述标号过程。得最短路。 3947326141287110(,0)svsv2v1v5v4v6v3vtv(,3)sv3(,11)v6(,12)v4(,9)v5(,6)v1( ,5)v(,9)svOR:SM17第三节第三节 最短路问题最短路问题二、策略递推法二、策略递推法 狄克斯特拉标号算法只适合所有弧权0的情况，当赋权有向图中存在负权（0）时，

15、标号算法失效。可以借助动态规划的递推方程，进行迭代寻求最短路 递推法的基本思路递推法的基本思路 从从 到到 任一点的最短路权记为任一点的最短路权记为 ，根据最短路，根据最短路的特性，若的特性，若 是是 到到 的最短路，的最短路，则则 一定是一定是 到到 的最短路，其的最短路，其路权为路权为 。故故 必定满足方程：必定满足方程：svjv(,)sjd v v skijvvvvsvjvskivvvsviv(,)sid v v(,)sjd v v(,)min (,)sjsiijd v vd v vw。OR:SM18第三节第三节 最短路问题最短路问题二、策略递推法二、策略递推法 例：用递推算法求解下表中

16、例：用递推算法求解下表中 到其余各点的最短路到其余各点的最短路 1v结点结点0828034230858066456066601v2v3v4v5v6v1v2v3v4v5v6vOR:SM19第三节第三节 最短路问题最短路问题二、策略递推法二、策略递推法 最短路的函数迭代过程最短路的函数迭代过程 11jd21jd31jd41jd结点0828034230858066456066601v2v3v4v5v6v1v2v3v4v5v6v0820521070521071305210713OR:SM20第三节第三节 最短路问题最短路问题二、策略递推法二、策略递推法 各结点之间的最短距离矩阵各结点之间的最短距离矩阵

17、 结点结点05210713503104102308511101080667456061310116601v2v3v4v5v6v1v2v3v4v5v6vOR:SM21第三节第三节 最短路问题最短路问题三、最短路的应用三、最短路的应用 1 1、网络的中心、网络的中心所谓网络的中心是指一个网络中，选择某一点，使之其所谓网络的中心是指一个网络中，选择某一点，使之其余各点到该中心点的距离之和为最小。余各点到该中心点的距离之和为最小。例：如果要在下表中例：如果要在下表中6 6个销售点中选一个作为仓库所在地，应个销售点中选一个作为仓库所在地，应该建在哪个经销点，使其余各销售点都离它较近？该建在哪个经销点，使

18、其余各销售点都离它较近？OR:SM22第三节第三节 最短路问题最短路问题三、最短路的应用三、最短路的应用 2 2、网络的重心、网络的重心引进点的权系数，将权系数与最短距离阵各列对应元素加权引进点的权系数，将权系数与最短距离阵各列对应元素加权求和，再从中选择最小的即为网络重心。求和，再从中选择最小的即为网络重心。OR:SM23第四节第四节 网络最大流网络最大流一、相关概念与定理一、相关概念与定理1 1、弧容量与容量网络、弧容量与容量网络 对于有向图对于有向图 D=(V,A),，弧，弧 的的容量容量表示弧的最大流通能力。表示弧的最大流通能力。在在V中指定一点称为发点中指定一点称为发点(记为记为vs

19、 )，另一点称收点，另一点称收点(记为记为vt)，其余点，其余点叫中间点，这样的赋权有向图就称为一个叫中间点，这样的赋权有向图就称为一个容量网络容量网络，记，记N=(V,A,B)2 2、弧的流量与可行流、弧的流量与可行流 弧的实际通过量称为该弧的流量。弧集弧的实际通过量称为该弧的流量。弧集A上的流量集合上的流量集合 称为网络上的流。称为网络上的流。满足下述条件的流称为可行流。满足下述条件的流称为可行流。 容量限制：对每条弧容量限制：对每条弧 ，都有，都有 平衡条件：中间点流出量平衡条件：中间点流出量= =流入量流入量 ijfx0ijijxbAvvji),(),(jivvOR:SM24第四节第四

20、节 网络最大流网络最大流一、相关概念与定理一、相关概念与定理3 3、前向弧与后向弧、前向弧与后向弧 4 4、饱和弧与非饱和弧、饱和弧与非饱和弧 弧弧 的流量的流量 与之容量与之容量 比较：比较： 满足满足 的弧称为饱和弧，弧的流量不能再扩充；的弧称为饱和弧，弧的流量不能再扩充； 满足满足 的弧称为非饱和弧，弧的流量允许再被扩大。的弧称为非饱和弧，弧的流量允许再被扩大。是从是从vs 到到vt 的链，方向从的链，方向从vs vt ，则链，则链上的弧分为两类上的弧分为两类 前向弧：弧的方向与链前向弧：弧的方向与链的方向的方向，记，记+ 后向弧：弧的方向与链后向弧：弧的方向与链的方向的方向，记，记-)

21、,(jivvijbijijxbijijxbijx5 5、零弧与非零弧、零弧与非零弧 满足满足 的弧称为零弧。由于的弧称为零弧。由于 ，所以弧的流量不能减小；所以弧的流量不能减小； 满足满足 的弧称为非零弧。弧的流量可以被减小，的弧称为非零弧。弧的流量可以被减小，但要满足但要满足 0。 0ijx 0ijx 0ijx ijx OR:SM25第四节第四节 网络最大流网络最大流一、相关概念与定理一、相关概念与定理6 6、流量可以扩充的路、流量可以扩充的路 设设 是一可行流，是一可行流，是从是从vs 到到vt 的链，若链的链，若链满足：满足： 上的所有前向弧为非饱和弧，即满足上的所有前向弧为非饱和弧，即

22、满足 ，可以扩充流量，可以扩充流量 上的所有后向弧为非零弧，即满足上的所有后向弧为非零弧，即满足 ，可以减少流量；，可以减少流量；则称是一条关于可行流则称是一条关于可行流 的可扩充流量的路，亦称增广链。的可扩充流量的路，亦称增广链。 ijfxijijxb0ijx f7 7、流量可以扩充的路、流量可以扩充的路 可行流中，网络发点的流出量（或网络收点的流入量）就可行流中，网络发点的流出量（或网络收点的流入量）就是网络的流量。是网络的流量。一个容量网络的诸可行流中，网络流量最大的可行流，称一个容量网络的诸可行流中，网络流量最大的可行流，称为最大流为最大流 OR:SM26第四节第四节 网络最大流网络最

23、大流二、求最大流标号法二、求最大流标号法 1956年，福特和富尔克逊提出了寻求网络最大流的基本方法，年，福特和富尔克逊提出了寻求网络最大流的基本方法，称为福特称为福特-富尔克逊算法（富尔克逊算法（Fold-Fulkerson Algorithm）。）。给定可行流给定可行流X=xij ，标号判断有无增广链，标号判断有无增广链 先给先给vs 标上标上(vs, +)，vs已标号尚未检查，其余未标号已标号尚未检查，其余未标号 取一个已标号但未检查的点取一个已标号但未检查的点vi进行检查，对未标号点进行检查，对未标号点vj ：前向弧(vi, vj)可以扩充流量(xijrij) vj尚未标号，则给vj 标

24、号(vi，+)，vj 成为己标号尚未检查的点后向弧(vk, vi)可以减少流量(xki0) vk尚未标号，则给vk 标号(vi, -)，vk成为己标号尚未检查的点vi 成为已标号已检查的点，在其标号下划横线 检查收点检查收点vt 是否已标号：是否已标号：vt被标上号则找到增广链，进行流量调整；否则转第步若所有标号都已检查，vt又未标号，则不存在增广链标号过程标号过程 OR:SM27第四节第四节 网络最大流网络最大流二、求最大流标号法二、求最大流标号法 流量调整过程流量调整过程 反向追踪找出反向追踪找出vs 到到vt 的增广链的增广链 计算增广链计算增广链上可调整的流量上可调整的流量),(),(

25、minjiijjiijijvvxvvxr 调整可行流的流量，得新的可行流调整可行流的流量，得新的可行流xij ),(),(),(jiijjiijjiijijvvxvvxvvxx 抹去所有标号，对新的可行流抹去所有标号，对新的可行流X =xij，重新进入标号过程，重新进入标号过程OR:SM28第四节第四节 网络最大流网络最大流二、求最大流标号法二、求最大流标号法 例：例：下图表示了企业所处的供应市场（下图表示了企业所处的供应市场（v1和和v2）、配送中心（）、配送中心（v3和和v4、以及销售市场（、以及销售市场（v5、v6和和 v7）组成的网络，各弧上括号里的）组成的网络，各弧上括号里的前一个数

26、字表示弧的容量，后一个数字是目前的实际流量。前一个数字表示弧的容量，后一个数字是目前的实际流量。试求这个供应试求这个供应-销售网络的最大流方案。销售网络的最大流方案。 1v2v3v4v5v6v(4,3)(10,6)(15,9)(4,4)(5,5)(6,3)(6,6)7vOR:SM29第四节第四节 网络最大流网络最大流二、求最大流标号法二、求最大流标号法 供应供应- -销售网络的可行流销售网络的可行流 (4,3)(10,6)(15,9)(4,4)(5,5)(6,3)(6,6)(15,6)(12,12)(5,4)(10,8)(8,6)1v2v3v4v5v6v7vtvsvOR:SM30第四节第四节

27、网络最大流网络最大流二、求最大流标号法二、求最大流标号法 供应供应- -销售网络的可扩充路销售网络的可扩充路 (4,3)(10,6)(15,9)(4,4)(5,5)(6,3)(6,6)(15,6)(12,12)(5,4)(10,8)(8,6)1v2v3v4v5v6v7vtvsv(+ ,)(+ ,4)(+ ,9)(- ,3)(+ ,3)(+ ,3)(+ ,2)sv1v2vsv3v4v6vOR:SM31第四节第四节 网络最大流网络最大流二、求最大流标号法二、求最大流标号法 调整后的可行流调整后的可行流 最大流量为最大流量为1256720sstttfxxxxx(4,1)(10,8)(15,11)(4

28、,4)(5,5)(6,5)(6,6)(15,8)(12,12)(5,4)(10,10)(8,6)1v2v3v4v5v6v7vtvsvOR:SM32第四节第四节 网络最大流网络最大流三、网络的瓶颈识别三、网络的瓶颈识别 1 1、截集、截集- -截量与最小截集截量与最小截集 2 2、最大流、最大流- -最小截量定理最小截量定理 网络中，任一可行流的流量恒不超过任一截集的截量，网络中，任一可行流的流量恒不超过任一截集的截量，称为流量称为流量-截量定理。截量定理。 最小截量的大小影响总流量的提高最小截量的大小影响总流量的提高 截集截集： 对于网络对于网络N=(V,A,R)，将，将V分为两个非空集合分为

29、两个非空集合S和和S，使，使发点发点vsS，收点，收点vtS 所有起点属于所有起点属于S而终点属于而终点属于S的弧的集合称为截集的弧的集合称为截集 (S,S)截量截量：截集：截集(S,S) 中所有弧的容量之和中所有弧的容量之和 r(S,S) 最小截集最小截集：截量最小的截集：截量最小的截集OR:SM33第五节第五节 最小费用流最小费用流一、调整法求解步骤一、调整法求解步骤 先不考虑费用问题，求得任一可行流先不考虑费用问题，求得任一可行流X 据此构造赋权有向图据此构造赋权有向图W(X) 顶点是原网络N的顶点弧权根据可行流X确定 弧(vi, vj)的流量可以增加，则照原方向画弧，标上费用bij 弧(vi, vj)的流量可以减少，则照反方向画弧，标上费用-bij 在赋权有向图在赋权有向图W(X)中寻找负回路中寻找负回路(总权为负值的回路总权为负值的回路)：若没有负回路，则得到最小费用流若存在负回路，则调整与负回路相对应的弧上的流量 计算调整量计算调整量，进行流量调整，进