白曉莉,陳巖,2,鄧珍美

(1.沈陽(yáng)工業(yè)大學(xué) 理學(xué)院,遼寧 沈陽(yáng) 110870;2.沈陽(yáng)工業(yè)大學(xué) 管理學(xué)院,遼寧 沈陽(yáng) 110870)

雙邊匹配研究可以追溯于Gale和Shapley[1]在關(guān)于婚姻匹配問(wèn)題中的研究,研究中論證了雙邊穩(wěn)定匹配的存在性以及最優(yōu)性,并提出了著名的Gale-Shapley算法.自此之后,雙邊匹配問(wèn)題的研究不斷涌現(xiàn)于各個(gè)領(lǐng)域.例如,崗位與求職者匹配問(wèn)題[2]、風(fēng)險(xiǎn)投資企業(yè)匹配問(wèn)題[3]、醫(yī)生與患者匹配問(wèn)題[4]、物流服務(wù)供應(yīng)方與需求方匹配問(wèn)題[5]等.隨著社會(huì)的發(fā)展,匹配問(wèn)題背景愈加復(fù)雜,由于評(píng)價(jià)主體受專業(yè)知識(shí)限制,評(píng)價(jià)信息通常具有不確定性.不確定信息下的雙邊匹配問(wèn)題是目前研究的熱點(diǎn),在不確定形式下,主體無(wú)法使用比較精確的數(shù)值進(jìn)行評(píng)價(jià),為了這一問(wèn)題得到解決,學(xué)者們將直覺(jué)模糊、猶豫模糊[6]、區(qū)間猶豫模糊[8]、區(qū)間直覺(jué)模糊[9]、三角模糊[10]等方法引入雙邊匹配問(wèn)題中,并應(yīng)用于各個(gè)領(lǐng)域.但在模糊環(huán)境下進(jìn)行評(píng)價(jià),就意味著主體所提供的語(yǔ)言術(shù)語(yǔ)集的重要程度是一致的.實(shí)際并非如此,主體給出的語(yǔ)言術(shù)語(yǔ)集中的語(yǔ)言術(shù)語(yǔ)不一定是等概率的.在2016年,Pang[11]等學(xué)者們對(duì)猶豫模糊語(yǔ)言術(shù)語(yǔ)集中的每一個(gè)語(yǔ)言項(xiàng)都賦予了概率,定義了概率語(yǔ)言術(shù)語(yǔ)集(PLTS).因此,學(xué)者們開(kāi)始對(duì)概率語(yǔ)言環(huán)境下雙邊匹配問(wèn)題進(jìn)行研究.Li等提出了一種在概率語(yǔ)言環(huán)境下,基于前景理論的屬性權(quán)重未知的雙邊匹配方法.Li等[13]提出了基于概率語(yǔ)言偏好關(guān)系的雙邊匹配方法,其中給出了時(shí)間滿意度的定義,并構(gòu)建模型來(lái)處理概率語(yǔ)言偏好關(guān)系.Li等[14]學(xué)者提出了一種在概率語(yǔ)言術(shù)語(yǔ)集下,考慮最低可接受值的基于后悔理論雙邊匹配決策方法.汪新凡等針對(duì)概率猶豫模糊信息下準(zhǔn)則具有期望水平的雙邊匹配問(wèn)題,提出了一種考慮匹配主體心理行為的雙邊匹配方法.之后就有一些學(xué)者提出匹配主體可能更傾向用類似于[好,非常好]這種語(yǔ)言評(píng)價(jià)區(qū)間的形式來(lái)表達(dá)偏好信息,基于Xu[11]在2004年提出了不確定語(yǔ)言變量(ULV)的概念后,在2017年,由Lin等[17]提出了概率不確定語(yǔ)言術(shù)語(yǔ)集(PULTS)的概念.概率不確定語(yǔ)言術(shù)語(yǔ)集體現(xiàn)不確定語(yǔ)言術(shù)語(yǔ)集的概率特征,是概率語(yǔ)言術(shù)語(yǔ)集與不確定語(yǔ)言術(shù)語(yǔ)的擴(kuò)展形式.但從目前來(lái)看,將概率不確定語(yǔ)言術(shù)語(yǔ)集應(yīng)用于雙邊匹配問(wèn)題中的研究鮮有涉足,并且已有研究大多以設(shè)立參照點(diǎn)獲得主體相對(duì)優(yōu)勢(shì),這會(huì)導(dǎo)致匹配主體評(píng)價(jià)信息的偏差,從而影響匹配結(jié)果.其次,為獲得符合匹配主體偏好的匹配方案,匹配主體在匹配過(guò)程中的心理行為也應(yīng)當(dāng)充分考慮.

