語言環(huán)境下具有容忍區(qū)間的有差異雙邊匹配決策方法

（湖南工業(yè)大學(xué) 理學(xué)院，湖南 株洲 412007）

0 引言

D.S.Gale 等[1]在入學(xué)匹配問題和婚姻穩(wěn)定性問題的基礎(chǔ)上提出了“雙邊匹配”的概念，并提出了經(jīng)典的Gale-Shapley 算法。之后，眾多國內(nèi)外學(xué)者對其進(jìn)行了研究，并提出了較多具有針對性的雙邊匹配決策方法[2-11]。雙邊匹配具有廣泛的實際應(yīng)用背景，目前已在人崗雙邊匹配[12-14]、公私合作中政府項目與企業(yè)的雙邊匹配[15-16]和婚姻匹配[17-18]等方面得到較廣泛的應(yīng)用。雙邊匹配決策問題包含中介和兩個有限的主體集，每個主體都對另一方主體給出評價信息，其目的是由中介匹配雙方主體并最大限度地使主體匹配到滿意的另一方主體。

針對主體給出的評價值為清晰數(shù)而期望值為區(qū)間數(shù)或離散區(qū)間數(shù)的無差異型雙邊匹配決策問題，文獻(xiàn)[17-18]分別基于匹配度和前景理論給出了兩種決策分析方法。值得指出的是，文獻(xiàn)[17-18]認(rèn)為，評價值落在期望區(qū)間內(nèi)所對應(yīng)的匹配度為1，而落在期望區(qū)間外所對應(yīng)的匹配度為0，其實這是值得商榷的。事實上，許多現(xiàn)實的雙邊匹配決策問題不屬于無差異的情形，而是有差異的，如對于效益型準(zhǔn)則，應(yīng)是越大越好，故大于期望區(qū)間的評價值所對應(yīng)的匹配度應(yīng)大于期望區(qū)間內(nèi)的評價值所對應(yīng)的匹配度；而對于成本型準(zhǔn)則，則是越小越好，故小于期望區(qū)間的評價值所對應(yīng)的匹配度應(yīng)大于期望區(qū)間內(nèi)的評價值所對應(yīng)的匹配度，因而無差異區(qū)間型準(zhǔn)則下的匹配度計算方法存在一定的局限性。另外，目前已有研究利用語言信息來定性表達(dá)主體對對方主體的評價，并進(jìn)一步提出了雙邊匹配決策方法[19-22]。但針對雙方主體給出的評價為語言信息而期望水平為區(qū)間語言信息的情形缺乏研究?；诖?，本文擬考慮區(qū)間型準(zhǔn)則的差異性，針對不同區(qū)間的評價值，分別定義相應(yīng)的匹配度，并進(jìn)一步提出一種雙邊匹配決策方法，最后應(yīng)用婚姻匹配算例進(jìn)行驗證和分析。

1 預(yù)備知識

1.1 語言標(biāo)度

語言標(biāo)度由若干語言術(shù)語組成，能夠比較準(zhǔn)確地表達(dá)模糊信息。徐澤水[23]設(shè)定了語言標(biāo)度，τ≥0，其中sφ表示語言術(shù)語，s-τ和sτ分別表示決策者實際使用的語言術(shù)語的下限和上限，且s滿足

1）如果φ1＞φ2，則＞；

為較準(zhǔn)確地描述主體的評價信息而又保證簡便性，課題組設(shè)定τ=3，即采用7 粒度的語言標(biāo)度S7={s-3,s-2,s-1,s0,s1,s2,s3}，其中s-3表示“極差”，s-2表示“差”，s-1表示“較差”，s0表示“一般”，s1表示“較好”，s2表示“好”，s3表示“極好”。

定義1設(shè)為實數(shù)，若則稱k為區(qū)間數(shù)，其中和分別表示k的左右端點。特別地，若=，則k退化為實數(shù)[17]。

定義2設(shè)，為語言術(shù)語集，τ≥0，若，sφ1≤sφf，則稱s為離散語言區(qū)間術(shù)語，其中sφ1和sφf分別表示s的左右端點。特別地，若sφ1=sφf，則s退化為語言術(shù)語，記s為。

1.2 雙邊匹配

