结构模型与技术.ppt

如果不借助模型下列问题很难解决：如果不借助模型下列问题很难解决：（（1）不可重复的过程（地震，山崩，导弹发射，回采冒顶））不可重复的过程（地震，山崩，导弹发射，回采冒顶）（（2）可以重复但是造价太高或时间太长（发射装置，桥梁流变））可以重复但是造价太高或时间太长（发射装置，桥梁流变）1.1 模型定义：模型定义： 模型是对实体的特征及其变化规律的一种表征或者抽象，而且往往是对实模型是对实体的特征及其变化规律的一种表征或者抽象，而且往往是对实体中那些所要研究的特定的特征的抽象具体见体中那些所要研究的特定的特征的抽象具体见P58 注意两点：一是特定特征；二是为什么只对特定特征进行抽象？注意两点：一是特定特征；二是为什么只对特定特征进行抽象？ 分类：（表达方式）分类：（表达方式） 模模型型实体模型实体模型抽象模型抽象模型实物模型实物模型模拟模型模拟模型数学模型数学模型物理、化学、美术物理、化学、美术结构模型结构模型城市规划、城市规划、作战沙盘、作战沙盘、采矿模型等采矿模型等地图、电路地图、电路图、建筑图图、建筑图等等1.2 现实世界与模型（实物与模型） P59图4-1表达了数学建模的过程，其实也是通用的建模过程。

1.3 建模原则和步骤建模原则和步骤原则：既要准确反映实物，有易于研究和解决问题即：（1）现实性；（2）简洁性；（3）适应性；（4）强壮性步骤：2.1引言引言七桥问题七桥问题2、图及网络方法图的基本概念图的矩阵表示法应用特例应用特例应用特例应用特例北京天津济南青岛郑州徐州连云港武汉南京上海图1 1城市交通图VBVCVDVAVE图2-5球队比赛赛图图1是我国北京，上海等10个城市之间铁路交通图，反映了这十个城市间的铁路分布情况这里用点代表城市，连线代表铁路诸如此类的还有线分布图，煤气（油）管道图等例2，A，B，C，D，E五球队比赛情况：A与其他队都比过一次，E和D比赛过，C和B，D比赛过可用V1，V2，V3，V4，V5级之间连线表示这些情况（图2）2. 2 基础知识基础知识V4e3e2e1e5e7e8e6e4V3V2V1V5（1）图：节点+边（弧）V3（2）无向图：V4V2V1（3）有向图：V5（4）节点数和边数：图G=（V，E），节点个数P（G），边Q（G），（5）端点和关联边：若ei=[Vi，Vj]∈E，则称Vi，Vj是边ei的端点，边ei是顶点Vi和Vj的关联边（6）相邻点和相郊边：同一条边的两端点成为相邻点；有公共端点的两条边称为相邻边。

7）多重边和环：具有相同端点的边；两个端点落在一个顶点的边8）多重图和简单图：含有多重边的图；无环，无多重边的图9）次：以Vi为端点的边的条数为定点Vi的次d（Vi）（10）悬挂点和悬挂边：次为1的顶点；与悬挂点相连的边11）孤立点：次为零的节点12）奇点与偶点：次为奇数的点；次数为偶数的点（13）圈：若链M中Vi1=Vir，即始点与终点重合，则称此链为圈14）连通图和不连通图：一个图G的任意两个顶点，若至少有一条通路将其连接起来，则这个图G为连通图，否则为不连通图15）支撑子图：给定一个图G=（V，E），若图G′=（V’,E’），使V=V’及E’属于E，则称G’是G的一个支撑子图16）赋权图：设G=（V，E），对任意一条边e∈E，若相应都有一个数值W（e），则称G为赋权图，W（e）称为边e的权17）赋权有向图：D=（V，A），a∈A，都由W（e）（权距离，费用，时间等）在实际工作中，很多问题的可行方案都可通过一个赋权有向图表示，（若物资运输线路的安排，装卸设备的更新，排水管道的铺设等所以赋权图被广泛应用于解决工程技术及科学管理领域的最优化问题18）网络：通常，我们称赋权图为网络，赋权有向图为有向网络，赋权无向图为无向网络。

V3V5V4V2V6V1V3V5V4V2V6V1图5ab2.3 树、最小支撑树树、最小支撑树在各式各样的图中，有一类图极其简单而却是很有用的例： 一支由五个城市，要在其之间架线，要求任两个城市都可以互相通话（允许通过其他城市），并且线根数最少解：用V1，…，V5五个点代表五个城市，若在某两城市之间架设线，则在相应的两个点之间连一条边，这样一个网就可以用一个图来表示为使任两个城市之间都可以通话，这样的图必须是连通的，其次，若图中有圈的话，从圈上任意去掉一条边，余下的图仍是连通的，这样可省去一根线因而要求得到满足的网所对应的图必定是不含圈的连通图树可满足这一要求）V1V4V2V3V5五城市网 例：例： 某厂组织机构，用树表示某厂组织机构，用树表示  树：一个无圈的连通图称为树，通常以树：一个无圈的连通图称为树，通常以T表示从定义推出性质：表示从定义推出性质：（（1）具有）具有n个顶点的树，其边数恰好为个顶点的树，其边数恰好为n-1条2）树的任意两顶点之间有且仅有一条链树的任意两顶点之间有且仅有一条链3）在树）在树T中去掉任一条边，则中去掉任一条边，则T成为不连通图。

