数学建模离散优化模型与算法设计

1、整理课件整理课件数学建模离散优化模型及算法设计之前之前, ,我们介绍了与计算复杂性有关的一些基本概念我们介绍了与计算复杂性有关的一些基本概念. .人们发现人们发现, ,在离散在离散问题中存在着两个互不相交的类：问题中存在着两个互不相交的类：P P类与类与NPNP完全类（若完全类（若P PNPNP）。前者具）。前者具有求解的有效算法而后者不可能有这种算法。从这一点上讲，有求解的有效算法而后者不可能有这种算法。从这一点上讲，P P问题可问题可以看成是一类具有良好性质而又较容易求解的问题，而以看成是一类具有良好性质而又较容易求解的问题，而NPNP完全问题则是完全问题则是固有地难解的。固有地难解的。在

2、中看到，有着广泛应用背景的线性规划问题是一个在中看到，有着广泛应用背景的线性规划问题是一个P P问题。这样，作为问题。这样，作为线性规划子问题的运输问题及作为运输问题子问题的指派问题自然更是线性规划子问题的运输问题及作为运输问题子问题的指派问题自然更是P P问题。虽然从平均的角度讲，人们似乎更常遇到问题。虽然从平均的角度讲，人们似乎更常遇到NPNP完全问题，但完全问题，但P P仍不失仍不失为一个十分重要的问题类。一方面，很多为一个十分重要的问题类。一方面，很多P P问题象线性规划一样有着极广问题象线性规划一样有着极广泛的应用前景，且它们本身又是十分有趣的；另一方面，它们也是研究泛的应用前景，且

3、它们本身又是十分有趣的；另一方面，它们也是研究一些更为复杂、难解的问题时经常被采用的研究工具。在本章中，将再一些更为复杂、难解的问题时经常被采用的研究工具。在本章中，将再介绍一些经常遇到的介绍一些经常遇到的P P问题并给出求解它们的有效算法。问题并给出求解它们的有效算法。 一、拟阵问题及贪婪算法一、拟阵问题及贪婪算法在在P类中又存在着一个被称为拟阵的具有更为良好性质的问题类，其中的任类中又存在着一个被称为拟阵的具有更为良好性质的问题类，其中的任一问题均可用一种被称为贪婪法的方法来求解，而这一性质并不是所有的一问题均可用一种被称为贪婪法的方法来求解，而这一性质并不是所有的P问题都具有的。问题都具

4、有的。 例例 9.1 （最小生成树问题（最小生成树问题MST）给定一连通图给定一连通图G=（V，E），）， ，有一表示边长的权有一表示边长的权C（e）（表示顶点间的距离或费用），求此图的具有最）（表示顶点间的距离或费用），求此图的具有最小总权的生成树。小总权的生成树。e此问题的标准形式为给定一完全图此问题的标准形式为给定一完全图G G，其每边赋有一权数，求此完全图的，其每边赋有一权数，求此完全图的最小生成树。所谓树是指连通而无圈的图，单独的一个点也可看成一颗最小生成树。所谓树是指连通而无圈的图，单独的一个点也可看成一颗树。树用树。树用( (U U，T T) )表示，表示，U U为树的顶点，为树

5、的顶点，T T为树的边集。不相交的树的集合为树的边集。不相交的树的集合被称为森林。一个连通图的生成树是指图中具有最多边数的一棵树。容被称为森林。一个连通图的生成树是指图中具有最多边数的一棵树。容易证明，对于一个连通图易证明，对于一个连通图G G，G G 的任一生成树必有的任一生成树必有V V-1-1条边。条边。求解最小生成树的算法主要依据下面的定理：求解最小生成树的算法主要依据下面的定理：定理定理 9.1 设设（V1，T1），），（Vk ,Tk）为连通图为连通图G中的森林，中的森林，V1 U V2U Vk=V。 k,若仅有一个顶点在若仅有一个顶点在Vi中的具有最小权的边为（中的具有最小权的边为

6、（ ,u），），则必有一棵则必有一棵G的最小生成树包含边（的最小生成树包含边（ ,u）。）。, 1i根据定根据定1可以作了如下算法：任选一点可以作了如下算法：任选一点 ，令，令 若若V1=V，停；否则，找出仅有一个顶点在，停；否则，找出仅有一个顶点在V1中的边里具有最小权的边中的边里具有最小权的边（ ,u），设，将），设，将u加入加入V1（ ,u）加入）加入T。重复上述步骤，直到。重复上述步骤，直到V1=V。 1 11:,:.VT 证明：设：设G的一棵最小生成树（的一棵最小生成树（V，T）不含（）不含（ ,u）。将（）。将（ ,u）加入）加入T，由于（由于（V，T）是生成树，）是生成树，T U

7、（ ,u）中含有过（）中含有过（ ,u）的唯一的圈。不）的唯一的圈。不妨设妨设 ，则，则 ，此圈中的点不全由，此圈中的点不全由Vi中的点组成中的点组成,因此必存在因此必存在圈中的另一边圈中的另一边 。删去边。删去边 得到一新的生成树（得到一新的生成树（V，T1），），T1= ，须其总权不超过（，须其总权不超过（V，T）的权）的权,即（即（V，T）是包含边（是包含边（ ,u）的最小生成树。）的最小生成树。iViV,iiuuu,uu例例9.2 求图中图求图中图G的最小生成树。的最小生成树。解：不妨从顶点开始寻找。不妨从顶点开始寻找。 标号标号1，先加入，先加入 （因为边权（因为边权最小），最小），

