樊治平，李銘洋，2，樂 琦

（1.東北大學(xué)工商管理學(xué)院，遼寧沈陽110819；2.沈陽化工大學(xué)數(shù)理系，遼寧沈陽110142；3.江西財經(jīng)大學(xué)信息管理學(xué)院，江西南昌330013）

考慮穩(wěn)定匹配條件的雙邊滿意匹配決策方法

樊治平1，李銘洋1，2，樂 琦3

（1.東北大學(xué)工商管理學(xué)院，遼寧沈陽110819；2.沈陽化工大學(xué)數(shù)理系，遼寧沈陽110142；3.江西財經(jīng)大學(xué)信息管理學(xué)院，江西南昌330013）

雙邊匹配問題是指如何在兩個不相交的主體集合中依據(jù)各主體針對潛在匹配對象給出的偏好信息來確定合適的匹配結(jié)果，其在經(jīng)濟(jì)管理領(lǐng)域中存在著大量的實際背景，是許多學(xué)者關(guān)注的研究課題。在本文中，針對雙邊主體給出偏好序值信息的雙邊匹配問題，給出了一種考慮穩(wěn)定匹配條件的雙邊滿意匹配決策方法。首先給出了雙邊匹配、穩(wěn)定匹配和滿意匹配的相關(guān)概念；然后考慮到穩(wěn)定匹配條件，并以雙邊主體滿意度最大為目標(biāo)，構(gòu)建了多目標(biāo)雙邊匹配優(yōu)化模型；進(jìn)一步地，采用線性加權(quán)法將多目標(biāo)優(yōu)化模型轉(zhuǎn)換為單目標(biāo)優(yōu)化模型，并通過求解優(yōu)化模型來獲得最優(yōu)匹配結(jié)果。最后，通過一個算例說明了本文提出方法的實用性和有效性。

雙邊匹配；序值；穩(wěn)定匹配；滿意度；滿意匹配；優(yōu)化模型

1 引言

最早的雙邊匹配問題研究是Gale和Shapley［1］針對男女婚姻匹配問題進(jìn)行了研究。之后，有關(guān)雙邊匹配問題的研究得到了許多學(xué)者的關(guān)注［2-14］。特別是近年來，可以看到一些具有實際背景的雙邊匹配問題研究，如電子商務(wù)環(huán)境下的供需雙邊匹配［2-3］、人力資源管理中員工與崗位的匹配［4-5］、廣告代理商與廣告客戶的匹配［6］、風(fēng)險投資商與風(fēng)險企業(yè)的匹配［7］等。在雙邊匹配問題研究中，關(guān)于雙邊給出偏好序值（或序）信息的雙邊匹配方法研究，一直是學(xué)者們多年來關(guān)注的研究重點(diǎn)［8-16］。針對這方面的研究，Gale和Shapley［1］最早提出了男女婚姻穩(wěn)定匹配的概念，并給出了獲得男方或女方最優(yōu)穩(wěn)定匹配結(jié)果的求解算法；Roth［8］針對婚姻匹配問題研究給出了具有一般意義的雙邊匹配概念；Mc Vitie和Wilson［9-10］給出了一種基于“Breakmarriage Operation”的遞歸算法來獲得婚姻匹配的全部穩(wěn)定匹配解，同時又研究了男女雙方人數(shù)不相等情形的婚姻匹配問題，并給出了有針對性的穩(wěn)定匹配概念和求解算法；Halldórsson等［11］針對具有不完全或無差異偏好序值信息的穩(wěn)定婚姻問題研究，給出一個隨機(jī)逼近算法；Vate和John［12］以及Roth等［13］通過構(gòu)建并求解考慮穩(wěn)定匹配約束條件的線性規(guī)劃模型來得到男方或女方最優(yōu)穩(wěn)定匹配結(jié)果；還有一些學(xué)者著重研究了考慮不完全或無差異偏好序值信息的雙邊穩(wěn)定匹配算法的復(fù)雜性［14-16］。需要指出的是，已有的研究成果大多是基于穩(wěn)定匹配的視角，求出一方或雙方偏好序值之和最小的穩(wěn)定匹配結(jié)果［9-13］，而這種做法的實質(zhì)是假設(shè)主體對于匹配結(jié)果的滿意程度與偏好序值呈逆線性關(guān)系，這在一些現(xiàn)實匹配問題中顯得不盡合理。例如在婚姻匹配問題中，某男士對8位女士進(jìn)行排序，該男士對排名第1與排名第2的兩位女士之間滿意程度的差距，通常要比排名第7和排名第8的兩位女士之間的差距要大。因此，如何刻畫在雙邊匹配中雙方主體的滿意度，進(jìn)而獲得“既穩(wěn)定、又滿意”的匹配結(jié)果是一個值得深入研究的問題。鑒于此，本文針對雙邊主體給出偏好序值信息的雙邊匹配問題，給出一種考慮穩(wěn)定匹配條件的滿意雙邊匹配決策方法。給出的方法是基于與已有方法不同的研究視角，即基于滿意匹配的研究視角來解決雙邊匹配問題，通過對雙邊匹配中雙方主體滿意度的刻畫，構(gòu)建考慮穩(wěn)定匹配約束條件的雙邊滿意匹配優(yōu)化模型，求得同時兼顧了“穩(wěn)定”和“滿意”兩種要求的雙邊匹配結(jié)果。

