Modeling第十讲：基于统筹方法的数学建模-数学建模理论与.ppt

数学建模理论与实践 基于统筹方法的数学建模 一、统筹图的有关概念 （一）事项的概念 （二）紧前工序与紧后工序的概念 （二）紧前工序与紧后工序的概念 （二）紧前工序与紧后工序的概念 （二）紧前工序与紧后工序的概念 书面作业 * * —— 基于统筹方法的数学建模 一、统筹图的有关概念 二、统筹图的要求及其检验方法 三、统筹图的分析方法 （一）事项的概念 （二）紧前工序与紧后工序的概念 一道工序以一条有向边来表示，有向边的权即为此工序的长度，表示完成该工序所需的时间。 有向边的起点和终点分别表示该工序的开始和结束，称为事项； 前接工序的完工事项即为后继工序的开工事项。 统筹图的最重要功能：表示所要作的事项的先后次序关系。若工序的终点是工序的起点（如下图所示），则称工序是工序的紧前工序，工序是工序的紧后工序。 统筹图的表示工序先后的次序关系的原则是： 一个工序只有当它的所有紧前工序都完成后，才可以开工。 或者说，对每一个事项来说，只有在指向该事项的所有工序都已完成的条件下，从该事项出发的工序才可以开始开工。 引例：这里我们以一个“以茶待客”这个任务的完成过程来理解统筹图及工序、事项、初始(最终)事项、紧前(紧后)工序等相关概念。 假设洗茶杯要1分钟，找茶叶并放入茶杯要1分钟，烧开水要5分钟，而最后的冲茶要1分钟。经过分析，我们把完成“以茶待客”这个任务用下图表示： 其中的A-洗茶杯、B-找茶叶并放入茶杯、C-烧开水、D-冲茶 从上面的统筹图可以读出各个事项发生的先后次序： （1）事项一定要在事项完成后才能做，也就是说，放茶叶前一定要先洗好茶杯，即：事项是事项的紧前工序，事件是事项的紧后工序； （2）事项一定要在、都完成的情况下才能开始。也就是说，冲茶前一定要先放好茶叶并且烧好开水。由此可见，对每一个事项来说，只有在指向该事项的所有工序都已完成的条件下，从该事项出发的工序才可以开始动手做。 二、统筹图的要求及其检验方法 （一）统筹图的要求 （二）如何画出正确的统筹图 （三）如何检查统筹图有无圈 （一）统筹图的要求 正确的统筹图要求：（1）整个统筹图只有一个初始事项和一个最终事项；（2）统筹图无圈。所谓“圈”是图中从某个事项出发经过若干首尾相连的有向线段又回到起点的一个工序序列。 如果说要求（1）是一种“表达形式上”的要求，而且也易满足，那么要求（2）“统筹图无圈”的要求则是“本质性”的。这是因为统筹图是一个有向图，有向图的圈与前述的无向图的圈不同。统筹图中一旦出现圈，由于它表示工序上互为前提，故在实践中无法实现。 （二）如何画出正确的统筹图 例1：下表是某个机床要加工的5种零件的先后的次序关系，试根据表格画出相应的统筹图来。 1 2 1,2 - - 紧前工序 5 4 3 2 1 工件编号 （二）如何画出正确的统筹图 先看零件5的情况，可以画出统筹图图(a)；对于零件3的情况，可以画出统筹图图(b)； 图(a) 图(b) （二）如何画出正确的统筹图 图(c) 图(d) 现在要把图(a)与(b)拼在一起，但千万不可画成图(c)的样子，因为工件5不以工件2作为紧前工序，必须加进一个虚工序，可以画出统筹图图(d)。虚工序只不过是用来帮助表示有关工序的先后次序关系。 × （二）如何画出正确的统筹图 图(e) 同样要对工序4进行讨论，当把它拼到统筹图图(d)时，也要加进一个虚工序，得到的正确的统筹图如下： （二）如何画出正确的统筹图 例2：自行车的装配问题 下图标出了自行车有关零件的名称。要把一堆自行车零件组装成一辆自行车，主要有以下几个工序： A--组装车架，包括装前叉、车把和前后挡泥板； B--安装并校正前轮； C--安装并校正后轮（含飞轮）； D--安装中轴，包括装轮 盘和大腿； E--在轮盘和飞轮间连接 链条； F--安装左、右脚蹬； G--安装前后车闸和车座。 （二）如何画出正确的统筹图 对于一个熟练的装配工，完成各个工序所需要的时间如下： 10 4 5 7 7 5 7 时间（分） G F E D C B A 工序 如果仅由一个人完成全部组装工作至少需要45分钟，这在集体化生产的今天显然是不可取的。现在安排两个工人合作组装一辆自行车，每道工序只能由一人完成，请你为这两个工人安排一个组装的工序流程，使他们在最短时间内装配好这辆自行车。并请算出最短时间。 （二）如何画出正确的统筹图 解： 1. 根据题目给出的