定義3設(shè)甲方主體集合為A={A1,A2,…,Am}，m≥2，Ai表示甲方第i個主體，i=1,2,…,m；乙方主體集合為B={B1,B2,…,Bn}，m≥n≥2，Bj表示乙方第j個主體，j=1,2,…,n。設(shè)γ：A∪B→A∪B為一一映射，若滿足以下3 個條件，則γ為雙邊匹配[24]。

1）γ(Ai)∈B，

2）γ(Bj)∈A∪{Bj}，

3）γ(Ai)=Bj當(dāng)且僅當(dāng)γ(Bj)=Ai。其中γ(Ai)=Bj表示Ai與Bj匹配并構(gòu)成匹配對(Ai,Bj)，γ(Bj)=Bj表示Bj無匹配對象，由于其匹配對(Bj,Bj)在匹配結(jié)果中無意義，故忽略。

2 雙邊匹配決策方法

2.1 問題描述

語言環(huán)境下具有容忍區(qū)間的雙邊匹配決策問題由以下幾個部分構(gòu)成。甲方主體的準(zhǔn)則集合為，α≥2，準(zhǔn)則對應(yīng)權(quán)重為，即準(zhǔn)則的權(quán)重為，0≤≤1，。乙方主體的準(zhǔn)則集合為準(zhǔn)則對應(yīng)權(quán)重為，即準(zhǔn)則的權(quán)重為，0≤≤1，。準(zhǔn)則間相互獨立，不互相產(chǎn)生影響。Bj在準(zhǔn)則下對Ai的評價值為，構(gòu)建評價值矩陣，Bj在準(zhǔn)則下的容忍區(qū)間為；Ai在準(zhǔn)則下對Bj的評價值為，構(gòu)建評價值矩陣，在準(zhǔn)則下的容忍區(qū)間為；所有的評價信息和容忍區(qū)間都由主體以語言的形式給出。本文要解決的問題是依據(jù)雙方主體的語言評價信息、容忍區(qū)間和準(zhǔn)則權(quán)重，如何通過有效的雙邊匹配決策，獲得最優(yōu)匹配方案。

2.2 匹配度

由于雙邊匹配決策問題中的準(zhǔn)則主要分為效益型準(zhǔn)則和成本型準(zhǔn)則，所以此部分從效益型準(zhǔn)則和成本型準(zhǔn)則兩個方面給出匹配度的計算公式。

效益型準(zhǔn)則要求主體的評價值越高越好，在主體存在容忍區(qū)間的情況下，小于容忍區(qū)間的評價值對應(yīng)的匹配度為0；容忍區(qū)間內(nèi)的評價值對應(yīng)的匹配度為0.5；大于容忍區(qū)間的評價值對應(yīng)的匹配度為1。

若為效益型準(zhǔn)則，對應(yīng)的匹配度為

類似地，如果為效益型準(zhǔn)則，對應(yīng)的匹配度為

為Ai在準(zhǔn)則下對Bj的評價值。

不同于效益型準(zhǔn)則，成本型準(zhǔn)則要求主體的評價值越低越好，在主體存在容忍區(qū)間的情況下，小于容忍區(qū)間的評價值對應(yīng)的匹配度為1，容忍區(qū)間內(nèi)的評價值對應(yīng)的匹配度為0.5，大于容忍區(qū)間的評價值對應(yīng)的匹配度為0。

如果為成本型準(zhǔn)則，對應(yīng)的匹配度為

為Ai在準(zhǔn)則下對Bj的評價值。

進(jìn)一步利用線性加權(quán)集結(jié)算子將各準(zhǔn)則下的匹配度集結(jié)為總匹配度：

式（5）（6）中：aij為Bj對Ai的總匹配度；

為對應(yīng)的匹配度；

為準(zhǔn)則的權(quán)重；

bij為Ai對Bj的總匹配度；

為對應(yīng)的匹配度；

為準(zhǔn)則的權(quán)重。

2.3 雙邊匹配模型

設(shè)xij為0,1變量，且在滿意雙邊匹配中，由雙方主體的總匹配度矩陣建立多目標(biāo)優(yōu)化模型(M-1)：

式（7）中maxZA表示乙方主體對甲方主體的總匹配度達(dá)到最大值；式（8）中maxZB表示甲方主體對乙方主體的總匹配度達(dá)到最大值；式（9）表示對于每一個甲方主體，都能找到一個乙方主體與之匹配，式（10）表示對于每一個乙方主體，可能不存在甲方主體與之匹配。

