，，，

(1.廣東工業(yè)大學(xué)管理學(xué)院，廣東 廣州 510520；2.華南理工大學(xué)工商管理學(xué)院，廣東 廣州 510640)

1 引言

設(shè)備租賃已成為企業(yè)越來越重要的融資方式之一，對國民經(jīng)濟(jì)各行業(yè)的發(fā)展起著重要的助推作用。企業(yè)往往在不知道設(shè)備未來需求期限的情況下就需要做出租賃決策，這是一個(gè)在線決策的問題。興起于理論計(jì)算機(jī)學(xué)科領(lǐng)域的在線算法與競爭分析理論[1-2]可以有效地為在線決策問題提供解決思路和方法。在線租賃問題的典型代表是著名的“租雪橇”模型[3]。在這個(gè)模型中，在線決策者需要使用某種設(shè)備,但并不清楚自己到底會(huì)用多長時(shí)間，只有在每個(gè)階段初才能決定是否繼續(xù)使用。在線決策者可以通過每期付較少的費(fèi)用以租賃的方式獲得設(shè)備的臨時(shí)使用權(quán)，也可以通過一次性付較多的費(fèi)用以購買的方式獲得設(shè)備的永久使用權(quán)。在線決策者可以先租賃設(shè)備一段時(shí)間然后再購買，問題的關(guān)鍵在于確定租賃多長時(shí)間之后購買比較好。根據(jù)在線算法和競爭分析理論，最優(yōu)的在線租賃策略是租賃k-1次之后購買設(shè)備，這樣可以保證在線策略費(fèi)用不會(huì)超過離線策略費(fèi)用的2-1/k倍，其中k為雪橇購買價(jià)格與租賃價(jià)格的比值。

眾多學(xué)者對“租雪橇”模型進(jìn)行了深入的擴(kuò)展研究。Karlin等[4]給出了在線租賃問題的最優(yōu)隨機(jī)性策略，其競爭比為e/(e-1)≈1.582。Irani等[5]研究了設(shè)備購買價(jià)格波動(dòng)而租賃價(jià)格不變的在線租賃模型，分別給出了確定性和隨機(jī)性策略競爭比的上下界，并研究了離線對手具有統(tǒng)計(jì)特征的情形，即限定未來價(jià)格波動(dòng)滿足一定條件?？紤]到市場利率是一個(gè)重要的因素，El-Yaniv等[6]研究了帶利率的在線租賃模型，分別給出了最優(yōu)確定性和最優(yōu)隨機(jī)性策略及其競爭比。Fujiwara等[7]將輸入序列的概率分布假設(shè)與競爭分析方法結(jié)合起來，研究了需求序列服從指數(shù)分布的在線租賃模型，研究結(jié)果更符合租賃決策的實(shí)際情況。由于傳統(tǒng)的競爭分析是最壞情形分析方法，往往被認(rèn)為過于保守。al-Binali[8]定義預(yù)期、風(fēng)險(xiǎn)和回報(bào)等概念，建立了在線租賃問題的風(fēng)險(xiǎn)回報(bào)模型，給出了不同風(fēng)險(xiǎn)容忍度下的風(fēng)險(xiǎn)回報(bào)策略和最優(yōu)約束競爭比。朱志軍等[9]考慮了市場利率下在線租賃問題的風(fēng)險(xiǎn)回報(bào)模型。徐寅峰等[10]研究了利率和稅率等市場因素下需求序列服從指數(shù)分布的在線租賃問題的連續(xù)結(jié)構(gòu)模型和需求序列服從幾何分布的在線租賃問題的離散結(jié)構(gòu)模型，分別給出了最優(yōu)競爭策略及其競爭比?？紤]到租賃價(jià)格的變化，徐維軍等[11]和馬衛(wèi)民等[12]分別研究了租賃價(jià)格可變情形的在線租賃模型。Lotker等[13]研究了無純購買策略的在線租賃模型，并給出了最優(yōu)隨機(jī)性策略及其競爭比?？紤]到大型設(shè)備具有可折舊和可轉(zhuǎn)賣的特點(diǎn)，張永等[14-15]分別給出了可折舊設(shè)備在線租賃的隨機(jī)性策略和風(fēng)險(xiǎn)回報(bào)策略。胡茂林[16]研究了連續(xù)可分資產(chǎn)的在線租賃問題，得到了最優(yōu)的逐步購買策略，同時(shí)給出了具體租賃過程中每期的購買值和租賃值的計(jì)算公式。Zhang Guiqing等[17]提出了帶有多種折扣選擇的在線租賃模型，構(gòu)造了一個(gè)競爭比為4的在線策略，證明了當(dāng)折扣選擇足夠多時(shí)該策略是最優(yōu)的。另外，競爭分析方法也在其它相關(guān)決策問題中得到了廣泛的應(yīng)用，如在線優(yōu)惠卡問題[18-19]、在線設(shè)備更新問題[20-21]。

