运筹学课件2(ppt 112)

1,第五章对策论模型,对策论是研究具有斗争性质现象的数学理论和方法，它是运筹学的一个重要分支。最早的运筹学思想可以追溯到战国时期的齐王赛马，近年来运筹学思想普遍运用到经济学中，用于解释一些经济现象和做出最好的经济决策。事实上，经济学和对策论的研究模式都是强调个人理性，在给定的约束条件下追求效用最大化，1994年诺贝尔经济学奖授予了三位博奕论专家：纳什(Nash)、塞尔腾(Selten)和豪尔沙尼(Harsanyi)，其中最重要的原因之一是他们在非合作博奕论方面作出了突出的贡献。,一、对策现象的三要素,2,任何对策现象都包括三个基本要素：1.局中人：对策中有权决定自己行动方案的参加者，称为局中人。局中人可以是人，也可以是集团，如齐王赛马的齐王和田忌分别都是局中人；在人与自然的斗争中，人和自然都是局中人。通常用I表示局中人集合，如果有n个局中人，则I=1,2,n。一般要求一个对策中至少有两个局中人。局中人总是被假定是聪明且有理智的。2.策略集：对策中可供局中人选择的一个实际可行的完整的行动方案，称为一个（纯）策略；参加对策的每一局中人iI的策略集记为Si。一般每一局中人的策略集中至少应包括两个（纯）策略。如齐王赛马中，若用（上、中、下）表示以上马、中马、下马依次参赛，就是一个纯策略。齐王与田忌的策略集中，各自都有六个纯策略：S1,S2=(上、中、下),(上、下、中),(中、上、下),(中、下、上),(下、上、中),(下、中、上),3,3.赢得函数（支付函数）（1）局势：对策中，每一局中人所选定策略形成的策略组合称一个局势。设局中人1从自己的策略集S1=1,2,m中选定策略i，局中人2从自己的策略集S2=1,2,n选定策略j，则(i,j)就构成两人对策中的一个局势。在n个对策中，设si表示第i局中人的一个策略，则n个局中人的策略组合形成的局势为S=(s1,s2,sn)。（2）赢得函数：当一个局势S出现后，各局中人都有自己的结果（得失），记为Hi(S)，它表示第i局中人的赢得（支付）值。显然Hi(S)是局势的函数。,例如在“齐王赛马”中，局中人集合I=1,2，齐王和田忌的策略集分别用S1=1,6和S2=1,6表示。在1=(上、中、下)，1=(上、中、下)构成的局势S1=1,1下，齐王的赢得为H1(S)=3，田忌的赢得为H2(S)=-3。,4,二、对策的分类,三、两人有限零和对策的数学模型,两人有限零和对策，又称为矩阵对策。其数学模型为：=,;S1,S2,A或=S1,S2;A其中策略集S1=1,2,m，S2=1,2,n分别为局中人和的策略集，A=(aij)mxn为局中人的赢得矩阵，由于假定对策的结果为零和，所以局中人的羸得矩阵为-A。,5,这是一个两人有限零和对策。,例如“齐王赛马”对策的数学模型如下：=S1,S2;A其中S1=1,6，S2=1,6，i，i(上、中、下),(上、下、中),(中、上、下),(中、下、上),(下、上、中),(下、中、上),6,四、在纯策略下有解的矩阵对策的解法,解：,1.解法的思想：双方都立足在不利的情况下争取最好的结果最大最小原则。例求解矩阵对策=S1,S2;A，其中:,7,3.方法步骤：上例求解过程可简单的表述如下：,其步骤是：第一步：分别确定A各行中的最小值，并在该数字上加圈表示；,2.在矩阵对策中，若ai*j*成立，则称ai*j*为对策的值，记为V=ai*j*。称使上式成立的纯局势(i*,j*)为对策在纯策略下的解（亦称均衡局势）。i*和j*分别称为局中人和的最优纯策略。,第二步：分别确定A各列中的最大值，并在该数字上加框表示；,8,第三步：若A中的某元素同时被圈和框住，则该元素即为对策的值，该元素所在的行和列对应的策略则分别为局中人和的最优纯策略，并由最优纯策略组成了对策的解。因此上例对策的值V=2，对策的解为(2,2)，2,2分别是局中人和的最优纯策略。在纯策略下有解的矩阵对策中，值ai*j*既是所在行的最小值，又是所在列的最大值，称其为鞍点。所以这类矩阵对策又称为有鞍点的对策。这个事实可推广到一般，即在纯策略下矩阵对策=S1,S2;A有解的充要条件是：存在纯局势(i*,j*)，使得对于一切的i=1,2m,j=1,2n均有,aij*ai*j*ai*j,矩阵对策的解可以不唯一。,9,例2求下列矩阵对策的解,在此例中,对策的解不唯一.当解不唯一时,解之间的关系具有如下性质:,(1)无差别性:即若(i1,j1),和(i2,j2)是对策的两个解，则,（2）可交换性：即若(i1,j1),和(i2,j2)是对策的两个解，则(i1,j2),和(i2,j1)是也对策的两个解。,10,五、具有混合策略的矩阵对策,该矩阵对策在纯策略下无解。此时，用最大最小原则来选取各自的纯策略都不会是稳定的，因为各局中人可以选取其它的纯策略来改善自己的赢得值。,11,在上述双方都不能固定采用任何一个纯策略下，必须随机地选取自己的各个纯策略，使双方捉摸不到自己使用的策略，以求得自己的期望赢得最大（或期望损失最小）。在上例中，若局中人1以概率x选用1,以概率1-x选用2,局中人2以概率y选1,以概率1-y选2，则局中人1的期望赢得为,12,1.混合策略和混合局势,（X，Y）称为混合局势。,2.混合扩充和混合策略下的解当X，Y由局中人1和局中人2分别独立决定以后，纯局势以概率xiyj出现，于是局中人1在混合策略下赢得的数学期望为,13,在纯策略下矩阵对策的解是混合策略下矩阵对策解的特殊情况。3.基本定理（不加证明）（1）在混合扩充下，任何矩阵对策必有解；（2）在混合策略下，(X*,Y*)是对策解的充要条件是：,类似于纯策略的情况，若,则称E（X*，Y*）为对策的值，称（X*，Y*）为对策在混合策略下的解，X*和Y*分别为局中人1和局中人2的最优混合策略。,其等价形式是:,14,作为应用，给出（2）的另一等价形式：（3）(X*,Y*)为对策的解的充要条件是存在数v，使X*,Y*分别是下面两个不等式组的解：,15,（1）,（2）,六、矩阵对策的一般解法1、LP法,其中v为对策的值。作如下变换，（设v0）,于是不等式组（1）和（2）变为等价的互为对偶线性规划问题,16,应当指出，在未求解(P)和(D)之前，V的正负是未知的。当V=v0时，可以v0或v0，此时建立的LP模型(P)和(D)可用单纯形法求解，且X*0,Y*0,（2）若A=(aij)mxn中含有负元素时，则有可能出现v0，由此则可能出现无解，这与基本定理相矛盾。此时，可根据下述定理进行处理：定理：设对策=S，S；A和对策=S，S；A，其中A=(aij)mxn，A=(aij+k)mxn,k为任一常数，则与的解相同，且V=Vk。,其方法是先对含有负元素的A加上正数k,k=-minaij，构成一个新的赢得矩阵A，再用LP法进行求解，所得的解就是原对策的解，但V=Vk。,17,2.2n对策的解法,(1)22对策的公式法,由于在纯策略下无解的22对策，其最优混合策略(x1*,x2*)0，(y1*,y2*)0，所以由LP对偶理论中的互补松驰性定理知，基本定理(3)的两组不等式均可取等式。即,由A建立的两个互为对偶的线性规划模型如下：,18,有唯一解：,19,例3求解下列矩阵对策=S1，S2；A,解：（1）这是一个无鞍点的矩阵对策。,（2）是一个有鞍点的矩阵对策，用鞍点法求得对策的解为(2*,1*)，对策值为V=2,20,(2)2n对策的代数解法：对2n对策，可先将2n对策转化为Cn2个22子对策，再利用22对策的公式法，分别求出各子对策的值，最后从中解出2n对策的解，其步骤如下：第一步：由2n阶矩阵A分别写出Cn2个22阶子矩阵Ai；第二步：分别求出各Ai相应子对策的值Vi；第三步：取V=minVi=Vk,1kN，其中N=Cn2,Ak是由A中的两列所构成；第四步：求出Ak相应子对策Vk的解X(o)、Y(o)，取X*=Xo，同时在Y(o)中添加n2个0分量在对应列的位置上，构成Y*，则(X*Y*)就是原2n对策的解。,21,解：（1）对应于A的三个子对策的赢得矩阵为,（2）分别求以A1，A2，A3为赢得矩阵的相应子对策的值VA1=21/5，VA2=119/23，VA3=7（3）取V=minVA1，VA2，VA3=min21/5，119/23，7=21/5（4）用公式法求V=21/5对应的子策略A1的解,由于A1是由A的第一、二列组成，则局中的选择第三列的概率为0。,（5）因此原矩阵对策的解为：X*=（3/5，2/5），Y*=（7/15，8/15，0），V=21/5,22,4、迭代法对于赢得矩阵阶数较高的矩阵对策，除了可用线性规划求解外，还可用以下的迭代法求解。迭代法的基本思想是：两个局中人反复进行多局对策，在每一局中各局中人都根据在此以前的各局对策中可能赢得的总和，在自己的纯策略中选取一个使自己累计所得最多（或损失最少）的纯策略。在多局对策后，当迭代的结果双方达到一定的满意程度时，迭代结束。此时用局中人纯策略在已进行的各局对策中出现的频率分布作为最优混合策略中概率分布的一个近似。因此，迭代法是一种求解矩阵对策的近似解法。,23,例11试用迭代法求解以下阵对策,解：对于第一个局中人,对于第二个局中人,24,对于第一个局中人,对于第二个局中人,25,对于第一个局中人,对于第二个局中人,局中人的最优混合策略,局中人的最优混合策略,对策值V=(2/3+4/3)/2=1,26,练习4、甲、乙两厂竞争A、B两种产品的市场，目前甲厂这两种产品的销量都只是乙厂销量的三分之一。两家工厂都已完成这两种产品更新换代的研制，但要投产上市则还需要一段时间。若同时投产两种新产品上市，每厂都需一年；若只投产一种抢先上市，则甲有厂需10个月，乙厂需9个月，而另一种产品对每厂都再需9个月才能上市。对任一种新产品，若两厂产品同时上市，估计甲厂该产品的市场占有率将增加8个百分点（即由25%增至33%）；若甲厂产品抢先2，6个月上市，则其市场占有率将分别增加20，30个百分点；若甲厂产品落后1，3，7个月上市，则其市场占有率将分别下降4，10，12个百分点。假设每厂都以其两种产品市场占有率增加的百分点数之和的一半作为赢得指标，试建立此对策的模型并求解。,27,七、求解矩阵对策中的计算技巧,1.用优超原则简化赢得矩阵例,优超原则：在A=(aij)mxn中(1)若第k行与第l行的各元素均有akjalj(j=1,2n)则称局中人的纯策略k优超于纯策略l，此时在最优混合策略中必有Xl*=0。（即可在A中删去第l行）。(2)若第p列与第q列的各元素均有aipaiq(i=1,2m)则称局中人的纯策略p优超于纯策略q，此时在最优混合策略中必有yq*=0（即可在A中删去第q列）,28,值得指出的是，对于A中的纯策略i1(或j1)不为纯策略i2im(或j2jm)所优超。但被它们的凸组合所优超，即,此时，同样可在A删去第i1行(或第j1列)，对策的解不变。2.若两个矩阵对策1=S,S,A1，2=S,S,A2且满足A1=A2+k(k为任一常数)，则V1=V2+k，且它们有相同的解。3.若两个矩阵对策1和2满足A1=kA2(k为任一常数)，则V1=kV2，且它们有相同的解。4.设A为n阶对角矩阵（即主对角线上的元素为a11,a22ann，其余元素均为0）。若a11,a22ann符号相同，则,29,例两小孩猜扑克牌花色，游戏规定：由甲小孩每次从4种花色的牌中拿出一张牌给乙小孩猜，猜对花色，甲付给乙小石子三个；猜不对，乙付给甲一个石子，试求游戏的解。解据题意，该游戏可归结为矩阵模型G=S甲,S乙,A，其中甲小孩的赢得,30,显然该对策无鞍点，为简化计算，对A中各元素减1，得,即甲、乙两小孩应以1/4的概率出（或猜）各种花色的牌，互不吃亏。,31,“齐王赛马”的羸得矩阵满足上述条件，故由此可得,X*=Y*=(1/6,1/6,1/6,1/6)，且VG=6/6=1。,对于矩阵对策，该选用哪种方法进行求解？一般可按以下顺序进行考虑：1首先，用最大最小原则试求鞍点。若无，则考虑以下方法；2若A为特殊矩阵，则可选用上述4,5给出的结论，直接求解；3对33阶以上的赢得矩阵A，试用优超法将A降阶4对2n对策，可转化为Cn2个22对策，分别用公式法求解，并从中求出原对策的解；5以上方法均不可行时，则可用LP法或迭代法求解。,32,2.两人有限非零和对策,在许多对策问题中，对策双方的得失之和并不等于零，即局中人一方的得并不等于另一方得失，这就是两人有限非零和对策。如两家企业竞争某种商品的市场占有率，当他们采取某些策略时，有可能产生双赢的结果。,1、两人有限非零和对策的数学模型例18甲、乙两家面包店在市场竞争中，各自都在考虑是否要降价，如果两家都降价，则各家可得3百元的利润，如果都不降价，则各家可得利润5百元，如果一家降价，另一家不降，则降价的一家可得利润6百元，不降价的一家由于剩余损坏等原因而亏损4百元，问双方应如何选择行动较为合理？,33,依题意，把上述问题表述成如下表格：,这个问题的数学模型可表示为：,一般地，两人有限零和对策的数学模型可表示为,34,随着A,B的确定，两人有限非零和对策也就确定，因此两人有限非零和对策又称为双矩阵对策。特别，当A=-B时，双矩阵对策就是矩阵对策。在上述这个竞争对策中，两家面包店在没有互通信息非合作情况下，各自都有两种策略的选择，降价或不降价。显然，双方最好策略的选择都是降价，即（1，1）。因为选择降价至少可以得到3百元的利润，如果选择不降价，则可能由于对方降价而蒙受4百元的损失。当然，在两店互通信息，进行合作的情况下，双方采取不降价的策略，各自都能得到5百元的利润。例19设想一个垄断企业已占领市场（称为在位者），另一个企业很想进入市场（称位进入者）。在位者想保持其垄断地位，就要阻绕进入者进入。假定进入者进入之前在位者的垄断利润为300，进入后两者的利润合为100（各得50），进入成本为10。试分析两者的最佳策略。,35,根据题意，可得如下表格：,对于这个对策问题，经过分析容易得到（1，1）（进入，默许）和（2，2）（不进入，斗争）是双方选择的最好的局势。,2、非合作两人对策的解法在这里所讨论的两人有限非零和对策中，假定对策双方都了解对方的纯策略集和赢得函数，但不合作，并且局中人在选择自己的策略时不知道对方的选择。（1）非合作两人对策的解纳什均衡一般地，对于非合作两人对策S1,S2;(A,B),如果i*S1,j*S2分别是局中人1和2的最优纯策略，则称局势(i*,j*)是一个纳什均衡.,36,求非合作两人对策的纳什均衡解的步骤如下：1、在双矩阵对策（A,B)表中，对于矩阵A的每列，分别找出赢得最大的数字，并在其下划一横线；2、在双矩阵对策（A,B)表中，对于矩阵B的每行，分别找出赢得最大的数字，并在其下划一横线；3、如果表中某格的数字下面都被划上横线，则此格对应于两个局中人相应策略的组合就是一个（纯策略下的）纳什均衡。否则，该对策不存在纯策略下的纳什均衡。例如：,37,（2）混合策略纳什均衡上面所介绍的非合作两人有限对策是在纯策略下有解的对策问题，其特点是纳什均衡中的策略是每一个局中人的一个完整策略。但是有些对策并不存在纯策略下的纳什均衡，如下例：例20局中人是政府和一个流浪汉，流浪汉有两个策略：寻找工作或游荡；政府也有两个策略：救济或不救济。政府帮助流浪汉的前提是后者必须试图寻找工作；否则，前者不予帮助；而流浪汉只有在得不到救济时才会寻找工作。下表给出了对策的赢得双矩阵：,因此，在这个对策问题中，没有一个纯局势可以构成纯策略下的纳什均衡。为求得纳什均衡，必须对矩阵加以扩充,38,设A,B分别为局中人1和2的赢得矩阵，且皆为mn矩阵，局中人1，2的混合策略集为：,如果一个混合策略组合（X*,Y*）同时满足,则称策略组合局势（X*,Y*）是一个混合策略纳什均衡。,39,对于上述例题，假定政府以概率x选择救济，以概率1-x选择不救济，即政府的混合策略为(x,1-x)，流浪汉以概率y选择寻找工作，以概率1-y选择游荡，即流浪汉的混合策略为(y,1-y)。那么政府的期望赢得函数为：,用微分求极值的方法：,这就是说，在混合策略中，流浪汉在对付给定政府的混合策略下，最优策略是以1/5的概率选择寻找工作，4/5的概率选择游荡，即Y*=(1/5,4/5),40,同样流浪汉的期望赢得函数为：,用微分极值法求：,即在混合策略均衡中，政府在对付给定流浪汉的混合策略下，最优策略是X*=(1/2,1/2)。由于纳什均衡要求每个局中人的混合策略是在给定对方的混合策略下的最优选择，因此，由x*=(1/2,1/2)和Y*=(1/5,4/5)构成的(x*,Y*)是唯一的纳什均衡。且此时赢得函数值为：EA(X,Y)=-1/5,EB(X,Y)=3/2,41,第六章图与网络分析(graphandnetworkanalysis),一、图与网络分析的实例,例1.哥尼斯堡七桥问题18世纪的哥尼斯堡城中有一条普雷格尔河,河的两岸和河中的两个小岛有7座桥彼此相接,当地的居民热衷于讨论这样一个话题:一个步行者能否通过每座桥一次且仅一次回到原出发地.,C岛,化为如上的简图,1736年数学家欧拉证明了这个问题是不可能的,42,例2公路连接问题某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市.假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？,例3旅行商问题/货郎（担）问题(TSP-TravelingSalesmanProblem)一名推销员准备前往若干城市推销产品.如何为他(她)设计一条最短的旅行路线(从驻地出发，经过每个城市恰好一次，最后返回驻地)？这一问题的研究历史十分悠久，通常称之为旅行商问题.,43,例4稳定婚配问题(StableMarriageProblem)假设有n个男人和n个女人,每人都希望从n个异性中选择一位自己的配偶.假设每人都对n个异性根据自己的偏好进行了排序,以此作为选择配偶的基础.当给定一种婚配方案(即给每人指定一个配偶)后,如果存在一个男人和一个女人不是互为配偶,但该男人喜欢该女人胜过其配偶,且该女人喜欢该男人也胜过其配偶,则该婚配方案称为不稳定的.安排稳定的婚配方案的问题称为稳定婚配问题。,44,二.图与网络分析基本内容框架,45,1.图与网络的基本概念,一、图及其分类,本章研究的图与平面几何中的图不同，我们只关心图中有多少个点，点与点之间有无线连接，至于连线的方式是直线还是曲线，点与点的相对位置如何，都是无关紧要的。下面介绍有关图的基本概念。1.图，图是点和线所组成的图形，即图是一个有序二元组(V,E)，记为G=(V,E)，其中V=v1,v2,vp是p个点的集合，E=e1,e2,eq是q条边的集合。V中的元素vi称为顶点，E中的元素ek称为边。如图1所示：其中,图1,V=v1,v2,v3,v4,E=e1,e2,e3,e4,e5,e6e1=v1,v1,e2=v1,v2,e3=v2,v3e4=v2,v3,e5=v3,v4,e6=v1,v3,46,对于边(vi,vj)，则称vi,vj两点相邻，也称vi,vj为边(vi,vj)的端点。若两条边有一个公共端点u，则称这两边是相邻的，也称这两边为点u的关联边。若两端之间多于一条边的，称为多重边。如图1中的e3、e4。若一条边的两个端点相同，则称此为环（自回路）。如图1中的e1。2.简单图与多重图.不含环和多重边的图称为简单图，含有多重边的图称为多重图。上图就是一个多重图。3.无向图与有向图.G=(V,E)中，若所有的边均有ek=(vi,vj)=(vj,vi),k=1,2,q，则称G为无向图，记为G=(V,E)。若图中边(vi,vj)的端点是有序的，即表示以vi为始点vj为终点。则称该图为有向图，记为D=(V,A)。在有向图中，把边称为弧。因此，A表示G中弧的集合。,47,4.赋权图.在实际问题中，只用图来描述所研究对象之间的关系往往是不够的。与图联系在一起，通常还有与点或边有关的某些数量指标，通常称之为“权”。图G中,如果每条边(弧)(vi,vj)都被赋予一个权数wij,则称G为赋权图.权可以表示为：距离、费用、通过能力（数量）等。与无向图和有向图相对应，赋权图可分为无向赋权图和有向赋权图，分别记为G=(V,E,W)和D=(V,A,W)。二、连通图1.链。在无向图G=(V,E)，称一个点和边交替的序列vi1,ei1,vi2,ei2,vit-1,vit为连接vi1和vit的一条链。简记为vi1,vi2,vit。其中eik=(vik,vik+1),k=1,2,t-1。点边序列中只有重复的点而无重复边者称为简单链。点边序列中没有重复的点和重复边者称为初等链。,48,如图3中：S1=v6,v5,v1,v5,v4,v3是一条连结v6和v3简单链。S2=v6,v5,v1,v4,v3是一条条连结v6和v3的初等链。首尾相接的链称为圈。2.路。在有向图D=(V,A)中，称链vi1,vi2,vit为一条从vi1到vit的路。若vi1=vit，则称之为回路。在图4中S1=v6,v5,v1,v5,v4,v3是一条从v6和v3的路。S2=v1,v2,v4,v5,v1是一条回路。,49,3.连通图。如果一个图中任意两点间至少有一条链相连，则称此图为连通图。如图5、图6任何一个连通图都可以分为若干个连通子图，每个连通子图称为由原图的分图。图5中的(b)就是(a)的三个分图。,50,三、图的矩阵表示,用矩阵表示图对于研究图的性质及应用常常是较方便的。图的矩阵表示方法有多种，这里介绍其中两种常用矩阵。1.权矩阵。网络G=(V,E,W)，其边(vi,vj)的权重为Wij，构造矩阵A=(aij)nxn，其中,称矩阵A为网络G的权矩阵。其中主对角线上的元素aij均为零。如图6的权矩阵为,51,2.邻接矩阵。对于图G=(V,E)构造一个矩阵A=(aij)nxn，其中,则称矩阵A为图G的邻接矩阵。当G为无向图时,邻接矩阵为对称的。,如图7的邻接矩阵为,52,给出了一个图的邻接矩阵就等于给出了图的全部信息，可以从邻接矩阵中得到图的很多重要性质。如（1）A=(aij)中第i行中的1的数目等于vi点的出次d+(vi)，第j列中1的数目等于vi点的入次d-(vi)。（2）路径问题。如果图7是路径图，则由邻接矩阵就可算出G中任一点与其它点之间是否有路可通？若有路，走几步可以达到该点？下面通过邻接矩阵的计算来求解v1v5和v1v6有无路可能。先求A2,53,由于a16(3)=1，表明从v1三步可达v6，若要了解这条路沿途经过哪些顶点到达v6，只要回溯前面计算过程中的a16(3)这个数是怎样产生的，就可知道。因为a16(3)是由A2中的第一行与A中的第六列相应各数乘加而得，即是由a15(2)=1和a56=1相乘而得。同理a15(2)=1是由a13=1与a35=1相乘而得。因此有v1v3v5v6。,54,2.树与最小树,一、树及其性质,连通且不含圈的无向图称为树，记为T(V,E)。设图T=(V,E)，顶点数为P，边数为q，则以下关于树的说法是等价的。1.T是一棵树；2.T无圈，且q=p1；3.T连通，且q=p1；4.T无圈，但每加一新边即得唯一的一个圈；5.T连通，但每舍去一边就不连通；6.T中任意两点，有唯一链相连。,55,二、图的生成树,若图G的生成子图是一棵树，则称该树为G的生成树。,图8中(b)就是(a)的生成树。图G=(V,E)有生成树的充要条件是G为连通图。,56,三、最小树问题,在给定连通赋权无向图G=(V,E,W)中，求G的生成树T=(V,E)，使E各边权Wij(0)的总和最小的问题称为最小树问题。其数学模型为：,其中T*称为最小树。许多网络问题都可归结为最小树问题，如设计长度最小的公路网把若干城市联通；设计用料最省的电话线网把有关单位联系起来。,57,求最小树有以下两种方法：（1）用“避圈法”(Kruskal算法)求最小树。其基本思想是：开始选一条权最小的边，以后每步从未选的边中选取一条权最小的边，使它与已选边不构成圈，直至选够q1条边止。（2）用“破圈法”(管梅谷算法)求最小树。其方法步骤是：1先从图G任取一个圈，并从圈中去掉一条权最大的边。若在同一圈中有几条都是权最大边，则任选其中一边去掉。2在余下的子圈中，重复上述步骤，直至没有圈止。例,v2,v1,v5,v4,v3,2,2,3,4,4,5,4,6,v3,v2,v1,v5,v4,2,2,3,4,58,3.最短路问题,最短路问题是网络理论中应用最广泛的问题之一，许多优化问题可以使用这个模型，如管道铺设，设备更新，线路安排等。在第四章我们曾介绍了最短路问题的动态规划解法，但某些最短路的问题构造动态规划基本方程较困难，而图论方法则直观有效。给定D=(V,A,W)，其中wijW，表示弧(vi,vj)的权（可以是费用、时间、距离等）。设vs和vt是D中任意两顶点，求一条路，使它是从vs到vt的所有路中总权最小的路。其数学模型为：,59,一、Wij0情况下，求最短路的Dijkstra标号法,1.该法的基本思想是基于以下原理：若序列vs,vi1,vik,vt是从vs到vt的最短路，则序列vs,vi1,vik必为从vs到vik的最短路。2.Dijkstra标号法的基本思想是采用两种标号：T标号与P标号，T标号为临时性标号(TemporaryLabel)，P标号为永久性标号(PermanentLabel)。从vs开始，逐步向外探寻最短路。给vi点P标号时，表示从vs到vi点的最短路权，vi的标号不再改变。给vi点T标号时，表示从vs到vi点的最短路权上界的估计。凡没有得到P标号的点都有T标号。标号法每一步都是把某一T标号点改为P标号，当终点vt得到P标号时，计算全部结束。如果点vj不能由T标号变为P标号，则说明vs到vj不存在路。,60,3.步骤：(1)给vs以P标号，P(vs)=0，其余各点给T标号，且T(vi)=+。(2)若vi点为刚得到P标号的点，考虑T标号点vj,(vi,vj)A。对vj的T标号进行如下的更改：,T(vj)=minT(vj),P(vi)+wij(4.1)(3)比较所有具有T标号点，把最小者改为P标号，即P(vjo)=minT(vj)vj为T标号若全部点均为P标号。则停止。否则以vjo代vi，返回(2),61,例，用Dijkstra标号法求下图由v1到各顶点的最短路。,解：标号过程如图10中(a)(e)，其中方框表示P标号，里面的数字表示从v1到该点的最短路长。圆圈表示T标号，其中的数字表示从v1到该点最短路长的上界。,62,63,（图10）,此时仍有T标号点v5不能改为P标号，说明不存在从v1到v5的路，所以计算终止。图(e)中各方框的数字表示从v1到各点的最短路长。D氏标号法只适用于全部权为非负情况。如果网络中含有负权的弧，则算法失效，应改用其它算法。,64,二、求网络中任意两点意最短路的Floyd算法,对求网络中任意两点间的最短路，当然可用改变起始点的办法，采用D氏标号法达到目的，但显然较繁。Floyd算法却可直接求出网络中任意两点间的最短路，且wij的正负不受限制。Floyd方法的具体步骤如下：开始(k=0)，作距离矩阵L(o)=(Lij(o)和序号矩阵(o)=(ij(o)其中,第一步：k=r(1rp)时，L(k)中第k行和第k列元素保持不变，其它元素按下式计算，并填入L(k)=(Lij(k)中：,65,相应地，(k)的各元素按下式变化：,(4.3),第二步：若存在Lii0(1ip)，计算终止，即说明D中存在一条含有顶点vi的负回路Q，(即dii=W(Q)0的回路)，并由ij(k)(i,j=1,2,p)，找出此回路。否则，置k=k+1。第三步：当k=p，计算终止。若Lij(p)=+，则说明D中不存在从vi到vj的路；否则，记dij=Lij(p)，表示由vi到vj的最短路长，相应的最短路可由ij(p)(i,j=1,2,p)找出。,66,例用Floyd方法求图11中各顶点间的最短路，其中弧（边）旁的数字表示弧（边）长。,解：k=0，把图11中的两条边看作长度相等，方向相反的两条弧。即有14=41=9，25=52=2。根据图11中的数据，作L(o)=(Lij(o)同时作(0)=(ij(o)，如表中k=0所示。k=1，将L(1)中第1行和第1列的元素保持不变（在表中用虚线将其覆盖），其它元素按(4.2)式进行计算，例如,67,L42(1)=minL42(o),L41(o)+L12(o)=min,9+3=12L43(1)=minL43(o),L41(o)+L13(o)=min,9+4=13其余元素经计算不变。对更新数字的元素均加上圆圈。同时，在k=1的序数矩阵中，按(4.3)式有42(1)=41(o)=1，43(o)=41(o)=1，并加上圆圈。如表中k=1所示。k=2，将L(2)的第2行和第2列的元素保持不变，按(4.2)式计算：L13(2)=minL13(1),L12(1)+L23(1)=min4,3+(-4)=-1L15(2)=minL15(1),L12(1)+L25(1)=min,3+2=5L43(2)=minL43(1),L42(1)+L23(1)=min13,12+(-4)=8L53(2)=minL53(1),L52(1)+L23(1)=min,2+(-4)=-2其余元素未变，并对L13(2)，L15(2)，L43(2)，L53(2)加圈。,同时在(2)中,按(4.3)式有13(2)=12(1)=2,15(2)=12(1),43(2)=42(1)=1,53=52(1)=2，并加圈。如表中k=2所示。k=3,4,5的结果均在表中给出，过程从略。,68,L(5)=(Lij(5)给出了图11中各点之间的最短路长，(5)=(ij(5)给出了从vi到vj的最短路必须经过点的下标，并由此可找出最短路。例如从v1到v5的最短路长为1(L15(5)=1),最短路由15(5)=2（即必经过v2），又由25(5)=3（即经过v3），再由35(5)=4（即必经过v4），最后由45(5)=5,可知从v1到v5的最短路是(v1,v2,v3,v4,v5)。同样，从v5到v1的最短路长为10，最短路为(v5,v2,v3,v4,v1)。,69,例用Flogd方法求图12中各顶点之间的最短路，其中各弧旁的数据表示弧长。,V1。V2。V4。V3。,-2,1,-2,2,-2,-2,-6,6,（图12）,解：k=0，由6.18中的数据作L(o)=lij(o)和(o)=ij(o),按(6.5)式计算及按(6.6)式得表6-2(k=0,1,2)如下：,70,由于L44(2)=-30，说明图12中含有顶点v4的负回路Q，由ij(2)中的44(2)=1,14(2)=2,24(2)=4可知，负回路Q=v4,v1,v2,v4，d44=L44(2)=-3，计算终止。否则，继续计算下去，则会出现更多的负回路，且随着计算次数增多，含有负回路P的长dij-。因此，本题不存在从vi到vj的最短路(i,j=1,2,3,4)。,71,4.最大流问题,最大流问题是一类极为广泛的问题。不仅在交通运输网络中有人流、车流、货物流、供水网络中有水流、金融系统中有现金流、通讯网络中信息流等。五十年代，Ford(福特)、Fulkerson(富克逊)建立的“网络流理论”，是网络应用的重要组成部分。,一、网络与流的概念,对于有向图D=(V,A)，如果V中有一发点vs（亦称源还有一收点（亦称为汇）记为vt，其余均为中间点，且对A中的每条弧均有权W(vi,vj)0（简记为Wij，并称为弧容量），则称这样的赋权有向图D为容量网络，记为D=(V,A,W)。通过D中弧(vi,vj)的物流量fij，称为弧(vi,vj)的流量。所有弧上流量的集合f=fij称为该网络D的一个流。,72,在图13中，弧旁括号中的两个数字(Wij,fij)，第1个数字表示弧容量，第二个数字表示通过该弧的流量。弧(vs,v1)上的(8,6)，前者是弧容量，表示可通过该弧最大流量的能力为8，后者是目前通过该弧的实际流量为6。,从图13中可见：（1）通过每弧的流量均不超过弧容量（2）发点vs流出的总量为6+3=9,等于流入收点vt的总量5+4=9；（3）各中间点的流出量等于其流入量。各中间点v2的流出量减去其流入量等于0,即4(3+1)=0,73,一般地，在容量网络D=(V,A,W)中，满足以下条件的流f，称为可行流：（1）弧流量限制条件0fijcij(vi,vj)A（2）平衡条件,式中v(f)为该可行流的流量，即发点的净输出量，或收点的净输入量。对于网络的流，可行流总是在存在的。如f=0。,74,二、最大流问题,最大流问题就是在容量网络D中，求一个可行流f=fij，使其流量v(f)达到最大。其数学模型为,显然，最大流问题是个特殊的LP问题可用单纯形法或表上作业法求解，但利用它与图的紧密关系，能更为直观简便地求解。,75,三、求网络最大流的有关概念与原理,1.增广链。设D=(V,A,C)中，有一可行流f=fij，按每条弧上流量的多少，可将弧分四种类型：饱和弧(即fij=wij)非饱和弧(即fij0)如图13中，(v1,v4)是饱和弧，又是非零流弧，其它各弧均为非饱和弧，也是非零流弧。设是D中从vs别vt的一条链，沿此方向，链上各弧可分为两类：正向弧（与链的方向一致的弧），其集合记为+反向弧（与链的方向相反的弧），其集合记为-如图13，在=v1,v2,v3,v4,vt中，+=(vs,v2),(v1,v4),(v3,vt),-=(v2,v1),(v4,v3),76,3.最大流最小截量定理：任一网络D中，最大流的流量=最小截集的截量。,77,四、求最大流的方法(Ford-Fulkerson标号法),从以上概念及定理可知，要判断可行流f是否最大流有两种途径：1）能否找出可行流f的增广链，若能，则f不是最大流，否则f是最大流。2）V(f)是否等于最小截量，若等，则f是最大流，否则f不是最大流。1.标号法的基本思想：从可行流f出发，由Vs开始，用对D中的每个顶点进行标号的办法找f的增广链。若无，则f为所求的最大流。否则，在增广链上进行调整。调整量：,调整方法：,78,79,80,例用FordFulkerson标号法求下图的最大流,调整后为：,81,5.最小费用最大流问题（详见书）,82,6.网络计划方法,网络计划方法又称统筹法。网络计划方法最为有代表性的是关键路线法(CPM)和计划评审法(PERT).关键路线法是用网络图反映某项工程(任务)各道工序所需时间以及它们之间的衔接关系,通过计算各工序有关的时间参数和完成工程(任务)所需的最少时间,从而确定关键工序的关键路线,并在此基础上通过网络分析方法制定出时间、成本和资源优化的网络计划方案.它主要应用于有历史资料和有以往类似项目经验的工程上.计划评审法同样是应用了网络计划与网络分析方法,但注重于对工程(任务)安排的评价与审查,主要应用于对研究与开发的新项目.,83,一.关键路线法关键路线法的基本步骤是:(1)根据工序的紧前紧后关系绘制网络图.(2)计算每个结点的最早开工时间和最迟开工时间.(3)确定关键路线.(4)对网络计划进行优化.,84,绘制网络图应遵守的原则1.工序从左向右排列,结点按时序编号,并沿箭头方向越来越大.2.两结点之间只能有一条箭线.3.网络图中不能有缺口和回路.4.利用交叉作业缩短工期.5.网络图中只能有一个始点和一个终点.6.对绘制的网络图要进行整理,去掉多余的虚工序;尽量避免出现交叉箭线,对于不可避免的,可在交叉处用弓形表示;最后按工序时间前后,工艺流程和组织管理的需要,重新调整图中结点的序号.,85,例某工程的各道工序与所需时间及它们之间的相互关系如下表所示，试绘制该工程的网络图。,86,图6.24,6.4.2计算时间参数、确定关键路线,绘制工程计划网络图后，接着就是算出完成该项工程最少所需要的时间，确定网络图的关键路线。为此，必须尽量准确地估算出工程各道工序时间，确定工程从开始到结束总的可利用时间，这样才能使工程管理者心中有数，抓住工程中的主要矛盾，在有限的资源情况下，统筹安排好时间、劳力、资金等，以保证工程的按期或提前完成。下面通过对图的6.24的分析加以说明（箭线旁的数字表示完成工序的时间）,87,在网络图中，从始点到终点共有8条不同的路线，各条路线所需的时间如表6.5所示。其中第5条路线所需的时间最长。如果这条路线上的3道工序均分别能在5天完成，则整个工程就可在15天完成。否则工程的工期就要被延误。因此，第5条路线中各工序能否按期完工成为整个工程的关键。把网络图中所需时间最长的路线称为关键路线，亦称主要矛盾线.其他称为非关键路线.关键路线上的工序称为关键工序；否则，称为非关键工序关键路线用粗黑线表示在一项工程的网络图中，关键路线可以不唯一关键路线的确定对于工程管理具有非常重要的意义，它是编制网络计划的中心对各关键工序优先安排人力、物力，挖掘潜力，采取有效措施，压缩所需工序时间而对非关键工序，只要在不影响工程完工的前提下，可适当延长完成时间，抽出部分人力、物力，支援关键工序，以达到工程工期的目的,88,表6.5,89,关键路线和非关键路线是相对的，可变的关键路线的确定取决于每道工序所需时间计算的准确程度，确定结点为i，j（ij）间的工序时间（记为tij）有两种方法：一是对于具有劳动定额资料的，或是具有类似工序的工时统计资料的，可用分析对比的方法确定。二是对于不具有劳动定额资料和类似工序工时统计资料的，可用“三点估计法”算工序时间。既先分别估算三种时间；在正常情况下完成工序的最保守时间，记为m；在顺利情况下完成工序的最乐观时间，记为a；在不利情况下完成工序的最保守时间，记为b。由这三种时间推算出工序时间tij的方法就是“三点估计法”。显然，由于m,a,b的不确定性，因而由他们推算出的tij是一个随机变量。据经验，可以认为近似地服从正态分布。,90,一般地，工作时间方差为假设各工序时间相互独立，且同分布。由于工程完工时间等于个关键工序时间之和，所以，可以认为工程时间是服从，以为均值，以为方差的正态分布。,91,若给定工程完工时间为，为求出的概率，可按下列计算(6.11)求出U后（UN（0，1），直接查正态分布表即可。反之，若要按指定概率求出工程完工时间，可反查正态分布表，先求出U，在由（6.11）式求出。例14已知某工程的关键路线由四道工序组成,并根据估计每道工序的最乐观时间a、最保守时间b和最可能时间m，按（6.7）（6.8）式计算出相应的工序时间及其方差，如表6.6所示，试求该工程的完工时间及规定完工时间为21天的概率。表6.6,92,解由表6.6，该工程完工时间为均方差为现在已知规定完工时间=21（天），按（6.11）式计算查正态分布表得P（U）=0.68即规定完工时间为21天的概率为0.68。如果要求工程提前1天完工，(既Tk=19天)则U=查正态分布表的P（U）=0.32既完工时间为19天的概率为0.32这说明工程要求提前1天完工的可能性不大。如果要求工程完工时间的概率，则可反查正态分布表得因此，工程完工时间为同时，利用（6.11）式和上述同样的方法，也可以求出每道工序能否在规定的时间内完工的概率，以及要求在完成工序时间的概率下，求出工序所需时间,93,确定关键路线常见的方法有图算法和表算法，它们都是通过有关参数的计算进行的。现分述如下：,1.图算法图算法是一种在网络图上通过对结点最早开工时间和结点最迟开工时间的计算，从而确定关键路线的方法。,结点最早时间TE(j)某结点j可能最早开工时间简称结点最早时间，记为TE(j)，它等于从工程开始到结点j最长路线的各工序时间之和。所以，从始点开始，自左向右逐个推算即可得到所以结点最早时间。如果同时有几条箭线指向结点j时，则取这些箭线的箭尾事项各结点最早时间与工序时间之和的最大值，即,94,其中，TE=(6)=15就是完成工程最少所需的时间，既工程总工期。,图6.24中各结点最早时间的计算如下：,95,结点最迟时间TE(j)某结点j最迟必须完成时间，简称结点最迟时间，记为TL(j)，它等于工程的计划完工时间（即TE(n)）减去某一结点j到终点n的最长间隔时间。所以，从终点开始，自右向左逐个推算即可得到所有结点的最迟时间。如果结点j同是几条箭线的箭尾事项，则结点j最迟时间应是这些箭线的箭头事项各结点最迟时间与工序时间之差的最小值，即,图6.24中各结点最迟时间的计算如下：,96,以下图为例确定关键路线,第三步.结点最早开工时间与最迟开工时间相同所确定的工序为关键工序.由关键工序组成的路线即为关键路线.,97,（2）表算法,表算法是一种在表上通过对各工序的有关时间参数的计算，从而确定关键路线的方法。工序最早开工时间tES(i,j)紧前工序最早完工时间即为紧后工序最早可能开工时间，简称工序最早开工时间，记为tES(i,j).它等于结点i的最早时间.如果有多道紧前工序，则取这些紧前工序最早开工时间与工序时间之和的最大值。即,工序最早完工时间tEF(i,j)从工序最早可能开工时间起到完成该工序任务所需要的可能时间，简称工序最早完工时间，记为tEF(i,j).它等于工序最早开工时间与该工序时间之和.即,（6.15）,98,工序最迟开工时间tLS(i,j)在不影响工程最早完工时间条件下，工序最迟必须开工的时间，简称工序最迟开工时间，记为tLS(i,j).它等于紧后工序最迟开工时间与该工序时间之和，如果紧后工序有多道时，则取其差的最小值，即,工序最迟完开工时间tLF(i,j)从工序最迟开工时间起到完成该工序任务所需的时间，简称工序最迟完工时间，记为tLF(i,j).它等于工序最迟开工时间与工序时间之和，即,99,工序总机动时间R(i,j)不影响工程最早完工时间的条件下，工序最早开工（完工）时间可以推迟的时间，简称工序总机动时间（亦称工序总时差）