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

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

胡茂林1，徐維軍2

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

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

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

收稿日期：2012-12-24

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(71471065)；教育部人文社會(huì)科學(xué)研究規(guī)劃基金(10YJA630062)；中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金資助(2012ZZ0035)

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

中圖分類號(hào)：F224.0 文章標(biāo)識(shí)碼：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引言

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

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

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

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

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

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

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

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

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

(1)

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

g(t)=t

(2)

等費(fèi)用函數(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ù)值，并且當(dāng)1≤tg(t)，當(dāng)T

把(1)式對(duì)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　當(dāng)0< ρ≤1- 時(shí)費(fèi)用函數(shù)的性態(tài)

圖2　當(dāng)1- < ρ<1- 時(shí)費(fèi)用函數(shù)的性態(tài)

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

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

(6)

由(3)和(5)可知

(7)

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

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

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

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

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

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

因此，此時(shí)最優(yōu)離線策略是當(dāng)n

因此，此時(shí)最優(yōu)離線策略是當(dāng)n

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

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

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

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

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

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

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

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

推論1證畢。

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

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

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

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

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

令n=t，由于t

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

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

定理3證畢。

4小結(jié)

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

參考文獻(xiàn)：

[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áng),徐維軍,徐寅峰.一類占線融資租賃問題的最優(yōu)競(jìng)爭(zhēng)策略與風(fēng)險(xiǎn)補(bǔ)償模型[J].管理學(xué)報(bào)，2011，8(12)：1866-1871.

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

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

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

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

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