然而，在現(xiàn)實(shí)租賃市場中，設(shè)備承租方往往需要與設(shè)備出租方簽訂合同確定租賃的天數(shù)。由于設(shè)備的未來使用期限未知，因此關(guān)鍵的問題是如何確定預(yù)租天數(shù)。若預(yù)租天數(shù)過多，承租方將會(huì)選擇提前結(jié)束合同，因而需要支付違約金；若預(yù)租天數(shù)過少，承租方將遭受設(shè)備缺失帶來的損失。本文主要從績效角度研究合同約束下的多階段在線租賃問題，提出用績效比來衡量在線策略的性能?；诳冃П确治龊途€性分?jǐn)?shù)規(guī)劃方法，本文首先研究合同約束下的單階段在線租賃模型，給出最優(yōu)預(yù)租策略及其績效比；然后進(jìn)一步研究合同約束下的多階段在線租賃模型并給出相應(yīng)的結(jié)果。最后，借助于數(shù)值算例，分析最優(yōu)預(yù)租策略及其績效比與日收益、租賃費(fèi)和損失費(fèi)等因素之間的關(guān)系。

2 預(yù)備知識

2.1 合同約束下的多階段在線租賃模型

在需要使用設(shè)備時(shí)，在線決策者與設(shè)備出租方簽訂合同確定租賃的天數(shù)。但是，在線決策者在簽訂合同時(shí)往往還不知道未來使用設(shè)備的天數(shù)，這是一個(gè)在線決策的問題。在線決策者的目標(biāo)是最大化自己的收益。若實(shí)際需求天數(shù)小于合同預(yù)租天數(shù)，則在線決策者提前終止合同，并按天賠償出租方一定的損失；若實(shí)際需求天數(shù)大于合同預(yù)租天數(shù)，則承租方在合同到期時(shí)撤走設(shè)備，在線決策者因設(shè)備缺失遭受一定損失。這里沒有考慮獲得設(shè)備永久使用權(quán)的購買策略。假設(shè)在線決策者在未來m個(gè)階段中需要使用設(shè)備，并對第i(1im)階段的在線租賃決策做以下假設(shè)：

(a) 在線決策者使用設(shè)備一天獲得的收益為ri，合同約定每天的租賃費(fèi)用為ci，不失一般性，有ri>ci；在線決策者需要支付在設(shè)備運(yùn)輸、安裝過程中產(chǎn)生的費(fèi)用Ti，該費(fèi)用與合同約定的租賃天數(shù)無關(guān)；

(b) 若提前終止租賃合同，在線決策者將在合同約定未使用的天數(shù)中每天賠償出租方損失si，不妨設(shè)si

(c) 若合同預(yù)租天數(shù)少于實(shí)際需要的租賃天數(shù)，則在線決策者在缺失設(shè)備的階段將遭受一定的收益損失，每天的損失記為li。

設(shè)在線決策者按照合同約定在第i階段預(yù)租ti天。若實(shí)際需要租賃天數(shù)ni小于合同約定預(yù)租天數(shù)ti時(shí)，在線決策者可以提前終止合同，在剩下的(ti-ni)天中每天賠償設(shè)備出租方si；若實(shí)際需要租賃天數(shù)ni大于合同約定租賃天數(shù)ti，則在線決策者需要在剩下的(ni-ti)天中每天遭受收益損失li。在線決策者的目標(biāo)是確定合適的預(yù)租天數(shù)ti，使得凈收益盡可能地大。當(dāng)合同約定預(yù)租天數(shù)為ti，實(shí)際需要租賃天數(shù)為ni時(shí)，第i階段的凈收益函數(shù)為：

gi(ni)=rimin{ti,ni}-citi+(ci-si)(ti-ni)+-li(ni-ti)+-TiΙ(ti)

