◎袁淑娟

男女相亲的最优配对问题

◎袁淑娟

随着社会的发展，相亲已成为很多人寻找配偶的一种选择。婚姻介绍所面对大量男士和女士，在了解他们的个人情况以及对对方的基本要求后，如何给他们配对才能使成功率最高就是一个亟需解决的问题。本文根据实际情况建立评价标准，得到男女相互间的评分表，然后利用匈牙利算法，计算出男女的最优配对组合，使得相亲的总体成功率最高。

问题描述

相亲已成为男女交友中较为流行的方式，其中大量相亲是通过婚姻介绍所之类的机构组织的。我们假设婚介所了解了10对男女的个人情况（年龄，身高，体重，容貌，学历，工作，家庭情况），以及他们对对方的要求（要求也是限制在这7个方面）。根据这些情况，婚介所该如何给这10对男女配对，才能使成功配对的人数最多。

模型的建立与求解

1） 处理数据，分析男女彼此满意度

记 10位 女 士 分 别 为：w1，w2，w3…，w10，10位男士分别为：m1，m2，m3…，m10。先从女士w1开始，根据她在7个方面对对方的要求，逐一对10位男士进行评价打分，最后将得分相加，即该女士对该男士的评分，分数越高表示满意度越高。结合实际情况，评价分为非常符合、比较符合、一般符合、不太符合和一定不行五种标准。为了量化处理，五种标准对应的数值如下表：

非常符合 比较符合 一般符合 不太符合 一定不行8 6 4 2 0

女士w1对10位男士的评价表：

w1 年龄 身高 体重 容貌 学历 工作 家庭情况 总分m1 8 8 8 6 4 2 4 40 m2 8 8 8 8 8 8 8 56 m3 6 8 8 6 6 6 6 46 m4 6 4 4 6 2 2 4 28 m5 6 6 4 8 2 4 4 34 m6 8 6 6 6 0 2 4 0 m7 2 2 2 2 2 2 2 14 m8 8 6 2 4 2 4 6 32 m9 8 2 4 2 4 2 2 24 m10 8 8 6 8 8 8 6 52

根据实际情况，我们规定如果表中某一项评价为0分，则总分为0分。

同样方式得到其余9位女士对10位男士的评价表，将总分汇总，得到10位女士对10为男士的评分表（表1），如下：

表中的数据表示所在列的女士对所在行的男士的评价总分。

同样得到10位男士对10位女士的评分表（表2），如下：

表1

表2

将表1和表2的数据分别记为矩阵A和B，其中矩阵A中的数据Aij表示女士 wi对男士mj的评分，矩阵B中的数据Bij表示男士mi对女士wj的评分。记，则Eij表示女士wi与男士mj的互评分的平均值，Eij值越大，说明wi与mj的相互满意度越高，两位配对成功的概率越大。特别地，若A或BT中有一项数据为0，则E中对应数据为0。这是符合实际情况的，因为若A或BT中有一项数据为0，说明有一方对另一方一定不满意，那么他们配对就不可能成功，所以E中对应数据为0。

2）建立模型并求解

要解决婚介所如何安排才能使配对成功的人数最多这一问题，只需要找出在矩阵E中的10个不同行不同列的元素，使其总和最大。显然，这是一个指派问题，我们运用匈牙利算法求解。算法如下：

第一步，找出矩阵E中的最大值，然后用最大值减去矩阵E中的每一个元素得到新矩阵F，这样就转化为指派问题的标准形式，即求矩阵F中10个不同行不同列的元素，使其总和最小;

第二步，将矩阵F中的每一行元素减去此行中的最小元素，得到新矩阵F1;

第三步，从矩阵F1中只能选出6个不同行不同列的零元素，最优指派还无法看出，此时按照如下步骤进行：（1）对未选出0元素的行打√；（2）对√行中0元素所在列打√；（3）对√列中选中的0元素所在行打√。重复（2），（3）直到无法再打√为止。

第四步，用直线画出没有打√的行和打√的列，就得到了能够覆盖住矩阵中所有0元素的最小条数的直线集合，找出未覆盖的元素中的最小者，令√行元素减去此数，√列元素加上此数，则原先选中的0元素不变，而未被覆盖的元素中至少会有一个已转变为0，得到新矩阵F1且新矩阵的指派问题与原问题也有相同的最优指派。

第五步，第三步和第四步反复进行，直到F1中能选出10个不同行不同列的0元素为止。

按照上述步骤计算，我们最终得到

该矩阵中已经可以选出10个不同行不同列的0元素（矩阵中已标记），这些0元素所在位置即最优指派，所以男女最优配对是 (M1,W3)、 (M2,W9)、 (M3,W10)、 (M4,W8)、(M5,W2)、 (M6,W7)、 (M7,W6)、 (M8,W4)、(M9,W5)、 (M10,W1)。

模型的推广与评价

为了方便说明模型的情况，本文是为10对男女进行配对，在个人情况这方面给出了7个要求，但在Matlab运算软件的帮助下，我们可以将人数和要求都提高至成千上万，模型依然适用。并且在现实生活中有很多类似相亲配对的问题，如公司招聘、学生就业等都可以用这个模型进行求解。

浙江经济职业技术学院）