数学建模离散优化模型与算法设计.ppt
《数学建模离散优化模型与算法设计.ppt》由会员分享,可在线阅读,更多相关《数学建模离散优化模型与算法设计.ppt(156页珍藏版)》请在三一办公上搜索。
1、数学建模离散优化模型及算法设计,第9章:某些P问题及其算法,之前,我们介绍了与计算复杂性有关的一些基本概念.人们发现,在离散问题中存在着两个互不相交的类:P类与NP完全类(若PNP)。前者具有求解的有效算法而后者不可能有这种算法。从这一点上讲,P问题可以看成是一类具有良好性质而又较容易求解的问题,而NP完全问题则是固有地难解的。,在8.4中看到,有着广泛应用背景的线性规划问题是一个P问题。这样,作为线性规划子问题的运输问题及作为运输问题子问题的指派问题自然更是P问题。虽然从平均的角度讲,人们似乎更常遇到NP完全问题,但P仍不失为一个十分重要的问题类。一方面,很多P问题象线性规划一样有着极广泛的
2、应用前景,且它们本身又是十分有趣的;另一方面,它们也是研究一些更为复杂、难解的问题时经常被采用的研究工具。在本章中,将再介绍一些经常遇到的P问题并给出求解它们的有效算法。,一、拟阵问题及贪婪算法,在P类中又存在着一个被称为拟阵的具有更为良好性质的问题类,其中的任一问题均可用一种被称为贪婪法的方法来求解,而这一性质并不是所有的P问题都具有的。,例 9.1(最小生成树问题MST)给定一连通图G=(V,E),有一表示边长的权C(e)(表示顶点间的距离或费用),求此图的具有最小总权的生成树。,此问题的标准形式为给定一完全图G,其每边赋有一权数,求此完全图的最小生成树。所谓树是指连通而无圈的图,单独的一
3、个点也可看成一颗树。树用(U,T)表示,U为树的顶点,T为树的边集。不相交的树的集合被称为森林。一个连通图的生成树是指图中具有最多边数的一棵树。容易证明,对于一个连通图G,G 的任一生成树必有V-1条边。,求解最小生成树的算法主要依据下面的定理:,定理 9.1 设(V1,T1),(Vk,Tk)为连通图G中的森林,V1 U V2U Vk=V。k,若仅有一个顶点在Vi中的具有最小权的边为(,u),则必有一棵G的最小生成树包含边(,u)。,根据定1可以作了如下算法:任选一点,令 若V1=V,停;否则,找出仅有一个顶点在V1中的边里具有最小权的边(,u),设,将u加入V1(,u)加入T。重复上述步骤,
4、直到V1=V。,证明:设G的一棵最小生成树(V,T)不含(,u)。将(,u)加入T,由于(V,T)是生成树,T U(,u)中含有过(,u)的唯一的圈。不妨设,则,此圈中的点不全由Vi中的点组成,因此必存在圈中的另一边。删去边 得到一新的生成树(V,T1),T1=,须其总权不超过(V,T)的权,即(V,T)是包含边(,u)的最小生成树。,例9.2 求图9.1中图G的最小生成树。,解:不妨从顶点开始寻找。标号1,先加入(因为边权最小),标号2。再加入 标号3。,每次加入一条一顶点已标号加一顶点未标号而又具有最小权的边,直到所有顶点均标号为止。找到的最小生成树已用又线标在图9.2中。,容易看出算法的
5、计算量为O(V)2,所以此算法是有效算法,若G具有O()条边,其中n=V,计算量的界还是不能改进的,因为每条边至少应被检查一次。,由例9.2可以看出,算法执行的每一步均加入一条可以加入的(即不生成圈的)具有最小权的边,而不去考虑它对以后选取的影响,这种算法被称为贪婪算法。,例9.3(入树问题)给出一个有向图G=(V,A),对A中的每一条孤e,给出一个权C(e),求A的一个具有最大权(或最小权)的子集B,要求B中任意两条孤都没有公共的终点。,考察下面的入树问题实例:,例9.4 给出有向图G=(V,A)(图9.3),孤上标出的数字为该边的权,求此图具有最大权的入树。,解:由于入树不能包含具有公共终
6、点的孤,故对每一顶点 只能选取一条入孤。为使选出的弧具有最大权,只需要对每一顶点选取权最大的入孤,可用计算量为O(VE)的贪婪法求解,具有最大权的入树为。,类似地,出树问题也可以用贪婪法求解。,例9.5(矩阵拟阵问题)给出一个矩阵Amxn,记其n个列向量为e1,,en。设对每一列向量en已指定一权C(en)求 的一个线性无关的子集,它具有最大的权和。,易见,这一问题也可以用贪婪法求解。集合 的线性无关的子集被称为独立子集,利用贪婪法必可求得具有最大权的独立子集,可用线性代数知识加以证明(见习题1)。,例9.6 求矩阵A的列向量具有最大权和的独立子集,C(ei)8 4 7 5 2 6 4,解:采
7、用贪婪法,先取权最大的列e1,同时对A作高斯消去,逐次加入线性无关的向量:,A的列向量中具有最大权的独立子集为。,定义9.1(拟阵)设E是一个有限集,为E的部分子集构成的封闭系统(即若,则必有)。若M=(E,)上的离散优化问题的每一实例均可用贪婪算法求出最优解,则称M为一拟阵。(注:被称为独立系统)。,现以矩阵拟阵为例,对定义9.1作一说明。对矩阵拟阵的每一实例,E=e1,en为矩阵列向量的集合,为E的线性无关子集构成的系统,称为独立系统,其元素被称为独立子集。由于E的任一线性无关子集的子集也是E的线性无关子集,故独立系统是封闭的。又由于这一离散优化问题的任一实例都可用贪婪法求解,故构成一拟阵
8、,被称为矩阵拟阵。例9.1被称为图拟阵,例9.3被称为划分拟阵。,拟阵问题(或称拟阵结构)有一个明显而又本质的特性,其任一极大独立子集中包含着相同个数的元素,从而可以引入基的概念。例如,矩阵列向量的所有线性无关极大组均具有相同的向量个数,这就导出了基即矩阵列秩的概念。对于图拟阵,每一极大独立集均为一生成树,其边数均为|V|-1。对于划分拟阵,孤集被划分成个|V|个子集,每一子集由指向同一顶点的孤组成。显然,任一极大独立集应在每一子集中取一条孤,故其基数为顶点个数。,我们不加证明地引入下面的定理,虽然其证明并不十分困难。,定理9.2 E为一有限集合,为E的部分子集构成的封闭独立系统。以下两个条件
9、均为M=(E,y)构成拟阵(即其上的优化问题可用贪婪法求解)的充分必要条件:,(条件2)若I、I均为A的两个极大独立集,则|I|=|I|。,(条件1)若I、I|I|I|,则必可找到一个元素e,使得(注:|表示元素个数),二、两分图匹配问题与增广路算法,在上一小节中我们已经看到,有些P问题可以用极为简单的贪婪法求解。但对绝大多数的P问题来说,这一结果并不成立,只能根据其本身的结构,去寻找求解它的独特算法。下面,我们将介绍几个这样的P问题。,例9.7(婚姻问题)在遥远的地方有一位酋长,他想把三个女儿嫁出去。假定三个女儿为A、B、C,三位求婚者为X、Y、Z。每位求婚者对A、B、C愿出的财礼数视其对她
10、们的喜欢程度而定:,问酋长应如何嫁女,才能获得最多的财礼(从总体上讲,他的女婿最喜欢他的女儿)。,例9.7显然是指派问题的实例,但它也可以看成是两分图赋权匹配问题的实例。,用三个点表示酋长的三个女儿,将它们放在一边。再用三个点表示求婚者,将它们放在另一边。在有可能结婚的两人之间画一条边,并在边上写上求婚者对这种结婚愿付出的财礼数,得到图9.4。图9.4是一个特殊的图,它的顶点可以分成两个子集,只有分属不同子集的点才可能有边相连(但也可以无边),这样的图称为两分图。,定义9.2(匹配)图G的一个匹配是指边集E的一个子集M,M中的任意两条边均不具有公共的顶点。,容易看出,酋长要解的问题是在两分图图
11、9.4中找出一个具有最大权和的匹配,读者不难由此得到一般两分图最大权匹配问题的数学模型。,由于两分图最大权匹配问题等价于指派问题,所以它是一个P问题。对于这一P问题,我们是否也能象前面一样用贪婪法求解呢?如果用贪婪法求解例9.7,则有C嫁y(28头),去除C、y及相应边(一夫一妻);再将B嫁x(5头),去除B、x及相应边;最后,A只能嫁Z(1头)。共得财礼34头牛。事实上,酋长的女儿只有六种嫁法(3!),比较所有方案,发现C嫁x、A嫁y、B嫁z最好(y几乎差不多同样喜欢C和A,而z则明显喜欢C而不太喜欢A),可得财礼57头牛。虽然后一算法不是多项式时间的,对待嫁者数量稍大的问题无法求得结果,但
12、对本例,它至少表明用贪婪法没有求得最优解,因而两分图最大权匹配问题不是拟阵问题(或者讲不具有拟阵结构),从而,一般赋权图上的最大权匹配问题更不是拟阵问题。J.Edmonds将最大权匹配问题表示成为一个特殊的线性规划并由此导出了用他的名字命名的O(n4)算法,由于他的算法较复杂,本书不准备作详细介绍,有兴趣的读者可查阅C.H.Papadimitriou“组合最优化,算法和复杂性”一书第十一章。至于两分图赋权匹配问题,由于它与指派问题的等价性,完全可以用计算量O(n3)的匈牙利方法求解,也可以化为后面的网络流问题求解。,如果所有边的权均为1,则最大权匹配化成最大匹配问题(即求边数最多的匹配)。对于
13、这一较为简单的子问题,存在着增广路算法。,定义9.3 设M是图G的一个匹配,M中的边称为匹配边,其端点称为一对配偶(其它边称为未匹配边或自由边)。V中已有配偶的点称为已盖点,否则称为未盖点。,定义9.4 依次取未匹配边、匹配边的路称为交错路。,由未盖点到未盖点的交错路称为增广路。易见,增广路中未匹配边的数目比匹配边的数目多一条,且交换增广路中的未匹配边与匹配边可以得到一个多一条边的匹配。,例9.8 在图9.5(a)中,用双线划出的边组成该图的一个极大匹配。由未盖点 出发,可作出增广路,从而可得到一个增加一条匹配边的更大匹配,如图9.5(b)所示。此时,图中虽然仍存在未盖点,但 均已成为已盖点,
14、故(b)中的匹配已是最大匹配。本例再次表明两分图匹配问题不是拟阵问题(即使是不加权的),因为其极大独立集中的无素个数可以不同。,定理9.3 M是图G中的最大匹配当且仅当G中不存在关于M的增广路。,证明:必要性显然,现证充分性。若存在G中的更大匹配M,合并M、M得到一个图G,易见G每一顶点的次至多为2(注:G可能不连通)。G可包括偶数边的圈,圈中M与M中的边的数量相等。由于|M|M|,G中至少含一条路,其中M中的边多于M中的边,不难看出,这条路是G的关于M的增广路。,现在可以看出,找最大匹配的关键在于找增广路。读者不难用顶点标号的办法(由未盖点出发),作出一个求解两分图匹配的增广路算法。此算法稍
15、加改动,还可以用于非两分图的情况。,三、网络流问题,网络流问题是又一类具有广泛应用前景的P问题,本节将介绍一些有关网络流问题的基本理论与算法。,1、最大流问题(MFP),边赋值的有向图称为网络。给定一个网络,其边赋值表示该边的容量。最大流问题要求在不超过边容量的前提下求出网络中两个指定顶点之间的最大流。例如:当网络是通讯网时,我们可能会去求出网络中两个指定点间的最大通话量;当网络是城市的街道时,我们又可能会去求两地间的最大交通流,即单位时间内允许通过的车辆数等等。,建模:给定一有向图G=(V,A),A的每一条孤(边)(i,j)上已赋一表示边容量的非负整数C(i,j)。并已指定V中的两个顶点 s
16、、t,分别称它们为发点和收点。,设网络中已存在一个流(不一定是最大流),记孤(i,j)上的流量为(i,j),记s发出的总流量(即t收到的总流量)为,根据平衡条件,可得如下的约束条件,有,其中是 指A中以顶点i为起点的孤集,是指A中以 i为终点的孤集,(.1)式表示s发出流为,t收入的流为,其余各点只起中转作用,既不增加也不消耗流量。根据边容量限止,还应有,而我们的愿望是使总流量尽可能地大。即在(9.1)、(9.2)式约束下使达到最大,易见,这是一个线性规划问题的子问题,故 类。,对于一个较为复杂的网络,要想直接找出最大流是不太可能的。为了简化问题,我们先引入一些符号。,记、为的两个不相交的子集
17、,s,用(,)表示发点在,收点在的边集,记,并定义如下的切割概念:,定义9.5(切割)设是的顶点集合的一个真子集,为关于的补集。若、满足 且 则称和 为的一个切割。,根据切割的定义可以看出,当和 为一切割时,如果去掉连接和的边集(,),就切断了由通往t的所有通路。所以,对网络的任一切割(,),(,)必为最大流的一个上界,而。,例9.9 网络如图9.6所示,边(弧)上的两数字分别表示边容量及实际流量。取,则,显然、是网络的一个切割。对于这一切割容易算出而网络的流量。,为了尽可能地增大网络上的流量,按如下方法作出一个和具有相同顶点并具有相同发点和收点的增广网络()(简记)。包含两类边,对中每一条边
18、(i,j):,(1)若,作正向边(i,j),规定容量,即剩余容量。,(2)若,作反向边(j,i),规定容量 事实上是边(j,i)上最多可减少的容量。,第一类边称为正规边,第二类边则称为增广边。例如由图9.6中的流可以作出其相应的增广网络图9.7,其中实箭线为正规定,虚箭线为增广边,边上的数字为边容量。,如果增广网络上存在着由st的通路p(称为原网络的一条增广路),记,则只要在P中的一切正规边上增加流量a,而在对应增广边(j,i),G的边(i,j)上减少流量a,就得到G的一个由st的增大了流量a的更大的流。例如,从图9.7上可以找出增广路,a=2。于是,图9.6中的流可改进增大为图9.8(a)中
19、的流,总流量为7。由于其增广网络图9.8(b)中不再存在增广路,无法再继续增大。容易看出,若取s出发(在增广网络上)可到达的点的集合为P,则P=,,=,,C(P,)=7,而流量已达到7,故此流已是最大流。,(1),(2),故,已不能再增大,(注:这是线性规划的补松驰定理)。,综上所述,有下面的有关网络流问题的定理。,定理9.5(Ford和Fulkerson最大流最小切割定理)任一由s到t的流,其流量不大于任一切割的容量C(P,),而最大流的流量则等于最小切割的容量。进而 为最大流且(P,)为最小切割当且仅当:(1)有(2)有。,增广路可以通过对顶点标号的方法来寻找。由于边容量均为整数,而每次经
20、改进,流量至少增加一,故算法总能很快求得最大流。,定理9.4 网络G上的流是最大流的充要条件为其增广网络上不存在由s到t 的通路。,证明:若增广网络上存在由s到t的通路P,则对P上的正规边(i,j)增加流量a,对P的增广边(j,i)对应G的边(i,j)减少流量a,即可得到一个更大的可行流。若增广网络上不存在由s到t的路,记增广图上s可达到的点组成的集合为P,则对切割(P,)必有:,2、最小费用最大流问题,对于一个给定的网络,由发点s到收点t常常存在着多个具有相同流量的最大流。如图9.9所示,图中的(a)、(b)、(c)均是流量为7的最大流,边上的两个数字依次为容量和边上的实际流量。有时候,当流
21、流经一条边时需支付一定的费用,我们不仅希望找出一个最大流,而且希望找出的最大流在具有相同流量的流中具有最小的总费用,这时问题可描述为:对有向图G=(V,A)的每条边(弧)(i,j)给定一个边容量C(i,j)及一个单位流量费用l(i,j)。希望求出由s到t的最大流,使得总费用最少,即求最大流*,使,例如,在交通网络中,l(i,j)可以是i,j之间的距离或运费。自然,在运送相同数量货物时,我们希望总距离或总运费最小。现在,我们将以最大流问题的增广路算法为基础,导出求解最小费用最大流问题的算法。,对于网络上的一个现行流,作出其增广网络G(),对G中的正规边赋值l(i,j),对G中的增广边(i,j)则
22、赋值l(i,j)。,定义9.6 增广网络G上由s到t的流量为零但边流量不全为零的流称为一个循环流。,最小费用最大流问题可以变换成为一个线性规划问题,根据线性规划理论可以证明下面的定理:,定理9.6 网络中的流 是最小费用的,当且仅当其增广网络G中不存在负费用的循环流(证明略)。,例9.10 图9.10(a)给出了有向图G上的一个可行流,其中弧上的三个数字分别为容量、单位流费用及实际流量。图9.10(b)为相应的增广网络,其中边(弧)上的两个数字分别为容量及单位流费用。求此网络的一个更小费用流。,从图9.10(b)中可以找出一个负费用循环流s21s(其余边流量为0),每单位流量的总费用为5。调整
23、此循环流上的流量,得到图9.11(a)中的流。原先的流总费用为17,调整后的总费用为12,减少值为负费用循环流的总费用。,图9.11(a)中流的增广网络(b)中已不存在负费用循环流,它是一个最小费用的流。,定理9.7 设1是网络上流量为的最小费用流,2是其增广网络上由s到t的最小费用单位流增广路,则1+2是此网络流量为+1的最小费用流。,证明:设1+2不是流量为+1的最小费用流,由定理6,在 1+2的增广网络中必存在一负圈C。记构造2的增广路为P。由于 1是最小费用流,1的增广网络中不存在负圈,故C中必有一边(i,j),其反向边(j,i)含在P中(因为如若不然,C不含P中任意边,则C将含在1的
24、增广网络中,与1为最小费用流的假设矛盾,见图9.12),但这又说明P(C(i,j)是S到t的更小费用单位流增广路,与P是最小费用单位流增广路的假设矛盾。,根据定理9.7及定理9.6,求最大流的算法只需稍作变动即可用来求解最小费用最大流。算法可以用归纳方式给出,当=0时,可取=0,这显然是=0的最小费用流。在以后逐次增大流量时,若增广网络中存在着多于一条增广路时,每次均选用其中单位流费用最小的一条。这样,每次得到的均为相同流量的流中费用最小的,而最后得到的即为最小费用最大流。,网络流问题的算法在解决实际问题时常常被用到。它可用来求解运输问题、指派问题及赋权两分图匹配问题(等价于指派问题),也可用
25、来寻找网络的瓶颈即最小切割(P,)确定的边。作为一个网络流问题的应用实例,我们来求解例9.7中的婚姻姻问题:增加发点s和收点t,将原图的边改为有向边,所有边的容量为1。找出最大财礼数28,以此数减每边原有的财礼费,并用此差为各边的费用,得一最小费用最大流问题(未注数字的边费用均为零),其网络图见图9.13。此问题在使用三次增广路后可求得最佳结果。,四、最短路径问题,最短路径问题是又一个经常遇到的P问题,它在工艺流程的安排、管道或网络的铺设、设备更新等实际生产中常被用到,是网络规划的基本问题之一。顾名思义,最短路径求的是以下问题:给定一个网络,如何求出网络中指定两点间总距离(或总费用)最小的路径
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学 建模 离散 优化 模型 算法 设计

链接地址:https://www.31ppt.com/p-5985149.html