8、 标号标号2。再加入。再加入 标号标号3。，每次加入一条一顶点已标，每次加入一条一顶点已标号加一顶点未标号而又具有最小权的边，直到所有顶点均标号为止。找号加一顶点未标号而又具有最小权的边，直到所有顶点均标号为止。找到的最小生成树已用又线标在图到的最小生成树已用又线标在图9.2中。中。 111,V212244 容易看出算法的计算量为容易看出算法的计算量为O (V)2 ，所以此算法是有效算法，若，所以此算法是有效算法，若G具有具有O（ ）条边，其中）条边，其中n= V ，计算量的界还是不能改进的，因为每条，计算量的界还是不能改进的，因为每条边至少应被检查一次。边至少应被检查一次。2nC由例可以看出

9、，算法执行的每一步均加入一条可以加入的（即不生成圈由例可以看出，算法执行的每一步均加入一条可以加入的（即不生成圈的）具有最小权的边，而不去考虑它对以后选取的影响，这种算法被称的）具有最小权的边，而不去考虑它对以后选取的影响，这种算法被称为贪婪算法。为贪婪算法。例例9.3 (入树问题入树问题) 给出一个有向图给出一个有向图G=（V，A），对），对A中的每一条孤中的每一条孤e，给，给出一个权出一个权C（e），求），求A的一个具有最大权（或最小权）的子集的一个具有最大权（或最小权）的子集B，要求，要求B中任意两条孤都没有公共的终点。中任意两条孤都没有公共的终点。考察下面的入树问题实例：考察下面的入树

10、问题实例：例例 给出有向图给出有向图G=（V，A）（图）（图），孤上标出的数字为该边的，孤上标出的数字为该边的权，求此图具有最大权的入树。权，求此图具有最大权的入树。解：由于入树不能包含具有公共终点的孤，故对每一顶点解：由于入树不能包含具有公共终点的孤，故对每一顶点 只能选取只能选取一条入孤。为使选出的弧具有最大权，只需要对每一顶点选取权最大的一条入孤。为使选出的弧具有最大权，只需要对每一顶点选取权最大的入孤，可用计算量为入孤，可用计算量为O O（V VE E）的贪婪法求解，具有最大权的入树）的贪婪法求解，具有最大权的入树为为 。 i 1221244553, 类似地，出树问题也可以用贪婪法求解

11、。类似地，出树问题也可以用贪婪法求解。 例例9.5 (矩阵拟阵问题矩阵拟阵问题)给出一个矩阵给出一个矩阵Amxn，记其，记其n个列向量为个列向量为e1,，en。设对每一列向量设对每一列向量en已指定一权已指定一权C（en）求）求 的一个线性无关的一个线性无关的子集，它具有最大的权和。的子集，它具有最大的权和。 1,iin易见，这一问题也可以用贪婪法求解。集合易见，这一问题也可以用贪婪法求解。集合 的线性无关的的线性无关的子集被称为独立子集，利用贪婪法必可求得具有最大权的独立子集，可用子集被称为独立子集，利用贪婪法必可求得具有最大权的独立子集，可用线性代数知识加以证明线性代数知识加以证明（见习题

12、（见习题1）。 1,iin例例 求矩阵求矩阵A的列向量具有最大权和的独立子集的列向量具有最大权和的独立子集7*45762101543100012731214531011AC(C(e ei i) ) 8 4 7 5 2 6 48 4 7 5 2 6 4解：采用贪婪法，先取权最大的列采用贪婪法，先取权最大的列e1，同时对，同时对A作高斯消去，逐次加入作高斯消去，逐次加入线性无关的向量：线性无关的向量：A的列向量中具有最大权的独立子集为的列向量中具有最大权的独立子集为 。1354取e6取e4取e3? ? ? ? ? ? ? ?4511020543100033421104531011123111054

13、3100033421104531011A4/904/194/90204/514/34/100033421104531011定义定义9.1 (拟阵拟阵) 设设E是一个有限集，是一个有限集，为为E的部分子集构成的封闭系统（即的部分子集构成的封闭系统（即若若 ，则必有，则必有 ）。若）。若M=（E，）上的离散优化问题的每一）上的离散优化问题的每一实例均可用贪婪算法求出最优解，则称实例均可用贪婪算法求出最优解，则称M为一拟阵。（注：为一拟阵。（注：被称为独立系被称为独立系统）。统）。,AAA现以矩阵拟阵为例，对定义作一说明。现以矩阵拟阵为例，对定义作一说明。对矩阵拟阵的每一实例，对矩阵拟阵的每一实例，

14、E=e1,en为矩阵列向量的集合，为矩阵列向量的集合，为为E的线性无关的线性无关子集构成的系统，称为独立系统，其元素被称为独立子集。由于子集构成的系统，称为独立系统，其元素被称为独立子集。由于E的任一线的任一线性无关子集的子集也是性无关子集的子集也是E的线性无关子集，故独立系统的线性无关子集，故独立系统是封闭的。又由于是封闭的。又由于这一离散优化问题的任一实例都可用贪婪法求解，故构成一拟阵，被称为这一离散优化问题的任一实例都可用贪婪法求解，故构成一拟阵，被称为矩阵拟阵。例被称为图拟阵，例被称为划分拟阵。矩阵拟阵。例被称为图拟阵，例被称为划分拟阵。 拟阵问题（或称拟阵结构）拟阵问题（或称拟阵结构

15、）有一个明显而又本质的特性，其任一极大独立有一个明显而又本质的特性，其任一极大独立子集中包含着相同个数的元素，从而可以引入基的概念。例如，矩阵列向子集中包含着相同个数的元素，从而可以引入基的概念。例如，矩阵列向量的所有线性无关极大组均具有相同的向量个数，这就导出了基量的所有线性无关极大组均具有相同的向量个数，这就导出了基即矩即矩阵列秩的概念。对于图拟阵，每一极大独立集均为一生成树，其边数均为阵列秩的概念。对于图拟阵，每一极大独立集均为一生成树，其边数均为|V|-1。对于划分拟阵，孤集被划分成个。对于划分拟阵，孤集被划分成个|V|个子集，每一子集由指向同一顶个子集，每一子集由指向同一顶点的孤组成

