运筹学案例 案例八：匹配问题 第 1 页 共 5 页 案例八：匹配问题 案例概述： 有 5 个待业者 i A(i 1,2, ,5)=L 和 5 项工作 j B(j 1,2, ,5)=L ，表 6.13 中 标记“√”表示 Ai 能干 Bj 工作。每项工作只允许一个待业者干， 每个待业者只能干一项工作。试设计一个就业方案，使尽量多的待业 者就业。 图 6.30 表 6.12 B1 B2 B3 B4 可供量 A1 5 10 5 20 A2 10 10 20 市 场 调 运 量 仓 库 运筹学案例 案例八：匹配问题 第 2 页 共 5 页 A3 15 10 40 5 100 需求量 20 20 60 20 案例求解： 由表 6.13，将待业者及其所能干的工作可用图 6.31 表示，其中 每条弧线表示 Ai 可干 Bj 工作。图 6.31 是一张二分图。本例就是一 个求二分图的最大匹配问题，它可借助于求最大流方法进行求解： 在 Ai（ i=1,2,… ,5）左边增加一个虚拟发点 S，在 Bj（ j=1,2,… ,5） 右边增加一个虚拟收点 t，分别连结 ij sA ,B t(i,j 1,2, ,5)=L ，且这些弧的 容量均为 1，而弧（ Ai， Bj）的容量为∞（省略） ，如图 6.32（ a）所 示。当这个网络流达到最大时，如果（ Ai， Bj）上的流量为 1，则 Ai 就干 Bj 工作，这就是使最多待业者就业的方案。 表 6.13 B1 B2 B3 B4 B5 A1 √ √ √ √ A2 √ √ A3 √ √ A4 √ A5 √ √ 工 作 待 业 者 运筹学案例 案例八：匹配问题 第 3 页 共 5 页 图 6.31 按最大流标号法得到图 6.32（ b）所示的最多待业者就业方案， 即最大流量是 4，待业者 A1， A2， A3， A5 分别干 B2， B1， B5， B4 工作，当然这个就业方案不是唯一的。 图 6.32 匹配问题在经济管理中应用很广。例如： 设一台机器由 4 个部件 I， II， III， IV 组装而成。组装前各部件 须分别在某台机床上进行加工， 中有 4 个部件全部加工完毕方可进行 组装。现有 4 台机床 A1， A2， A3， A4，各部件在每台机床上所需加 工时间如表 6.14 所示（单位：工作日） 。现规定一台机床只能加工一 种部件，试问应将哪一部件安排在哪台机床上，加工机器才能最早开 运筹学案例 案例八：匹配问题 第 4 页 共 5 页 始组装？ 显然， 机器最早开始组装的时间即为 4 个部件各在一台机床上加 工完成的最长时间。因此，先任意选定一个可行方案，如表 6.14 中 用圆圈定的数字，即各部件加工所需时间为 5， 7， 2， 4。其中加工 所需最长时间为 7，即在 7 个工作日后就可开始机器的组装。为了求 出更好的方案，把加工时间不少于 7 个工作日的数字从表中删去，留 下加工时间小于 7 的数字，并用空圈表示。见表 6.15。 表 6.14 I II III IV A1 ⑤ 4 7 6 A2 9 ⑦ 3 5 A3 8 11 ② 3 A4 7 5 1 ④ 表 6.15 I II III IV A1 ○ ○ ○ A2 ○ ○ A3 ○ ○ A4 ○ ○ ○ 部 件 加 工 所 需 时 间 机 床 部 件 机 床 运筹学案例 案例八：匹配问题 第 5 页 共 5 页 图 6.33 并依据表 6.15 中的对应关系建立机床与机器部件的配对网络图 6.33。用求最大流方法求得 max (f ) 4υ = ，其中 A1→ B1， A2→ B4， A3 → B3， A4→ B2， { }max 5,5, 2,5 5= 。也就是说，用 A1 机床加工 I 部件， A2 机床加工 IV 部件， A3 机床加工 III 部件， A4 机床加工 II 部件， 能在第 6 天最早开始机器的组装。