运筹学中中的数学问题及模型.ppt

《运筹学中中的数学问题及模型.ppt》由会员分享，可在线阅读，更多相关《运筹学中中的数学问题及模型.ppt（86页珍藏版）》请在三一文库上搜索。

1、2021/6/7,1,第一章 运筹学中的几个数学问题及模型,本章主要介绍运筹学中的几个数学问题及模型，即线性规划问题、运输问题、图与网络优化技术等。学习的重点是基本概念。1.线性规划问题及其数学模型问题2.运输问题3.树和最小支撑树问题4.最短路径问题5.网络最大流问题6.最小费用最大流问题7.中国邮递员问题8. NP-完备性,2021/6/7,2,数学预备知识：矩阵的基本概念及初等运算参考文献1.运筹学教材编写组编，运筹学，清华大学出版社，2005年6月第3版2. 田丰、马仲番编著，图与网络流理论，科学出版社，1987年3. 刘振宏、 蔡茂城(译)，组合最优化：算法和复杂性，清华大学出版社,

2、1988 年第1版4. C.H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Printice-Hall, 1982,2021/6/7,3,运筹学的性质和特点,运筹学是一门应用科学，至今还没有统一且确切的定义。在此提出以下几个定义来说明运筹学的性质和特点： 定义1: 为决策机构在对其控制下的业务活动进行决策时, 提供以数量化为依据的科学方法. 特点1: 该定义强调的是科学方法,以定量化为基础,利用数学工具.但任何决策都包含定量和定性两个方面,而定性方面又不能简单地用

3、数学表示,如政治、社会等因素，只有综合多种因素的决策才是全面的。运筹学工作者的职责是为决策者提供可以量化方面的分析，并指出那些是定性因素。,2021/6/7,4,定义2：运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据。 特点2：该定义表明运筹学具有多学科交叉的特点，如综合应用经济学、心理学、物理学和化学中的一些方法。 特点3：由系统的观点研究功能关系。 综上所述，运筹学的定义可以提炼为： 定义3：运筹学就是利用计划的方法和多学科专家组成的队伍，把复杂的功能关系表示成数学模型，其目的是通过定量分析为决策和揭露新问题提供数量

4、依据。,2021/6/7,5,运筹学与计算机,计算机是运筹学发展的基本因素，对任何实际问题，没有现代计算机用来产生最终结果，大多数运筹学技术是完全不能实现的。许多大规模运筹技术的应用只需计算机几分钟的时间，而用人工则需要很长时间。更为重要的是计算机能快速利用某些类型的管理信息，而没有这些信息，许多运筹设计是没有意义。 计算机是运筹学不可分割的部分和不可缺少的工具，而且计算机方法和运筹学方法是并行发展的。预计今后运筹学和计算机方法的分界线将会消失，并将组成更通用、更广泛的管理科学的形式。,2021/6/7,6,运筹学的工作步骤,1. 提出和形成问题：要弄清问题的目标，可能的约束，问题的可控变量以

5、及有关参数。2. 建立模型：把问题中可控变量、参数和目标与约束之间的关系用一定的模型表示出来。3. 求解：用数学方法将模型求解。解可以是最优解、次优解、满意解。复杂模型的求解需用计算机,解的精度要求由决策者提出。4. 解的检验：先检验求解步骤和程序有无错误，然后检查解是否反映现实问题。5. 解的控制：通过控制解的变化过程决定对解是否要作一定的修改。6. 解的实施：将解用到实际中去，必须考虑到实际的问题，如向实际部门讲清楚解的用法，在实施中可能产生的问题等。 以上过程应反复进行。,2021/6/7,7,1.线性规划问题及其数学模型问题,例1：某工厂在计划期内安排生产、两种产品，已知生产单位产品所