2 雙邊匹配的相關(guān)概念

2.1 雙邊匹配

記I=｛1，2，…，m｝，J=｛1，2，…，n｝，且不妨設(shè)m≤n。設(shè)甲方主體集合為A=｛A1，A2，…，Am｝，其中Ai表示第i個甲方主體，i∈I；乙方主體集合為B=｛B1，B2，…，Bn｝，其中Bj表示第j個乙方主體，j∈J。依據(jù)文獻(xiàn)［17-19］，下面給出關(guān)于雙邊匹配的定義。

定義1 一一映射μ：A∪B→A∪B稱為雙邊匹配，當(dāng)且僅當(dāng)?Ai∈A、?Bj∈B滿足下列條件：（1）μ（Ai）∈B；（2）μ（Bj）∈A∪Bj；（3）若μ（Ai）=Bj，則μ（Bj）=Ai。

定義1中，μ（Ai）=Bj表示Ai與Bj在μ中匹配，此時稱（Ai，Bj）為μ-匹配主體對。由定義1中的條件（3）可知，若（Ai，Bj）為μ-匹配主體對，則（Bj，Ai）也為μ-匹配主體對。μ（Bj）=Bj表示Bj在μ中未匹配，此時記（Bj，Bj）為μ-匹配主體對。因此，雙邊匹配μ可表示為μ=μt∪μs，其中，μt=｛（Ai，Bf（i））|i=1，…，m｝，μs=｛（Bj，Bj）| j=｛1，…，n｝｛f（1），…，f（m）｝｝，f（i）∈J，且?k，l∈I，k≠l，有f（k）≠f（l）。

根據(jù)以上描述，雙邊匹配問題如圖1所示。在雙邊匹配μ中，由于m≤n，因此，針對甲方主體集合A中的每一個主體Ai，乙方主體集合中都存在不同的主體Bj與之構(gòu)成一個μ-匹配主體對，且乙方主體集合中有n-m個主體未匹配。

圖1 雙邊匹配問題示意圖

對于主體A1，可在B中全部的n個主體中選擇一個與其構(gòu)成匹配主體對；在A1確定好匹配對象之后，對于主體A2，可在B中剩余的n-1個主體中選擇一個與其構(gòu)成匹配主體對；以此類推，對于主體Am，在其余的m-1個甲方主體確定好匹配對象之后，可在B中剩余的n-m+1個主體中選擇一個與其構(gòu)成匹配主體對。因此，對于考慮的雙邊匹配問題，共有n（n-1）…（n-m+1）種可能的雙邊匹配。為分析方便，記γ=n（n-1）…（n-m+1），所有雙邊匹配構(gòu)成的集合記為HT=｛μ1，μ2，…，μγ｝，其中μk表示第k個雙邊匹配（k∈｛1，2，…，γ｝）。雙邊匹配決策就是依據(jù)某種準(zhǔn)則在雙邊匹配集合HT中找到合適的雙邊匹配μ，以盡量滿足雙方主體的需求或要求。

2.2 穩(wěn)定匹配

