数学建模离散模型培训.pptx

《数学建模离散模型培训.pptx》由会员分享，可在线阅读，更多相关《数学建模离散模型培训.pptx（94页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、参考书数学模型 姜启源 谢金星等著 高等教育出版社任何数学建模方面的书计算机语言方面的书(matlab,mathematica,lindogo）第1页/共94页数学建模的历史1988.6叶其孝教授在美国讲学期间向美国大学生数学建模竞赛发起者和负责人Fusaro教授了解这项竞赛的情况，商讨中国学生参赛的办法和规则。1989.2.2426我国大学生（北京大学、清华大学、北京理工大学共4个队）首次参加美国大学生数学建模竞赛，自此每年我国都有同学参加这项竞赛。1989.3高校应用数学学报第4卷第1期发表叶其孝教授的文章“美国大学生数学建模竞赛及一些想法”，第一次向国内介绍这项竞赛。1990.6.227

2、.1美国Fusaro教授访问北京和上海，作了有关美国大学生数学建模竞赛的报告，并与叶其孝、姜启源等讨论数学建模竞赛的组织工作。第2页/共94页1990.12.79上海市举办大学生（数学类）数学模型竞赛，这是我国省、市级首次举办数学建模竞赛。1991.8.2022第三届全国数学建模教学及应用会议在湖南张家界举行，对举办全国性竞赛起了组织作用。（第一、二届会议分别于1986、1988年举行。）1991.11.2324中国工业与应用数学学会第一届第三次常务理事会决定成立数学模型专业委员会，俞文？为主任，姜启源、叶其孝、谭永基为副主任，并责成他们组织1992年部分城市大学生数学模型联赛。这个委员会实际

3、上成为我国大学生数学建模竞赛的主要组织者。1992.11.27291992年部分城市大学生数学模型联赛举行，这是全国性的首届竞赛，10省（市）79所院校的314队参加。第3页/共94页模型模型:为了一定目的，对客观事物的一部分为了一定目的，对客观事物的一部分进行简缩、抽象、提炼出来的进行简缩、抽象、提炼出来的原型原型的替代物的替代物.集中反映了原型中人们需要的那一部分特征集中反映了原型中人们需要的那一部分特征什么是什么是数学模型数学模型数学模型定义:对于一个现实对象，为了一个特定目的，根据其内在规律，作出必要的简化假设，运用适当的数学工具，得到的一个数学结构。数学建模:建立数学模型的全过程（包

4、括表述、求解、解释、检验等）第4页/共94页 数学建模的基本方法数学建模的基本方法机理分析机理分析测试分析测试分析根据对客观事物特性的认识，找出反映内部机理的数量规律将对象看作“黑箱”,通过对量测数据的统计分析，找出与数据拟合最好的模型机理分析没有统一的方法，主要通过实例研究机理分析没有统一的方法，主要通过实例研究 (CaseStudies)来学习。以下建模主要指机理分析。来学习。以下建模主要指机理分析。二者结合二者结合用机理分析建立模型结构,用测试分析确定模型参数 数学建模的方法和步骤数学建模的方法和步骤 数学建模的重要意义数学建模的重要意义 数学建模的具体应用数学建模的具体应用第5页/共9

5、4页 数学建模的一般步骤数学建模的一般步骤模型准备模型假设模型构成模型求解模型分析模型检验模型应用模型准备了解实际背景了解实际背景明确建模目的明确建模目的搜集有关信息搜集有关信息掌握对象特征掌握对象特征形成一个形成一个比较清晰比较清晰的的问题问题第6页/共94页模型假设针对问题特点和建模目的针对问题特点和建模目的作出合理的、简化的假设作出合理的、简化的假设在合理与简化之间作出折中在合理与简化之间作出折中模型构成用数学的语言、符号描述问题用数学的语言、符号描述问题发挥想像力发挥想像力使用类比法使用类比法尽量采用简单的数学工具尽量采用简单的数学工具 数学建模的一般步骤数学建模的一般步骤第7页/共9

6、4页模型求解各种数学方法、软件和计算机技术如结果的误差分析、统计分析、模型对数据的稳定性分析模型分析模型检验与实际现象、数据比较，检验模型的合理性、适用性模型应用 数学建模的一般步骤数学建模的一般步骤第8页/共94页数学建模的全过程数学建模的全过程现实对象的信息数学模型现实对象的解答数学模型的解答表述表述求解求解解释解释验证验证(归纳)(演绎)现现实实世世界界数数学学世世界界表述表述求解求解解释解释验证验证根据建模目的和信息将实际问题“翻译”成数学问题选择适当的数学方法求得数学模型的解答将数学语言表述的解答“翻译”回实际对象用现实对象的信息检验得到的解答实践理论实践第9页/共94页模型的逼真性

7、和可行性模型的渐进性模型的强健性模型的可转移性模型的非预制性模型的条理性模型的技艺性模型的局限性数学模型的特点数学模型的特点第10页/共94页数学建模能力的培养数学建模能力的培养数学建模与其说是一门技术，不如说是一门艺术数学建模与其说是一门技术，不如说是一门艺术技术大致有章可循艺术无法归纳成普遍适用的准则想像力洞察力判断力 学习、分析、评价、改进别人作过的模型学习、分析、评价、改进别人作过的模型 亲自动手，认真作几个实际题目亲自动手，认真作几个实际题目 *也是一种创新能力的培养也是一种创新能力的培养 第11页/共94页 *没有没有创新创新，就没有，就没有发展发展，创新促进人类，创新促进人类社会

8、的进步社会的进步.*正处于传统的继承性教育向创新性教育正处于传统的继承性教育向创新性教育转变的时期转变的时期.重要的科学思维方式之一是创新思维，重要的科学思维方式之一是创新思维，创新思维是创新能力的核心与灵魂创新思维是创新能力的核心与灵魂.创新能力的培养创新能力的培养 第12页/共94页图与网络模型数学建模中的图论方法1.图论的起源 图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736 年发表的“哥尼斯堡的七座桥”。1847年，克希霍夫为了给出电网络方程而引进了“树”的概念。1857年，凯莱在计数烷的同分异构物时，也发现了“树”。哈密尔顿于1859年提出“周游世界”游戏，用图论的术语，

9、就是如何找出一个连通图中的生成圈，近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、生物遗传学、心理学、经济学、社会学等学科中。第13页/共94页 图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联

10、结起来问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。第14页/共94页 当然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。欧拉为了解决这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有四个“点”，七条“线”的“图”。问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。最短路问题、最大流

11、问题、最小费用流问题和匹配问题等都是图与网络的基本问题第15页/共94页2.问题（通过一些例子来了解图解决的问题）问题一：最短路问题（SPPshortest path problem）一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。问题二：公路连接问题某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那

12、么应如何决定在哪些城市间修建高速公路，使得总成本最小？第16页/共94页问题三：指派问题（assignment problem）一家公司经理准备安排名员工去完成项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大？问题四：中国邮递员问题（CPPchinese postman problem）一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？由于这一问题是我国管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题。第17页/共94页问题五：

13、旅行商问题（TSPtraveling salesman problem）一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商问题。问题六：运输问题（transportation problem）某种原材料有个产地，现在需要将原材料从产地运往个使用这些原材料的工厂。假定个产地的产量和家工厂的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低？第18页/共94页上述问题有两个共同的特点：一是它们的目的都是从若干可能的安排或方案中寻求某种意义下

14、的最优安排或方案，数学上把这种问题称为最优化或优化（optimization）问题；二是它们都易于用图形的形式直观地描述和表达，数学上把这种与图相关的结构称为网络（network）。与图和网络相关的最优化问题就是网络最优化或称网络优化（netwok optimization）问题。所以上面例子中介绍的问题都是网络优化问题。由于多数网络优化问题是以网络上的流（flow）为研究的对象，因此网络优化又常常被称为网络流（network flows）或网络流规划等。第19页/共94页 3.图论的基本概念 图定义：图是由顶点集合(vertex)(vertex)及顶点间的关系集合组成的一种数据结构：Grap

15、hGraph(V V,E E)其中 V V=x x|x x 某个数据对象 是顶点的有穷非空集合；E E=(=(x x,y y)|)|x x,y y V V 或 E E=y|x x,y y V V&PathPath(x x,y y)是顶点之间关系的有穷集合，也叫做边(edge)(edge)集合。PathPath (x x,y y)表示从 x x 到 y y 的一条单向通路,它是有方向的。有向图与无向图：在有向图中，顶点对是有序的。在无向图中，顶点对(x,y)(x,y)是无序的。完全图：若有 n n 个顶点的无向图有 n(n-1)/2 n(n-1)/2 条边,则此第20页/共94页图为完全无向图。

16、有 n 个顶点的有向图有n(n-1)条边,则此图为完全有向图。邻接顶点：如果(u,v)是 E(G)中的一条边，则称 u 与 v 互为邻接顶点。若ek,el至少有一个公共端点,则称ek,el 是彼此相邻的,简称相邻的 权：某些图的边具有与它相关的数,称之为权。这种带权图叫做网络。顶点的度：一个顶点v v的度是与它相关联的边的条数。记作T TD D(v v)。在有向图中,顶点的度等于该顶点的入度与出度之和。第21页/共94页 顶点 v v 的入度：以 v v 为终点的有向边的条数,记作 I ID D(v v););顶点 v v 的出度：以 v v 为始点的有向边的条数,记作 O OD D(v v)

