占线租赁问题

占线租赁问题（共3篇）

占线租赁问题 篇1

摘要：考虑到设备的使用寿命通常呈现出更一般的非线性衰减, 本文以非线性指数价格函数为回购合同约束建立了占线租赁决策模型, 并得到了模型的最优竞争策略。首先分别对指数非线性回购合同进行数学刻画并讨论了其相关的一些性质。其次对存在旧货市场的离线租赁问题进行最优分析, 进而提出该问题的占线租赁策略, 并运用竞争分析方法从理论上完美证明了该策略的最优性。与经典的占线租赁模型比较发现, 其竞争比小于Karp“雪橇租赁”模型中最优策略的竞争比。另外, 本文提出的具有回购合同约束的占线租赁模型是对已有研究仅考虑新货市场进行扩展突破, 即考虑了允许旧货市场的存在, 是对现有占线租赁模型库的一个有益补充。

关键词：占线租赁问题,竞争策略,合同,竞争比,占线算法

1 引言

某生产厂家需要某种设备进行生产, 假设采用租赁的方式进行生产, 单位时间内的租赁价格为c;若采用购买的方式进行生产, 购买价格为p, 而且一旦买下了设备就不必再付费租赁。现实中通常无法准确知道使用时间n, 此时需要决策应该怎么组织生产——是租用还是购买设备, 这就是经典的占线“租雪橇”模型。1992年, “图灵奖”得主Karp[1]给出了该问题的最优解决方案, 即当在p/c-1期前的各阶段租用设备, p/c阶段后若仍需要则购买该设备, 并严格证明了这一策略是该占线问题的最优策略。随后许多学者基于这一经典模型展开研究[2,3,4,5,6,7,8,9,10,11], 但这一经典模型的最优解决方案是在假定一旦承租人购买了设备并完成了生产任务, 那么自己拥有的设备就再无剩余价值的前提下给出的。

事实上, 随着租赁业的快速发展, 现实中租赁业务开展都是伴随着承租人与租赁公司签订的某种合同下进行的。作为占线租赁问题, 如果承租人在某一时刻从租赁公司买下了设备并在另一时刻完成了生产任务, 那么此时对承租人来讲, 生产期间所买设备已是无用之物, 当然希望自己手上拥有的闲置的旧设备还可以折价出售换取一定的资金, 从而降低此次投资的生产成本, 提高投资回报。对于租赁公司而言也希望以最便宜的价格购进一部分运转良好或者稍加维修后仍可较长时间使用的二手设备以供再次出租赚取可观的租金, 从而降低公司的运作成本, 提高利润。因此对于占线租赁问题, 租赁公司也愿意从自己的客户手中以相对便宜的价格购回自己了解性能的设备。这样, 承租人与租赁公司最容易签订一份互惠互利的回购合同—如果承租人购买了设备并经一段时间后完成了生产任务, 租赁公司就根据承租人使用设备时间的长短以一定的价格回购该设备。我们把这种承租人与租赁公司签订了回购合同的占线租赁问题叫具有回购合同约束的占线租赁问题。

实事上, 设备回购价格随着使用时间的推移跟设备的损耗或寿命有关, 关于设备的各种寿命分布已有大量的研究[12,13,14,15,16], 如胡必锦[12]文中讨论基于寿命分布类的特性, 研究不同于现有文献的另一类残余寿命熵的特性, 并在一定的条件下得到残余寿命熵的上界。同时, 作为一种应用, 讨论一类依赖于参数的指数型寿命模型的残余寿命熵等。蔡南莲[13]得出了随机时间剩余寿命性质, 并以指数分布进行了详细的探讨。黎子良和郑祖康[14]在其编著《生存分析》一书中对各种寿命分布及其相关性质进行了详细讨论。关于“图灵奖”得主Karp提出的占线租赁问题, 实质上就是寻求最佳停止时间, 即占线人一直采取租赁策略直到某一时刻突然购买使决策活动结束的一类问题。从经典的优化方法来讲, 这是一个典型的最优停止问题, 近半个世纪以来有大量相关的研究成果[15], 也有学者以相关分布为假定给出了相应的最优停止判断法则, 如魏立力和张文修[16]研究了线性指数危险率模型的贝叶斯停止判决问题等等。因此, 从已有的相关文献和资料可知, 设备折旧除了线性损耗或折旧外, 非线性损耗更为常见更贴近现实问题, 正如许多学者以指数函数为例进行了大量的讨论。但运用占线算法与竞争分析理论研究占线租赁决策问题时, 关于设备回购函数为非线性时, 目前尚未有相关文献展开讨论。

本文试图运用占线算法理论研究非线性回购合同约束的占线租赁问题。首先对设备的指数回购函数进行数学刻画并讨论相关的一些性质, 其次讨论存在回购合同约束下的最优离线策略, 进而提出具有回购合同约束的占线租赁策略, 并证明该策略是最优竞争策略, 通过竞争分析得到该策略的竞争比, 并与典型的Karp占线租赁模型进行比较分析, 最后, 给出数值分析验证结论的正确性。

2 指数回购函数

将考虑回购价格函数是指数函数的非线性回购合同结束的占线租赁问题:设某用户或投资者要租赁 (租用或购买) 某种设备在时间t∈[1, n]内进行生产。如果租用设备在每一个租用期的租金是c, 如果购买设备, 购买价格是p;一旦投资者在某一期买下了该设备就不必再支付租赁费用并且当使用结束时还可以将设备以价格p′ (t) 回卖给租赁公司, p′ (t) 是指数函数或对数函数的非线性函数, t是承租人自购买设备后到使用结束时的使用时间。但投资者不知道自己将要使用这种设备多长时间, 即使用期数n是不确定的。此时回购价格完全由价值随时间的损耗决定, 设回购价格函数为

$p^{\prime }(t)=\frac{p}{(1+\eta ){}^t}$

其中, t≥0是承租人购买设备后的使用时间;η是大于零的常数, 我们称其为折旧因子。

显然, p′ (0) =p, 这表明当承租人购买设备但没有使用还可以以原价格退货;而当t>0时p′ (t) <p且p′ (t) 随使用时间的增加而严格单调降, 并有$\underset{t\to \infty }{{\displaystyle \lim }}{p}^{\prime }(t)=0$。这表明承租人购买了设备一旦使用一段时间后回购价格必然小于初始购买价格, 而且使用时间越长回购价格越低以至于使用充分长的时间后回购价格接近于零。

