江西财经大学：《运筹学》课程教学资源（案例）匹配问题

运筹学案例 案例八:匹配问题 案例八:匹配问题 案例概述: 有5个待业者A(=12…5)和5项工作B(=2…5),表613中 标记“√”表示Ai能干B工作。每项工作只允许一个待业者干, 每个待业者只能干一项工作。试设计一个就业方案,使尽量多的待业 者就业。 (10,10) 20,20) (20.20(40 B2(2,2 图630 表6.12 调 BI B2 B4 可供量 510 5 20 A2 10 10 20 第1页共5页

运筹学案例 案例八：匹配问题 第 1 页 共 5 页 案例八：匹配问题 案例概述： 有 5 个待业者A (i 1, 2, ,5) i = L 和 5 项工作B (j 1,2, ,5) j = L ，表 6.13 中 标记“√”表示 Ai 能干 Bj 工作。每项工作只允许一个待业者干， 每个待业者只能干一项工作。试设计一个就业方案，使尽量多的待业 者就业。 图 6.30 表 6.12 B1 B2 B3 B4 可供量 A1 5 10 5 20 A2 10 10 20 市 场 调 运 量 仓 库

运筹学案例 案例八:匹配问题 A3 15 40 5 100 需求量 20 20 20 案例求解: 由表6.13,将待业者及其所能干的工作可用图6.31表示,其中 每条弧线表示A可干B工作。图6.31是一张二分图。本例就是 个求二分图的最大匹配问题,它可借助于求最大流方法进行求解 在Ai(i=1,2;…,5)左边增加一个虚拟发点S,在Bj(j=1,2…5) 右边增加一个虚拟收点t,分别连结A,B1=12…,5),且这些弧的 容量均为1,而弧(Ai,B)的容量为∞(省略),如图6.32(a)所 示。当这个网络流达到最大时,如果(Ai,Bj)上的流量为1,则 Ai就干Bj工作,这就是使最多待业者就业的方案 表6.13 作 BI B2 B3 B4 B5 者 Al A2 √ A3 A4 A5 第2页共5页

运筹学案例 案例八：匹配问题 第 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，分别连结 i j 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 √ √ 工 待 作 业 者

运筹学案例 案例八:匹配问题 B A B B B 图631 按最大流标号法得到图6.32(b)所示的最多待业者就业方案, 即最大流量是4,待业者A1,A2,A3,A5分别干B2,B1,B5,B4 工作,当然这个就业方案不是唯一的。 图6.32 匹配问题在经济管理中应用很广。例如 设一台机器由4个部件I,I,Ⅲ,I组装而成。组装前各部件 须分别在某台机床上进行加工,中有4个部件全部加工完毕方可进行 组装。现有4台机床A1,A2,A3,A4,各部件在每台机床上所需加 工时间如表6.14所示(单位:工作日)。现规定一台机床只能加工 种部件,试问应将哪一部件安排在哪台机床上,加工机器才能最早开 第3页共5页

运筹学案例 案例八：匹配问题 第 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个部件各在一台机床上加 工完成的最长时间。因此,先任意选定一个可行方案,如表6.14中 用圆圈定的数字,即各部件加工所需时间为5,7,2,4。其中加工 所需最长时间为7,即在7个工作日后就可开始机器的组装。为了求 出更好的方案,把加工时间不少于7个工作日的数字从表中删去,留 下加工时间小于7的数字,并用空圈表示。见表615。 表6.14 部 机 6 A2 A3 7 表6.15 机 件 床 A2 A3 A4 第4页共5页

运筹学案例 案例八：匹配问题 第 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 ○ ○ ○ 部 件 加 工 所 需 时 机 床 间 部 机 件 床

运筹学案例 案例八:匹配问题 A B31 图633 并依据表6.15中的对应关系建立机床与机器部件的配对网络图 633。用求最大流方法求得maxw()=4,其中A1→Bl,A2→B4,A3 B3,A4→B2,ma5.525}=5。也就是说,用Al机床加工I部件, A2机床加工Ⅳ部件,A3机床加工Ⅲ部件,A4机床加工Ⅱ部件, 能在第6天最早开始机器的组装。 第5页共5页

运筹学案例 案例八：匹配问题 第 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 天最早开始机器的组装