成为不连通图4）在树）在树T中不相邻的两个顶点间添上一条边，则恰好得到一个圈中不相邻的两个顶点间添上一条边，则恰好得到一个圈进一步地说，若再从这个圈上任意去掉一条边，则可得到一个树进一步地说，若再从这个圈上任意去掉一条边，则可得到一个树5）图的支撑树：设图）图的支撑树：设图T=（（V，，E）是图）是图G=（（V，，E）的支撑子图，若）的支撑子图，若图图T=（（V，，E’）是一个树，则称）是一个树，则称T是是G的一个支撑树如图的一个支撑树如图5-b是图是图5-a的一个支撑树的一个支撑树V3V5V4V2V6V1V3V5V4V2V6V1图5ab由此可得出两种寻求连通图的支撑树的方法1）破图法：在图G中任取一个圈，从圈中去掉一边，对余下的图中重复这个步骤，直到不含圈时为止，即得到一个支撑树例：图5-a图5-b.（2）避圈法：在图中任取一条边e1，找一条与e1不构成圈的e2，再找一条与{e1，e2}不构成圈的边e3，一般，设已有{e1，e2，…，ek}，找一条与{e1，e2，…，ek}中任何一些边不构成圈的边ek+1，重复这个过程，直到不能进行为止这时，由所取出的边构成的图是一个支撑树43222233315a666783143322b 最小支撑树问题最小支撑树问题 设有一个连通图G=（V，E），每一边e=（Vi，Vj）有一个非负权W（e）=（Wij≥0）。

若T=（V，E′）是G的一个支撑树，称E'中所有边的权之和为支撑树T的权，记为W（T），即W（T）=∑Wij若存在一个支撑树T* 使得W（T*）在所有的支撑树中权最小，则 称T* 是G的最小支撑树 不同地点间网架设，管线，道路铺设，旅游路线安排均可用“求最小支撑树”解决最小支撑树求法：最小支撑树求法：（1）破圈法：在连通图G中，从圈中去掉一条权最大的边在余下的图重复这一步骤，直到不含圈为止，即为最小支撑树2）避圈法：在连通图G中，开始选一条最小权的边，以后每步中，总从未被选取的边中选一权最小的边，并使之与已选取的边不构成圈重复，直到不存在与已选边不构成圈的边为止 Example 1道路网V3V5V4V2V1543427156权重有向图权重有向图1、邻接矩阵、邻接矩阵 图的基本的矩阵表示，它用来描述图中各节点两两之间的关系图的基本的矩阵表示，它用来描述图中各节点两两之间的关系如图所示的有向图可以用邻接矩阵表示如图所示的有向图可以用邻接矩阵表示S2S5S3S6S1S4S1S2S3S4S5S6 行为零的元素对应的点为汇入点；行为零的元素对应的点为汇入点； 列为零的元素对应的点为源点。

列为零的元素对应的点为源点 比如多个点之间的距离问题即为一个邻接矩阵，只是该图是一个比如多个点之间的距离问题即为一个邻接矩阵，只是该图是一个无向图，其邻接矩阵和有向图的邻接矩阵相比不同无向图，其邻接矩阵和有向图的邻接矩阵相比不同S=V2V4V6V1V3V568427231132、能源需求模型、能源需求模型 每一有向线段标出的数字代表起始节点变化单位值对于相邻节点每一有向线段标出的数字代表起始节点变化单位值对于相邻节点的影响，的影响，1和和3节点之间的权重节点之间的权重2.6表示能源供给量增加表示能源供给量增加1单位则用户数单位则用户数增加增加2.6单位1和和2节点之间的节点之间的 权重为权重为-1.8表示能源供给量增加表示能源供给量增加1单位单位价格将下降价格将下降1.8单位1234-1.8-0.45.82.60.71.23、人口转移模型、人口转移模型 （（1））用权重有向图还可以描述一类概率模型，如人口由一个地用权重有向图还可以描述一类概率模型，如人口由一个地方向另一个地方流动的概率而这类以权重为概率的有向图，其邻方向另一个地方流动的概率而这类以权重为概率的有向图，其邻接矩阵称为传递概率。

接矩阵称为传递概率 1/61/81/41/21/41/101/161/41/44/102/101/161/33/83/101/23/41/8 （（2）马尔可夫链）马尔可夫链 具有传递概率的即其记忆跨度只有一步的随机过程，是一种由多具有传递概率的即其记忆跨度只有一步的随机过程，是一种由多步距组成的链，相应发生的状态称之为马尔可夫链步距组成的链，相应发生的状态称之为马尔可夫链4、莱氏人口模型、莱氏人口模型 用以预测各年龄组的人口，如今后用以预测各年龄组的人口，如今后10年内对不同职业人口的预年内对不同职业人口的预测掌握内容1 1、掌握模型的概念掌握模型的概念模型是对实体的特征及其变化规律的一种表征或者抽象，而且往往是对实体中那些所要研究的特定的特征的抽象2 2、现实与模型转换．、现实与模型转换．本章小结3 3、建模的原则建模的原则准确反映实物，有易于研究和解决问题4 4、灵活运用最小支撑树灵活运用最小支撑树。