图论数学模型精品文稿.ppt

《图论数学模型精品文稿.ppt》由会员分享，可在线阅读，更多相关《图论数学模型精品文稿.ppt（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图论数学模型第1页，本讲稿共13页2.3 2.3 建立图模型建立图模型 解决实际问题的趣例解决实际问题的趣例第2页，本讲稿共13页例例 1 1 节目排序问题节目排序问题 一场文艺演出共有8个节目,全体演员中有10人须参加两个以上的节目演出,情况如表，表中的号所示,如演员1要参加三个节目A、B和H.若节目主办单位希望首尾两个节目为A和H,或为H和A,并且希望每个演员不连续参加两个节目的演出,试为主办单位安排一个节目顺序表.第3页，本讲稿共13页第4页，本讲稿共13页分析如演员1要参加三个节目A、B和H。若节目主办单位希望首尾两个节目为A和H。或为H和A，并且希望每个演员不连续参加两个节目的演出，

2、试为主办单位安排一个节目顺序表。所谓开头为节目A（或H），结尾为H（或A），可以认定是一个图的出发点和结束点，由此考虑，以8个节目为顶点构建图模型。由于每个演员不连续参加两个节目的演出,意味着对八个顶点联线时要注意相邻顶点的演员关系.于是决定,若两个节目无同一名演员参加,则可连一条边,表示这两个节目可以紧排,否则不连边,便构成一个图模型（图219）.第5页，本讲稿共13页解：第6页，本讲稿共13页例例2 2 药品存储问题药品存储问题有八种化学药品A、B、C、D、P、R、S和T要放进贮藏室保管,出于安全原因,下列各组药品不能贮在同一室内:AR，AC，AT，RP，PS，ST，TB，BD，DC，RS

3、，RB，PD，SC，SD，试为这八种药品设计一个使用房间数最少的贮藏方案。第7页，本讲稿共13页解：TCP;ABS;RD第8页，本讲稿共13页例例 3 3 工程流程图工程流程图（第五届北京高中数学知识应用竞赛题）机床的大修有如下的工作项目：拆卸，清洗，电器检修，部件检查，零件加工，零件修理，床身和工作台研合，部件组装（不含电器），变速器组装，试车.1.画出工序的流程图，即用图表示出各项工作的衔接关系.2.假定大修期间没有耽误任何时间，并把开始拆卸时刻记为 0，试问：大修完成的时刻最早是多少？3.在不影响最短时间完工的条件下，每个工作项目最早和最迟开工时间各是多少？第9页，本讲稿共13页关于工序

4、流程图画法的说明关于工序流程图画法的说明（1）“拆卸”，“清洗”等这些具体工作称为 工序，用实箭线“”来表示。工序名称写在箭线上方，完成这项工序的时间写在箭线下面，箭线的方向代表了工序时间的流向.（2）工序之间交接处表示的圆圈称为 事项 或 结点，用以标志前面工序的结束和允许后面工序的开始，是工序完成或开始的瞬间符号，具有承上启下、把工序衔接起来的作用.（3）若 A 工序必须在 B 工序完成之后才有条件进行，则称 A 是 B 的 紧后工序，或称 B 是 A 的 紧前工序.另外，同一对结点间不能表示两个及其以上个工序，如图 2 21（左图）的画法是不允许的，为此引进了虚工序概念而将此表示式画成图 2 21（右图）的形式.第10页，本讲稿共13页第11页，本讲稿共13页解：关键路线为 11 第12页，本讲稿共13页自我检测练习题2：5、6、7第13页，本讲稿共13页