16、。显然，任一极大独立集应在每一子集中取一条孤，故其基数点的孤组成。显然，任一极大独立集应在每一子集中取一条孤，故其基数为顶点个数。为顶点个数。 我们不加证明地引入下面的定理，虽然其证明并不十分困难。我们不加证明地引入下面的定理，虽然其证明并不十分困难。 定理定理 E为一有限集合，为为一有限集合，为E的部分子集构成的封闭独立系统。以下的部分子集构成的封闭独立系统。以下两个条件均为两个条件均为M=(E, y)构成拟阵（即其上的优化问题可用贪婪法求解）构成拟阵（即其上的优化问题可用贪婪法求解）的充分必要条件：的充分必要条件：（条件（条件2） 若若I、I均为均为A的两个极大独立集，则的两个极大独立集，

17、则|I|=|I|。AE （条件（条件1）若若I、I |I| M|，G中至少含一条路，其中中至少含一条路，其中M中的边多于中的边多于M中的边，不难看出，这条路是中的边，不难看出，这条路是G的的关于关于M的增广路。的增广路。 现在可以看出，找最大匹配的关键在于找增广路。读者不难用顶点标号现在可以看出，找最大匹配的关键在于找增广路。读者不难用顶点标号的办法（由未盖点出发），作出一个求解两分图匹配的增广路算法。此的办法（由未盖点出发），作出一个求解两分图匹配的增广路算法。此算法稍加改动，还可以用于非两分图的情况。算法稍加改动，还可以用于非两分图的情况。三、网络流问题三、网络流问题网络流问题是又一类具有

18、广泛应用前景的网络流问题是又一类具有广泛应用前景的P问题，本节将介绍一些有关问题，本节将介绍一些有关网络流问题的基本理论与算法。网络流问题的基本理论与算法。1、最大流问题（、最大流问题（MFP）边赋值的有向图称为网络。给定一个网络，其边赋值表示该边的容量。最边赋值的有向图称为网络。给定一个网络，其边赋值表示该边的容量。最大流问题要求在不超过边容量的前提下求出网络中两个指定顶点之间的最大流问题要求在不超过边容量的前提下求出网络中两个指定顶点之间的最大流。例如：当网络是通讯网时，我们可能会去求出网络中两个指定点间大流。例如：当网络是通讯网时，我们可能会去求出网络中两个指定点间的最大通话量；当网络是

19、城市的街道时，我们又可能会去求两地间的最大的最大通话量；当网络是城市的街道时，我们又可能会去求两地间的最大交通流，即单位时间内允许通过的车辆数等等。交通流，即单位时间内允许通过的车辆数等等。建模：建模：给定一有向图给定一有向图G=（V，A），），A的每一条孤（边）（的每一条孤（边）（i,j）上已赋一）上已赋一表示边容量的非负整数表示边容量的非负整数C（i,j）。并已指定）。并已指定V中的两个顶点中的两个顶点 s、t，分别称，分别称它们为发点和收点。它们为发点和收点。设网络中已存在一个流（不一定是最大流），记孤（设网络中已存在一个流（不一定是最大流），记孤（i,j）上的流量为）上的流量为 （i,

20、j），记），记s发出的总流量（即发出的总流量（即t收到的总流量）为收到的总流量）为 ，根据平衡条件，可，根据平衡条件，可得如下的约束条件，得如下的约束条件， ，有，有i 其中是其中是 指指A中以顶点中以顶点i为起点的孤集，为起点的孤集， 是指是指A中以中以 i为终点的孤集为终点的孤集,(.1)式表示式表示s发出流为发出流为 ，t收入的流为收入的流为 ，其余各点只起中转作用，其余各点只起中转作用，既不增加也不消耗流量。根据边容量限止，还应有既不增加也不消耗流量。根据边容量限止，还应有 iAiA,i jC i ji jA而我们的愿望是使总流量尽可能地大。而我们的愿望是使总流量尽可能地大。即在（即在