在考慮的雙邊匹配問題中，假設(shè)甲方主體Ai（i∈I）和乙方主體Bj（j∈J）給出的偏好信息均為序值。記R=［rij］m×n為甲方針對乙方給出偏好信息的序值矩陣，其中rij表示甲方主體Ai把乙方主體Bj排在第rij位，rij∈J；T=［tij］m×n為乙方針對甲方給出偏好信息的序值矩陣，其中tij表示乙方主體Bj把甲方主體Ai排在第tij位，tij∈I。下面給出關(guān)于穩(wěn)定匹配的定義［1，17-19］。

定義2 對于雙邊匹配μ，若以下兩種情況均未出現(xiàn)：

（1）?Ai，Al∈A，Bj，Bk∈B，μ（Ai）=Bk，μ（Al）=Bj，滿足rij＜rik且tij＜tlj；

（2）?Ai，Al∈A，Bj∈B，μ（Ai）=Bk，μ（Bj）=Bj，滿足rij＜rik，

則稱μ為穩(wěn)定匹配，即μ為具有穩(wěn)定性的匹配，否則稱μ為不穩(wěn)定匹配。

可以看出，滿足定義2中情況（1）或（2）的主體對（Ai，Bj），會使雙邊匹配μ不穩(wěn)定，這是因為主體Ai與Bj相互間都認(rèn)為對方要優(yōu)于目前所匹配的主體，此時稱主體對 （Ai，Bj）為μ-阻礙穩(wěn)定對［1，17-19］。

為了理解穩(wěn)定匹配的實際含義，下面舉例說明。

例1 在婚姻匹配問題中，設(shè)男士集合為A=｛A1，A2，A3｝，女士集合為B=｛B1，B2，B3，B4｝，男方針對女方給出偏好信息的序值矩陣為R，女方針對男方給出偏好信息的序值矩陣為T，R和T分別為

進(jìn)一步地，給出如下3個雙邊匹配：

那么，依據(jù)定義2可知：雙邊匹配μ1是不穩(wěn)定匹配，這是因為對于μ1，主體對（A3，B3）為μ-阻礙穩(wěn)定對，在A3給出的序值中，r33＜r34，即A3認(rèn)為B3要優(yōu)于目前所匹配的主體B4，而B4又未匹配，符合定義2中的情況（2）；雙邊匹配μ2和μ3均為穩(wěn)定匹配，這是因為對于μ2和μ3都不存在μ-阻礙穩(wěn)定對。

基于上述分析可知，對于一個現(xiàn)實的雙邊匹配問題，一般會同時存在多個穩(wěn)定匹配，如何刻畫這些雙邊匹配的“優(yōu)劣”是一個需要關(guān)注的問題。為此，下面給出關(guān)于滿意匹配的相關(guān)概念。

2.3 滿意匹配

雙方主體給出的偏好序值信息在一定程度上反映了雙方主體間的相互滿意程度，但在現(xiàn)實中，偏好序值的增加（減小）與滿意程度的降低（增加）之間不一定呈線性關(guān)系。這里，為了更好地刻畫一方主體對另一方主體的滿意程度，給出關(guān)于滿意度的定義如下：

定義3 設(shè)κij為甲方主體Ai對乙方主體Bj的滿意度，βij為乙方主體Bj對甲方主體Ai的滿意度，則滿意度κij與βij可分別表示為：

其中，φ（·）為嚴(yán)格單調(diào)遞減函數(shù)，滿足φ（·）＞0，φ（1）=1。

注1 在定義3中，函數(shù)φ（·）可以是多種表示形式，若考慮主體的心理感受或心理因素，則φ（·）還應(yīng)滿足φ″（·）＞0。本文考慮給出如下形式：

依據(jù)式（1）-（3），可將偏好序值rij與tij轉(zhuǎn)化為滿意度κij與βij（i∈I；j∈J），進(jìn)而構(gòu)建甲方主體滿意度矩陣=［κij］m×n與乙方主體滿意度矩陣=［βij］m×n。

定義4 設(shè)μ=μt∪μs為甲方主體集合A與乙方主體集合B之間的雙邊匹配，其中μt=｛（Ai，Bf（i））|i∈I，f（i）∈J｝，μs=｛（Bj，Bj）|j=｛1，…，n｝｛f（1），…，f（m）｝｝，則稱：

（1）甲方主體A1，A2，…，Am的滿意度之和為雙邊匹配μ的甲方總體滿意度，記為φ～（μ），即：

（2）乙方主體Bf（1），Bf（2），…，Bf（m）的滿意度之和為雙邊匹配μ的乙方總體滿意度，記為φ~～（μ），即：