17、。度为奇数的顶点个数为偶数.路径：在图 G G(V V,E E)中,若从顶点 v vi i 出发,沿一些边经过一些顶点 v vp p1 1,v vp p2 2,v vpmpm，到达顶点v vj j。则称顶点序列 (v vi i v vp p1 1 v vp p2 2.v vpm pm v vj j)为从顶点v vi i 到顶点 v vj j 的路径。它经过的边(v vi i,v vp p1 1)、(v vp p1 1,v vp p2 2)、.、(v vpmpm,v vj j)应是属于E E 的边。第22页/共94页路径长度：非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边

18、的权之和。简单路径：若路径上各顶点 v v1 1,v v2 2,.,.,v vm m 均不互相重复,则称这样的路径为简单路径。回路：若路径上第一个顶点 v v1 1 与最后一个顶点v vm m 重合,则称这样的路径为回路或环。连通图与连通分量：在无向图中,若从顶点v v1 1到顶点v v2 2有路径,则称顶点v v1 1与v v2 2是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。非连通图的极大连通子图叫做连通分量。第23页/共94页强连通图与强连通分量：在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子

19、图叫做强连通分量。第24页/共94页关联：设ek(vi,vj)为无向图G中的一条边,称vi,vj为ek的端点,ek与vi(或vj)是彼此关联的.无边关联的顶点称为孤立点.若一条边所关联的两个顶点重合,则称此边为环.第25页/共94页ek与vi(或vj)的关联次数1vivj,2vi vj,0vi(vj)不是ek的端点bavV第26页/共94页关联矩阵对无向图G，其关联矩阵M=(mij)ve，其中：对有向图G，其关联矩阵M=(mij)ve，其中：第27页/共94页邻接矩阵 (Adjacency Matrix)(Adjacency Matrix)图的邻接矩阵就是表示各个顶点之间关系的一个矩阵。设图