对于上述定义的指数回购函数约束的占线租赁问题, 若承租人每一期都采用租用设备的方式进行生产, 假定共需要n期设备, 则所花费用为V1 (n) =cn是n的严格递增函数且无界。

若采用一开始就购买设备的方式进行生产, 则所花费用为$V{}_2(n)=p-\frac{p}{(1+\eta ){}^n}$虽然也是n的严格递增函数但以p为上界。

一般地, 承租人与租赁公司签订的合约必然使得V1 (1) <V2 (1) , 即ηp> (1+η) c;否则, 一开始承租人就购买设备。函数V1 (n) 和V2 (n) 随使用期数n的变化态势如图1所示。

虽然合同约定V1 (1) <V2 (1) , 但由于V1 (n) 无上界, 而V2 (n) 以p为上界, 因此二者的图像必在某一点n*处相交 (如图1所示) , 即n*是关于n方程$cn=p-\frac{p}{(1+\eta ){}^n}$的根, 即$cn{}^{*}=p-\frac{p}{(1+\eta ){}^{n{}^{*}}}$.为了计算与表达方便, 设$\frac{p}{c}=s$ (以后经常用s表示$\frac{p}{c}$, 不再声明) , 则$n{}^{*}=s-\frac{s}{(1+\eta ){}^{n{}^{*}}}$.显然n*<s.另外, 由于n*是关于n方程$cn=p-\frac{p}{(1+\eta ){}^n}$的根。因此, 关于回购函数$p^{\prime }(t)=\frac{p}{(1+\eta ){}^t}$, 还有下面的结论:

结论1 当n<n*时, $cn<p-\frac{p}{(1+\eta ){}^n}$, 即$n<s-\frac{s}{(1+\eta ){}^n}$, 特别地, 1+η<ηs.

结论2 当n>n*时, $cn>p-\frac{p}{(1+\eta ){}^n}$, 即$n>s-\frac{s}{(1+\eta ){}^n}.$

不失一般性, 我们约定, s≥3是正整数且n*≥2。于是由$2\le s-\frac{s}{(1+\eta ){}^2}\le s(1-\frac{1}{(1+\eta ){}^{n{}^{*}}})$, 有$(1+\eta ){}^2\ge \frac{s}{s-2}$, 进而有$\eta \ge \sqrt{\frac{s}{s-2}}-1$。

3 离线问题的最优解

对于回购价格函数是指数函数的占线租赁问题, 其所对应的离线问题是租赁时间n是已知的。由上一节末的分析可知最优离线决策必然是根据n与n*的大小关系分以下两种情况之一作出的: (1) 当n<n*时, 总是租用; (2) 当n≥n*时, 租用t次然后买入, 其中0≤t≤n-1。

(1) 当n<n*时, 投资者在使用设备的n期内都采用租用设备最为划算, 每一期花费的租金是c, 于是在这种情况下, 投资者花费的租用金总额是V1 (n) =cn.

(2) 当n≥n*时, 投资者在使用设备的n期内前t期都采用租用设备而在t+1期再购买设备时, 投资者在前t期花费的租用金总额是ct, 在t+1期付出的购买金是p, 而在第n期结束后完成了生产任务, 投资者共使用购买的设备n-t期, 按照回购合同约定, 租赁公司以价格$\frac{p}{(1+\eta ){}^{n-t}}$从投资者手中回购了设备, 因此, 在这种情况下投资者花费的资金总额是$V{}_3(n)=U(t)=c(t+s-\frac{s}{(1+\eta ){}^{n-t}})$其中t∈[0, n-1]。

下面讨论V3 (n) =U (t) 中当t取何值时可以取得最小值。首先把函数V3 (n) =U (t) 的定义域延拓到t∈[0, n], 对U (t) 关于t求一阶导数, 并令U′ (t) =0解得稳定点$t{}^{*}=n-\frac{\ln (\ln (1+\eta ){}^s)}{\ln (1+\eta )}$.再对U (t) 关于t求二阶导数, 有U″ (t) <0。因此函数U (t) 为凹函数, U (t*) 为最大值, t*为其最大值点, 而且当t∈[0, t*]时, 函数U (t) 为单调递增函数, 当t∈[t*, n]时, 函数U (t) 为单调递减函数。

①若t*≥n-1, 则U (0) 是函数U (t) 当t∈[0, n-1]的最小值;

②若t*<n-1, 有$U(n-1)-U(0)=c[n-1+s-\frac{s}{1+\eta }-(s-\frac{s}{(1+\eta ){}^n})]$。

当t*<n-1时, 能够证明U (n-1) >U (0) 。由于当t∈[0, t*]时, 函数U (t) 为单调递增函数, 所以当t∈ (0, t*]时, 有U (t) >U (0) ;而当t∈[t*, n]时, 函数U (t) 为单调递减函数, 所以当t∈[t*, n-1) 时, 有U (t) >U (n-1) 。故, 当t*<n-1且t∈ (0, n-1]时, 有U (t) >U (0) 。

综合①和②两种情况可知, 无论t*≥n-1还是t*<n-1, U (0) 都是函数U (t) 当t∈[0, n-1]的最小值。

U (0) 是函数U (t) 当t∈[0, n-1]的最小值表明:当n≥n*时, 投资者决不会租用设备一段时间后再购买设备, 而是一开始就购买设备而且所花的最小费用为$V{}_3(n)=U(0)=c(s-\frac{s}{(1+\eta ){}^n})$。

综合 (1) 和 (2) 两种情况可知, 当使用期数n已知时, 最优离线策略是:当n<n*时, 投资者在使用设备的n期内都采用租用设备而且花费的租用金总额是V1 (n) =cn;当n≥n*时, 投资者从第一期开始就购买该设备并使用到n期结束, 再把该设备按回购合同事前约定的回购价格卖回给租赁公司。这样, 投资者花费的资金总额是$V{}_3(n)=U(0)=c(s-\frac{s}{(1+\eta ){}^n})$。

通过上面的分析, 如果用COPT (n) 表示最优离线策略的花费, 可得到定理1。

定理1 对于回购价格函数为指数函数p′ (t) , 每期租用金为c, 购买价格为p的离线租赁问题, 其最优离线费用为

