在线多租赁选择问题的最优竞争策略  

Competitive Analysis for the Online Rental Problem with Multiple Options

作　　者：张桂清[1] 徐寅峰[1,2] 王扬[1] 

机构地区：[1]西安交通大学管理学院,陕西西安710049 [2]西安交通大学机械制造系统工程国家重点实验室,陕西西安710049

出　　处：《运筹与管理》2012年第1期11-18,共8页Operations Research and Management Science

基　　金：国家自然科学基金项目(71071123);国家自然科学基金重点项目(60736027)

摘　　要：在线算法与竞争分析是研究信息不确定决策问题的一种新工具,应用该方法研究在线租赁问题是近年来国内外的一个研究热点。传统的在线租赁问题以经典的"雪橇租赁模型"为基础,考虑在线决策者可以选择购买或按单位时间租赁的方式来使用设备。然而现实租赁市场(比如汽车租赁,房屋租赁)往往提供多种租赁方式供在线决策者选择,除了按单位时间进行租赁,通常可以以一个较优惠的价格租赁多个单位时间。在这种现实背景下,本文建立了多种租赁形式下的在线租赁模型,给出了这种租赁模型下的确定性竞争策略,并证明该策略具有最优竞争比。The online algorithm and competitive analysis provides a powerful tool to deal with uncertain decision making problems.Applying this tool,many researchers study rental problems in details.These studies are on the basis of Karp ＇s ski-rental model,and the player only has two choices： lease or buy.And the algorithm needs to decide when to switch from renting to buying.However,in realistic rental markets（e.g.vehicle rental market,house rental market）,the player often has multiple rental options.In this paper,we construct a rental model with multiple options,and present an online deterministic algorithm for this problem with a matching lower bound.

关 键 词：决策分析 竞争策略 在线算法 租赁问题 

分 类 号：F272.3[经济管理—企业管理]