20、A=(V,E)A=(V,E)是一个有 n n 个顶点的图，则图的邻接矩阵定义为：无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。在有向图中,统计第 i i 行 1 1 的个数可得顶点 i i 的出度，统计第 j j 行 1 1 的个数可得顶点 j j 的入度。在无向图中,统计第 i i 行(列)1)1 的个数可得顶点i i 的度。对于网络图（带权图）：第28页/共94页第29页/共94页树的定义：连通而不含回路的无向图称为无向树,简称树,常用T表示树.连通分支数大于等于2,且每个连通分支均是树的非连通无向图称为森林.平凡图称为平凡树.设T是无向图G的子图并且为树，则称T为G的树.若T

21、是G的树且为生成子图，则称T是G的生成树.第30页/共94页最小生成树最小生成树使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。按照生成树的定义，n n 个顶点的连通网络的生成树有n n 个顶点、n-n-1 1 条边。构造最小生成树的准则必须只使用该网络中的边来构造最小生成树；必须使用且仅使用 n n-1-1 条边来联结网络中的 n n 个顶点；不能使用产生回路的边。生成最小树的方法有克鲁斯卡尔算法和普里姆算生成最小树的方法有克鲁斯卡尔算法和普里姆算法法 第31页/共94页普里姆普里姆普里姆普里姆(Prim)(Prim)算法算法算法算法 普里姆算法的基本

