第15卷第1期运筹与管理Vol.15,No.12006年2月OPERATIONSRESEARCHANDMANAGEMENTSCIENCEFeb.2006多人合作费用分摊的多目标规划解法熊国强(西安理工大学工商管理学院,陕西西安710048)摘要:考虑核心是空集的情况,针对核心法的适用范围和局限性,建立了一种多人合作费用分摊的多目标规划模型,给出了求解费用分摊方案的两阶段算法。最后通过一个实例说明了该方法的可行性。关键词:数学规划;多人合作对策;费用分摊;核心中图分类号:O2216文章标识码:A文章编号:10073221(2006)01001305SolutionofMultiobjectiveProgrammingforCostAllocationofnpersonCooperationXIONGGuoqiang(SchoolofManagement,XianUniversityofTechnology,Xian710048,China)Abstract:Consideringacoreisanemptyset,inviewoftheapplicationscopeofthecoreanditslimit,thispaperdevelopsonemultiobjectiveprogrammingmodelforthecostallocationproblemofnpersoncooperationgame,andthenpresentstwophaseapproachforsolvingthecostallocationproblem.Finallythefeasibilityofthismethodisillustratedbyanexample.Keywords:mathematicalprogramming;npersoncooperationgame;costallocation;core0引言费用分摊是经济管理工作中经常遇到的一类问题,如企业重组过程中的投资费用分摊问题、城市基础设施建设项目中的公共费用分摊问题和环境管理中的污染物治理费用分摊问题等。实践表明,合作能使参与者获得比他们单独行动更大的收益或者降低成本,所以,一个投资项目往往有多个部门或单位合作参加投资建设,如何确定公平合理的费用分摊方案,使合作者之间形成稳定的合作联盟,是费用分摊问题的主要研究内容。费用分摊问题可以转化为一个多人合作对策问题来解决[1,2],常用的方法有Shapley值法、最大最小费用法MCRS(MinimumCostremainingSaving)法、核心法(Core)、二次规划法GQP(GameQuadraticProgramming)法等[3,4],核心法按照给联盟S分摊费用C(S)所加额外量形式的不同,又分为最小核心法,弱最小核心法和比例最小核心法。这些方法都是基于不同的公平性或计算的简单性等原则来考虑,既有各自的优点,又都不同程度地存在着不足[5]。本文针对核心法的局限性,提出一种新的求解模型,即给联盟费用C(S)以不同额外增加量,建立一种多目标规划模型,并结合多目标规划的有效解法,给出求解费用分摊方案的两阶段算法。收稿日期:20050531基金项目:国家自然科学基金资助项目(70272063)作者简介:熊国强(1961)男,陕西西安人,副教授,研究方向:管理系统工程。14运筹与管理2006年第15卷1费用分摊的多人合作对策模型对于一个费用分摊问题,可以建立一个相应的多人合作对策模型=(N,C)。其中参与活动的各部门或单位称为局中人,全体局中人的集合记作N={1,2,,n};N的非空子集S称为联盟,即一部分局中人联合成一体像一个!局中人∀一样选择策略,N为总体联盟。C(S)称为特征函数,表示当若干局中人联合成一个联盟S进行活动时所应分摊的费用;C(N)表示全体局中人形成大联盟时的总费用,费用分摊问题的实质就是如何在各局中人之间合理分摊总费用C(N)。各局中人之间的一个分摊方案用x=(x1,x2,,xn)表示,xi为第i个局中人应分摊的费用。核心是Gillies[6]于1953年提出的一个合作对策的解概念,它是不被任何分摊方案优超的分摊方案的集合,或者说,核心中的每个分摊方案都能够被任何联盟所接受。按照这一基本思想,一个合理的分摊方案x=(x1,x2,,xn)应满足以下两个条件:xiC(S)!S∀N集体合理性i#∃Sxi=C(N)总体合理性(1)i#∃Nxi#0x=(x1,x2,,xn)的全体就