①

清洗 3
②
③
组装 8
• （与本题无关） • 表示清洗完之后再组装，所用时间分别 为3和8小时。
2、工序之间的交接以圆圈表示，称为事 项或结点，用以标志前面工序的结束和后 面工序的开始，是工序完成或开始的间符 号，具有承上起下，把工序衔接起来的作 用。
• 3、若工序A必须在工序B完成之后才有 条件进行，则称A是B的紧后工序，或 称B是A的紧前工序。
注意：并行工序外的其它工序组成的 工序路线显然不能随意改动的，称为 关键路线，关键路线上的各工序也称 为关键工序。 • 本项中关键路线为
1 2 3 4 6 8 9 11
• 其中各工序为关键工序，所用的时 间为整个工程完成的最短时间。
• 。
A
c
B
再反向追踪，可知
• 一共可有四种节目排序表可供选择。
二、存贮问题
• 有八种化学药品要放进贮藏室保管，代 号为A，B，C，D，P，R，S和T，出于安 全原因，下列各组药品不能贮藏在同一 室内。 • A–R，A–C，A–T，R–P，P–S，S–T， T–B，B–D，D–C，R–S，R–B，P–D， S–C，S–D。 • 试为这八种药品设计一个使用房间数最 少的贮藏方案。
模型分析与建立
• 1、以8种药品为研究对象而作为顶点出 现。 • 2、总共给出14个不配的药品对，不能 放在一室的连一条边，得到一个图模型。
如图
• 。
A T
B
C
S
R P
D
如图
• 。
A T
B
C
S
R P
D
模型求解
• T、C、P间无连线，A、B、S间无连线， R与D间无连线。 • 由此得到一个贮藏方案： • TCP一室，ABS一室，RD一室，故至少 需要三个贮藏室。 • 还有其它的选择吗？ • 大家自己找找吧。
如图
A B C D E F G H 1 √ √ 2 3 √ √ 4 5 √ √ √ √ √ √ √ 6 √ 7 √ 8 9 √ 10
√
√ √
√ √
√
√
√
√
√
若节目主办单位希望首尾两个节目为 A和H，并且希望每个演员不连续参加 两个节目的演出，试为主办单位安排 一个节目顺序表。
• 模型建立与分析 • 开头节目A（或H），结尾为H（或A）， 可以认定是一个图的出发点和结束点， 由此，可以8个节目为顶点构建图模型。
四、机床大修最短时间问题
• 机床的大修有如下工作项目： • 拆卸③，清洗④，电器检修④，部件检 查①，零件加工④，零件修理⑤，床身 和工作台研合②，部件组装（不含电器） ②，变压器组装①，试车③。 • 每个工作项目后面圆圈中给出的数字是 完成该项工作所需的时间（小时）
首先的工作是“拆卸”，然后才能 “清洗”和“电器检修”，这两项工 作可以独立地同时进行。 • “部件检查”要在“清洗”之后进 行，然后才可以“零件加工”和 “零件修理”，这两项工作也可以 独立地同时进行。
回答下列问题
• 1、画出工序的流程图，即用图表示出 各项工作的衔接关系。 • 2、假定大修期间没有耽误任何时间， 并把开始拆卸时记为0。 • 试问：大修完成时刻最短为多少？ • 3、在不影响最短时间完工的条件下， 每个工作项目最早和最迟开工时间各是 多少？
1、关于工序流程图画法的说明
• （1）拆卸情况等这些具体工作称为工 序，用实箭线来表示，工序名称写在箭 头上方，完成这项工序的时间写在箭线 的下方，箭线的方向代表了工序的流向。 • 比如：
• 其二是从一顶点出发走遍所有边一次后 到达另一顶点 • 其次，图中顶点可分为两种点，一种是 过路点，另一种是出发点或结束点，过 路点是指沿某条也到达该点后又从该点 沿另一条走向其它顶点。
因此与过路顶点相连接的边的个数必 为偶数，称这种顶点为偶点，非偶点 的顶点称奇点。
• 最后，若一笔画问题是第一种情况，那 么，其顶点均为偶点，即该图中无奇点， 如果一笔画问题属于第二种情况，则图 中奇点个数为2。
A
各工序衔接关系图
⑥④③②① ⑧⑨⑩⑤⑦
电器检修 ④
床身和 工作台 研合
B
10
零件修理 部件组装
1 2 3 4 6 8 9 11
拆卸 ③ 清洗 ④
部件检查
试车
①
零件加工 ④
⑤
②
②
③
变压器组装
①
5
7
2、关于并行工序的说明
• 在没有耽误任何时间条件下，在大修完成的 时刻最早是拆卸开始的第20个小时，即整个 大修最低需要20小时 • 这时因为未将工序“电器检修”，“零件加 工”和“变压器组装”的时间计9个小时在内。 • 道理是这三个工序分别与其它至少一个工序 可同时，称它们为并行工序，并行工序不影 响总工期。
如图
• 。
A
B
C
H
D
G
F
E
如图
• 。
A
B
C
H
D
G
F
E
模型求解
• 从A（或H）出发，寻求一条从A到H （或H到A）的并且经过所有顶点的线 路。 • 易得，A→H的两个节目表，为 • 方案Ⅰ：A → F → B → C → G → D → E→H • 方案Ⅱ：A → F → G → C → B → D → E→H
• 。
D
A
B
C
问题：能否从四块陆地A、B、C、D之 一出发，走遍每座桥一次且仅一次， 而后回到出发地？
• 。
A D
B
C
如果一个图能够从一个顶点出发，笔 不离纸地连续画出每一条边线一次且 仅一次，然后回到出发顶点，则记该 图为“一笔画”。
• 。 • 。
• 。
D
A
B
C
首先如果一个图能够一笔画出，则只 有两种情况出现，其一是从一顶点出 发走遍所有也一次而回到该顶点；
欧拉定理：一个连通图能够一笔画充分必 要条件是图中奇点个数为0或2。 • 一个图是否能够一笔画，只需要看图中 奇点个数是0或是2，则必可一笔画，否 为顶点， 相连接街路为边，邮路成为一个图，而 只要该图能一笔画出，则其长度必然最 短。
《数学建模》
图论模型
主讲 李华平
重庆城市管理职业学院 信息工程系
图论模型
• • • • • 节目排序问题 存贮问题 中国邮路问题 七桥问题 机床大修最短时间问题
1、节目排序问题
• 一场文艺演出共有8个节目，用大写字 母A，B，C，D，E，F，G，H代表。 全体演员有10人须参加两个以上节目演 出，情况如下表中的√号所示，如演员1 要参演三个节目A，B和H。
本例要求从A出发返回到A，故其 奇点个数应该为0
• 但本例中奇点个数计16，因此不能可能 一笔画出，即邮递员肯定要重复走某些 街路。 • 为力求得最短路程，因此将奇点都变为 偶点，就能求得最短路程而将奇点全部 变为 偶点。
因为图中各边长均相同，而在图模型 中边的曲直不加区别，
• 总长度最短为
5 6 2 8 68(km)
另外，同一对结点间不能表示两个及 其以上个工序。
• 如：
①