定義5 設(shè)H=｛μ1，μ2…，μg｝為甲方主體集合A與乙方主體集合B之間的任一雙邊匹配集合，若則稱匹配μA為H中的甲方滿意匹配；若｝，μB∈H，則稱匹配μB為 H中的乙方滿意匹配；若φ（μ*）= max｛φ（μ1），φ（μ2），…，φ（μg）｝，μ*∈H，則稱匹配μ*為H中的雙方滿意匹配。

（3）雙方主體的滿意度之和為雙邊匹配μ的雙方總體滿意度，記為φ（μ），即：

3 雙邊匹配決策方法

3.1 優(yōu)化模型建立

在考慮的基于偏好序值信息的雙邊匹配問題中，獲得穩(wěn)定匹配結(jié)果是有其現(xiàn)實意義的［20-22］，這是因為：若匹配結(jié)果是不穩(wěn)定的，則存在兩個未匹配的主體，他們相互之間的偏好程度均優(yōu)于目前所匹配的主體，換句話說，他們有著放棄目前所匹配的主體而相互匹配在一起的“動機(jī)”。因此，結(jié)合實際雙邊匹配問題的要求，在穩(wěn)定匹配集合中依據(jù)滿意度最大化的原則尋求相應(yīng)的匹配結(jié)果是比較合理的。這樣，本文要解決的問題就是：依據(jù)甲乙雙方給出的偏好序值矩陣R和T，通過某種決策方法，在穩(wěn)定匹配集合中依據(jù)一定準(zhǔn)則獲得盡可能使雙方主體滿意程度高的匹配結(jié)果。

為了求解上述問題，引入0-1變量xij，其中：

易見，對于甲乙雙方主體數(shù)目分別為m與n的雙邊匹配問題，穩(wěn)定匹配約束條件共有mn個。這里，仍以例1為例進(jìn)行闡釋，由于m=3和n=4，故穩(wěn)定匹配約束條件有12個，即：

為了更好地說明穩(wěn)定匹配約束條件的確定方法，這里以上述穩(wěn)定匹配約束條件中第1個約束條件“x11+x21≥1”為例進(jìn)行說明：考慮到r11=1，可知不存在r1k（k=2，3，4），使得r1k＜r11，又因為1=t21＜t11=2，因此，根據(jù)式（8）可知，主體對（A1，B1）的穩(wěn)定性約束條件為x11+x21≥1；其余的11個穩(wěn)定匹配約束條件亦可通過同樣的方法獲得。

進(jìn)一步地，在考慮穩(wěn)定匹配條件的情況下，以甲、乙各方總體滿意度最大為目標(biāo)，可建立如下多目標(biāo)優(yōu)化模型：

依據(jù)式（7），可構(gòu)建一個匹配矩陣X=［xij］m×n。

根據(jù)定義2可知，在穩(wěn)定匹配μ中，若μ（Ai）≠Bj，則以下兩個條件至少滿足其一：

（1）μ（Ai）=Bk，其中Bk∈B，rik＜rij

（2）μ（Al）=Bj，其中Al∈A，tlj＜tij

否則（Ai，Bj）就構(gòu)成一個μ-阻礙穩(wěn)定對。

考慮穩(wěn)定匹配的約束條件可表示為［12-13］：在模型（9）中，式（9a）和式（9b）為目標(biāo)函數(shù)，其含義分別是盡可能使雙邊匹配μ的甲方總體滿意度和乙方總體滿意度最大。式（9c）和式（9d）為雙邊匹配的約束條件，由于m≤n，故式（9c）為等式約束，其含義是每個甲方主體都必須與一個乙方主體匹配；式（9d）為不等式約束，其含義是每個乙方主體最多與一個甲方主體匹配；換句話說，在匹配矩陣X中，每行中有一個元素為1，其余元素為0；每列中最多有一個元素為1，其余元素為0。式（9e）為穩(wěn)定匹配約束條件，其確保了通過求解模型（9）獲得的匹配結(jié)果為穩(wěn)定匹配。

3.2 模型求解

為求解上述多目標(biāo)優(yōu)化模型（9），采用線性加權(quán)法［23］，將式（9a）和式（9b）進(jìn)行加權(quán)。設(shè)w1和w2分別表示目標(biāo)Z1和Z2的權(quán)重或重要程度，滿足0≤w1，w2≤1，w1+w2=1，則模型（9）可轉(zhuǎn)化為如下單目標(biāo)優(yōu)化模型：