$C{}_{{\rm O}{\rm P}{\rm T}}(n)=\{\begin{array}{cc}cn,& n<n{}^{*}\\ cs(1-\frac{1}{(1+\eta ){}^n}),& n\ge n{}^{*}\end{array}$

其中, $\eta \in [\sqrt{\frac{s}{s-2}}-1,\infty ),s\ge 3$为整数且n*≥2。

4 占线策略及其竞争比分析

占线策略S*:对于回购价格函数为指数函数p′ (t) , 每期租用金为c, 购买价格为p的占线租赁问题, 占线人在前n*-1期的每一期都租用设备, 到了第n*期买下设备。

定理2 对于回购价格函数为指数函数p′ (t) , 每期租用金为c, 购买价格为p的占线租赁问题, 占线策略S*的竞争比是$R=2-\frac{1}{s}-\frac{1}{(1+\eta ){}^{n{}^{*}}}.$

证明 由于当使用设备的时间n<n*时, 最优离线策略与占线策略S*都是从第一期开始每期都租用设备直到第n期结束, 因此二者的费用都等于cn.这样一来, 问题的最坏情况发生于n≥n*的输入时间序列。

而当使用设备的时间n≥n*时, 最优离线策略从第一期开始就以价格p购买设备使用到第n期结束后并把设备按照合同约定以价格$p^{\prime }(t)=\frac{p}{(1+\eta ){}^n}$回卖给租赁公司, 这样最优离线策略所花费用为$C{}_{{\rm O}{\rm P}{\rm T}}(n)=p-\frac{p}{(1+\eta ){}^n}$.而占线策略S*是在前n*-1期每期都租用设备, 而到了第n*期开始就以价格p购买设备使用到第n期结束后并把设备按照合同约定以价格$p^{\prime }(t)=\frac{p}{(1+\eta ){}^{n-n{}^{*}+1}}$回卖给租赁公司, 这样占线策略S*所花费用为$C{}_{n{}^{*}}(n)=c(n{}^{*}-1)+p-\frac{p}{(1+\eta ){}^{n-n{}^{*}+1}}$.于是, 利用p=cs, 可得

$R(n)=\frac{C{}_{n{}^{*}}(n)}{C{}_{{\rm O}{\rm P}{\rm T}}(n)}=\frac{n{}^{*}-1+s[1-(1+\eta ){}^{-n-n{}^{*}-1}]}{s[1-(1+\eta ){}^{-n}]}$

因此, 占线策略S*的竞争比是函数R (n) 的最大值, 其中n≥n*.

对R (n) 关于n求一阶导数, 可以证明R′ (n) >0, 故R (n) 在[n*, ∞) 是严格单调增函数。由于$n{}^{*}=s-\frac{s}{(1+\eta ){}^{n{}^{*}}}$, 从而有$\underset{n\to \infty }{{\displaystyle \lim }}R(n)=2-\frac{1}{s}-\frac{1}{(1+\eta ){}^{n{}^{*}}}$.因此对任何输入序列n, 占线策略S*满足$R(n)\le 2-\frac{1}{s}-\frac{1}{(1+\eta ){}^{n{}^{*}}}$, 但又存在充分大的输入n使得R (n) 与$2-\frac{1}{s}-\frac{1}{(1+\eta ){}^{n{}^{*}}}$无限接近, 以琢于$\underset{n\to \infty }{{\displaystyle \lim }}R(n)=2-\frac{1}{s}-\frac{1}{(1+\eta ){}^{n{}^{*}}}$.所以占线策略S*的竞争比为$R=2-\frac{1}{s}-\frac{1}{(1+\eta ){}^{n{}^{*}}}$.定理2证毕。

定理3 对于回购价格函数为指数函数p′ (t) , 每期租用金为c, 购买价格为p的占线租赁问题, 占线策略S*的竞争比是最优的。

证明 用类似于文献[17]的方法证明这一定理, 即运用反证法。假设策略S*的竞争比R不是最优的, 那么必存在一个不同于策略S*的策略具有比R更小的竞争比。设S**是任意一个不同于策略S*的策略, 则策略S**不是在租用n*-1期后在n*购买设备, 于是策略要么一直租用设备;要么一开始就购买设备;要么租用t-1期后在t期购买设备但u≠n*.

(1) 若对于任意使用时间n, 策略S**每一期总是采取租用设备。

令n=2s, 由于2s>n*, 则策略S′所花费用为cn, 最优离线策略所花费用为$p-\frac{p}{(1+\eta ){}^n}$, 因此$R^{\prime }{}_{S{}^{**}}(n)=\frac{n}{s-\frac{s}{(1+\eta ){}^n}}>\frac{2s}{s}=2>2-\frac{1}{s}-\frac{1}{(1+\eta ){}^{n{}^{*}}}.$

(2) 若对于任意使用时间n, 策略S**总是一开始就购买设备。

令n=1, 由于1<n*, 则策略S**所花费用为$p-\frac{p}{1+\eta }$, 最优离线策略所花费用为c, 因此

$R^{\prime }{}_{S{}^{**}}(n)=\frac{s-\frac{s}{1+\rho }}{1}=\frac{\eta s}{1+\eta }$

对于购买价格远远大于租用价格的情形, $\frac{\eta s}{1+\eta }$可以任意大, 即$R^{\prime }{}_{S{}^{**}}(n)>2-\frac{1}{s}-\frac{1}{(1+\eta ){}^{n{}^{*}}}.$

(3) 若对于任意使用时间n, 策略S′租用设备t-1期后在第t期购买设备但t≠n*.

①当2≤t≤n*-1时

令n=t, 由于t<n*, 则策略S**所花费用为$c(t-1)+p-\frac{p}{1+\rho }$, 最优离线策略所花费用为ct, 因此

$R^{\prime }{}_{S{}^{**}}(n)=R^{\prime }{}_{S{}^{**}}(t)=1+\frac{s-1-\frac{s}{1+\eta }}{t}$

对R′S** (t) 关于t求一阶导数, 能够得到$\frac{d}{dt}(R^{\prime }{}_{S{}^{**}}(t))<0$, 从而在t∈[2, n*]上R′S** (t) 是严格单调减函数, 即只有租用设备到n*-1期后在第n*期购买设备才可能是最优策略, 因此策略S**租用设备t-1期后在第t期购买设备, 当2≤t≤n*-1时不是最优策略。

②当t>n*时

对于n远远大于t的使用时间, 则策略S**所花费用为$c(t-1)+p-\frac{p}{(1+\eta ){}^{n-t+1}}$, 最优离线策略所花费用为$p-\frac{p}{(1+\eta ){}^n}‚$因此$R{}_{S{}^{**}}(n)=\frac{t-1+s-\frac{s}{(1+\eta ){}^{n-t+1}}}{s-\frac{s}{(1+\eta ){}^n}}.$

令n→∞, 则有$\underset{n\to \infty }{{\displaystyle \lim }}R{}_{S{}^{**}}(n)=1-\frac{1}{s}+\frac{t}{s}$.由于t>n*, 所以

$1-\frac{1}{s}+\frac{t}{s}>1-\frac{1}{s}+\frac{n{}^{*}}{s}=2-\frac{1}{s}-\frac{1}{(1+\eta ){}^{n{}^{*}}}$

即存在充分大的使用时间n, 使得RS** (n) >R.

综合以上 (1) 、 (2) 、 (3) 三种情况可知, 任意一个不同于S*的占线策略S**具有比策略S*的竞争比R更大的竞争比, 这与必存在一个不同于策略S*的策略具有比R更小的竞争比矛盾, 因此占线策略S*的竞争比是最优的。定理3证毕。

推论1 对于回购价格函数为指数函数p′ (t) , 每期租用金为c, 购买价格为p的占线租赁问题, 占线策略S*是最优占线策略, 它的竞争比小于Karp模型的最优占线策略的竞争比, 即$R<2-\frac{1}{s}$, 而且该问题的最优竞争比是η的严格单调增函数, 并有$\underset{\eta \to \infty }{{\displaystyle \lim }}R=2-\frac{1}{s}.$

由定理3和推论1可以看出:我们构建的非线性指数回购合同约束的占线租赁决策模型具有较高的应用价值和实现意义, 因为不但给出了该问题的占线租赁策略, 而且运用竞争分析方法从理论上完美的证明了该策略的最优性。并与经典的占线租赁模型比较发现, 其竞争比小于Karp“雪橇租赁”模型中最优策略的竞争比。同时, 本文具有回购合同约束的占线租赁模型是对已有经典“租雪橇”模型研究中仅考虑新货市场的一个有效扩展, 即考虑了允许二手旧货市场的存在, 由以往假定设备寿命无限长向实现租赁市场中设备寿命有限长更接近了一步, 是对现有占线租赁模型库的一个有益补充。

5 数值分析

根据前面的在线算法对存在二手旧货市场的租赁问题进行模型构建及理论分析, 本节将对模型中参数分别取不同数值进行算例分析, 进一步说明租赁市场中折旧因子的引入对于投资者的决策有着重要的影响。对于本文讨论的非线性回购合同约束的占线租赁问题, 主要决策参数为:购买价格p, 租赁费用c, 折旧因子η.根据租赁问题的实际情况, 表1给出模型参数的若干可能取值, 假设每期租赁费用c为1, 购买价格p分别为20、30和40, 折旧因子η分别为0.08、0.16和0.24, 并计算得到本文模型的最优竞争策略和对应的最优竞争比 (表1最后两列) , 其中第三、四列为Karp雪橇租赁模型[1]对应的最优竞争策略与该策略下的最优竞争比。

从表1可以看出:当购买价格p不变时, 随着折旧因子η的增大, 最优在线策略的竞争比持续增大, 最佳决策日期也随着推迟。当折旧因子η不变时, 随着价格p的增大, 最佳决策日期相应推迟, 且最优竞争比持续增大。但无论折旧因子η取何值, 对于给定的一定价格p, 本文非线性回购合同约束的占线租赁问题的竞争比都小于Karp模型的最优占线策略的竞争比, 且最佳决策日期也比Karp模型对应的决策日期有所提前。进一步发现, 在相同价格下, 随着折旧因子η的不断增大, 本文模型的最优竞争比和最优决策日都逐渐趋近于Karp模型的最优竞争比和决策日。在租赁市场中引入折旧因子对于投资者的设备租赁决策有着显著的影响, 这与推论1的结论分析恰好吻合。

6 小结

本文在Karp[1]及El-Yaniv等学者[2]模型基础上, 从仅考虑新货市场引入设备旧货市场, 探讨分析了回购合同中价格函数为非线性函数的两种典型函数, 即指数函数和对数函数。首先对这两类非线性回购合同进行数学刻画并讨论了其相关的一些性质, 其次对存在旧货市场的离线租赁进行最优分析, 进而提出该问题的占线租赁策略, 运用竞争分析方法从理论上完美的证明了其最优性, 最后结合数值分析, 发现存在折旧因子因素时, 最优决策日期相应提前, 并且改善了最优竞争比。与经典的占线租赁模型比较发现, 本文理论结果的应用价值主要在于:一是突破了已有占线租赁研究仅考虑新货市场, 二是设备价格回购的价格函数更一般化。分析技巧难度上也远远复杂于已有占线租赁模型研究, 如Karp及El-Yaniv等学者模型由于未考虑设备回购函数, 在分析模型的最优性时简单易行。本文回购函数的引入使得旧货市场的存在, 在模型讨论过程中无论是分析离线解还是占线策略最优性时, 均要对多个变量分不同情形进行分析, 并借助相关函数及不等式的性质进行讨论, 使分析问题的处理技巧和难度大大增加。幸运的是, 对于这类非线性约束函数能得到完美的理论分析, 事实上, 关于设备的寿命分布有许多类型, 如常见讨论的线性指数危险率分布及威布尔分布等等, 不同寿命分布会影响到设备的不同类型回购价格。若用这些分布刻画回购价格函数时, 由于分布的复杂, 在占线租赁模型中无法进行完美的数学推理分析, 进而不能获得模型的解析解, 只能从数值解上加以讨论分析, 有兴趣的读者可以自行探讨。

占线汽车租赁模型及竞争分析方法 篇2

随着经济的高速发展, 人们追求更舒适、便捷的生活方式, 拥有自己的一辆车成为了很多中国人的梦想。近几年中国汽车销量已占据世界第一。由于汽车持有量的剧增, 交通堵塞已经成为我国一些大城市的严重问题, 不仅如此, 大量的使用汽车给环境也造成庞大的压力。以北京为例, 大气污染物中, 39%的一氧化碳、74.8%的碳氢化合物和46.2%的氮氧化物来自汽车的尾气, 严重破坏了生态环境, 更危及人类健康。近年来, 政府部门高度重视, 北京出台了汽车“限购”措施, 限定年度汽车总量且每月26日实行摇号分配车辆。近几年购车的成本高昂, 租车免去了个人在汽车保养、维修、停放等方面的费用。因此, 理性的消费者开始关注汽车租赁市场。

汽车租赁[1]是指个人通过与汽车销售商之间签订各种合同, 汽车公司提供车辆、各种税费、车险、维修等服务, 个人在合同期内享有汽车使用权的一种实物租赁。

在西方各主要汽车大国, 汽车租赁业已有很长的历史, 经过近一个世纪的发展和竞争, 在众多的汽车租赁公司中, 已经形成了许多国际汽车租赁业的巨头。目前, 国内汽车租赁市场正处于起步阶段, 但却有着广阔的发展前景。

关于汽车租赁问题, 本文运用近年来优化领域兴起的竞争分析理论对占线汽车租赁问题进行详细的研究。占线租赁问题的研究始于Karp提出的著名的“租雪橇”问题[4]。

一般地, 在占线决策问题[2]中, 未来的信息不是完全知道的, 这种前提下, 设计合理的占线算法来解决实际问题就变得尤为重要。占线决策问题讨论的是成本最优或利润最优, 由于汽车租赁明显是成本最优问题, 故先给出成本

最优 (即费用最优) 的相关概念。现假设当期输入的信息, 不妨设为I, 占线算法下其所花费用用Cost ON (I) 表示。离线算法OFF则是指在事先知道全部输入I的情况下该问题的最优算法, 则其所花费用用Cos OFFt (I) 表示。在实际设计算法时, 往往占线算法和离线算法共同考虑在内的, 即对于实际问题, 占线和离线可以看成是竞争对手。显然, 我们可以求得它们的竞争比, 设为这个比值可以解释为:对于任意输入的信息I, 竞争比为c的占线算法, 均能保证费用不会超过离线最优费用的c倍。

风险预测作为风险规避的基础, 是风险管理的重要组成部分。外界多方面因素都可能引起风险事件的发生。因此, 在对风险事件进行预测中, 需要综合考虑到不确定以及随机的因素。根据已有信息进行合理预测。由于每个人的风险容忍水平不一样, 所以在做风险预测时还要考虑这一点, 使得预测不成功时所造成的损失在个人所能容忍的水平之内。

本文基于近几年的研究热点———占线算法与竞争分析理论, 设计了考虑交易成本、用车费用及汽车折旧的最优确定性占线策略。之后引入风险预测至汽车租赁问题中, 在预测的基础上设计了风险占线策略。将预测不成功的占线策略与最优确定性占线策略进行比较, 得到了将风险控制在决策者容忍水平内的策略。

1 模型的假设与建立

汽车类似于住房都是价格昂贵而且还可以进行二手交易。因此, 我们需要在租车和买车之间作出选择, 如果不考虑用汽车进行投资的情况, 则汽车的使用时间主要取决于工作性质 (如工作需要经常出差, 购买物品等等) 。选择买车, 则车主要承担够购车费、车险、维修费、保养费, 车子本身还会发生折旧, 如果不需要车了, 进行二手交易, 交易过程会产生交易成本。相比之下, 选择租车就只需付租赁费 (车险租赁公司出) 。

现有一实际问题:甲找到了一份工作, 需要一辆汽车满足工作及生活需求, 显然他将面临租车或买车两种选择。如果需要汽车的时间是已知的, 则问题的求解较为容易, 当租车成本超过购买成本时, 选择购买;反之, 则选择租车。

然而现实中需要汽车的时间往往甲是不能确定的, 此时就需设计相应的占线算法, 以达到费用最少的目的。为了讨论方便, 不妨令T表示此人在工作地的生活时间 (这段时间需要汽车) , 令B表示单位时间内租车的费用, D为单位时间汽车的折旧, 买车和卖车的交易费用都为C, Q表示单位时间内发生的车险、保养维修费。

首先汽车租赁公司要赚取利润, 租赁费用肯定要高于它所承担的汽车自身相关费用 (折旧及车险、保养) , 也就是D+Q约B。其次对于决策者而言, 一开始租车费用小于买车费用, 否则就没有讨论的必要, 即2C+D+Q跃B。

若需要汽车时间T是已知, 显然临界状态是:买车的费用和租车费用相同, 即令BT0=2C+ (D+Q) T0, 得T0=

2 C则离线最优策略是:B-D-Q

2 占线策略的设计与分析

多数情况下, 决策者 (甲) 对他需要汽车的时间是不知道的, 否则就没有讨论的必要了假设甲先租车到一定时间后再买车, 则占线策略为:嗓

下面的问题就是确定上述函数中的

1) T约j时, Cost ON=Cost OFF=BT, 这样得到的竞争比为1。两种策略均可。2) T叟j时, Cost ON=Bj+2C+ (D+Q) (T-j) ,

