考虑稳定匹配条件的双边满意匹配决策方法.docx

该【考虑稳定匹配条件的双边满意匹配决策方法 】是由【科技星球】上传分享，文档一共【19】页，该文档可以免费在线阅读，需要了解更多关于【考虑稳定匹配条件的双边满意匹配决策方法 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。考虑稳定匹配条件的双边满意匹配决策方法??樊治平,李铭洋,2,乐琦(,辽宁沈阳110819;,辽宁沈阳110142;,江西南昌330013)考虑稳定匹配条件的双边满意匹配决策方法樊治平1,李铭洋1,2,乐琦3(,辽宁沈阳110819;,辽宁沈阳110142;,江西南昌330013)双边匹配问题是指如何在两个不相交的主体集合中依据各主体针对潜在匹配对象给出的偏好信息来确定合适的匹配结果,其在经济管理领域中存在着大量的实际背景,是许多学者关注的研究课题。在本文中,针对双边主体给出偏好序值信息的双边匹配问题,给出了一种考虑稳定匹配条件的双边满意匹配决策方法。首先给出了双边匹配、稳定匹配和满意匹配的相关概念;然后考虑到稳定匹配条件,并以双边主体满意度最大为目标,构建了多目标双边匹配优化模型;进一步地,采用线性加权法将多目标优化模型转换为单目标优化模型,并通过求解优化模型来获得最优匹配结果。最后,通过一个算例说明了本文提出方法的实用性和有效性。双边匹配;序值;稳定匹配;满意度;满意匹配;优化模型1引言最早的双边匹配问题研究是Gale和Shapley[1]针对男女婚姻匹配问题进行了研究。之后,有关双边匹配问题的研究得到了许多学者的关注[2-14]。特别是近年来,可以看到一些具有实际背景的双边匹配问题研究,如电子商务环境下的供需双边匹配[2-3]、人力资源管理中员工与岗位的匹配[4-5]、广告代理商与广告客户的匹配[6]、风险投资商与风险企业的匹配[7]等。在双边匹配问题研究中,关于双边给出偏好序值(或序)信息的双边匹配方法研究,一直是学者们多年来关注的研究重点[8-16]。针对这方面的研究,Gale和Shapley[1]最早提出了男女婚姻稳定匹配的概念,并给出了获得男方或女方最优稳定匹配结果的求解算法;Roth[8]针对婚姻匹配问题研究给出了具有一般意义的双边匹配概念;McVitie和Wilson[9-10]给出了一种基于“BreakmarriageOperation”的递归算法来获得婚姻匹配的全部稳定匹配解,同时又研究了男女双方人数不相等情形的婚姻匹配问题,并给出了有针对性的稳定匹配概念和求解算法;Halldórsson等[11]针对具有不完全或无差异偏好序值信息的稳定婚姻问题研究,给出一个随机逼近算法;Vate和John[12]以及Roth等[13]通过构建并求解考虑稳定匹配约束条件的线性规划模型来得到男方或女方最优稳定匹配结果;还有一些学者着重研究了考虑不完全或无差异偏好序值信息的双边稳定匹配算法的复杂性[14-16]。需要指出的是,已有的研究成果大多是基于稳定匹配的视角,求出一方或双方偏好序值之和最小的稳定匹配结果[9-13],而这种做法的实质是假设主体对于匹配结果的满意程度与偏好序值呈逆线性关系,这在一些现实匹配问题中显得不尽合理。例如在婚姻匹配问题中,某男士对8位女士进行排序,该男士对排名第1与排名第2的两位女士之间满意程度的差距,通常要比排名第7和排名第8的两位女士之间的差距要大。因此,如何刻画在双边匹配中双方主体的满意度,进而获得“既稳定、又满意”的匹配结果是一个值得深入研究的问题。鉴于此,本文针对双边主体给出偏好序值信息的双边匹配问题,给出一种考虑稳定匹配条件的满意双边匹配决策方法。给出的方法是基于与已有方法不同的研究视角,即基于满意匹配的研究视角来解决双边匹配问题,通过对双边匹配中双方主体满意度的刻画,构建考虑稳定匹配约束条件的双边满意匹配优化模型,求得同时兼顾了“稳定”和“满意”两种要求的双边匹配结果。={1,2,…,m},J={1,2,…,n},且不妨设m≤n。设甲方主体集合为A={A1,A2,…,Am},其中Ai表示第i个甲方主体,i∈I;乙方主体集合为B={B1,B2,…,Bn},其中Bj表示第j个乙方主体,j∈J。依据文献[17-19],下面给出关于双边匹配的定义。定义1一一映射μ:A∪B→A∪B称为双边匹配,当且仅当?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)。根据以上描述,双边匹配问题如图1所示。在双边匹配μ中,由于m≤n,因此,针对甲方主体集合A中的每一个主体Ai,乙方主体集合中都存在不同的主体Bj与之构成一个μ-匹配主体对,且乙方主体集合中有n-m个主体未匹配。图1双边匹配问题示意图对于主体A1,可在B中全部的n个主体中选择一个与其构成匹配主体对;在A1确定好匹配对象之后,对于主体A2,可在B中剩余的n-1个主体中选择一个与其构成匹配主体对;以此类推,对于主体Am,在其余的m-1个甲方主体确定好匹配对象之后,可在B中剩余的n-m+1个主体中选择一个与其构成匹配主体对。因此,对于考虑的双边匹配问题,共有n(n-1)…(n-m+1)种可能的双边匹配。为分析方便,记γ=n(n-1)…(n-m+1),所有双边匹配构成的集合记为HT={μ1,μ2,…,μγ},其中μk表示第k个双边匹配(k∈{1,2,…,γ})。双边匹配决策就是依据某种准则在双边匹配集合HT中找到合适的双边匹配μ,以尽量满足双方主体的需求或要求。,假设甲方主体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。下面给出关于稳定匹配的定义[1,17-19]。定义2对于双边匹配μ,若以下两种情况均未出现:(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,则称μ为稳定匹配,即μ为具有稳定性的匹配,否则称μ为不稳定匹配。可以看出,满足定义2中情况(1)或(2)的主体对(Ai,Bj),会使双边匹配μ不稳定,这是因为主体Ai与Bj相互间都认为对方要优于目前所匹配的主体,此时称主体对(Ai,Bj)为μ-阻碍稳定对[1,17-19]。为了理解稳定匹配的实际含义,下面举例说明。例1在婚姻匹配问题中,设男士集合为A={A1,A2,A3},女士集合为B={B1,B2,B3,B4},男方针对女方给出偏好信息的序值矩阵为R,女方针对男方给出偏好信息的序值矩阵为T,R和T分别为进一步地,给出如下3个双边匹配:那么,依据定义2可知:双边匹配μ1是不稳定匹配,这是因为对于μ1,主体对(A3,B3)为μ-阻碍稳定对,在A3给出的序值中,r33<r34,即A3认为B3要优于目前所匹配的主体B4,而B4又未匹配,符合定义2中的情况(2);双边匹配μ2和μ3均为稳定匹配,这是因为对于μ2和μ3都不存在μ-阻碍稳定对。基于上述分析可知,对于一个现实的双边匹配问题,一般会同时存在多个稳定匹配,如何刻画这些双边匹配的“优劣”是一个需要关注的问题。为此,下面给出关于满意匹配的相关概念。,但在现实中,偏好序值的增加(减小)与满意程度的降低(增加)之间不一定呈线性关系。这里,为了更好地刻画一方主体对另一方主体的满意程度,给出关于满意度的定义如下:定义3设κij为甲方主体Ai对乙方主体Bj的满意度,βij为乙方主体Bj对甲方主体Ai的满意度,则满意度κij与βij可分别表示为:其中,φ(·)为严格单调递减函数,满足φ(·)>0,φ(1)=1。注1在定义3中,函数φ(·)可以是多种表示形式,若考虑主体的心理感受或心理因素,则φ(·)还应满足φ″(·)>0。本文考虑给出如下形式:依据式(1)-(3),可将偏好序值rij与tij转化为满意度κij与βij(i∈I;j∈J),进而构建甲方主体满意度矩阵=[κij]m×n与乙方主体满意度矩阵=[βij]m×n。定义4设μ=μ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设H={μ1,μ2…,μg}为甲方主体集合A与乙方主体集合B之间的任一双边匹配集合,若则称匹配μA为H中的甲方满意匹配;若},μB∈H,则称匹配μB为H中的乙方满意匹配;若φ(μ*)=max{φ(μ1),φ(μ2),…,φ(μg)},μ*∈H,则称匹配μ*为H中的双方满意匹配。(3)双方主体的满意度之和为双边匹配μ的双方总体满意度,记为φ(μ),即:,获得稳定匹配结果是有其现实意义的[20-22],这是因为:若匹配结果是不稳定的,则存在两个未匹配的主体,他们相互之间的偏好程度均优于目前所匹配的主体,换句话说,他们有着放弃目前所匹配的主体而相互匹配在一起的“动机”。因此,结合实际双边匹配问题的要求,在稳定匹配集合中依据满意度最大化的原则寻求相应的匹配结果是比较合理的。这样,本文要解决的问题就是:依据甲乙双方给出的偏好序值矩阵R和T,通过某种决策方法,在稳定匹配集合中依据一定准则获得尽可能使双方主体满意程度高的匹配结果。为了求解上述问题,引入0-1变量xij,其中:易见,对于甲乙双方主体数目分别为m与n的双边匹配问题,稳定匹配约束条件共有mn个。这里,仍以例1为例进行阐释,由于m=3和n=4,故稳定匹配约束条件有12个,即:为了更好地说明稳定匹配约束条件的确定方法,这里以上述稳定匹配约束条件中第1个约束条件“x11+x21≥1”为例进行说明:考虑到r11=1,可知不存在r1k(k=2,3,4),使得r1k<r11,又因为1=t21<t11=2,因此,根据式(8)可知,主体对(A1,B1)的稳定性约束条件为x11+x21≥1;其余的11个稳定匹配约束条件亦可通过同样的方法获得。进一步地,在考虑稳定匹配条件的情况下,以甲、乙各方总体满意度最大为目标,可建立如下多目标优化模型:依据式(7),可构建一个匹配矩阵X=[xij]m×n。根据定义2可知,在稳定匹配μ中,若μ(Ai)≠Bj,则以下两个条件至少满足其一:(1)μ(Ai)=Bk,其中Bk∈B,rik<rij(2)μ(Al)=Bj,其中Al∈A,tlj<tij否则(Ai,Bj)就构成一个μ-阻碍稳定对。考虑稳定匹配的约束条件可表示为[12-13]:在模型(9)中,式(9a)和式(9b)为目标函数,其含义分别是尽可能使双边匹配μ的甲方总体满意度和乙方总体满意度最大。式(9c)和式(9d)为双边匹配的约束条件,由于m≤n,故式(9c)为等式约束,其含义是每个甲方主体都必须与一个乙方主体匹配;式(9d)为不等式约束,其含义是每个乙方主体最多与一个甲方主体匹配;换句话说,在匹配矩阵X中,每行中有一个元素为1,其余元素为0;每列中最多有一个元素为1,其余元素为0。式(9e)为稳定匹配约束条件,其确保了通过求解模型(9)获得的匹配结果为稳定匹配。(9),采用线性加权法[23],将式(9a)和式(9b)进行加权。设w1和w2分别表示目标Z1和Z2的权重或重要程度,满足0≤w1,w2≤1,w1+w2=1,则模型(9)可转化为如下单目标优化模型:对于模型(10),有如下结论。定理1模型(10)存在最优解。证明:由于模型(10)为含有mn个变量的0-1规划模型,故其最多具有2mn个可行解,即模型(10)的可行解为有限多个。依据Gale等[1]可知,本文考虑的双边匹配问题必存在稳定匹配解,故由式(10b)-(10e)构成的可行域非空,即模型(10)至少存在一个可行解。因此,模型(10)必存在最优解。模型(10)中目标函数和约束条件均是线性的,因此可采用整数规划方法进行求解[24]。考虑到现实中基于偏好序值信息的双边匹配问题规模一般不是很