图论模型(看一笔画).ppt

第九章 图论模型•在生产生活中，人们常常用图或网络来刻画、解释和处理某些实际问题,常见的如车辆流通图、电路网络图、赛事安排图和工程进度管理图等.这种表示方式不仅使实际问题变得直观、简洁、明了，而且也为实际问题的研究提供了一种有效的方法 .近几十年来，随着运筹学、信息论和计算机科学的发展，人们对图论和网络的研究也越来越广泛和深入，并且迅速地产生了一门新兴的数学分支—图论.在这一章里，我们将简略地介绍一些与此有关的实际问题以及解决这些问题的巧妙方法.9.1 一笔画问题•9.1.1 七桥问题 18世纪，东普鲁士的哥尼斯堡是一座景致迷人的城市，普勒格尔河横贯其境，并在这儿形成两条支流，把整座城市分割成4个区域（如图） ABCD哥尼斯堡哥尼斯堡七桥示意图七桥示意图河的两岸(C和D），河中的岛(A)和两条支流之间的半岛(B).当时有7座桥横跨普勒格尔河及其支流， 把河岸、半岛和河心岛连接起来.有趣的桥群和哥城4区域的的迷人景色吸引了众多的的游客.有人在游览时提出这样的问题：能否从某个地方出发，穿过所有的桥各一次后再回到出发点？很多人做了尝试，但没有一个人成功.是否存在成功的可能性呢？人们既拿不出成功的方案，又找不到否定的理由.后来这个令人困惑的问题被年轻的瑞士数学家欧拉（Leonhard Eular）知道了，他在1736年向圣彼得堡学院递交的一篇论文中巧妙的解决了这个问题. 他是怎么解决这个问题的呢？他首先把哥尼斯堡的4个区域分别用A,B,C,D表示， 7座桥表示成7条连接这4个点的线，于是哥尼斯堡七桥的情形就转化为下图的情形ABDC七桥七桥问题模拟图问题模拟图这个由4个点和7条连线（也叫边）组成.问题相应地变为：在上述模拟图中，从A,B,C,D中任何一点出 发，笔不离纸，但又不能重复任何一条边地画出模拟图，且起点与终点重合，这样的画法存在吗？这就是众所周知的“一笔画”问题. 接下来，欧拉研究了能够“一笔画”的图形所应具有的性质.他注意到，这类图中的点倘若不是“一笔画”的起点和终点，那它作为“一笔画”的“中途点”应该具有这样的特性：笔沿着某条边“进入”点后，必定要沿着另一条边“出去”.于是， “中途点”的边必定成对出现.也就是说，与“中途点”相连的边的条数必是偶数. 我们把与点v相连接的边的条数称为该点的度数， 记作d（v）.d（v）为偶数时，点v称为偶点，否则称为奇点.按欧拉的分析，能“一笔画”的图的“中途点”的度数为偶点，而奇点只能作为“一笔画”的起点或终点.当起点和终点重合时，该图不存在奇点.概括起来，就是这样一个结论：如果一个图形可以“一笔画”，那么其奇点个数必为0（起点和终点重合）或2（起点和终点不重合）.9.1.2 有关图的基本概念 为了便于说明，我们简要的介绍一下图的基本概念及其性质. 我们经常遇到这样一些问题，他们仅包含两方面的内容：一是一些“对象”（如七桥问题中的岛和河岸），二是这些对象之间的某种关系（如岛与岛、岛和河岸之间是否有桥连接，有几座桥连接）.为表示这些对象和它们之间的关系，可以在纸上画一些点，每一点代表一个对象，称这些点为顶点，如果两个对象之间有所讨论的关系，就在相应的两点之间连一条线，这些线称为边，这样有若干个点和若干条边就构成了一个图.由若干个不同的顶点与连接其中某些顶点的边所组成的图形称为图.通常用G来表示图.用V表示图中所有顶点的集合，用 E表示所有边的集合，并且记为G=(V,E).图G中顶点的个数|V|称为G的阶. 图的基本性质： 设G是n阶图，则G中n个顶点的度数之和等于边数的两倍.证明： 所有顶点的度数之和表示以每一顶点为端点的边的总数.由于一条边有两个端点，因此每条边在顶点的度数之和中都被记入两次，所以顶点的度之和应为边数的两倍.推论： 对于任意的图G，奇点的个数是偶数.在图G中，有一个不同的边组成的序列： e1, e2, …, em，如果其中边, ei=(vi-1，vi),i=1,2,3…m.则称这个序列是从v0到vm的链.如果一条链的始点v0和终点vm重合，则称这条链为圈.如果对于图G中的任意两个顶点u和v，都有一条从u到v的链，则称这样的图G是连通的，否则称G是不连通的. 经过图G的每条边的链，称为G的欧拉链.经过图G的每条边的圈称为G的欧拉圈.一个图若包含欧拉圈，则称这个图为欧拉图. 直观的讲，欧拉图就是从某一顶点出发而每边恰通过一次又能回到出发点的图.9.1.3 一笔画定理及其证明 在七桥问题的讨论中，我们得到了一个结论:如果一个图形可以“一笔画”，当且仅当其奇点个数必为0或2.那么我们自然会问，这个命题的逆命题成立吗？也就是说，当一个图形的奇点个数为0或2时，它可以“一笔画”吗？如果能画，是否有一种一般可行的画法？答案是肯定的.将原命题与其逆命题综合起来，就是我们所说的一笔画定理.•一笔画定理：图G是欧拉链（即可以一笔画）的充要条件是：G是连通的，并且奇点的个数为0或2.当且仅奇点个数等于0时，连通图G是一个圈.证明 必要性：如果图G是一条从v1到vn+1的链，那么每一个不同于v1及vn+1的顶点vi（i=2,3…你）都是偶顶点。

故G至多有两个奇点，即v1与vn+1若G是圈，则v1与vn+1也是偶定点.充分性：如果G是连同，且奇顶点的个数为0，那么G一定是一个圈.事实上，从G中任一顶点v0出发，经相邻的边e1进入 V1，因为d（v1）是偶数，由v1再经相邻的边e2可进入v2，如此继续下去，每条边仅取一次，经过若干步后必可回到v0，于是就得到一个圈u1：v0v1…v0. 如果u恰好是图G，则命题得证.否则在图G中去条u1后得子图G1，G1中每个顶点也都是偶顶点.因图G是连通的，所以在G1中必定存在一个和u1公共的顶点u，使得G1中存在一个从u出发到u 的圈u2.于是u1和u2合起仍是一个圈. 重复上述过程，因为G中总共只有有限条边，总有一个时候，得到的这些圈恰好是图G.所以G是欧拉图. 如果G连通，其奇顶点的个数为2，不妨设u和v是两个奇顶点.在u和v之间连一条边e得图G‘，于是G’中奇顶点的个数为0，故G‘是一个圈，从而去掉e后，G便是一条欧拉链.证毕.注： 在充分性的证明过程中，我们提供了”一笔画“的一种方法，即一笔画图形是由具有公共顶点的一个一个圈组合而成的，而且一个图能够”一笔画“的方法往往有很多种.9.1.4 一笔画定理的简单应用 回过头来看哥尼斯堡七桥问题。

有模拟图知：d（A）=d（B）=d（D）=3，d（C）=5.4个顶点都是奇点，所以模拟图不可能被一笔画成.也就是说，哥尼斯堡七桥问题中要找的那条道路是不存在的.9.1.5 评注在这个模型中，不需要考虑点线的长短大小，也不需要涉及量的计算，而只要研究点与点的关系就可以了.这种特殊的研究对象、研究方法和研究模型被公认为是图论学科的起源，现在以体现出它广泛的应用价值.9.2 中国邮递员问题 邮路问题：一个邮递员每次上班，要走遍他负责的每条路，然后回到邮局.问他应该怎么走才能使所走的路程最短？ 首先考虑这样一个问题：如图，每条线上的数字表示距离，小圆圈中的数字表示交叉路口的编号.我们从一点出发，有没有可能沿每条路都走过一遍（不许重复也不许遗漏），然后回到出发点呢？由于这一问题是我国管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题1234567易见，当图中只要有一个奇点时，就不可能那样走一遍了，因为对一个路口来说，有走进去的一条路，必有走出来的一 条路.反之也不难证明，当道路图上没有没有奇点时，便可以那样走一遍了.如果起点和终点可以不同，则允许有两个奇点.这就是上节讨论的“一笔画”问题.回到邮路问题，如果道路图上没有奇点，问题就已经解决了.如果有奇点，我们总可以通过在某一些路上再重复走一遍的办法来消灭奇点，这相当于在图上再添一些路. 在图中，， 是偶点， 是奇点，因此，在图上要再添一些路来消灭奇点.如果在 和 之间， 和 之间各添上一条路（即在2，3和5，6上走两次），奇点就没有了，于是就可以一笔画了.但我们还要求所走的路程最短，所以问题就归结为：如何选择要重复的路程，使之既能消灭奇点,又能使重复的路程最短？14723562356这个问题已经被我国数学家管梅谷解决了，所以邮路问题又称为中国邮递员问题.他证明了只要在每个圈上所走的重复路 程不超过整个圈长的一半，就可以得到路程最短的走法.例如在上图中，如果重复 和 ， 和 两条路，虽能消灭奇点，但在圈 上重复路程2+3=5已经超过整个圈长的一半(4.5)，所以它不是路程最短的走法.我们可以改为重复 - ， - ， - ，这样既消灭了奇点，又使得每个圈上的重复路程都不超过整个圈长的一半.于是就得到这样一个路程最短的走法： . 综上所述，得出解决邮路问题的基本步骤如下：首先把道路图上所有的奇点都找出来，然后选择一些需要重复的路，消灭奇点，再在每个圈上检查重复路程是否超过整个圈长之半，如有超过的情况，则在这个圈上，把原来不重复的路定为重复的路，而把原来重复的路定为不重复的路，这样逐步调整，当所有圈上的重复路程都不超过整个圈长之半时，就达到路程最短的要求了，最后将整个图形一笔画出.23562345622634451346575432621一般说来，一个图形所具有的圈数是很多的，是否每个圈都必须要检查？答案是否定的，如上图中共有6个圈，实际上 只要检查3个就够了.一般的，若一个图有s条路，n个顶点，则需要检查的圈数为s-n+1. 这里提出的问题，不只是邮递员会碰到，在其他一些场合也会碰到，如在马路上扫地、洒水的车子所走的路线.9.3 周游世界问题 人们在旅游时常常希望设计这样一条路线，能够不重复地经过所有想要游览的景点，而且路程最短.1859年，爱尔兰数学家哈密尔顿设计了一种叫做“周游世界”的游戏.游戏的玩具是一个正十二面体.如下图:哈密顿圈（环球旅行游戏）哈密顿圈（环球旅行游戏）在它的20个顶点上分别表有世界上20个著名的城市，每两个 顶点之间的棱表示这两个城市之间的可通行道路顶点之间的棱表示这两个城市之间的可通行道路.游戏的游戏的规则是：找出一条道路，使他从某个城市出发，经过所有规则是：找出一条道路，使他从某个城市出发，经过所有其他城市一次后返回原出发城市其他城市一次后返回原出发城市. 为方便起见，我们把这个十二面体投影到平面上保持原点、为方便起见，我们把这个十二面体投影到平面上保持原点、线之间的连接关系线之间的连接关系.能否在下图（能否在下图（2）中找出一条道路，使）中找出一条道路，使它从某个顶点出发，经过所有其他定点各一次后再回到出它从某个顶点出发，经过所有其他定点各一次后再回到出发点呢？发点呢？ 如果这条首尾相连的道路存在，我们把它叫做原图的一个如果这条首尾相连的道路存在，我们把它叫做原图的一个哈密尔顿圈，含有哈密尔顿圈的图称为哈密尔顿图哈密尔顿圈，含有哈密尔顿圈的图称为哈密尔顿图. 我们注意到，哥尼斯堡七桥问题的几何模型与哈密尔顿周游我们注意到，哥尼斯堡七桥问题的几何模型与哈密尔顿周游世界问题的几何模型有某些相似之处，即都是在图中寻找一世界问题的几何模型有某些相似之处，即都是在图中寻找一 条首尾相连的道路，都要求所走的路程最短条首尾相连的道路，都要求所走的路程最短.不同的是，前不同的是，前者所找的道路要经过所有的边恰好一次（每条边至少一遍）者所找的道路要经过所有的边恰好一次（每条边至少一遍），而后者则要求经过所有的顶点恰好一次（有的路可以不，而后者则要求经过所有的顶点恰好一次（有的路可以不走）走）. 解决哈密尔顿周游世界问题，可借助于解决哈密尔顿周游世界问题，可借助于“一笔画一笔画”的性质：的性质：如果图（如果图（2）中存在哈密尔顿圈，那么由于这个）中存在哈密尔顿圈，那么由于这个“圈圈”是是一个一个“一笔画一笔画”图形，其所经过的点必都是图形，其所经过的点必都是“圈圈”上度数上度数为为2的偶点，在图（的偶点，在图（2）中，这个）中，这个“圈圈”要经过要经过20个顶点，个顶点，而所有顶点的度数之和为边数的两倍，由此可知而所有顶点的度数之和为边数的两倍，由此可知“圈圈”上上的边数为的边数为20.已知正十二面体共有已知正十二面体共有30条边，于是问题转化条边，于是问题转化为：能否抹去为：能否抹去10条边，使图中（条边，使图中（2）中）中20个顶点的度数都个顶点的度数都变为变为2.这是可以做到的这是可以做到的.第10章 数学建模的常见方法10.1 数据建模法 在用数学模型解决实际问题时，如果能够利用物理、化邓自然科学的规律来建立数学模型，就把这种建模的方法称为机理分析法.但是在不少实际问题中，人们所掌握的仅仅是一些通过检测所得到的数据资料，根据这些数据建立尽量符合问题实际的数学模型，称为数据建模法. 这里所说的数据资料是指人们从实际问题中收集得到的事实观察值和测量值.它是数学模型与实际问题相联系的重要途径和手段.由于来自实际的数据资料有可能是不精确的，或者是不完善的，因此建模过程中处理好数据资料和模型的关系非常重要的. 在使用数据建模法时，有时所采集的数据资料对于建模与分析已经足够了，无需另外采集更多的数据；有时则不然，得从采集数据做起.收集有效数据并不是一件容易的事，一般得注意以下两点（1）收集数据应有明确的目标.（2）对于收集得来的数据应作适当的预处理.在建模过程中，数据资料的作用很大，主要体现在以下三个方面：（a）在建模过程中（特别是在建模的初期），当我们开始构架问题的模型时，数据资料能够对我们所构架模型给予了提示.有些模型（如经验模型）则是完全建立在数据资料的基础之上.（b）数据资料可以帮助我们对模型的参数给出估计.使用数据资料给出模型参数值的估计过程，我们称之为模型的参数估计. （c）数据资料还可以用于检验模型的效果，也就是检验由模型计算出来的理论数据是否合理地反映了实际的观测结果.如果有若干个模型描述同一个实际问题时，模型效果的检验可以帮助我们选择最优的模型. 本节主要讨论数据建模的两种情形，即由确定性数据建模和由随机性数据建模.10.1.1 从不同角度看待数据资料 解决问题最重要的往往并不是怎样将数据代入公式，而是要确定哪些数据、哪些因素对事件有影响.请看下面的例子.例1. 香港地区的中学数学教材中有这样一个题目：某企业有股东5人，工人100人，1990—1992年的3年间，该企业的收益情况如表所示，要求根据表中数据绘制一幅坐标图. 年份股东利润（万元）工资总额（万元）1990年1991年1992年 5 7.5 10 10 12.5 15 面对这样一组数据，不同的思维哦方法可以构建出不同的数学模型，描绘出不同的图形. 可以是两条平行线，传递出的信息是劳资双方共同发展，有福同享、有难同当。

这样的图形是老板最愿意看到的，我们姑且称它为“老板图” 也可以那全体股东利润增长的比例和全体工人工资增长的比例作比较，以1990年为起点（100），3年后，股东利润增长了100%，而工人工资只增长了50%.这幅图传递出来的信息是工人工资的增长比例是股东利润增长比例的一半，应该适当增加工人的工资，我们把它称为“工会图”.我们还可以那股东跟人收入的增长和工人个人收入的增长作比较，传递出来的信息则是股东和工人的收入差距十分悬殊，而且差距越来越大，这样的图可称为“工人图”. 华东师大的张奠宙教授拿这一题目请一位教师到中学做实验，让同学们根据数据汇出图来结果100%的学生绘制出第一个图形.在学生们看来，第一个图是最规范的思路，也是最标准的答案，他们根本没想过这一题目会具有多种答案，也没有想过一组数据中透露出来的生活中的实际信息，而只是想到把这一题目解出来就行了. 由此可见，面对不同的数据或条件、不同的需要、不同的构思，完全可能建立起不同的数学模型来，关键在于我们看待问题要多角度，思维力求发散.10.1.2 依据确定性数据的建模方法 在某种变化过程中，所涉及的变量之间存在某种确定性的函数关系，检测所得的数据资料仅仅是这种确定性的函数关系在量上的反映，我们把这种情况称为确定性现象. 既然此时变量之间存在确定性的函数关系，那么就需要我们通过对数据资料进行分析处理，来揭示其内在的函数关系，建立数学模型.一个简单的例子就是，圆的周长C与直径d之间的关系.不同的圆有不同的周长，人们通过大量的检测数据，揭示了这一本质关系，建立了函数模型 C= d 其中圆周率是一个常数3.141592653……例10-2 跳板承受力的问题10.1.3依据随机性数据的建模方法10.3 统筹法10.3.1 定义 一项工程由若干道工序组成，每道工序都需要一定的工期，各道工序之间存在一定的前后衔接关系，那么工程进度如何安排呢？ 解决这类问题的方法一般是统筹法，国外又叫做计划外评审方法. 又称网络计划法。

它是以网络图反映、表达计划安排，据以选择最优工作方案，组织协调和控制生产（项目）的进度（时间）和费用（成本），使其达到预定目标，获得更佳经济效益的一种优化决策方法10.3.2 背景1957年，美国化学公司Du Pont的M.R.Walker与Rand通用电子计算机公司的J.E.Kelly为了协调公司内部不同业务部门的工作，共同研究出关键路线方法（简记作CPM）.首 次把这一方法用于一家化工厂的筹建，结果筹建工程提前两个月完成.随后又把这一方法用于工厂的维修，结果使停工时间缩短了47个小时，当年就取得节约资金达百万元的要观效益　　1958年，美国海军武器规划局特别规划室研制含约3000项工作任务的北极星导弹潜艇计划，参与的厂商达11000多家.为了有条不紊地实施如此复杂的工作，特别规划室领导人W.Fazar积极支持与推广由专门小组创建的计划评审技术（简记作PERT）.结果研制计划提前两个完成，取得了极大的成功　　CPM在民用企业与PERT在军事工业中的显著成效，自然引起了普遍的重视.在很短的时间内，CPM与PERT就被应用于工业、农业、国防与科研等等复杂的计划管理工作中，随后又推广到世界各国.在应用推广CPM与PERT的过程中，又派生出多种各具特点，各有侧重的类似方法.但是万变不离其宗，各种有所不同的方法，其基本原理都源于CPM与PERT。

　CPM与PERT两种方法实质上大同小异，因此，人们把• CPM与PERT及其他类似方法统称为网络计划技术，简称为网络技术或网络方法，简记为统筹法网络计划技术最适用于大规模工程项目，工程愈大，非但人们的经验难以胜任，就是用以往的某些管理方法（例如反映进度与产量的线条图等方法）来进行计划控制也愈加困难.相反地在项目繁多复杂的情况下，网络计划是可以大显身手•　　1962年，我国科学家钱学森首先将网络计划技术引进国内1963年，在研究国防科研系统SI屯子计算机的过程中，采用了网络计划技术，使研制任务提前完成.计算机的性能稳定可靠，随后，经过我国数学家华罗庚对网络计划技术的大力推广，终于使这一科学的管理技术在中国生根发芽，开花结果，鉴于这类方法共同具有“统筹兼顾、合理安排”的特点，我们又把它们称为统筹法，网络图也称统筹图，本节主要讲述统筹法的基本思想•现在通过对下例的分析，来了解统筹法的基本思想项目工期（天）代号设计锻模10A制造锻模 15 B生产锻模10 C制造木模25 D生产铸件15 E设计工装 20 F 制造工装 40 G作出该部件的生产计划流程图并加以分析，再提出使完工期缩短的 改进措施。

•分析 本例可称为“生产过程的优化问题”，衡量的数量指标是“完成工程的时间”越短越好.鉴于工厂生产的实际情况，可知明细表中所列各项目的先后顺序关系不允许更动，也中可能对任一项目进行分解.例如，依照工艺过程，必须先制造木模，才能去生产铸件，这样就可得到下图所示的生产计划流程的一个方案 从上图中可见，A、D、F三个项目同时开工，随后分成三条支路.先考察上、中、下三条支路上各项目总共所费的时间，具体地说，有　　上支路 10＋15＋10＝35　　中支部 25＋15＝40　　下支部 20＋40＝60　　比较之，可见F与G两个项目合成的下支部所花时间最长该部件生产计划的完工期实质上受F与G两个项目工时的制约 　　设想一下，即使A、B、C、D、E都如期完工，但是由于F、G还在进行中，先完工的人员与设备如不及时利用只能闲置起来，造成所谓“窝工”现象，这就是生产力浪费，要是有可能重新调配力量，适当地让A、B、C、D或D、E慢点完工，同时力求F、G快点完工，那么就可能缩短工程的完工期.于是可以采取如下措施：把上支部或中 支部上的资源（人员、设备等）适当抽调一部发到下支路上去，以加快完工期.当然，这里已设被抽调的资源适用于下支部上的项目。

例如，设计锻模（A）的人也要会设计工装（F）从而可以去支援F此外，从某项目上被抽调的资源数量必须适当，抽调过多，原项目的完工时间将大为延长，反过来又会影响完工期 因此，时间最长的那条支路对于完工期起着关键的作用，所以被称为关键路线　　可见统筹法基本思想，简单地说就是：向关键路线要时间，向非关键路线要资源，以达到预期目标的最优　　统筹法主要由互相关联的三部分内容组成：　　1、统筹图概念及绘图规划；　　2、统筹图各参数的计算法； 3、统筹图的调整与优化由柳洪平创建•统筹法的基本步骤如下：•第一： 确定工序，估计工时，弄情歌工序之间的结合及顺序关系（工序本身的基本关系）；•第二：绘制工序流程图；•第三： 计算各条工序线路的工期数，•第四： 通过比较，选出主要矛盾线及若干条次要矛盾线.盯住主要矛盾线，按流线图安排施工并时刻收集各工序进展情况，通过信息反馈调整流线图.有条不紊的指挥整个工程.例 想泡壶茶喝当时的情况是：开水没有；水壶要洗，茶壶茶杯要洗；火生了，茶叶也有了各项工作要用的时间(单位：分钟)如下：A洗水壶1;B烧开水15；C洗茶壶1；D洗茶杯1，E拿茶叶2；F泡开茶1/3.问各项工作怎么安排才能尽快喝到茶？最快多长时间？  办法甲： 洗好水壶，灌上凉水，放在火上；在等待水开的时间里，洗茶壶、洗茶杯、拿茶叶；等水开了，泡茶喝。

办法乙： 先做好一些准备工作，洗水壶，洗茶壶茶杯，拿茶叶；一切就绪，灌水烧水；坐待水开了泡茶喝 办法丙： 洗净水壶，灌上凉水，放在火上，坐待水开；水开了之后，急急忙忙找茶叶，洗茶壶茶杯，泡茶喝 哪一种办法省时间？我们能一眼看出第一种办法好，后两种办法都窝了工 水壶不洗，不能烧开水，因而洗水壶是烧开水的前提没开水、没茶叶、不洗茶壶茶杯，就不能泡茶，因而这些又是泡茶的前提 •办法甲总共要161/3分钟（而办法乙、丙需要20分钟）如果要缩短工时、提高工作效率，应当主要抓烧开水这个环节，而不是抓拿茶叶等环节同时，洗茶壶茶杯、拿茶叶总共不过4分钟，大可利用「等水开」的时间来做•练习•造某幢房子的工序、工期和工序衔接关系如表所示，问：怎样才能使工程尽快完工？工序代号工序名称工期（天）紧前工序A了解设计要求 3无B地基建设 5AC建造主体结构 12BD排设管道 5CE埋置电缆电线 3CF安装空调设备 7EG建隔离墙 9D,FH外墙装饰 15CI内墙装饰 7GJ地面装饰 3IK环境美化 4H开始AB35C12D5G9I7J3E3F7H15K4结束1.开始ABCFGIJ结束，需44天.2.开始 ABCEDGI J结束，需49天.3.开始 ABCEF结束，需30天.4.开始 ABCHK结束，需39天. 我们知道，每个工序链的完成都是工程完成的必要条件.所以，我们应该在其中找一条工期最长的链作为关键工序链，其链上的每道工序都是关键工序.在这项建房工程中，工序链2可以作为关键工序链，不在链上的工序都是非关键工序. 下面来确定各工序的开工时间.由于关键工序链已经确定，所以各关键工序的开工、完工时间是确定的，关键工序链上每道工序的开工日期都可以定在其紧前工序的完成之时.结果见右表.工序开工时间（天数从0开始）工期完工时间ABCEFGIJ038202330394635123797338202330394649确定非关键工序开工时间的原则是不影响关键工序的施工.例如，非关键工序D是关键工序G的紧前工序，而G的开工日期已定为30，因此D最迟必须在第30天完成.考虑到D的施工期为5天，所以D的最迟开工日期应为第25天（即第26天开始）.至于D的最早开工日期则是它的紧前工序C的完成之时----日期为第20天，相应的最早完工日期为第25天.总之，对非关键工序，它们的开工日期由一定的松动余地，我们可按其紧前的关键工序的完工日期推算出它们的最早开工日期和最早完工日期；再按其‘‘紧后’’的关键工序的开工日期推算出它们的最迟完工日期和最迟开工日期.于是，一份完整的各工序时间安排表就制作完毕（见表）工序开工日期时差工期完工时间最早最迟ABCDEFGHIJK0382020233020394645038252023303039464500050001000103820252330393546493938203023303945464949 总的施工进度安排妥当后，还要把各项任务和完成任务的时间落实到各施工组.设工序A由技术组负责；工序B和C由建筑组负责；工序D由管道组负责；工序E、F由电工组负责；工序G、H、I、J、K由泥工组和木工组共同负责.汇总上述情况，可将施工进度按组作出条状的进度管理图.见下表. 其中，泥木工组的任务比较多，又有一些工序需同时施工，所以把泥木工组分为两组分头施工.技术组A(3)建筑组B(8)C(20)管道组D(30)电工组E(23)F(30)泥木工组(一)H(45)K(49)(二)G(39)I(46)J(49)日期 0 20 30 4910.4 聚类分析法 分类是人类认识客观世界的基本方法之一.人们把所研究的对象分成若干类，然后分门别类地进行仔细研究，从而加深对事物的认识.例如，通过对感冒病人病史的分类，可以加深对感冒病因的认识；通过对公司经营业绩分类，可以找到改善经营状况的途径.历史上很早以前就有分类这门学问，但是那时主要是依靠专业知识进行分类，很少利用数学工具.随着生产和科学技术的发展，分类越来越细，分类准确性的要求也越来越高.于是，分类学中逐渐形成了“统计聚类分析”或“统计聚类建模”这门学问.10.4.1 如何衡量两事物的差别 衡量两个事物接近程度的方法很多，我们用量化手段来处理.例1 体型差别. 从生活中我们知道，影响人类体型的因素中最重要的莫过于身高和体重了.我们把一个人的身高用 表示，体重用 表示；另一个人的身高用 表示，体重用 表示.两个人体形的差别大体上可以用他们的身高和体重的差别来表示.为此，我们可以把 和 看做坐标平面上的两个点.用这两个点的“距离”来表示这连个人在体型上的差别.如果该距离比较小，说明这两个人的体型比较接近；反之，他们体型的差别则较大.于是就得到了衡量两个人体型差别的两个简单指标：（1）矩形距离 ； （2）欧氏距离 . 当然，在衡量体形的差别时，我们还可以考虑更多的因素，如坐高、臂长等等.例2 语言差别. 每种语言都非常复杂，各种语言既有差别，又有很多相近之处，如何对各种语言做一个恰当的分类呢？ 首先，必须寻找一种既简单又能反映他们之间联系和差别的方法.一种简单的方法就是对各种语言中表达数字的词进行比较，这些词之间的差别在一定程度上代表了不同语言之间的差别. 其次，不同语言的两个数词之间的差别如何用数来刻画呢？我们设法用一种简单的方法来规定两种语言中数词间的距离：若数词的第一个字母相同，规定其距离为零；若数词的第一个字母不同，则规定为1. 然后，用十个数词间的距离之和a来规定这两种语言的距离.显然，a越小，这两种语言就越接近；反之，则相差越大.例如，欧洲各国之间有着悠久的历史渊源关系，意大利语与西班牙语的距离为1，因此十分相近；而意大利语与匈牙利语的距离为10，因此相差很大. 最后，我们还可以对一些语言进行适当的分类.例如欧洲10种语言与英语之间的距离见下表.国别挪威丹麦荷兰德国法国西班牙意大利波兰匈牙利芬兰距离227 6666799 根据这些距离指标，可以粗略的讲着10种欧洲语言分为三类：挪威、丹麦；荷兰、德国、法国、西班牙、意大利、波兰；匈牙利、芬兰.10.4.2 聚类分析法 将每个事物都看做数学空间中的一点，在这个数学空间中规定两点间的距离，以距离来表示事物的差别，分类时，常把距离近的点归于一类，这种方法叫做聚类分析法. 聚类分析法如何操作呢？ 我们用D(i,k)表示第i个事物与第k个事物间的距离.丙用适当的方法规定类与类之间的距离.了；例如：以 、 …表示类，以D(p,q)标记类 与类 之间的距离， D(p,q)可以规定为 中任一事物和 中任一事物距离的最小值，即类 与类 之间的“最短距离”. 假设现在要对100个事物进行分类.可先将100个事物各自成一类，这样开始时共有100类.我们规定事物之间的距离，以表示事物之间的差别.同时规定类与类之间的距离，以表示类之间的差别.开始时，由于100个事物自成一类，故类与类之间的距离就是事物与事物之间的距离.将距离最小(或不超过某一数值)的类合并成一个新类，计算新类与其它类之间的距离，再将距离近的类合并.这样，每次可以减少类的数目，直至类的数目满足聚类的要求为止.这是一种逐步合并的聚类方法.10.4.3 有序事物的聚类分析 许多实际问题中的事物是按一定的次序排列的，这样的事物称为有序事物.例如，儿童的增重数按年龄排序，历史按时间的先后排序，地质勘探取样按地层的深浅排序.  对有序事物进行分类时，不能打乱原先事物的次序.那么有序 事物如何聚类呢？10.4.3.1 问题 儿童体重每年增加的数量与儿童的生长发育过程有关.下表给出了1岁至11岁儿童每年的平均增重数.年龄12345678910 11增重(千克)9.3 1.8 1.9 1.7 1.5 1.3 1.4 2.0 1.9 2.3 2.1 从上表中可以粗略地看到：1岁时儿童增重的高峰，6岁是儿童增重的低谷.我们主要讨论：应该把1岁到11岁的儿童划分成几个发育好阶段？如何划分阶段为好？10.4.3.2 分析 一种好的分类方法，应能使处于同一类中的事物之间的差别尽可能的小，而使类与类之间的差别尽可能的大.例如，把一个班级的学生分成学习成绩好、中、差三类，同是成绩好的一类学生之间的差别应该不大.而若一个学生属于成绩好的类，另一个学生属于成绩中等的类，则这两个学生之间应有明显的差别.如何表示类内部事物与事物之间的差别呢？我们借用统计中全距(即两数的距离)的计算方法.10.4.3.3 模型建立及求解 以 ， ，… ，记上述对应的儿童增重的11个数据， 表示i岁儿童的增重数.设想要把它们分成保持次序的3个组，这时可以有多种选择.例如，{1，2，3}，{4，5，6，7，8}，{9，10，11}就是一种可选择的分类方法.这里{1，2，3}表示把1岁~3岁分为一组， {4，5，6，7，8}表示把4岁~8岁分为一组.可 以知道，把11个事物不改变其排列次序地分为3类，相当于在10个位置(每个位置想象为两个事物的“间隔”)放置2各栅栏.因此，按组合方法共有 种分法. 现在，以下面的一种分类方法：{1,2,3},{4,5,6,7,8},{9,10,11} 为例，说明计算类内差别的方法.其中，第一类{1,2,3}对应的数据为：9.3，1.8，1.9.此处最大值为9.3，最小值为1.8.这一类内的差异我们用其全距9.3-1.8=7.5来表示.第二类{4,5,6,7,8} 对应的数据中的最大值和最小值分别为2.0和1.3，于是，这一类内的差异可用2.0-1.3=0.7来表示.同理，第三类{9,10,11}内的差异可用2.3-1.9=0.4来表示. 为度量上述分类方法的优劣，我们计算此种分类方法中三个类内差异的平均数，即规定该分类方法的优劣指标K，其值为 对于另一种分类方法{1,2,3,4}，{5,6},{7,8,9,10,11}，第一类内 差异为7.6，第二类内差异为0.2，第三类内差异为0.9.该分类方法的优劣指标约为2.90.相比之下，此分类方法不如上述分类方法好. 把11个有序数据分成3类，有45种方法.计算每种分法的优劣指标，加以比较，可得最好的分类方法为{1},{2,3,4,5,6,7,8,9}, {10,11}.此类方法的优劣指标 同样,把这11个数据分成2类的最好分类方法是： {1},{2,3,4,5,6,7,8,9,10,11},这时的优劣指标 K=0.5，分成4类的最好分类方法是{1},{2,3,4},{5,6,7},{8,9,10,11}, 这时的优劣指标K为0.20. 那么，这11个数据分成几类为宜呢？ 为此，我们分别找到把这11个数据分成1类，2类，…，11类的 最好的分类方法，计算出各最好分类方法的优劣指标，如下图所示.分类数目n1234567891011优劣指标K8.00.5 0.30.20.140.1 0.07 0.04 0.02 0.010 由上表可以看出，如果把1岁~11岁的儿童只分成两类(n=2)，则K=0.5，优劣指标值太大；对n大于4的情况，优劣指标值K相差不多，而当n=3或n=4时，K值已降为0.30和0.20.因此，分成3类或4类为宜. 以下对分成4类的情况予以解释.儿童从1岁到11岁可分为4个阶段：1岁的儿童睡得多吃得多，处于体重增加最快的阶段；2岁至4岁的儿童在幼儿园，体重增加有所减缓；5岁至7岁的儿童处于入学前或刚入学的阶段，特别好动，体重增加相对缓慢；8岁至11岁生活规律化，使儿童体重稳定增加.练习：1. 隼的分类（第四届北京高中数学知识竞赛初赛题）燕隼和红隼是同属于隼形目隼科的鸟类.它们的体形大小如鸽，形略似燕，身体的形态特征比较相似.红隼的体形比燕隼略大.通过抽样测量，已知燕隼的平均体长约为31厘米，平均翅长约为27厘米；红隼的平均体长约为35厘米，平均翅长约为25厘米.近日在某地发现了两只形似燕隼或红隼的鸟，经测量，知道这两只鸟的体长和翅长分别为A（32.65厘米，25.2厘米）B（33.4厘米，26.9厘米）.你能否设计出一种近似方法，利用这些数据判断这两只鸟是燕隼或者红隼？ 可用指标衡量（1）矩形距离；（2）欧氏距离；（3）体长与翅长的和；（4）体长与翅长的差；（5）体长与翅长的比（6）翅长与体长的比.等等。