對于模型（10），有如下結(jié)論。

定理1 模型（10）存在最優(yōu)解。

證明：由于模型（10）為含有mn個變量的0-1規(guī)劃模型，故其最多具有2mn個可行解，即模型（10）的可行解為有限多個。依據(jù)Gale等［1］可知，本文考慮的雙邊匹配問題必存在穩(wěn)定匹配解，故由式（10b）-（10e）構(gòu)成的可行域非空，即模型（10）至少存在一個可行解。因此，模型（10）必存在最優(yōu)解。

模型（10）中目標(biāo)函數(shù)和約束條件均是線性的，因此可采用整數(shù)規(guī)劃方法進(jìn)行求解［24］?？紤]到現(xiàn)實中基于偏好序值信息的雙邊匹配問題規(guī)模一般不是很大，即雙邊主體的數(shù)目一般不是很多，所以針對變量數(shù)目不是很多情形的模型（10），可以使用專門的優(yōu)化軟件包進(jìn)行求解，如可以使用LINGO11.0、Cplex9.0等優(yōu)化軟件包求解模型（10）。若雙邊匹配問題的規(guī)模較大，可進(jìn)行優(yōu)化模型的復(fù)雜性分析，進(jìn)而嘗試設(shè)計啟發(fā)式方法或遺傳算法等求解模型（10）。

綜上，求解基于偏好序值信息的雙邊匹配問題的計算步驟如下：

步驟1 依據(jù)式（1）和（3），將序值rij轉(zhuǎn)化為滿意度κij，并構(gòu)建甲方主體滿意度矩陣=［κij］m×n；

步驟2 依據(jù)式（2）和（3），將序值tij轉(zhuǎn)化為滿意度βij，并構(gòu)建乙方主體滿意度矩陣=［βij］m×n；

步驟4 使用線性加權(quán)法將優(yōu)化模型（9）轉(zhuǎn)化為優(yōu)化模型（10）；

步驟5 求解優(yōu)化模型（10），獲得匹配結(jié)果。

4 算例分析

考慮一個現(xiàn)實中的求職者與崗位的雙邊匹配問題。MC公司是一家期貨經(jīng)紀(jì)公司，主要從事期貨交易咨詢、代理買賣期貨合約等業(yè)務(wù)。該公司在最新的一批人員招聘中，擬針對5個空缺的管理崗位（A1，A2，…，A5）進(jìn)行招聘?，F(xiàn)有多名求職者前來應(yīng)聘，經(jīng)過初篩之后，有7名求職者（B1，B2，…，B7）符合該公司的各項基本要求，從而進(jìn)入了最終的面試考核環(huán)節(jié)。在對7名求職者進(jìn)行面試之后，該公司的人力資源部門從性格、管理經(jīng)驗、專業(yè)能力、溝通能力以及團(tuán)隊合作能力等5個指標(biāo)對各個求職者進(jìn)行評價，給出各崗位針對不同求職者的偏好序值rij，i=1，2，…，5，j=1，2，…，7。各求職者從薪水和福利、發(fā)展前景、勞動強(qiáng)度以及工作環(huán)境等4個指標(biāo)對不同崗位進(jìn)行評價，給出各求職者針對不同崗位的偏好序值tij，i=1，2，…，5，j=1，2，…，7。記R=［rij］5×7表示崗位針對求職者的偏好序值矩陣，T=［tij］5×7表示求職者針對崗位的偏好序值矩陣，假設(shè)R和T分別為：

為了獲得求職者與崗位的雙邊匹配結(jié)果，下面簡要說明采用前文給出方法的部分計算過程及結(jié)果。

依據(jù)偏好序值矩陣R和T，運(yùn)用式（1）-（3），計算滿意度κij和βij（i=1，…，5；j=1，…，7），并構(gòu)建滿意度矩陣=［κij］5×7與=［βij］5×7如下：

使用LINGO11.0軟件包求解上述模型，可得匹配矩陣為：

此時目標(biāo)值為Z*=3.14，得到的最優(yōu)匹配結(jié)果為：

即A1與B1匹配、A2與B3匹配、A3與B2匹配、A4與B4匹配、A5與B7匹配、B5和B6未匹配。