因此,本文對(duì)于概率不確定語(yǔ)言環(huán)境下的雙邊匹配問(wèn)題進(jìn)行了研究,并且考慮了主體的心理行為.首先,給出了概率不確定語(yǔ)言術(shù)語(yǔ)集區(qū)間型得分的定義,進(jìn)而根據(jù)可能度公式計(jì)算概率不確定語(yǔ)言術(shù)語(yǔ)集間的可能度,比較概率不確定語(yǔ)言術(shù)語(yǔ)集的優(yōu)劣程度;其次構(gòu)造出優(yōu)先度函數(shù)來(lái)反映匹配主體心理行為;然后,利用新的滿意度公式構(gòu)建滿意度矩陣,建立雙邊匹配滿意度最大化模型,通過(guò)求解模型,獲得最優(yōu)匹配方案;最后,進(jìn)行算例分析,并與現(xiàn)有雙邊匹配方法進(jìn)行比較,證明了所提出方法的優(yōu)點(diǎn).

1 基礎(chǔ)知識(shí)

1.1 不確定語(yǔ)言變量

1.2 概率不確定語(yǔ)言術(shù)語(yǔ)集(PULTS)相關(guān)概念

其中〈[Lk,Uk],pk〉表示不確定語(yǔ)言術(shù)語(yǔ),且[Lk,Uk]的概率為pk,Lk和Uk是語(yǔ)言術(shù)語(yǔ),滿足Lk≤Uk,#S(p)是S(p)的基數(shù).

Lin[17]等學(xué)者給出了概率不確定語(yǔ)言術(shù)語(yǔ)集標(biāo)準(zhǔn)化的方法:

(1)S(p)為任一概率不確定語(yǔ)言術(shù)語(yǔ)集,則已標(biāo)準(zhǔn)化的概率不確定語(yǔ)言術(shù)語(yǔ)集Sn(p)為

(2)如果#S1(p)<#S2(p),則給S1(p)增加具有概率為0的最小不確定語(yǔ)言變量#S2(p)-#S1(p)個(gè),這樣使得兩個(gè)概率不確定語(yǔ)言術(shù)語(yǔ)集的基數(shù)相等.

定義3 設(shè)兩個(gè)標(biāo)準(zhǔn)化概率不確定語(yǔ)言術(shù)語(yǔ)集為

那么它們的運(yùn)算法則為

(3)λS(p)=∪〈[Lk,Uk],pk〉∈S(p){λpk[Lk,Uk]};

(4)(S(p))λ=∪〈[Lk,Uk],pk〉∈S(p){[Lk,Uk]λpk}.

其中λ≥0.

=

為概率不確定語(yǔ)言術(shù)語(yǔ)集平均算子(PULA).

1.3 雙邊匹配

設(shè)雙邊匹配主體集合分別為A={A1,A2,…,Am},B={B1,B2,…,Bn},其中,Ai表示A中的第i個(gè)主體,i∈M,M={1,2,…,m}.Bj表示B中的第j個(gè)主體j∈N,N={1,2,…,n}.一般地,m≥n.

定義5 設(shè)一一映射μ:A∪B→A∪B,若?Ai∈A,?Bj∈B,滿足:

(1)μ(Ai)∈B;

(2)μ(Bj)∈A∪{Bj};

(3)μ(Ai)=Bj當(dāng)且僅當(dāng)μ(Bj)=Ai.

則稱μ為雙邊匹配.其中μ(Ai)=Bj或μ(Bj)=Ai,表示Ai與Bj在μ中匹配,記為(Ai,Bj);μ(Bj)=Bj表示Bj在μ中未匹配,記為(Bj,Bj).

2 優(yōu)先度函數(shù)

2.1 可能度