(1)

其中，(ti-ni)+=max{ti-ni, 0}，(ni-ti)+=max{ni-ti, 0}，Ι(ti)為指示函數(shù)，即

記t=(t1,…,tm)，表示m個(gè)階段的預(yù)租天數(shù)向量；記n=(n1,…,nm)，表示m個(gè)階段的實(shí)際需要租賃天數(shù)向量。在線策略m個(gè)階段總的凈收益函數(shù)為：

(2)

2.2 績效比分析

本文研究的帶合同約束的在線租賃模型是傳統(tǒng)的在線租賃模型的一種推廣。競爭分析方法是研究在線決策問題的一種重要方法，它將在線策略的收益與最優(yōu)離線策略的收益作比較，是一種最壞情形分析方法。該方法利用競爭比衡量在線策略的優(yōu)劣。滿足不等式：

(3)

的最小的α稱為在線策略的競爭比，其中δ為與n無關(guān)的常數(shù)。若δ=0，則α稱為嚴(yán)格競爭比，此時(shí)有：

由于本文討論的在線策略凈收益Gm(n)可能為零或者負(fù)值，因此需要對上述定義進(jìn)行修正。本文把在線收益偏離離線收益的程度與離線收益的比值作為衡量在線策略優(yōu)劣的標(biāo)準(zhǔn)。定義：

為在線策略的嚴(yán)格績效比。類似于競爭比，定義績效比如下：滿足不等式：

-Gm(n)?n≥0

(4)

的最小的ω稱為在線策略的績效比。顯然，績效比越小，在線策略越好。

2.3 線性分?jǐn)?shù)規(guī)劃方法

線性分?jǐn)?shù)規(guī)劃問題是指目標(biāo)函數(shù)為最小化(最大化)一個(gè)比值(分?jǐn)?shù)形式)，且其約束條件為線性形式的數(shù)學(xué)規(guī)劃問題。根據(jù)本文需要，我們給出一維的線性分?jǐn)?shù)規(guī)劃模型，即

(5)

本文討論過程中將用到如下結(jié)論：

引理1 如果線性分?jǐn)?shù)規(guī)劃問題(5)的可行域{x:fx+g>0,x≥0}非空，則線性分?jǐn)?shù)規(guī)劃問題(5)與線性規(guī)劃問題等價(jià)。

(6)

引理1及其證明參見文獻(xiàn)[22]第151頁。引理1表明可將線性分?jǐn)?shù)規(guī)劃問題轉(zhuǎn)化為線性規(guī)劃問題進(jìn)行求解。

3 合同約束下的在線租賃績效分析

3.1 合同約束下的單階段在線租賃績效分析

合同約束下的單階段在線租賃的凈收益函數(shù)可以用(1)式表示(其中i=1)。為簡便起見，略去下標(biāo)i，即：

g(n)=rmin{n,t}-ct+(c-s)(t-n)+-l(n-t)+-TΙ(t)

(7)

基于績效比分析和線性分?jǐn)?shù)規(guī)劃方法，我們給出合同約束下的單階段在線租賃問題的最優(yōu)預(yù)租策略及其績效比。

定理 1 對于合同約束下的單階段在線租賃問題，最優(yōu)策略是預(yù)租t*=T/(r-c)天，且最優(yōu)績效比為:

(8)

證明 由(7)知，最優(yōu)離線策略凈收益是關(guān)于實(shí)際需求租賃天數(shù)n的函數(shù)，因此最優(yōu)離線策略選擇t=n或者t=0，此時(shí)凈收益為g*(n)=max{(r-c)n-T, -nl}。由假設(shè)(d)知離線凈收益為正，所以：

(r-c)n-T>0

即

t*是關(guān)于實(shí)際預(yù)租天數(shù)n的一個(gè)下界。因此此時(shí)的績效比可以表示為：

(9)

在線策略凈收益g(n)與預(yù)租天數(shù)t有關(guān)，我們分別考慮t>0和t=0兩種情形。當(dāng)t>0時(shí)，我們又分別考慮t>n和tn兩種情形。

(a)t>n。這種情形下的績效比可表示為：

(10)

(11)

由對偶理論知線性規(guī)劃問題(11)的對偶問題為

(12)

若原線性規(guī)劃問題(11)有可行解，則對偶問題(12) 也有可行解。故有：

