雙向選擇問題中的最優(yōu)分配_熊福生

《雙向選擇問題中的最優(yōu)分配_熊福生》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、第21卷第l期經(jīng)濟數(shù)學Vol.12Nol1995年6月MATHEMATICSINECONOMICSJune1995雙向選擇問題中的最優(yōu)分配熊福生,,(湖南財經(jīng)學院基礎(chǔ)課部長沙410079).,首先把這類“摘要本文討論的是雙向選擇中的分配問題問題進行全化隨即建立起一種延緩接受葬,.法”然后證明了用這種茸法處理雙向選擇問題是德定分配和最優(yōu)分配關(guān)鍵詞雙,,最優(yōu)分配,延緩接受葬法.向選擇德定分配12百心卜..1口.丘習,、、,隨著市場經(jīng)濟體制的逐步建立在人事的安排勞務(wù)的選擇商品的交易等方面逐.,,、:,漸實行了

2、雙向選擇的模式例如高校的招生畢業(yè)生的分配企事業(yè)單位的招工招聘..,目前存在著兩個方面的問題一是在相當一市場上商品的買賣等等在這些雙向選擇中些雙向選擇的分配方案中,帶有盲目性和不科學性.往往不能使所有招收單位和每一個應(yīng).,召者獲得盡可能滿意的結(jié)果另一方面是,,雖然有些方案或作法是比較合理的科學的例:,“”,,如在購買商品時要貨比三家等等但是這些作法的合理性與科學性沒有從理論上得到證明.本文把這類雙向選擇問題進行量化,建立起算法模型,推廣組合數(shù)學【1〕、、3,用“”,〔幻〔」中的結(jié)論這種稱之為延緩接受算法的

3、方法圓滿地解決了雙向選擇中的穩(wěn)定分配和最優(yōu)分配問題.從理論上證明了:用“延緩接受算法”解決雙向選擇問題是最合理的,最科學的.,,,,:所謂雙向選擇問題就是有X和Y兩個群體(集合)其中X有m人成員Y有個,,,,,,..,:1x:x。y:y:,yx`成員分別記為x一{x…}Y一{…}x的第i個成員i(,,,,,:,1:“”;一123…m)計劃在Y中擇優(yōu)選取(l簇in鎮(zhèn))個成員作為合作對象Y的,,,,,,第j個成員y(j一123…n)計劃在X中擇優(yōu)選取m(l簇mj簇m)個成員作為“合作”者.這種雙向選擇問題,

4、實質(zhì)是一個分配間題.在依某種規(guī)則確定了一種分配方案之后,如,。.,.,果至少存在著一對成員x任X和y任Y使得x與頭沒有合作但是x和y都認為對方若,,,。,xy則稱這種分配與自己合作境況會更好些而一致要求改變原分配方案使之與合作.,否則稱之為穩(wěn)定分配是不穩(wěn)定的:1994一12一收稿日期07一94一經(jīng)濟數(shù)學第12卷,x`,x`y,在一個穩(wěn)定分配中如果對每個任X使得對與自己合作的任Y的滿意程度不.x`,低于其它穩(wěn)定分配中與合作的為任Y的滿意程度則稱這個分配是對X的最優(yōu)分配類似地可以定義對Y的最優(yōu)分配.2.延緩

5、接受法.、用j士,y,y,x,,,丸和iq分別表示愿意選擇的程度和愿意選擇的程度iP如都是非負數(shù),.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獷的大小重新排列并記為{心結(jié),,.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”`…牛}其中`)磚鄉(xiāng)妻…妻牛i(0q一”任s{1一`,,,s`,;尸,~)如果護獷鄉(xiāng)…布},則令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作回應(yīng)選擇專,.任X被y,任。一”“”,,`,,Y或者拒絕或者確定為侯選的合作者當筍p兮e{心…件}時,x,,,,,s則在第k次迭代中選擇了y這時如果有。護q護〔is{護…岑}即二合符yj的基1雙向;選擇第期熊福生問題中的最優(yōu)分配一9一5,,y,x、,x、y,;本條件又排在他計劃選擇的名額之內(nèi)則也選擇了即被確定為候選合作者,.,,,,,否x`y,i一`,kx