22、思想：普里姆算法的基本思想：普里姆算法的基本思想：普里姆算法的基本思想：从连通网络从连通网络从连通网络从连通网络 NN=V V,E E 中的某一顶点中的某一顶点中的某一顶点中的某一顶点 u u0 0 出发，出发，出发，出发，选择与它关联的具有最小权值的边选择与它关联的具有最小权值的边选择与它关联的具有最小权值的边选择与它关联的具有最小权值的边(u u0 0,v v)，将其顶点加，将其顶点加，将其顶点加，将其顶点加入到入到入到入到生成树的顶点集合生成树的顶点集合生成树的顶点集合生成树的顶点集合UU中。中。中。中。以后每一步从以后每一步从以后每一步从以后每一步从一个顶点在一个顶点在一个顶点在一个顶

23、点在UU中中中中，而，而，而，而另一个顶点不在另一个顶点不在另一个顶点不在另一个顶点不在UU中中中中的各条边中选择的各条边中选择的各条边中选择的各条边中选择权值最小的边权值最小的边权值最小的边权值最小的边(u u,v v),把它的顶点加入把它的顶点加入把它的顶点加入把它的顶点加入到到到到集合集合集合集合UU中。如此继续下去，直到网络中的所有顶点都加中。如此继续下去，直到网络中的所有顶点都加中。如此继续下去，直到网络中的所有顶点都加中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合入到生成树顶点集合入到生成树顶点集合入到生成树顶点集合UU中为止。中为止。中为止。中为止。采用邻接矩阵作为

24、图的存储表示。采用邻接矩阵作为图的存储表示。采用邻接矩阵作为图的存储表示。采用邻接矩阵作为图的存储表示。第32页/共94页用普里姆算法构造最小生成树的过程用普里姆算法构造最小生成树的过程第33页/共94页prim算法如下：，while end第34页/共94页用prim算法求右图的最小生成树。我们用的第一、二、三行分别表示生成树边的起点、终点、权集合。Matlab程序如下：clc;clear;M=1000;a(1,2)=50;a(1,3)=60;a(2,4)=65;a(2,5)=40;a(3,4)=52;a(3,7)=45;a(4,5)=50;a(4,6)=30;a(4,7)=42;第35页/

