購買價格遞減的在線租賃問題策略設(shè)計

購買價格遞減的在線租賃問題策略設(shè)計

胡茂林1，徐維軍2

(1.淮陰師范學(xué)院數(shù)學(xué)科學(xué)學(xué)院運籌與優(yōu)化研究室，江蘇淮安223300；2.華南理工大學(xué)工商管理學(xué)院決策科學(xué)系，廣東廣州510641)

摘要：運用在線問題與競爭分析的方法研究了購買價格遞減的在線租賃問題。通過揭示相關(guān)費用函數(shù)的性質(zhì)，先后給出了最優(yōu)離線策略以及在線策略。通過競爭比分析，證明了我們給出的在線策略是該問題唯一最優(yōu)策略，而且該策略的競爭比隨購買價格的優(yōu)惠率的增加呈嚴格遞減趨勢。競爭分析結(jié)果表明考慮購買價格遞減因素能夠改進在線策略的競爭比從而提高決策效率。

關(guān)鍵詞：在線租賃問題；在線策略；競爭分析；競爭比；購買價格遞減

收稿日期：2012-12-24

基金項目：國家自然科學(xué)基金資助項目(71471065)；教育部人文社會科學(xué)研究規(guī)劃基金(10YJA630062)；中央高?；究蒲袠I(yè)務(wù)費專項資金資助(2012ZZ0035)

作者簡介：胡茂林(1963-)，男，寧夏人，教授, 碩士生導(dǎo)師，研究方向：運籌與優(yōu)化、在線金融算法；徐維軍(1975-)，男，寧夏人，研究員，博士生導(dǎo)師，研究方向：管理科學(xué)與工程、在線金融算法。

中圖分類號：F224.0 文章標識碼：A

Strategy Design on Online Leasing Problem with Decreasing Purchasing Price

HU Mao-lin1, XU Wei-jun2

(1.SchoolofMathematicalScience,HuaiyinNormalUniversity,Huaian223300,China; 2.SchoolofBusinessAdministration,SouthChinaUniversityofTechnology,Guangzhou510641,China)

Abstract:In this paper, we use the method of competitive analysis for online problem to study an online leasing problem with decreasing price for purchasing. By analyzing the properties of cost functions concerned, the optimal offline strategy and an online strategy are given. By way of the analysis of competitive rate, we prove online strategy to be the unique optimal strategy for this problem, and competitive rate of this strategy is strictly decreasing with the preferential rate of purchasing price. The result shows that taking the factors of the decreasing of purchasing price will improve the competitive rate of online strategy and thereby increase the decision-making efficiency.

Key words:online leasing problem; online strategy; competitive analysis; competitive rate; decreasing purchasing price

0引言

租賃是社會經(jīng)濟活動中最常見的一種經(jīng)濟現(xiàn)象。關(guān)于租賃問題，經(jīng)典的研究側(cè)重于資產(chǎn)租賃合同分析及稅收對租賃與購買決策的影響分析。到了1992年,Karp[1]提出了在理論計算機科學(xué)領(lǐng)域享有盛名的在線租雪橇問題：某滑雪者去滑雪場滑雪，在滑雪場每天租用一幅雪橇的租金為1，購買一幅雪橇的價格為s，一旦他在某一天買下一幅雪橇，則以后要滑雪時就不再付租用費。問滑雪者在不知道自己要滑多少天的情況下是租用雪橇還是購買雪橇或者是在租用多少天后再購買雪橇使得所花費用較少? 若滑雪天數(shù)已知則為離線問題，若滑雪天數(shù)未知則為在線問題。對于在線租雪橇問題，Karp證明了在租用s-1天后若要繼續(xù)滑雪則立即購買雪橇最為劃算。此時問題的競爭比為2-1/s。