1) T约j时, Cost ON=Cost OFF=BT, 这样得到的竞争比为1。两种策略均可。2) T叟j时, Cost ON=Bj+2C+ (D+Q) (T-j) ,

当占线决策者选择j时刻之后购买汽车, 离线竞争对手总是选择实际时间T=j+1就是在占线决策者购买汽车之后马上宣布不需要使用汽车了, 这样竞争比最大、占线算法所花费的费用最高。因此j是最优的确定性策略的临界值, 该策略的竞争比是:

再将T=2CB-D-Q和T=j+1带入 (4) 式即可得到竞争比为c=1+ (B-D-Q) 2 (B2CC-B+D+Q)

再由B跃D+Q可知该竞争比总是小于2。即汽车租赁问题采取的策略是:租车至租金与购买使用成本 (车险及折旧) 的差几乎达到交易成本之和时, 然后购买汽车, 它可以保证汽车使用的费用不超过相应的最优离线策略费用的2) 倍。

3 模型的改进与完善

由现实生活可知, 决策者对需要汽车的时间也不是完全不知道, 他可根据劳动合同, 工作环境、工作偏好等因素对T作出合理的预测。显然, 这些预测存在一定的风险, 决策者对风险也会有特定的容忍度。考虑以上这些情况, 我们只需设计出一个风险占线策略, 并且将风险控制在决策者可容忍的水平之内。令停止租车的时刻为a, 决策者的风险容忍水平为r。以下就要依据预测信息, 确定a的取值范围。使得即使预测失败, 其所造成的损失也不会超过决策者的容忍水平。