25、共94页a(5,6)=70;a=a;zeros(2,7);a=a+a;a(find(a=0)=M;result=;p=1;tb=2:length(a);while length(result)=length(a)-1 temp=a(p,tb);temp=temp(:);d=min(temp);jb,kb=find(a(p,tb)=d);j=p(jb(1);k=tb(kb(1);result=result,j;k;d;p=p,k;tb(find(tb=k)=;endresult第36页/共94页结果result=125447254673504050304245第37页/共94页克鲁斯卡尔算法的基

26、本思想：克鲁斯卡尔算法的基本思想：设有一个有设有一个有 n n n n 个顶点的连通网络个顶点的连通网络 N N N N=V V V V,E E E E,最初先构造一个只有最初先构造一个只有 n n n n 个顶点，没有边的非连通图个顶点，没有边的非连通图 T T T T =V V V V,图中每个顶点自成一个连通分量。图中每个顶点自成一个连通分量。当在当在 E E E E 中选到一条具有最小权值的边时中选到一条具有最小权值的边时,若该边的两个若该边的两个顶点落在不同的连通分量上，则将此边加入到顶点落在不同的连通分量上，则将此边加入到 T T T T 中；否中；否则将此边舍去，重新选择一条权值

27、最小的边。如此重复则将此边舍去，重新选择一条权值最小的边。如此重复下去，直到所有顶点在同一个连通分量上为止。下去，直到所有顶点在同一个连通分量上为止。第38页/共94页克鲁斯卡尔克鲁斯卡尔（Kruskal）算法如下:(1)选使得(2)若已选好，则从中选取，使得(3)直到选得为止。中无圈，且第39页/共94页生成上例中的最小生成树Matlab程序如下：clc;clear;M=1000;a(1,2)=50;a(1,3)=60;a(2,4)=65;a(2,5)=40;a(3,4)=52;a(3,7)=45;a(4,5)=50;a(4,6)=30;a(4,7)=42;a(5,6)=70;i,j=fin

28、d(a=0)&(a=M);第40页/共94页b=a(find(a=0)&(a=M);data=i;j;b;index=data(1:2,:);loop=max(size(a)-1;result=;whilelength(result)v2index(find(index=v1)=v2;elseindex(find(index=v2)=v1;enddata(:,flag)=;index(:,flag)=;endresult第42页/共94页结果result=424314657725304042455050第43页/共94页2 最短路径问题及其算法 最短路径问题：最短路径问题：最短路径问题：最短路

29、径问题：如果从图中某一顶点如果从图中某一顶点如果从图中某一顶点如果从图中某一顶点(称为源点称为源点称为源点称为源点)到达另到达另到达另到达另一顶点一顶点一顶点一顶点(称为终点称为终点称为终点称为终点)的路径可能不止一条，如何找到一条的路径可能不止一条，如何找到一条的路径可能不止一条，如何找到一条的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。路径使得沿此路径上各边上的权值总和达到最小。路径使得沿此路径上各边上的权值总和达到最小。路径使得沿此路径上各边上的权值总和达到最小。问题解法问题解法问题解法问题解法 边上权值非负情形的单源最短路径问题边上权值非负情形的单源最短路

30、径问题边上权值非负情形的单源最短路径问题边上权值非负情形的单源最短路径问题 DijkstraDijkstra算法算法算法算法 边上权值为任意值的单源最短路径问题边上权值为任意值的单源最短路径问题边上权值为任意值的单源最短路径问题边上权值为任意值的单源最短路径问题 Bellman Bellman和和和和FordFord算法算法算法算法 所有顶点之间的最短路径所有顶点之间的最短路径所有顶点之间的最短路径所有顶点之间的最短路径 Floyd Floyd算法算法算法算法第44页/共94页边上权值非负情形的单源最短路径问边上权值非负情形的单源最短路径问题题固定起点的最短路最短路有一个重要而明显的性质：最短

31、路是一条路径，且最短路的任一段也是最短路假设在u0v0的最短路中只取条，则从u0到其余顶点的最短路将构成棵以u0为根的树。因此可采用树生长的过程来求制定顶点到其余顶点的最短路径.实现这一过程的方法是Dijkstra算法设G为赋权有向图或无向图，G边上的权均非负Dijkstra算法：求G中从顶点u0到其余顶点的最短路S：具有永久标号的顶点集对每个顶点，定义两个标记(l(v)，z(v)，其中：l(v)：表示从顶点u0到v的一条路的权z(v)：v的父亲点，用以确定最短路的路线第45页/共94页算法的过程就是在每一步改进这两个标记，使最终l(v)为从顶点u0到v的最短路的权，输人为带权邻接矩阵w(u,

32、v)Dijkstra算法步骤matlab程序dijkstra.m第46页/共94页第47页/共94页第48页/共94页第49页/共94页第50页/共94页matlab程序floyd.mRoad.m第51页/共94页第52页/共94页第53页/共94页1可划为最短路径问题的多阶段决策问题多阶段决策问题常用动态规划方法处理：原问题原问题阶段阶段1阶段阶段2阶段阶段n状态转移方程状态转移方程无论过去的状态和决策如何,对前面的决策所形成的的状态而言,余下的决策必须构成最优解.求解顺序求解顺序状态决策第54页/共94页动态规划方法的特点动态规划方法的特点构造动态递推关系式关系式构造具有艺术性递推关系式解

33、法因问题而异图的最短路问题是典型的多阶段决策问题，且具有成型Dijkstra算法求解探索将多阶段决策问题转化为适当的图，在转化为最短路问题，可将问题清晰、直观，解法统一。第55页/共94页例例设备更新问题设备更新问题（设备更新问题）企业使用一台设备，每年年初，企业领导就要确定是购置新的，还是继续使用旧的。若购置新设备，就要支付一定的购置费用；若继续使用，则需支付一定的维修费用。现要制定一个五年之内的设备更新计划，使得五年内总的支付费用最少。设备在每年年初的价格为：第1年第2年第3年第4年第5年1111121213使用年限使用年限01 12233445维修费维修费5681118使用不同时间设备所

34、需维修费为 ：第56页/共94页模型分析设备在每年年初的价格为：第1年第2年第3年第4年第5年1111121213使用年限使用年限01 12233445维修费维修费5681118使用不同时间设备所需维修费为 ：模型建立与求解G1(V,E)的含义为：（1）顶点集每个顶点代表年初的一种决策，其中顶点代表第i年初购置新设备的决策，顶点 代表第i年初修理用过k年的旧设备的决策.（2）弧集第57页/共94页（3）构造加权有向图G1(V,E)Matlab程序minroad.m第58页/共94页（4）问题转化为顶点到顶点的最短路问题五年的最优购置费为：其中 为顶点 到 的最短路的权。求得最短路的权为5353

35、，而两条最短路分别为：因此，计划为第一、三年初购置新设备，或第一、四年初购置新设备，五年费用均最剩，为5353。第59页/共94页l=Columns 1 through 14 Inf 11 16 22 30 11 22 16 28 27 22 34 33 33 Columns 15 through 20 30 43 39 39 41 41z=Columns 1 through 14 1 1 6 8 11 1 2 6 3 7 8 4 9 10 Columns 15 through 20 11 5 12 13 14 15第60页/共94页另一类图的构造策略此问题也可构造如图所示的加权有向图 顶点集

36、 表示第 年初购置新设备的决策，表示第五年底.带权有向边集 权 表示由这一决策在第 年初到第 年初的总费用，如 弧（，）表示第 年初购置一台设备一直使用到第 年初的决策。问题转化为求 到 的最短路问题，求得两条最短路为 权为5353，与图 的解相同。Matlab程序minroad1.m第61页/共94页l=Inf 11 16 22 30 39z=1 1 1 1 1 3第62页/共94页 Euler图定义 经过G的每条边的迹叫做G的Euler迹；闭的Euler迹叫做Euler回路或回路；含Euler回路的图叫做Euler图。直观地讲，Euler图就是从一顶点出发每边恰通过一次能回到出发点的那种图

37、，即不重复地行遍所有的边再回到出发点。定理 （i）G是Euler图的充分必要条件是G连通且每顶点皆偶次。（ii）G是Euler图的充分必要条件是G连通且 是圈。（iii）G中有Euler迹的充要条件是G连通且至多有两个奇次点。第63页/共94页Euler回路的Fleury算法1921年，Fleury给出下面的求Euler回路的算法。Fleury算法：1o.，令 。2o.假设迹 已经选定，那么按下述方法从 中 选取边 ：（i）和 相关联；（ii）除非没有别的边可选择，否则 不是 的割边(cut edge)。(所谓割边是一条删除后使连通图不再连通的边)。3o.当第2步不能再执行时，算法停止。第64

38、页/共94页返回第65页/共94页匹配与覆盖设图G=(V,E),M E,若M的边互不相邻，则称M是G的一个匹配.一般用来处理工作安排问题.若图G的每条边都至少有一个端点在顶点集V的一个子集K之中，则K称为G的覆盖（Covering）。一个图可以有很多覆盖。一般来解决消防设施安置问题，化学物品存放问题等.比如：监狱看守问题一座监狱的几间牢室有道路相连，不妨设其示意图为图为右图，第66页/共94页 表示牢室，表示道路，监狱看守要设在通过道路能直接监视所有牢室的地方，如果看守不得走动，那么他们应呆在某些牢室（即路口）所在地。问至少需要几名看守才能完成监视任务呢？第67页/共94页设图：顶点集：边集：

39、关联矩阵（n为顶点数，m为边数），其中即仅当以为顶点的邻边是时的关联矩阵为第68页/共94页邻接矩阵，其中即使当与之间有边相连时的邻接矩阵为第69页/共94页如()，()，()，()，(都是图所示的G的覆盖。含顶点个数最少的覆盖称为最小覆盖。最小覆盖也不是唯一的。)因为关联矩阵表示的是顶点与边之间的关系，所以关联矩阵与覆盖密切相关。下面的结论显然成立。顶点集V的子集K是图G的一个覆盖，当且仅当G的关联矩阵R中K的各顶点所对应的行内，每列至少存在一个元素1。第70页/共94页从关联矩阵可以找出一个最小覆盖，下面仅以右式为例说明其步骤：1.在右式中取恰有两个1的那一列中1所在的行，如行，令，划去行

40、及行中所在的列，得2.在（5）中取恰有两个1的那一列中1所在的行，如行，令划取行及行中元素所在的列，得第71页/共94页3.因为划去行，过程结束，最小覆盖综上可知，最小覆盖的概念解决了这一问题。在每间牢室设一看守是多余的，在各设一看守可同时监视。还可以把处的看守去掉，只留。当然，在或处设看守亦可。但是只在一处设看守是不行的。所以至少需要2名看守。第72页/共94页在每间牢室设一看守是多余的，在各设一看守可同时监视。还可以把处的看守去掉，只留。当然，在或处设看守亦可。但是只在一处设看守是不行的。所以至少需要2名看守。第73页/共94页作业最优截断切割问题从一个长方体中加工出一个已知尺寸、位置预定

41、的长方体（这两个长方体的对应表面是平行的）通常要经过6次截断切割.设水平切割单位面积的费用是垂直切割单位面积费用的r倍.且当先后两次垂直切割的平面（不管它们之间是否穿插水平切割）不平行时，因调整刀具需额外费用e，试设计一种安排各面加工次序（成“切割方式”）的方法，使加工费用最少。第74页/共94页2 效益的合理分配效益的合理分配例例甲乙丙三人合作经商，若甲乙合作获利甲乙丙三人合作经商，若甲乙合作获利7元，元，甲丙合作获利甲丙合作获利5元，乙丙合作获利元，乙丙合作获利4元，元，三人合作获利三人合作获利11元。又知每人单干获利元。又知每人单干获利1元。元。问三人合作时如何分配获利？问三人合作时如何

42、分配获利？记甲乙丙三人分配为记甲乙丙三人分配为解不唯一解不唯一(5，3，3)(4，4，3)(5，4，2)第75页/共94页(1)Shapley合作对策合作对策 I,v n人合作对策，人合作对策，v特征函数特征函数n人从人从v(I)得到的分配，满足得到的分配，满足v(s)子集子集s的获利的获利第76页/共94页公理化方法公理化方法 s 子集子集 s中的元素数目，中的元素数目，Si 包含包含i的所有子集的所有子集由由 s 决定的决定的“贡献贡献”的权重的权重 Shapley值值 i 对合作对合作s 的的“贡献贡献”Shapley合作对策合作对策第77页/共94页三人三人(I=1,2,3)经商中甲的

43、分配经商中甲的分配x1的计算的计算 1/3 1/6 1/6 1/31 1 2 1 3 I1 7 5 11 0 1 1 4 1 6 4 7 1/3 1 2/3 7/3x1=13/3类似可得类似可得 x2=23/6,x3=17/6 1 2 2 3第78页/共94页合作对策的应用合作对策的应用 例例1 污水处理费用的合理分污水处理费用的合理分担担20km38km河流河流三城镇地理位置示意图三城镇地理位置示意图123 污水处理，排入河流污水处理，排入河流三城镇可单独建处理厂，三城镇可单独建处理厂，或联合建厂或联合建厂(用管道将污水用管道将污水由上游城镇送往下游城镇由上游城镇送往下游城镇)Q1=5Q3=

44、5Q2=3Q污水量，污水量，L管道长度管道长度建厂费用建厂费用P1=73Q0.712管道费用管道费用P2=0.66Q0.51L第79页/共94页污水处理的污水处理的5 种方案种方案1）单独建厂）单独建厂总投资总投资2）1,2合作合作3）2,3合作合作4）1,3合作合作总投资总投资总投资总投资合作不会实现合作不会实现第80页/共94页5）三城合）三城合作总投资作总投资D5最小最小,应应 联联 合建厂合建厂 建厂费：建厂费：d1=73(5+3+5)0.712=453 12管道费：管道费：d2=0.66 50.51 20=30 23管道费：管道费：d3=0.66 (5+3)0.51 38=73D5城

45、城3建议：建议：d1 按按 5:3:5分担分担,d2,d3由城由城1,2担负担负城城2建议：建议：d3由城由城1,2按按 5:3分担分担,d2由城由城1担负担负 计算：计算：城城3分担分担d1 5/13=174C(3),城城2分担分担d1 3/13+d3 3/8=132C(1)不不同同意意D5如何分担？如何分担？第81页/共94页特征函数特征函数v(s)联联 合合(集集s)建厂比单独建厂节约的投资建厂比单独建厂节约的投资三三城从城从节约投资节约投资v(I)中得到的分配中得到的分配 Shapley合作对策合作对策第82页/共94页计算计算城城1从从节约投资中得到的分配节约投资中得到的分配x11

46、1 2 1 3 I 0 40 0 640 0 0 250 40 0 39 1 2 2 31/3 1/6 1/6 1/3 0 6.7 0 13 x1=19.7,城城1 C(1)-x1=210.4,城城2 C(2)-x2=127.8,城城3 C(3)-x3=217.8三城在总投资三城在总投资556中的分担中的分担x2=32.1,x3=12.2x2最大，如何解释？最大，如何解释？第83页/共94页优点：优点：公正、合理，有公理化基础。公正、合理，有公理化基础。如如n个单位治理污染个单位治理污染,通常知道第通常知道第i方单独治理的投资方单独治理的投资yi 和和n方共方共同治理的投资同治理的投资Y,及第

47、及第i方不参加时其余方不参加时其余n-1方的投资方的投资zi(i=1,2,n).确定共同治理时各方分担的费用。确定共同治理时各方分担的费用。其它其它v(s)均不知道均不知道,无法用无法用Shapley合作对策合作对策求解求解Shapley合作对策小结合作对策小结若定义特征函数为合作的获利若定义特征函数为合作的获利(节约的投资节约的投资)，则有，则有缺点：缺点：需要知道所有合作的获利，即要定义需要知道所有合作的获利，即要定义I=1,2,n的所有的所有子集子集(共共2n-1个个)的特征函数，实际上常做不到。的特征函数，实际上常做不到。第84页/共94页设只知道设只知道无无 i 参加时参加时n-1方

48、合作的获利方合作的获利全体合作的获利全体合作的获利求解合作对策的其他方法求解合作对策的其他方法例例.甲乙丙三人合作经商，若甲乙合作获利甲乙丙三人合作经商，若甲乙合作获利7元，元，甲丙合作获利甲丙合作获利5元，乙丙合作获利元，乙丙合作获利4元，三人元，三人合作获利合作获利11元。问三人合作时如何分配获利？元。问三人合作时如何分配获利？第85页/共94页（2）协商解）协商解11将剩余获利将剩余获利 平均分配平均分配 模模型型以以n-1方合作的获利为下限方合作的获利为下限求解求解 xi 的下限的下限第86页/共94页（3）Nash解解(均衡解）均衡解）为现状点（谈判时的威慑点）为现状点（谈判时的威慑

49、点）在此基础上在此基础上“均匀地均匀地”分配全体合作的获利分配全体合作的获利B模模型型平均分配获利平均分配获利B3）Nash解解 2）协商解）协商解第87页/共94页（4）最小距离解）最小距离解模模型型 第第i 方的边际效益方的边际效益若令若令4）最小距离解）最小距离解 2）协商解）协商解第88页/共94页（5）满意解）满意解di现状点现状点(最低点最低点)ei理想点理想点(最高点最高点)模模型型5）基于满意度的解）基于满意度的解 2）协商解）协商解第89页/共94页（6）Raiffi 解解与协商解与协商解x=(5,4,2)比较比较第90页/共94页求解合作对策的求解合作对策的6种方法（可分为

50、三类）种方法（可分为三类）Shapley合作对策合作对策A类类B类类协商解协商解Nash解解 最小距离解最小距离解满意解满意解di现状现状,ei理想理想B类类4种方法相同种方法相同第91页/共94页例：有一资方例：有一资方(甲甲)和二劳方和二劳方(乙乙,丙丙),仅当资方与至少仅当资方与至少一劳方合作时才获利一劳方合作时才获利10元，应如何分配该获利？元，应如何分配该获利？Raiffi解解C类类第92页/共94页B类：计算简单，便于理解，可用于各方实类：计算简单，便于理解，可用于各方实力相差不大的情况；一般来说它偏袒强者。力相差不大的情况；一般来说它偏袒强者。C类：类：考虑了分配的上下限，又吸取