定義6 對(duì)于任意的概率不確定語(yǔ)言術(shù)語(yǔ)集S(p)={〈[Lk,Uk],pk〉|pk≥0,k=1,2,…,#S(p)},稱

為概率不確定語(yǔ)言術(shù)語(yǔ)集的區(qū)間型得分.

定義7 概率不確定語(yǔ)言術(shù)語(yǔ)集間的可能度定義為:

(1)

①若0.5<ρ(S1(p1)≥S2(p2))≤1時(shí),則S1(p1)優(yōu)于S2(p2),記為S1(p1)?S2(p2);②若ρ(S1(p1)≥S2(p2))=0.5時(shí),則S1(p1)和S2(p2)無(wú)差異,記為S1(p1)～S2(p2);③若0≤ρ(S1(p1)≥S2(p2))<0.5時(shí),則S1(p1)劣于S2(p2),記為S1(p1)S2(p2).

顯然,通過(guò)此公式,不僅能夠反映出概率不確定語(yǔ)言術(shù)語(yǔ)集間“期望”的差異,還可以反映它們之間“方差”的差異;其次,此公式無(wú)需借助像 Lin等學(xué)者提出的雙層比較的方式,就可以進(jìn)行概率不確定語(yǔ)言術(shù)語(yǔ)集間的優(yōu)劣比較,并能度量出兩個(gè)概率不確定語(yǔ)言術(shù)語(yǔ)集間的優(yōu)劣程度.

(1)有界性:0≤ρ(S1(p1)≥S2(p2))≤1;

(2)互補(bǔ)性:ρ(S1(p1)≥S2(p2))+ρ(S2(p2)≥S1(p1))=1;

(3)自反性:當(dāng)S1(p1)=S2(p2)時(shí),ρ(S1(p1)≥S2(p2))=0.5;

(4)傳遞性:ρ(S1(p1)≥S2(p2))≥0.5,ρ(S2(p2)≥S3(p3))≥0.5,則ρ(S1(p1)≥S3(p3))≥0.5.

證明

(1)由定義7可知,可能度滿足0≤ρ(S1(p1)≥S2(p2))≤1.

(2)分兩種情況討論,第一種情況,當(dāng)SL1≥SU2時(shí),ρ(S1(p1)≥S2(p2))=1,而ρ(S2(p2)≥S1(p1))=0,滿足ρ(S1(p1)≥S2(p2))+ρ(S2(p2)≥S1(p1))=1;

(3)根據(jù)公式(1),當(dāng)S1(p1)=S2(p2)時(shí),SL1=SL2,SU1=SU2,因此,ρ(S1(p1)≥S2(p2))=0.5.

(4)ρ(S1(p1)≥S2(p2))≥0.5,ρ(S2(p2)≥S3(p3))≥0.5時(shí),

可以推導(dǎo)出SU1-SL2≥SU2-SL1,SU2-SL3≥SU3-SL2,接著推導(dǎo)出,SU1-SL3≥SU3-SL1,再由公式

因此,ρ(S1(p1)≥S3(p3))≥0.5.

2.2 優(yōu)先度

定義8 設(shè)任意兩個(gè)已標(biāo)準(zhǔn)化的概率不確定語(yǔ)言術(shù)語(yǔ)集為

(2)

其中0≤ρ≤1.

進(jìn)一步說(shuō)明,當(dāng)ρ∈[0,0.5)時(shí),S1(p1)S2(p2),此時(shí)ρ*<0;當(dāng)ρ=0.5時(shí),S1(p1)和S2(p2)無(wú)差異,ρ*=0;

當(dāng)ρ∈(0.5,1]時(shí),S1(p1)?S2(p2),此時(shí)ρ*>0.

(1)-0.5<ρ*(S1(p1)≥S2(p2))<0.5;

(2)互補(bǔ)性:ρ*(S1(p1)≥S2(p2))+ρ*(S2(p2)≥S1(p1))=0;

(3)自反性:當(dāng)S1(p1)=S2(p2)時(shí),ρ*(S1(p1)≥S2(p2))=0;

(4)傳遞性:ρ*(S1(p1)≥S2(p2))≥0,ρ*(S2(p2)≥S3(p3))≥0,則ρ*(S1(p1)≥S3(p3))≥0.

由定理1及證明和公式(2),可證明優(yōu)先度函數(shù)具有以上性質(zhì).

2.3 距離測(cè)度

為了避免匹配主體評(píng)價(jià)信息中偏倚數(shù)據(jù)的影響,根據(jù)區(qū)間型得分,定義了兩個(gè)概率不確定語(yǔ)言術(shù)語(yǔ)集間的距離測(cè)度.

(3)

定理3 給定概率不確定語(yǔ)言術(shù)語(yǔ)集S1(p1),S2(p2),S3(p3),則式(3)滿足:

(1)d(S1(p1),S2(p2))≥0;

(2)d(S1(p1),S2(p2))=d(S2(p2),S1(p1));

(3)d(S1(p1),S2(p2))+d(S2(p2),S3(p3))≥d(S1(p1),S3(p3)).

注:d(S1(p1),S2(p2))=0當(dāng)且僅當(dāng)S1(p1)與S2(p2)相等.

3 基于優(yōu)先度函數(shù)的雙邊匹配模型與方法

3.1 雙邊匹配問(wèn)題描述

3.2 滿意度計(jì)算

雙邊匹配的目標(biāo)是使得雙邊匹配主體滿意度最大,由式(2)、式(3)概率不確定語(yǔ)言術(shù)語(yǔ)集的優(yōu)先度函數(shù)以及距離測(cè)度,在此定義雙邊匹配主體的滿意度.

定義10 設(shè)SdAi→Bj是在屬性Up下,匹配主體Ai對(duì)匹配主體Bj的滿意度,其計(jì)算公式為

(4)

定義11 設(shè)SdBj→Ai是在屬性Vq下,匹配主體Bj對(duì)匹配主體Ai的滿意度,其計(jì)算公式為

(5)

那么,匹配主體Ai對(duì)于Bj的綜合滿意度以及匹配主體Bj對(duì)于Ai的綜合滿意度分別為

(6)

(7)

3.3 雙邊匹配模型

基于以上匹配雙方滿意度矩陣的計(jì)算,建立了匹配雙方滿意度最大化目標(biāo)雙邊匹配模型P1如下:

(8)

(9)

(10)

(11)

其中,xij為0-1變量,xij等于1時(shí),說(shuō)明Ai與Bj匹配,xij等于0時(shí),說(shuō)明Ai與Bj不匹配.式(8)是表示匹配主體A的最大化滿意度,式(9)是表示匹配主體B的最大化滿意度,式(10)表示任一匹配主體A只能與一主體B匹配或不匹配,式(11)表示任一匹配主體B與一匹配主體A匹配.

由于匹配雙方的目標(biāo)函數(shù)是等級(jí)的,因此,通過(guò)線性加權(quán)法可將多目標(biāo)模型P1轉(zhuǎn)化為單目標(biāo)模型P2,分別加權(quán)α和β(0≤α,β≤1,α+β=1).則P2為:

3.4 雙邊匹配方法步驟

基于概率不確定語(yǔ)言術(shù)語(yǔ)集下考慮心理行為的雙邊匹配問(wèn)題,提出了優(yōu)先度函數(shù)和距離測(cè)度,用于構(gòu)造滿意度矩陣,進(jìn)而建立雙邊匹配模型,具體步驟如下:

Step 2 對(duì)評(píng)價(jià)信息進(jìn)行標(biāo)準(zhǔn)化處理,并集結(jié)屬性準(zhǔn)則下的評(píng)價(jià)信息.

Step 3 將已標(biāo)準(zhǔn)化的評(píng)價(jià)信息,根據(jù)定義6和式(1)-(5)求得SdAi→Bj和SdBj→Ai.

Step 4 利用式(6)、(7)得到滿意度aij和bij,進(jìn)而構(gòu)造滿意度矩陣A=[aij]m×n和B=[bij]m×n.

Step 5 構(gòu)建多目標(biāo)模型P1,并將其轉(zhuǎn)化為單目標(biāo)模型P2.

Step 6 用Kuhn-Munkras算法求解模型P2,得到最優(yōu)匹配方案.

4 算例分析

4.1 問(wèn)題描述

某工業(yè)園有3家新進(jìn)企業(yè)需要實(shí)施倉(cāng)儲(chǔ)管理系統(tǒng)(WMS),通過(guò)服務(wù)中介機(jī)構(gòu)投放廣告等相關(guān)信息,有4家軟件供應(yīng)商有合作意向,記為Ai(i=1,2,3,4),這3家軟件需求企業(yè)記為Bj(j=1,2,3),軟件供應(yīng)商Ai對(duì)軟件需求企業(yè)Bj評(píng)價(jià)的參考屬性為U1(系統(tǒng)實(shí)現(xiàn)的收益)、U2(企業(yè)規(guī)模)、U3(發(fā)展前景),加權(quán)向量為

S={s-3:非常差,s-2:較差,s-1:差,s0:中等,s1:好,s2:很好,s3:非常好}.

4.2 求解過(guò)程

Step 1獲得評(píng)價(jià)信息.

表1 在屬性U1下的評(píng)價(jià)信息矩陣

表2 在屬性U2下的評(píng)價(jià)信息矩陣

表3 在屬性U3下的評(píng)價(jià)信息矩陣

表4 在屬性V1下的評(píng)價(jià)信息矩陣

表5 在屬性V2下的評(píng)價(jià)信息矩陣

表6 在屬性V3下的評(píng)價(jià)信息矩陣

Step 2根據(jù)式(1)-(5)分別求得滿意度SdAi→Bj和SdBj→Ai,如下表7、8所示:

表7 Ai對(duì)Bj滿意度矩陣

表8 Bj對(duì)Ai滿意度矩陣

Step 3 利用式(6)、(7)獲得滿意度aij和bij,進(jìn)而構(gòu)造滿意度矩陣A=[aij]4×3和B=[bij]4×3.

Step 4 構(gòu)建多目標(biāo)模型P1,令α=β=0.5,將多目標(biāo)模型P1轉(zhuǎn)化為模型P2.

Step 5 將綜合滿意度作為二分圖匹配中的權(quán)值,用Kuhn-Munkras算法求解模型P2,獲得雙邊匹配矩陣為

所以最優(yōu)匹配方案為{(B1,A2),(B2,A3),(B3,A4)}.

4.3 比較分析

表9 不同匹配方法的對(duì)比

表9顯示,這4種不同的匹配方法所對(duì)應(yīng)的匹配方案存在差異,進(jìn)一步分析存在差異的原因:

文獻(xiàn)[12]、文獻(xiàn)[19]中均應(yīng)用前景理論來(lái)考慮匹配主體心理行為,但前景理論需要考慮雙邊匹配主體的損失規(guī)避系數(shù)、風(fēng)險(xiǎn)厭惡系數(shù)和風(fēng)險(xiǎn)偏好系數(shù),參數(shù)較多,計(jì)算較冗雜,本文的優(yōu)先度不需要考慮參數(shù)的設(shè)置,計(jì)算較簡(jiǎn)潔;文獻(xiàn)[14]中通過(guò)概率語(yǔ)言術(shù)語(yǔ)集期望值與匹配主體評(píng)價(jià)值的方式來(lái)獲得滿意度會(huì)導(dǎo)致綜合滿意度偏高或偏低,從而影響匹配結(jié)果.

文獻(xiàn)[14]的雙邊匹配方案與本文的方案不完全一致,造成這種差異的主要原因:一方面在于文獻(xiàn)[14]構(gòu)建基于期望值的滿意度函數(shù),建立了基于后悔理論的雙邊匹配模型,這樣應(yīng)用期望值會(huì)導(dǎo)致評(píng)價(jià)信息的失真,后悔理論也僅反映了匹配主體的后悔心理;另一方面在于文獻(xiàn)[14]考慮了最低可接受度,但最低可接受度是假設(shè)的虛擬值,選取不同可能會(huì)對(duì)匹配結(jié)果有影響.本文應(yīng)用優(yōu)先度與距離測(cè)量來(lái)獲得滿意度,可以避免信息的失真,從而確保匹配結(jié)果更合理,更準(zhǔn)確.并且參照點(diǎn)設(shè)置為評(píng)價(jià)信息的綜合平均值而不是虛擬值,這樣不但可以集中于原始評(píng)價(jià)信息,而且使計(jì)算更簡(jiǎn)化,本文中提出的優(yōu)先度函數(shù)不同于后悔理論,它能更靈活的反映匹配主體的趨優(yōu)性、規(guī)避劣性的心理行為.

5 結(jié) 論

針對(duì)概率不確定語(yǔ)言環(huán)境下的雙邊匹配問(wèn)題,考慮雙邊主體趨優(yōu)性的心理行為特征,提出了一種基于優(yōu)先度函數(shù)的雙邊匹配方法.(1)定義概率不確定語(yǔ)言術(shù)語(yǔ)集區(qū)間型得分,給出可能度公式,以此把定性信息轉(zhuǎn)化為定量分析,使得匹配結(jié)果更符合匹配雙方主體的預(yù)期.(2)定義的優(yōu)先度函數(shù)和距離測(cè)度為處理概率不確定語(yǔ)言環(huán)境下的雙邊匹配問(wèn)題提供了一種有力工具,有效避免了目前研究中直接應(yīng)用期望值或評(píng)分值的方式來(lái)獲得滿意度所導(dǎo)致的信息失真.(3)定義的優(yōu)先度函數(shù)可以反映主體趨優(yōu)性和規(guī)避劣性的心理行為且不需要考慮參數(shù)的設(shè)置,計(jì)算較簡(jiǎn)潔.