為進(jìn)一步說明穩(wěn)定匹配的意義，給出如下分析。

在本例中，若不考慮雙邊匹配穩(wěn)定性，即在上述模型中不考慮穩(wěn)定匹配約束條件，那么通過模型求解可得匹配矩陣為：

此時目標(biāo)值為Z′=3.35，得到的匹配結(jié)果為

μ′=｛（A1，B1），（A2，B5），（A3，B2），（A4，B4），（A5，B7），（B3，B3），（B6，B6）｝

即A1與B1匹配、A2與B5匹配、A3與B2匹配、A4與B4匹配、A5與B7匹配、B3和B6未匹配。

將上述兩個匹配結(jié)果進(jìn)行對比分析，可以看到，雖然匹配μ′比匹配μ*的雙方總體滿意度高，但μ′卻是不穩(wěn)定匹配，主體對（A2，B3）為μ-阻礙穩(wěn)定對，這是因為r23=3＜4=r25，即該公司認(rèn)為求職者B3相比B5來說更適合崗位A2，而B3卻未匹配。換句話說，在信息透明的情況下，若按照μ′來確定崗位錄用結(jié)果，B3會因為自己比B5更適合崗位A2卻未被錄用而不滿，公司也會因崗位A2未錄用比B5更好的員工B3而產(chǎn)生不滿。因此，選擇匹配μ*作為最優(yōu)匹配結(jié)果，具有較好的現(xiàn)實意義。

5 結(jié)語

本文給出了一種考慮穩(wěn)定匹配條件的滿意雙邊匹配決策方法，該方法是針對雙邊主體給出的偏好序值信息，通過構(gòu)建滿意度函數(shù)來計算匹配滿意度，并在考慮穩(wěn)定匹配條件的前提下，以雙邊主體滿意度最大為目標(biāo)，構(gòu)建了多目標(biāo)雙邊匹配優(yōu)化模型，通過求解優(yōu)化模型可獲得最優(yōu)匹配結(jié)果。與已有的方法相比，本文提出的方法可以求得在穩(wěn)定匹配集合中使雙方主體各自總體滿意度盡可能大的匹配結(jié)果，這樣的匹配結(jié)果在一定程度上兼顧了“穩(wěn)定”和“滿意”兩種要求。本文提出的方法具有較好的理論支撐，具有概念清晰、易操作等特點(diǎn)，也具有實際應(yīng)用價值，為解決基于偏好序值信息的雙邊匹配問題提供了一種新的途徑。

［1］Gale D，Shapley L.College admissions and the stability of marriage［J］.American Mathematical Monthly，1962，69（1）：9-15.

［2］Janssen M，Verbraeck A.Comparing the strengths and weaknesses of Internet-based matching mechanisms for the transport market［J］.Transportation Research Part E，2008，44（3）：475-490.

［3］Sarne D，Kraus S.Managing parallel inquiries in agents'two-sided search［J］.Artificial Intelligence，2008，172（4-5）：541-569.

［4］Lin H T.A job placement intervention using fuzzy approach for two-way choice［J］.Expert Systems with Applications，2009，36（2）：2543-2553.

［5］Huang D K，Chiu H N，Yeh R H，et al.A fuzzy multicriteria decision making approach for solving a bi-objective personnel assignment problem［J］.Computers& Industrial Engineering，2009，56（1）：1-10.

［6］Kaiser U，Wright J.Price structure in two-sided markets：Evidence from the magazine industry［J］.International Journal of Industrial Organization，2006，24（1）：1-28.

［7］Elitzur R，Gavious A.A multi-period game theoretic model of venture capitalists and entrepreneurs［J］.European Journal of Operational Research，2003，144（2）：440-453.

［8］Roth A E.Common and conflicting interests in two-sided matching markets［J］.European Economic Review，1985，27（1）：75-96.

［9］Mc Vitie D G，Wilson L B.The stable marriage problem［J］.Communications of the Association for Computing Machinery，1971，14（7）：486-492.

［10］Mcvitie D G，Wilson L B.Stable marriage assignment for unequal sets［J］.Bit Numerical mathematics，1970，10（3）：295-309.

［11］Halldórsson M M，Iwama K，Miyazaki S，et al.Randomized approximation of the stable marriage problem［J］.Theoretical Computer Science，2004，325（3），439-465.

