双向选择问题中的最优分配_熊福生

《双向选择问题中的最优分配_熊福生》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第21卷第l期经济数学Vol.12Nol1995年6月MATHEMATICSINECONOMICSJune1995双向选择问题中的最优分配熊福生,,(湖南财经学院基础课部长沙410079).,首先把这类“摘要本文讨论的是双向选择中的分配问题问题进行全化随即建立起一种延缓接受葬,.法”然后证明了用这种茸法处理双向选择问题是德定分配和最优分配关键词双,,最优分配,延缓接受葬法.向选择德定分配12百心卜..1口.丘习,、、,随着市场经济体制的逐步建立在人事的安排劳务的选择商品的交易等方面逐.,,、:,渐实行了

2、双向选择的模式例如高校的招生毕业生的分配企事业单位的招工招聘..,目前存在着两个方面的问题一是在相当一市场上商品的买卖等等在这些双向选择中些双向选择的分配方案中,带有盲目性和不科学性.往往不能使所有招收单位和每一个应.,召者获得尽可能满意的结果另一方面是,,虽然有些方案或作法是比较合理的科学的例:,“”,,如在购买商品时要货比三家等等但是这些作法的合理性与科学性没有从理论上得到证明.本文把这类双向选择问题进行量化,建立起算法模型,推广组合数学【1〕、、3,用“”,〔幻〔」中的结论这种称之为延缓接受算法的

3、方法圆满地解决了双向选择中的稳定分配和最优分配问题.从理论上证明了:用“延缓接受算法”解决双向选择问题是最合理的,最科学的.,,,,:所谓双向选择问题就是有X和Y两个群体(集合)其中X有m人成员Y有个,,,,,,..,:1x:x。y:y:,yx`成员分别记为x一{x…}Y一{…}x的第i个成员i(,,,,,:,1:“”;一123…m)计划在Y中择优选取(l簇in镇)个成员作为合作对象Y的,,,,,,第j个成员y(j一123…n)计划在X中择优选取m(l簇mj簇m)个成员作为“合作”者.这种双向选择问题,

4、实质是一个分配间题.在依某种规则确定了一种分配方案之后,如,。.,.,果至少存在着一对成员x任X和y任Y使得x与头没有合作但是x和y都认为对方若,,,。,xy则称这种分配与自己合作境况会更好些而一致要求改变原分配方案使之与合作.,否则称之为稳定分配是不稳定的:1994一12一收稿日期07一94一经济数学第12卷,x`,x`y,在一个稳定分配中如果对每个任X使得对与自己合作的任Y的满意程度不.x`,低于其它稳定分配中与合作的为任Y的满意程度则称这个分配是对X的最优分配类似地可以定义对Y的最优分配.2.延缓

5、接受法.、用j士,y,y,x,,,丸和iq分别表示愿意选择的程度和愿意选择的程度iP如都是非负数,.x`y,。一;y,x`,如果不愿意选择则取P。如果不愿选择则取iq,一0这样可得到两个矩阵:`s,x,;“.x.P=(P)Q=(,):。,。;。,。首先记P护~Pp一尸q护~qQ一Q;:延缓接受算法中,,,,一”,一”,r一`’,i()在尸卜k(一12…L)中的第i行依P犷的大小重新排列并记为{心结,,.r一”r一“r一`’r一”…忿}其中片)忿)…)岔一,,一”,,r一`,,;,,i()如果O尹p兮任{

6、r片…狡}则令q华一公否则令q护一0并记Q-,,x二(g琴),,s,:,,s,:i(i)在Q中的第j列依q护的大小重新排列并记为(护扩…男}其中沙弄,·s心)…)留,s一”一`,,r`,,`’;iv()如果o护q护〔{s1护一岑}或o

7、…L)中的第j列依q犷的大小重新排列并记为{sI贯,,s,.一”’)一”一”s”`…牛}其中`)砖乡妻…妻牛i(0q一”任s{1一`,,,s`,;尸,~)如果护犷乡…布},则令p护=p护否则令p护一0,并记二,.,x(P琴);,,,,,,,,,i(i)在p中的第i行依P黔的大小重新排列并记为{心心一心}其中心r.r尸)罗)…)v,r,,r一”s一`,,s`,,,一`,;(i)如果o并户犷任{忿一即}或o<、犷去{牙一布}则令`一`q~0.*一(.x二否则令华并记Qq护),,.一、多次重复上述迭代运算直到

8、第L次使得q一仇为止,,.:,在算法巾的每一次迭代过程中首先X向Y作选择然后Y再向X作回应选择专,.任X被y,任。一”“”,,`,,Y或者拒绝或者确定为侯选的合作者当笋p兮e{心…件}时,x,,,,,s则在第k次迭代中选择了y这时如果有。护q护〔is{护…岑}即二合符yj的基1双向;选择第期熊福生问题中的最优分配一9一5,,y,x、,x、y,;本条件又排在他计划选择的名额之内则也选择了即被确定为候选合作者,.,,,,,否x`y,i一`,kx