21、（9.1）、）、(9.2)式约束下式约束下使达到最大，易见，这是一个线性规划问题的子问题，故使达到最大，易见，这是一个线性规划问题的子问题，故 类。类。PtivtsisivjijiAijiAiji若若若.0),(),(),(),(对于一个较为复杂的网络，要想直接找出最大流是不太可能的。为了简化对于一个较为复杂的网络，要想直接找出最大流是不太可能的。为了简化问题，我们先引入一些符号。问题，我们先引入一些符号。记记、为为的两个不相交的子集，的两个不相交的子集，s ，用（，）表示发，用（，）表示发点在，收点在的边集，点在，收点在的边集，记记，并定义如下的切割概念：，并定义如下的切割概念：,P tQ,

22、i P j Qi P j QP Qi j C P QC i j定义定义9.5 （切割）（切割） 设设是是的顶点集合的顶点集合的一个真子集，的一个真子集， 为为关于关于的补集。若的补集。若、 满足满足 且且 则称则称和和 为的一个切割。为的一个切割。PPSPtPP根据切割的定义可以看出，当和根据切割的定义可以看出，当和 为一切割时，如果去掉连接为一切割时，如果去掉连接和的和的边集（边集（， ），就切断了由通往），就切断了由通往t的所有通路。所以，对网络的任一切的所有通路。所以，对网络的任一切割（割（， ），），（， ）必为最大流的一个上界，）必为最大流的一个上界，而而 。PPPP,P PP P例

23、例9.9 网络如图网络如图9.6所示，边（弧）上的两数字分别表示边容量及实际流所示，边（弧）上的两数字分别表示边容量及实际流量。取，则，显然量。取，则，显然、 是网络的是网络的一个切割。对于这一切割容易算出一个切割。对于这一切割容易算出而网络的流量而网络的流量 。P,6,9P PC P P为了尽可能地增大网络上的流量，按如下方法作出一个和为了尽可能地增大网络上的流量，按如下方法作出一个和具有相同顶具有相同顶点并具有相同发点和收点的增广网络点并具有相同发点和收点的增广网络 （ ） （简记（简记）。）。包含两包含两类边，对中每一条边（类边，对中每一条边（i，j） ： A（1）若）若 ，作正向边（，

24、作正向边（i，j）, 规定容量规定容量 ，即剩余容量。，即剩余容量。,i jC j i,C j iC j ij i（2）若）若 ，作反向边（，作反向边（j,i），）， 规定容量规定容量 事实上是边（事实上是边（j,i）上最多可减少的容量。）上最多可减少的容量。,0i j,Cj ij iCj i第一类边称为正规边，第二类边则称为增广边。例如由图中的流可以作第一类边称为正规边，第二类边则称为增广边。例如由图中的流可以作出其相应的增广网络图，其中实箭线为正规定，虚箭线为增广边，边上出其相应的增广网络图，其中实箭线为正规定，虚箭线为增广边，边上的数字为边容量。的数字为边容量。如果增广网络上存在着由如果

25、增广网络上存在着由st的通路的通路p（称为原网络的一条增广路），（称为原网络的一条增广路），记记 ，则只要在，则只要在P中的一切正规边上增加流量中的一切正规边上增加流量a，而在对应，而在对应增广边（增广边（j, i），），G的边（的边（i, j）上减少流量）上减少流量a，就得到，就得到G的一个由的一个由st的增的增大了流量大了流量a的更大的流。例如，从图的更大的流。例如，从图9.7上可以找出增广路上可以找出增广路，a=2。于是，图。于是，图9.6中的流可改进增大为图中的流可改进增大为图9.8(a)中中的流，总流量为的流，总流量为7。由于其增广网络图。由于其增广网络图9.8(b)中不再存在增广路

26、，无法再中不再存在增广路，无法再继续增大。容易看出，若取继续增大。容易看出，若取s出发（在增广网络上）可到达的点的集合出发（在增广网络上）可到达的点的集合为为P，则，则P=, ， =,，C（P， ）=7，而流量已达到，而流量已达到7，故此流已是最大流。故此流已是最大流。 ( , )min( , )i jPaC i jPP（1）( , )( , ), ( , )( ,)i jC i ji jP P（2） ( , )0, ( , )( , )i ji jP P故故 ，已不能再增大，（注：这是线性规划的补松驰定理）。已不能再增大，（注：这是线性规划的补松驰定理）。( ,)( ,)P PC P P综上

27、所述，有下面的有关网络流问题的定理。综上所述，有下面的有关网络流问题的定理。定理定理9.59.5 （Ford和和Fulkerson最大流最小切割定理）最大流最小切割定理） 任一由任一由s到到t的流，的流，其流量不大于任一切割的容量其流量不大于任一切割的容量C（P， ），而最大流的流量则等于最小），而最大流的流量则等于最小切割的容量。进而切割的容量。进而 为最大流且（为最大流且（P， ）为最小切割当且仅当：）为最小切割当且仅当：（1） 有有（2） 有有 。PP( , )( ,)i jP P( , )( , )i jC i j( , )( ,)i jP P( , )0i j增广路可以通过对顶点标号

28、的方法来寻找。由于边容量均为整数，而每次增广路可以通过对顶点标号的方法来寻找。由于边容量均为整数，而每次经改进，流量至少增加一，故算法总能很快求得最大流。经改进，流量至少增加一，故算法总能很快求得最大流。定理定理 网络网络G上的流是最大流的充要条件为其增广网络上不存在由上的流是最大流的充要条件为其增广网络上不存在由s到到t 的通路。的通路。证明：证明：若增广网络上存在由若增广网络上存在由s到到t的通路的通路P，则对，则对P上的正规边（上的正规边（i, j）增加流）增加流量量a，对，对P的增广边（的增广边（j, i）对应）对应G的边（的边（i, j）减少流量）减少流量a，即可得到一个更，即可得到

29、一个更大的可行流。若增广网络上不存在由大的可行流。若增广网络上不存在由s到到t的路，记增广图上的路，记增广图上s可达到的点组可达到的点组成的集合为成的集合为P，则对切割（，则对切割（P, ）必有：）必有：P2、最小费用最大流问题、最小费用最大流问题对于一个给定的网络，由发点对于一个给定的网络，由发点s到收点到收点t常常存在着多个具有相同流量的最常常存在着多个具有相同流量的最大流。如图所示，图中的（大流。如图所示，图中的（a）、（）、（b）、（）、（c）均是流量为）均是流量为7的最大流，边的最大流，边上的两个数字依次为容量和边上的实际流量。有时候，当流流经一条边时上的两个数字依次为容量和边上的实

30、际流量。有时候，当流流经一条边时需支付一定的费用，我们不仅希望找出一个最大流，而且希望找出的最大需支付一定的费用，我们不仅希望找出一个最大流，而且希望找出的最大流在具有相同流量的流中具有最小的总费用，这时问题可描述为：对有向流在具有相同流量的流中具有最小的总费用，这时问题可描述为：对有向图图G=（V，A）的每条边（弧）（）的每条边（弧）（i, j）给定一个边容量）给定一个边容量C（i, j）及一个单位）及一个单位流量费用流量费用l(i, j)。希望求出由。希望求出由s到到t的最大流，使得总费用最少，即求最大流的最大流，使得总费用最少，即求最大流*，使，使*( , )()min ( , ) (

31、, )i jALl i ji j最大流例如，在交通网络中，例如，在交通网络中，l(i, j)可以是可以是i, j之间的距离或运费。自然，在运送之间的距离或运费。自然，在运送相同数量货物时，我们希望总距离或总运费最小。现在，我们将以最大相同数量货物时，我们希望总距离或总运费最小。现在，我们将以最大流问题的增广路算法为基础，导出求解最小费用最大流问题的算法。流问题的增广路算法为基础，导出求解最小费用最大流问题的算法。对于网络上的一个现行流对于网络上的一个现行流 ，作出其增广网络，作出其增广网络G( )，对，对G中的正规边中的正规边赋值赋值l(i, j)，对，对G中的增广边中的增广边(i, j)则赋

32、值则赋值l(i, j)。 定义定义 增广网络增广网络G上由上由s到到t的流量为零但边流量不全为零的流称为一个循环流。的流量为零但边流量不全为零的流称为一个循环流。最小费用最大流问题可以变换成为一个线性规划问题，根据线性规划理最小费用最大流问题可以变换成为一个线性规划问题，根据线性规划理论可以证明下面的定理：论可以证明下面的定理： 定理定理9.69.6 网络中的流网络中的流 是最小费用的，当且仅当其增广网络是最小费用的，当且仅当其增广网络G中不存在中不存在负费用的循环流（证明略）。负费用的循环流（证明略）。例例 图（图（a）给出了有向图）给出了有向图G上的一个可行流，其中弧上的三个数字分别为上的

33、一个可行流，其中弧上的三个数字分别为容量、单位流费用及实际流量。图（容量、单位流费用及实际流量。图（b）为相应的增广网络，其中边（弧）为相应的增广网络，其中边（弧）上的两个数字分别为容量及单位流费用。求此网络的一个更小费用流。上的两个数字分别为容量及单位流费用。求此网络的一个更小费用流。从图（从图（b）中可以找出一个负费用循环流）中可以找出一个负费用循环流s21s（其余边流量为（其余边流量为0），），每单位流量的总费用为每单位流量的总费用为5。调整此循环流上的流量，得到图（。调整此循环流上的流量，得到图（a）中的）中的流。原先的流总费用为流。原先的流总费用为17，调整后的总费用为，调整后的总费

34、用为12，减少值为负费用循环，减少值为负费用循环流的总费用。流的总费用。图（图（a）中流的增广网络（）中流的增广网络（b）中已不存在负费用循环流，它是一个最小费用）中已不存在负费用循环流，它是一个最小费用的流。的流。定理定理 设设1是网络上流量为是网络上流量为的最小费用流，的最小费用流，2是其增广网络上由是其增广网络上由s到到t的最小的最小费用单位流增广路，则费用单位流增广路，则1+2是此网络流量为是此网络流量为+1的最小费用流。的最小费用流。证明：证明：设设1+2不是流量为不是流量为+1的最小费用流，由定理的最小费用流，由定理6，在，在 1+ 2的增广网的增广网络中必存在一负圈络中必存在一负

35、圈C。记构造。记构造2的增广路为的增广路为P。由于。由于 1是最小费用流，是最小费用流， 1的增广网络中不存在负圈，故的增广网络中不存在负圈，故C中必有一边（中必有一边（i, j），其反向边（），其反向边（j, i）含）含在在P中（因为如若不然，中（因为如若不然，C不含不含P中任意边，则中任意边，则C将含在将含在1的增广网络中，与的增广网络中，与1为最小费用流的假设矛盾，见图为最小费用流的假设矛盾，见图9.12），但这又说明），但这又说明P（C（i, j）是）是S到到t的更小费用单位流增广路，与的更小费用单位流增广路，与P是最小费用单位流增广路的假设矛盾。是最小费用单位流增广路的假设矛盾。根据

36、定理及定理，求最大流的算法只需稍作变动即根据定理及定理，求最大流的算法只需稍作变动即可用来求解最小费用最大流。算法可以用归纳方式可用来求解最小费用最大流。算法可以用归纳方式给出，当给出，当=0时，可取时，可取=0，这显然是，这显然是=0的最小费的最小费用流。在以后逐次增大流量时，若增广网络中存在用流。在以后逐次增大流量时，若增广网络中存在着多于一条增广路时，每次均选用其中单位流费用着多于一条增广路时，每次均选用其中单位流费用最小的一条。这样，每次得到的均为相同流量的流最小的一条。这样，每次得到的均为相同流量的流中费用最小的，而最后得到的即为最小费用最大流。中费用最小的，而最后得到的即为最小费用

37、最大流。网络流问题的算法在解决实际问题时常常被用到。它可用来求解运输问网络流问题的算法在解决实际问题时常常被用到。它可用来求解运输问题、指派问题及赋权两分图匹配问题（等价于指派问题），也可用来寻题、指派问题及赋权两分图匹配问题（等价于指派问题），也可用来寻找网络的瓶颈找网络的瓶颈即最小切割（即最小切割（P， ）确定的边。作为一个网络流问题）确定的边。作为一个网络流问题的应用实例，我们来求解例的应用实例，我们来求解例9.7中的婚姻姻问题：增加发点中的婚姻姻问题：增加发点s和收点和收点t，将，将原图的边改为有向边，所有边的容量为原图的边改为有向边，所有边的容量为1。找出最大财礼数。找出最大财礼数2

38、8，以此数，以此数减每边原有的财礼费，并用此差为各边的费用，得一最小费用最大流问减每边原有的财礼费，并用此差为各边的费用，得一最小费用最大流问题（未注数字的边费用均为零），其网络图见图题（未注数字的边费用均为零），其网络图见图9.13。此问题在使用三。此问题在使用三次增广路后可求得最佳结果。次增广路后可求得最佳结果。 P四、最短路径问题四、最短路径问题最短路径问题是又一个经常遇到的最短路径问题是又一个经常遇到的P问题，它在工艺流程的安排、管道或问题，它在工艺流程的安排、管道或网络的铺设、设备更新等实际生产中常被用到，是网络规划的基本问题之网络的铺设、设备更新等实际生产中常被用到，是网络规划的基

39、本问题之一。顾名思义，最短路径求的是以下问题：给定一个网络，如何求出网络一。顾名思义，最短路径求的是以下问题：给定一个网络，如何求出网络中指定两点间总距离（或总费用）最小的路径。中指定两点间总距离（或总费用）最小的路径。例例 给定图中的网络，边上的数字为两顶点间的距离（或费用），求由给定图中的网络，边上的数字为两顶点间的距离（或费用），求由A到到E的最短路径。的最短路径。求解最短路径问题的求解最短路径问题的Dijkstra算法体现了动态规划算法的基本思想。若点算法体现了动态规划算法的基本思想。若点P在在A到到E的最短路上，则的最短路上，则P到到E的最短路径必整个地包含在的最短路径必整个地包含在

40、A到到E的最短路的最短路径上。因为，若不然，将由径上。因为，若不然，将由P到到E的最短路径导出的最短路径导出A到到E的更短路径，从而的更短路径，从而导出矛盾。算法既可以通过对顶点逐次标号来实现，也可以通过矩阵运导出矛盾。算法既可以通过对顶点逐次标号来实现，也可以通过矩阵运算进行。在使用标号法时，既可以从起点开始标，也可以从终点开始标。算进行。在使用标号法时，既可以从起点开始标，也可以从终点开始标。（两者目的略有不同）对例中的网络，如从起点（两者目的略有不同）对例中的网络，如从起点A开始标导，先在开始标导，先在A点标点标上上0。再找出离。再找出离A最近的点最近的点B3，标上，标上A到到B3的最短

41、矩离的最短矩离1并记录下并记录下A点（表点（表明由明由A而来）。一般，在标新顶点时，先找出离已标号顶点最近的顶点。而来）。一般，在标新顶点时，先找出离已标号顶点最近的顶点。比较各已标号顶点（与拟标号顶点有边相连）的标号与它到拟标号顶点比较各已标号顶点（与拟标号顶点有边相连）的标号与它到拟标号顶点距离之和，找出各种中最小者作为新顶点的标号，并记录下其前的已标距离之和，找出各种中最小者作为新顶点的标号，并记录下其前的已标号顶点。直到拟到达的终点已标号为止。例如，图指出，号顶点。直到拟到达的终点已标号为止。例如，图指出，A到到E的最短路的最短路径为径为AB2C1D1E，最短距离为，最短距离为19。

42、容易看出，算法是多项式时间的。在标每一顶点时，最多作了容易看出，算法是多项式时间的。在标每一顶点时，最多作了| V |次运算。次运算。算法进行中，事实上在构造一棵由已标号顶点及它们与其前行点间的边算法进行中，事实上在构造一棵由已标号顶点及它们与其前行点间的边组成的树。每一顶点均不可能重复标号，故总计算量的一个上界为组成的树。每一顶点均不可能重复标号，故总计算量的一个上界为O（|V|2）。）。按一般习惯，动态规划算法常按逆顺序进行。图给出了按向前标号的结果，按一般习惯，动态规划算法常按逆顺序进行。图给出了按向前标号的结果，最短路径已用双线划出。最短路径已用双线划出。 从图中可看出从图中可看出A到

43、各点的距离及最短路径，而从图中则可看出由各点到到各点的距离及最短路径，而从图中则可看出由各点到E点的距离及最短路径，这是两者的区别。点的距离及最短路径，这是两者的区别。 读者不难给出一般问题的计算步骤，也不难推广得到能求出任意两点间最读者不难给出一般问题的计算步骤，也不难推广得到能求出任意两点间最短路径的算法。短路径的算法。作为最短路径问题的一个应用实例，我们来研究下面的设备更新问题：作为最短路径问题的一个应用实例，我们来研究下面的设备更新问题：例例 某单位使用一种设备。该设备在某单位使用一种设备。该设备在5年内的预期价格见表，使用不同年年内的预期价格见表，使用不同年数的设备的年维修费用见表数

44、的设备的年维修费用见表9.2 。现准备制订一个五年内的设备更新计划，。现准备制订一个五年内的设备更新计划，使五年内支付的设备购置费用及总维修费用最少。使五年内支付的设备购置费用及总维修费用最少。这显然是一个十分有意义的实际问题，即使作为个人，也会经常遇到更这显然是一个十分有意义的实际问题，即使作为个人，也会经常遇到更换交通工具、家用电器等设备更新问题的实例。当然，作为一般情况，换交通工具、家用电器等设备更新问题的实例。当然，作为一般情况，还可能要考虑残值，如购买了新车，旧车可以折价处理，回收资金与已还可能要考虑残值，如购买了新车，旧车可以折价处理，回收资金与已使用年数有关。使用年数有关。解：解

45、：作有向图图，图中点作有向图图，图中点i表示第表示第i年初（或第年初（或第i1）年末），弧（）年末），弧（i, j）上的数字表示第上的数字表示第i年初购买设备到第年初购买设备到第j年初更换，在该段时间内的总费用。年初更换，在该段时间内的总费用。例如，弧（例如，弧（，）上的数）上的数68表示第一年初购买设备到表示第一年初购买设备到5年后的第六年年后的第六年初更换，需支付购设备费初更换，需支付购设备费10万元及各年维修费万元及各年维修费 58 万元，共计万元，共计68万元。万元。问题化为求由顶点问题化为求由顶点到顶点到顶点的最短路。的最短路。容易看出，作出容易看出，作出n年设备更新问题的有向图将问

46、题化为最短路径问题大约年设备更新问题的有向图将问题化为最短路径问题大约需要需要O(n2)计算量，其后要求求解的最短路径问题的计算量也是计算量，其后要求求解的最短路径问题的计算量也是O(n2)，故，故设备更新问题可在设备更新问题可在O(n2)时间内求解。时间内求解。表表表表第i年12345价格（万年）1010111213已使用年数01234（万年）48111520五、欧拉圈与最短邮路问题五、欧拉圈与最短邮路问题欧拉圈问题起源于著名的七桥问题。给定一个无向图欧拉圈问题起源于著名的七桥问题。给定一个无向图G=（V，E），问能），问能否由一个顶点出发，经且仅经过每条边一次并返回原出发顶点。如果能够，否

47、由一个顶点出发，经且仅经过每条边一次并返回原出发顶点。如果能够，则每一个这样的圈被称为图则每一个这样的圈被称为图G的欧拉圈，而图的欧拉圈，而图G则被称为是一个欧拉图。则被称为是一个欧拉图。显然，图显然，图G为欧拉图的充要条件是它可以被一笔画出且首尾相连（当首尾为欧拉图的充要条件是它可以被一笔画出且首尾相连（当首尾不能相连时则被称为欧拉路）。由此，立即可得出下面的定理：不能相连时则被称为欧拉路）。由此，立即可得出下面的定理：定理定理 G为为 欧拉图的充要条件是：欧拉图的充要条件是：G是连通的且是连通的且G的每一个顶点都与偶数的每一个顶点都与偶数条件相关联。条件相关联。把关联偶数条边的顶点称为偶顶

48、点，把关联奇数条边的顶点称为奇顶点，把关联偶数条边的顶点称为偶顶点，把关联奇数条边的顶点称为奇顶点，则容易看出奇顶点的个数必为偶数个（因为每一笔画都产生一个起点与则容易看出奇顶点的个数必为偶数个（因为每一笔画都产生一个起点与一个终点），又易得出一个终点），又易得出定理定理 G为欧拉路的充要条件为：为欧拉路的充要条件为：G是连通的且奇顶点的个数为是连通的且奇顶点的个数为2。综合定理和定理可知，综合定理和定理可知，G可一笔画出的充要条件为可一笔画出的充要条件为G是连通的且奇顶点的是连通的且奇顶点的个数为个数为0或或2，当奇顶点个数为零时，尚可设法使起点和终点相重。下面的，当奇顶点个数为零时，尚可设

49、法使起点和终点相重。下面的图（图（a）为欧拉圈，而图（）为欧拉圈，而图（b）则为欧拉路，后者虽可一笔画出，但必须以）则为欧拉路，后者虽可一笔画出，但必须以一个奇顶点为起点，以另一个奇顶为终点。一个奇顶点为起点，以另一个奇顶为终点。图的连通性可以十分容易地用标号算法加以检验。而图的奇顶点数又可通图的连通性可以十分容易地用标号算法加以检验。而图的奇顶点数又可通过对其顶点一一检测而求得。容易看出总计算量是多顶式时间的，故欧拉过对其顶点一一检测而求得。容易看出总计算量是多顶式时间的，故欧拉圈问题和欧拉路问题均是十分简单的圈问题和欧拉路问题均是十分简单的P问题，从而，等价地，一笔画问题问题，从而，等价地

50、，一笔画问题也可十分容易地求解：若图也可十分容易地求解：若图G是欧拉图，则从任一顶点出发均可将它一笔是欧拉图，则从任一顶点出发均可将它一笔画出；若图画出；若图G是欧拉路，则由一奇顶点出发，一一经偶顶点地走过各条边，是欧拉路，则由一奇顶点出发，一一经偶顶点地走过各条边，最后到达另一奇顶点，即可将最后到达另一奇顶点，即可将G一笔画出；否则一笔画出；否则G不能一笔画出，（当然，不能一笔画出，（当然，如何走法仍需规划一下）。如何走法仍需规划一下）。 与欧拉图有较大联系的另一有名的与欧拉图有较大联系的另一有名的P问题是无向图上的中国邮路问题。给问题是无向图上的中国邮路问题。给定一个无向图，它的每一条边上

51、都赋有一个表示该边长度（或费用）的权。定一个无向图，它的每一条边上都赋有一个表示该边长度（或费用）的权。要求从一指定顶点出发，至少经过每一条边一次最后返回原出发点，并使要求从一指定顶点出发，至少经过每一条边一次最后返回原出发点，并使经过边的总长度最小。其中如重复走过某些边，则边长应重复计算，重复经过边的总长度最小。其中如重复走过某些边，则边长应重复计算，重复几次计算几次。一个由邮局出发去各街道送信最后返回邮局的邮递员遇到几次计算几次。一个由邮局出发去各街道送信最后返回邮局的邮递员遇到的问题就是一个中国邮路问题。的问题就是一个中国邮路问题。无向图上的中国邮路问题也不难解决。若无向图无向图上的中国

52、邮路问题也不难解决。若无向图G是欧拉图，则任一欧拉是欧拉图，则任一欧拉图都提供了一条最佳邮路。若图都提供了一条最佳邮路。若G不是欧拉图，如前所说，图中的奇顶点数不是欧拉图，如前所说，图中的奇顶点数必为偶数。然后，求出任意两个奇顶点之间的最短路径及最短矩离最短必为偶数。然后，求出任意两个奇顶点之间的最短路径及最短矩离最短路径长度），再解一个奇顶点之间的最小权匹配（或指派问题，注意这路径长度），再解一个奇顶点之间的最小权匹配（或指派问题，注意这里的距离矩阵是对称的）。将各匹配奇点间的最短路径加入里的距离矩阵是对称的）。将各匹配奇点间的最短路径加入G中，就得到中，就得到了最知路问题的解，我们将在中考

53、察一个这类问题的实例。了最知路问题的解，我们将在中考察一个这类问题的实例。 在本节中，我们例举了几个较为典型而又时常遇到的在本节中，我们例举了几个较为典型而又时常遇到的P问题。由于事实上问题。由于事实上存在着无穷多个存在着无穷多个P问题，而且即使某问题是问题，而且即使某问题是NP完全的，它的许多特殊条完全的，它的许多特殊条件下的子问题也仍然可以是多项式时间可解的，因而我们不可能对件下的子问题也仍然可以是多项式时间可解的，因而我们不可能对P类作类作一完整的介绍。如果本章内容能起到抛砖引玉的作用，使读者看到一些一完整的介绍。如果本章内容能起到抛砖引玉的作用，使读者看到一些P问题所具有的某些特征及构

54、造算法上的某些技巧，那么，我们的目的也问题所具有的某些特征及构造算法上的某些技巧，那么，我们的目的也就达到了。从上述就达到了。从上述P问题（包括第八章中的线性规划、运输问题及指派问问题（包括第八章中的线性规划、运输问题及指派问题）可以看出，它们都可以用某种逐次改进的方法来求解。每次改进中题）可以看出，它们都可以用某种逐次改进的方法来求解。每次改进中的计算量是多项式界的，改进的次数也是多项式界的。线性规划的单纯的计算量是多项式界的，改进的次数也是多项式界的。线性规划的单纯形法例外，改进次数可能达到指数次。但即使是线性规划问题，也已经形法例外，改进次数可能达到指数次。但即使是线性规划问题，也已经找

55、到了具有这种特性的算法，如椭球算法、卡马卡算法，虽然其结构是找到了具有这种特性的算法，如椭球算法、卡马卡算法，虽然其结构是相当复杂的，但计算量却是多项式时间的。相当复杂的，但计算量却是多项式时间的。最后，我们还想强调几点：最后，我们还想强调几点：1、许多表面有点相象的问题事实上可能具有完全不同的计算复杂性。、许多表面有点相象的问题事实上可能具有完全不同的计算复杂性。 这样的例子举不胜举，我们略举一、二，以提醒读者注意。这样的例子举不胜举，我们略举一、二，以提醒读者注意。（1）最短路径问题是）最短路径问题是P问题，而由一点出发到达每一顶点一次（不必返回问题，而由一点出发到达每一顶点一次（不必返回

56、原点）的哈密顿路问题及由一顶点出发经所有顶点一次到达另一顶点的最原点）的哈密顿路问题及由一顶点出发经所有顶点一次到达另一顶点的最短路径问题短路径问题流浪的旅行商问题（流浪的旅行商问题（WTSP）均是）均是NP完全的。这里只增加完全的。这里只增加了每个顶点都要去一次的要求，但问题发生了质的变化，由了每个顶点都要去一次的要求，但问题发生了质的变化，由P问题变成了问题变成了NP完全问题。完全问题。（2）指派问题与）指派问题与TSP也有相似之处，前者求一置换而使目标值最小，后者也有相似之处，前者求一置换而使目标值最小，后者求一循环置换（不包含子圈）而使目标值最小。前者是求一循环置换（不包含子圈）而使目

57、标值最小。前者是P问题，而后者则是问题，而后者则是NP完全的。完全的。（3）欧拉圈问题求由一顶点出发经且仅经过每边一次回到原顶点的圈，而）欧拉圈问题求由一顶点出发经且仅经过每边一次回到原顶点的圈，而TSP则求由一顶点出发经且仅经过每个顶点一次返回原顶点的圈。前者是十则求由一顶点出发经且仅经过每个顶点一次返回原顶点的圈。前者是十分容易的分容易的P问题，而后者是极其困难的问题，而后者是极其困难的NP完全问题，迄今还没有求解它的较完全问题，迄今还没有求解它的较好算法。好算法。（4）线性规划问题、运输问题及指派问题均为）线性规划问题、运输问题及指派问题均为P问题，但相应的整数线性问题，但相应的整数线性

58、规划及规划及01规划均为规划均为NP完全的。完全的。 （5）无向图中国邮路问题是）无向图中国邮路问题是P问题，而有向图中中国邮路问题则是问题，而有向图中中国邮路问题则是NP完完全的，（容易看出，会解有向图上的某问题必也会解无向图上的相同问题，全的，（容易看出，会解有向图上的某问题必也会解无向图上的相同问题，但反之不真）。但反之不真）。 2、求最小的问题是、求最小的问题是P问题，求最大的问题可以是问题，求最大的问题可以是NP完全的，这样的例子完全的，这样的例子也不少。例如，最短路径问题是也不少。例如，最短路径问题是P问题，而最长简单路径（不含圈的路径）问题，而最长简单路径（不含圈的路径）问题却是

59、问题却是NP完全的。如若不然，我们可以利用它的有效算法如下构造出完全的。如若不然，我们可以利用它的有效算法如下构造出哈密顿问题的有效算：令图哈密顿问题的有效算：令图G=（V，E）的所有边的权均为）的所有边的权均为1，以一端点，以一端点为起点求到其余各顶点的最长简单路径。由于简单路径不含圈，所有顶点为起点求到其余各顶点的最长简单路径。由于简单路径不含圈，所有顶点均不会重复到达，故均不会重复到达，故G有哈密顿路当且仅当存在一起点及一终点，其最长有哈密顿路当且仅当存在一起点及一终点，其最长简单路径为简单路径为| V |1。由于哈密顿路问题是。由于哈密顿路问题是NP 完全的，故最长简单路径问完全的，故

60、最长简单路径问题的有效算法不可能存在，除非题的有效算法不可能存在，除非P=NP。所以，如果你想设计一个求图上。所以，如果你想设计一个求图上两点间的最长简单路径的有效算法，不管你是多么努力，最终必将以失败两点间的最长简单路径的有效算法，不管你是多么努力，最终必将以失败告终。又譬如，网络流中的最大流问题是告终。又譬如，网络流中的最大流问题是P问题。相应地，最小切割问题问题。相应地，最小切割问题也是也是P问题（它是最大流问题的对偶问题，见线性规划的对偶理论）。但问题（它是最大流问题的对偶问题，见线性规划的对偶理论）。但可以证明，最大切割问题却是可以证明，最大切割问题却是NP完全的。完全的。总之，在研