隨后在線問題之競爭分析的方法便成了研究租賃問題的熱點方法。學(xué)者們在這一經(jīng)典模型的基礎(chǔ)上結(jié)合實際經(jīng)濟背景考慮了隨機性算法，引入了利率，折舊，風(fēng)險等因素得到了很多推廣變形，涌現(xiàn)出了大量的關(guān)于在線租賃問題研究的文章。Karlin[2]等學(xué)者給出了在線租賃問題的隨機性在線算法。El-Yaniv[3]等建立了設(shè)備更新模型，考察了資本市場上一個生產(chǎn)商更新設(shè)備問題，該模型可廣泛地應(yīng)用于供貨商變更問題、菜單成本問題、融資抵押問題等。之后，El-Yaniv[4]又從實際經(jīng)濟決策角度出發(fā)，考慮了當投資者進行租賃活動時所面臨的一個不可忽視的重要因素利率，給出了最優(yōu)確定性算法和最優(yōu)隨機性算法。Irani和Ramanathan[5]研究了當購買價格波動而租賃費用保持不變情形，分別給出了確定性算法和隨機性算法的競爭比上下界，并運用具有統(tǒng)計特征對手來研究在線租賃問題等。Azar[6]等考慮了生產(chǎn)商面對未知的需求訂單和市場不斷出現(xiàn)生產(chǎn)該商品的生產(chǎn)設(shè)備，生產(chǎn)商采取什么策略更新生產(chǎn)設(shè)備才能使得成本最小化問題。Fujiwara[7]等人結(jié)合未來輸入具有連續(xù)性概率信息研究了在線租賃決策問題。Xu[8]等在Fujiwara研究的基礎(chǔ)上，深入研究了存在利率情況下當輸入的概率信息具有離散型結(jié)構(gòu)的設(shè)備融資決策問題。在國內(nèi)，王揚[9]、董玉成[10]等分別研究了有無利率情形下投資者具有各種預(yù)期的風(fēng)險回報在線租賃問題等；胡茂林[11]考慮了連續(xù)可分資產(chǎn)的多重在線租賃問題；徐維軍[12]等還考慮了購買價格和租金費用均連續(xù)可變的在線競爭策略分析問題，特別地，文中最后還提出了需要進一步研究的問題：當購買價格每期以固定比例呈現(xiàn)遞減趨勢變化時如何設(shè)計競爭策略。

雖然當購買價格遞減變化時使在線租賃模型復(fù)雜化，但能獲得更小的競爭比同時也是問題的研究向現(xiàn)實的一種貼近。正像文獻[13]指出的那樣，隨著租賃業(yè)的快速發(fā)展，市場的激烈競爭,供求關(guān)系的不斷變化，購買設(shè)備的價格也會不斷發(fā)生變化。當供大于求時，租賃公司為了維持或者擴大業(yè)務(wù)量，經(jīng)常會推出一些購買價格隨租用時間的長短而給予優(yōu)惠的措施或合同。

基于以上考慮，本文研究購買價格遞減的在線租賃問題：設(shè)某用戶或投資者要租用或購買某種設(shè)備進行生產(chǎn)。如果租用設(shè)備每個租用期的租金是1；如果購買設(shè)備，隨著租用期數(shù)t的增加，購買價格等比例遞減為(1-ρ)t-1s，即若在第一期購買則價格是s，若第一期租用再第二期購買則價格是(1-ρ)s，…… 若前n-1期租用到第n期購買則價格是(1-ρ)n-1s，0<ρ<1/e叫購買價格的優(yōu)惠率。一旦投資者在某一期買下了設(shè)備就不必再付租用費。但投資者不知道自己將要使用這種設(shè)備多長時間，即使用期數(shù)t1,t2,…,tn是長度n不確定的租用期構(gòu)成的時間序列。

如果ρ=0，則這一問題退化為Karp模型，因此我們考慮的購買價格遞減的在線租賃問題是Karp模型的一種推廣。