6、需的设备台时、A、B两种原材料的消耗及两种产品每件可获利润见如下表1-1所示：问如何安排计划使该工厂获利最多？,2021/6/7,8,表11,2021/6/7,9,解：假设 x1、x2分别表示在计划期内生产产品I、II的数量，则该计划问题可用如下数学模型表示为： 目标函数 Max Z = 2x1 +3x2 约束条件其最优解为x1=4, x2=2, 最优值为z=14。,2021/6/7,10,例2:（营养问题）某养鸡场所用的混合饲料是由 n 种配料组成。要求这种混合饲料必须含有 m 种不同的营养成份，而且要求每单位混合饲料中第i种营养成份的含量不能低于bi(i= 1,2,m）。已知第i种营养成份

7、在每单位的第 j 种配料中的含量为 aij , j = 1,2, , n，每单位的第 j 种配料的价格为 cj 。现在要求在保证营养条件的前提下，应采用何种配方，使混合饲料的成本最小。,2021/6/7,11,解：设 xj 表示在单位混合饲料中，第 j 种配料的含量（j = 1,2, , n）, 则有如下的数学模型： Min Z = c1x1 + c2x2 + + cnxn,2021/6/7,12,以上两个例子，从数学上来讲,它们的共同特征是:(1) 每个问题都用一组决策变量(x1 , x2 , , xn)表示某一方案 ,这组未知数的值就代表一个具体的方案,通常要求这些未知数取值是非负的。(2

8、) 存在一定的限制条件(称为约束条件)，这些条 件都可以用关于决策变量的一组线性等式或 不等式来表示。 (3) 都有一个目标要求,并且这个目标可表示为这 组决策变量的线性函数(称为目标函数),按研 究问题的不同，要求目标函数实现最大化或 最小化。,2021/6/7,13,满足以上三个条件的数学模型称为线性规划数学模型。其一般形式为(1.1)和(1.2)形式。 在该模型中，方程(1.1)称为目标函数， (1.2)称为约束条件。,2021/6/7,14,线性规划问题的解法,1. 对于简单的线性规划问题(只有两个决策变量或等价于两个决策变量的线性规划问题)，我们通过图解法可以对它进行求解。2. 图解

9、法虽然有直观、简便等优点,但是在变量个数较多（如大于等于3）时，一般就无能为力了。美国数学家丹捷格（G.B.Dantzig）提出了求解线性规划问题的方法：单纯形算法 （一种代数的方法）。,2021/6/7,15,例3. 求解线性规划 min z=x1+2x2+x3-x4 s.t. 2x1+4x2+x3+x4 = 6 2x1 +x4+x5 = 3 x1-x2 +x5 = 1 x1, x2, x3, x4, x5 0解：对原问题进行初等变换，得到,2021/6/7,16,min z=x1+2x2+x3-x4 s.t. x1+3x2+x3 = 4 x1+x2 +x4 = 2 x1-x2 +x5 =

10、1 x1, x2, x3, x4, x5 0 即 min z=2 + x1 s.t. x1+3x2 4 x1+x2 2 x1-x2 1 x1, x2 0 然后用图解法求解。求出x1，x2最优解后，再求出x3, x4, x5 ，就得到了原问题的最优解。,2021/6/7,17,线性规划问题的标准型,这里我们假设 bi 0 , i = 1,2,m, 否则两端同时乘以“-1”。用矩阵向量描述就是：,2021/6/7,18,其中：c = ( c1, c2, , cn )T ，X = ( x1, x2, , xn )T ，b = ( b1, b2, , bm )T , A = ( P1, P2, , P

11、n ) ，Pj = ( a1j, a2j, , amj )T ，0 = ( 0, 0, , 0 )T , ( j = 1, 2, , n ) 。 我们称 A 为约束方程组的系数矩阵( mn阶),一般情况下 m n , m 和n 为正整数,分别表示约束条件的个数和决策变量的个数, C 为价值向量, X 为决策向量, 通常aij , bi , cj为已知常数，这里 i = 1, 2, , m , j = 1, 2, , n。,2021/6/7,19,对偶问题的提出 我们将简单叙述对偶线性规划。这里的对偶是指对同以事物（或问题）从不同的角度观察，有两种不同的表述。例如：“平面中矩形的面积与周长的关系

12、”有下面两种表述 周长一定时，面积最大的矩形式正方形； 面积一定时，周长最小的矩形式正方形。,2021/6/7,20,在前面例1中，我们讨论了工厂生产计划模型及其解法，现从另一个角度来讨论这个问题。 假设该工厂的决策者决定不生产产品I、II，而将其所有资源出租或出售。这时，工厂的决策者就要考虑给每种资源进行定价的问题。 设用 y1、 y2、 y3 分别表示出租单位设备台时的租金和出让单位原材料 A、B 的附加费。,2021/6/7,21,作决策时，需要如下的比较：若一个单位设备台时和四个单位原材料 A可以生产一件产品I，可获利2元，那么生产每件产品I的设备台时和原材料出租和出让的所有收入应不低

13、于生产一件产品I的利润。这就有： y1 + 4y2 2 ； 对于产品II同理有： 2 y2 + 4y3 3； 把工厂所有设备台时和资源都出租和出让，其收入应为：w = 8y1 + 16y2 + 12y3 。,2021/6/7,22,从工厂的决策者来看，当然希望 w 的值越大越好；但从接受者的角度来看，他支付的越少越好。所以工厂决策者只能在满足 所有产品的单位利润条件下，使其总收入尽可能地小，才能实现工厂决策者的意愿。为此需要解如下的线性规划问题：,我们称这个线性规划问题为例1线性规划问题（称之为原问题）的对偶问题。,2021/6/7,23,根据上述例题可见，对于形如如下形式的线性规划问题：,我

14、们可以马上得出它的对偶问题：,从以上的线性规划问题和其对偶问题中，我们可以得出：原问题的约束条件的个数 m 就是对偶问题的变量的个数；原问题的变量的个数 n 就是对偶问题的约束条件的个数；若原问题的目标函数是 Max 型，则对偶问题的目标函数必是 Min 型。它们二者的最优目标函数值相等。,2021/6/7,24,例4 某工厂拟用用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润及托运所受限制如下表所示。问两种货物各托运多少，可使获得利润最大？ 表1-2,2021/6/7,25,解：设x1、x2分别为甲、乙两种货物的托运箱数，则得到整数线性规划： Max Z=20 x1+10 x2 5x1+

15、4x2 24 2x1+5x2 13 x1, x2 0 x1,x2 为整数 解决此整数线性规划的松驰线性规划，得到x1=4.8, x2=0, 目标值为Z=96。（用图象法来说明）但是整数最优解为x1=4, x2=1, 目标值为Z*=90。,2021/6/7,26,2.运输问题,例1：(运输问题）假设有 m 个生产地点,可以供应某种物资(以后称为产地)，用 Ai 表示，i = 1,2,m；有 n 个销售地，用 Bj 表示，j = 1,2, ,n；产地的产量和销售地的销售量分别为 ai 和 bj , i = 1,2,m, j = 1,2, ,n，从 Ai 到 Bj 运输单位物资的运价为 cij ，这

16、些数据可汇总于如下表2-1。,2021/6/7,27,在假设产销平衡的条件下，即要求得总运费最小的调运方案。 表2-1 产销平衡表与单位运价表,2021/6/7,28,解:假设 xij 表示从 Ai 到 Bj 的运量,则所求的数学模型为:,2021/6/7,29,指派问题的数学模型,在生活中经常会遇到这样的问题，如某单位需要指派 n 个人去完成 n 项任务，每个人只做一项工作，同时，每项工作只由一个人完成。由于各人的专长不同，每个人完成各项任务的效率也不同。于是产生了应指派哪一个人去完成哪一项任务，使完成 n 项任务的总效率最高（如所用的时间为最少）。我们把这类问题称之为指派问题或分派问题（A

17、ssignment Problem）。,2021/6/7,30,例2 :有一份中文说明书,需要译成英、日、德、俄四 种文字，分别记作 E、J、G、R 。现有甲、乙、丙、丁四人，他们将中文说明书翻译成不同文字说明书所 需要的时间如表2-2所示。问应指派何人去完成哪一项工作，使所需的总时间最少？,2021/6/7,31,表2-2,2021/6/7,32,类似的有：n 项加工任务，怎样指派到 n 台机床上分别完成的问题；n 条航线，怎样指定 n 艘船去航行的问题，等等。对应每个指派问题, 都有类似表2-1那样的表格，我们称之为效率矩阵或系数矩阵，某元素 cij (i,j = 1,2, n ) 表示指

18、派第 i 个人去完成第j项任务时的效率(或时间、成本等)。解题时需要引入变量 xij ,其取值只能是 1 或 0，并令 ：,2021/6/7,33,当问题是要求极小化时的数学模型是：,2021/6/7,34,指派问题的解矩阵应当是每行或每列只能有一个元素为1、其余均为 0 的 n 阶方阵。如下就是例 2 的一个解矩阵：,指派问题是0-1规划的特例，也是运输问题的特例；即 m = n ，ai = bj = 1。我们利用指派问题的特点可以有更为简便的匈牙利算法。,2021/6/7,35,以上讨论仅限于求极小化目标的指派问题。对于求极大化的问题，只要经如下变换，仍可利用匈牙利算法进行求解。,2021

19、/6/7,36,3. 树和最小支撑树,3.1图的基本概念 定义3.1 图论中的图是由点及点与点之间的线所组成的。我们把点与点之间不带箭头的线称为边，带箭头的线称为弧。 定义3.2 如果一个图是由点和边所构成的，那么，称它为无向图，记作G =(V，E)，V表示图G的点集合，E表示图G的边集合。连接点vi,vj V的边记为vivj或vjvi。,2021/6/7,37,定义3.3如果一个图是由点和弧所构成的，称它为有向图，记作D =(V,A)，其中V 表示有向图D的点集合，A表示有向图D的弧集合。一条方向从vi指向vj的弧，记作(vi,vj)。 如果边vivjE，称vi,vj是边的端点，或者vi,v

20、j是相邻的。如果一个图G中，一条边的两个端点是相同的,那么称为这条边是环。如果两个端点之间有两条以上的边，那么称它们为多重边。 一个无环、无多重边的图标为简单图。 一个无环，有多重边的图标图称为多重图。,2021/6/7,38,端点的度 d(v)：点 v 作为边端点的个数； 奇度点v：d(v)=奇数； 偶度点v：d(v)=偶数； 类似地，可以定义有向图中的出度d+(v) 、入度d-(v)等。 定理 3.1（握手定理）所有顶点次数之和等于所有边数的2倍。 定理 3.2 在任一图中，奇点的个数必为偶数。,2021/6/7,39,3.2 图的连通性 定义3.4（路）：给定一个图G=(V,E)，一个点

21、、边交错的由序列P=(v0 ,e1 ,v1 , e2 , v2 ，e3 , v3 , , vk-1,ek,vk), 如果满足ei=vi-1vi, i=1,2,k,则称P为一条联结v0和 vk，记为P=v0 v1v2v3vk-1vk；称v0 ，vk分别为路的起点和终点,其余为中间点。 特别，当路的起点和终点相同时，称该路为圈或回路。 定义3.5（连通图）：图中任意两点之间均至少有一条路，否则称之为不连通图。,2021/6/7,40,3.3 子图与支撑子图 设有图G1=（V1,E1）和G2=（V2 ,E2） 定义3.6（子图）：如果 V2 V1 , E2 E1，且E2中每条边的两个端点均属于V2，

22、称 G2 是 G1 的子图。 定义3.7（支撑子图）：如果 V2 = V1 , E2 E1 ， 称 G2 是 G1 的支撑子图（或生成子图）。 定义3.8（导出子图）： 如果V2 V1, E2=vi,vjvi,vjV2,称 G2 是 G1 中由V2 导出的导出子图。,2021/6/7,41,3.4 树及其性质 定义3.9：一个无圈的连通图称为树。 树有一些重要性质： 定理3.3 设图G=（V，E）是一个树，其顶点数2，那么图G中至少有两个度为1的顶点。 定理3.4 图G=（V，E）是一个树的充要条件是G不含圈，并且有且仅有n-1条边。 定理3.5 图G=（V，E）是一个树的充要条件是G是连通图

23、，并且有且仅有n-1条边。 定理3.6 图G是一个树的充分必要条件是任意两个顶点之间有且仅有一条路。,2021/6/7,42,从以上定理，不难得出以下结论： （1）从一个树中任意去掉一条边，那么剩下的图不是连通图，亦即，在点集合相同的图中，树是含边数最少的连通图。 （2）在树中不相邻的两个点之间加上一条边，那么恰好得到一个圈。,2021/6/7,43,3.5 最小支撑树模型 定义3.10（支撑树）：设图T=(V,E)是图G=(V,E)的一支撑子图,如果图T=(V,E)是一个树,那么称T是G的一棵支撑树。 定理3.7 一个图G有支撑树T的充要条件是G是连通图。 问题3.1 给定一个图G，如何求图

24、G的一棵支撑树？ 问题3.2 给定一个图G，如何判断图G是连通的？,2021/6/7,44,反圈算法求解支撑树： 设G=(V,E)为一个图,取X0=u1,u1为V中的任意一点,E0=. 若已知有Xk及Ek(k0)，(Xk)为Xk的反圈集合,在(Xk)中选取一条或多条边,使得所选边在V-Xk中具有不同的端点,记所选边的集合为Fk,所选顶点的集合为Yk,取Xk+1=XkYk, Ek+1=EkFk. 当Xk=V时,停止,有支撑树(V,Ek)；在某步，当 ，但 ，表明G是不连通的，没有支撑树。,2021/6/7,45,利用反圈法来求一些优化问题的步骤： 取 (下面已存在 )，按下面方式构造 。在 中，

25、按所需条件选边，使得所选边在 中具有不同端点，记这些边组成集合 ，这些被选端点为 。取 ，重复上述过程或停止。 该算法有三个因素要确定：（1）初值；（2）选边条件；（3）算法停止条件。,2021/6/7,46,定义3.11（赋权图）：如果图G =（V，E），对于G中的每一条边vivj，相应地有一个数wij，那么称这样的图G为赋权图，wij称为边vivj的权。这里所指的权，是具有广义的数量值。根据实际研究问题的不同，可以具有不同的含义。例如长度，费用、流量等等。 赋权图在图论及实际应用方面有着重要的地位，被广泛应用于现代科学管理和工程技术等领域，最小支撑树问题就是赋权图的最优化问题之一。,202

26、1/6/7,47,定义3.12 如果图T =（V，E）是图G 的一个支撑树，那么称E中所有边的权重之和为支撑树T 的权重，记作w(T)。如果图G 的支撑树T* 的权重w(T*)在G的所有支撑树T中的权重达到最小，即w(T*) = min w(T) ，那么称T*是G 的一棵最小支撑树。 在已知的几个城市之间联结电话线网，要求总长度最短和总建设费用最少，这个问题的解决可以归结为最小支撑树问题。城市间交通线的建造等，都可以归结为这一类问题。,2021/6/7,48,常用的方法有破圈法、生长法（避圈法）和反圈法三种方法：1. 破圈法 在图中寻找一个圈。若不存在圈，则已经得到最短树或该图不存在最短树；

27、去掉该圈中权数最大的边； 反复重复 两步，直到最小支撑树或判断图G不是连通图。,2021/6/7,49,2.避圈法 从图中依次寻找权数较小的边，寻找过程中，节点不得重复，即不得构成圈。注意在找较小权数边时不考虑已选过的边和可能造成圈的边。如此反复进行，直到得到最小支撑树或证明图不存在最小支撑树。,2021/6/7,50,3.反圈法 设G=(V,E)为一个图,取X(0)=u1,u1为V中的任意一点,E(0)=. 若已知有X(k)及E(k)(k0)，(X(k)为X(k)的反圈集合,在(X(k)中选取一条权重最小的边,记所选边的集合为F(k),所选顶点的集合为Y(k),取X(k+1)=X(k)Y(k

28、), E(k+1)=E(k)F(k). 当X(k)=V时,停止,有最小支撑树(V,E(k)；在某步，当 ，但 ，表明G是不连通的，没有支撑树，则没有最小支撑树。,2021/6/7,51,4.最短路径问题,一般意义下的最短路问题：设一个赋权有向图D=（V，A），对于每一个弧a=（vi,vj），相应地有一个权wij。vs,vt是D中的两个顶点，P是D中从vs到vt的任意一条路，定义路的权是P中所有弧的权重之和，记作w(P)。 最短路问题就是要在所有从vs到vt的路中，寻找一个权重最小的路P0，亦即w(P0)=minw(P)。P0叫做从vs到vt的最短路。P0的权重w(P0)称为从vs到vt的距离，

29、记作d（vs，vt）。由于D是有向图，显然d（vs，vt）与d（vt，vs）一般不相等。,2021/6/7,52,反圈算法 利用反圈法来求vs到vt的最短路：（1）初值： ，给vs一个标号 ( 从vs到v的距离，从vs到v的最短长度）（2）选边条件：在 中选边e=uv，满足： 达到最小, i.e. 取,2021/6/7,53,(3) 停止条件：当 ，则存在从vs到vt的最短路，其长度为 当 ，但 ，说明从vs到vt没有路，当然亦无最短路。（当 时，说明存在vs到所有点的最短路;当 ，但 ，说明图G是不连通的。）,2021/6/7,54,最短路径问题还有其他算法：1. Dijkstra算法2.

30、Bell-Ford算法3. Floyd-Warshall算法,2021/6/7,55,5.网络最大流问题,定义5.1 设一个赋权有向图D =（V,A）,在V中指定一个发点vs和一个收点vt,其他的点称为中间点。对于D中的每一个弧（vi,vj）A,都有一个权cij称为弧的容量。我们把这样的图D 称为一个网络系统，简称网络，记做D =（V，A;c）。 网络D上的流，是指定义在弧集合A上的一个函数f=f(vi,vj)=fij, fij =f(vi,vj)称为弧(vi,vj)上的流量。,2021/6/7,56,网络系统上流的特点：(1)发点的总流出量和收点的总流入量必相等；(2)每一个中间点的流入量与

31、流出量的代数和等于零；(3)每一个弧上的流量不能超过它的最大通过能力（即容量）。 对于不满足上述条件的网络暂时不考虑。,2021/6/7,57,定义5.2 网络上的一个流 f 叫做可行流，如果 f 满足以下条件 （1）容量条件：对于每一个弧（vi,vj）A,有 0 fij cij. （2）平衡条件： 对于发点vs，有fsj-fjs=v(f) 对于收点vt，有ftj-fjt=-v(f) 对于中间点，有fij-fji=0 其中发点的总流量（或收点的总流量）v(f)称 为这个可行流f的流量。,2021/6/7,58,任意一个网络上的可行流总是存在的。例如零流v(f)=0,就是满足以上条件的可行流。

32、网络系统中最大流问题就是在给定的网络上寻求一个可行流f，其流量v(f)达到最大值。 设流f=fij是网络D上的一个可行流，我们把D中fij=cij的弧称为饱和弧，fij0的弧称为非零流弧，fij=0的弧称为零流弧。,2021/6/7,59,设是网络D中连接发点s和收点vt的一条路。定义路的方向是从vs到vt，于是路上的弧被分为两类：一些弧的方向与路的方向相同，称为前向弧，前向弧的集合记做+。二些弧的方向与路的方向相反，称为后向弧，后向弧的集合记做-。,2021/6/7,60,定义5.3（增广路）: 如果路是连结vs到vt的一条路，满足以下条件： 1在弧（vi,vj）+上，有0fijcij，即+

33、中的每一条弧是非饱和弧。 2在弧（vi,vj）-上，有0fij cij，即-中的每一条弧是非零流弧。,2021/6/7,61,定义5.4 设一个网络D=（V，A；c），如果点集V被剖分为两个非空集合V1和V-V1，发点vsV1,收点vtV-V1,那么将弧集（V1, V-V1）称为是分离vs和vt的截集。 定义5.5 设一个截集（V1, V-V1），将截集（V1, V-V1）中所有弧的容量之和称为截集的截量，记做c(V1, V-V1)，亦即c(V1, V-V1)=cij，这里对所有 (vi,vj)(V1, V-V1)求和。,2021/6/7,62,下面的事实是显然的： 一个网络D中，任何一个可行

34、流f的流量v(f)都小于或等于这个网络中任何一个截集(V1,V-V1)的截量。并且，如果网络上的一个可行流f*和网络中的一个截集（V1*,V-V1*），满足条件v*(f*)=c(V1*,V-V1*),那么f*一定是D上的最大流，而（V1*,V-V1*）一定是D的所有的截集中截量最小的一个（即最小截集）。,2021/6/7,63,定理5.1 网络中的一个可行流f*是最大流的充分必要条件是，不存在关于f*的增广链。 定理5.2 在一个网络D中，最大流的流量等于分离vs和vt的最小截集的截量。,2021/6/7,64,如果存在一条从vs到vt的增广路，这时，取调整量= minmincij-fij|

35、(vi,vj) +, minfij|(vi,vj)- fij +， 当(vi,vj)+ 令fij= fij -， 当(vi,vj)- 其它不变 再去掉所有的标号，对新的可行流f=fij,重新进行标号过程，直到找到网络D的最大流为止。,2021/6/7,65,6.最小费用最大流问题,在实际的网络系统中，当涉及到有关流的问题的时候，我们往往不仅仅考虑的是流量，还经常要考虑费用的问题。比如一个铁路系统的运输网络流，即要考虑网络流的货运量最大，又要考虑总费用最小。最小费用最大流问题就是要解决这一类问题。,2021/6/7,66,定义6.1设一个网络D=（V，A；c），对于每一个弧(vi,vj)A,给定

36、一个单位流量的费用bij0，网络系统的最小费用最大流问题，是指要寻求一个最大流f，并且流的总费用b(f)=bij fij达到最小，这里对所有弧（vi,vj）A求和。,2021/6/7,67,在一个网络D中，当沿可行流f的一条增广路，以调整量=1改进f，得到的新可行流f的流量，有v(f)= v(f)+1，而此时总费用b(f)比b(f)增加了 b(f)-b(f)=bij(fij-fij)- bij(fij-fij) + - = bij-bij + - 将bij-bij称为这条增广链的费用。 + -,2021/6/7,68,如果可行流在流量为v(f)的所有可行流中的费用最小，并且是关于f的所有增广链

37、中的费用最小的增广链。那么沿增广链调整可行流f，得到的新可行流f，也是流量为v(f)的所有可行流中的最小费用流。 依次类推，当f是最大流时，就是所要求的最小费用最大流。 求解最小费用流的算法有迭加算法和Klein圈算法（省略）。,2021/6/7,69,7.中国邮递员问题,7.1 欧拉问题(Euler Problem) 1736年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文，解决了著名的哥尼斯堡七座桥问题。德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，如图7.1所示。,2021/6/7,70,A,B,图7.1,C,D,2021/6/7,71,当地的居

38、民热衷于这样一个问题，一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都没有成功。 为了寻找答案，欧拉1736年将这个问题抽象成图7.2所示图形的一笔画问题,即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。,2021/6/7,72,图7.2,A,C,D,B,2021/6/7,73,定义7.1（欧拉回路）设有一个连通图G=（V，E），并且 是G中存在一条回路, 称为图G的欧拉回路, 如果 经过(包含)图G中的

39、每条边，并且仅包含一次。此时，也称图G是欧拉图。 问题7.1 ：给定一个连通图G=（V，E），如何判断G是一个欧拉图？ 定理7.1(Euler定理) 设G=（V，E）是连通图，则G是欧拉图iff图G中不含有次为奇数的顶点。,2021/6/7,74,算法 用 表示在第k步得到的一条路（其中有的顶点可能相同），记 （初始时，取）。按下面方式进行第k+1步：在 中选一条与 相关联的边 , 使得 不是割边，除非此时 ，令 ，取，重复上述过程，直到无边可选为止。,2021/6/7,75,定义7.2（一笔划问题）：给定一个图G，能否找到一条路 ，使得该图中的每条边恰好在 中出现一次如果图G满足上述要求，称

40、G是M图问题7.2 ：如何判定一个图G是M图？定理7.2 设G是一个连通图，则G是M图iff图G中奇次的顶点的个数2,2021/6/7,76,定义7.3（有向欧拉回路）设有一个强连通有向图D=（V，A）,并且 是D中存在一条有向回路, 称 为图D的有向欧拉回路, 如果 经过(包含)图D中的每条弧,并且仅包含一次。此时，也称图D是有向欧拉图。 问题7.3：给定一个强连通有向图D=（V，A），如何判断D是一个有向欧拉图？ 定理7.3(Euler定理) 设D=（V，A）是强连通有向图,则D是有向欧拉图iff图D中每个顶点的出度等于入度，d-(u)=d+(u),uV。,2021/6/7,77,7.中国

41、邮递员问题(Chinese Postman Problem) 定义7.4（中国邮递员问题）设G=(V,E;w)是赋权图， ，能否在图G中寻找一条回路 ，使得G的每一条边在 中至少出现一次，并且使得 达到最小，称该问题是中国邮递员问题（CPP）。 中国邮递员问题也叙述为图论问题：设G=(V,E;w)是赋权图，寻找 ，使得GE1是欧拉图，其目标是使得 达到最小。,2021/6/7,78,称上述达到最小的E1为CPP问题的最优集。 当图G是欧拉图时，则利用 算法能够找到一条欧拉回路（这也是最优的回路）。 定理7.4（管梅谷，1960）设G=（V，E;w)是一个赋权连通图，则E1是最优集iff对于每个

42、简单圈C，均有,2021/6/7,79,当图G不是欧拉图，利用Edmonds算法求解:1 在G中找到的所有2k个奇数次顶点，2 在G中寻找这个顶点之间的最短路及路径，构造一个图 ，这里 定义为G中 与 之间的最短路长度。3 在图H中寻找最小的完美匹配M。,2021/6/7,80,4 利用M中的每个元素 对应于图G中的最短路 ，把相应的所有最短路 叠加到图G上，即把最短路上的边使用两次，得到一个图G*（此时G*就是一个欧拉图）。5 再利用 算法在欧拉图G*上，所得到的欧拉回路就是中国邮递员问题的最回路，即最优解。 定理7.5 Edmonds算法能够得到CPP的最优解。,2021/6/7,81,定

43、义7.5（有向中国邮递员问题）设D=(V,A; w)是赋权有向图， ，能否在有向图D中寻找一条有向回路 ，使得D的每一条弧在 中至少出现一次，并且使得 达到最小，称该问题是有向中国邮递员问题(DCPP)。 有向中国邮递员问题也叙述为图论问题：设D=(V,A;w)是有向赋权图，寻找 ，使得DA1是有向欧拉图，其目标是使得 达到最小。,2021/6/7,82,注意到有向连通图不一定存在有向邮路。,我们总是假设所讨论的赋权有向图是强连通的。如果讨论的图是有向欧拉图，则该图的有向欧拉回路就是最优有向邮路。,例图：,图7.3 不存在有向邮路的例子,2021/6/7,83,当连通赋权有向图不是有向欧拉图，

44、算法：1 设 为连通赋权有向图。 ，计 算 。若所有 ，令 ，转第2步，否则转第3步。 2 求出 的有向欧拉回路 ，结束， 是 的最优有向路。3 构造集合 和 求出 中从 到 最短路。4 构造集合 和,2021/6/7,84,5 构造赋权网络N=（V*，A*；b* ，c* ）,这里V*=s,t ， 对 和 ， 表示在D中 从x到y的最短路长度，其余费用为0，容量 全为1。6 求出N中最小费用最大流f。7 8 找出M中每条边(x,y)对应的N中的从x到y的 最短路。把这些最短路上的每条弧都作为添加弧加到D中去，得到有向欧拉图 ，转第2步。,2021/6/7,85,定理7.6 Edmonds-Johnson算法能够得到有向中国邮递员问题(DCPP)的最优解。 也可以把构造网络的步骤由LP表示：,部分资料从网络收集整理而来，供大家参考，感谢您的关注！,