(13)

則有tt*。

(14)

(b)tn。這種情形下的績效比為：

(15)

(16)

由對偶理論知線性規(guī)劃問題(16)的對偶問題為：

(17)

若原始線性規(guī)劃問題(16)有可行解，則對偶問題(17) 也有可行解。故有：

(18)

即t≥t*

(19)

當(dāng)t=0時(shí)，對偶問題(17)的可行域{λ:λ≥l/(r-c),λ-1}為空，因此這種情形下有限績效比不存在。由于實(shí)際需要租賃天數(shù)n對在線決策者而言是未知的，因此(14)式和(19)式應(yīng)該同時(shí)滿足，即t=t*，此時(shí)績效比有限。由最壞情形分析法知最優(yōu)績效比為：

3.2 合同約束下的多階段在線租賃績效分析

在前面單階段模型分析的基礎(chǔ)上，本節(jié)討論合同約束下的多階段在線租賃績效分析。

(20)

-gi(ni)

(21)

當(dāng)i?A時(shí)，有ni從而有：

因此，該情形下的績效比滿足:

4 數(shù)值分析

本節(jié)借助于數(shù)值算例分析模型中各參數(shù)對最優(yōu)在線策略及其績效比的影響。假設(shè)某企業(yè)需要租賃一種大型生產(chǎn)設(shè)備，固定的交易費(fèi)用為T、使用設(shè)備每天產(chǎn)生的收益為r、合同約定每天的租賃價(jià)格為c、缺失設(shè)備每天的損失為l。表1給出了不同參數(shù)組合下的最優(yōu)在線預(yù)租策略及其績效比。

表1 不同參數(shù)組合下最優(yōu)在線預(yù)租策略及其績效比

由表1和定理1知，合同約束下的單階段最優(yōu)在線預(yù)租天數(shù)t*關(guān)于交易費(fèi)用T遞增(觀察第1、2、3行)，收益r遞減(觀察第1、4、5行)，關(guān)于租賃費(fèi)用c遞增(觀察第1、6、7行)；相應(yīng)的最優(yōu)績效比w*關(guān)于收益r遞減(觀察第1、4、5行)，關(guān)于租賃費(fèi)用c遞增(觀察第1、6、7行)，關(guān)于損失費(fèi)l遞增(觀察第1、8、9行)。同時(shí)也可以看出最優(yōu)預(yù)租天數(shù)及其績效比與合同賠償損失費(fèi)s無關(guān)。事實(shí)上，在預(yù)租天數(shù)一定的情況下，離線策略要想盈利必須滿足n>T/(r-c)，即預(yù)租天數(shù)小于實(shí)際需要租賃天數(shù)，在線決策者不會(huì)遭受合同賠償損失費(fèi)，從而績效比與s無關(guān)。

假設(shè)該企業(yè)需要預(yù)租設(shè)備9個(gè)階段，第i階段的參數(shù)取值對應(yīng)于表1中的第i組參數(shù)組合(1i9)，則對應(yīng)的最優(yōu)在線預(yù)租策略為：

t*=(20,40,60,13,10,27,40,20,20)，

該策略的績效比為3。由定理2知，合同約束下的多階段在線租賃的最優(yōu)績效比是每個(gè)階段最優(yōu)績效比的最大值。從中可以看出績效比只與每個(gè)階段的日收益、租賃價(jià)格及設(shè)備缺失損失費(fèi)有關(guān)。

(22)

5 結(jié)語

本文結(jié)合租賃市場的實(shí)際情況，提出了帶合同約束的多階段在線租賃問題。本文從收益角度出發(fā)，用績效比來衡量在線策略的競爭性能?；诳冃П确治龊途€性分?jǐn)?shù)規(guī)劃方法，首先給出了單階段在線租賃的最優(yōu)預(yù)租策略及其績效比；在此基礎(chǔ)上，進(jìn)一步給出了多階段在線租賃的最優(yōu)預(yù)租策略及其績效比，并分析了最優(yōu)預(yù)租策略及其績效比與各因素之間的關(guān)系。研究結(jié)果一方面可以為設(shè)備承租方確定預(yù)租天數(shù)提供一定的決策依據(jù)，另一方面可以在確定租賃費(fèi)、損失費(fèi)等方面為設(shè)備出租方提供一定的理論指導(dǎo)。然而，本文僅從最壞情形分析的角度研究了合同約束下的在線租賃問題，顯得有些保守。為了提高在線策略的性能，可以在模型中引入在線者的預(yù)期或者輸入序列的概率分布假設(shè)。利率和通貨膨脹是影響租賃決策的重要因素，將這些因素引入到本文討論的模型中也是值得進(jìn)一步研究的方向。

