ֻ13ज ֻ5௹ᇏݓܵ॓࿐, 2005୍ 10ᄅ ChineseJournalofManagementScienceOct., 2005໓ᅣщݼ:1003-207(2005)05-0044-05基于整数规划方法的组合双向拍卖最优化模型范小勇,梁 木梁(中国科学技术大学,合肥 230052)ᅋ ေ:ቆކචཟஅછ൞ቆކஅછބචཟஅછ֥ቆކbაቆކஅછࠇචཟஅછཌྷб,ቆކචཟஅછ໙ี۷ࡆگᄖ,ଢభ္֥࣮ؓࢠഒbЧ໓ᄎႨᆜඔܿ߃֥ٚمࡹ৫ਔ၂۱ቆކචཟஅછ໙ี֥၂Ϯ߄ଆ,ѩ๙ݖᇯ҄ሇ߄,Ϝቆކචཟஅછࡥ߄ູֆшஅછ,ႵᇹႿ০Ⴈࢳֆшஅછ֥ٚمটࢳگᄖ֥චཟஅછ໙ี,ᆃ၂໙ี֥࣮֤֞ਔࡥ߄bܱՍ:ቆކචཟஅછ;ֆшஅછ;ቋႪ߄ଆ;ࢌၞഺჅᇏٳোݼ:F724;O22 ໓ངѓ്:A1 ႄؓՎࣉྛਔٳ༅აሸඍbቆކචཟஅછ(CombinatorialDoubleAuctionԮ֥அછٚൔࢠݺֹࢳथਔପུၛקࡎ֥CDA)ቔູቆކஅછ(CombinatorialAuction)ބචཟ٤ѓሙഅᄝ൧ӆࢌၞࠏᇅ༯ၛൌགྷ܄ࢌၞ֥அછ(DoubleAuction)֥ࢲކ,൞ઙછචٚࡼ؟ᇕഅ໙ี,թᄝ֥໙ี൞:(1)֒ҕაದݖ؟ֹҕაᆃοᅶ҂ᇕোაඔਈ֥ቆކࣉྛචٚБࡎஅછ֥ဢ֥அછࢌၞൈ,ླေӵքնਈ֥ٮႨb(2)ೂݔ൧ࢌၞྙൔbაఃஅછࢌၞࠏᇅཌྷб,ቆކචཟஅӆഈႵ၂ٚԩႿ؎ֹ,໊ᄵԩႿ؎ֹ໊֥၂ٚછ҂ࣇିࢳथֆшஅછᇏթᄝ֥؎Ⴊ൝໙,ีཁࡼट౼۷ն֥ഺჅb(3)൧ӆؓႿഅᇕোაඔਈᇷֹࢆ֮ࢌၞՑඔაࢌၞӮЧ,طડቀളӁބള֥ླѩ٤൞ሹ൞ֆ၂,֥Ⴕൈ൞҂ᇕোაඔਈࠃཨٮླರၭ؟ဢྟ֥ླေ,ၹطᄝሰഅༀᇏ֥ቆކbೂచӚളӁᇅᄯഅӈӈοᅶ၂ק֥б২ҐऎႵܼখ֥ႋႨభࣟ[3]bଢభ,ؓႿቆކචཟஅછܓളӁਬ҆ࡱbູࢳथԮஅછٚൔ֥ಌཊ,ൡႋ֥࣮໓ངߎ҂؟bFan,M [4],J Stallaertགྷൌࣜ࠶ࢌၞ֥ླေ,ՖԮ֥அછٚൔᇏؿᅚԛ(1999)ิԛਔ၂۱ܱႿࣁವ൧ӆ֥࣍රଆ,࣮ਔቆކஅછ(CombinatorialAuction)ބචཟஅછਔ؟۱܄ඳࡗචٚБࡎ֥ܢௐቆކࢌၞ໙ีbھଆ(DoubleAuction)֩ࢌၞٚൔbఃᇏ,ቆކஅછ൞ࡼෙಖॖၛᄎႨႿචٚБࡎ֥౦ঃ,ଆ֥ࢳ؟۱ቆކӮ၂۱ѓ֥টஅછࢌၞ,҂ࣇࡨഒ؇ཌྷ֒նbBa Su[5]linandStallaert(2000)ิԛਔஅછ֥ቆᆮބҕაٮႨ,ิۚஅછ֥ࢌၞི,ੱطܱႿᆩ്Ӂ൧ӆᇏ֥චཟቆކஅછࠏᇅbᆩ്ቔࢆ֮ਔࣩѓದ֥ڄག[1]b҂ݖ,ᄝቆކஅછ֥ࠏູቆᆮᇏ֥܋Ӂ,ఃሱಖඋྟࠇఃऎႵ҂ॖٳᇅഡ࠹ᇏ,ቆކஅછ഻ࣩѓ໙ี൞၂۱NPี[2]b۩֥ڸඋ֥หྟथקਔҐႨቆކஅછ൞ൌགྷഠ߶චཟஅછ൞ઙછචٚ۲ሱԛࡎҕაஅછ֥ࢌၞࠏڞ০ቋն߄֥Ⴕིࢌၞࠏᇅ,ѩીႵ۳ԛھ໙ᇅ,ڿэਔ ֆшஅછ ᇏႚႵྐ༏Ⴊ൝ࠇሧჷႪี֥ࢳٚمbႮႿቆކචཟஅછᇏສສടࠣ؟ᇕ൝֥ઙٚ(ࠇછٚ)֥ཌྷؓ؎Ⴊ൝,ૌᆭࡗ֥അ,҂ᇕഅ֥҂ඔਈቆކႻၛ౫࣐bܱ༢эӮਔ၂ᇕ܂۳ބླ֥ܱ֩༢bචཟஅછၹՎ,ೂޅഡ࠹ቋႪ߄֥அછଆ,ѩ࿙ᅳކൡ֥ෘ္࣮၂ᆰ൞թᄝሢંഈ֥ಣׄބׄ໙ี,ఃمটࢳ໙ี֥ቋႪࢳ൞࣮ቆކචཟஅછླေࢳᇏ,ቋູᇷ֥൞] Smithύ ໙ี[10b໓ང[10]थ֥ᇗေ໙ีbЧ໓ҐႨᆜඔܿ߃֥ٚمࡹ৫ਔቆކචཟஅછ൬۠ರ௹:2004-07-14;ྩרರ௹:2005-06-21ࠎࣁཛଢ:ݓࡅሱಖ॓࿐ࠎࣁሧᇹཛଢ໙ี֥၂Ϯ߄ଆ,ѩ๙ݖଆ֥ሇ߄,ࡼቆކචཟ(70371023);ݓࡅ࢝ტჴ߶Ѱൖׄࠎࣁ(20030358052)அછ໙ีሇ߄ູֆшஅછ,໙ี֤֞ࡥ߄,ູ࣮ቔᆀࡥࢺ:ٓཬႧ(1976-),ଳ(ݱቂ),Кشᇜದ,ᇏݓ॓նቆކචཟஅછࢌၞࠏᇅ֥൧ӆིੱaሧჷᇂ֥Ⴕ࿐അ࿐ჽѰൖള,࣮ٚཟ:༢۽ӱބथҦٳ༅.ིྟބ഻ࣩѓथҦ֩໙ีקਔࠎԤb
ֻ5௹ ٓཬႧ֩:ࠎႿᆜඔܿ߃ٚم֥ቆކචཟஅသቋႪ߄ଆ 45 ࡌഡ෮Ⴕഅ҂թᄝົა९թٮႨ,ൌ࠽ᇏႵޓ2 ቆކචཟஅછ֥ቋႪ߄ଆ؟അ൞ླေ९թބົٮႨ֥bഈඍࡌקᄝགྷൌቆކචཟஅછࢌၞࠏᇅ֥Ⴊׄԛіགྷᄝ:ൌᇏໃсປಆડቀ,ᆃႵᇹႿᄝં࣮ᇏࡼگᄖགྷሧჷ֥Ⴊ߄ᇂ,ѩઙછච֥ٚ൬ၭղ֞ቋնb໙ีࡥֆ߄,ෛު֥࣮ࡼᇯ҄٢ࠇูսᆃུࡌၹՎ,ࡼቆކචཟஅછ໙ีଆ߄֥၂۱ᆰࢤٚمק,ཟᆇൌൗࢸЯ࣍bପહ,ᄝھࠎЧࡌק༯,ቆކ൞ࡼіൕູ၂۱ഠ߶ڞ০ቋն߄໙ีbࠧ:ᄝॖචཟஅછ໙ีॖၛіൕູ၂۱ᆜඔܿ߃໙:ีิ܂֥Ӂਈჿඏ่ࡱ༯(ઙࣩٚઙ֥ૄ၂ᇕഅ(CDA)Max pjxjିႮછٚิ܂),ቋն߄ઙٚބછ֥ٚሹ൬ၭbೂj B:Ⴕ؟۱ઙٚބ؟۱છٚҕࡆ၂ ུཛଢ ֥ࣩઙބࣩs t aijxj 0 i M(1)j Bછ(ᆃ ֥ཛଢ ൞ᆷઙٚބછٚླေࢌၞ֥۲ᇕ0 xj uj xj z+ j B:fj=0അᇕোބඔਈ֥҂ቆކ)bૄ၂۱ࣩஅҕაᆀxj {0,uj} xj z+ j B:fj=1(2)ᆌؓૄ၂۱ཛଢิԛሱ֥ࣩ࠭ઙބࣩછླb֒ఃᇏ,(1)ൔսіሧჷჿඏ:ઙٚܓઙ֥അඔઙٚБࡎ҂֮ႿછٚБࡎൈ,ࢌၞؿളbஅછ֥ଢਈсྶႮછٚิ܂;(2)ൔսіࢌၞჿඏ:ૄ۱ࣩஅѓ൞ሹ֥ࢌၞഺჅ(ࠧഠ߶ڞ০)ղ֞ቋն,ჿඏ่ᆀ෮ିࣉྛ֥ቋնࢌၞඔਈbࡱ൞:ؓૄ၂ᇕഅ,ઙٚ࿊ᄴࣩઙཛଢᇏ֥ھᇕഅഈඍ൞ቆކචཟஅછ໙ีᄝ၂Ϯ߄౦ঃ༯֥ଆඔਈ҂ӑݖછٚ෮ିิ܂֥ඔਈb,൞,ൌ࠽֥ቆކචཟஅછࢌၞສສ൞ٴَگᄖഡႵ၂۱ࠢކM,Ⴎmᇕ҂അܒӮbႵn֥,ၹՎ,Ⴕсေॉ੮༯૫ห൹౦ঃ:۱அછҕაದ(ઙٚބછٚ),ૌ֥ࣩஅཛଢႨࠢ(1)ᆺႵື၂֥છٚކB={B1, ,Bj, ,Bn}іൕbBj൞၂۱ົཟՎൈ,൧ӆഈ෮ႵഅႮછ֥ٚ၂۱ཛଢቆކਈ (j,bf,pj,uj,fj),ఃᇏ,j {1,2, ,n},іൕࣩิ܂,ࠧࠢކNsᇏᆺݣႵ၂۱ჭbପહ,ഈඍቆஅཛଢ֥༯ѓ ,bj={a1j, ,aij, ,amj)|aij ކචཟஅછႪ߄ଆॖၛڿཿູ:Z},aijіൕᄝֻj۱ࣩஅཛଢᇏ෮Їݣֻ֥iᇕഅMax֥ඔਈbૄ۱ࣩஅཛଢေહ൞ࣩઙ,ေહ൞ࣩછb pjxjj Bೂݔ൞ࣩઙs t ,ପહ,ิԛ֥അཛଢ൞ࣩઙླ, aijxj bj i M(3)j Bّᆭ,ᄵิԛ֥അཛଢ൞ࣩછླbೂݔླ֥0 xj uj xj Z+ j B(4)അi҂ᄝࣩஅཛଢᇏ,ᄵaij=0;ೂݔഅi൞ࣩ(2)ቋ؟ᆺࢌၞ၂۱ቆކઙཛଢ,ᄵaij>0;ೂݔഅi൞ࣩછཛଢaij<0bՎൈ,uj=1( j B),ࠧxj {0,1}bpj R,іൕѓದjؓھቆކཛଢ֥ࣩࡎbೂݔpj(3)ֆ໊അཛଢቆކ>0,іൕࣩઙБࡎ;pj<0,іൕࣩછБࡎbuj Z,Վൈ,ૄ۱ཛଢቆކ֥ૄᇕഅᆺݣႵ၂۱ֆіൕֻj۱ቆކཛଢᇏ bj֥ቋնࢌၞ۱ඔbfj {0,໊ඔਈ,ࠧaij {-1,0,1}b1},൞၂۱ᆷൕэਈbೂݔfj=1,іൕႵuj۱ b(4)ປಆЎބࢌၞࠇປಆ҂ࢌၞ:ၩj B,jཛଢФࢌၞࠇᆀ҂Фࢌၞ(ٳљӫູ ປಆЎބࢌႵჿඏ่ࡱfj=1ၞ ބ ປಆ҂ࢌၞ );ೂݔfj=0,ᄵіൕࢺႿ0აՎൈ, ປಆЎބࢌၞ ა ປಆ҂ࢌၞ ॖၛሇu߄ ູ٤ປಆЎބࢌၞ bၹູBj=(j,u jbj,uj,pj,jᆭࡗ֥ bjФࢌၞ(ӫ ູ٤ປಆЎބࢌၞ )bࡌק҂թᄝࠁކࢌၞ,ࠧ:ujᆺିູᆜඔbູࡥьఏ 1,0)֩ࡎႿBj=(j,bj,pj,uj,1)bೂݔႨN ={Bj,ࡼઙ֥ࣩٚઙྛႨࠢކNb={B j|bj>0}іൕ N|fj=1}іൕᆃᇕ౦ঃ༯֥ࣩஅࠢ,ପહ໙ี;છ֥ࣩٚછྛႨࠢކNࣼэູਔ:s={B j|bj<0}іൕbଆ֥ࠎЧࡌק൞:(1)෮Ⴕ֥Бࡎ൞ૡٿMax pjxjj B,֥ھࡌഡაൌ࠽֥؟அછᇏ္ӈӈܿקҐ౼ૡٿࣩࡎࠇӫٿѓஅછ֥ܿᄵཌྷژކs t aijxj bj i M;(2)ઙછචٚj B֥Бࡎބࣩѓཛଢ֥ቆކ൞৫ದྐ༏,ھࡌ0 xj uj,xj Z+, j,s t Bj N/N ഡ൞அછིࠛٳ༅֥མࠎሙ,ӈ֥அછંଆ0 xj 1, j,s t Bj NҐႨᆃᇕམࡌഡ;(3)ູٳ༅აࡹଆ֥ࡥь,ఃᇏ,aij Z+bj Z+
46 ᇏݓܵ॓࿐ 2005୍ཁಖ,X*0S൞(CDA3 චཟஅછაֆшஅછ֥֩ࡎሇߐ)֥၂۱ॖྛࢳ,ၹູux*j0jေؓഈඍ၂Ϯ߄ଆࢳቋႪࢳѩ҂ಸၞ,ห a*ijxkj= aij( 1) a*ijx0j=0bط,jљ൞֒அછ֥ᇕোაቆކ٤ӈ؟ൈ۷൞ೂՎbj Bk=1j Bk=1j Bjjujཌྷؓটඪ,ଢభؓֆшஅછ໙ี֥࣮бࢠ؟,طX*0Sؓႋ֥ଢѓݦඔᆴW*0S= pjxkj=ؓఃෘم္֥࣮бࢠӮඃbၹՎ,ೂݔିࡼචཟjj Bk=1jxஅછଆሇэູֆшஅછଆ,ࡼႵᇹႿ໙ี֤kjj֞ࠞն֥ࡥ߄b pj( 1)= *pjx0j=W*0(࠺ູ(7)ൔ)b࠻ಖj Bk=1j Bj3 1 ࡼ؟ཛଢ֥ቆކචཟஅછሇ߄ູֆཛଢ֥ቆX*0S൞(CSDA)֥ቋႪࢳ,ᄵW*S W*0Sbൈ,Ⴎކචཟஅછb(7)ൔ֤W*S W*0,൞,W*=W*S,ᄵW* ෮໌؟ཛଢ֥ቆކචཟஅછ൞ᆷࢌၞཛଢඔਈW*0,ᆃაW*0>W*؛bၹՎ,X*൞(CDA)֥҂ᆸ၂۱,ࠧuj>1bᄝഅቆކ҂ॖٳ۩֥౦ঃቋႪࢳbקᆣૼປиb༯,ॖࡼఃሇ߄ູֆ၂ཛଢ(uj=1)֥ቆކஅછ໙3 2 ࡼֆ၂ཛଢ֥ቆކචཟஅછሇ߄ູֆཛଢ֥ีটࢳbቆކֆшஅછק:ࡌק༯૫0-1ᆜඔܿ߃໙ี:Ⴎഈඍקॖᆩ,ૌॖၛϜቆކචཟஅછ၂ujϮ߄ଆ֥ࢳ֥ᇗׄ٢ᄝֆ၂ཛଢ(ࠧؓႿ෮Ⴕ(CSDA) WS=Max pjxkjjj Bk=1֥j B,uj=1)౦ঃ༯ॉ੮b༯૫,ૌࡼϜֆjuj၂ཛଢ֥ቆކචཟஅછଆ,ሇ߄ູཌྷႋ֥ֆཛଢs t aijxkj 0, i M(5)j֥ቆކֆшஅછଆbj Bk=1j0 xkj 1,xؓႿ۳ק֥ֆ၂ཛଢ֥ቆކචཟஅછ(IP)ᆜඔkj Z+, j B,kj {1, ,jjuj}(6ܿ߃ଆ,๙ݖࡼઙࣩٚઙࠢކაછ֥ࣩٚછࠢކ)ೂݔ*ٳ:B=Bs Bb,ఃᇏ,Bs={Bj|aij 0,,X*s={x11, *,x1u, *,x|B|1, *,x|B|u}1|B|൞ഈඍ(CSDA)໙ี֥၂۱ቋႪࢳ,ቋႪᆴູ j}սіࣩછࠢކ;Bb={Bj|aij 0, j}սіࣩઙࠢކbᄵuu1|B|W**Max( pjxj- (-pj)xj)Sbପહ,X*= xk1, ,1 *xk|൞ཌྷ|B|B|j Bj Bk=1kbs1|B=1|ႋ֥(CDA)໙ี֥၂۱ቋႪࢳ,ቋႪଢѓᆴູs t aijxj- (-aij)xj 0,i Mj Bj BW*bs=W*Sbᆣૼ:ᆣૼݖӱٳ,҄൮༵ᆣૼX*൞ཌྷႋ֥0 xj 1,xj Z+, j Bၹູxj {0,1},҂ٞႨ1-xjูߐછࣩٚஅࠢᇏ(CDA)֥၂۱ॖྛࢳbၹູ0* xkj 1,ཁಖ,0 j֥xjbࠇᆀ,۷၂Ϯֹ,ؓႿ j B,xj 1-xj,ujႿ൞,ഈඍଆॖڿཿ:ູ *xkj uj, j BbᄵX*ડቀ(2)bႮ(5)ᆩ=jk1Max( pjxj- pj)jj Bj Buj ( aijxkj) 0, i M,ᄵX*ડቀ(1)bၹs t aijxj aij,i Mjj Bj Bj Bk=1sjՎxj {0,1}, j B,X*൞(CDA)֥၂۱ॖྛࢳ,ଢѓᆴW*=uujjཁಖ,ഈඍ໙ีФሇ߄Ӯູਔ၂۱؟ົॢࡗഈ֥М *pj( xkj)=j=W*Sb༯૫ᄜႨّj *pjxkjЇ໙ี(multi-dimensionalknapsackproblemj Bk=1j Bk=1jjᆣمᆣૼX*൞MDK),ಯಖඋႿᆜඔܿ߃໙ีb۷ࣉ၂ֹ҄,ࡼ(CDA)֥ቋႪࢳbࡌקX*҂൞ჿඏ҂֩ൔ֥ਆшԢӈඔ aij,ᄵଆॖ߄ູ(CDA)֥ቋႪࢳ,ᄵсקթᄝбX*۷Ⴊ֥ࢳX*0j Bs*={x01, *,x0|B|}൞(CDA)֥ቋႪࢳ,X*0 ۷၂Ϯ֥ྙൔ:X*,ؓႋ֥ଢѓݦඔᆴ࠺ູW*0,ႵW*0>W*bॉ(IP)Max pjxj੮ཟਈj BX*0S=1, ,1,0, ,0,1, ,1,0, ,0,**s t xx-*xxu-*x aijxj 1, i M2011010|B||B|0|B|j B
ֻ5௹ ٓཬႧ֩:ࠎႿᆜඔܿ߃ٚم֥ቆކචཟஅသቋႪ߄ଆ 47 xj {0,1}, j Bၞਫ਼ࣥა൧ӆིੱ֩໙ีקਔࠎԤb(ႮႿଢѓᄝႿቋႪࢳ,ၹՎޭוଢѓݦඔ֥ӈඔཛ4 ႋႨൕ২ pj)j BsཁಖIPଆ൞ֆшஅછ౦ঃ༯֥၂Ϯ߄ଆbູࢳഈඍଆ,༯૫۳ԛ၂۱ቆކචཟஅછᇀՎ֥ႋႨൕ২bࡌקచӚᇅᄯഅބਬ҆ࡱളӁഅٳљ,ૌॖၛࡼቆކචཟஅછ໙ี၂Ϯ߄ଆᇯ҄ሇ߄ູֆ၂ཛଢ֥ቆކֆшஅછଆটٳ༅ླေࣩઙބࣩછ၂ུచӚਬ҆ࡱ,ೂؿࠏaၻཙބ࣮ቖၕ,ٳљႨAaBaCսіbࣩઙٚބࣩછٚླေࢌ,ѩॖၛ๙ݖࢳཌྷܱ֥МЇ໙ีটࢳචཟஅછ໙ี֥ቋႪࢳ,Ֆطิۚૌࢳ໙ี֥ି৯ၞ֥ཛଢቆކ෮ݣ֥അᇕোaቆކб২aቋնࢌၞა؇ඔਈބБࡎೂ༯і:,ູ࣮گᄖ֥ቆކචཟஅછࢌၞࠏᇅ֥ࢌࣩѓದABCupjjࣩѓದABCupjj(1)1248320(10)0-1-110-20(2)12410260(11)-1-4010-140(3)1448280(12)0-1-24-60(4)1446200(13)0-1-26-40(5)011460(14)-1-404-120(6)012480(15)-1006-60(7)1006100(16)0-2-48-100(8)-1-204-90(17)0-4-84-120(9)0-1-18-40(18)-1004-90 ۴ऌഈඍٚم,ࡹ৫ؓႋ֥ᆜඔܿ߃໙ีѩLINDO༢܄ඳषؿളӁ)ࢳ:ࢳbЧσ২ᄎႨᄎԔ࿐ೈࡱ LINDO6 1 (ૅݓࢌၞഺჅ(ଢѓݦඔᆴ):2660 0эਈ(ࣩѓದ)ቆކඔਈֆ໊ࢌၞحэਈ(ࣩѓದ)ቆކඔਈֆ໊ࢌၞحx18 0-320 0x1010 020 0x23 0-260 0x111 0140 0x38 0-280 0x121 060 0x40 0-200 0x136 040 0x54 0-60 0x144 0120 0x64 0-80 0x156 060 0x70 0-100 0x168 0100 0x84 090 0x174 0120 0x90 040 0x184 090 0 ۴ऌЧ໓֥ᆣૼࠣࢲ:ં၂Ϯ߄֥ቆކචཟஅၞࢲݔཁൕ,ࣩѓದ4a7a9උႿ ປಆીࢌၞ ,2aછଆॖၛሇ߄ູֆ၂ཛଢ༯֥ቆކֆшஅછ໙11a12උႿ ҂ປಆЎބࢌၞ ,ఃࣩѓದඋႿ ປ,ีѩॖᄎႨࢳཌྷႋ֥МЇࠇ0-1ᆜඔܿ߃໙ีಆЎބࢌၞ bটࢳथbၹՎ,x1=x11+x12+ +x16+x17࠹ෘࢲݔඪૼ,ᄝЧଆ༯,ࡼگᄖ֥ቆކචཟ+x18;x2=x21+x22+ +x28+x29+x210;၇Ցஅછሇ߄ູֆ၂ཛଢ༯֥ቆކֆшஅછ໙ีࢳ൞uiোປಆॖྛ֥bൈ,ഈඍஅછࢌၞࢲݔԉٳඪૼ,அ,xj= xij(xij {0,1}),Ⴟ൞ॖၛሇ߄ູഈj=1છ֥Ӯࢌࢲݔ൳֞അቆކྙൔaБࡎ֮ۚaቆކࢌඍ֥IPଆѩࢳ:֤X*={(1,1,1, 1,1,1),ၞඔਈ֩؟۱ၹ֥႕ཙbᄝࢌၞഺჅቋն߄֥ଢx1ѓ༯,ؓႿᇕഅቆކ,Бࡎቋ֥ۚઙٚაေࡎቋ(1,1,1,0,0, 0,0),(1,1,1 ,1,1,1,0,0),֥֮છٚࠆ֤ࡎ۬Ⴊ൝,ุགྷਔஅછ֥Чᇉหׄ;ؓxx23Ⴟ҂ᇕഅቆކ,ቆކб২ބБࡎ֮ۚ܋थק(0,0,0,0) ,(1,1,1,1),(1,1,1,1)},ဢ֤֞xxxਔࣩஅႪ൝,ุགྷਔቆކஅછࠏᇅି۷ݺֹൌགྷሧ41718ഈඍࢲݔ,ࠧ:X*=(8,3,8,0,4, ,6,8,4,4)bࢌჷႪ߄ᇂ;ൈ,ሧჷჿඏ(ࠧuj)ބ அછ֥Ӯࢌ
48 ᇏݓܵ॓࿐ 2005୍ၩ჻(ࠧfj)थקਔࣩஅഅቆކ֥ඔਈྟb֒f[2]RothkopfMH,PekeeA,HarstadRM Computaionallyj=1ൈ,ඪૼඔਈ൞ીႵྟ֥(ࠧܥק܂۳manageablecombinatorialauction[J].ManagementSc-i),ّᆭ,ඔਈᄵ൞Ⴕྟ֥(ࠧэ܂۳)bᆃུԉٳඪence,1995,44(8):1131-1147 ૼਔЧଆؓஅછ൧ӆᇏ֥؟ဢྟࣉྛਔޓݺ֥ଆ[3]Mu Xia,CombinatorialDoubleAuctionandBusiness-to-BusinessElectronicCommerce[Z].workingpaper,theUn-i,֤ଆ۷ऎႵսіྟbversityofTexasatAustin,2001,45-55 5[4]Fan,M ,J Stallaert,A B Whinston Aweb-basedfinan- ࢲંაఓൕcialtradingsystem[J].IEEEComputer,1999,32(4):64-Ч໓֥࣮ࢲݔඪૼ:(1)࣐ܵቆކචཟஅછ໙70 ี֥ࡹଆބࢳбࢠگᄖ,ᄎႨᆜඔܿ߃ٚمॖ[5]Ba,S,J Stallaert,A B Whinston Optimalinvestmentinၛࡹ৫ቆކචཟஅછ֥၂Ϯ߄ଆ,໙ี֤֞ਔknowledgewithinafirmusingamarket-mechanism[Z].ႵིࢳथbCRECworkingpaper,theUniversityofTexasatAustin,(2)ቆކචཟஅછ֥၂Ϯ߄ଆॖၛሇ߄ູֆшஅછଆ,໙ี֥࣮֤֞ਔࡥ߄bforthcominginManagementScience,2001 (3)ᄎႨཌྷܱ֥ᄎԔ࿐ೈࡱॖၛؓࡥֆ֥ቆކචཟஅછ[6]Bikhchandani,Sushil,S deVries,J Schummer,.ଆࣉྛࢳ;൞LinearProgrammingandVickreyAuctions[Z].working,֒அછടࠣ֞նਈ֥അቆކѩթᄝ ປಆЎބࢌၞpaper,2001 ა ٤Ўބࢌၞ ൈ,౦ঃࡼ۷ູگᄖ,གྷႵೈࡱބෘمၛડቀླေbϜቆ[7]Bikhchandani,SushiandJ Ostroy Thepackageassignmentmodel[Z].workingpaper,UCLA,2001 ކචཟஅછଆࡥ߄ູ0-1ᆜඔܿ߃໙,ีࡼଆ[8]Billionnet Alain,Linearprogrammingforthe0-1֥ࢳٚم۷؟,۷Ӯඃ,ིੱ္۷ۚb(4)Ч໓quadraticknapsackproblem[J].EuropeanJournalofOpera-֥࣮ٚمაࢲંູࣉ၂࣮҄ቆކචཟஅછࢌၞtionalResearch,1996,19:310-325 ࠏᇅ֥ࢌၞਫ਼ࣥaሧჷᇂིੱa഻ࣩѓ֥थҦ֩ཌྷ[9]Freville,A andG Plateau Heuristicsandreductionmeth-ܱ໙ีิ܂ਔ่ࡱbᄝྐ༏҂ؓӫ֥౦ঃ༯,৫odsformultipleconstraints0-1linearprogrammingprob-ದྐ༏֥ࡌקࡼ҂ᄜӮ৫,ᆃؓஅછིࠛջট֥lems[J].EuropeanJournalofOperationalResearch,1986,႕ཙླေࣉ၂ֹ࣮҄b49:189-212 [10]ᅓ໓ࢭ,ລ൰ဝ Smithύ აචཟஅછ֥࣮ࣉҕॉ໓ང:ᅚ[J].ܵ॓࿐࿐Б,2003,2 [11]ӧࡴ,ӧ༄ ຩഈڇ֮ઙೆྙൔ༯֥ઙٚҦ[J].[1]RassentiSJ,SmithVL,BulfinRL Acombinatorialauc-ᇏݓܵ॓࿐,2002,10(5):1-7 tionmechanismforairporttimeslotallocation[J].Bell[12]ဎ,ԣਡ ٤ؓӫ౦ঃ༯֥؟அછ[J].ᇏݓJournalofEconomics,1992,13:402-417 ܵ॓࿐,2003,11(6):61-65 AnOptimizationModelforCombinatorialDoubleAuctionBasedonIntegerProgrammingMethodFANXiao-yong,LIANGLiang(SchoolofBusiness,UniversityofScienceandTechnologyofChina,Hefei230052,China)Abstract:Combinatorialdoubleauction(CDA)combinescombinatorialauctionanddoubleauction Comparedwithcombinatorialauctionanddoubleauction,thereisverylitterdocumentedresearchonCDAduetoitscom-plexity Anoptimizationmodelforcombinatorialdoubleauctionbasedonintegerprogrammingmethodisestab-lishedandtransformedintosingle-sidedauction,whichwillbenefittosolvecombinatorialdoubleauctionwiththemethodusedforsingle-sidedauctionandtomaketheproblemmuchmoreeasier Keywords:combinatorialdoubleauction;single-sidedauction;optimizationmodel;tradesurplus
