论文研究-具有序区间偏好信息的双边稳定匹配决策方法.pdf

所需积分/C币:22 2019-09-20 20:37:37 688KB .PDF
收藏 收藏
举报

论文研究-具有序区间偏好信息的双边稳定匹配决策方法.pdf,  针对具有序区间偏好信息的双边匹配决策问题,提出了一种新的决策方法.首先,给出了具有序区间偏好信息的双边匹配决策问题的描述,并给出了序区间偏好信息下的可接受对和个体理性匹配的定义;然后,给出了基于可能度的弱稳定匹配、α-稳定匹配、强稳定匹配和超稳定匹配的定义,并分析了各种稳定匹配之间的关系;在此基础上,分别构建了获得弱稳定匹配、α
2154 系统工程理论与实践 第37卷 设甲方主体集合为A={A1,A2,…,Am},其中Az表示第个甲方主体,讠=1,2,……,m;乙方主体集合 为B={B1,B2,…,Bn}其中B,表示第j个乙方主体,=1,2,…,m.本文考虑的是一对一的双边匹配问 题,即一个甲方主体A1最多与一个乙方主体进行匹配,一个乙方主体B;也最多与一个甲方主体进行匹配 设R2=(1,i2,…,rmn)表示A给出的关于所有乙方主体集合B的序区间向量其中=[r,r引表示 A给出的关于B的序区间偏好信息、具体地,;表示A把D排在第r位至第m位,1≤7,≤n+1, 且行越小,则A认为B;越优,反之亦然设S;-(51,52),…,5m)表示B;给出的关于所有甲方主体集 合A的序区间向量,其中5=,表示B给出的关于A的序区间偏好信息具体地,5表示B,把 A;排在第位至第位,1≤,≤m+1,且越小则B,认为A1越优,反之亦然不失一般性, 行=1,1和8=[1,1分别表示A1认为B;是所有乙方主体中最优的和B;认为A;是所有甲方主体中 最优的:行=+1,m+1和5;=m+1,m+1分别表示A认为B;是所有乙方主体中最差的和B;认 为A:是所有甲方主体中最差的此外,1≤7,m≤m和1≤s,s≤m分别表示对A:而言B,是可接受 的和对B而言A2是可接受的:=m=m+1和=对=m+1分别表示对A而言B,是不可接受 的和对B;而言A2是不可接受的 本文要解决的问题是:依据A1给出的序区间偏好信息和B;给出的序区间偏好信息8;,讠=1,2,…,m, j=1,2,…,m,通过某种决策方法,在考虑双边匹配稳定性的情况下获得双边匹配主体的最优匹配方案 3概念界定及相关理论分析 下面首先给出一对一双边匹配的概念 定义22(一对一双边匹配)一对一×边匹配可以定义为一一映射p:AUB→AUB,且A∈A vB,∈B满以下条件:()若p(A4)B.则p(A)=4;(1)若p(B1)gA,则p(B)=B3;(i)uy(A)=B 当且仅当p(B3)=A2·其中,()=B或p(B1)=A1表示A1与B匹配,并称(42,B)为A与B;在 匹配方案p中形成的匹配对.特别地在匹配中,p(A)=41表示4没有匹配对象;同样(B)=B;表 示B没有匹配对象.根据μ确定的所有匹配对集合称为匹配方案 31个体理性匹配 下面对具有序区间偏好信息的双边匹配问题中的可接受对以及个体理性匹配概念进行界定 定义3(可接受对)在一对一双边匹配问题中、对于∨A∈A,VB;∈B,若(A,B)∈AB满足 ,m≤m且1≤,5≤m,则称(A,B)为可接受对;否则,称为不可接受对 在双边匹配方案中,若对于任意的一个匹配主体要么没有匹配对象,要么其匹配对象是可接受的,则称 该匹配方案为个体理性匹配.下面给出个体理性匹配的具体定义 定义4(个体理性匹配)在一对一双边匹配μ中若不存在A∈A,B;∈B,在μ(A)=B;的情况下, 满足r=m%=n+1或==m+1,则称匹配方案是个体理性匹配 由定义3和定义4可见,若匹配方案是个体理性匹配,且(A)=B,或(B)=A1,则A1和B,一 定是可接受对 32基于序区间偏好信息的弱稳定匹配 设pn表示A认为乃优于Bn的可能度,0≤mn≤1:mk表示B认为Az优于Ak的可能度, 0≤qk≤1.在双边匹配中,稳定性是衡量匹配方案优劣的一个重要准则.在匹配方案中,对于没有形成匹配 对的匹配主体,如果双方都认为对方优于当前匹配对象的可能度大于当前匹配对象优于对方的可能度,则这 两个匹配主休将会放弃已有匹配对象而私下进行匹配,由此造成原有匹配方案的不稳定和匹配失效的现象 称这两个匹配主体为匹配方案的阻塞对.为防止获得的匹配方案中出现这种现象,首先给出基于序区间偏好 信息的双边匹配方案的弱稳定阻塞对的桄念凹,进一步地给出弱稳定匹配的概念 定义5(弱稳定阻塞对)设一对一双边匹配μ:A∪B→AUB,对任意的A1,Ak∈A,B;,Bh∈B, ≠k,h≠j若(A;,B)是可接受对,并且A1和B满足如下条件之一:(1)(A)=A1,p(B:)=B3;(i (4;) u(Bj)=Bi, a pih Phi:(ii)u(Ai)=Ai, u(B,)= Ak:, E. ik ki(iv)u(A, 第8期 姜艳萍,等:具有序区间偏好信息的双边稳定匹配决策方法 2155 1(4k)=B,且mh>pi,>k则称(4,B)是匹配方案的弱稳定阻基对 定义6(弱稳定匹配)在一对一双边匹配μ中,若μ是个体理性匹配,并且μ中不存在弱稳定阻塞对, 则称匹配μ为弱稳定匹配 33基于序区间偏好信息的α-稳定匹配 在现实的双边匹配中,没有形成匹配对的匹配主体,如果双方都认为对方优于当前匹配对象的可能度大 于当前匹配对象优于对方的可能度的程度满足一定的阈值α(≤a≤1),则这样的匹配主休可能会放弃已 有匹配对象而与对方重新匹配.本文称这两个匹配主体形成的“匹配对”为a-稳定阻塞对.下面引入基于序 区间偏好信息的双边匹配方案的a-稳定阻塞对的概念18,进一步地给出a-稳定匹配的概念 定义7(α-稳定阻塞对)设一对一双边匹配p:AUB→A∪B,对任意的A2,Ak∈A,B,BA∈B, ik,h≠,若(A;,B)是可接受对,并且A1和B满足如下条件之一:(i)(A1)-42,p(B)-B;(i) u(Ai)=Bh. u(Bi)=B,, Epih-Phi >a;(iii)u(Ai)=Ai. u(B,)=Ar, H ik-gki > a; (iv)u(Ai)=Bh, 1(A)=B;,且nh-pn1>a,h-9h>a,则称(A;,B;)是匹配方案的a-稳定阻寒对 由定义7可以看出,未形成匹配对的匹配主体,只要存在一方匹配主体认为当前匹配对象优于对方的可 能度大于对方优于当前匹配对象的可能度,或虽然对方优于当前匹配对象的可能度大于当前匹配对象优于对 方的可能度,但是大于的程度不高于阈值a,则这两个匹配主体就不会形成a-稳定阻塞对 定义8(α-稳定匹配)在对一双边匹配μ中,若μ是个体理性匹配,并且μ中不存在a稳定阻塞 对,则称匹配为a-稳定匹配 由定义5、定义6、定义7和定义8可以看出,形成弱稳定阻塞对的条件要比形成a-稳定阻塞对的条件 更加严格,由此导致产生a-稳定匹配的数量可能比弱稳定匹配的数量会更多 34基于序区间偏好信息的强稳定匹配 在双边匹配中,对于没有形成匹配对的四配主体,有时刈方并不都要求对方优于当前匹配对象的可能度 大于匹配对象优于对方的可能度,只要存在一方认为对方优于当前匹配对象的可能度大于匹配对象优于对方 的可能度,而另外一方认为对方优于当前匹配对象的可能度不劣于匹配对象优于对方的可能度,双方就愿意 放弃已有匹配对象而进行重新匹配.例如,在婚姻匹配中,假设男士m1和女士e1、男士m2和女士w2形成 了匹配对,此时,m1和v2未形成匹配对但是m1认为v2优于v1,m2认为v1优于w2,t2认为m1不劣 于m2通常女士在面对同样好的两个男士时更愿意选择那个喜欢自己的男士;所以在m1认为2优于1 且ω2认为m1不劣于m2情形下:m1和v2会愿意放弃已有匹配对象而进行重新匹配.鉴于此,下面给出 基于序区间偏好信息的双边匹配方苿的强稳定阻塞对的概念,进一步地给出强稳定匹配的概念 定义9(强稳定阻塞对)设一对一双边匹配:AUB→AUB,对任意的A2Ak∈A,B,Bh∈B ≠k,h≠,若(Aa,B1)是可接受对,并且A,和;满足如下条件之一:(1)(A)=A,p(B)=B;(i) (4)=Bh,(B)=B,且ph2min(i)1(A4)=A,(B1)=Ak,且qik≥qki(iv)A(A)=B 1(Ak)=B,且pn>mn;,9hk29k,或ph≥pin,hk>k;则称(A;B3)是匹配方案P的强稳定阻塞对 定义10(强稳定匹配)在一对一双边匹配中若p是个体理性匹配、并且中不存在强稳定阻塞对, 则称匹配μ为强稳定匹配 由定义5、定义7和定义9可以看出,形成强稳定阻塞对的条件要比形成弱稳定阻塞对和-稳定阻塞 对的条件要弱. 3.5基于序区间偏好信息的超稳定匹配 在双边匹配中,未形成匹配对的匹配主体,如果双方都认为对方优于当前匹配对象的可能度不劣于当前 匹配对象优于对方的可能度,则这样的四配主体可能会放弃已有匹配对象而与对方重新匹配本文称这两个 匹配主体形成的“匹配对”为超稳定阻塞对.下面给出基于序区间偏好信息的双边匹配方案的超稳定阻塞对 的概念,进一步地给出超稳定匹配的概念 定义11(超稳定阻塞对)设一对一双边匹配:AUB→A∪B,对任意的A,Ak∈A,B3,Bh∈B ≠k,h≠j,若(A;,B)是可接受对,并且A和B;满足如下条件之一:(1)(A1)=A;,p(B)=B;(i) 2156 系统工程理论与实践 第37卷 (4)=Bn,(B)=B,且ph (ii)u(Ai)=Ai, u(B)=Ak, a qik 2 qki ;(iv)u(Ai)= B, (4k)=B1,且h>Pn,h≥9,则称(,B)是匹配方案p的超稳定阻塞对 由定义11可以看出,未形成匹配对的匹配主体,只要存在一方匹配主体认为当前匹配对象优于对方的 可能度大于对方优于当前匹配对象的可能度,则这两个匹配主体就不会形成超稳定阻塞对.例如,在婚姻匹 配中,假设男士m1和女士1、男士m2和女士v2形成了匹配对,此时,m1和ω2未形成匹配对.只要m1 认为v1优于ω2,那么无论2认为m1是否优于m2,m1都不愿意放弃ω1而与v2进行重新匹配.类似 地,只要2认为m2优于m1,那么无论m1认为v2是否优于1,w2都不愿意放弃m2而与m1进行重新 匹配.所以只要m1认为1优于v或v2认为m2优于m1,那么mu1和v2就不会进行重新匹配 定义12(超稳定匹配)在一对一双边匹配中,若是个体理性匹配,并且A中不存在超稳定阻塞对, 则称兀配μ为超稳定配 由定义6、定义8、定义10和定义12可知,从α-稳定匹配、弱稳定匹配、强稳定匹配到超稳定匹配,形 成阻塞对的条件越来越弱 36弱稳定匹配、α-稳定匹配、强稳定匹配和超稳定匹配之间的关系 设双边匹配方案的集合为U,个体理性匹配的集合为I,弱稳定匹配的集合为W,a-稳定匹配的集合为 V,强稳定匹配的集合为S,超稳定匹配的集合为H.关于不同匹配之间的关系,依据定义5~定义12,可证 明如下定理: 定理2H∈S∈WsV≤IsU,特别地,当α=0时,W=V;当0<α<1时,WsV;当a=1 时,W=U 由定理2可以看岀.弱稳定匹配一定是α-稳定匹配,反之,未必成立;强稳定匹配一定是弱稳定匹配和 α-稳定匹配,反之,未必成立;超稳定匹配一定是弱稳定匹配、α-稳定匹配和强稳定匹配,反之,未必成立 4双边匹配优化模型构建与求解 4.1模型构建 依据A给出的B和Bn的序区间偏好信息行=分,r和=[,7由式(1)计算B;优于 B的可能度获得A;的可能度矩阵P为 0.5p 0.5 0.5 显然mhn+m=1,m方=0.5.类似地依据B给出的A:和Ak的序区间偏好信息=[5,%和 k;=%k,由式(1)计算A:优于Ak的可能度mk获得乃的可能度矩阵Q为 0.5 0.5 0.5 显然qk+gk2=1,q=0.5 进一步地,依据A和B的可能度矩阵信息P和Q,i=1,2,…,m,j=1,2,…,m,在考虑双边匹 配主体稳定性的情况下,分别构建获得弱稳定匹配、α-稳定匹配、强稳定匹配和超稳定匹配的多目标优化模 型.设c为01型决策变量,xx=1表示A与B;进行匹配;否则x1=0 目标函数1:使与甲方主体匹鬥的乙方主体优于其它乙方主体的可能度尽可能地大 m 2=>>(∑n) 目标函数2:使与乙方主体匹配的甲方主体优于其它甲方主体的可能度尽可能地大 ∑∑ 第8期 姜艳萍,等:具有序区间偏好信息的双边稳定匹配决策方法 2157 匹配数量约束条件:每个甲方主体至多与一个乙方主体进行匹配 1.2 =1 兀配数量约束条件:每个乙方主体至多与一个甲方主体进行匹配 匹配对约束条件:双边主体的不可接受对不能实现匹配 0≤x≤min{n+1-7,m+1-},i=1,2 ;=1,2 令 {n+1 }>0 2; 1.2... -(.,min{n+1-mn,m+1-s}=0 下面给出确定各类稳定匹配方案的稳定性约束条件 (a)获得弱稳定匹配的约束条件为: ∑mn+∑x1+Mo≥1,=1.2,…,m;j=1,2,…, 0n≤mh 由式(2)~(⑧)构成的数学模型为确定弱稳定匹配方案的双边匹配优化模型,为∫说明所确定的约束条件 式(8)的合理性,可以证明如下的定理 定理3满足约束条件(⑧)的匹配方案是一个弱稳定匹配方案,该条件称为弱稳定性约東. 证明为了证明约束条件(⑧)能够保证获得的匹配方案是一个弱稳定匹配方案,可以证明满足式(8)的 vA;∈A和VB∈B组成的(A2,B)不是弱稳定阻塞对 当(A,B3)是不可接受对,即ax=1时,式(8)一定成立,此时,(A;,B)一定不是弱稳定阻寒对 当(A2,B)是可接受对,即ax;=0时,式(8)化简为 a;+ Wih+ (9) qikh≤ 为了证明满足式(9)的可接受对(A,B;)不是弱稳定阻塞对,可证明若可接受对(A,B)满足式(10), 则(A,B3)一定是弱稳定阻塞对 C2i;十 由于∈{0,1},由式(10)可得x=∑n5m,边=2≤,=0.由此可得,对于A;有 (A2)=A2或p(A2) 而对于B;有1(B3)=B或川(B)=Ak项>2.那么由弱稳 定阻塞对的定义5可知可接受对(A2B)一定是弱稳定阻塞对.因此,若可接受对(A2,B3)满足式(8),则 (4;,B)一定不是弱稳定阻塞对 (b)获得α-稳定匹配的约束条件为: x十 Tih+ +Mi>1 由式(2)~(⑦)和式(11)构成的数学模型为确定α-稳定匹配方案的双边匹配优化模型.类似于定理3的 证明,根据定义7和定义8,可证明如下定理 定理4满足约束条件式(11)的匹配方案是一个-稳定匹配方案,该条件称为a-稳定性约束 (c)获得强稳定匹配的约束条件为 Cii rih t k+M;≥1 1.2 +∑x+∑k+Mo≥1, 2158 系统工程理论与实践 第37卷 由式②)~(⑦)以及式(12)~(13)构成的数学模型为确定强稳定匹配方案的双边匹配优化模型.类似于定 理3的证明,根据定义9和定义10,可证明如下定理: 定理5满足约朿条件式(12)~(13)的匹配方案是一个强稳定匹配方案,该条件称为强稳定性约束 (d)获得超稳定匹配的约束条件为: ∑+∑+M0;≥1,1=1,2,…,m;j=1.2,…,n (14) Pih <Ph 4 由式(2)~(⑦)和式(14)枃成的数学模型为确定超稳定匹配方案的双边匹配优化模型.类似于定理3的证明, 根据定义11和定义12,容易证明如下定理 定理6满足约束条件式(14的匹配方案是一个超稳定匹配方案,该条件称为超稳定性约束 42模型求解 本文建立的双边匹配优化模型均是多目标的0-1型整数规划模型,这些数学模型具有相似的特征和结 构,可以采用一类相同的求解方法进行求解.本文采用理想点法进行求解,下面仅对弱稳定匹配优化模型 (2)~(8)的求解方法进行介绍 考虑到双边主体的公平性,设日标函数Z1和Z2的重要性相同,同时将日标函数Z1、Z2的最优解z1 和z2作为理想点.因此,多目标优化模型(2)~(8)可以转换为如下的单目标优化模型(15)~(16) Minz=(Z1-z1|9+|Z2-221)1 (15 . (4)~(8) (16) 其中,1≤q≤+∞.根据多目标规划理论可知,模型(15)~(16)的最优解为模型(2)~(8)的有效解19决 策者可根据实际需求选择不同的q值、当φ1时,最优解与理想点的距离为海明距离或对距离,此时 由于模型(2)~(8)是求解目标哟数的最大值,所以么1≤1,Z2≤∠2.因此目标函数(15)可化简为Min Z=(z1+22-(z1+Z2),这样,模型(15)~(16)等价于求解目标函数为Maxz=Z1+Z2的模型.这 是一个单目标线性优化模型,当冋题规模比较小时,可使用分支定界算法求解;当冋题规模比较大时,可采用 Cplex12.0、 Lingo11.0等软件求解.当q=2时,最优解与理想点的距离为欧氏距离,目标函数(15)为 Minz=√(Z1-z1)2+(z2-2).此时模型是单目标非线性优化模型,可以釆用 Cplex12.0、 Lingo1.0 等软件求解,或设计智能优化算法,如遗传算法、差分进化算法等求解.当q→∞时,最优解与理想点的距 离为切比雪夫距离,目标函数(15)可转换为Minz-max{z1-z1+Z2-2},此时模型(15)~(16)等 价于如下的模型(17)~(20) Minz=入0 s t (18) Z2-Z< (4)~(8) 模型(17)~(②0)是单目标线性优化模型.可以采用分支定界法或 Cplex12.0、 Lingo110等软件求解. 5算例分析 某家政服务中介公司是一家提供住家保姆、月嫂、育儿嫂、家庭教师、高级管家等服务的专业家政服务 杌构.公司始终将雇主的满意度和家政服务人员的满意度作为整个公司运营的核心目标,为∫向雇主和家政 服务人员提供便利、优质的中介服务,公司采用线上电子网络平台和线下实体门店相结合的运耆模式.家政 服务人员和雇主既可以通过网络平台提交供需信息,也可以到中介公司去填写供需信息.寻找家政服务工作 的人员提交的个人基本信息,包括年龄、受教育程度、工作经验、服务技能等;寻求雇佣家政服务人员的雇 主提交的个人雇佣信息,包括需求的服务技能、工资待遇、食宿条件等.在某段时问内中介公司通过线上和 线下共收到6个家政服务人员{A1,A2,…,A6}的个人基本信息和8个雇主{B1,B2,…,Bs}需要的服务 信息.家政服务人员依据雇主提供的工资待遇、食宿条件、工作环境、服务内容等指标对每个雇主进行综合 评价,然后中介公司将雇主的雇佣信息发送给家政服务人员,并将家政服务人员的个人基本信息发送给雇主 第8期 姜艳萍,等:具有序区间偏好信息的双边稳定匹配决策方法 2159 每个家政服务人员依据雇主需求的服务技能、提供的工资待遇、食宿条件等指标对每个雇主进行综合评价, 给出关于雇主旳确定偏好序信息或序区间偏好信息,并将自己的偏好信息提交给中介公司,家政服务人员给 出的关于雇主的偏好信息,如表1所示,雇主依据家政服务人员的年龄、受教育程度、工作经验、服务技能 等指标对每个家政服务人员进行综合评价,给出关于家政服务人员的确定偏好序信息或序区问偏好信息,并 将自己的偏好信息提交给中介公司.雇主给出的关于家政服务人员的偏好信息,如表2所示.家政服务中介 公司依据家政服务人员和雇主给出的偏好信息对双方进行优化匹配 表1家政服务人员给出的关于雇主的偏好信息表2雇主给出的关于家政服务人员的偏好信息 B1 B2 B3 B4 B5 B6 B, Bs B1 B Ba B, B A14,56,7][2,4]8312 A12.3][3,4[1,2]4[2.3[6.75 A2{5,63,4[7,8][1,2846,75A216,745,7][4.5][3.4]6,7[5,7] A33,4]4,5[1,2[3,4][7,8]72[5,6]A3[6.7]1[6,7[1,2]6.7][5.6]61 A45,61,22 467,8][4,54445[4,534[1.2]53 A516,8[2,38 3,4]6A5[5.6]4[1,35[1.2]42.3][4,5] A62476,78513,5]66 5 5 4 5 首先由式(1)获得家政服务人员A的可能度矩阵Pi=1,2,…,m和雇主B;的可能度矩阵Q, 讠=1.2,…,m.依据家政服务人员和雇主的可能度信息.构建获得弱稳定匹配方案的优化模型(2)~(8)、获 得α-稳定匹配方案的优化模型(2)~(7),(11)、获得强稳定四配方案的优化模型(2)~(7),(12)~(13)以及获 得超稳定匹配方案的优化模型(②)~(7)(14).然后采用理想点法,并取q=1、将多目标优化模型转换为单目 标优化模型,并利用 Lingo软件包对单目标优化模型进去求解.获得旳弱稳定匹配、强稳定匹巸和超稳定匹 配的最优解如表3所示. 表3不同类型稳定匹配的最优匹配方案 稳定匹此类型 最优解 Z1+Z2目标函数Z1值目标函数Z2值 弱稳定匹配x17=x26=x34=x43=51=x62 54.09 35.46 18.03 强稳定匹配x13-x26-x37-44-c51-x62-152.64 34.84 17.80 超稳定匹配16=x24=x37=43=51=62=148.92 39.00 9.92 依据上述分析结果,家政服务中介可以根据实际需求选择家政服务人员和雇主的弱稳定匹配、强稳定匹 配或超稳定匹配.由表3获得的最优匹配方案可以看岀,从弱稳定匹配到强稳定匹配、超稳定匹配,它们对 应模型最优解的目标函数值Z1+Z是从大逐渐变小的.这是由于从弱稳定匹配到强稳定匹配再到超稳定匹 配,它们形成阻塞对的条件越来越松弛,相应的形成稳定匹配条件越来越严格,从而形成稳定匹配的数量就 越来越少.可见本算例获得的结果与理论分析是一致的,表明本文方法是有效的 为了进一步说明本文方法的有效性,下面将本文获得的匹配结果与采用文献15]的方法获得的匹配结 果进行对比分析.首先令r表示序区间=[,70]上任意可能的取值,r≤≤y0且r∈N+,并且y在 F={72,r是均匀分布的.令p表示在序区间={r2,r」中偏好排序取值为y的概率,0≤p≤1,则 p2=1/-p2+1.此外,令E(表示序区间产的期望排序值则E(F)=∑n2xr=y+/2.本 文采用E()来对两种方法的匹配结果进行比较 采用文献[15]的方法获得的匹配结果为={(A1,B8),(A2,B1),(A3,B3),(A1,B2),(A5,B1),(A1,B7)}, 需要说明的是,文献[1’的稳定匹配与本文的强稳定匹配、超稳定匹配的概念定义是不相同的,不具有可比 性.因此,只对文献卬5获得的稳定匹配结果与本文获得的弱稳定匹配结果进行比较,如图1所示 山图1可以看出,在采用文猷[15]的方法获得的匹配结果中,家政服务人员获得的匹配对象在其偏好列 表中的期望排疗值都是比较小的,说明家政服务人员对匹配到的雇主的满意度是很高的;而雇主获得的匹配 对象在其偏好列表中的期望排序值都是比较大的,说明雇主对匹配到的家政服务人员的满意度是比较低的, 这使得雇主往往很难接受匹配到的家政服务人员.很可能导致雇主放弃当前的匹配结果.而在采用本文方法 获得的匹配结果中,家政服务人员和雇主的匹配对象在他们偏好列表中的期望排序值大小是差不多的,即双 方的满意度分布是比较均匀的,这使得双方更容易接受对方 2160 系统工程理论与实践 第37卷 通过求解α-稳定匹配模型,获得不同α取值下α-稳定匹配旳数量变化如图2所示.特别地,α=0时 的α-稳定匹配就是弜稳定匹配.由图2可以看岀,随着α-取值的逐渐增大,α-稳定匹配的数量呈现逐渐增 加的趋势.这与定理2中的结论是一致的 8 本文方法 文献方法 600 4 2 100 0 Al A2 A3 A4 A5 A6 B1 B2 B3 B4 B6 B7 0.C 0.2 0.4 0.6 0.8 1.C 实现匹配的家政服务人员和雇主 取值 图1匹配结果比较 图2Q-稳定匹配的数量变化 6对 6结论 本文针对具有序区间偏好信息的双边匹配问题,给出了可接受对和个体理性匹配的定义,在此基础上,针 对现实中可能存在的匹配主体放弃当前匹配对象而与其他匹配主体进行匹配的几种不同情形,给出了基于可 能度的弱稳定阢配、α-稳定匹配、强稳定匹配以及超稳定匹配的定义,并分析了各种稳定匹配之间的关系, 弥补了以往基于序区间偏好信息的双边匹配研究成果中仅仅考虑匹配方案弱稳定性的不足;进一步地,本文 依据双边匹配主体的可能度信息,分别构建了获得弱稳定匹配、a-稳定匹配、强稳定匹配以及超稳定匹配的 多目标优化模型,通过求解优化模型获得相应的最优稳定匹配.与已有硏究成果相比,采用该方法获得的匹 配方案同时考虑了双边主体的满意性和稳定性,弥补了以往研究成果单纯考虑匹配方案满意性或稳定性的不 足。此外,本文提出的双边匹配决策方法,为进一步地解决现实中存在的具有语言评价信息、模糊评价信息 的双边匹配决策问题提供了一种研究思路. 参考文献 1 Gale D. Shapley L S College admissions and the stability of marriage J]. The American Mathematical Monthly, 1962,69(1):9-15 2 Roth A E. The evolution of the labor market for medical interns and residents: A case study in game theory[J The Journal of Political Economy, 1984: 991-1016 3蒋忠中,樊治平,汪定伟.电子中介中具有模糊信息且需求不可分的多属性商品交易匹配问题J.系统工程理论与实践, 2011,31(12):2355-2366 Jiang ZZ, Fan Z P, Wang d w. Trade matching for multi-attribute exchanges with fuzzy information and divisible demand in E-brokerage J. Systems Engineering- Theory Practice, 2011, 31(12):2355-2366 4 Chen J, Song K. Two-sided matching in the loan market[J. International Journal of Industrial Organization 013,31(2):145-152 5 Sorensen M. How snart is SInlart Money? A two-sided Latching Inodel of venture capitalJ. Journal of Finance 2007,62(6):2725-2762 [6 Iwama K, Miyazaki S, Morita Y, et al. Stable marriage with incomplete lists and ties[ M. Automata, Languages and Programming. Springer Berlin Heidelberg, 1999: 443-452 Irving R W. Stable marriage and indifference. Discrete Applied Mathematics, 1994, 48 (3): 261-272 8 Gale D, Sotomayor M. Some remarks on the stable Inatching problein[J]. Discrete Applied Mathenatics, 1985 11(3):223-232 ⑨梁海眀,姜艳萍,孔德财考虑偏好序的多满意稳定导向双边匹配决策方法J.系统工程理论与实践,2015,35(6):1535 1546 第8期 姜艳萍,等:具有序区间偏好信息的双边稳定匹配决策方法 2161 Liang H M, Jiang Y P, Kong D C. Decision-making mcthod on multiple targets of satisfied and stable two- sided matching considering the preference ordering. Systems Engineering Theory Practice, 2015, 35(G) 1535-1546 10 Iwama K, Miyazaki S, Yanagisawa H. A 25/17-approximation algorithm for the stable marriage problem with one-sided ties[M. Algorithms-DSA 2010. Springer Berlin IIeidelberg, 2010: 135-146 11 Gelain M, Pini M S, Rossi F, et al. Local search approaches in stable matching problems. Algorithm, 2013, 6 591-617. 12 Chakraborty A, Citanna A, Ostrovsky M. Two-sided matching with interdependent values J] Journal of Eco nomic Theory,2010,145(1):85-105 卬3乐琦,樊治平具有不确定偏奷序信息的双边匹配决策问题硏究运筹与管理,2012,21(1):57-63 Yue Q, Fan Z P. Study on two-sided matching decision-making problems with uncertain preference ordinal information[J. Operations Research and Management Science, 2012, 21(1):57-63 [14乐琦,张磊,张莉莉.不确定偏妤序信息下考虑主体心理行为的双边匹配决策方法[J.运筹与管理,2015,24(2)∷:113- 120. Yue Q, Zhang L, Zhang L L. Decision method for two-sided matching considering agents'psychological behavior with uncertain preference ordinal information[J. Operations Research and Management Science, 2015, 24(2) 113-120 15 Kisclgof S. Matchings with interval ordcr preferences: Efficiency vs strategy-proofncss[J. Proccdia Computer Science,2014,31:807-813. 16 Fan Z P, Liu Y. An approach to solve group-decision-making problems with ordinal interval numbers J. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2010, 40(5): 1413-1423 17 Vate J II V. Linear programming brings marital bliss J. Operations Research Letters: 1989, 8(3 : 147-153 18 Pini M S, Rossi F, Venable K B, et al. Stability and optimality in matching problems with weighted prefer encesM. Agents and Artificial Intelligence. Springer Berlin Heidelberg, 2011: 319-333 19 Zeleny M. Multiple criteria decision makingM. New York: McGraw-Hill, 1982

...展开详情
试读 10P 论文研究-具有序区间偏好信息的双边稳定匹配决策方法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    img
    • 至尊王者

      成功上传501个资源即可获取

    关注 私信 TA的资源

    上传资源赚积分,得勋章
    最新推荐
    论文研究-具有序区间偏好信息的双边稳定匹配决策方法.pdf 22积分/C币 立即下载
    1/10
    论文研究-具有序区间偏好信息的双边稳定匹配决策方法.pdf第1页
    论文研究-具有序区间偏好信息的双边稳定匹配决策方法.pdf第2页
    论文研究-具有序区间偏好信息的双边稳定匹配决策方法.pdf第3页

    试读已结束,剩余7页未读...

    22积分/C币 立即下载 >