局内管理决策问题及其竞争策略

①马卫民1,2,王刊良1(11西安交通大学管理学院,西安710049;21香港理工大学计算科学系,香港)摘要:基于优化领域的热点研究方向之一的局内问题与竞争策略理论,将相关概念引入管理决策,提出了局内管理决策及其竞争策略的概念,说明了处理局内管理决策问题的竞争策略和传统方法的区别以及后者的缺陷.
构建了利用局内问题及其竞争策略研究局内管理决策问题的理论框架,并介绍了一个具体研究实例.
关键词:局内管理决策;竞争策略;竞争比中图分类号:TB114.
1文献标识码:A文章编号:1007-9807(2003)02-0029-060引言局内问题和竞争策略的研究始于Sleator和Tarjan[1]的工作,20年来,研究成果层出不穷,已经成为一个非常值得注意的新研究方向.
1985年,Sleator和Tarjan[1]发表"AmortizedEfficiencyofListUpdateandPagingRules"一文,以计算机列表的更新和存储管理为应用背景,但解决问题的思路和方法完全可以用于企业的仓储管理.
Borodin,Linial和Saks[2]1987年提出度量任务系统(metri2caltasksystem)模型,基于局内问题及竞争策略理论,讨论了局内作业管理决策及资源管理决策问题(但未提出局内管理决策概念).
El-Yaniv和Karp[3]讨论了局内设备更新问题,使局内优化理论讨论的问题更接近于实际管理决策问题.
1997年,徐寅峰等[12]基于k-服务器问题提出并较好地利用竞争策略解决了局内k-出租车问题.
文献[11]第一次明确提出了局内管理决策问题的实例,将局内优化理论和局内售后服务交通费用管理问题结合起来.
更多的相关文献见文献[4~10,12~22].
但是,局内问题及其竞争策略的应用潜力还远没有被挖掘出来.
一个重要的原因就在于,迄今为止,如何把局内问题及其竞争理论和经典的管理决策模型很好地结合,还缺乏系统的研究工作.
在局内问题及其竞争策略的理论研究方面,国外已取得了很大的成就,国内的工作却开展的很少[11~16].
要改变国内管理学基础理论的研究现状,必须引进和掌握先进的研究工具.
本文论述了传统管理决策学涉及不确定性问题时的缺陷,提出了局内管理决策行为和局内管理决策学的概念,建立了利用局内问题及其竞争策略解决管理决策问题的理论框架,并给出了一个简单的案例,同时,本文也介绍一种先进的研究工具.
1传统管理决策学的缺陷运动是物质的固有属性.
现实生活中的许多管理现象乃至社会现象,通常都具有非常强的动态特征1人们在面对现实生活中的具体问题时,常忽略或无法把这些动态因素考虑进去.
以管理决策问题为例,人们一般先对其进行数学上的抽象,然后用静态或统计的方法来研究或处理,求出最优策略.
所以,经典的管理决策优化理论总是首先确定已知条件,然后给出最优方案(即最优策略).
但是,条件如果发生变化,这种方法给出的最第6卷第2期2003年4月管理科学学报JOURNALOFMANAGEMENTSCIENCESINCHINAVol.
6No.
2Apr.
,2003①收稿日期:2001-11-13;修订日期:2002-07-05.
基金项目:国家自然科学基金委员会优秀创新群体资助项目(70121001).
作者简介:马卫民(1971—),男,博士生1优方案就会失去其最优性.
在涉及不确定性时,传统管理决策学通常使用两种经典的策略.
一是将可变化的因素随机化,寻求平均意义上的最优方案;二是考虑可变化因素的最坏情形,寻求使最坏情形达到最优的方案———最坏情形分析.
寻求平均意义上的最优方案,是在遇到对所研究问题影响很大的不确定性因素时,利用历史的或统计的资料、决策者的经验知识等,给出这种不确定性因素的某种概率分布,在这种概率分布下研究该管理决策问题,这实际上是一种概率建模方法.
这种方法已在传统管理决策学以及博奕论中得到了广泛的应用.
所谓"最坏情形"是指,不可预测的因素对于决策者的某种决策,总是使问题呈现某种特殊情形,这种情形总是使管理决策问题的求解背离决策者期望的方向,使其目标难于实现.
"最坏情形分析"指的是,面对不可预测因素,决策者总是寻求最坏情形下的最优决策,即"做最坏的打算".
对于第一种经典策略,虽然利用概率模型研究管理决策问题取得了成功,但在如何选取不确定性因素的概率分布,为什么选取此种概率分布而不是其他概率分布的问题上,一直存在着争议.
事实上,对于复杂的管理决策问题,确定其不确定性影响因素的概率分布是非常困难的,有时其难度不亚于解决该管理决策问题本身.
而且,即使通过这种概率建模方法得到了问题的概率意义上的解,但当问题的最坏情形发生时(即使这种最坏情形是小概率事件),这种概率上的解就失去了意义.
对于第二种经典策略,考虑不确定性管理决策问题可变化因素的最坏情形,寻求使最坏情形达到最优的方案———最坏情形分析有可能给出决策者一种"无为"的无奈选择.
换言之,如果决策者总是考虑"最坏情形",最终的结果有可能是"不能做出任何可行的决策".
总之,对于管理决策问题中的可变化因素,两种传统的处理方法都可能给出离实际最优解相距甚远的解.
是否存在一种方法,在变化因素的每一个特例中都能给出一个方案,使这一方案所得到的解离最优方案给出的解总在一定比例之内,近年来兴起的局内问题与竞争策略的研究结果在一定意义上给如上问题一个肯定的答案[1~22].
2基本概念局内问题(on-lineproblem),亦译为联机问题或占线问题,提出于20世纪80年代初期[1].
局内问题相对于局外问题(off-lineproblem)而言1人们都有这样的体验:对某一段时间的工作或生活回顾与总结时,总会情不自禁地想,要是当初如何…….
此时面对的就是一个局内与局外的问题.
回顾与总结时,置身局外,可以看到事物的全部,易于得出对你而言的最佳方案.
但经历这些事件时,通常只能看到事物的一部分,很难作出最优决策.
所谓:"当事者迷,旁观者清","不识庐山真面目,只缘身在此山中".
事实上,大多数管理决策问题都具有局内性,决策者不可能完全置身于局外,不可能事先知道所有的信息,所作出的决策只能基于部分信息,使管理决策具有某种局内性.
局内管理决策问题是指决策者置身于某一管理决策问题的发展过程中,只知道某种对决策目标有致命影响的不确定因素的局部信息,而需对全局进行优化的管理决策问题.
局内管理决策行为是决策者处理上述局内管理决策问题时的行为.
以在管理决策问题中是否存在不确定因素(通常其对决策目标应有致命影响)作为分类的标准,把管理决策问题分为局内管理决策问题和局外管理决策问题.
传统决策理论把决策问题按所处的条件分为3种:确定型决策,风险型决策和不确定型决策.
本文按是否存在不确定性因素把管理决策问题分为局内管理决策问题和局外管理决策问题.
传统决策理论以解决确定型决策问题为主,以概率模型解决风险型决策问题,但对不确定型决策问题则无能为力.
本文以解决涉及不确定型和风险型决策问题为主要研究方向.
显然,局内管理决策问题包含了传统决策理论中的风险型决策和不确定型决策,局外管理决策问题对应的是传统决策理论中的确定型决策问题.
概率建模及最坏情形分析是传统管理决策学处理局内管理决策问题的典型方法1局内管理决策论则致力于用竞争策略的方法处理局内管理决策问题.
局内管理决策问题的竞争策略,指的是局内决策者在处理局内管理决策问题(包含不可预—03—管理科学学报2003年4月测的变化因素)时,选择一种策略,此种策略可以在变化因素的每一个特例都能给出一个方案,使这一方案所得到的解离最优方案(对应局外决策问题的最优解)给出的解总在一定的比例之内.
此处的"比例",称为该种策略的竞争比.
Karp在文献[21]中提出并研究了滑雪橇租购问题(TheSkiProblem).
这是一个典型的局内管理决策问题.
一个滑雪初学者,他不知道他对这种业余运动会感兴趣多长时间,换言之,他不知道他会滑多少次雪.
因此,他每次去滑雪时都会面临两种选择,每次花1个单位的钱租借滑雪撬,还是用B个单位的钱一次性购买滑雪撬.
假设他最多滑T次雪,那么存在两种情形.
第一种情形,若T已知,则此决策问题为局外决策问题.
问题的求解较为容易,若T>B则选择买,否则选择租;但是,在现实生活中,T往往是不能事先知道的,这时怎样决策呢此为第二种情形.
文献[21]给出了一种竞争策略,它可以保证其费用不超过相应的最优费用的(2-1/B)倍.
Baeza-Yates,Culberson和Rawlins[22]提出并研究了斯坦福教授失车问题(TheStanfordProfessor'sLostCarProblem).
一位斯坦福的教授把汽车停在巨大的椭圆形的花坛一侧,而他要做的是如何能走较短的路程找回他的汽车,如图1所示.
图1斯坦福教授失车问题1)事先知道汽车停在椭圆的哪一侧,如何决策使所走路程最短2)事先不知道汽车停在椭圆的哪一侧,如何决策使所走路程最短问题1)是局外问题,问题2)是局内问题.
两者的不同点在于决策者是否知道汽车停在椭圆的哪一侧.
问题1)的最优策略并不难找,已经知道了汽车停在椭圆的哪一侧,只要选择该侧为找车方向,直至找到汽车,所走的路程是问题的最优解,问题2)则有些棘手,因为汽车停于椭圆的哪一侧对于决策方案有着致命的影响.
在这种不确定性因素存在的情形下,寻求问题的相对较优的解,是对局内问题进行研究的原因所在.
可以用最坏情形分析法和建立概率分布的方法来处理.
例如,可以对以往教授停车于哪一侧进行概率统计,进而对此次停车于哪一侧进行估计,然后选择最有可能停车的一侧为选择的对象,解决此问题.
但是,当选择了左侧而汽车停于右侧(尽管此种情形的概率可能很小)———即最坏情形发生———则可能得到一个离最优解很远的解(若椭圆趋于无穷大,解也趋于无穷大).
文献[22]给出了一种竞争比为9的竞争策略,即无论何种情况,按照其竞争策略进行决策所得到的解不会超过其最优解的9倍.
局内计算机内存管理决策问题及其竞争策略[1],亦称换页问题(PagingProblems),与管理学中的仓储问题非常相似,更接近于实际的局内管理问题.
两级存储系统中有两种存储器:一为高速缓冲存储器(auxiliarystorage),存储容量很小但存储速度很快;另一为主存储器(mainstorage),存储容量很大但存储速度很慢.
每一级存储器都可以存储一定数量的数据块(或者指令块、指令数据块).
存储在高速缓冲存储器的所有数据块总是存储在主存储器中的数据块的一个子集.
假设前者的容量为k,后者的容量为n,显然有k≤n.
问题的输入为一系列数据块的调用.
当要调用一个数据块时,总是首先在高速缓冲存储器中查找该数据块,如果找到则其调用费用为0;如果要查找的数据块不在高速缓冲存储器中———换页错误(pagingfault)发生,则先把此数据块从主存储器中调入高速缓冲存储器,同时从后者中剔出另外一个数据块,此时的调用费用为1.
换页问题就是决定当页误发生时,把哪一个数据块剔出高速缓冲存储器,目的是使总调用费用最小(或页误发生的次数最少).
事先知道调用序列则可以很简单地确定剔出数据块的原则(局外问题).
当不知要调用的是哪些—13—第2期马卫民等:局内管理决策问题及其竞争策略数据块,而且需要立即作出剔出数据块的决策时,最坏情形分析法将处于一种"无为"的境地:每一次决策的最坏情形,是下一次调用的数据块正好是前一次从高速缓冲存储器剔出的数据块,这显然无助于任何决策.
文献[1]给出利用竞争策略解决此问题的一些结果,更多的结果见文献[17~19].
综上所述,竞争策略实际上是一种解决局内问题的较好的策略,与以往解决此类问题的策略的最大区别在于:它能够始终把局内问题的策略限制在一个距相应局外问题的最优策略的常数倍范围之内,并给出此常数,使某一局内问题的解始终保持在一个较优的状态.
3研究框架局内管理决策问题的研究一般遵循以下思路:首先要善于发现现实生活中的局内管理决策问题,然后对其进行必要的数学抽象,建立该局内管理决策问题的模型,并依据局内问题的解决方案提出并选择恰当的竞争策略,最后给出该竞争策略的理论证明.
通常,给出局内竞争策略及其理论证明是整个研究过程最难的两个步骤.
对于两类局内管理决策问题,给出一般情形下的求解模型(图2).
图2局内管理决策问题的求解模型对于成本优化的局内管理决策问题P,以costA(I)记策略A对于问题P的某一实例I的实现成本.
则问题P的策略A的竞争比c定义为inf{c|costA(I)≤c·costB(I),ΠI∈P,ΠB}对于利润优化的局内管理决策问题P,以benefitA(I)记策略A对于问题P的某一实例I的实现利润.
则问题P的策略A的竞争比c定义为sup{c|c·benefitA(I)≤benefitB(I),ΠI∈P,ΠB}上述竞争比的概念是一种严格竞争(strictlycompetitive)策略的结果.
一般情形下的竞争比定义,通常需要在定义中的不等式右侧加上一个常数1此常数不影响竞争比的求解.
4局内管理决策问题实例4.
1问题的提出某工厂在全国有十几个流动售后服务小分队,对全国几十个城市的用户使用的该厂生产的某大型设备进行售后服务(维修).
多年来,一直根据"就近原则"进行调度,每当接到一个服务需求时总是调度离该需求最近的维修小分队去满足该服务请求.
随着用户数量的增加,发现售后服务人员的交通费用的年度结算总数占了该厂管理费用相当大的一部分.
为了降低该项费用,厂销售部组织技术人员对此项费用进行统计与分析,根据全年实际售后服务的顺序排成的序列,在所有用户所在城市组成的铁路网上,利用运筹学动态规划的方法求出全年售后服务人员交通费用的最优值(最小值)及全年的最佳调度方案.
分析结果表明:1)在年度结算中,售后服务人员交通费用的实际值远大于该项费用的最优值,即就近原则确定的调度方案是极不合理的;2)想使调度方案保持最佳状态几乎是不可能的,因为随着新的服务需求的到来,此刻以前所确定的最佳方案的每一步都有可能改变,因此,只好还采用就近原则.
如何减少这笔开支,是管理者多年来一直头疼的问题.
售后服务人员的调度问题是一个局内问题,因为存在不可预测的因素:服务需求,而且这种不可预测的因素对调度方案有着致命的影响.
而传统的对此因素的处理方法(例如就近原则)显然是不能令人满意的.
4.
2数学模型设G是一个有n个顶点的图,其意义为该厂分布于全国的用户所在城市构成的铁路交通网络.
它具有正权距离且距离之间符合三角不等式.
有k个维修小分队外驻于k个有用户的城市中.
给出一个需求序列σ=(ɑ1,ɑ2,…,ɑm),其中每一项都代表一个有服务需求的顶点(城市).
k-售后服务问题就是决定如何调动服务人员,去满足每一项服务需求,而且能求得相对较优的解,使交通费用较少.
服务小分队的原始位置已经确定,如—23—管理科学学报2003年4月果某个提出服务需求的顶点上没有服务小分队,则必须派遣某个去满足该服务请求.
而且满足服务请求序列时,必须按照该序列中的需求顺序进行服务.
这样,满足服务需求序列的总的交通费用就正比于所有服务小分队所走的总路程.
该问题显然是一类对称的k-售服问题,即对任意顶点,从i点到j点的距离与从j点到i点的距离相等(即对所有的u和v都有duv=dvu).
k-售服问题是一个局内问题,换言之,就是在决定派遣服务小分队时对以后的服务需求一无所知.
以CA(σ)来表示局外算法A在满足服务需求序列σ时发生的费用.
如果算法B是局内的,且存在常数α,使得对任意A和α都有CB(σ)≤c·CA(σ)+α则称算法B为局内k-售服问题的c-竞争算法.
如果某一算法对常数c而言是竞争的,则称该算法为c竞争的.
如果常数c较小,就称该竞争算法是高效的.
常数c称为竞争比.
当某个算法的竞争比达到尽可能小时,称该算法为强竞争的.
可以看出,局内k-售服问题是k-服务器问题在管理决策领域的一个具体应用.
4.
3竞争策略———新的调度原则一般情况,k-售服问题的竞争策略比较复杂,现给出一种竞争比为2k-1的竞争策略[20].
依据建立的数学模型,定义:状态———为图G的一个k元子集,用大写字母表示,顶点用小写字母表示.
用"A+ɑ"表示"A∪{ɑ}",用"A-ɑ"表示"A-{ɑ}",用ab表示顶点a与b间的最短距离.
工作函数———wt(X)表示满足t时刻的服务需求序列且处于状态X的累计最优费用,这种以一系列状态和正实数定义的函数wt称作时间t的工作函数.
显然,如果w为当前的工作函数,那么完成一个新的服务需求r(其意义为顶点r发出维修服务请求)后的工作函数为w′(X)=minx∈X{w(X-x+r)+rx}根据以上的论述可得出一种新的竞争策略,即工作函数竞争算法如下:以w表示当前的工作函数,且局内算法开始于状态A.
假定顶点r为新的维修服务需求顶点,以w′表示完成该服务请求后的工作函数.
若顶点a(ɑ∈V)可使式w′(A′)+rɑ最小,则调度顶点a处的维修小分队去顶点r处进行维修服务,式中A′=A-ɑ+r.
文献[11]给出该局内管理决策问题的另外两种特殊情形下的竞争策略,这两种策略使该局内问题获得了最优的竞争比.
5结束语作为将局内问题及其竞争策略分析引入管理学领域的尝试,本文提出了局内管理决策及其竞争策略的一系列概念.
这些基本概念可用来界定局内管理决策问题和局外管理决策问题.
本文同时论述了竞争策略在处理局内管理决策问题时和传统方法的区别以及传统方法的缺陷.
揭示了进行局内管理决策问题及其竞争策略研究的必要性.
在构建相应的理论研究框架之后,还介绍了一个具体研究实例———局内售后服务交通费用管理决策问题.
参考文献:[1]SleatorDD,TarjanRE.
Amortizedefficiencyoflistupdateandpagingrules[J].
CommunicationsoftheACM,1985,28:202—208[2]BorodinA,LinialN,SaksM.
Anoptimalonlinealgorithmformetricaltasksystems[J].
JournaloftheACM,1992,39(4):745—763[3]El-Yaniv,KarpRM.
Nearlyoptimalreplacementpolicies[J].
MathematicsofOperationsResearch,1997,22(3):814—839[4]CoverTM,Universalportfolios[J].
MathematicalFinance,1991,1(1):1—29[5]El-Yaniv,FiatRA,KarpR,etal.
Optimalsearchandone-waytradingalgorithms[J].
Algorithmica,2001,30:101—139[6]CoverT,JulianD.
Performanceofuniversalportfoliosinthestockmarket[A].
InProceedingsofIEEEInternationalSymposiumonInformationTheory[C].
Sorrento,Italy:2000.
232—33—第2期马卫民等:局内管理决策问题及其竞争策略[7]CoverT,OrdentlichE.
Universalportfolioswithsideinformation[J].
IEEETransactionsonInformationTheory,March1996,42(2):348—363[8]HelmboldD,SchapireR,SingerY,etal.
On-lineportfolioselectionusingmultiplicativeupdates[J].
MathematicalFinance,1998,8(4):325—347[9]MaWeimin,JaneY,XuYinfeng,etal.
Ontheon-linenumberofsnacksproblem[J].
JournalofGlobalOptimization,2002,24(4):449—462[10]MaWeimin,XuYinfeng,WangKanliang.
k-Truckproblemanditscompetitivealgorithms[J].
JournalofGlobalOptimization,2001,21(1):15—25[11]马卫民,刘新梅.
售后服务交通费用管理的竞争策略[J].
华中科技大学学报,2001,29:105—107[12]徐寅峰,王刊良.
局内出租车问题与竞争算法[J].
西安交通大学学报,1997,(1):56—61[13]马卫民,徐青川.
局外出租车问题的动态规划求法[J].
系统工程学报,2001,16(16):481—485[14]马卫民,徐寅峰,王刊良.
局内卡车问题及其竞争策略[J].
西北大学学报(自然科学版),1999,29(4):254—258[15]马卫民,徐青川.
局内k-军车问题及其竞争策略研究[J].
系统工程学报,2002,17(5):395—400[16]堵丁柱.
k车服务问题与竞争算法[J].
数学的实践与认识,1991,(4):36—40[17]AwerbuchB,BartalY,FiatA.
Distributedpagingforgeneralnetworks[J].
JournalofAlgorithms,1998,28(1):67—104[18]AlbersS,KogaH.
Newon-linealgorithmsforthepagereplicationproblem[J].
JournalofAlgorithms,1998,27:75—96[19]AlbersS,KogaH.
Pagemigrationwithlimitedlocalmemorycapacity[A].
InAklS,DehneF,SackJR.
etal.
eds.
Proc4thInternationalWorkshoponAlgorithmsandDataStructures(WADS95)[C].
Kingston,Ont,Canada:SpringerLNCS955,1995.
147—158[20]KoutsoupiasE,PapadimitriouC.
Onthek-serverconjecture[J].
JournalofACM,1995,42(5):971—983[21]KarpRM.
On-lineAlgorithmsVersusOff-lineAlgorithms:HowMuchisitWorthtoKnowtheFuture[R].
InternationalCom2puterScienceInstituteTechnicalReportTR-92-044,Berkeley,CA:1992[22]Baeza-YatesRA,ClubersonJC,RawlinsGJE.
Searchingintheplane[J].
InformationandComputation,1993,106(2):234—252On-linemanagementdecisionproblemanditscompetitivestrategiesMAWei-min1,2,WANGKan-liang11.
ManagementSchool,Xi'anJiaotongUniversity,Xi'an710049,China;2.
ThePolytechnicUniversityofHongKong,HongKong,ChinaAbstract:Basedonthetheoryofon-lineproblemandcompetitivestrategy,whichisahotresearchdirectioninthedomainofoptimization,byintroducingtherelatedconceptsintothemanagementfield,weproposeaseriesofcon2ceptsfortheon-linemanagementtheory.
Wealsoillustratethedifferencebetweenthecompetitivestrategyandsometraditionalmethodswhentheyfacetheon-linemanagementproblems.
Furthermore,weproposeaframeworkoftheresearchforon-linemanagementdecisionproblemsbycompetitivestrategy.
Finally,wegiveapracticalexampleofon-linemanagementprobleminordertocombinesomerelevanttheorywiththem.
Keywords:on-linemanagementdecision;competitivestrategy;competitiveratio—43—管理科学学报2003