A a
②
③
C c
①
b

A a B
②
③
C c
④
为此引进了虚工序概念
• 其中到的虚箭头表示虚工序，虚工序用 来说明一项工序 • 图中的表示方法把三道工序关系画得十 分清楚 • A与B工序同时开工，C工序A，B工序 的紧后工序，工序A，B是C的紧前工序。
3、关于项目最早和开工时间概念
• （1）以下各项工作项目（工序）不能 提前也不能推后 • 0时拆卸，3时清洗，7时部件检查，8时 零件修理，13时床身与工作台研合，15 时部件组装，17时试车。
（2）以下工序开工时间可早可晚， 但有最早与最迟开工时间限制
• “电器检修”最早3时与“清洗”同时 开工。 • 最迟在13时开工，否则会影响下一工序 “试车” • “零件加工”最早8时与“零件修理” 同时开工，最迟9时必须开工 • 同理，“变压器组装”最早13时，最迟 16时。
三、中国邮路问题
• 一个邮递员每次送信都从邮局出发，必 须至少一次走过他负责投递范围的每一 第街道，待完成任务后回到邮局，问如 何选择一条投递路线，使他所走的路程 最短？ • （中国著名数学家管梅谷教授在1962年 提出）
设邮递员从邮局A出发，沿格形街道 路走遍所有街路后回到邮局，若方格 形路的每条路长为1（km），邮递员 至少要走多少路程？ •
• A.
关于七桥问题
• 问题的提出 • 18世纪，东普鲁士 有个城市叫哥尼斯 堡，城内有一条普 雷格尔河，这条河 有两条支流，在城 中心汇合成大河， 河中间有一小岛， 河上有七座桥，如 图 所示. 图
陆地D 半岛B
小岛A
陆地C
每天傍晚，人们总要在这七座桥之间散步.很多
人总想一次不重复地走过这七座桥，再回到出
发点.
这就是数学史上著名的哥尼斯堡七桥问题. 可是试来试去总是办不到，于是有人写 信给当时著名的数学家欧拉.欧拉于 1736年，建立了一个数学模型解决了这 个问题.
能否从四块陆地A、B、C、D之一出发，走遍每 座桥一次且仅一次，而后回到出发地？ 1
陆地D 半岛B
小岛A
2
D
A
B
陆地C
C
七桥问题的模型如图所示 • 其中顶点A、B、 C、D代表四块 陆地，其间的 连线（边）表 示相应陆地之 间有桥相连接, 所连边数表示 桥的个数，