可采用線性加權(quán)法將多目標(biāo)優(yōu)化模型(M-1)轉(zhuǎn)化為單目標(biāo)優(yōu)化模型。設(shè)甲方主體的權(quán)重為ωA，乙方主體的權(quán)重為ωB，且0≤ωA≤1，0≤ωB≤1，ωA+ωB=1，建立單目標(biāo)優(yōu)化模型(M-2)：

式（11）中maxZ表示綜合甲乙雙方對對方主體的匹配度達(dá)到最大值。

模型(M-2)可使用支持線性優(yōu)化的優(yōu)化軟件包進(jìn)行求解，如Matlab、Lingo11。

定理1優(yōu)化模型(M-2)存在最優(yōu)解。

證明由于求解目標(biāo)為0,1 變量，故可將模型(M-2)轉(zhuǎn)化為指派問題，并用匈牙利算法求解。由模型可知，式（11）自變量數(shù)目為mn，故至多出現(xiàn)2mn個解。顯然，匹配方案i=1,2,…,m；j=1,2,…,n，為目標(biāo)函數(shù)的可行解，故模型(M-2)的可行域非空，則在該可行域中，必能在某處取值使得式（11）目標(biāo)函數(shù)達(dá)到最大值，取得最優(yōu)解，證畢。

綜上，給出語言環(huán)境下主體存在容忍區(qū)間的有差異雙邊匹配決策方法的計算步驟：

步驟1利用式（1）～（4）計算各準(zhǔn)則下評價值對應(yīng)的匹配度。

步驟2利用式（5）～（6）將各準(zhǔn)則下的匹配度集結(jié)為總匹配度并構(gòu)建總匹配度矩陣和。

步驟3基于總匹配度矩陣建立多目標(biāo)優(yōu)化模型(M-1)。

步驟4將多目標(biāo)優(yōu)化模型(M-1)轉(zhuǎn)化為單目標(biāo)優(yōu)化模型(M-2)。

步驟5求解單目標(biāo)優(yōu)化模型(M-2)得到最優(yōu)匹配方案。

3 算例分析

株洲一婚介所對3 位女士(A1,A2,A3)和4 位男士(B1,B2,B3,B4)作婚姻匹配，雙方共同考慮的準(zhǔn)則有家境C1、年收入C2及相貌C3。其中C1、C2、C3的準(zhǔn)則評價值均包含在7 粒度的語言標(biāo)度S7，假設(shè)準(zhǔn)則權(quán)重向量為W=(0.3,0.4,0.3)T，顯然3 個準(zhǔn)則都為效益型準(zhǔn)則。由于甲方主體和乙方主體的準(zhǔn)則集合相同，將和同時表示為，α=3。男士對女士給出的評價值矩陣和容忍區(qū)間如表1所示；女士對男士給出的評價值矩陣如表2所示，與RB相對應(yīng)的容忍區(qū)間如表3所示。

表1 評價值矩陣RA 和相應(yīng)容忍區(qū)間Table 1 Evaluation matrix RA with its related tolerance interval

表2 評價值矩陣RBTable 2 Evaluation matrix RB

表3 與RB 相對應(yīng)的容忍區(qū)間Table 3 Tolerance interval related to RB

以下利用本文提出的雙邊匹配決策方法求解匹配結(jié)果。

步驟1利用式（1）和式（2）計算各準(zhǔn)則下評價值對應(yīng)的匹配度。各準(zhǔn)則下男士對女士的評價值對應(yīng)的匹配度和各準(zhǔn)則下女士對男士的評價值對應(yīng)的匹配度可分別由表4和表5表示。

表4 各準(zhǔn)則下男士對女士的評價值對應(yīng)的匹配度Table 4 Matching degrees of evaluations of females given by males under each criteria

表5 各準(zhǔn)則下女士對男士的評價值對應(yīng)的匹配度Table 5 Matching degrees of evaluations of males given by females under each criteria

步驟2利用式（5）和式（6）將各準(zhǔn)則下的匹配度集結(jié)為總匹配度。男士對女士的匹配度和女士對男士的匹配度可分別由表6和表7表示。

表6 男士對女士的匹配度Table 6 Matching degrees of females give by males

表7 女士對男士的匹配度Table 7 Matching degrees of males give by females