在本文中，像文獻[4]等其它研究在線租賃問題的文獻一樣，我們約定s、t*和s*等參數(shù)都是正整數(shù)且s≥2。有關(guān)在線問題與在線算法的方法和術(shù)語我們參閱文獻[13,14]。

1費用函數(shù)的性質(zhì)

我們知道，對于原Karp在線租賃問題，無論投資者在租賃期內(nèi)哪一期購買設(shè)備，購買價格恒為常數(shù)s；而且最優(yōu)離線策略是當n

f(t)=t-1+(1-ρ)t-1s

(1)

與在租賃期內(nèi)，從第一期租用設(shè)備直到t期結(jié)束所花費用的函數(shù)

g(t)=t

(2)

等費用函數(shù)的性質(zhì)。這里1≤t≤n，并且先不妨假定優(yōu)惠率0<ρ<1。

設(shè)F(t)=t-1+(1-ρ)t-1s-t，通過F(t)考察易知函數(shù)f(t)與g(t)在

(3)

處取得相等的函數(shù)值，并且當1≤tg(t)，當T

把(1)式對t求導(dǎo)并令其等于零得關(guān)于t的方程

f′(t)=1+(1-ρ)t-1sln(1-ρ)=0

(4)

解得其根

(5)

由于t*是方程(4)的根，所以

f″(t*)=(1-ρ)t*-1sln(1-ρ)·ln(1-ρ)=-ln(1-ρ)>0

因此，我們令

f(t*)=t*-1+(1-ρ)t*-1s

圖1　當0< ρ≤1- 時費用函數(shù)的性態(tài)

圖2　當1- < ρ<1- 時費用函數(shù)的性態(tài)

如果我們令s*=f(t*)，則有s*

把(5)式兩邊對ρ求導(dǎo)得

(6)

由(3)和(5)可知

(7)

2最優(yōu)離線策略

雖然該問題所對應(yīng)的離線問題的租賃時間序列t1,t2,…,tn的長度n是已知的，但最優(yōu)離線策略與購買價格的優(yōu)惠率密切相關(guān)。事實上，最優(yōu)離線決策必然是根據(jù)已知n的大小分以下兩種情況之一作出的：

(i)當n較小時，總是租用；(ii)當n較大時，租用t-1次然后買入，其中1≤t≤n(當t=1時，就是一開始購買)。

(i)當n較小時，總是租用。在這種情況下，投資者花費的租用金總額是租用函數(shù)g(t)=t當t=n時的函數(shù)值，即g(n)=n。

(ii)當n較大時，租用t-1次然后買入，其中1≤t≤n。在這種情況下，投資者花費的資金總額是f(t)=t-1+(1-ρ)t-1s。

下面，我們來討論(i)(ii)兩種情況中的臨界值及(ii)中t的取值。

因此，此時最優(yōu)離線策略是當n

因此，此時最優(yōu)離線策略是當n

通過上面的分析，如果用COPT(n)表示最優(yōu)離線策略的花費，我們可得到下面的定理1。

定理1對于購買價格以優(yōu)惠率ρ(0<ρ<1-e-1)等比遞減的在線租賃問題，有

3最優(yōu)在線策略

在本節(jié)中，我們討論購買價格以優(yōu)惠率ρ(0<ρ<1-e-1)等比遞減的在線租賃問題的最優(yōu)在線策略。

我們給出下面的在線策略Sρ并分析其競爭比、證明最優(yōu)性。

在線策略Sρ：對于購買價格以優(yōu)惠率ρ(0<ρ<1-e-1)等比遞減的在線租賃問題，根據(jù)ρ的大、小分以下兩種情況：

定理2對于購買價格以優(yōu)惠率ρ(0<ρ<1-e-1)等比遞減的在線租賃問題，在線策略Sρ的競爭比

綜合以上討論可知，策略Sρ的競爭比R在區(qū)間(0,1-e-1)上是ρ的連續(xù)且嚴格單調(diào)減函數(shù)。

推論1證畢。