下面对需要汽车的时间T分两种情况进行讨论:

情况1若0约T约2CB-D-Q, 此时确定性占线策略租赁汽车一直到B-2DC-Q-1时刻仍是最优风险占线策略。

情况2若T叟2CB-D-Q, 风险占线策略下d有两种情形:

1) 若a跃2CB-D-Q-1, 此时风险占线策略的竞争比总是比最优确定性占线策略的竞争比差, 显然决策者不会选择该风险策略;2) 若0燮a燮2CB-D-Q-1。

如果预测成功, 情况当然是最好的;如果预测失败, 该占线策略的竞争对手——离线对手为了使竞争比尽可能大, 总是会把T确定为占线决策者决定购买汽车的下一时刻, 亦即。此时的竞争比为:

在这种情形下, 我们需要将风险控制在决策者的容忍度内, 再根据风险占线策略集合的定义有:

解得:a叟2C (D+Q+2C) -茁-2r BC (其中茁=r (B-D-Q)

(2C-B+D+Q) ) 综上所述, a的取值区间为[2C (D+Q+2C) -茁-2r BC, 2C-1]

这样使得所设计的占线策略更加具有现实意义。

4 结束语

占线决策是决策领域中的一个重要方面, 占线算法的研究在很多经济管理问题上具有很强的实践性。本文就汽车租赁问题运用了占线策略, 具有较强的实用性。本文基于成本最优的目标, 通过与离线策略的结果进行竞争比较, 从而获得应对未来无法预知情形的最优确定性占线策略, 同时引入风险预测使模型更加完善。但现实中相关费用不可能是定值, 本文也未考虑通货膨胀、市场利率、政府政策等因素的影响, 还有待进一步提高。

