◎袁淑娟

男女相親的最優(yōu)配對(duì)問題

◎袁淑娟

隨著社會(huì)的發(fā)展，相親已成為很多人尋找配偶的一種選擇。婚姻介紹所面對(duì)大量男士和女士，在了解他們的個(gè)人情況以及對(duì)對(duì)方的基本要求后，如何給他們配對(duì)才能使成功率最高就是一個(gè)亟需解決的問題。本文根據(jù)實(shí)際情況建立評(píng)價(jià)標(biāo)準(zhǔn)，得到男女相互間的評(píng)分表，然后利用匈牙利算法，計(jì)算出男女的最優(yōu)配對(duì)組合，使得相親的總體成功率最高。

問題描述

相親已成為男女交友中較為流行的方式，其中大量相親是通過(guò)婚姻介紹所之類的機(jī)構(gòu)組織的。我們假設(shè)婚介所了解了10對(duì)男女的個(gè)人情況（年齡，身高，體重，容貌，學(xué)歷，工作，家庭情況），以及他們對(duì)對(duì)方的要求（要求也是限制在這7個(gè)方面）。根據(jù)這些情況，婚介所該如何給這10對(duì)男女配對(duì)，才能使成功配對(duì)的人數(shù)最多。

模型的建立與求解

1） 處理數(shù)據(jù)，分析男女彼此滿意度

記 10位 女 士 分 別 為：w1，w2，w3…，w10，10位男士分別為：m1，m2，m3…，m10。先從女士w1開始，根據(jù)她在7個(gè)方面對(duì)對(duì)方的要求，逐一對(duì)10位男士進(jìn)行評(píng)價(jià)打分，最后將得分相加，即該女士對(duì)該男士的評(píng)分，分?jǐn)?shù)越高表示滿意度越高。結(jié)合實(shí)際情況，評(píng)價(jià)分為非常符合、比較符合、一般符合、不太符合和一定不行五種標(biāo)準(zhǔn)。為了量化處理，五種標(biāo)準(zhǔn)對(duì)應(yīng)的數(shù)值如下表：

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

女士w1對(duì)10位男士的評(píng)價(jià)表：

w1 年齡 身高 體重 容貌 學(xué)歷 工作 家庭情況 總分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

根據(jù)實(shí)際情況，我們規(guī)定如果表中某一項(xiàng)評(píng)價(jià)為0分，則總分為0分。

同樣方式得到其余9位女士對(duì)10位男士的評(píng)價(jià)表，將總分匯總，得到10位女士對(duì)10為男士的評(píng)分表（表1），如下：

表中的數(shù)據(jù)表示所在列的女士對(duì)所在行的男士的評(píng)價(jià)總分。

同樣得到10位男士對(duì)10位女士的評(píng)分表（表2），如下：

表1

表2

將表1和表2的數(shù)據(jù)分別記為矩陣A和B，其中矩陣A中的數(shù)據(jù)Aij表示女士 wi對(duì)男士mj的評(píng)分，矩陣B中的數(shù)據(jù)Bij表示男士mi對(duì)女士wj的評(píng)分。記，則Eij表示女士wi與男士mj的互評(píng)分的平均值，Eij值越大，說(shuō)明wi與mj的相互滿意度越高，兩位配對(duì)成功的概率越大。特別地，若A或BT中有一項(xiàng)數(shù)據(jù)為0，則E中對(duì)應(yīng)數(shù)據(jù)為0。這是符合實(shí)際情況的，因?yàn)槿鬉或BT中有一項(xiàng)數(shù)據(jù)為0，說(shuō)明有一方對(duì)另一方一定不滿意，那么他們配對(duì)就不可能成功，所以E中對(duì)應(yīng)數(shù)據(jù)為0。

2）建立模型并求解

要解決婚介所如何安排才能使配對(duì)成功的人數(shù)最多這一問題，只需要找出在矩陣E中的10個(gè)不同行不同列的元素，使其總和最大。顯然，這是一個(gè)指派問題，我們運(yùn)用匈牙利算法求解。算法如下：

第一步，找出矩陣E中的最大值，然后用最大值減去矩陣E中的每一個(gè)元素得到新矩陣F，這樣就轉(zhuǎn)化為指派問題的標(biāo)準(zhǔn)形式，即求矩陣F中10個(gè)不同行不同列的元素，使其總和最小;

第二步，將矩陣F中的每一行元素減去此行中的最小元素，得到新矩陣F1;

第三步，從矩陣F1中只能選出6個(gè)不同行不同列的零元素，最優(yōu)指派還無(wú)法看出，此時(shí)按照如下步驟進(jìn)行：（1）對(duì)未選出0元素的行打√；（2）對(duì)√行中0元素所在列打√；（3）對(duì)√列中選中的0元素所在行打√。重復(fù)（2），（3）直到無(wú)法再打√為止。

第四步，用直線畫出沒有打√的行和打√的列，就得到了能夠覆蓋住矩陣中所有0元素的最小條數(shù)的直線集合，找出未覆蓋的元素中的最小者，令√行元素減去此數(shù)，√列元素加上此數(shù)，則原先選中的0元素不變，而未被覆蓋的元素中至少會(huì)有一個(gè)已轉(zhuǎn)變?yōu)?，得到新矩陣F1且新矩陣的指派問題與原問題也有相同的最優(yōu)指派。

第五步，第三步和第四步反復(fù)進(jìn)行，直到F1中能選出10個(gè)不同行不同列的0元素為止。

按照上述步驟計(jì)算，我們最終得到

該矩陣中已經(jīng)可以選出10個(gè)不同行不同列的0元素（矩陣中已標(biāo)記），這些0元素所在位置即最優(yōu)指派，所以男女最優(yōu)配對(duì)是 (M1,W3)、 (M2,W9)、 (M3,W10)、 (M4,W8)、(M5,W2)、 (M6,W7)、 (M7,W6)、 (M8,W4)、(M9,W5)、 (M10,W1)。

模型的推廣與評(píng)價(jià)

為了方便說(shuō)明模型的情況，本文是為10對(duì)男女進(jìn)行配對(duì)，在個(gè)人情況這方面給出了7個(gè)要求，但在Matlab運(yùn)算軟件的幫助下，我們可以將人數(shù)和要求都提高至成千上萬(wàn)，模型依然適用。并且在現(xiàn)實(shí)生活中有很多類似相親配對(duì)的問題，如公司招聘、學(xué)生就業(yè)等都可以用這個(gè)模型進(jìn)行求解。

浙江經(jīng)濟(jì)職業(yè)技術(shù)學(xué)院）