定理3對于購買價格以優(yōu)惠率ρ(0<ρ<1-e-1)等比遞減的在線租賃問題，在線策略Sρ是該問題唯一最優(yōu)策略。

(1)對于任意使用時間實例t1,t2,…,tn，策略S′每一期都租用設(shè)備。

(2)對于任意使用時間實例t1,t2,…,tn，策略S′一開始就購買設(shè)備。

令n=1，則策略S′所花費用為s，最優(yōu)離線策略所花費用為1，因此

(3)對于任意使用時間實例t1,t2,…,tn，策略S′租用設(shè)備t-1期后在t期購買設(shè)備，其中0

令n=t，由于t

(4)對于任意使用時間實例t1,t2,…,tn，策略S′租用設(shè)備t-1后在t期購買設(shè)備，其中t>s*。

令n=t，則策略S′所花費用為t-1+(1-ρ)t-1s，最優(yōu)離線策略所花費用為s*=t*-1+(1-ρ)t*-1s。由于t>s*>t*時，函數(shù)f(t)=t-1+(1-ρ)t-1s為增函數(shù)，因此

定理3證畢。

4小結(jié)

經(jīng)典的在線租賃研究是基于Karp提出的租雪橇模型，一般都是在假定購買價格保持恒定不變的情況下考慮問題的。考慮到現(xiàn)實經(jīng)濟活動中一些設(shè)備的購買價格是隨著供求關(guān)系不斷發(fā)生變化的，本文考慮了購買價格遞減的在線租賃問題。雖然當購買價格呈等比遞減趨勢下降時，在線租賃的模型比原Karp模型復(fù)雜化，但我們針對購買價格等比遞減的特征給出的最優(yōu)在線策略具有更小的競爭比。從原Karp模型的競爭比2-1/s下降到R=1+[(1-ρ)s*-1s-1]/s*，而且R是ρ在區(qū)間(0,1-e-1)上的連續(xù)且嚴格單調(diào)減函數(shù)，并有1

參考文獻：

[1]Karp R. On-line algorithms versus off-line algorithms: how much is it worth to know the future?[C]. Proc. IFIP 12th World computer congress. The Netherlands: North-Holland Publishing Co., 1992, 1: 416-429.

[2]Karlin A R, Manaees M S, McGeogh L, Owichi S. Competitive randomize algorithms for non-uniform problems[J]. Algorithmica, 1994, 11(6): 542-571.

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

[4]El-Yaniv R, Kaniel R, Linial N. Competitive optimal oline leasing[J]. Algorithmica, 1999, 25: 116-140.

[5]Irani S, Ramanathan D. The problem of renting versus buying[Z]. Personal communication, 1998.

[6]Azar Y, et al. On capital investment[J]. Algorithmica, 1999, 25: 22-36.

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

[8]Xu Y F, Xu W J, Li H Y. On the online rent or buy problem in probabilistic environments[J]. Journal of Global Optimization, 2007, 38(1): 1-20.

[9]王揚,徐維軍,徐寅峰.一類占線融資租賃問題的最優(yōu)競爭策略與風(fēng)險補償模型[J].管理學(xué)報，2011，8(12)：1866-1871.

[10]董玉成，徐寅峰，徐維軍.可退貨在線租賃競爭分析及其風(fēng)險回報模型[J].中國管理科學(xué)，2007，15(4)：28-33.

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

[12]徐維軍，張衛(wèi)國，胡茂林.購買價格和租金費用均連續(xù)可變的在線競爭策略分析[J].中國管理科學(xué)，2006，14(2)：96-101.

[13]堵丁柱.k-車服務(wù)問題與競爭算法[J].數(shù)學(xué)的實踐與認識，1991，(4)：36-40.

[14]馬衛(wèi)民，王刊良.局內(nèi)管理決策問題及其競爭策略[J].管理科學(xué)學(xué)報，2003，6(2)：29-34.