参考文献

[1]李美娜.汽车租赁市场研究[J].上汽销售, 2001 (12) :11-23.

[2]徐维军, 徐寅峰, 卢致杰, 徐金红.占线决策问题及竞争分析方法[J].系统工程, 2005, 23 (5) :106-110.

[3]刘斌, 崔文田, 辛春林.基于风险补偿模型的占线住房租赁问题及其竞争分析[J].系统工程理论与实践, 2008, 28 (12) :154-159.

占线租赁问题 篇3

离散网络选址问题无论是对公共事业还是对私营公司的战略规划方面都有着非常重要而深远的影响。一般的,网络上任意两点间的最短路长度被定义为该两点间的距离。如果网络上的某点到其余点的距离之和最小,该点被称为median(中心)。如果问题是求在n个点的网络中寻求k个点,使得这k个点到其余的点的距离之和最小,这个问题就是著名的k-中心(k-median)选址问题,已经证明该问题是NP-hard的[1,2]。

k-中心选址问题是一个很基本的选址模型,实际中的选址问题或者本身就是一个k-中心选址问题,或者能将该问题作为一个子问题[3]。考虑到模型在计算上的复杂性,实际中的处理方法常常是将之建立成一个静态的、决定性的数学模型。但是,实际过程中的选址决策过程常常是一个长期的过程,会受到诸多因素的影响。因此,将选址决策模型建立成一个受相关不确定参数影响的动态选址模型更加符合实际。在一些研究文献中,已经考虑的不确定因素有需求和费用等等[4]。

本文主要考虑如下的实际情形:在全部需要建立的设施的个数不知道的前提下,需要决定在哪里建立初始的设施(或设施集),同时还要求,当新的设施建立后,前面已经建立的设施不能被删除。这是一个待选址个数不确定的选址问题。理论上,由于最优的选址方案同选址的个数是紧密相关的,不同的选址个数将决定不同的选址点,因此我们只能考虑如何将实际的选址集费用同在同样的选址个数下最优的选址集费用尽量的靠近,同时,需要在建立了新的设施时,不能删去现存的设施集。实际上,上述约束就是考虑如何使得待修建的设施集在最坏情形下达到某种最优,可以考虑用占线算法和竞争策略的相关理论来建立模型和进行研究。

Mettu和Plaxton在2003年建立并研究了占线中心(online median)选址问题[5]。他们的模型的输出是一个待选址序列, 并保证序列的每一个k元前序的费用, 都同相应的k-median问题的最优解费用接近。具体的性能度量是用算法竞争比来度量的,竞争比越小越好。自从该模型被提出后, 受到了越来越多的管理学家、 运筹学家以及计算机学家的重视, 但是进一步的研究成果很少。在Mettu和Plaxton的文章[5]中,他们对度量空间占线中心选址问题给出了一个竞争比下界,并同时给出了一个常数竞争比的竞争算法,他们的这些结果都强烈地利用到了度量空间的性质,即要求连接两点间的距离满足三角不等式。

本文研究一般网络上占线中心选址问题。一般网络上的占线中心选址问题同度量空间的占线中心选址问题的唯一差别是不要求两点间定义的距离满足三角不等式,根据现实中的两点间的距离的实际含义,这在实际中是有一定现实意义的,例如针对连接两点间的距离不是直线的交通网络,这时距离函数就不一定满足三角不等式。本文将给出这个问题的具体数学形式,并给出一个多项式时间的竞争算法并证明其竞争比。

2 问题描述

一般网络上占线中心选址问题可以数学描述如下:给定一个点集U及定义在U上的非负的距离函数d:U×U→R+和一个正的权重函数w:U→R+.这里不再假设距离函数d是一个度量,即d非负,对称但不满足三角不定式。同时定义一个点x到一个点集S的距离是$d(x,S)=\underset{y\in S}{{\displaystyle \min }}d(x,y)$,且|S|表示点集S中的点的个数。记n=|U|表示所有的点的数目,对任意子集S,S⊆U,定义其费用是$\cos t(S)={\displaystyle \sum _{x\in U}d}(x,S)w(x)$。一般网络上占线中心选址问题的数学描述如下:寻求子集序列Fi,i=1,2,…,n,使得|Fi|=i,F1⊂F2⊂…⊂Fn=U,且cost(Fi)≤c·opti,其中opti是一般网络上的i-median问题的最优解费用,c称为竞争比,c越小越好。

