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

第一章第一章 运筹学中的几个数学问运筹学中的几个数学问题及模型题及模型 本章主要介绍运筹学中的几个数学问题及模型，即本章主要介绍运筹学中的几个数学问题及模型，即线性规划问题、运输问题、图与网络优化技术等。学习线性规划问题、运输问题、图与网络优化技术等。学习的重点是基本概念。的重点是基本概念。1.线性规划问题及其数学模型问题线性规划问题及其数学模型问题2.运输问题运输问题3.树和最小支撑树问题树和最小支撑树问题4.最短路径问题最短路径问题5.网络最大流问题网络最大流问题6.最小费用最大流问题最小费用最大流问题7.中国邮递员问题中国邮递员问题8.NP-完备性完备性.数学预备知识：矩阵的基本概念及初等运算数学预备知识：矩阵的基本概念及初等运算参考文献参考文献1.1.运筹学教材编写组编，运筹学，清华大运筹学教材编写组编，运筹学，清华大学出版社，学出版社，20052005年年6 6月第月第3 3版版2.2.田丰、马仲番编著，图与网络流理论，科学出版田丰、马仲番编著，图与网络流理论，科学出版社，社，19871987年年3.3.刘振宏、刘振宏、蔡茂城蔡茂城(译译)，组合最优化：算法和，组合最优化：算法和复杂性，清华大学出版社复杂性，清华大学出版社,1988,1988 年第年第1 1版版4.4.C.H.Papadimitriou and K.Steiglitz,Combinatorial Optimization:Algorithms and Complexity,Printice-Hall,1982.运筹学的性质和特点运筹学的性质和特点 运筹学是一门应用科学，至今还没有统一且确运筹学是一门应用科学，至今还没有统一且确切的定义。在此提出以下几个定义来说明运筹学的切的定义。在此提出以下几个定义来说明运筹学的性质和特点：性质和特点：定义定义1:为决策机构在对其控制下的业务活动进为决策机构在对其控制下的业务活动进行决策时行决策时,提供以数量化为依据的科学方法提供以数量化为依据的科学方法.特点特点1:该定义强调的是科学方法该定义强调的是科学方法,以定量化为基以定量化为基础础,利用数学工具利用数学工具.但任何决策都包含定量和定性两个但任何决策都包含定量和定性两个方面方面,而定性方面又不能简单地用数学表示而定性方面又不能简单地用数学表示,如政治、如政治、社会等因素，只有综合多种因素的决策才是全面的。社会等因素，只有综合多种因素的决策才是全面的。运筹学工作者的职责是为决策者提供可以量化方面运筹学工作者的职责是为决策者提供可以量化方面的分析，并指出那些是定性因素。的分析，并指出那些是定性因素。.定义定义2：运筹学是一门应用科学，它广泛应用现：运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据。专门问题，为决策者选择最优决策提供定量依据。特点特点2：该定义表明运筹学具有多学科交叉的特：该定义表明运筹学具有多学科交叉的特点，如综合应用经济学、心理学、物理学和化学中点，如综合应用经济学、心理学、物理学和化学中的一些方法。的一些方法。特点特点3：由系统的观点研究功能关系。：由系统的观点研究功能关系。综上所述，运筹学的定义可以提炼为：综上所述，运筹学的定义可以提炼为：定义定义3：运筹学就是利用计划的方法和多学科专：运筹学就是利用计划的方法和多学科专家组成的队伍，把复杂的功能关系表示成数学模型家组成的队伍，把复杂的功能关系表示成数学模型，其目的是通过定量分析为决策和揭露新问题提供，其目的是通过定量分析为决策和揭露新问题提供数量依据。数量依据。.运筹学与计算机运筹学与计算机 计算机是运筹学发展的基本因素，对任何实际问计算机是运筹学发展的基本因素，对任何实际问题，没有现代计算机用来产生最终结果，大多数运筹题，没有现代计算机用来产生最终结果，大多数运筹学技术是完全不能实现的。许多大规模运筹技术的应学技术是完全不能实现的。许多大规模运筹技术的应用只需计算机几分钟的时间，而用人工则需要很长时用只需计算机几分钟的时间，而用人工则需要很长时间。更为重要的是计算机能快速利用某些类型的管理间。更为重要的是计算机能快速利用某些类型的管理信息，而没有这些信息，许多运筹设计是没有意义。信息，而没有这些信息，许多运筹设计是没有意义。计算机是运筹学不可分割的部分和不可缺少的工计算机是运筹学不可分割的部分和不可缺少的工具，而且计算机方法和运筹学方法是并行发展的。预具，而且计算机方法和运筹学方法是并行发展的。预计今后运筹学和计算机方法的分界线将会消失，并将计今后运筹学和计算机方法的分界线将会消失，并将组成更通用、更广泛的管理科学的形式。组成更通用、更广泛的管理科学的形式。.运筹学的工作步骤运筹学的工作步骤1.提出和形成问题：要弄清问题的目标，可能的约束，提出和形成问题：要弄清问题的目标，可能的约束，问题的可控变量以及有关参数。问题的可控变量以及有关参数。2.建立模型：把问题中可控变量、参数和目标与约束之建立模型：把问题中可控变量、参数和目标与约束之间的关系用一定的模型表示出来。间的关系用一定的模型表示出来。3.求解：用数学方法将模型求解。解可以是最优解、次求解：用数学方法将模型求解。解可以是最优解、次优解、满意解。复杂模型的求解需用计算机优解、满意解。复杂模型的求解需用计算机,解的精度解的精度要求由决策者提出。要求由决策者提出。4.解的检验：先检验求解步骤和程序有无错误，然后检解的检验：先检验求解步骤和程序有无错误，然后检查解是否反映现实问题。查解是否反映现实问题。5.解的控制：通过控制解的变化过程决定对解是否要作解的控制：通过控制解的变化过程决定对解是否要作一定的修改。一定的修改。6.解的实施：将解用到实际中去，必须考虑到实际的问解的实施：将解用到实际中去，必须考虑到实际的问题，如向实际部门讲清楚解的用法，在实施中可能产题，如向实际部门讲清楚解的用法，在实施中可能产生的问题等。生的问题等。以上过程应反复进行。以上过程应反复进行。.1.线性规划问题及其数学模型问题 例例1：某工厂在计划期内安排生产：某工厂在计划期内安排生产、两两种产品，已知生产单位产品所需的设备台种产品，已知生产单位产品所需的设备台时、时、A、B两种原材料的消耗及两种产品每两种原材料的消耗及两种产品每件可获利润见如下表件可获利润见如下表1-1所示：问如何安所示：问如何安排计划使该工厂获利最多？排计划使该工厂获利最多？.表表1111产品产品I产品产品II 资源总量资源总量 设设 备备 1台时台时 2台时台时 8 台时台时 原材料原材料A 4公斤公斤 0公斤公斤 16公斤公斤 原材料原材料B 0公斤公斤 4公斤公斤 12公斤公斤 利利 润润 2元元/件件 3元元/件件.解：假设解：假设 x1、x2分别表示在计划期内生产产品分别表示在计划期内生产产品I、II的数量，则该计划问题可用如下数学模型表的数量，则该计划问题可用如下数学模型表示为：示为：目标函数目标函数 Max Z=2x1+3x2 约束条件约束条件其最优解为其最优解为x1=4,x2=2,最优值为最优值为z=14。.例例2:（营养问题）某养鸡场所用的混合饲料是由营养问题）某养鸡场所用的混合饲料是由 n 种配料组成。要求这种混合饲料必须含有种配料组成。要求这种混合饲料必须含有 m 种不同的营养成份，而且要求每单位混合饲料种不同的营养成份，而且要求每单位混合饲料中第中第i种营养成份的含量不能低于种营养成份的含量不能低于bi(i=1,2,m）。已知第。已知第i种营养成份在每单位的第种营养成份在每单位的第 j 种配料中种配料中的含量为的含量为 aij,j=1,2,n，每单位的第，每单位的第 j 种配种配料的价格为料的价格为 cj。现在要求在保证营养条件的前。现在要求在保证营养条件的前提下，应采用何种配方，使混合饲料的成本最提下，应采用何种配方，使混合饲料的成本最小。小。.解：设解：设 xj 表示在单位混合饲料中，第表示在单位混合饲料中，第 j 种配料种配料的含量（的含量（j=1,2,n）,则有如下的数学模型：则有如下的数学模型：Min Z=c1x1+c2x2+cnxn .以上两个例子，从数学上来讲以上两个例子，从数学上来讲,它们的共同它们的共同特征是特征是:(1)每个问题都用一组决策变量每个问题都用一组决策变量(x1,x2,xn)表表示某一方案示某一方案,这组未知数的值就代表一个具体这组未知数的值就代表一个具体的方案的方案,通常要求这些未知数取值是非负的。通常要求这些未知数取值是非负的。(2)存在一定的限制条件存在一定的限制条件(称为约束条件称为约束条件)，这些条，这些条 件都可以用关于决策变量的一组线性等式或件都可以用关于决策变量的一组线性等式或 不等式来表示。不等式来表示。(3)都有一个目标要求都有一个目标要求,并且这个目标可表示为这并且这个目标可表示为这 组决策变量的线性函数组决策变量的线性函数(称为目标函数称为目标函数),按研按研 究问题的不同，要求目标函数实现最大化或究问题的不同，要求目标函数实现最大化或 最小化。最小化。.满足以上三个条件的数学模型称为线性规划满足以上三个条件的数学模型称为线性规划数学模型。其一般形式为数学模型。其一般形式为(1.1)和和(1.2)形式。形式。在该模型中，方程在该模型中，方程(1.1)称为目标函数，称为目标函数，(1.2)称为约束条件。称为约束条件。.线性规划问题的解法线性规划问题的解法1.对于简单的线性规划问题对于简单的线性规划问题(只有两个决策变量只有两个决策变量或等价于两个决策变量的线性规划问题或等价于两个决策变量的线性规划问题)，我，我们通过图解法可以对它进行求解。们通过图解法可以对它进行求解。2.图解法虽然有直观、简便等优点图解法虽然有直观、简便等优点,但是在变量但是在变量个数较多（如大于等于个数较多（如大于等于3）时，一般就无能为）时，一般就无能为力了。美国数学家丹捷格（力了。美国数学家丹捷格（G.B.Dantzig）提）提出了求解线性规划问题的方法：单纯形算法出了求解线性规划问题的方法：单纯形算法 （一种代数的方法）。（一种代数的方法）。.例例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解：对原问题进行初等变换，得到解：对原问题进行初等变换，得到.min z=x1+2x2+x3-x4 s.t.x1+3x2+x3 =4 x1+x2 +x4 =2 x1-x2 +x5 =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，就得到了原问题的最优解。，就得到了原问题的最优解。.线性规划问题的标准型线性规划问题的标准型 这里我们假设这里我们假设 bi 0,i=1,2,m,否则两端否则两端同时乘以同时乘以“-1”。用矩阵向量描述就是：。用矩阵向量描述就是：.其中：其中：c=(c1,c2,cn)T，X=(x1,x2,xn)T，b=(b1,b2,bm)T,A=(P1,P2,Pn)，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。.对偶问题的提出对偶问题的提出 我们将简单叙述对偶线性规划。这里的对偶我们将简单叙述对偶线性规划。这里的对偶是指对同以事物（或问题）从不同的角度观察，是指对同以事物（或问题）从不同的角度观察，有两种不同的表述。有两种不同的表述。例如：例如：“平面中矩形的面积与周长的关系平面中矩形的面积与周长的关系”有下面有下面两种表述两种表述 周长一定时，面积最大的矩形式正方形；周长一定时，面积最大的矩形式正方形；面积一定时，周长最小的矩形式正方形。面积一定时，周长最小的矩形式正方形。.在前面例在前面例1中，我们讨论了工厂生产计划模中，我们讨论了工厂生产计划模型及其解法，现从另一个角度来讨论这个问题型及其解法，现从另一个角度来讨论这个问题。假设该工厂的决策者决定不生产产品假设该工厂的决策者决定不生产产品I、II，而将其所有资源出租或出售。这时，工厂的决而将其所有资源出租或出售。这时，工厂的决策者就要考虑给每种资源进行定价的问题。策者就要考虑给每种资源进行定价的问题。设用设用 y1、y2、y3 分别表示出租单位设备台分别表示出租单位设备台时的租金和出让单位原材料时的租金和出让单位原材料 A、B 的附加费。的附加费。.作决策时，需要如下的比较：若一个单位作决策时，需要如下的比较：若一个单位设备台时和四个单位原材料设备台时和四个单位原材料 A可以生产一件产可以生产一件产品品I，可获利，可获利2元，那么生产每件产品元，那么生产每件产品I的设备台的设备台时和原材料出租和出让的所有收入应不低于生时和原材料出租和出让的所有收入应不低于生产一件产品产一件产品I的利润。这就有：的利润。这就有：y1+4y2 2；对于产品对于产品II同理有：同理有：2 y2+4y3 3；把工厂所有设备台时和资源都出租和出让把工厂所有设备台时和资源都出租和出让，其收入应为：，其收入应为：w=8y1+16y2+12y3。.从工厂的决策者来看，当然希望从工厂的决策者来看，当然希望 w 的值越大的值越大越好；但从接受者的角度来看，他支付的越少越越好；但从接受者的角度来看，他支付的越少越好。所以工厂决策者只能在满足好。所以工厂决策者只能在满足 所有产品的单所有产品的单位利润条件下，使其总收入尽可能地小，才能实位利润条件下，使其总收入尽可能地小，才能实现工厂决策者的意愿。为此需要解如下的线性规现工厂决策者的意愿。为此需要解如下的线性规划问题：划问题：我们称这个线性规划问题为例我们称这个线性规划问题为例1线性规划问线性规划问题（称之为原问题）的对偶问题。题（称之为原问题）的对偶问题。.根据上述例题可见，对于形如如下形式的线性规根据上述例题可见，对于形如如下形式的线性规划问题：划问题：我们可以马上得出我们可以马上得出它的对偶问题：它的对偶问题：从以上的线性规划问题和其对偶问题中，我们从以上的线性规划问题和其对偶问题中，我们可以得出：原问题的约束条件的个数可以得出：原问题的约束条件的个数 m 就是对偶问就是对偶问题的变量的个数；原问题的变量的个数题的变量的个数；原问题的变量的个数 n 就是对偶就是对偶问题的约束条件的个数；若原问题的目标函数是问题的约束条件的个数；若原问题的目标函数是 Max 型，则对偶问题的目标函数必是型，则对偶问题的目标函数必是 Min 型。它们型。它们二者的最优目标函数值相等。二者的最优目标函数值相等。.例例4 4 某工厂拟用用集装箱托运甲乙两种货物，每某工厂拟用用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润及托运所受限制如箱的体积、重量、可获利润及托运所受限制如下表所示。问两种货物各托运多少，可使获得下表所示。问两种货物各托运多少，可使获得利润最大？利润最大？表表1-21-2货物货物体积体积（米（米3/箱）箱）重量（百公斤重量（百公斤/箱）箱）利润利润（百元（百元/箱）箱）甲甲5220乙乙4510托运限制托运限制24米米313百公斤百公斤.解：设解：设x1、x2分别为甲、乙两种货物的托运箱分别为甲、乙两种货物的托运箱数，则得到整数线性规划：数，则得到整数线性规划：Max Z=20 x1+10 x2 5x1+4x2 24 2x1+5x2 13 x1,x2 0 x1,x2 为整数为整数 解决此整数线性规划的松驰线性规划，解决此整数线性规划的松驰线性规划，得到得到x1=4.8,x2=0,目标值为目标值为Z=96。（用图象。（用图象法来说明）但是整数最优解为法来说明）但是整数最优解为x1=4,x2=1,目目标值为标值为Z*=90。.2 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，这些数据可汇，这些数据可汇总于如总于如下表下表2-1。.在假设产销平衡的条件下，即在假设产销平衡的条件下，即要求得总运费最小的调运方案。要求得总运费最小的调运方案。表表2-1 2-1 产销平衡表与单位运价表产销平衡表与单位运价表 销地销地产地产地 B1 B2 Bn 产量产量 A1 c11 c12 c1n a1 A2 c21 c22 c2n a2 .Am cm1 cm2 cmn am 销量销量 b1 b2 bn.解解:假设假设 xij 表示从表示从 Ai 到到 Bj 的运量的运量,则所求的数学则所求的数学模型为模型为:.指派问题的数学模型指派问题的数学模型 在生活中经常会遇到这样的问题，如某单在生活中经常会遇到这样的问题，如某单位需要指派位需要指派 n 个人去完成个人去完成 n 项任务，每个人只项任务，每个人只做一项工作，同时，每项工作只由一个人完成做一项工作，同时，每项工作只由一个人完成。由于各人的专长不同，每个人完成各项任务。由于各人的专长不同，每个人完成各项任务的效率也不同。于是产生了应指派哪一个人去的效率也不同。于是产生了应指派哪一个人去完成哪一项任务，使完成完成哪一项任务，使完成 n 项任务的总效率最项任务的总效率最高（如所用的时间为最少）。我们把这类问题高（如所用的时间为最少）。我们把这类问题称之为指派问题或分派问题（称之为指派问题或分派问题（Assignment Problem）。）。.例例2:有一份中文说明书有一份中文说明书,需要译成英、日、德、需要译成英、日、德、俄四俄四 种文字，分别记作种文字，分别记作 E、J、G、R。现有。现有甲、乙、丙、丁四人，他们将中文说明书翻译甲、乙、丙、丁四人，他们将中文说明书翻译成不同文字说明书所成不同文字说明书所 需要的时间如表需要的时间如表2-2所示。所示。问应指派何人去完成哪一项工作，使所需的总问应指派何人去完成哪一项工作，使所需的总时间最少？时间最少？.表表2-2 任务任务人员人员EJGR甲甲215134乙乙1041415丙丙9141613丁丁78119.类似的有：类似的有：n 项加工任务，怎样指派到项加工任务，怎样指派到 n 台机台机床上分别完成的问题；床上分别完成的问题；n 条航线，怎样指定条航线，怎样指定 n 艘船艘船去航行的问题，等等。对应每个指派问题去航行的问题，等等。对应每个指派问题,都有类都有类似表似表2-1那样的表格，我们称之为效率矩阵或系数矩那样的表格，我们称之为效率矩阵或系数矩阵，某元素阵，某元素 cij(i,j=1,2,n)表示指派第表示指派第 i 个人去个人去完成第完成第j项任务时的效率项任务时的效率(或时间、成本等或时间、成本等)。解题时。解题时需要引入变量需要引入变量 xij,其取值只能是其取值只能是 1 或或 0，并令，并令：.当问题是要求极小化时的数学模型是：当问题是要求极小化时的数学模型是：.指派问题的解矩阵应当是每行或每列只能有指派问题的解矩阵应当是每行或每列只能有一个元素为一个元素为1、其余均为、其余均为 0 的的 n 阶方阵。如下就阶方阵。如下就是例是例 2 的一个解矩阵：的一个解矩阵：指派问题是指派问题是0-1规划的特例，也是运输问题规划的特例，也是运输问题的特例；即的特例；即 m=n，ai=bj=1。我们利用指派问。我们利用指派问题的特点可以有更为简便的题的特点可以有更为简便的匈牙利算法匈牙利算法。.以上讨论仅限于求极小化目标的指派问题。以上讨论仅限于求极小化目标的指派问题。对于求极大化的问题，只要经如下变换，仍可利对于求极大化的问题，只要经如下变换，仍可利用匈牙利算法进行求解。用匈牙利算法进行求解。.3.3.树和最小支撑树树和最小支撑树3.1图的基本概念图的基本概念 定义定义3.1 图论中的图是由点及点与点之间的图论中的图是由点及点与点之间的线所组成的。我们把点与点之间不带箭头的线线所组成的。我们把点与点之间不带箭头的线称为边，带箭头的线称为弧。称为边，带箭头的线称为弧。定义定义3.2 如果一个图是由点和边所构成的，如果一个图是由点和边所构成的，那么，称它为无向图，记作那么，称它为无向图，记作G=(V，E)，V表示表示图图G的点集合，的点集合，E表示图表示图G的边集合。连接点的边集合。连接点vi,vj V的边记为的边记为vivj或或vjvi。.定义定义3.3如果一个图是由点和弧所构成的，如果一个图是由点和弧所构成的，称它为有向图，记作称它为有向图，记作D=(V,A)，其中，其中V 表示有向表示有向图图D的点集合，的点集合，A表示有向图表示有向图D的弧集合。一条方的弧集合。一条方向从向从vi指向指向vj的弧，记作的弧，记作(vi,vj)。如果边如果边vivjE，称称vi,vj是边的端点，或者是边的端点，或者vi,vj是相邻的。如果一个图是相邻的。如果一个图G中，一条边的两个端点中，一条边的两个端点是相同的是相同的,那么称为这条边是环。如果两个端点那么称为这条边是环。如果两个端点之间有两条以上的边，那么称它们为多重边。之间有两条以上的边，那么称它们为多重边。一个无环、无多重边的图标为简单图。一个无环、无多重边的图标为简单图。一个无环，有多重边的图标图称为多重图。一个无环，有多重边的图标图称为多重图。.端点的度端点的度 d(v)：点：点 v 作为边端点的个数；作为边端点的个数；奇度点奇度点v：d(v)=奇数；奇数；偶度点偶度点v：d(v)=偶数；偶数；类似地，可以定义有向图中的出度类似地，可以定义有向图中的出度d+(v)、入度入度d-(v)等。等。定理定理 3.1（握手定理）所有顶点次数之和（握手定理）所有顶点次数之和等于所有边数的等于所有边数的2倍。倍。定理定理 3.2 在任一图中，奇点的个数必为偶在任一图中，奇点的个数必为偶数。数。.3.2 图的连通性图的连通性 定义定义3.4（路）：给定一个图（路）：给定一个图G=(V,E)，一个，一个点、边交错的由序列点、边交错的由序列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（连通图连通图）：）：图中任意两点之间均图中任意两点之间均至少有一条路，否则称之为不连通图。至少有一条路，否则称之为不连通图。.3.3 子图与支撑子图子图与支撑子图 设有图设有图G1=（V1,E1）和）和G2=（V2,E2）定义定义3.6（子图）：如果（子图）：如果 V2 V1,E2 E1，且且E2中每条边的两个端点均属于中每条边的两个端点均属于V2，称，称 G2 是是 G1 的子图。的子图。定义定义3.7（支撑子图）：如果（支撑子图）：如果 V2=V1,E2 E1，称称 G2 是是 G1 的支撑子图（或生成子图）。的支撑子图（或生成子图）。定义定义3.8（导出子图）：（导出子图）：如果如果V2 V1,E2=vi,vj vi,vj V2,称称 G2 是是 G1 中由中由V2 导出导出的的导出子图。导出子图。.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是连通图，并且有且仅有是连通图，并且有且仅有n-1条边。条边。定理定理3.6 图图G是一个树的充分必要条件是任意是一个树的充分必要条件是任意两个顶点之间有且仅有一条路。两个顶点之间有且仅有一条路。.从以上定理，不难得出以下结论：从以上定理，不难得出以下结论：（1）从一个树中任意去掉一条边，那么剩下）从一个树中任意去掉一条边，那么剩下的图不是连通图，亦即，在点集合相同的图中的图不是连通图，亦即，在点集合相同的图中，树是含边数最少的连通图。，树是含边数最少的连通图。（2）在树中不相邻的两个点之间加上一条边）在树中不相邻的两个点之间加上一条边，那么恰好得到一个圈。，那么恰好得到一个圈。.3.5 最小支撑树模型最小支撑树模型 定义定义3.10（支撑树）：设图（支撑树）：设图T=(V,E)是图是图G=(V,E)的一支撑子图的一支撑子图,如果图如果图T=(V,E)是一个树是一个树,那么称那么称T是是G的一棵支撑树。的一棵支撑树。定理定理3.7 一个图一个图G有支撑树有支撑树T的充要条件是的充要条件是G是连通图。是连通图。问题问题3.1 给定一个图给定一个图G，如何求图，如何求图G的一棵的一棵支撑树？支撑树？问题问题3.2 给定一个图给定一个图G，如何判断图，如何判断图G是连是连通的？通的？.反圈算法求解支撑树：反圈算法求解支撑树：设设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是不连通是不连通的，没有支撑树。的，没有支撑树。.利用反圈法来求一些优化问题的步骤：利用反圈法来求一些优化问题的步骤：取取 (下面已存在下面已存在 )，按下面方式构造，按下面方式构造 。在。在 中，按所中，按所需条件选边，使得所选边在需条件选边，使得所选边在 中具有不同端中具有不同端点，记这些边组成集合点，记这些边组成集合 ，这些被选端点为，这些被选端点为 。取。取 ，重，重复上述过程或停止。复上述过程或停止。该算法有三个因素要确定：（该算法有三个因素要确定：（1）初值；（）初值；（2）选边条件；（选边条件；（3）算法停止条件。）算法停止条件。.定义定义3.11（赋权图）：如果图（赋权图）：如果图G=（V，E），对于，对于G中的每一条边中的每一条边vivj，相应地有一个数，相应地有一个数wij，那么称这样的图那么称这样的图G为赋权图，为赋权图，wij称为边称为边vivj的权。的权。这里所指的权，是具有广义的数量值。根据实际这里所指的权，是具有广义的数量值。根据实际研究问题的不同，可以具有不同的含义。例如长研究问题的不同，可以具有不同的含义。例如长度，费用、流量等等。度，费用、流量等等。赋权图在图论及实际应用方面有着重要的地赋权图在图论及实际应用方面有着重要的地位，被广泛应用于现代科学管理和工程技术等领位，被广泛应用于现代科学管理和工程技术等领域，最小支撑树问题就是赋权图的最优化问题之域，最小支撑树问题就是赋权图的最优化问题之一。一。.定义定义3.12 如果图如果图T=（V，E）是图是图G 的一的一个支撑树，那么称个支撑树，那么称E中所有边的权重之和为支中所有边的权重之和为支撑树撑树T 的权重，记作的权重，记作w(T)。如果图。如果图G 的支撑树的支撑树T*的权重的权重w(T*)在在G的所有支撑树的所有支撑树T中的权重达到最中的权重达到最小，即小，即w(T*)=min w(T)，那么称，那么称T*是是G 的一棵的一棵最小支撑树。最小支撑树。在已知的几个城市之间联结电话线网，要在已知的几个城市之间联结电话线网，要求总长度最短和总建设费用最少，这个问题的求总长度最短和总建设费用最少，这个问题的解决可以归结为最小支撑树问题。城市间交通解决可以归结为最小支撑树问题。城市间交通线的建造等，都可以归结为这一类问题。线的建造等，都可以归结为这一类问题。.常用的方法有破圈法、生长法（避常用的方法有破圈法、生长法（避圈法）和反圈法三种方法：圈法）和反圈法三种方法：1.破圈法破圈法 在图中寻找一个圈。若不存在圈，在图中寻找一个圈。若不存在圈，则已经得到最短树或该图不存在最短树；则已经得到最短树或该图不存在最短树；去掉该圈中权数最大的边；去掉该圈中权数最大的边；反复重复反复重复 两步，直到最小支撑树两步，直到最小支撑树或判断图或判断图G不是连通图。不是连通图。.2.避圈法避圈法 从图中依次寻找权数较小的边，寻找过程从图中依次寻找权数较小的边，寻找过程中，节点不得重复，即不得构成圈。注意在找中，节点不得重复，即不得构成圈。注意在找较小权数边时不考虑已选过的边和可能造成圈较小权数边时不考虑已选过的边和可能造成圈的边。如此反复进行，直到得到最小支撑树或的边。如此反复进行，直到得到最小支撑树或证明图不存在最小支撑树。证明图不存在最小支撑树。.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),E(k+1)=E(k)F(k).当当X(k)=V时时,停止停止,有最小支撑树有最小支撑树(V,E(k)；在在某步，当某步，当 ，但，但 ，表明，表明G是不连通是不连通的，没有支撑树，则没有的，没有支撑树，则没有最小支撑树最小支撑树。.4.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的距离，记作的距离，记作d（vs，vt）。由于）。由于D是有向是有向图，显然图，显然d（vs，vt）与）与d（vt，vs）一般不相等。）一般不相等。.反圈算法反圈算法 利用反圈法来求利用反圈法来求vs到到vt的最短路：的最短路：（1）初值：）初值：，给，给vs一个标号一个标号 (从从vs到到v的距离，从的距离，从vs到到v的最短长度）的最短长度）（2）选边条件：在）选边条件：在 中选边中选边e=uv，满足：满足：达到最小达到最小,i.e.取取.(3)停止条件：当停止条件：当 ，则存在从，则存在从vs到到vt的的最短路，其长度为最短路，其长度为 当当 ，但，但 ，说明从，说明从vs到到vt没有路，当然亦无最短路。没有路，当然亦无最短路。（当（当 时，说明存在时，说明存在vs到所有点的最短到所有点的最短路路;当当 ，但，但 ，说明图，说明图G是不连通的。）是不连通的。）.最短路径问题还有其他算法：最短路径问题还有其他算法：1.Dijkstra算法算法2.Bell-Ford算法算法3.Floyd-Warshall算法算法.5.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)上的流量。上的流量。.网络系统上流的特点：网络系统上流的特点：(1)发点的总流出量和收点的总流入量必相等；发点的总流出量和收点的总流入量必相等；(2)每每一一个个中中间间点点的的流流入入量量与与流流出出量量的的代代数数和和等于零；等于零；(3)每每一一个个弧弧上上的的流流量量不不能能超超过过它它的的最最大大通通过过能力（即容量）。能力（即容量）。对于不满足上述条件的网络暂时不考虑。对于不满足上述条件的网络暂时不考虑。.定义定义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的流量。的流量。.任意一个网络上的可行流总是存在的。例任意一个网络上的可行流总是存在的。例如零流如零流v(f)=0,就是满足以上条件的可行流。就是满足以上条件的可行流。网络系统中最大流问题就是在给定的网络网络系统中最大流问题就是在给定的网络上寻求一个可行流上寻求一个可行流f，其流量其流量v(f)达到最大值。达到最大值。设流设流f=fij是网络是网络D上的一个可行流，我们上的一个可行流，我们把把D中中fij=cij的弧称为饱和弧，的弧称为饱和弧，fij0的弧称为非零流弧，的弧称为非零流弧，fij=0的弧称为零的弧称为零流弧。流弧。.设设是网络是网络D中连接发点中连接发点s和收点和收点vt的一的一条路。定义路的方向是从条路。定义路的方向是从vs到到vt，于是路，于是路上上的弧被分为两类：一些弧的方向与路的方向的弧被分为两类：一些弧的方向与路的方向相同，称为前向弧，前向弧的集合记做相同，称为前向弧，前向弧的集合记做+。二些弧的方向与路的方向相反，称为后向弧二些弧的方向与路的方向相反，称为后向弧，后向弧的集合记做，后向弧的集合记做-。.定义定义5.3（增广路）（增广路）:如果路如果路是连结是连结vs到到vt的一条路，满足以下条件：的一条路，满足以下条件：1在弧（在弧（vi,vj）+上，有上，有0fij cij，即，即+中的每