［12］Vate V，John H.Linear programming brings marital bliss［J］.Operations Research Letters，1989，8（3）：1 -23.

［13］Roth A E，Rothblum U G，John H，et al.Stable matchings，optimal assignments and linear programming［J］.Mathematics of Operations Research，1993，18（4）：803-828.

［14］Iwama K，Manlove D，Miyazaki S，et al.Stable marriage with incomplete lists and ties［C］//Giorgio A，Mariangiola D C，Simonetha R.Proceedings ICALP' 99：The 26th International Colloquium on Automata，Languages，and Programming，Lecture Notes in Computer Science，Springer，Berlin，1999，1644：443-452.

［15］Manlove D F，Irving R W，Iwama K，et al.Hard variants of stable marriage［J］.Theoretical Computer Science，2002，276（1-2）：261-279.

［16］Iwama K，Miyazaki S，Yamauchi N.A（2-c/）-approximation algorithm for the stable marriage problem［J］.Algorithmica，2008，51（3）：342-356.

［17］Teo C P，Sethuraman J，Tan W P.Gale-Shapley stable marriage problem revisited strategic issues and applications［J］.Management Science，2001，47（9）：1252-1267.

［18］Gale D.The two-sided matching problem：Origin，development and current issues［J］.International Game Theory Review，2001，3（2-3）：237-252.

［19］Echenique F.What matchings can be stable？The testable implications of matching theory［J］.Mathematics of Operations Research，2008，33（3）：757-768.

［20］黨興華，賈衛(wèi)峰.GS匹配算法在企業(yè)技術(shù)創(chuàng)新網(wǎng)絡(luò)結(jié)構(gòu)形成中的應(yīng)用［J］.系統(tǒng)工程，2009，27（4）：31-36.

［21］Clark S，Kanbur R.Stable partnerships，matching，and local public goods［J］.European Economic Review，2004，48（4）：905-925.

［22］Alkan A，Gale D.Stable schedule matching under revealed preference［J］.Journal of Economic Theory，2003，112（2）：289-306.

［23］Cohon J L.Multiobjective programming and planning［M］//Mustoe L R，Barry M D J.Mathematics in Science and Engineering，New York：Academic Press，1978.

［24］錢頌迪.運(yùn)籌學(xué)［M］.北京：清華大學(xué)出版社，1996.

Decision Analysis Method for Two-Sided Satisfied Matching Considering Stable Matching Condition

FAN Zhi-ping1，LI Ming-yang1，2，YUE Qi3
（1.School of Business Administration，Northeastern University，Shenyang 110819，China；2.Department of Science，Shenyang University of Chemical Technology，Shenyang 110142，China；3.School of Information Management，Jiangxi University of Finance and Economics，Nanchang 330013，China）

Two-sided matching problem refers to how to obtain proper matching result from two disjoint sets of agents according to the preference information of each agent for potential partners from the opposite set.It is a research topic with extensive practical backgrounds in the field of economic management and attracts the attention of many scholars.In this paper，a decision analysis method for two-sided satisfied matching considering stable matching condition is proposed to solve the two-sided matching problem，in which the preference ordinal numbers are provided by agents on both sides.Firstly，the related concepts on two-sided matching，stable matching and satisfied matching are given.Then，considering the stable matching condition，a multi-objective two-sided matching optimization model which maximizes the satisfaction degrees of two-sided agents is constructed.Furthermore，the linear weighted method is used to convert the multi-objective optimization model into a single-objective optimization model，and the optimal matching result can be obtained by solving the model.Finally，a numerical example is given to illustrate the practicality and effectiveness of the method proposed in this paper.

two-sided matching；ordinal number；stable matching；satisfaction degree；satisfied matching；optimization model

C 934

：A

1003-207（2014）04-0112-07

2012-02-15；

2013-01-22

國家自然科學(xué)基金資助項目（71271051，71371002）；遼寧省高等學(xué)校創(chuàng)新團(tuán)隊支持計劃項目（WT2013004）；中央高校基本科研業(yè)務(wù)費(fèi)專項資金資助項目（N110706001）

樊治平（1961-），男（漢族），江蘇鎮(zhèn)江人，東北大學(xué)工商管理學(xué)院教授，博士生導(dǎo)師，研究方向：運(yùn)作管理與決策分析.