下面用一个实际例子来说明一般网络上占线中心选址问题的思路。考虑一个公司为了服务其顾客,准备修建服务设施来满足顾客的需要,这是一个经典的选址问题,但是考虑如下的实际情形:由于公司资本量的限制,公司在现在只能修建很少的服务设施,但是为了提高公司的服务水平,公司准备在不久的将来扩展其服务设施。同时由于一些因素的影响,以往修建的服务设施公司不能被拆除,因此公司的扩展计划实际上是一个待修建的服务设施个数不确定的选址序列问题。占线中心问题实际上考虑的是这样的问题:是否存在一个待修建的服务设施的序列使得,对于该序列的任意k个前序(即取出序列的前面k个作为选定的修建设施)的费用,与仅选择建造k个设施的最优费用(即已经确定只建造k个设施的最小费用)很靠近?对每一个k,考虑修建序列的前k个设施的费用与最优选择k个设施的费用的比值,占线中心问题的目标就是选择一个设施的排序使得对于所有的k,得到的最大比值最小。如果对于所有的k,得到的比值都不大于c,就称占线选址算法是竞争比是c的竞争算法,同时c被称为占线选址算法的竞争比。

本文研究的一般网络是指不要求两点间的距离满足三角不等式,这在现实中是有一定现实意义的,例如如果连接两点间的距离不是直线,那么这时的距离就不一定满足三角不等式。但同时考虑到实际问题距离及权重一定不是无限的,类似于文献[6],本文引入下述定义。

定义 对任意给定的选址问题, 定义$\Delta {}_e=\frac{\underset{u,v\in U}{{\displaystyle \max }}d(u,v)}{\underset{u,v\in U,u\ne v}{{\displaystyle \min }}d(u,v)}$,即Δe表示输入空间中最大的相对距离,定义$\Delta {}_w=\frac{\underset{u\in U}{{\displaystyle \max }}w(u)}{\underset{v\in U}{{\displaystyle \min }}w(v)}$,即Δw表示输入空间点的最大的相对权重。

文献[6]证明了对于网络上的占线中心选址问题的竞争比下界是$\frac{(n-2)\Delta {}_e+\sqrt{(n-2){}^2\Delta {}_e^2+4(n-1)}}{2(n-1)}$,并由此得到该问题不存在常数竞争比的竞争算法。本文将给出一个多项式时间的竞争算法,并证明该算法的竞争性能比为ΔeΔw.

一般网络上的占线中心选址问题是一个非常困难的问题, 这体现在如下两点上: ①问题的离线形式是一般网络上的k-中心(k-median)问题,这是一个是非常困难的问题, 已经证明该问题是NP难的[1], 并且构造任何一个常数近似比的近似算法也是NP难的[7]。②同时需要确定n个待修建的设施的序列,要求其满足Fi⊂Fi+1.

3 一般网络上的占线中心选址问题竞争算法设计

在Mettu和Plaxton的文章[5]中,针对度量空间占线中心选址问题,他们给出了一个常数竞争比的竞争算法,但是由于他们的算法强烈地依赖于三角不等式这一假设,因此他们的算法在本文问题中将不再适用,下面利用贪婪算法的思想给出一般网络上的占线中心选址问题的一个竞争算法,并在后面给出竞争比的证明。

一般网络上的占线中心选址问题竞争算法:

输入:空间(U,d),每一个点x∈U上定义的正权重函数w(x)>0;

输出:子集序列Fi,j=1,2,…,n,使得|Fj|=j,且F1⊂F2⊂…⊂Fn=U.

算法:

Step 1:对j=1,通过枚举得到最优值opt1,设得到的最优解为A={x0}。

Step 2:令Fn=U,对j=n-1,n-2,…,2,依次令rj∈Fj+1-A是Fj+1-A中使得 cost(Fj+1-r)最小的元素r,则令Fj=Fj+1-{rj}。

上述算法是一个多项式时间的算法,描述在下面的定理中。

定理1 上述构造的对一般网络上的占线中心问题的竞争算法是多项式时间算法。

证明 对于算法的第1步,为了得到1-median问题的最优解,必须计算出n个解的数值,这需要O(n)次乘法, O(n)次比较得到最小值, 因此完成算法第1步需要的时间为O(n)。对于算法的第2步,为了计算每一个Fj需要n-j次加法产生j个费用,再需要j次比较得到最小的费用,这样产生集合Fj需要${\displaystyle \sum _{t=n,\cdots ,k}n}=n(n-k)={\rm O}(n{}^2)$。综合这两步,算法需要的时间复杂度是O(n2),因而该算法是多项式时间算法。

下面考察算法得到的输出结果F1,F2,…,Fn的竞争比性能。首先有下面的引理。

引理1 对每一个j=n-1,n-2,…,2,有$\cos t(F{}_j)\le \frac{1}{j}\cos t(A)+\frac{j-1}{j}\cos t(F{}_{j+1})$,其中集合Fj和Fj+1是由算法输出的点集。

证明

$\begin{array}{l}\text{c}\text{o}\text{s}t(F{}_j)-\text{c}\text{o}\text{s}t(F{}_{j+1})\\ =\underset{r\in F{}_{j+1}-A}{{\displaystyle \min }}\{\text{c}\text{o}\text{s}t(F{}_{j+1}-\{r\})-\text{c}\text{o}\text{s}t(F{}_{j+1})\}\\ \le \frac{1}{|F{}_{j+1}-A|}{\displaystyle \sum _{r\in F{}_{j+1}-A}\{}\text{c}\text{o}\text{s}t(F{}_{j+1}-\{r\})-\text{c}\text{o}\text{s}t(F{}_{j+1})\}\\ =\frac{1}{j}{\displaystyle \sum _{r\in F{}_{j+1}-A}\{}\text{c}\text{o}\text{s}t(F{}_{j+1}-\{r\})-\text{c}\text{o}\text{s}t(F{}_{j+1})\}\\ \le \frac{1}{j}(\text{c}\text{o}\text{s}t(A)-\text{c}\text{o}\text{s}t(F{}_{j+1}))\end{array}(1)$

