多对多双边匹配的优化方法

在现实中存在许多典型的多对多双边匹配问题，如高校大学生与公选课程匹配问题、供应链中提供原材料的供应商和产品制造商之间的匹配问题等。首先给出多对多双边匹配定义的相关符号说明。

设甲方主体集合为A={A1，A2，…，Am}，其中Ai表示第i个甲方主体，i=1，2，…，m；乙方主体集合为B={B1，B2，…，Bn}，其中Bj表示第j个乙方主体，j=1，2，…，n。每个甲方主体Ai最多可以与pi个乙方主体进行匹配，每个乙方主体Bj最多可以与qj个甲方主体进行匹配，pi，qj∈N+其中N+为正整数集，i=1，2，…，m，j=1，2，…，n，且∃pg＞1，g∈{1，2，…，m}，∃ph＞1，h∈{1，2，…，n}。

下面给出多对多双边匹配的定义。

定义1.4（多对多双边匹配） 多对多双边匹配可以定义为一个映射：μ：A∪B→2A∪B，且∀Ai∈A，∀Bj∈B满足以下条件：

（i）μ（Ai）⊆B，且|μ（Ai）|≤pi。特别地，若|μ（Ai）|=0，则表示Ai没有匹配对象。

（ii）μ（Bj）⊆A，且|μ（Bj）|≤qj。特别地，若|μ（Bj）|=0，则表示Bj没有匹配对象。(www.xing528.com)

（iii）Bj∈μ（Ai）当且仅当Ai∈μ（Bj）。

在定义1.4中，|μ（Ai）|和|μ（Bj）|分别表示与Ai匹配的乙方主体数量和与Bj匹配的甲方主体数量；Bj∈μ（Ai）或Ai∈μ（Bj）表示Ai与Bj进行匹配，并称（Ai，Bj）为Ai与Bj形成的匹配对。根据μ确定的所有匹配对的集合称为多对多匹配方案μ。

根据上述分析，多对多双边匹配如图1.1所示。

图1.1　多对多双边匹配示意图

在图1.1中，单向虚线“——→”表示Ai给出关于Bj的偏好信息，Bj没有给出关于Ai的偏好信息，即Ai认为Bj是可接受的，Bj认为Ai是不可接受的；单向虚线“←——”表示Ai没有给出关于Bj的偏好信息，Bj给出关于Ai的偏好信息，即Ai认为Bj是不可接受的，Bj认为Ai是可接受的；双向虚线“←—→”表示Ai和Bj相互给出关于对方的偏好信息，即是相互可接受的，双向实线“←→”表示Ai和Bj形成了匹配对，所有的“←→”连接的匹配对构成了一个多对多双边匹配方案。