參考文獻(xiàn)：

[1] Borodin A, El-Yaniv R.Online computation and competitive analysis[M].Cambridge: Cambridge University Press, 1998.

[2] Fiat A, Woeginger J G.Online algorithms: The state of the art[M].Berlin: Springer, 1998.

[3] Karp R.Online algorithms versus offline algorithms: How much is it worth to know the future[C].Proceedings of IFIP 12th World Computer Congress, Madrid, September，7-11, 1992.

[4] Karlin A R, Manaees M S, McGeogh L, et al.Competiitive randomized algorithms for non-uniform problems[J].Algorithmica, 1994, 11(1): 542-571.

[5] Irani S, Ramanathan D.The problem of renting versus buying[R].Working Paper, University of Califoria, 1998.

[6] El-Yaniv R, Kaniel R, Linial N.Competitive optimal on-line leasing[J].Algorithmica, 1999, 25(1): 116-140.

[7] Fujiwara H, Iwama K.Average-case competitive analyses for ski-rental problems[J].Algorithmica, 2005, 42(1): 95-107.

[8] Al-Binali S.A risk-reward framework for the competitive analysis of financial games[J].Algorithmica, 1999, 25(1): 99-115.

[9] 朱志軍, 徐寅峰, 徐維軍.局內(nèi)租賃問題的風(fēng)險(xiǎn)補(bǔ)償模型及其競爭分析[J].管理科學(xué)學(xué)報(bào), 2004, 7(3): 64-74.

[10] Xu Yinfeng, Xu Weijun, Li Hongyi.On the on-line rent-or-buy problem in probabilistic environments[J].Journal of Global Optimization, 2007, 38(1): 1-20.

[11] 徐維軍, 張衛(wèi)國, 胡茂林.租金費(fèi)用和購買價(jià)格連續(xù)可變的在線租賃競爭策略分析[J].中國管理科學(xué), 2006, 14(2): 94-99.

[12] 馬衛(wèi)民, 陳國青.價(jià)格連續(xù)型局內(nèi)設(shè)備租賃問題的競爭分析[J].系統(tǒng)工程理論與實(shí)踐, 2006, 26(4): 90-96.

[13] Lotker Z, Patt-Shamir B, Rawitz D.Ski rental with two general options[J].Information Processing Letters, 2008, 108(6): 365-368.

[14] 張永, 張衛(wèi)國, 徐維軍.可折舊設(shè)備在線租賃的隨機(jī)性競爭策略[J].管理科學(xué)學(xué)報(bào), 2010, 14(1): 69-77.

[15] Zhang Yong, Zhang Weiguo, Xu Weijun, et al.A risk-reward model for the online leasing of depreciable equipment[J].Information Processing Letters, 2011, 111(6): 256-261.

[16] 胡茂林.可分資產(chǎn)的在線租賃策略及其競爭分析[J].系統(tǒng)工程理論與實(shí)踐, 2011, 31(1): 144-150.

[17] Zhang Guiqing, Poon C K, Xu Yinfeng.The ski-rental problem with multiple discount options[J].Information Processing Letters, 2011, 111(18): 903-906.

[18] Fleischer R.On the bahncard problem[J].Theoretical Computer Science, 2001, 268(1): 161-174.

[19] 辛春林, 徐寅峰, 馬衛(wèi)民.基于概率分布的局內(nèi)特殊優(yōu)惠卡問題及其競爭分析[J].系統(tǒng)工程理論與實(shí)踐, 2007, 27(10): 84-92.

[20] El-Yaniv R, Karp R M.Nearly optimal competitive online replacement policies[J].Mathematics of Operations Research, 1997, 22(4): 814-839.

[21] Xin Chunlin, Ma Weimin, Yang Lei.Competitive analysis of two special online device replacement problems[J].Journal of Computer Science and Technology, 2008, 23(2): 203-213.

[22] Boyd S, Vandenberghe L.Convex optimization[M].Cambridge: Cambridge University Press, 2004.