论文研究-考虑偏好序的多满意稳定导向双边匹配决策方法.pdf

所需积分/C币:9 2019-09-20 19:19:04 619KB .PDF
收藏 收藏
举报

论文研究-考虑偏好序的多满意稳定导向双边匹配决策方法.pdf,  针对考虑偏好序的多满意稳定导向双边匹配决策问题, 提出了一种新的决策分析方法. 首先, 给出了双边匹配方案、稳定双边匹配方案、弱稳定双边匹配方案和 α-稳定双边匹配方案的相关定义. 然后, 考虑双边匹配主体给出的强偏好序、弱偏好序、无差异偏好序和未知偏好序信息, 分别计算了双边匹配主体的满意度. 进一步地, 分别构建满意、弱满
第6期 梁海明,等:考虑偏好序的多满意稳定导向双边匹配决策方法 1537 对”越优,所形成的匹配方案也越优 设9和h表示分别A1对B的满意度和B;对A的满意度依据满意度9;和h·下面分别给出 稳定匹配方案、弱稳定匹配方案和α-稳定匹配方案的定义 2.1稳定匹配方案 所谓稳定匹配方案是指匹配方案中形成匹配对的任意一方匹配主体,除当前匹配对象以外,无法找到新 的匹配对象,使得该匹配主体与新匹配对象的满意程度同时超过对各自现有匹配对象的满意程度 根据上述描述,首先,给出阻塞对的定义 定义210若双边匹配u确定的匹配对(41,B)和(1.Bk),即若()=B1和(A1)=Bk,满足 g≤9且hk≤hak同时成立时,将(4,Bk)称为阻塞对 从定义2来看,阻塞对并不是双边匹配确定的匹配对,而是对匹配方案的稳定性产生阻碍的配对.因此, 稳定匹配方案中往往不存在阻寒对.下面给出稳定匹配方案的数学定义 定义3013对于双边匹配:A∪B→AJB,所确定的匹配方案,A,A;∈A,B,B;∈B,i≠, ≠j,其中p(A2)=B1,以(41)=Bk,若(A1,B)和(A1,Bk)不满足:91;≤9k且1k≤hk同时成立,则称 该匹配方案为稳定匹配方案;否则称为不稳定匹配方案 需要指出的是,匹配方案的稳定性强弱主要体现其对于阻塞对的要求上,并且关于阻塞对的要求越放松, 相应的匹配方案稳定性越弱 22弱稳定匹配方案 所谓弱稳定匹配方案是指匹配方案中形成匹配对的任意一方匹配主体,除当前匹配对象以外,允许找到 新的匹配对象,使得该匹配主体与新匹配对象的满意程度同时超过对各自现有匹配对象的满意程度,但对于 匹配方案的稳定性影响较小 为了更好地描述弱稳定性匹配方案,下面首先给出弱阻塞对的定义. 定义4对于任意的阻塞对(A2,Bk)来说,若满足下列条件之一:1)彐B,且(A,Dk)为阻塞匹配对, g≤9n;2)34,且(41,Bk)为组塞匹配对,hk≤hk;则称阻塞对(A,Bk)为弱阻塞对 对于定义4而言,若阻塞对(4;,Bk)满足条件1),则称阻塞对(4,B)占优于阻塞对(A2,Bk),叮表示 为(A,B1)←(42,Bk),其中“←”表示占优;若阻塞对(A,Bk)满足条件2),则称阻塞对(41,Bk)占优于 狙塞对(A2,Bk),可表示为(A1,Bk)←(A1,Bk) 然后,可给出如下的弱稳定匹配方案定义 定义5对于双边匹配μ:A∪B→A∪B,所确定的匹配方案,若满足下列情形之一:1)不存在阻塞对 2)若存在阻塞对,不妨设(A2,Bk)为阻碍双边匹配的任一阻塞对,即体(A)Bk,且满足阻塞对(42,Bk) 为弱阻塞对.则称该匹配方案为弱稳定匹配方茱. 根据定义5,容易证明如下定理 定理1稳定匹配方案必是弱稳定匹配方案,但弱稳定匹配方案不一定是稳定匹配方案 从定义5和定理1米看,稳定匹配方案是弱稳定匹配方案的一种特殊情形.弱稳定匹配方案放松了对匹 配方案的稳定条件限制,它不仅包含了稳定匹配方案,还包含了具备一定稳定性的匹配方案 为了便于理解弱阻塞对和弱稳定阢配方案的定义,下面给出一个例子. 例1设 B1 BBB BI B2 B3 B4 10.750.530.36 A1「0.410.770.891 0.8410.250.67 A20.740.3810.84 A30.560.3210.75 A30.9210.270.53 A 0.330.630.871 10.830.680.:6 现假设所求的匹配方案u={(A1,B1),(A2,B3),(A3,B2),(A,B1)} 根据定义4和定义5,容易证明μ为弱稳定匹配方案,即共存在4个阻寒对(A2,B1)、(A3,B1)、(A3,B4) 和(A2,B4),这些阻塞对的占优关系为(A2,B1)→(A2,B4)→(A3,B4)→(A3,B1)→(A2,B1).显然,每一 个阻塞对均被另外一个阻塞对占优,因此,这4个阻塞对均为弱阻塞对,进而μ为弱稳定匹配方案 1538 系统工程理论与实践 第35卷 23a-稳定匹配方案 所谓a-稳定匹配方案是指匹配方案中形成匹配对的任意一方匹配主体,除当前匹配对象以外,无法找 到新的匹配对象,使得该匹配主休与新匹配对象的满意程度同时超过对各自现有匹配对象的满意程度,并且 超过的程度大于或等于决策主体预先设定的满意度阈值a,0≤c≤1. 下面首先给出Q-阻塞对的定义 定义6若双边匹配确定的匹配对(A,B)和(A2Bk),即1(A)=乃和(A)=Bk,满足 gk-9;≥a且hk-bk≥a同时成立时,将(A;,Bk)称为a-阻塞对 特别地,定义6还满足退化性质,即当a=0时,则任一a-阻塞对均为阻塞对 然后,可给出如下的a-稳定匹配方案的定义 定义7对于双边匹配μ:AUB→AUB所确定的匹配方案,不存在a-阻寒对,即VA,At∈A Bk,B;∈B,i≠l,k≠j其中(A)=B,以A1)=Bk,若(A1,B3)和(A1,Bk)不满足:gk-9≥a且 h2k-htk≥a同时成立,则称该匹配方案为a-稳定匹配方案. 从定义7来看,稳定匹配方案也是α-稳定匹配方案的一种特殊情形,这里a可以视作为决策者关于匹 配方案的稳定性要求.可见,α-稳定匹配方案集,不仅包含了稳定匹配方案,还包含了决策者的有限稳定性 要求的匹配方案 定理2当a=0时,任何一个a-稳定匹配方案均是稳定匹配方案,反之也成立 证明根据定义3,当a=0时,则任一a-阻塞对均为阻塞对.而a-稳定匹配方案要求不存在a-阻塞 对,可等价为不存在阻塞对,此时与稳定匹配方案的要求一致,因此,任一a-稳定匹配方案均为稳定匹配方 案;反之,根据定义7,可知任一稳定匹配方案均是a-稳定匹配方案 定理3当0<a<1时,任何一个稳定匹配方案均是a-稳定匹配方案,但a-稳定匹配方案未必是稳 定匹配方案 证明不妨采用反证法.若为一稳定匹配方案,且u不为a-稳定匹配方案,则存在u中的匹配对(A B)和(41,Bk),满足:9;k-9≥a且hik-hk≥a同时成立 由于0<a<1,此时g-9≥a>0且hik-hk>0≥a同时成立,显然,根据定义3,(A1,Bk)为 狙塞对,从而与p为稳定匹配方案矛盾 另一方面,若p为a-稳定匹配方案,则不存在1中的匹配对(A,B1)和(A,Bk),满足:9k-9 且hk-hk≥q同时成立,进而有:9k-91<a或hik-htk<a 当0≤β≤9-9<α且0≤6≤hk-h<α时,有:9≤9k且hk≤h同时成立,根据定理3, 可得:(A,Bk)为阻塞对,此时μ就不是a-稳定匹配方案 综合定理2和定理3,可知a-稳定匹配方案的集合包含稳定匹配方案的集合 此外由于一方匹配主体和另一方匹配主体的满意度满足:0<9,h≤1,容易证明如下定理 定理4当a=1时,任何一个匹配方案均是a-稳定匹配方案 需要指出的是,Q-稳定匹配方案和弱稳定匹配方案并没有确定的包含关系,也没有等价关系.例如:当 〓1时,任意弱稳定匹配方案均是α-稳定匹配方案;当α=0时,任意α-稳定匹配方案又是弱稳定匹配 方案 2.4稳定匹配方案、弱稳定匹配方案和α-稳定匹配方案的帕累托有效性 为了说明稳定匹配方案,弱稳定匹配方案和α-稳定匹配方案的啪累托有效性,下面首先给出关于匹配 方案的帕累托占优的定义 定义8对于任意的匹配方案μ和μ,如果满足如下两个条件,则称匹配方案μ帕累托占优于匹配方案 1)对于VA2∈A,设p(A)=By,p(A)=Bk,A2在中的匹配对象均不劣于在中的匹配对象,即 9≥9,k;同时至少存在一个甲方匹配主体A∈A,1(A1)=Bp,1(41)=B4,A1在1中的匹配对象优于在 1中的匹配对象,即91>917 2)对于VB;∈B,设(B)=A2,1'(B)=At,B;在中的匹配对象均不劣于在/中的匹配对象,即 h≥h+;同时至少存在一个乙方匹配主体Bk∈B,设H(Bk)=Ap,'(Bk)=A,满足Bk在中的匹配 对象优于在p′中的匹配对象,即hnk>hk 第6期 梁海明,等:考虑偏好序的多满意稳定导向双边匹配决策方法 1539 然后可给出帕累托有效匹配方案的定义 定义96,13如果没有其他匹配方案啪累托占优于匹配方案p,则称μ为帕累托有效匹配方案 进一步地,关于稳定四配方案、弱稳定匹配方案和a-稳定匹配方案的帕累托有效性,可通过如卜定理进 行证明 定理5稳定匹配方案为帕累托有效匹配厅案. 证明不妨采用反证法,假设p为一稳定匹配方案,但匹配方案∥帕累托占优于匹配方案p 由于匹配方案μ帕累托占优于匹配方案,则彐A2∈A,设p(A2)=B3,1(A2)=Bk,A在u中的匹 配对象均不劣于在μ中的匹配对象,即9k≥91同时,彐Bk∈B,设风(Bk)=A,1(Bk)=A1,Bk在1中 的匹配对象不劣于在μ中的匹配对象,均有hik≥h2k,显然,根据定义3,匹配对(A;Bk)阻塞匹配方案p, 与μ为稳定匹配方案矛盾 综上,稳定匹配方案为帕累托有效匹配方案得证. 定理6弱稳定匹配方案未必为帕累托有效匹配方案 为∫说明定理6,下面以一个例子进行说明 例2设 BI B2 B3 bi B2 B3 A10.650751 0.3910.86 G=A210.530.86,H=A20.870.541 0.6310.44 A 10.780.28 现假设两个匹配方案为={(A1,B1),(A2,B2),(A3,B)}和p={(A1,B2),(A2,B3),(A3,B1)} 从匹配方案μ来看,共存在6个阻塞对(A1,B2)、(A1,B3)、(A2,B3)、(A2,B1)、(A3,B1)和(A3,B2) 其中每个阻塞对均被另外一个阻塞对占优即相应的占优关系:(A1,B2)←(A3,B2)←(A3,B1)←(A2,B1) -(A2,B3)←(A1,B3)←(A1,B2).可见匹配方案u为弱稳定匹配方案 对于甲方匹配主体A1、A2和A3,乙方匹配主体B1、B2和B3来说,均对匹配方案p中的匹配对象更 满意,因此匹配方案p′啪累托占优于弱稳定匹配方案p 定理7a-稳定匹配方案未必为帕累托有效匹配方案 类似地,为了说明定理7,下面仍以一个例子进行说明 例3设 b B2 B bi B2 B 10.750.88 0.920.740.86 G= A 0.81 0.56 H= A 10.890.77 A30.730.861 A 0.831 1 现假设两个匹配方案为={(A1,B2),(A2,B3),(43,B1)}和p={(41,B1),(A2,B2),(A3,B3)} 从匹配方案米看,当a=0.2时,根据定义7,匹配方案为a-稳定匹配方案但对于甲方匹配主体 A1、A2和A3,乙方匹配主体B1、B2和B3来说,均对匹配案中的匹配对象更满意因此匹配方案n 帕累托占优于弱稳定阢配方案p 3匹配决策分析方法 在本节中,首先,给出了甲方匹配主体和乙方匹配主体的满意度的计算方法;然后,构建了多种类型满意 稳定的匹配决策模型,并给出了模型的求解方法 31计算甲方匹配主体和乙方匹配主体的双边满意度 设G=9]mxn为甲方匹配主体对乙方匹配主体的满意度矩阵.由于偏好关系“?”包含三层含义:第 种是“优于”(“>”),第二种是“等价于”(“~”),第三种是“劣于”(“<”),所以,对于甲方匹配主体A;而 言,当其提出的关于乙方匹配主体的偏好序链中只包含t个“?”关系时,则甲方匹配主体A的偏好序链包 含3条偏好序子链,并且每条偏好序子链发生的概率均为1/34.类似地,若甲方匹配主体Az给出的关于 乙方匹配主体的偏好序链中只包含m;个“≥”关系时,则A;的偏好序链包含2m条偏好序子链,并且每 条偏好序子链发生的概率均为1/2m.一般地,若A;的偏好序链中同时包含m;个“”关系和t;个“?” 1540 系统工程理论与实践 第35卷 关系时则A的偏好序链包含2·3条偏好序子链,并且每条偏好序子链发生的概率均为1/(2m1·34) 特别地,当m;=t;=0时则A;只有一条偏好序链 需要指岀的是,当“?”表示劣于“<”关系时,为表示方便需要将偏好序子链进行调整,使偏好序子链 变成从优到劣的一个排列 令D和D分别为A认为第条偏好序子链中优于和等价于B的乙方匹配主体集合,=1,2, 2m34,|D和D|分别为集合D和D分的基数R(B)为A认为第l条偏好序子链中B,的偏 好序值.P(n(B)-q)表示A认为在第l条偏好序子链中R(B)排在第q位的概率,q-1,2,…,n,并 且 P(R:(B3)=q)= 若D|≥1,则Fn1(B)是均匀分布在区间D+1,D分+D上的离散随机变量,即 P(Ril(Bi)=q |D分 1+1<0<|D D分|+|D q<D)+1orq>|D分|+|D (1) 对于第条偏好序子链而言,A关于B的偏好序期望值E(Bz(B)为 E(Ril(B))=2qP(Ri(B,)=q) 考虑2m·3条偏好序子链,A;关于B;的总体偏好序期望值E(R:(B,)为 E(B2(B;) ∑qP(R(B,)=0)/(2 T么 (3) 进一步地,由于序值越小,相应的乙方匹配主体愈优,将F(R(B)进行规范化,得到A对B;的满意 度9为 g=(m-E(R2(B)+1)/(m-E(R)+1) 式(2)中,F(R)为A关于乙匹配主体的最小总体偏好序期望值,即F(R2)=min{F(R2(B1),F(R2(B2) ,E(R3(Bn)}特别地,当甲方匹配主体A:的偏好序链中仅包含>或~关系时,有2m=1 司理设H=[hm×n为乙方匹配主体对甲方匹配主体的满意度矩阵.设乙方匹配主体B;提出的偏 好序链中包含m个≥关系,Q分和Q;分别表示B认为第条偏好序子链中优于和等价于A的甲方 匹配主体集合,P=1,2,…23;Q分和Q2分别为集合Q和Q的基数:Op(A)为B认为第 p条偏好序子链中A1的偏好序值P(Ojp(4z)=ω)表示B;认为第p条偏好序子链中Oj(A1)排在第v位 的概率,U=1,2,…,m,∑m=1P(Op(42)=v)=1.P(Op(A)=)可由下式给出 P(Oip(Ai)=u ∫1/Q,1|+1≤”≤Q+1Q21 0,v<12;1+1or0>1Q|+1Q 类似于公式(4),可得B;对A2的满意度h为 h=(m-E(O1(Aa)+1)/(m-E(O;)+1)2=1,2,…,m;j=1,2,…, 式(6)中,E(O1(4)=∑2=1m=1P(O1(4)=0)/203,E(O)=mnEO4),E(O1(4) E(O3(Am)}.特别地当乙方匹配主体B;的偏好序链中仅包含>或~关系时,有2n=1 3.2多种类型满意稳定导向的匹配决策模型构建与求解 在现实生活中,考虑匹配决策者对于匹配方案的满意性和稳定性的不同要求,本文将匹配决策问题划分 为满意导向、弱满意稳定导向、α-满意稳定导向和满意稳定导向等四类子问题,下面将具体进行介绍,并给 出相应的模型构建 引入0-1变量,其中x动=0表示甲方匹配主体A2与乙方四配主体B;没有形成匹配对,否则表示甲方 匹配主体A:与乙方匹配主体B;形成匹配对 1)满意导向匹配决策者此时不考虑匹配案的稳定性,而是将匹配主体双方满意度最大作为匹配的决 策日标 根据上述描述,可构建如下满意匹配决策的多目标优化模型为 max 21 ∑∑;; (7a) 第6期 梁海明,等:考虑偏好序的多满意稳定导向双边匹配决策方法 1541 77 max2∑∑h; s t ∑x≤1,1=1,2,…,m ≤1,j=1,2 (7d) x21=0或1,2=1,2,……,m;j=1,2,…,n 7 在模型(7a)~(7o)中,式(7a)和(7b)为目标函数,式(7a)表示甲方匹配主体对乙方匹配主体的总体 满意度最大,式(7b)表示乙方匹配主体对甲方匹配主体的总体满意度最大;式(7c)和(7d)为约束条件,式 (7c)表示每个甲方匹配主体至多与一个乙方匹配主体形成匹配对,式(7d)表示每个乙方匹配主体至多与 个甲方匹配主体形成匹配对 需要指出的是,采用满意导向原则,所求得的匹配方案虽然可以使得匹配主体的满意度尽可能地高,但 也存在因匹配方案的稳定性较差,而使得某些匹配主体放弃匹配的情形. 2)弱满意稳定导向.匹配决策者此时考虑匹配方案的稳定性和满意性,但对匹配方案的稳定性要求不 高.弱满意稳定导向原则的提出,主要是因为考虑到满意导向下求得的匹配方案不具有稳定性,同时如果严 格要求稳定匹配方案,可能会出现不能使得大多数匹配主体满意的情形,因此选择了放松对匹配方案稳定性 的要求,即弱满意稳定导向的决策者的目标在于保证所求匹配方案为弱稳定匹配方案的基础上,使得匹配主 休双方的总休满意度尽可能地高 由于在任一弱稳定匹配方案中,或者所有的阻塞对为弱阻塞对,或者不包含阻塞对,因此,需要构建两个 弱满意稳定匹配决策的多日标优化模型 ①当选取包含弱阻塞对的满意的弱稳定匹配方案时,则构建如下的多目标优化模型 max 21- ∑∑ gini 8a) t=1j=1 nax 22 ∑∑h; s t 8 +∑+∑a+∑ y1M,)≠ (8e) x+x+∑x1+∑m1+∑xr≥3-m121M,i≠ k:qk≤qi :h1≤hij<huy r:9ur≤9uj 0/21+yi12≤1 0或1,t=1,2, 1+m+∑+∑m;+∑ ≤hz 2;+xa+ ∑x+∑m+∑ k:9ik≤9i +x+ k t k:9ik≤9i≤q L: hl, shi3 t: hushi 1,++∑正+∑+∑ (8j) l: hi <h t: htu<h 1542 系统工程理论与实践 第35卷 在模型(8a)~(8)中,式(8a)~(8d)的含义与式(7a)~(7d)的含义相同;式(8e)和(8f)为保证(42,B,)为 弱阻塞对的两个条件,式(8e)表示匹配对(A,B)和(A;,B)为阻塞对,但阻塞对(A;,B)占优于(A:B); 式(f)表示匹配对(A;,B;)和(AB;)均为阻寒对,但阻塞对(A2,B,)占优于(A2,B);式(8g)保证了式 (8e)和(8f)只需要成立一个即可表明匹配对(A;,B)满足式(8e)或(8f)时,就为弱阻塞对;式(8)~(8h) 为变量约束 为了说明式(8e)和(8f)的合理性,下面给出一个定理进行说明 定理8若满足x1+x+∑x;k+∑x1+∑xt≥3,可保证匹配对(A:B)和 k:gk≤91≤91 t: hto <h (A,B)均为阻塞对,但阻塞对(A,B)古优于(A2,B) 证明根据约束条件(8c)和(8d),当且仅当 x:k=1 x1=1和∑xt=1时, k:k≤9≤91 l:h≤ha t:t≤h 满足xx+x0+∑mik+∑xn+∑t≥3,并且进一步可得:A2与Bk匹配、A与B k:gk≤9≤9 l:h;≤hi t: hta <h i 匹配和At与B2匹配 根据定义3以及∑ 1和 x1=1可得:A较匹配对象Bk,更愿意与B,匹配,即 k:9k≤9i≤9 gk≤9;同时,B;较匹配对象A1,更愿意与A,匹配.即M≤h因此,匹配对(A,B;)为阻塞对 同理.根据∑k=1和∑xtm=1可得:A;较匹配对象Bk,更愿意与B,匹配,即 :9k≤9i≤gi t: hty <hiv g≤9s;同时,B较匹配对象A,夏愿意与A;匹配,即h≤h.因此匹配对(4a2B)为阻塞对 此外由∑ik=1还可以得出:A;对于乃,更愿意与B匹配,即9≤9a根据定义4,可 k:9k≤qj≤9i 得阻塞对(42,B2)占优于(A2,B1) 类似地,还可以证明如下定埋: 定理9若满足r+xn+∑x+∑x1+∑xm≥3,可保证匹配对(4,B)和 k:k≤9 :≤h≤九 r:gur<ga A,B1)均为阻塞对,但阻塞对(A,B,)占优于(A,B) ⑨当选取不包含阻塞对的满意的弱稳定匹配方案时,则构建如下的多目标优化模型 maX ∑∑9 nax 22- ∑∑h (9b i=1y=1 s t 3 ≤1,i=1,2, 2≤1,J=1, 2k+ k:39k≥9 k:hky≥h动 =0或1,i=1,2 7; (9f) 在模型(9a)~(Or)中,式(9a)~(9d)的含义与式(7a)~(7d)的含义相同;式(9e)为根据文献14确定的 稳定性约束条件 在构建上述模型之后,需要说明的是,模型(8a)~(8f)和(9a)~(9f)的可行解组成了所有可行的弱稳定 匹配方案的集合进而最优弱满意稳定匹配方案应由模型(8a)~(Sf)和(9a)~(9f)共同确定 此外.根据定理1.由于稳定配方案集是弱稳定匹配方案集的子集,当进一步考虑匹配主体双方的总 体满意度时,可得:最优弱满意稳定匹配方案的总体满意度大于或等于最优满意稳定匹配方案的总体满意度. 因此、采用弱满意稳定导向原则,有助于提升匹配主体双方的总体满意度 3)α-满意稳定导向.匹配决策者此时考虑匹配方案的稳定性和满意性,但对匹配方案的稳定性要求不 高.与弱满意稳定导向原则相同的是,α-满意稳定导向原则的提出.同样也克服了满意导向和满意稳定导向 第6期 梁海明,等:考虑偏好序的多满意稳定导向双边匹配决策方法 1543 原则下所求匹配方案的缺陷但与弱满意稳定导向原则有所区别的是,a满意稳定导向原则中,匹配决策者 可以凭借自身知识和经验给出判定稳定的满意度阈值.即a-满意稳定导向的决策者的目标在于保证所求匹 配方案为α-稳定匹配方案的基础上,使得匹配主体双方的总体满意度尽可能地高 根据上述描述,可构建如下-满意稳定匹配决策的多目标优化模型为 rr n max ∑∑9x j-1 naX 22=∑∑h双 (10b s t 100 i≤1,y=1,2 (10d) + ik+ ∑ Wkj k:gii-gik<a A: hii-hki<a 0或1,i=1, (10f) 在模型(10a)~(10)中,式(10a)~(10d)的含义与式(7a)~(7)的含义相同;式(10e)为c-稳定性约束 条件,保证匹配对(A,B)不为a-阻塞对 标996kh/k≥1的匹配方案一定是a稳定匹配方案,该 定理10满足条件x2;+∑xk+ 条件称为稳定性约束 证明设匹配方案为p往证1+∑+∑xk<1时,p是不稳定的由于x是 < hi: 1uij-hukj<'e 0-1变量,因此,往证:,xx=0,∑x认同时成立时,p是不稳定的 左: <ar 根据约束条件(10c),若1(A1)≠A;时,则∑11x= 35x+∑x=1,进而满足 k:ga-9ak≥ ∑mk=1,不妨设(A)=B3,则有9;-9≥a.同理,根据约束条件(10d),若(B;)≠B;时,有 k:91j-9k≥ ∑xk=1,不妨设p(Ak)=B3,则有h-h k:ha3-hkj≥c 综上由定义2,9-9≥a和hx-hk≥a同时成立说明匹配方案μ是不稳定的进而说明满足约 束条件(10e)的匹配方案是μ稳定匹配方案 根据定理2~4,由于稳定匹配方案集是α-稳定匹配方案集的子集,当进一步考虑匹配主体双方的总体 满意度时,可得:最优α满意稳定匹配方案的总体满意度大于或等于最优满意稳定匹配方案的总体满意度 因此依据a-满意稳定导向原则,也可以有效提升配主体双方的总休满意度同时,若采用a-满意稳定导 向原则匹配决策者也可根据实际需要,通过合理调节a的取值获得匹配主体双方总体满意度较大的匹配 方案 4)满意稳定导向.匹配决策者对匹配方案的稳定性和满意性提出较高的要求,因此,满意稳定导向的决 策者的目标在于保证所求匹配方案为稳定匹配方案的基础上,使得匹配主体双方的满意度尽可能地高 根据上述描述,所构建的满意稳定匹配决策的多目祘优化模型就是模型(9a)~(⑨f),因此,为避免重复,这 里不再赘述 不难看出,模型(7a)~(7e)、(8a)~(j)、(9a)~(⑨f)和(10a)~(10f)均是多目标0-1整数规划模型.针对这 些模型的特点,本文依据文献[15的思想设计了如下的变步长算法.不失一般性,以模型(7a)~(7e)为例, 下面对算法进行介绍 步骤1将模型(7a)~(τe)转化为两个单目标优化模型(T)和模型(T),其中模型()和模型(T)的目标 和2为最优解X和X对应的目标函数值将X代入式(7b)中求得相应的目标函数值为飞,公 两数分别为式(7a)和(7b),约東条件均为式(7c)~(7e).分别求解模型(I)和(I,得到最优解X1和 1544 系统工程理论与实践 第35卷 步骤2设初始迭代变量s=1,最大迭代次数为H. 步骤3设步长为△=(2-21)/(H-8,构建模型(s即在模型(中加入约束条件∑m1∑=1h 2-1)+△.求解模型(s),输出X{°,得到相应的目标函数值2{),并将x{)代入到式(7b)中,得到相应 的目标函数值为)若s>H,或2)+△>2,则转步骤5;否则转步骤4 步骤4令s=s+1,转步骤3. 步骤5设初始迭代变量t=1,最大迭代次数为H +)+A求解模型(s+1+1,输出x++求得相应的目标函数值2+,并将x+t+代A罗 步骤6设步长为A=(21-2+0)(H-1),构建模型(+t+1,在模型(1加入约束条件∑1∑m=1a 式(7a)中,求得相应的目标函数值为x++,t>H,或x++1)+A>x,则转步骤8;否则转步骤7 步骤7令t=t-1,转步骤6 步骤8输出有效解集合Ⅱ={X,X2,X),…,X1),X2°+2),…,X+},并求出有效解对应的目标 函数值即1=21(X),22=22(X),X∈∏ 步骤9根据决策者设定的偏好函数V=V(≈1,2),确定最优解 4算例 沈阳某中介公司提供机术类新产品的专利技术服务.甲方匹配主体是拥有机床专利技术产权的个人或 企业:乙方匹配主体是求购机专利技术使用权的个人或企业.该技术中介公司在某一时段收到甲方匹配主 体集合A={A1,A2,……,A6}的转让信息和乙方匹配主体B={B1,B2,…,Br}的求购信息.甲方匹配主 体A;关于B给出的偏好序主要考虑专利技术的转让成本和专利技术的转化速度等指标.乙方匹配主体B 关于A给出的偏好序主要考虑专利技术能力建设和专利技术的潜在价值等指标.甲方匹配主体和乙方匹配 主体给出的偏好序信息如表1所示 表1甲方主体和乙方主体给出的偏好序信息 偏好序 偏好序 11 B5> Br? B3 >:BA BI A1A3, A6?A5>A A2 BA B3>B6? B5 B7> B2>B1 B2 A5>A6N A1? A3>A4> A2 B1>B6~B3>B4B344>A3xA6>A2>A5~A1 A4B6×B1~B3≥份5>B7?B4>F2B4A5A2≥A3xA4?A1>A6 A5B1>B4>B7>B6>B5?B2>B3B544?A2>A6>A1>A3>A5 A6 B7>B2>B3>B6? B4>B5 Bl A>A B742A3>A5~A6>A1>A4 根据式(1)~(4),可得甲匹配主体的满意度矩阵G=0x]6×7如下 0.460.540.790.1410.290.79 0.150.300.9310.810.810. 0.6410.390.140.640.390.83 9a 6×7 0.750.140.750.360.6410.36 10.360.140.820.360.570.75 0.210.910.710.500.210.501 根据式(5)~(6),可得乙方匹配主体的满意度矩阵H=[h6×7如下 10.670.250.420.550 0.36 0.170.210.500.8910.321 0.910.670.830.710.320.861 H=[h]1×7 0.520.2910.4210.230.18 0.5210.2510.230.860.64 0.520.670.580.170.7310.64 引入0-1决策变量,可建立确定满意匹配方案、弱满意稳定匹配案、-满意稳定匹配方案和满意稳 定匹配方案的优化模型.下面采用本文所提出来的变步长算法,分别求解模型(7a)~(7e)、(8a)~(8j)、(9a)~(9f) 和(10a)~(10f)

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

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

    关注 私信 TA的资源

    上传资源赚积分,得勋章
    最新推荐
    论文研究-考虑偏好序的多满意稳定导向双边匹配决策方法.pdf 9积分/C币 立即下载
    1/12
    论文研究-考虑偏好序的多满意稳定导向双边匹配决策方法.pdf第1页
    论文研究-考虑偏好序的多满意稳定导向双边匹配决策方法.pdf第2页
    论文研究-考虑偏好序的多满意稳定导向双边匹配决策方法.pdf第3页
    论文研究-考虑偏好序的多满意稳定导向双边匹配决策方法.pdf第4页

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

    9积分/C币 立即下载 >