这里, 第一个等号是根据算法中Fj的定义, 第二个不等式是由于用平均数来代替最小值, 第三个等号是因为根据算法有|Fj+1|=j+1,|A|=1及A⊂Fj+1,下面只需要证明,∀A⊂R,成立${\displaystyle \sum _{r\in R-A}\{}\cos t(R-\{r\})-\cos t(R)\}\le \cos t(A)-\cos t(R)$,记该式为式(1)。∀x∈U,由于d(x,R-{r})-d(x,R)≥0,得到${\displaystyle \sum _{r\in R-A}\{}d(x,R-\{r\})-d(x,R)\}={\displaystyle \sum _{r\in R-A:d(x,R-\{r\})>d(x,R)}\{}d(x,R-\{r\})-d(x,R)\}‚$由r∈R-A以及d(x,R-{r})>d(x,R),点r必定是惟一的满足d(x,r)=d(x,R)的点,因此上式等于d(x,R-{r})-d(x,R)|r∈R-A:d(x,r)=d(x,R).另一方面,由r∈R-A可以得到d(x,R-{r})-d(x,R)|r∈R-A:d(x,r)=d(x,R)≤d(x,A)-d(x,R),这样将该式两边乘上w(x)并对所有的x∈U求和可以得到式(1),$\cos t(F{}_j)-\cos t(F{}_{j+1})\le \frac{1}{j}(\cos t(A)-\cos t(F{}_{j+1}))$成立,根据这个不等式,将结果重排可以得到本引理。

引理2 对每一个j=n,n-1,…,1,下面的不等式成立

$\text{c}\text{o}\text{s}t(F{}_j)\le (1-\frac{j-1}{n-1})\text{c}\text{o}\text{s}t(A)$

其中, 集合Fj是由算法输出的点集。

证明 利用反向数学归纳法。首先由cost(Fn)=cost(U)=0知命题对于j=n成立。现假设命题对于2≤t≤n-1中的某个t成立,证明对于t-1也同样成立。根据引理1得$\cos t(F{}_{t-1})\le \frac{1}{t-1}\cos t(A)+\frac{t-2}{t-1}\cos t(F{}_t)$,据归纳假设,有$\cos t(F{}_t)\le (1-\frac{t-1}{n-1})\cos t(A)$,从而有$\cos t(F{}_{t-1})\le \frac{1}{t-1}\cos t(A)+\frac{t-2}{t-1}(1-\frac{t-1}{n-1})\cos t(A)=(1-\frac{t-2}{n-1})\cos t(A)$,得证。

引理3 对于一般网络上的k-median问题,令j=1,2,…,n,有$opt{}_1\le \frac{n-1}{n-j}\Delta {}_e\Delta {}_{w}opt{}_j$,其中,opt1和optj分别是1-median问题和j-median问题的最优值。

证明 设给定的一般网络的顶点集U={x1,x2,…,xn},且不妨假设{x1}使得1-median问题达到最优,Y使得j-median问题达到最优,|Y|=j,则有

$\begin{array}{l}opt{}_1={\displaystyle \sum _{i=2}^{n}d}(x{}_i,x{}_1)w(x{}_i)\\ \le (n-1)\underset{u,v\in U}{{\displaystyle max}}d(u,v)\cdot \underset{u\in U}{{\displaystyle max}}w(u)\\ opt{}_j={\displaystyle \sum _{x\in UY}d}(x,Y)w(x)\\ \ge (n-j)\underset{u,v\in U,u\ne v}{{\displaystyle \min }}d(u,v)\cdot \underset{u\in U}{{\displaystyle \min }}w(u)\end{array}$

于是,我们得到

$\frac{opt{}_1}{opt{}_j}\le \frac{(n-1)\underset{u,v\in U}{{\displaystyle max}}d(u,v)\cdot \underset{u\in U}{{\displaystyle max}}w(u)}{(n-k)\underset{u,v\in U,u\ne v}{{\displaystyle \min }}d(u,v)\cdot \underset{u\in U}{{\displaystyle \min }}w(u)}=\frac{n-1}{n-j}\Delta {}_e\Delta {}_w$

命题成立。

根据这些引理,可以得到关于构造的竞争算法的竞争性能比结果。

定理2 算法所得到的集合序列F1,F2,…,Fn满足如下性质:

①F1⊂F2⊂…⊂Fn=U;

②∀k=1,2,…,n,|Fk|=k;

③∀k=1,2,…,n,费用函数满足cost(Fk)≤ΔeΔwoptk,即算法对一般网络上的占线中心选址问题的竞争比是ΔeΔw.

证明 根据算法的第2步, 本命题①和②成立, 只需要考虑③。首先根据上面的引理2知, 对于j=n, n-1,…,1, 成立$\cos t(F{}_j)\le (1-\frac{j-1}{n-1})\cos t(A)$, 再根据引理3和算法的第1步, 可以得到$\cos t(F{}_j)\le (1-\frac{j-1}{n-1})\text{c}\text{o}\text{s}t(A)\le (1-\frac{j-1}{n-1})(\frac{n-1}{n-j})\Delta {}_e\Delta {}_{w}opt{}_j=\Delta {}_e\Delta {}_{w}opt{}_j$,这样③得到证明,命题证毕。

推论 对于权重函数相等的情形,算法得到的竞争比是Δe.

4 结束语

本文针对一般网络上的占线中心选址问题进行了研究。 文献[6]证明了该问题的竞争比下界是$\frac{(n-2)\Delta {}_e+\sqrt{(n-2){}^2\Delta {}_e^2+4(n-1)}}{2(n-1)}$(该下界大于$\Delta {}_e-\frac{\frac{\Delta {}_e+1}{\Delta {}_e}}{n-1})$,并证明了该问题不存在常数竞争比的竞争算法。本文给出了一个竞争比为ΔeΔw的竞争算法,特别地,该算法针对权重函数都相等的情形竞争比能达到Δe.在以后的工作中,可以考虑如果设计出更好的竞争算法来改进这个竞争比结果。

参考文献

[1]Garey M R,et al.Computers and intractability:aguide to the theory of NP-completeness[M].SanFrancisco,CA:Freeman,1979.

[2]Kariv O,Hakimi S L.An algorithm approach tonetwork location problems,Part II:the p-medians[J].SIAM J.Appl.Math,1979,37:539~560.

[3]Drezner Z,Hamacher H.Facility location:application and theory[M].Springer,2002.

[4]Current J,Daskin M,Schilling D.Discretenetwork location models[A].Drezner Z,HamacherW.Facility location:applications and theory[M].Springer,2002:81~118.

[5]Mettu R R,et al.The online median problem[J].SIAM Journal of Computing,2003,32(3):816~832.

[6]代文强,徐寅峰,李毅学.占线中心选址问题竞争比的下界研究[J].系统工程,2006,24(8):98~101.