步驟3基于表6和表7所示數(shù)據(jù)建立多目標(biāo)優(yōu)化模型(M-1)。

步驟4由于婚介所未給出對男方和女方的偏好信息，故ωA=ωB=0.5，將多目標(biāo)優(yōu)化模型(M-1)轉(zhuǎn)化為單目標(biāo)優(yōu)化模型(M-2)。

步驟5求解單目標(biāo)優(yōu)化模型(M-2)得到匹配結(jié)果x11=1，x23=1，x32=1，即最優(yōu)匹配方案為{(A1,B1)，(A2,B3)，(A3,B2)}，B4無匹配對象。

4 對比分析

文獻(xiàn)[17]認(rèn)為評價值對應(yīng)的匹配度只能為0 或1，即期望區(qū)間內(nèi)的評價值對應(yīng)的匹配度為1 而期望區(qū)間外的評價值對應(yīng)的匹配度為0，然而在考慮效益型準(zhǔn)則和成本型準(zhǔn)則后，本文指出：在效益型準(zhǔn)則下，大于期望區(qū)間的評價值對應(yīng)的匹配度應(yīng)大于期望區(qū)間中的評價值對應(yīng)的匹配度；在成本型準(zhǔn)則下，小于期望區(qū)間的評價值對應(yīng)的匹配度應(yīng)大于期望區(qū)間中的評價值對應(yīng)的匹配度。效益型準(zhǔn)則下，文獻(xiàn)[17]中主體給出的期望區(qū)間在本文中可視為容忍區(qū)間右端點至語言標(biāo)度中最大語言術(shù)語的左開右閉區(qū)間，相對地，成本型準(zhǔn)則下[17]中主體給出的期望區(qū)間在本文中可視為容忍區(qū)間左端點至語言標(biāo)度中最小語言術(shù)語的左閉右開區(qū)間，故容忍區(qū)間將語言標(biāo)度區(qū)分為了3 個有差異的區(qū)間，每個區(qū)間評價值對應(yīng)的匹配度不同。為研究[17]提出的雙邊匹配決策方法與此研究所提出的雙邊匹配決策方法有何異同，假定在此研究的實例中，容忍區(qū)間中的評價值對應(yīng)的匹配度為1，對應(yīng)于文獻(xiàn)[17]為期望區(qū)間中的評價值對應(yīng)的匹配度為1，且雙方主體的權(quán)重保持均等，則得到最優(yōu)匹配方案{(A1,B3)，(A2,B1)，(A3,B2)}，B4無匹配對象。

在匹配度修改處理后，A1的匹配對象由B1變?yōu)锽3，A2的匹配對象由B3變?yōu)锽1，不難發(fā)現(xiàn)，在表3和表4與A1，B3二者相關(guān)的匹配度中，匹配度0.5出現(xiàn)的次數(shù)較多，與A2，B1二者相關(guān)的匹配度中，匹配度0.5 出現(xiàn)的次數(shù)同樣較多，在將匹配度0.5 修改為1 后，對（A1,B3）和（A2,B1）兩組主體的匹配傾向起到了放大作用。雖然整體來看，在將匹配度0.5修改為1 后，對所有主體的匹配傾向都起到了放大作用，但是對（A1,B3）和（A2,B1）兩組主體的匹配傾向的放大作用要高于其他任意兩組主體的匹配傾向放大作用，這就導(dǎo)致了最優(yōu)匹配結(jié)果的改變。

5 結(jié)語

無差異雙邊匹配決策方法利用期望區(qū)間將評價值信息總區(qū)間劃分為兩個具有不同匹配度的區(qū)間，本文指出該方法在效益型準(zhǔn)則和成本型準(zhǔn)則的情形下不適用，然后提出容忍區(qū)間，在語言環(huán)境下指出容忍區(qū)間內(nèi)的評價值對應(yīng)的匹配度為0.5，將語言標(biāo)度劃分為3 個不同的區(qū)間，分別針對3 個區(qū)間的評價值定義匹配度，體現(xiàn)不同區(qū)間中評價值的差異性。在容忍區(qū)間和匹配度的基礎(chǔ)上，本文提出了一種有差異雙邊匹配決策方法。最后，本文將所提出的有差異雙邊匹配決策方法與無差異雙邊匹配決策方法進(jìn)行了對比與分析，指出本文所提出的方法適用性更廣泛。