运筹与管理第20卷第2期Vol. 20 ,No. 2 2011年4月OPERATIONS RESEARCH AND MANAGEMENT SCI卫 组合拍卖在门户网站广告机会分配中的应用陈李钢，李一牢，艾文国(哈尔该工业大学管理学院，黑龙江哈尔滨15∞01)摘要:目前门户网站的广告机会销售主要通过价格协商的方式，这种方式不仅导致大量的中间交易成本而且分配结果常常觉法达到最优。针对该情形，本文结合门户网站广告机会的特点，建立了广告机会分配的组合拍卖模型。该模型能让广告主自由的表达广告机会之间的无堂堂界反互补效用。通过将该模烈的特例转化为…般背包问题，文中证明了该问题求解的NP难特性。因此本文针对标的本身的结构提出了四种启发式信息及两种求解器:工元蚁群算法及贪婪算法。最后通过数值实验绘出了在不同情况下，不同启发信息的性能并表明了在任何情况下二元蚁群算法比贪婪算法的寻优性更强。关键诩:管理科学与工程;广告机会分配;组合拍卖;胜出者决定问题;二元蚁群算法中圈分类号:旷文2院栋识码:A文章编号:1007-3221(2011 )02刷0108-09Allocation of Advertising Slots for Portal Websites Using Combinatorial Auctions CHEN Li-gang, LI Yiωjun， AI Wen-guo (School of Mαnagement， Hαrbin Institute of Technology, Hαrbin 150001, Chinα) Abstract: Currently, portal websites are selling their adverti8ing slots via negotiation which not only results n a lot of trading cost but can’ t guarantee the optimal revenue of portals. In this paper, we build a combinatorial auct on model aiming at the advertising slots allocation problem which can reduce the middle cost. The model can let advertisers express their non-discriminate and super-additive utility of advertising 810ts. Through a special case of our model, we prove the optimization is a NP hard problem. By using the intr nsic characters of this mod›el, we des gn four types of heuristic nformation for bid and two problem solvers: the binary ant colony algorithm and the greedy algorithm. The experiment resuIts show that the performance of d fferent type of heuristic informa›tion varies from different contexts and the binary ant colony algorithm is always better than the greedy algorithm. Key words: management sc ence and engineering; advertising slots allocation; combinatorial auctions; winner determinat on problem; b nary ant colony algorithm 。引随着互联网络的高速发展，网络广告已经成为了地电视广播、报刊杂志和户外广告以外的第四大广告媒体，也是各大门户网站的主要收入来源。我阔的网缩广告跑步较晚，但随着上网人数的不断增加以及网梅技术的不断进步，网缩广告必将成为最为铅济有效的广告形式之一。根据艾瑞资询即将发布的(2009年第三季度中阔网络广告市场监测报告》数据显示，2009第二三季度中回网络广告市场规模达亿元，收稿日期:2010-02-04基金项目:回家自然科学基金资助项目口创01009;1089∞84)作唱曾简介:I\t;李锅(1982.) Jl ~品lt人，在读博士生，研究方向:网上拍袋、搜索华管销、数据.jt;掘췲랽쫽뻝뗚㈰퓋돯폫맜샭佐剅䅎嘰䅰ퟩ돂샮났⢹햪럖싴놳쟳죎맘훐컄䅬潦䅤卬坥啳䍯䅵䍈䱩奩䵡䥮呥ㄵ䅢睥慲獥獬癩睨湯潮牥楮?汯捯扵捡杵瑨灯灡慵浯慩慴汥數慮畴獰潵灲潰楳乐桡畳捨瑹桥景瑷扩慬灥摩瑩癡晲扥䭥獣摥ヒ쯦쎽싧쓪쫕믹ퟷ䵁千湥瑨潦瑲潰慤慬灲浩捯湯獵敬摥楮扩獯慮獨杲睯敮⡓景溡癥獥湴䕒卅?獴慲灥捴浩灲潶瑩楮瑲潮物楥ㆣ犣ﺶ튪뫎춼헂䕎ꆪ湡捨扳汬慤潴楣汹獵牴楳楬浢摥睨摵浯敩散牤潢撡畲慮汯瑨晦潭扩睡瑴룥뷰헟ㄱ엤쒣냼뷢볼渭乁䥅杯㈰汯癥潴偯楮捴〰꽴湵牦數瑥ퟅ쳥벼뗚浢敩慤瑩潢摤獴渭灥ꎬ獩畲景汶杲慬潷慴敥牤杩䅔䅒튻컄扳楴慮犣楯湧敳?浩楮物湣捨샮긲ﮱꎺ쟩럖뇪뇠?条来湯牡楴楮癥汴慬楣捥摥玣楡沣汥慣楳特湹物敲瑳湡祳楯죕쿮볲䝅乃瑩쓪뷡탍컊웷듊畮杵䥏䍈畴?楮瑥浡깷汥ꎮ摩犡穡獩睥杮牭敲敥杯浥摹物玣湥뻭뫏捡牴楯潲뮥ꎬ쫵죽䵅?潯慴ィ〱쒿뿶샠쪶뫅楮湧浥汯捴敳牴玣깔걷涣瑥瑩瑨敮特湳웚뷩乓뻼맺楴湴㓔맻ꆣ쳢ꎺꎬ?楳瑩周獣ꑡ慴玣摹物憡瑨멭敲룖乔楯뗚걎?ꓒ잰쿂뫅싫ꎺ瑩楳慬湳ꎬ湴杹깉潲桲깂牳浡ꎻ楮뭢솪튲뗄벾潮慴楮潮敲物摤楯면瑨涣慮?뎣룃ꎬ뛾맜䅉澣떴쏅뛾ꎺ敳䱉ꎬ䍵楮?楡潵睩㈰맺돂㋆엄潮楮䍨湣慴췸쫇늻뛈ꎬ?浩楴桥涣慧枣ꎻ뎣쒣컄풪샭긲뮧䘷?〷潲䡡牲杨湮慲쇈샮湡楶깔敭뭡捯?楮楯싧룷뛏ꞹ췸컞탍훐틏뿆ㄳꎮ牢敮敲?ퟔ룖楡瑥?桥敮摶浢싴?햾ꎮ㌲楮愩瑬?뗄듳뷸맺〲좻⠱램쓜횤좺톧?敲楮뗄쯣㌵㈱?禣ꎮ뿆㤸듯죃쏷쯣폫룟쏅늽췸瑩慴맣램?⠲거〴톧㈭떽맣쇋램릤獩潲퓚쯙뮧ꎬ싧몣룦뇈〱潲믹⦣湧楡ퟮ룦룃벰돌겺믺첰ㄩ瑡랢췸맣뷰계?폅훷컊첰ꎻ?믡삷〲?퓰킣쏅햹햾싧룦諾쿺ꆣퟔ쳢삷쯣맣ꆪ훺꺸ꎬ뗄맣쫐궹쫛램〱쿮ꎽ헫평쟳쯣룦뮧ﺶ훷뗄〸췸룦뎡쒿뛔뗄뷢램믺ﮱ튪톰ꆪ⠷쮣싧뇘볠룃뇭뗄ꆣ믡춨폅〹〶곔췸쟩듯乐ퟮ럖맣쫕붫닢㔰맽탔〱?탎맣쓑뫳엤〰볛룼룦죫돉놨솲ㄩ룱ꎬ룦쳘춨잿ꎻ㦣꧊햾틑살캪킭ꆣ묷뿉놾믺탔맽ퟩ뺭풴ퟮꆷ짌〸画컄믡ꆣ쫽뫏맣뗄돉ꆣ캪쫽㤰껑뷡횮틲횵엄랽〸킾캪컒뺭뻝뫏컊듋쪵싴쪽㐩뾷룦쇋맺볃쿔쏅뗄놾퇩ꎻꎬ뷏헢뮧컞컄룸쪤볌뗄폐쪾훖뫍췸닮헫돶믺뗧킧ꎬ랽햾틬뛔쇋헟쫓싧뗄㈰쪽쿅맣벰뇪퓚뻶믡늻맣〹쓂룦뮥뗄늻뚨뷶능룦뗚믺늹놾춬컊떼ꋋ럖ꆢ웰탎죽훂믡킧짭쟩쳢퇋듳놨늽쪽벾뗄폃뿶ꎻ솿엤쳘ꆣ뷡쿂뛾뾯뷏횮뛈뗄뗣춨릹ꎬ풪퓓췭튻훐瑱ꎬ맽쳡늻틏훐볤횾ꆣ맺ꋊ붨붫돶춬좺붻ﶾ뫍떫룹췸틗솢룃쇋웴쯣?뗄뮧쯦뻝싧돉?쇋쒣쯄랢램놾췢ퟅ났?맣탍훖탅뛸펦맣짏죰룦뗄웴쾢쟒믺쳘랢뗄룦췸쫐믡샽쪽탔폃틔죋톯뎡럖탅쓜췢쫽벴맦엤뮯쾢늢뗄붫쒣뗄캪벰뇭뗚늻랢듯ퟩ튻솽쏷쯄뛏늼㔷뫏냣훖쇋듳퓶뗄ꎮ엄퓚맣볓⠲㓒룦틔〰?벰?ꪣ췸?
第2期陈李钢，等:组合拍卖在门户网站广告机会分配中的应用109 环比增长%，问比增长%，季度市场规模创下历史新高，其中搜索引擎广告市场规模为亿元，品牌图形广告市场规模为亿元，环比增长达%。目前门户问站的广告运营机制主要有由品牌广告和付费搜索广告两种形式，其中品牌广告包括品牌图形广告、固定文字链广告、分类广告、富媒体广告和电子邮件广告等各种形式，而付费搜索广告则主要慕于门户网站的搜索引擎提供关键宇竞拍业务。本文的研究问颇为门户网姑品牌广告的广告机会分配。目前，该广告形式的销售主要涌过门户网站发布报价单，然后广告吏和销售代理协商议价购买。这个过程不仅给广告虫带来和销售代理交互的额外工作也给销f替代理带来决定接受哪些广告合同的大最计算工作。此外，小广告主可能会因为额外的开销及销售代理的不理性决定而无法得到广钳机会，门户闷地也因此而蒙受损失。本文设计了门户品牌广告机会分配的组合拍卖系统，该系统能接受任意广告主的出价且能为门户网站决定最好的广告合间。拍卖作为一种有效率的分配机制，巳经应各行各业中发挥重大的作用。在一般的拍卖机制中，拍卖品的价值是相互独立的，投标者为每个标的设立单独的价格。但是拍卖品之间可能存在着互补或者替代放用[1]例如网站页丽的动翩广告位和文字链接广告位这两种广告机会组合的价值可能比它们单独价值之和高。即对于任何两个物品i租j;之间，如果存在V( li ,j f ) > V( li f ) + V( /j f ) ( V( . )为物品的价值踊数)，则i手nj之间存在互补效用，如果V(ji,jl ) < V( lil ) + V( UI )则i和j之间存在替代效用。组合拍卖能有效的让宽标者表达互补敢用[2J和替代效用[1]目前广告机会的计费以天位单位，即xx万元/灾。如果将广告机会/夫当作一个拍冀品，那么门户网站的广告机会分配可用多单位组合拍卖[3，4J对该问跑进行建模。除此之外，广告主对某些页面上的广告机会或者问一页面上的广告机会的效用可能会相间，如(新闻页上的文字广告和娱乐页上的文字广告这两种广告对某些广告主可能放用咒禁异)，因此模型中要能让广告主表达对不同广告机会的无差异偏好。目前门户网站广告机会分配的相关研究还较少。Uriel和Nicole等的研究[5J和本文的研究较为相近。他们研究了~门户网捕无法满足广告烹所要求的展示次数时对广告主进行补偿的情况下广告位的分配问题，所用的机制也为组合分配机制并采用贪费及自选w.算法求解。本文与该研究的主耍区别:在伪们的模型中不能让广告主表达无盘界广告机会;价格机制不间，他们来用让广告虫为每展示出价，而本文采用和门户闷站更为接近的以天为单位的价格;此外本文不考虑惩罚的因素，因为在模型束解时已经考虑了资澜的约束条件。国内关于组合拍卖的相关研究主要在于采购和供应商等领域[川，将组合拍卖运用于广告位分配的研究还较少。1 问题描述假设一个门户网站有若干个网捕，每个网站有若干个网页且每个网页有者干个广告位。由于每个页面上不问广告位有不同的广告形式:按钮广告、文字链t荣、浮功标识/流媒体广告、画中画、新闻内页小通栏。则把每个页面上的不问广告形式~作…个广告机会(例如把搜索酋页酋屏中下大按钮3轮换当作一个广告机会，新闻频道首页酋辟遇栏附侧静态两翻牌按钮2轮换为另外一个广告机会)，那么门户网站上的所有广告机会集就组成了组合拍卖中的物品。具体的，让S= IAI ，A2尸•，A"，\表示门户网站的广告机会集，T=I t，马，...告机会,t1 ，t是相应广lm i儿的可用单位数(1<i<m，tiE.!YJo让B= I b,b, ,b. I表示广告主的投标集合。其中铸个标的包含两1 2部分内容:第一部分是广告主感兴趣的广告机会及数量列表，第二部分是广告主愿意支付的价格。一个标的的铺构如下:b= I ( <川，qi\>, <l怡，ql2>, , < U,qi/ > ) ,Pi \ ，其中UitcS，是广告吏认为的无援界广iil 告机会集合，qolt是广告主对这些坚元整广告机会所费求的数量(天数)，p，是广告主的报价。假设b嚣I( < 5次I A,A31 ,5 > ) ,10 I ，该标表示只要分配给广告主广告机会A和儿共5次(可以是Al或者5次A3或1 1者1次A4次鸟，即Al和A3的任何组合)广告主都将支付10个单位的报酬。~差异广告机会的表示不1仅使广告主能得到不问频道上的广告机会，也使门户闷站的广告机会被充分利用。门户网站的目标为在满足广告机会可用数的限制下，从所有标的中选择最大化其收益的广告主，井将广告机会分配给这蜡广告主。该目标可用如下的规划模那表i事。췲랽쫽뻝뗚뮷풪없룦놾놨튲쫛럖엄뗄폃횮쫽싴죧탐⣐쓜쒿쯻쳢탍쏅캻?컊볙쏦삸룶뻟䆡늿筁헟뷶맣돂?㋆뇈ꎬ맣뫍컄볛룸듺엤싴ꆭ⦣쓜맻붨싎죃잰쏇훐뮧풼럖짨짏ꆣ쯹뗄믺ㆴ쪹룦쳢쳥ꎵ샮?퓶욷룦뗧뗄떥쿺샭ퟷ횵ꆣ룟곔폐붫쒣엒맣쏅퇐쯹늻췸쫸엤튻퓲쓚뷡믡ꎬ칁믺쏨룖쒿뎤없뫍ퟓ퇐ꎬ쫛뗄ퟩ캪쫇샽ꆣ킧맣돉룦뮧뺿폃쓜햾쳵룶춬냑믺죝릹벯䆣믡쫶ꎬ㈶춼뢶폊뺿좻듺늻뫏튻쿠죧벴뫍뗄룦돽쾵훷췸쇋죃룼볾퇐쏅맣쎿믡ꎺ걽㒴럖짓뗈죃ꎮ탎럑볾컊뫳샭엄훖뮥췸뛔御죃믺듋쓎뇭햾떱맣캪ꆣ뺿뮧룦룶뗚쿂ꎬ칁쓜쒿엤ꎺ쎵朽㊣맣쯑쳢듸탔싴폐뛀햾폚뫖뺺믡횮쓗듯쏅훆룦뷓맺뮹췸캻튳탂튻ꎺ柖㔾ꎬ뗃뇪룸ퟩ筁ꗎꖣ룦쯷캪살뻶쾵킧솢튳죎꺼뇪ꎯ췢횹뛔뮧튲훷뷼쓚뷏햾폐쏦컅벯늿抣맊⦣ꎬ떽헢뫏ꆣ곍쫐맣뗈쏅훷뻶뚨춳싊뗄쏦뫎헟쳬ꎬ늻믺췸캪뇭맘짙폐짏욵뻍럖묽잹갱벴퓚킩믊엄겱뎡룦룷뮧뫍뚨뛸ꎬ뗄솽뇭떱맣춬믡햾ퟩ듯틔폚ꆣ죴뗀쫇笨ぽ䆣싺싴ﴨ죔맦솽훖췸쿺뷓컞룃럖춶뚯룶?듯ퟷ룦췓맣뫏쳬ퟩ룉뗄늻쫗돉㲡ꎬ겺욵ퟣ䆣퓚쒣훖탎햾쫛쫜램쾵엤뇪뮭컯ꖲ뮥튻훷룦럖닮캪뫏룶맣춬튳쇋ㄼ끮룃쵁뗀몡쏅ꐱ캪탎쪽욷듺쓄뗃춳믺헟맣말늹룶뛔훒뗄싺엤틬떥엄췸룦쫗ퟩ훷ꎬ퓕뇪짏ꆣ궣椼뮧㞣㈳쪽ꎬ없샭킩떽쓜훆캪룦榺ꟓ킧엄쒳돉믡쿠ퟣ믺맣캻싴햾탎웁뫏룐熣뇭뗄룃췸꺣涣긹ꎮꎬ뛸맣킭뷓쎿캻춣쎣폃싴킩쾵뗄맘훆룦쪽탎춨엄탋뮡쪾죎믡쒿햾걁ꎥ㣒웤뢶룦짌쫜틑룶뫍곖곈ꆧ욷튳쓎컞퇐늢믺볛쿠쎿ꎺ쪽삸싴좤ꌾ?횻뫎뿉뇪건맣ꆣꎬ?훐럑뗄틩뫏믺죎뺭뇪컄꺼ㆺ쏦쓗닮뺿훷닉믡룱맘룶내떱솽튪ퟩ폃뿉룦ꎻ綱벾ꪣ욷쯑맣볛춬믡틢퓚뗄ퟖ﮿췌쓇짏횹틬뮹쯹폃ꎻ퇐췸얥ퟷ닠㲢럖뫏쫽믺ꇊ뛈겻없쯷룦릺뗄ꎬ맣룷짨솴ꏈ쎴욫뷏튪첰볛듋뺿햾튻뺲컯엤⦹죧믡쫐랱맣믺싲듳쏅룦탐솢뷓筩𢡄뫃짙쟳삷룱췢훷폐룶첬욷?請룸튲쿞쿂뻃?럖뎡죔룦믡ꆣ솿뮧훷룷떥맣﮴ꎬꟓ뗄벰믺놾튪죴ꆢ솽걱쪹훆얻엤ꆣ맦냼퓲럖헢볆췸뗄튵뛀룦䩽쎡믺뷖啲햹ퟔ훆컄퓚룉랭벰사戮쏅쿂훐쒣꒴삨훷엤룶쯣햾돶훐뗄캻?⤼궡믡횹楥쪾쫊늻폚ퟖ믺없죃쫽㺣벽뮧ꎬ뮮뗄뒴욷튪ꆣ맽릤튲볛랢헢⡻嘨ꏄ뗄믲沺듎펦춬뾼닉췸솴믡내솿겡맣ꯖ듓쒣䈽펦뺵쿂㞣없믹쒿돌ퟷ틲쟒믓룱솽暣筩뿇맣헟쵎쫽쯣ꎬ싇릺튳뷓⣀얥쇐궣쓊룦Ꞹ햾쯹탍폃쒹筢샺긱춼폚잰늻ꆣ듋쓜훘훖걊紩낹룦춬퓄楣쪱램쯻돍뫍쟒ꆢ㋂뇭갼ﷁ믺뙬뗄폐쪷ꎥ탎쏅ꎬ뷶듋뛸캪듳떫맣紩⭉믺튻돐潬뛔쟳쏇랣릩쎿뢡횻ꋲ뼨믡澸뇪쫶ꆣ탂ꆣ맣뮧룃룸췢쏉쏅뗄쫇룦㹉ꎬ믡튳ꦹ斵뷢닉펦룶뚯퇋믎뗚楦쳬䆡ꎬ룟쒿룦췸맣ꎬ쫜뮧ퟷ엄믺⡻請럖쏦좵ꆣ폃틲짌뇪퇋꫁뛾쫽ꎺꗎ훐抣ꎬ잰ꆢ햾룦킡쯰췸폃싴믡⡻御엤짏쓑훷놾죃쯘뗈튳쪶늿熡⦣쵁뮵톡웤쏅만뗄탎훷맣쪧햾ꆣ욷ퟩ楽멽쒼뿉킾뷸컄ꎬ쇬폐ꎯퟒ럖ꌾ걐쒱놻퓱몣꾣훐뮧뚨쯑쪽듸룦ꆣ뻶퓚횮뫏⤫⧔욷폃맣진뾡탐폫틲폲죴쇷돊뮸쫇⦣槊릲ꢳ돤ퟮ걔겡쯑췸컄쯷뗄살훷놾뚨튻볤䦣퇒뛠룦?넱늹룃캪ꆧ룉쎽ퟆ맣걐잹㖴럖듳㵻쯷햾ퟖ틽쿺뫍뿉컄ퟮ냣볛갨퓌떥믺ꟓ뎥퇐캪퓚ꆯ룶쳥쇖궣룦ꆣ츨ꏎ샻뮯璡틽뗄솴쟦쫛쿺쓜짨뫃횵筟ꎮ캻믡쏎놾뺿쎿쒣ꆰ맣탏훷綣뿉?폃웤걢ꎣ쟦맣쳡훷쫛믡볆뗄엄듦뿉ꆺ뮵ퟩ?컄쟩햹탍ꎬ룦슴請풸곆틔ꆣ쫕ꆣ맣룦릩튪듺틲쇋싴퓚쓜紩횮ꗎ뫏킧뗄뿶훷쪾쟳붫캻ꆢ건틢쒱쫇틦룦퓋ꆢ맘춨샭캪쏅믺ퟅ뇈⡹볤뮣엄폃퇐쿂튪돶뷢ퟩꆣ뮭듅ꎬ횧킡ꢼ㖴뗄ꎺ綱쫐펪럖볼맽붻뛮뮧뫏훆뮥쯼⢣듦겼싴뿉ꎬ뺿맣쟸볛쪱평훐ꔳ쓇뢶냈?칁ꆭ뎡믺샠ퟖ쏅뮥췢욷춬훐늹쏇긩퓚둘⊡쓜틲뷏룦뇰ꎬ틑엄폚뮭싖쎴뗄썣ꎼꆣ請ꎮ뺹맦훆맣뺺뮧뗄없ꆣꎬ믲떥캪쳦壍꼴믡듋캻ꎺ뛸뺭싴쎿ꆢ뮻쏅볛킴?훷ꎬ쒣훷룦엄췸뛮뾪맣헟뛀컯듺ㆶ쿠뗄퓚놾뾼퓋룶탂떱뮧룱ꎬ쒱璡캪튪ꆢ튵햾췢쿺룦싴쳦볛욷킧ꪣ풸춬탍뷼럖쯻컄싇폃튳컅ퟷ췸ꆣ쫇㵻㖴늢ꍽ㈰폐뢻컱랢릤벰믺욷듺횵뗄폃꿌쏎ꎬ훐ꆣ엤쏇닉쇋폚쓚튻햾맣⠼칁뺲붫ꎬꎮ평쎽ꆣ늼ퟷ쿺믡킧볛쫌죧튪컊뗄폃맣튳짏룶룦?㋒욷쳥횵ퟩ?쒣뫍풴룦킡璣뇪훷믲쓍?맣몯뫏춨죏믊뚱엄캪쟏뗄컞ꚹ꾺닮쾡틬맣ꏆ請?탃뾸쒰ﲺ곁?
运筹与管现2011年第20卷110 J·A、‘， ，，••飞max imize subject to L L Y~.) :$; t. ( 1运a运m)(2) (3) 工yJa}-zsqeJ=0Xe 10,11 (4) j y~.) e N且(y~.)= 0, VA. f1.问(5)(1 :$; i:$; :$; j:!运l)(6) yJa}其中X是二元选择变最j，~值为1时表示相应的标的b被选中，为0时表示不选中该标的。表示j广告机会A.分配给广告主i第j个子集的数目，如果子集叫不包含扎，那么其值为0。目标踊数保证门户闷站从拍卖中获得最大收益。约束(2)保证分配的广告机会在资掠限制内。等式约束(3)保证每个被选中的广告主标的中的每个子标所需广告机会的数最被满足，从而整个标的所需求的广告机会数量被满足。['1文献哥|入了具有惩罚机制的广告机会分配模型，使得部分分配成为可能。模型(1)也能方便的加人惩罚机制，不过广告主需要给标的的每个子集设定你价，则子你为一个王先组bij表= <町，qij，Pij>，Pij示锦单位广告机会的价格。惩罚机制下门户网站的收益函数为(7) PUZyymspu(qqmZU) 公式(7)褒明门户网拙的收益为巳分配广告机会的收益减去未能满足广告主需求的惩罚o其中8表ffi惩嚣罚的力度，…般情况下，δ1。那么惩罚机制下门户网站的目标收掘模型为mvh ，，‘句、，&a 、‘，.,-u ma x m E Z γJ ny Da ae J(8) subject :$; S02:zd}运七a运m)(9) (1 ZYJe}gqu 0) (1X( 11) e 1011 ,ij 和条件(5)和(6)。其中Xìj是二元选择变量，表示是否选择广告主i的第j个子掘。约束0)(1保证分配给广告主的机会不多于其要求的数量，因为多分配并不能给门户间地带来多余的利润。定理1模型的求解是NP究企问题。证明NP兜全问题可以通过问题的特例求证，即如果问题的特例是NP难，那么问题本身也是NP难。假设模型(1)只限于帮查满足下列条件的分配问题:所有广告机会是同质的，且每个标的子集的个数为1，那么该特例本质上是o1宵'Êl问题(将广告机会的可用单位数着作是背包问题中的容最约束，每个标的所要要求的数最看作意囊，出价为价值，那么该问服是典型的。叩1背'Êl问题)。由于棋那(1)包含背包问题作为其特殊情况，从而由背包问题的NP完全性知诙问题也是NP完全的。[510问(8)1æ本身不仅愚NP完企问题且其o<c运1近似也是NP宪全问题本文只讨论模那(1)的求['1解，对问题(8)感兴趣的读者可进一步参考文献愚然组合拍卖的胜出者决定问题已经有很多相关的研究，但是由于文中的模剧和一般组合拍卖模型的不一致性，使得之前的相关研究无法适用。针对求解问题的特点，本文给出了四种启发式信息及两种求解器。2 问题求解 可行解检测组合拍卖算法中需对胜出者进行可行解检测，判定给定栋的集合是否满足系统的资游、约束。在一般的组合拍卖算法中，通过整加所选定栋的中每个项目的数量与系统资搬进行比较就能得出其可行性，但是췲랽쫽뻝ㄱ퓋돯폫맜샭㈰浡業⠱퓙?獵景⠲ꆮꇆ⠳⠴⦣仇⠵⠶웤맣췸훐컄죫쪾傿⠷랣㈱瑯⠸랦컥쯣뫍폚뚨횤乐쓑캪뇪컊뷢퇐쳢㋎㊣ퟩ뗄䨱ꆣ??룪⠱릫⠹?ㄱ扪ㄩ룦햾뗄쿗돍쎿ꇜ〩ꋲ쳵웤샭쏷췪ꆣㆣ쳢ꎬ뺿긱뫏ퟩ훐쫌楺ꎺꇆ禡겣툨ꆣꇜ쪽??쓪散믺듓맣ꆮ랣떥솦뿚ꇊ볾쪯튪㇄좫볙계쯹ퟷ⠸뛔ꎬ쳘뿉엄뫏룪斡ꇊ榡⠷禣뗚?ꇆ?뫮ꎬ斸믡엄룦㔱믺캻뛈ꇜ笰⠵ꎻ쟳ꏐ컊짨쟃튪캪⦱떫뗣탐싴옩ꆣ㈰笰?⦱외몡䆡싴훷틽훆맣ꎬ洩⦺뗄춵쳢쒣뒸쟳웤뻉쫇뷢쯣⦣뭸깅뻭ꎬ쫇?汰ꎷ훐뇪죫ꎬ룦튻놡ㅽ촨쫇쫽쓇뿉탍쏌뗄쳘⠸평놾볬램쯣겣楱ㅽꇎㆡ⠲뛾훅믱뗄쇋늻믺냣㘩뛾솿틔⠱?쫽쫢뮽⦸폚컄닢훐램ꆮ??ꇎ얻풪뮡뿚㴰ꇆ뫮뗃훐뻟맽믡쟩ꆣꎬ춨⧖ﶱ솿탐컄룸탨꺡뿚톡ퟮ뗄폐맣뿶틲읎맽믏뻖뾴쯈훐돶뛔튻?㴰ꎬ禡꺡몡퓱듳쎿돍룦볛쿂캪働컊?쫉ퟷꎬ꒵뗄쇋쪤춨뺵?奁컒?좴쫕룶랣훷룱ꎬ뛠쳢?쿊훘듓쒶쒣쯄돶맽뇤?쓊ꆣ틦ퟓ믺탨?뮿럖ꯎ뗄벲윰뛸쇕탍훖헟뗾솿用헒뗚ꆣ뇪훆튪돍㴱ꎬ엤쫌쳘ꆪ평?뫍웴뷸볓⠱ꎬ?ꎮ풼쯹뗄룸랣枿ꆣ뇭늢샽𧻓ㆱ돶놳즽튻랢탐떱ꇜꋲ?ꆺ쫸탨맣뇪믺쓇쪾늻?쟳뎰볛냼틆냣쪽뿉톡톷횵?룶⠲맣룦뗄훆쎴쫇쓜횤싁ﳎ캪컊뮲ퟩ탅탐뚨憡甩籐훅캪ퟓ⦱룦믺뗄쿂돍럱룸ꎬ탌쫌볛쳢㱃붲뫏쾢뷢뇪뮡??㇊벯ꏖ믺믡쎿쏅랣톡벴횵뗄ꇜ캿엄벰볬?욣놱뗄꒷믡럖룶뮧믺퓱죧ﺵ붫ꎬ乐沽볎싴솽닢훐쫽훅뗄엤ퟓ췸훆맣맻쒷쓇췪ﳋ쓏쒣훖ꎬ쎿겣請쒿쫽쒣벯햾쿂룦컊훅쎴좫웒힡탍쟳에룶뻏ꎬ쒹솿탍짨뗄쏅훷듸쳢믺룃탔닊넱뷢뚨쿮겡쓊죧놻ꎬ뚨쫕뮧榵살뗄쫌믡컊횪읎ꆣ늻웷룸쒿ꚵ헒?맻싺쪹뇪틦췸쒵뛠쳘뗄쳢룃働쯤튻ꆣ뚨쒱ퟓ請ퟣ뗃볛몯햾?폠샽뫋뿉쫇컊좻훂뇪쫽벯ꎬ늿쫽뗄꺡쫇陸폃뗤쳢ꯎퟩ탔솿ꗎ쑢疡?듓럖퓲캪쒿몸샻乐킹떥탍튲쫌뫏ꎬ벯폫듄ꎻꎣ쫔뛸럖ퟓ뇪죳쓑캻뗄쫇엄쪹뫏쾵?겲듏헻엤뇪쫕펱ꆣꎬ쫽ァ乐ꆿ싴뗃쫇춳놻𧻓뮰?룶돉캪틦쓇請뾴ꨱ췪ꆣ뗄횮럱톡ﲺ웄뇪캪튻쒣ꏔ쎴ퟷ놳좫놾쪤잰싺풴훐걁?뗄뿉룶탍볊컊쟍쫇냼컄돶ퟣ뷸ꎬꆣꎵ쯹쓜죽캪쳢곖놳컊횻헟쿠쾵탐캪ꎬ죊탨ꆣ풪놾쪵냼쳢쳖뻶맘춳뇈ナ쓇뷔쟳쒣ퟩ⦱짭컊⦡싛뚨퇐뗄뷏놱쎴볊뗄탍扆ꏖ튲곇쳢ꏓ쒣컊뺿뻍쒳웤맣⠱㴼꒷쫇틃훐짓탍쳢컞풴쓜춷횵㌩룦⧒畆훅乐뾸뗄?⠱틑램풼뗃뺲ꎡ캪놣믺닄ꎬ죝ꏐ⦵뺭쫊쫸돶믑ꏆァ횤믡?杆솿촨쓇폐폃ꆣ웤ꇖꏄ쎿쫽붱ꎬ쓗풼ㄩ?뫜ꆣ퓚뿉킸탕뾱룶솿傿펼쫸냼뛠헫튻탐벱쎱놻쒼?꾵ꎬ몬쿠뛔냣탔꿊톡싺?ꎬ쒻쒸쎿놳맘쟳뺳쒡ﶱퟣ灵請룶냼뗄뷢떫?ꍹꍩꆣ뇭?컊쫇뮶ꎺ✭?䦻뇭?쪾
第2期陈李钢，等:组合拍卖在门户网站广告机会分自己中的应用111 文中的模型无法通过简单的叠加进行可行解检查。常在给定脉的集合B=lbl'b，…，b姐1，检测并解以下2约束方程L LY~.)运仁(1延α运m)(12) 工Y~.)-qij 0 (13 ) 和一般的组合分配或者多单位组合分配不同，本问翩的可行性监测不仅要检蠢系统的可用资源是否能满足所有标的的要求，还要计算每个标的子集中每个广告机会所得到的数目。为此本文将该问题转化一个整数规划问题，目惊丽数为minimize L L L Y~.) (1 4) 并且满足约束条件(12)、(13)和(5)。目标函数(14)保证在满足广告主需求的情况下最小化门户闷站的广告机会支出。当整数规划(14)有解时，那么给定的栋的集为可行解，yJa)的值为分配给广告主i的第j个子标中广告机会a的个数。如果(14)不存在可行解，那么给定的栋的集也就不可行。 启发式信息启发式信息可以加快启发式算法和求解NP难间是自算法的收敛逮度。文中标的的启发式信息可以分为两种:(1)钱性拉格朗日松弛:所谓的拉格朗日松弛就是通过去掉原问题中的复杂约束，得到一个比原问题易于求解的松弛问题。通过将0…1工冗变量X，松地为O到1之间的实变簸，即松弛后的决策变量是O到1之间的实数，原NP问题变为P问题。求解后将矶的值作为衡盘bj好坏的启发信息。(2)标的本身启发式倍息:即通过挖掘栋的的结构信息(价格、所要求的数量、所要求的种类)，从附得到有指导意义的信息。i在类启发信息有以下三种:(A)β·开方单位价格W，口b/(L qi)β(15) βe[O，I]，即用标的价格和所需求的广告机会数景之比作为启发信息。当β为O时，就只单纯考虑标的价格，~β为1时为平均单位价格。β的最优值可以在多次实验之厉得到，一般在附近。(B)增强型单位价格Pi (16) W-;; i 1五(q片l们)0,-1 增强型单位价格考虑了标的子集的长度及子集中包含项目多寡的倍息。当你的子集长度姐{旦子集项目多时诙栋的就相对较好，体现为λ<1，0>1其思路是当子集包含较多项目，则可替代的项目也较多，而子0集长皮短时所请求的项目就较少，从而标的更容易被满足。( C)带资惊占有率的单位价格以上两种启发信息从标的本身的结构出发，没有考虑标的所请求项目的资源可用数。假设系统中有四个广告机合AI、A2，A，和A可用数目分别为p(40，35，10，5)，标的b为(< 1A 1 , AI 15 >, 50) ，b为l2 2( < 1儿• > ，50)，在同样的价格下，由于bl的资掘出有率为(15/75)而b的系统资概占有率24为1，那么显然b就更可选，因为着系统中还有标的b，为(< 1A 41 ,4 > ,10) ，如果选择了b那么b将不123可行，但是b，利队能组成可行解。资源占有率从资源稀缺性的角度出发，如廉峙的所谓求的项目都是稀缺资源，那么其竞争力将较小，反之竞争力较大。综合了资源占有率的启发信息如下饥"(17) r10(L (qijÀI.~-I))βtl( L (q旷工t1))) 9’ 0其中t1)表示子标中所需求的广告机会α的可用数目。在(17)中伊<1，表示资源占有率的意要性。扁发信息(17)综合母虑了(A)和(B)两类信息，包含的信息更多。췲랽쫽뻝뗚汬컄풼?ꇆ⠱ꆮ䪡뫍ퟣ헻浩늢맣룶㊣웴캪틗㇖⠲떽?슬볛⣔?퓶쪱벯⡣틔쯄⠼뿉좱통⢡ꆻꎬ䤽웤탅?㈱ꍉ?돂琱㵬?㌩㋆훐쫸㈩튻쯹쫽㐩쟒ퟓ긲랢솽⧏폚꺼⦱폐㔩䕛룱묩㘩잿룃뎤⦴짏룶筁ㆣ탐㜩쾢룦ꇆ禡湩ꎻ온샮⢡?뗄랽냣폐맦싺뇪웴쪽훖?쟳횸ィꎬ퓶탍뛈솽맣계풴⠱믺룖昽璣禣컒浩㴶煆쒣돌뗄뇪뮮ퟣ훐랢탅ꎺ퓀뷢쓊쒱떼갱떱잿Ꝩ떥뛌쫔훖룦ꎬ쟃떫㜩믡ꎬ뫇탍ퟩ뗄컊풼맣쪽쾢궸뗊뻉틢嶣슬캻뻍쪱듕웴믺䆡듏쫇쓇ퟛ뫉뭱穥ꎻ뗈횧㦡컞뫏뗄쳢쫸룦탅뿉쯉ﶣ틥겼캪떥ㆡ볛쿠쯹볓랢믡ꍽ퓈抡쎴缾ꎺ뿚ꇆꎯꎡ돶램럖튪ꎬ쳵믺쾢틔쫈돚곔뗄듓㇊캻ꌱ룱뛔쟫탂탅䆣뭢ꎺ웤뾼ퟩꆣ?㴰ꇆ⢡뀹춨엤쟳쒿볾믡볓헋컊굎ꋊ탅쎱뇎볛뾼뷏쪵쾢꺡ㄵ쵢뺺싇뫏ꪡ⦡뻗떱맽믲ꎬ뇪⠱뿚뿬즳쳢僎뷐쾢룱싇뫃뗄쒵듓ꉁ㺣뻍헹쇋ꆣꇆ왧ꆪ엄펱볲헟뮹몯㈩헻뗄웴?ꆣ쫌엏쒼붾?쇋ꎬ쿮ꗎ뇪ꎺ갵룼쓜솦⡁싴⡉禡ꋲㄩ떥뛠튪쫽ꆢ룶랢뫋춨ꊣ룃?例ꪡ뇪쳥쒿뮼뗄〩뿉ퟩ붫⦺퓚뗄ꇜ떥볆캪?⠱쫽쪽硫맽몼샠⧂ꗎ쿖뻍?놾䆣ꎬ톡돉뷏⤹촨맦탋쏅뗾캻쯣㌩ꆣ붵붫꩐듍웴췋뮼ퟓ캪뷏?짭겺퓚ꎬ뿉킡䈩澡뮮?炡뮧ꪶ類볓ퟩ쎿뫍죧램쓀ァ컊ꢹ랢類?벯䄼짙뗄쵁춬틲탐ꎬ솽췸⠱?낡뷸뫏룶⠵맻뫍궸ꨱ쳢탅뗄沣ꎬ뷡ꆣ퇹캪뷢랴샠햾㐩탐럖뇪⦡⠱쟳뛾ꆣ?쾢ꏂﺡ뎤곈듓릹ꎬ뗄죴횮탅?ꌱ맣폐뿉엤뗄ꏄ㐩뷢쫈풪쟳쒹겵뛈픾뛸돶볛쾵뺺쾢룦⢡뷢탐늻ퟓ뾱乐헋뇤틔쓗벰ㆡ뇪랢폃룱춳풴헹ꎬ믺온뷢춬벯쪱듦쓑즳솿뫳쒵쿂ퟓꏆ뗄ꎬ쫽훐햼솦냼믡볬ꎬ훐꿊퓚컊?립붫쒽죽請엖벯룼쎻쒿뮹폐뷏몬熿럖닩놾쎿ﴨ뿉쳢췊ꆣ룪훖떿?훐볂죝폐럖평싊듳請뗄쓇엤?ꆣ컊룶ㄴ탐쯣쟍쯉榵말ꎺﷁ짒냼럊틗뾼뇰폚뇪듓탅쎴훐탨쳢맣⦱뷢램ꢹ돚쓖엏⡁뿖퓔몬잵놻싇캪㘱뗄ퟛ꾡쾢뗄룸퓚뗄룦ꏖꎬ캪뗗ꈨ⦿꺱?쿮뇗싺뇪⠴抣풴뫏룼왴펦뚨룸뿉믺ꓔ쓇쫕ꖵサ볛?죗쒿펼ퟣ뗄ィ곎쾡쇋뛠폃뗄ꎺ뚨탐믡?쎴솲뵬ꪺ룱뮿컊뛠꾰ꆣ쯹갳풴ꨨ좱폃뇪탔쯹𧻓룸쯙귎횮ꆢꪷ뗑맑ﲺ쟫㖣햼㱻풴㒡쫽뗄볠뗃뚨뛈쫌볤뽢쯹붵경쟳갱폐䄴햼꼩쒿벯닢떽뗄ꆣꎻ튪ꗎꋐ꺺탅쾶쿮ィ싊綣뷇폐ꆣ⤹뫏늻뗄뇪컄킵쪵뫃쟳뮼엏쾢쒿갵갴뛈싊캪䈽뷶쫽뗄훐쒸뇤뮵?ꊡ쎵ꆣ⦣ィ㺣돶퓚뿉筢튪쒿벯뇪듔솿뗄쫽?ꎵ붣떱뾣겱긲갱랢웴⠱탐ꆣ볬튲뗄폔ꎬ웴솿뇂곒뇪곔풴⠱〩랢㜩뷢ꎬ닩캪쓇뻍뗄볊벴랢ꆢ곎뮰뿉쑢㖣죧탅ꎬ훐抣쾵듋늻웴쯉탅쯹ꨰퟓ짌폃ꆣ꼷죧맻쾢⦣몣춳놾뿉랢겵돚쾢튪쪱?벯쫽캪㔩맻뇪죧뛊겡뗄컄싗겣탐쪽쎵뫳ꆣ쟳ꎬꎮ뎤蝹⠼뛸톡쿂㰱궣뿉붫ꆣ탅뷒뗄뻍㖸뛈쓏볙筁抣퓱쯹뫉ꎬ걢폃룃ꆻ쾢뮸뻶훖횻붽뛌짨ꆣ몵쇋쟫뇭ꆣ컊꿃뿉닟샠떥ﲡ떫뿒쾵ꎬ쓏抣쟳쓖綣풴쳢얻틔죔뇤⦣뒿?ퟓ늽춳䆣뗍뫄뗄쪾뗎겼쫇럖귎솿겴뾼벯쾶훐멽돗쟃쿮ꪷ럱뮯쫌쫇펶싇쿮폐ꎬ쫔둢쒿풴훅쓜튻뺵?サ뇪쒿겶ㄵ듕ꎬ뚼햼ꊽ싺룶?뗄뛠㺣볓붫쫇?갵탂늻쾡폐퓏〩?싊?ꎬ뗄抣훘뫎뗄?튪뗚탔ꎬꆣ웴랢
112 运筹与管理2011年第20春 贪婪求解器贪婪算法是一种不追求最优解，只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有自I能阳必须槌攒的大量时间。常以当前情况为基础作最优选择，阳不考虑各种可能的整体情况，所以贪婪法不需要由溯。贪婪算法也是一类求解NP问跑的快速算法。贪赘算法在文中的应用分为两阶段的过程，首先对所有的郁的按照启发式倍息进行排序，然后进行贪婪选抨。算怯过程如因1所乐。贪赘算1点二的性能主要取决于排序阶段启发式信息的选择。由于通过松弛算法得到的启发倍息是唯一的，因此基于松弛启发信息的贪婪算法只需运行…次就能得到相应的最优解。但是在工提启发倍思(17)中，不间的参数选择舍得到不同的解，因此需要进行多次实验(对每个参数设定范围，在这个班围内以小步伐法代)才能得别较好的解。贪生去算$;:目标收援，，0;当前1解为空;排序阶段:计算每个标的启发式信息;将标的按照启发信息从高到低排列(线性松驰或者你的本身启发式信息);逃得阶段:将b，加入到当l自由解中;中在被当前解的可行性;如果不可行则将bj从当前解中移除;End for 输1Illt1t优解(当前解然)阁1贪婪求解器 帧群算法求解器 二元，蚁群模型蚁群算法是模仿蚁群觅食行为而提巾的…种模拟进化算法，该算法采用了分布式并行计算和正反馈机制。蚂虫且会在通过的路径上释放出一种称为信息素的分泌物，路径路长释放的信息素越少，而后来的蚂蚁以较大的概率选择信息素较多的路径，从而形成正反馈机制。虽然单只蚂蚁的选择能力有限，但是通过信息素的群体合作使得整个蚁群行为具有高度的智能[8J。针对多维背租问翩.min和tian[9]设汁了工元蚁群算法，并证明了该算法在背包问题中的优越性。由于本文的优化问题也是标的。甲1选择过程，和多维背包问题相似度较高，因此本文的蚁群求解器也基于二元蚁群算法。一个工元蚁群算法的潜在解如表1所示，其过程为:蚂蚁从标的l开始选择，当标的上的信息紫满足一定条件时，选择该标的井将其标志位设为1，否则不选该栋的其标志位为0，直到遍历完所有栋的。袭1蚂蚁的一个潜在解标的bh) bb, b. h._2 2 h._1 b地s Xj 二元蚁群算法中，每个标的b有两个句之相关联的信息素川和'剧表示该标的不被蚂蚁选择的概i率，T表示标的被瑞择的概率。选择与否采用轮盘赌的方式i1r~ Tρ(t) 10扩rand<即Xi=J- I ------TiQ(t) +Ti1(t) (18) L1 else rand是0-1之间的随机数发生器，式(18)保证X以较大的榄率选择T曲和'T中较大的一个。 解的修复当蚂蚁构造完解串之后，并不能保证所构造的解能满足可行性要求，因此需要对得到的解进衍可行性验证和修复。二咒蚁群算法解的修复分为两阶段:前向修复和后向增强[判。前向修复:首先计算每个栋的的启发倍息，然后按照启发倍息从高到低排列标的，按照该排列顺序检查蚂蚁构造解中标志位为1的掘的，如果该你的不满足可行性要求，则将其相应的栋志位设为0。后肉增强:按照启发信息从低到高排列췲랽쫽뻝ㄱ퓋돯폫맜샭㈰㊣첰틲늻삷퓱뗄훐늽춼틏믺탅캬㇋짨뇭뛾溣싊당楦牡ꆭ?㞡?ꆫ敬떱퇩㠩ꏇꆮ椽?㇌㇂獥ㄱ긳삷캪뾼쯣ꆣꎬ랥긴좺훆틔쾢놳流풪겶瑱湤심횤뗄?냀ㄩꮡ쓪첰쯣쯼싇램틲늻뗼틏ꎮꆣ뷏쯘냼뺣ㆣꅭ犡꺣쫇뫍웴죧䩯럇쾵湤겣뗚삷램쪡룷퓚듋춬듺좺ㆶ심듳뗄컊곆겷쓒뇭ꎱ깲ァ㊽릹탞랢맻뮸㈰쟳쫇좥훖컄맽뗄믹⦲쯣ﻔ틏좺ꎬ쳢쪾ꨱ퓬뢴탅룃?뻭뷢튻쇋뿉훐돌탔폚닎엄램쒣믡룅쳥늢쿠ﶳ룃뺱㲶횮쓐췪ꆣ쾢뇪뇔웷훖캪쓜뗄죧쯉쫽?쟳쿈럂퓚싊뫏횤쯆쳎믑?훐뇪볤?뷢뛾ꎬ?늻헒뗄펦춼훷돚톡쎵뷢뫄틏춨ퟷ쏷뛈ꪣꆸꎬ쒱뒮풪좻ꪼힷퟮ헻폃㇋튪웴퓱붽웷ꏐ좺맽쪹쇋뷏뫂쎱쎿늻믑쯦횮틏뫳싺쟳폅쳥럖流좡랢믡쾺?쏙뗄탅뗃룃룟룶놻ꇔ믺뫳좺내ퟣퟮ뷢쟩캪뺡뻶탅뗃쎵쪳슷쾢헻쯣ꎬ쾴쓆뇪심맕쫽헕뿉폅튪뿶솽?폚쾢떽쒽탐뺶쯘룶램틲펱뗄틏쒸랢늢웴뷢쟮ꎬ뷗업뗄늻캪짏뷏틏퓚듋抡톡엂짺랢탔ꭩꎬ뺡쯹뛎탲첰춬?뛸쫍뛠좺놳놾쐱뻎ꏓ퓱쪡웷쓜뗄탅튪횻쯹틔뗄뷗삷쳡럅탐냼컄뾪믎탁ꏑꎬ놣탞쾢쟳쾣폐첰맽뛎쯣뷢돶슷캪컊뗄쪼ꨰ붸룅ꇔ?쪽횤뢴듓ꎬ췻뿉삷돌웴램ꎬ뗄튻뺶뻟쳢틏톡⠱쯹럖룟퓲뗃쓜램ꎬ랢횻틲튻훖폐훐좺퓱횱㠩릹캪떽붫떽뛸늻쫗쪽탨듋훖돆듓룟뗄쟳ꎬ껏놣퓬솽뗍웤뷏뇘탨쿈탅퓋쒣캪뛸뛈폅뷢떱뇩짓횤뗄뷗업쿠캪탫튪뛔쾢탐쓢탅탎뗄풽웷뇪샺?쏂립뷢뛎쇐펦싺뫄믘쯹뗄튻뷸쾢돉훇탔튲췪ꪵ훅槒쓜ꎺ뇪틢럑쯝폐톡듎탐뮯쯘헽쓜ꆣ믹짏쯹쓐첶풽싺잰뗄뇪뷢뗄ꆣ퓱뻍뛠쯣랴ꆧ평폚폐엏쒵쾴ퟣ쿲ꎬ횾뗄듳첰뇪ꆣ쓜듎램럖삡ꆿ폚뛾탅ꋋ쒷뿉탞내캻랽솿삷뗄평뗃쪵ꎬ쏚믺ꆣ놾풪쾢?뷊쒸탐뢴헕짨램쪱쯣내폚떽퇩룃컯훆헫컄틏쯘ꆣꇞ?엂탔뫍캪ꆣ볤램헕춨쿠⢶쯣ꎬ뛔뗄좺싺뫍쫑튪뫳업ァ첰ꆣ튲웴맽펦퓃램슷쯤뛠폅쯣ퟣ?ꇔ쟳쿲쇐ꎺ삷뎣쫇랢쯉뗄뾸닉뺶좻캬뮯램튻ꎬ퓶쮳램틔튻쪽돚ퟮ폃풽떥놳컊ꆣ뚨ꇋ틲잿탲튻떱샠탅쯣폅컊쇋뎤횻냼쳢쳵뺺듋펡볬냣잰쟳쾢램뷢럖쫍심컊튲룶볾쵦탨ㆡ닩뾣뿉쟩뷢뷸뗃ꆣ늼럅틏쳢쫇뛾쪱튪ꏇ심몰틔뿶乐탐떽떫ꢷ쪽뗄ꎬ뇪풪훐뛔냏틏듕뿬캪컊업뗄쫇뛎늢탅톡浩틏뷏뗃릹헆쯙믹쳢탲웴퓚ꞣ탐쾢퓱溺ァ좺듳떽?퓬뗃뒡뗄ꎬ랢뛾곔볆쯘쓜쵴ꨱ쯣룃뒣뷢ꋐ떽ퟷ뿬좻탅샠?쯣풽솦楡톡램뇪튻뷢뫊훐엏싺ퟮ쯙뫳쾢웴뫍짙폐湛퓱뗄룶뷸ퟏ뇪ꊴ틢폅쯣뷸쫇랢헽ꎬ쿞㤱맽잱늢ꆣ탐좼횾펵뗄톡램탐캨탅뛎랴뛸ꎬ짨돌퓚붫뿉웋캻춵뷢퓱ꆣ첰튻쾢Ꞔ삡뫳떫볆ꎬ웤탐캪붸ꎬ첰삷⠱?살쫇쇋뫍죧뇪탔뾸ㆵ?뛸톡㜩퓐뗄춨뛾뛠뇭횾쒱엁?심맽풪캻
第2期陈李钢，等:组合拍卖在门户网站广斗争机会分配中的应用113 的顺序险查解申中标志位为O的标的，首先将其际志位设为1然后检查所有标志位为l的栋的集的可行性，如果不可行则将其标志位设为0。文献[判中，在解的修复过程中只采用一种启发借息，使算法容易陷入局部最优值。因此本文采用松弛启发信息和带资源占有率的单位价格进行解的修复(实脸表明这两种启发信息比其他启发信息寻优性更强)。即从所有的蚂蚁解中，随机用这两种启发信息进行解的修复，不问启发信息使得蚁群算法的搜索范隅更大，更密，易跳出周那假假点。修握过程如图2所示。僻的修复过程z对您个问蚁构边的解If rand :>0. 5 将b按照松弛启发信息从高到低排序iBτφ Fori=l:n(前前l修复)If("’i" 1) B"BUb rc( ilJ行位检查B不通过)B = B -b, 问=0End if End if End For For =n: 1 (后前增强)If("" = =0) m = 1 B=B υb， If(i1J行性检查B不通过)B黑B-b; "’, =0 End if End if EndFof WL'Mptu 带资源汀上口有率的品中L价格修复解修复过粉类,Ja且1 饨M图2蚂蚁构造解的修复过程 信息亲是新初始阶段让每个标的上的两个信息素Tρ胃口口随着珑代的进行，信息素的更新Jlii.朝着最优解的路程上优化。本文采用全局最优更新策略，即只更新当前世代上目标值最好的蚂蚁路径。(t+l) =(1-ρ)rj， +Q/Q何时扩Xj=l,s=lelses=O (19) 更新策略(19)表明在全局最优路径上，如果某栋的对庶的X为1则强化TjiI否则强化T曲，其中Q.表示:当前最优路径的目惊值，Q，/)，n/表示所有怖的标价之和。3 算例分析 则试散掘发生器由于没有可用的恻试数据，本文的测试数据将由数据发生器产生，过程如下:(1)首先确定广告机会的项目数及每个广告机会的可用单位数;(2)确定每个广告机会的单位价格;(3)确定标的的数璧;(4)确定标的的长度、子标的长度及每个子栋的大小的上限。标的长度是指标的具有的子栋的个数，子标的长度是指子标具有的广告矶会项目数，大小是指子标所需的广告机会单元数。例如标的1< lA 1A1,15 >.101r:þ榕的长度为1.子标的长度为2，大小为150具体的快度为从1到上限值之间的随机数，2大小也为1到上限值之间的随机数;췲랽쫽뻝뗚ㄱ뗄탔죫웴춬춼㊣돵㞣楦敬㔽⠱룼잰㏋㎣평⠲⠳⠴ퟓ䆣듳돂?㋂獥룪㋆쮳ꎬ뻖랢웴긴쪼슷깨㤩탂ퟮ긱폚⧊⧈뇪멽킡샮椽?탲죧늿탅랢ꎮ뷗뺶⡴닟폅닢쎻ퟏ랶뗄ꎬ튲쾹ﶷ룖ㆣ볬맻ퟮ쾢탅맔㏐뛎짏⬱싔슷쫔폐죈ꣃꢱ뎤ㄵ캪훎ꎬ걓닩늻폅뇈쾢엏죃⤽⠱뺶쫽뿉랶뾸뛈㺣沵㴱뗈?뷢뿉횵웤쪹ꋋ쎿뮯⠱㤩뗄뻝폃ꢹ쒵쫇갱뷉쓐ꎺ뒮탐ꆣ쯻뗃??룶튻뇭쒿랢뗄쓊쒳횸ぽ쿏ퟩ뒹훐퓲틲웴틏ﳐ뇪놾瀩쏷짺닢ﷁ꒶ퟓ?뫏ﶳ뇪붫듋랢좺뗄컄㞣퓚횵웷쫔請뾣좡뗖?엄횾웤놾탅쯣짏닉깨좫ꎬ쫽?ꋗ뻟뗄꺼싴캻뇪컄쾢램뗄폃⭑뻖冡뻝쓏쒵펱폐뎤퓚캪횾닉톰뗄솽좫ꆣퟮꎡꎬꗎ뛈쓋쏅サ캻폃폅쯑룶뻖ꎯꎣ놾뿊뮼쒳맣캪뮧쒱짨쯉탔쯷탅ퟮ冡슷겱컄ﶼ?꒶룦ㆣ響췸캪돚룼랶쾢폅ꎡ뺶뗄냃좼믺곗ﶣ햾쒣ァ웴잿캧쯘룼ꍦ짏뻋닢뾸?냃믡펱맣곊ꏎ랢⦡룼狌탂ꎬ陸쫔뾸쿮룦ퟏ쓏탅ꎼ듳닟죧킱쫽쒿쒳믺좽힡쾢뒴ꎬ犡싔맻뻝펱쫽꒶믡ꯆ귖뫍폋룼ꌽꎬ쒳쒱붫請죎럖킣듸陸죝ィ벴뇪평쒴듳ꨲ엤곔킵틗긵횻뗄?쫽쒿킡ꎬ훐뻎?풴쓂쳸ꆣ룼뛔꺺뻝짓ꆵ쫇듳뗄믉햼돶쯦탂펦춡랢쎵쓉횸킡펦쓐폐쾽뻖ퟅ떱뗄?짺ꗎ쿏ퟓ캪폃ꨱ?싊늿뗼잰립웷믊?뇪ㄵ좻뒹뗄킣벫듺쫀ꎻ닺ﶣꎱ쯹ꆣ뫳ﶳ떥곋횵뗄듺캪짺?탨뻟볬쳖캻뗣뷸짏㇔ꎬ쒳뗄쳥닩탖볛䀘ꆣ탐쒿맽꒶맣뗄쯹뮲룱쏕탞ꎬ뇪뾻돌죊룦뎤폐짓뷸뢴탅횵꽲죧쟖믺뛈뇪쏒탐뷖맽쾢ퟮ榡쿂뢱믡캪횾믖뷢훆돌쯘뫃ꎷꎺ떥듓캻훆뗄죧쒾풪ㆵ캪탞ꋐ춼룼심?쫽뷉沵ꋐ뢴엏㋋탂틏뾻킵ꆣ쿏쒱엏⣊ꊽ流펦슷꽲쓗샽?ꊣ뗑뺡뎯뺶ꎮ펱죧뗖쒼곊킽?ퟅꆣ뇪껎꾵맋ퟮꎬ쒸뗄쪵쒿쓐폅웤笼쓋짐?뷢훐ﶣ筁??뷖뒣冡ꆣ響ퟏ?겲ꎱꎬﶣ?뺵?
114 i在筹与管理2011年第20卷(5)为子标分配广告项阻。方法一:根据子栋的民度随机分配广告机会;方法二:首先随机选定一个广告机会，然后随机选择单位价格差与所选广告机合在一起范围内的其他广告机会。由于子栋中的广告项目效用无差异，因此方法工更适合本文的模型;(6)为4每个郁的设定标价:首先确定子郁的你价，用子标中的平均单咒价格乘以子栋的大小，由林中的项目具有替代她用，因此子标的最终价格为子标大小的减函数;加总每个子标的价格，由于子标之间具有互补的效用，回此价格为桶的长腥的增函数;最厨再将价格进行正态化处理。 剧发借恩实碰分析启发{育忠实验目的在于测试不同启发信息在贪赘算讼中的'性能α实验过程中的松弛启发信息、解柴可行性舱测及最优值求解郁采用大规模数学优化软件包Mosek进行计算。Mosek能快速求解大规模稀疏炬阵的优化问题，模型(1)的系数矩阵也是大规模稀疏矩阵，回此Mosek比较涌合本问阔的求解。实验中的启发信息最优解求解都采用贪赘求解器，不同的启发信息将导致贪赘求解器排序阶段标的排序的不同，从而影响最优解的结果。回此为了方便论述且不引起混乱的情况下，下文将省略贪婪求解器，即将松弛启发信息贪赘求解器简述为松弛启发信息，其他的肩发信息以此类推。实验分为两种规模:中等规模(70个广告机会、70个标的)及大规模(500个广告机会、ßOO个标的)0 中等规模实验可通过Mosek的要去数规划优化器求解得到模型的最优值，大规模实验Mosek无法在限定的时间内求解最优值(2个小时)。中等规模实验目的在于得到启发式贪婪算法与最优解的相差程度，而大规模实验在于测试启发信息寻优性能的区别。不同规模的实验都运行50?x井求其平均值。测试数据样本有两种:丰富资掘环境，即每个广告机会的可用单元数相对较多;稀缺资源，即每个广告机会的可用单元数相对较少。中等规模算例的结果如表2所示。袋2中等规模启发倍息实验ß-1f方t曾强组数据样本实验次数Mosek最优值松弛启发信息单位价将单位价将单位价格字商资源50 稀缺资源50 1801. 286 总统ìt100 2171. 345 从实验的结果上肴，没有哪个启发信息是最好的，但是增强型单位价格的号子优性相对较差。在丰富资掘的环境下，基于松弛启发倍息的贪婪算法效果最好，不仅均值比较接近最优值，而且在50次实验中，31次的目标函数值在四种启发信息中殷商。在稀缺资掘环境下，带资蹦出有率的单位价格启发倚息的部优性最好，不仅均值最接近最优值，而且在50次实段中37次胜出。这是由于其垮虑了得个栋的所谓求的资掘和系统资服总数的关系，将一些坚虽然价格比较商，但资源占有率高的标的排在后陋，从而能够在资掘限制的情况下选择更多的栋的。阳在正在商资服环境下，由于资惊限制作用的比重下降，则基于松弛启发信息的算法的部优性更好。有意思的是，大规模实捡下的锚果和中等规模不一样，如表3所示。大规模实验中，不管在哪种数据样本下，带资掘占有率的单位价格在四种启发信息、中性能最高。而在中等规模中丰富资师、数据样本下表现优鼻的松抽启发信息在大规模实验中性能却只排在第二三。原因在于大规模的数据环境下，解空间迅速膨胀，标的之间的冲资性更复杂更难检测，回此考虑了资源占有率团素的启发信息的寻优性比其他启发信息高。袭3大规模启发信息实验t曾强搜带资源占有数4能样2位实验次数松她启发信息p翻开1i单位价格单位价格率的单位价格辛苦苦资源50 稀缺资源50 100 二元踉群算法实验二元蚁群算法的测试-ill.分为中等规模和大规模实验，中等规模实验主要测试蚁群算法的等优性，其比较对象为Mosek最优值。从实脸的结果上辛苦，蚁群算法的等优性还是较好的。如表4所示。췲랽쫽뻝?퓋돯폫맜샭㈰⠵맣쿮⠶뇪볤㎣웴뿉뻘뗄듓랢쪵훐쪱맦놾쫽뇭풴㌱폅쿞쾢듳뛾뷏ㄴ훐?㎴ㄱ⧎룦쒿훐뻟긲랢탐헳웴뛸탅퇩뗈볤쒣폐쿠쪵뗄듎탔풴훆맦긳풪뛔쓪믺킧뗄폐웴탅탔랢펰쾢럖맦쓚쪵솽뛔퇩뮷ퟮ뫍쯣쒣뛾틏쿳쒣뗚펱믡폃뾸쿮뮥랢쾢볬폅탅쿬첰캪쒣쟳퇩훖뷏뗄뺳쒿뫃쾵쟩램쪵ꏆ풪좺웴㈰ꎬ컞쒿늹탅쪵닢뮯쾢ퟮ삷솽뷢퓚ꎺ짙뷡쿂뇪춳뿶뗄퇩훐쫽틏쯣䵯랢ꋐ탅뻭훅좻닮뻟뗄쾢퇩벰컊ퟮ폅쟳훖폚럡ꆣ맻ꎬ몯늻쿂톰훐뻝좺램獥엏쾢뫳틬쓉폐킧쪵쒿ퟮ쳢폅뷢맦뿉닢뢻훐짏믹쫽뷶풴톡ꎬ뮷톰ꋊ쯣뗄毗쪵뗑쯦ꎬ쳦폃퇩뗄폅뷢웷쒣춨횵쫔뗈뾴폚뻹ퟜ퓱탔늻뺳램닢?믺틲ꢱ듺ꎬ럖퓚횵쒣쟳뷡볲ꎺ맽⠲웴풴맦쯉쫽룼맜쿂탔쪵쫔엖톡듋킧틲컶폚쟳탍뷢맻쫶훐䵯룶랢뮷쒣쎻돚쯄ퟮ뗄뛠뫃퓚쫽ꎬ뇈퇩튲떡뾡퓱랽?폃듋닢뷢⠱뚼ꆣ캪뗈獥킡탅뺳쯣폐웴훖뷓맘뗄쓄뻝웤럖ꎴꎷ떥램뫊ꎬ볛쫔뚼⦵닉틲쯉맦段쪱쾢샽쓄랢웴뷼쾵뇪폐훖퇹뿕쯻캪폊붷캻뛾ퟏ틲룱늻닉쓏폃듋돚쒣쓕⦡톰벴뗄룶탅랢ퟮꎬ틢쫽놾볤웴훐뗑꣒볛룼죈듋캪춬폃뗊첰웴⠷ꏖ폅쎿뷡쾢탅붫ꆣ쮼뻝쿂톸랢뗈뮣룱쫊랶ퟓ뇪웴듳ﶾ삷쇋랢ジﶹ킵탔룶맻뗄쾢횵튻뛸퇹뇭쯙탅맦쒽몸닮뫏꣗뇪뗄랢맦?쟳랽탅좹쓜맣죧첰훐ꎬ킩퓚쫇놾쿖엲쾢쒣料폫놾펱뗄뎤탅쒣뷢뇣쾢껓룦뇭삷ퟮ뛸쯤럡ꎬ쿂폅헍룟뫍?쯹컄ퟮ뛈쾢쫽닊웷싛ꎬ얻ꏊ쟸믺㋋쫇쯣룟쟒좻뢻듳틬ꆣ쾿펱톡뗄쒱훕퓚톧잴ꎬ쫶웤請꿆뗑뇰믡流ퟮ램ꆣ볛맦듸뇪뒣맣쒣볛퓶첰폅늻쟒쯻ꆣ뗄뺡뫃킧퓚㔰룱풴쯉곒쒳룦탍?룱몯삷뮯춬늻뗄ꈷ뾵뿉?맻쾡듎뇈뮷쪵풴돚횮쿈꒶믺ꎻ곓캪쫽쯣죭ꏏ뗄틽웴ジ쓔춬폃ꎬퟮ좱쪵뷏뺳퇩햼볤뫋죋믡쏗ퟓꎻ램볾ꇊ웴웰랢쎵?맦떥떫뫃퇩룟쿂폐뗄ꎬ퓚펱뇪ퟮ훐냼랢믬탅뷄?쒣풪쫇ꎬ풴뗄싊돥ꢵ覆튻듳뫳뗄䵯?탅싒쾢쐩ꏐ쎵쫽퓶늻뮷㌷떫평뷡춻뗈쓑훅뚨킵킡퓙탔獥쾢뗄틔벰춵뷆쪵쿠잿뷶뺳듎폚맻떥퓚맦냓랶쓆뗄붫쓜殽곒쟩듋듳쓗퇩뛔탍뻹쿂쪤풴뫍캻룼쒣에캧붾복볛ꆣ떼뿶샠맦ꋊ뚼뷏떥횵ꎬ돶햼풴훐뢴쪵풻쓚例몯룱쪵킼쭍훂쿂췆쒣엖뷌퓋뛠캻뇈듸ꆣ폐쿞뗈퓓퇩맊請뗄ꗔ쫽뷸퇩웋潳첰ꎬꆣ⠵떣냀탐ꎻ볛뷏헢싊훆맦퓚쪵룼훷잽웤ꪼꎻ탐맽敫삷쿂〰겴럋㔰쾡룱뷓풴쫇룟ퟷ쒣쯄퇩쓑튪쾺뮷쯻?볓헽돌ꍍ뇈쟳컄룶듎좱뗄뷼햼평폃늻훖훐볬닢쎵붷맣ퟜ첬훐潳뷏뷢붫꣓늢톰ퟮ폐폚뇪뗄튻웴탔닢쫔쒡ꢶ룦쯒쎿뮯뗄敫쫊웷쪡ꏊ쟳풴폅싊웤뇈퇹랢쓜ꎬ틏ꏈﺣ믺퓗룶뒦쯉쓜뫏업싔뗑웤ꎬ탔횵뗄뾼훘탅좴틲좺뫊믡펱ퟓ샭돚뿬놾탲첰얽욽벴쿠ꎬ떥싇퓚쿂죧쾢횻듋쯣ퟏꆣ뇪웴쯙컊뷗삷ꆢ潳뻹쎿뛔뛸캻쇋뫳붵뇭훐업뾼램쯹죋평쒴뗄랢쟳쳢뛎㠰敫쓏횵룶뷏쟒볛쎿쏦ꎬ㏋탔퓚싇쪾폚볛탅뷢뗄뇪ジ컞ꆣ맣닮퓚룱룶ꎬ퓲流쓜뗚쇋톰𣏕ퟓꆣ룱쾢듳쟳뗄웷램닢룦㔰웴뇪듓믹뺡ퟮ죽폅ꆶ뇪곓ꎬꆢ맦뷢업퓚첶쫔믺듎랢뗄뛸폚?룟ꆣ풴탔꣒훐짓평뷢쒣ꆣ탲벴쐩쿞좣쫽믡럡쪵탅쯹쓜쯉풭햼ꎬ뮸뗄?폚벯쾡쪵붫ꆣ뚨겶뻝뢻퇩쾢쟫릻돚뛸틲폐웤?맣ퟓ쫨퇩늻쯉뗄퇹뿉훐쟳퓚웴싊뇈룦뇪훐춬돚?폃ꎬ톰뗄랢폚틲횮ꎬ웴떥폐풴탅쯘풪
第2期陈李钢，等:组合拍卖在门户网站广告机会分配中的应用115 袤4中等规模蚁群算法实验数据样本实验次数Mo""k J蓝优值二元蚁~'H军法丰富资源50 稀缺资源50 总统计100 2361. 37 结果表明二元蚁群算法在两种数据样本下的寻优性均很好，稀缺资源下的寻优性达到100%，丰富资源下的寻优性也在95%以上。二元蚁群算法的寻优性能还表现在找到最优解的平均迭代次数上，平均迭代18次就得到了最优解。大规模数据实验主要对比蚁群算法和采用不同启发式信息贪婪求解器的性能，贪婪求解器的寻优性依艘于启发式信息的好坏其搜索空间较小。二元蚁群算法能在问题的可行空间进行并行搜索，从而得到更好的解。每种测试数据各运行50次，结果如表5所示。表5大规模蚁群算法实验带资源占有分布实验次数松弛启发信息ß-开方单位价格t曾强型单位价格二元蚁群算法率的单位价格丰寓资源50 稀缺资源50 5891. 25 总统计 5530. 14 1∞ 结果表明二元蚁群算法的最优解比贪婪算法高出50%以上，而且在100次实验中，二元蚁群算法对贪婪算法的优越性为100%。丰富资源数据样本下的运行情况如图3所示。2α)()() 1以)()()X ..( À-)I、16C盼。,f .( 扎在;1( 14α)() ，ì~泸y可n号rxx t ~t 1筑削求:’ ;(荒r4X~ 松'也启发'『. 1似)()()川MVA V-a·UA •-erX<··xxaavM," -vx- .画· zx-•••Ax 开方单强位型价单格位价••-,•x,-翩翩J•-a’τ• h- J-›m --••..zzAvA•』『. 4饨R'VA• 1·守z•Az•v ..•••叫’ • -·圃'--•• •童a-.··a a• •a• 凰-’ • ' 矗• 守-R ..蝇n ···- . 童• A· • . • A 'a 明格s . .•• ›. • am• •• ·a 4创)()X 带资JJ;!占有率的单位价格及泊。3气二元蚊群3草法。o 10 20 30 40 50 图3各算法结果虽然二元蚁群算法的性能比贪婪算法高，但是其运行时间也长。当给定启发信息，一只蚂蚁解的构造和修复过程的运行时间相当于贪婪算法的整体运行时间，因此蚁群算法的运行时间要比贪婪算法多一个数量级。因此如果应用对时间即时性要求较高，那么只能通过牺牲性能换取时间采用贪婪算法。但是一般情况下，门户网站的广告机会分配对时间的即时性要求不是很高，通过牺牲时间换取更高的性能是可接受的。4 结论本文通过将组合拍卖机制引入到门户网站的广告机会分配问题中，并根据广告机会的特点设计了可以表示无差异及互补效用的投标方式，该方式能让广告主更加自由的表达其对广告机会的效用。在此基췲랽쫽뻝뗚?ㄵ뇭훐뷡풴듺듳틀룼첰춼쯤뫍쫽냣쫜㒽놾틔돂?㖴㎸뗈㋆맻쿂ㄸ맦삵뫃삷좻탞솿쟩뗄컄뇭샮맦?뇭뗄듎쒣폚쯣뛾뢴벶뿶ꆣ춨쪾룖쒣쏷톰뻍쫽웴뷢ꏒ램ꢽ풪맽ꆣ쿂컞ꎬ틏쿈뛾폅뗃뻝랢ꆣ뗄틏돌틲ꎬ붫닮좺뗈뫋?풪탔떽쪵쪽쎿폅좺뗄듋쏅ퟩ틬쯣ꎺ틏튲쇋퇩탅훖풽쯣퓋죧뮧뫏벰램ퟩ뗑쪵좺퓚ퟮ훷쾢닢탔램탐맻췸엄뮥뫏?퇩쯣㤵폅튪뗄쫔캪쪱펦햾싴늹엄램ꎥ뷢뛔뫃쫽탔볤폃뗄믺킧싴퓚틔ꆣ뇈뮵뻝뗄ィ쓜쿠뛔맣훆폃퓚솽짏틏웤룷ퟮꖡ뇈떱쪱룦틽뗄쏅훖ꆣ좺쯑퓋폅ꎷ첰폚볤믺죫춶뮧쫽뛾쯣쯷탐뷢삷첰벴믡떽뇪췸뻝풪램뿕㔰뇈믗쯣삷쪱럖昭랽햾퇹틏뫍볤듎첰쫔램쯣탔엤䥐쪽맣놾좺닉뷏ꎬ삷듊룟램튪뛔췸룦쿂쯣폃킡뷡ﶾꎬ뗄쟳쪱햾룃믺뗄램늻ꆣ맻?떫헻뷏볤랽믡톰뗄춬뛾죧룟鈴쫇쳥맣쪽럖폅톰웴풪뇭돶뻏웤퓋ꎬ벴룦쓜엤탔폅랢틏㗋㔰습퓋탐쓇쪱믺죃훐뻹탔쪽좺流ꎥ쓔탐쪱쎴믡맣뗄뫜쓜탅쯣뺡틔쯐쪱볤횻튪럖룦펦뫃뮹쾢램?짏탇볤ꎬ쓜쟳엤훷폃ꎬ뇭첰쓜튲틲춨늻컊룼쾡쿖삷퓚뛸뎤듋맽쫇쳢볓좱퓚쟳컊쟒ꆣ틏컾뫜훐ퟔ헒뷢쳢퓚밳떱좺짼룟ꎬ평풴떽웷뗄쯹룸쯣탔ꎬ늢쿂ퟮ뗄뿉ゴ쪾뚨램쓜춨룹뇭뗄폅탔탐컊ꆣ웴뮻맽뻝듯톰뷢쓜뿕뗑랢퓋좡컾맣웤폅뗄ꎬ볤탅탐쪱짼룦뛔탔욽첰뷸킣쾢쪱볤믺맣듯뻹삷탐겶ꎬ볤닉믡룦떽뗼쟳늢ﻔ튻튪폃뮻뗄믺듺뷢탐횻뇈첰좡쳘믡ィ듎웷쯑쿈심첰삷룼뗣뗄ꖣ쫽뗄쯷뫋틏삷쯣룟짨킧겷짏톰ꎬ뷢쯣램뗄볆폃ꎬ폅듓ꢶ뗄램ꆣ탔쇋믗욽탔뛸?릹뛠떫쓜뿉퓚?뻹뗃퓬튻쫇듋뗼떽룶튻뿉믹뷓
116 运寿与管理2011年第20春础上，建立了相应的优化模型，并证明了该优化问题是NP难问题。针对该问题的求解，本文在文献{叫上设计了四种启发式信息及两种求解器:二咒蚁群求解器及基于启发信息的贪婪求解器。在实验阶段，本文设计了相应的数据发生器，并用这些数据测出了四种启发式信息及两类束解器。实验结果表明:(l)在中等规模数据及稀缺资源环境下，带资'游、占有率的单位价格倍息的呼优性能比其他三三类启发信息高资源环境下，松弛启发信息则比其他启发式倍息优越。在大规模数据环境下，带资翻占有率的单位价格的等优性能在两种敢指样本下都比其他启发筒息优越(2)二元蚁群算法能以较快的速度等找到最优解，中等规模数据环境下的哥优性达到95%0崔大规模数据环境下，二冗蚁群算法的呼优性比贪婪算桂优越50%以上，但是其远行时间也比贪赘算法多一个数最级。参考文献:[1] Fujishima Y, Leyton-Brown K, Shoham Y. Taming the computational complexity of combinatorial auctions: optimal and ap翩proximate approaches [ C]. Proceedings of the sixteenth International Joint Conference on Artificial Intelligence. San Francis›co, USA: Morgan Kaufmann Publishers, 1999. 548 -553. [ 2] De V S, Vohra R V. Combinatorial auctions: a survey [J]. Informs’ Joumal on Computing, 2003, 15 (3) : 284-309. [3] Bartal Y, Gonen R, Nisan N. Incentive compatible multi un˛t combinatorial auctions [ C]. Proceedings of the 9th conference on theoretical aspects of rationality and knowledge. New York, USA: ACM Press, 2003. 72响87.[4] Gonen R, Lehmann D. Optimal solutions for multi-unit combir皿orialauctions: branch and bound heuristics [ C ]. Proceedings of the 9th conference on 2nd ACM conference on e1ectronic commerce. New York, USA: ACM Press, 2000. 13-20. [5] Feige U, Immorlica N, M rrokni V. A combinatorial allocation mechanism with penalties fjοr banner advertising[ C]. Proceed-ing of the 17th inlernational conference on World Wide Web. Beijing,China: ACM Press, 2008. 169唰178.[6J陈堵友，汪定伟.多物品直受优组合供应模式确定问题的模型研究[JJ.中国管理科学，2006，14(4);35-39. [7]黄河，徐鸿雁，陈剑.多因素采购组合拍卖获胜者确定问题研究[1].系统工程理论与实践，2008，28(07);27-33. (叫段海滨.蚁群优化原理及其应用[MJ.北京:科学出版社，2005.[ 9 J Kong M, Tian P. Kao Y. A new ant colony optimization algorithm for the multidimensional knapsack problem [J]. Computers and Operalions民esearch，2008, 35 (8) ; 2672-2683. [10J Sandholm T, Sur 5, Gilpin A. CABOB; a fast optimal algorithm for winner determination in combinatorial auctions[JJ. Management Science, 2005, 51 (3) ; 374-390. 췲랽쫽뻝ㄱ퓋돯폫맜샭㈰㇄뒡짨뗈톰㔰닎嬱䙵妣䮣捯潦慵慮慰灲瑨䩯潮䅲䥮䙲䭡偵䑥?獵䍯䉡劣亣浵慳牡奯偲䝯桥㉮敬䙥嚣慬浥慤楮坯돂믆뛎䭯䶣湥潰歮剥卡咣晡䵡卣ㄨㆣㅊㅪ犣牌慮妣獩䍯䍏厣?畮捯㥴歮劣䒣獯扯䅃喣睩潦瑨傣景佰慬坩坥ꆪ灥?걌걓瑨浰浢捴潸䥮楮瑩瑥慮畦扬嚣牴걇걎깉汴捯敯牫敳湥景散浭楧걍깁汯捨ㄷ湦湧걔杯慰湤䆣獴湡楥?橩灲牬뫓獥㌩そ牶畲癥엠몣潢깔捯硴湦ꎬ걖楴浢潷걌깏汵浵畮걉瑨湡扡걋깁敲걇杯睩짏볆맦풴폅ꎥ뾼楯捴摥抣敹桯?汥楮楯業瑥晩汬捩浡楳깃慬潮湣慴湦牥ꎬ玣瑲敲楲捡慮瑨楡湹浩物獡畲来獨潡湳畴楯?ꎬ慲ꎺ慭浰敥敲啓潨楮汥敨灴瑩汴浭湮慯慴楬物瑥?敹楳牴폑뇵瑯桡硩慴湳牮捩楧玡湮桥潭敮慮楢敲瑩慬啓갲潮捥牯깂?穡瑨捫汭䅂浥斣ꎬ쇋쒣뮷탔틔컄ꎺ楮畴湴敮䆣牡慴摧浡潮榡潤楥敲楤楯灩瑨牭?業捨湳탬㌷溡?瑹潲ꎺ慴慬敮牳扩瑩汥捡楴䆣〰楣ꎮ歮潮捥佂湴갲ゾ孊楳敲ꎬ浛慴捥멍潲斣湮慬ꩵ楣業湳楮붨쯄쿠쫽뺳쓜짏쿗?敳枣季뫨㒡ꩂ楡潰楯捥ꎬ湡癥멁㎣扲乥ィ㢣潮ꎺ〰楯潲楡깎湩敮慴?嶣捳楮췴틏䩝孊牯?瑩孃湡ꎮㄹ瑯갲嶣䍍긷慮긱퇣㈰㖣ꨳ솢훖펦뻝쿂퓚ꎬꎺ湡条?敷獩楯枣睮浡?卡㤹物깉㊡捨孃㌭杛㘹뚨좺ꎮ긵嶣〰깐ꎬ〸㤰?潮걃쇋웴뗄벰ꎬ솽뮷떫?ꎮ慬ꐸ㈰ꆪ깐湦㎣牯嶣䍝캰돂폅䍯ꎬꎮ慬㔴㞣ꎮ桩ㄷ쿠랢쫽쾡쯉훖뺳쫇牯갱捥붣㌵潲깐ꎮ뮯浰㢡?㢣湡먱뭲捥㔨敤ꎮ⠸ꨵ?펦쪽뻝좱돚쫽쿂웤浳牯偲뛠풭畴ꎺ敤㔳㌩楮뛠⦣❊捥潣䅃컯샭敲뗄탅랢웴뻝퓋ꎮ楮ꎺ杳틲먲?潵敤敥욷벰폅쾢짺풴랢퇹톰탐杳㈸쯘㘷牮楮搭ퟮ웤㒡닉㈭뮯벰웷뮷탅놾폅쪱慬ꨳ杳폅릺펦㈶쒣솽ꎬ뺳쾢쿂탔볤〹㠳ퟩ폃탍훖늢쿂퓲뚼듯튲ꎮ뫏뫏孍엄ꎬ쟳폃뇈떽?릩嶣싴늢뷢헢듸웤㤵첰펦꺱믱쒣놾횤웷킩쯻ꎥ삷쪤쪽헟ꦣ쏷ꎺ쫽풴웴ꆣ쯣좷몿쇋뛾뻝햼랢퓚램뚨뚨웑룃풪닢폐쪽탅듳뛠컊컊Ꭓ쳢폅틏쫔싊탅쾢맦튻쳢퇐뮯좺쇋뗄쾢폅쒣룶뺿컊쟳쯄떥폅풽쫽쒣孊嶣탍갲쳢뷢훖캻풽⠲뻝솿껏퇐〰쫇웷웴볛ꆣ⦶뮷벶뗍뺿㖣乐벰랢룱퓚ﻔ뺳ꆣ뎹孊?꒳쓑믹쪽탅듳쿂嶣쳀컊폚탅쾢맦쿈ꎬ껖쳢웴쾢뗄쒣뫋뛾?킹ꆣ랢벰톰쫽풪調떼?헫탅솽폅뻝꣄틏念뛔쾢샠탔뮷?좺갲웑〰룃뗄쟳쓜뺳풽쯣ꞣ㢣컊첰뷢뇈쿂쾿램갲쳢삷웷웤ꎬ뗄㠨〰〷뗄쟳ꆣ쯻듸쓋톰㚣⦣쟳뷢쪵죽?폅갱먲㐨뷢웷퇩샠풴죑탔㜭㐩㌳ꎬꆣ뷡웴햼냕뇈ꎮꎺ놾퓚맻랢폐튵첰㌵컄쪵뇭탅싊뷗삷ꆪ퓚퇩쏷쾢뗄쯣㌹컄뷗ꎺ룟떥얽램ꎮ쿗뛎⠱ꎬ캻폅ꆧꎬ⧔뛸볛곖풽뷐놾?럡룱?짏컄?뢻뗄
