程玲燕，何世偉

（北京交通大學(xué)運輸學(xué)院，北京　100044）

購價租金降低下賃購平衡在線策略的最優(yōu)性分析

程玲燕，何世偉

（北京交通大學(xué)運輸學(xué)院，北京100044）

摘要：證明了在購價與租金隨時間降低，且決策時間未定的情況下，獲得具有上界為2的最小競爭比的近似最優(yōu)在線策略，即僅當(dāng)實時購買價格與已累積租金額的數(shù)量關(guān)系為相等時選擇購買。該研究分別針對購價租金恒定與一般情形兩種情況下，不同的市場崩潰時間與設(shè)備購買時間的先后關(guān)系、購買價格與累計租金的數(shù)量關(guān)系進行了分析論證，為賃購平衡策略在現(xiàn)實租買決策中的應(yīng)用提供了理論依據(jù)。

關(guān)鍵詞：在線算法；在線租賃；賃購平衡策略；競爭比

相較于傳統(tǒng)的決策優(yōu)化方法，在線（On-line，也稱占線、局內(nèi)）算法與競爭比分析方法為在線租賃問題提供了尋求概率意義上的最優(yōu)決策新視角。其中，在設(shè)備購買價格與租金為單調(diào)遞減序列的在線問題中，賃購平衡策略（renting-buyingbalancestrategy）是學(xué)者們提出的一種較為普遍且實際易執(zhí)行的在線策略?，F(xiàn)階段，對于不確定情形下租或買的決策研究，國內(nèi)外相關(guān)的研究方向主要為在線算法與競爭分析方法，其研究始于Karp［1］1992年提出的“SkiRentalProblem模型”，該模型假設(shè)滑雪初學(xué)者不知道自己會滑雪多少次，因此，每次滑雪時都面臨兩種選擇：花費c成本租滑雪撬，或者花費P成本一次性購買雪撬。Karp給出了競爭比為2-c/P的最優(yōu)確定性競爭策略。這類具有非常強的動態(tài)特征的租賃問題稱為在線租賃問題，實質(zhì)在于在線人一直采取租賃策略直到某一時刻點采取購買策略使該決策結(jié)束。隨后，很多學(xué)者結(jié)合現(xiàn)實租賃問題，對該基本模型進行了擴展研究，主要思路有兩種。一種思路是將基本租賃模型推廣應(yīng)用到其他現(xiàn)實問題中，如Fleischer［2］提出的占線優(yōu)惠卡（Bahncard）模型；Al-Binali［3］把在線決策者的風(fēng)險行為引入傳統(tǒng)競爭分析，建立了風(fēng)險補償模型；Karlin等［4］將租賃模型應(yīng)用于傳輸控制協(xié)議（TCP）問題；2004年朱志軍等［5］給出了一般設(shè)備租賃問題的風(fēng)險補償模型；辛春林等［6］、丁黎黎等［7］將風(fēng)險補償概念應(yīng)用于優(yōu)惠卡模型，并進行了相應(yīng)的擴展研究；徐寅峰等［8］從收益率的角度，對實際問題進行了研究，并討論了基于風(fēng)險補償模型的風(fēng)險補償收益。另一種思路是對原模型的假設(shè)進行修正，改善決策者的決策信息，得到更優(yōu)的競爭比，如Karlin等［9］討論了未來需求為隨機變量的租賃問題，給出了隨機在線算法，使競爭比達到了約1.582，近似最優(yōu)；Irani等［10］研究了購買價格波動而租賃費用保持不變的情形，分別給出了確定性和隨機性算法的競爭比上下界，還第一次運用具有統(tǒng)計特征對象，即限定未來價格波動滿足一定條件來研究租賃問題；El-Yaniv等［11］考慮了存在利率時的在線租賃問題，給出了最優(yōu)確定性算法（其競爭比大小在［3/2，2）之內(nèi)）及最優(yōu)隨機性算法（其競爭比大小在［4/3，1.582）之內(nèi)）；隨后，F(xiàn)ujiwara等［12］結(jié)合指數(shù)分布概率信息研究了連續(xù)型在線租賃決策問題，并說明了競爭比大約在1.5左右；馬衛(wèi)民等［13］研究了租賃價格可變情形的連續(xù)型在線租賃問題；Lotker等［14］在前人研究的基礎(chǔ)上對基本租賃模型進行了擴展，提出了“MuhislopeSkiRentalProblem”的模型，在該模型中，決策者不僅是“純粹的買或租”的選擇，而是在花費一定購置費的基礎(chǔ)上，在不同階段使用設(shè)備還要花費一定比例的使用費；張永等［15］在研究了設(shè)備價格呈離散型下降的在線租賃策略后，給出了其策略的競爭比上界；劉斌等［16］研究了具有線性交易成本的耐用性設(shè)備的在線租賃問題，假定在設(shè)備壽命周期內(nèi)，使用時間結(jié)束后可以進行二手交易來降低使用成本。徐維軍等［17］結(jié)合輸入結(jié)構(gòu)的分布信息研究了離散型在線租賃問題，建立了最優(yōu)的離散型在線租賃決策模型，并給出了實際問題的精確解。

關(guān)于在線租賃策略研究，已有的成果主要是研究者在特定的條件下，根據(jù)自己的合理假設(shè)或推論構(gòu)建在線策略，并得出其競爭比，以此得到某一類在線策略的合理性。其中，在購價租金連續(xù)下降型問題上，馬衛(wèi)民等［13］、張永等［15］學(xué)者均在設(shè)備購買價格下降的情況下提出賃購平衡策略，即購買價格與累積租賃費用相等時選擇購買策略。該策略中累積租金與購買價格成比例關(guān)系，且具有競爭比上界2。而在購買價格與租金連續(xù)下降的情況下，在線人依據(jù)累積租金與購買價格具備數(shù)量關(guān)系的前提下作決策時，為何兩者相等而非其他的數(shù)量關(guān)系是具有最小競爭比的最優(yōu)策略，學(xué)者們沒有相關(guān)的探討與證明。本文則在購價租金在較大時間單位內(nèi)（如季度、年）隨著市場一般規(guī)律降低的情況下，證明了賃購平衡模型的最優(yōu)性，為其在實際租買決策中的應(yīng)用中提供了清晰的理論證明。

1　問題描述與基本假設(shè)

在傳統(tǒng)競爭分析［3］中，存在著一個供決策者選擇的策略集S和一個離線對手發(fā)出的序列集I。在線決策者的目的就是設(shè)計一個好的策略A∈S以應(yīng)對離線對手可能發(fā)出不確定的輸入序列σ∈I。競爭分析方法與以往解決此類問題方法的最大區(qū)別在于：它在變化因素的每一個特例中都能給出一個方案，使得這一方案所得到的解與最優(yōu)方案給出的解總在一定的比例之內(nèi)，從而使在線問題的解始終保持在一個較優(yōu)的狀態(tài)。在線算法中，決策者在事先不完全知道的情況下設(shè)計在線策略與事先完全知道未來信息時的最優(yōu)離線策略進行比較。即，根據(jù)在線問題的競爭分析理論［18］，對在線策略A以及任何有限的輸入序列σ，假定CostON（σ）為在線策略A的費用，CostOPT（σ）為最優(yōu)離線策略的費用，如果存在一個常數(shù)c，使得

則稱此在線策略具有競爭比c，或稱在線策略A為c競爭策略，顯然c≥1。競爭比的大小反映在線策略的性能，競爭比越小，在線策略性能越好。

某企業(yè)在市場前景無法預(yù)知的情形下，需要使用某種設(shè)備，則可知該企業(yè)有兩種方案可以選擇：

（i）租賃設(shè)備。租賃費用定義為一個在非負整數(shù)N上的序列｛r（t）｝，表示第t期的租賃費用；

（ii）一次購買設(shè)備。購買設(shè)備的費用類似地定義為一個在非負整數(shù)N上的序列｛p（t）｝，表示在第t期購買該設(shè)備的費用。

由于購買價格p（t）與租賃價格r（t）都是隨著市場規(guī)律而變化的，在較小的時間維度內(nèi)（如日、月）可能上下波動，不存在顯著的降低特征；但是在較大的時間單位內(nèi)（如季度、年），上兩者隨著市場的技術(shù)發(fā)展、新產(chǎn)品競爭等關(guān)系較大概率上會呈現(xiàn)出下降趨勢，這也是本文研究的現(xiàn)實意義所在。故這里假設(shè)r（t）為單調(diào)遞減序列，即邊際租賃費用隨著租賃時間的增加而越少。p（t）為單調(diào)遞減序列，且p（t）＞＞r（t），即任何時候的購買費用都遠遠大于當(dāng)前的租賃費用。任何時間段（i，j）（i＜j，i，j＞0）內(nèi)設(shè)備降價幅度小于這段時間內(nèi)設(shè)備租賃費用的累計值，即，否則在線設(shè)備投資者將不會選擇購買設(shè)備策略。

購買價格和租賃費用都是隨著時間而不斷變化的連續(xù)函數(shù)。假設(shè)設(shè)備使用時期為［0，T］，記T為市場崩潰時期（CrashingTime），這與未知的市場需要相關(guān)，第T期之后不再使用該設(shè)備。T已知則為離線問題，CostOPT（T）為離線策略的最優(yōu)費用；若T未知則為在線問題，CostON（T）為在線策略的費用。而在離線問題中，由于T以及設(shè)備購買價格、租賃費用變化情況均為已知，因而決策問題衍化為一個簡單數(shù)學(xué)問題：到崩潰時刻第T期為止，若，則從一開始就租賃設(shè)備；反之，若則選擇購買策略。

2　在線最優(yōu)策略證明

由假設(shè)可知，當(dāng)設(shè)備使用時間（即市場崩潰時期）T、購買設(shè)備的時期t購買價格及租金信息未知時，在線策略的費用CostON（T）滿足下述公式：

即，當(dāng)市場崩潰時期T早于購買設(shè)備時期t時，在線策略費用為至T時期的累計租賃費用；當(dāng)市場崩潰時期T晚于購買設(shè)備時刻t時，在線策略費用為至第T期的累計租賃費用與在t期設(shè)備的購買價格的總和。

2.1購價租金恒定

首先討論比較特殊的購價租金恒定的情況，可以看作是遞減速率為0的單調(diào)遞減函數(shù)，可以假定賦值p（t）≡P0。這種情況下的離線最優(yōu)費用為：

其中，x是大于0的實數(shù)參數(shù)。不難發(fā)現(xiàn)，對于t＜t

1

，不等式

成立；對于t＞t

1

，則

成立。在這種情況下，有如下定理：

定理1當(dāng)累積租賃費用與購買費用相等時購買策略具有最小的競爭比2［13］。

證明由于崩潰時期T未知，所以分兩種情況來證明：

情況1T＜t1。因為第t1期還未到來設(shè)備已無需使用，因此購買策略不會發(fā)生，得到競爭比：

可視為離線策略。

情況2T≥t1。易知。租賃設(shè)備至第t1期，然后購買設(shè)備。x取值不同，在線策略的選擇也有區(qū)別，故按x的不同取值計算其競爭比：

（1）x＞1，即在線策略為當(dāng)累積租賃費用大于購買價格x倍時選擇購買設(shè)備，則顯然離線最優(yōu)策略為一開始就購買設(shè)備。此時的競爭比為：

因為x＞1，所以競爭比為x無限取1時得到最小值2。

（2）x≤1，即在線策略為當(dāng)累積租賃費用小于購買價格x倍時選擇購買設(shè)備，由于崩潰時間T的未知，此時離線最優(yōu)策略又分為兩種情況：

i.購買設(shè)備，此時的競爭比為：

因為x＜1，所以競爭比為x無限取0時最小，即在線策略為一開始就購買設(shè)備，這種購買時刻確定的策略也就不能稱之為在線策略，為無效在線策略。

ii.租賃設(shè)備，此時的競爭比為：

因為x≤1，所以競爭比當(dāng)x＝1時取到最小值2。

綜上所述，當(dāng)x＝1，即累積費用與購買費用相等時競爭比最小，得其上界為2，即在線策略的競爭力最強。事實上，在實際經(jīng)濟活動中可能并不會出現(xiàn)某一期結(jié)束時累積租金恰好等于當(dāng)期的購買價格，這里不妨近似為當(dāng)購買價格與累積租賃費用的正差額最小的時候選擇購買策略。

定理1得證，即在購價租金恒定的情況下，若在線策略為購價與累積租金成正比，則兩者相等，即賃購平衡時達到最小競爭比。

2.2一般情形

當(dāng)設(shè)備的購價租金根據(jù)市場一般規(guī)律降低時，同樣設(shè)計如下策略：租賃設(shè)備至第t1期然后購買設(shè)備，其中t1滿足下式：

易得，對于t＜t1，不等式

成立；對于t＞t1，則成立。在這種情況下，有如下定理：

定理2當(dāng)累積租賃費用與當(dāng)時購買費用相等時購買策略具有最小的競爭比2［13］。

證明由于崩潰時期T未知，所以分兩種情況來證明：

情況1T＜t1。因為第t1期還未到來設(shè)備已無需再使用，因此在線決策者不會選擇購買策略，得到競爭比：

可視為離線策略。

情況2t1≤T≤t2。其中假定t2滿足。易知，按照不同x取值計算其競爭比：

（1）x＞1，即在線策略為當(dāng)累積租賃費用大于當(dāng)時購買價格x倍時選擇購買設(shè)備，則顯然離線最優(yōu)策略為一開始就購買設(shè)備。此時的競爭比為：

因為x＞1，所以競爭比為x無限取1時得到最小值2。

（2）x≤1，即在線策略為當(dāng)累積租賃費用小于當(dāng)時購買價格x倍時選擇購買設(shè)備，顯然此時離線最優(yōu)策略應(yīng)該為一開始就租賃設(shè)備，競爭比為：

因為x≤1，所以競爭比當(dāng)x＝1時取到最小值2。

（1）x＞1，即在線策略為當(dāng)累積租賃費用大于當(dāng)時購買價格x倍時購買設(shè)備，則顯然離線最優(yōu)策略為一開始就購買設(shè)備。此時的競爭比為：

因為x＞1，所以競爭比為x無限取1時得到最小值2。

（2）x≤1，即在線策略為當(dāng)累積租賃費用小于當(dāng)時購買價格x倍時購買設(shè)備，由于崩潰時間T的未知，此時離線最優(yōu)策略又分為兩種情況：

i.購買設(shè)備，此時的競爭比為：

因為x≤1，所以競爭比為x無限取0時最小，即在線策略為一開始就購買設(shè)備，但是這種購買時刻確定的策略也就不能稱之為在線策略，為無效在線策略。

ii.租賃設(shè)備，此時的競爭比為：

因為x≤1，所以競爭比當(dāng)x＝1時取到最小值2。

綜上所述，當(dāng)x＝1，即累積費用與當(dāng)時購買費用相等時競爭比為2，在線策略的競爭力最強。事實上，在實際中可能并不會出現(xiàn)某一期累積租金恰好等于當(dāng)期的購買價格。這里不妨近似為當(dāng)時購買價格與累積租賃費用的正差額最小的時候選擇購買策略。

定理2得證。即在購價租金降低的情況下，若在線策略為當(dāng)購價與累積租金成不確定性比例關(guān)系，則兩者相等，即賃購平衡時達到最小競爭比。

由上述的證明可得，在購買價格恒定和一般購價租金遞減的情形下，購買價格與累積租賃費相等（實際中可采用正差額最?。r選擇購買策略是最具競爭力的在線策略，即t1滿足實際中可采用，此策略稱為租賃購買平衡策略（近似平衡），也可簡稱為賃購平衡策略［13］，采取購買策略的時刻稱之為費用平衡點。

3　結(jié)語

在線設(shè)備租買是現(xiàn)實中在線決策者們面臨的重要問題，也是在線算法與競爭比方法著重研究的方向。根據(jù)市場競爭的正常規(guī)律，購買價格與租金在較大時間單位內(nèi)隨時間降低的可能性很大。本文在此假設(shè)下，利用在線算法及競爭比，證明了賃購平衡策略（近似），即實時購買價格與累積租賃費用相等（實際中可為正差額最?。r選擇購買策略是最具競爭力的在線策略，并得出賃購平衡策略的競爭比上界。而本文只證明了在無利率情況下賃購平衡策略的最優(yōu)性，卻沒有考慮利率情況下此策略的合理性與最優(yōu)性。另外，現(xiàn)實生活中設(shè)備購買價格與租金的波動情況遠不止單調(diào)遞減，而購價與累積租金之間存在比例關(guān)系也是一個比較理想的假設(shè)。如何在更加復(fù)雜的情況下，將購價、租金、利率、折舊、風(fēng)險補償以及通貨膨脹等因素一并加以考慮，研究出更加合理、現(xiàn)實的在線策略，有待于今后進一步的探討研究。

參考文獻：

［1］KARPRm.Onlinealgorithmsversusofflinealgorithms：Howmuchisitworthtoknowthefuture［M］//Proc.IFIP12thWorldComputerCongress.Amsterdam，Netherlands：North-HollandPublishingCo.，1992：416-429.

［2］FLEISCHERR.Onthebahncardproblem［J］.TheoreticalComputerScience，2001，268（1）：161－174.

［3］AL-BINALIS.Arisk-rewardframeworkforthecompetitiveanalysisoffinancialgames［J］.Algorithmica，1999，25（1）：99－115.

［4］KARLINAR，KENYONC，RANDALLD.DynamicTCPacknowledgmentandotherstoriesaboute/（e-1）［J］.Algorithmica，2003，36（3）：209－224.

［5］朱志軍，徐寅峰，徐維軍.局內(nèi)租賃問題的風(fēng)險補償模型及其競爭分析［J］.管理科學(xué)學(xué)報，2004，7（3）：64－68.

［6］辛春林，徐寅峰，衣方磊.基于預(yù)期的占線特殊優(yōu)惠卡問題與競爭分析［J］.管理工程學(xué)報，2007，21（4）：14－18.

［7］丁黎黎，康旺霖.占線Bahncard問題的風(fēng)險補償模型［J］.管理科學(xué)學(xué)報，2008，11（4）：38－43.

［8］徐寅峰，徐維軍，盧致杰.存在市場利率條件下的占線租賃策略研究［J］.系統(tǒng)工程，2005，23（3）：29－34.

［9］KARLINAR，MANAEESmS，McGEOGHLA，etal.Competitiverandomizedalgorithmsfornon-uniformproblem［EB/OL］.［2015-07-12］.https：//www.researchgate.net/publication/220780194＿Competitive＿Randomized＿Algorithms＿for＿Non-Uniform＿Problems.

［10］IRANIS，RAMANATHAND.Theproblemofrentingversusbuying［EB/OL］.［2015-07-12］.http：//citeseerx.ist.psu.edu/viewdoc/download？doi＝10.1.1.44.8179＆amp%3Brep＝rep1＆amp%3Btype＝pdf＆origin＝publication＿detail.

［11］EL-YANIVR，KANIELR，LINIALN.Competitiveoptimalon-lineleasing［J］.Algorithmica，1999，25（1）：116-140.

［12］FUJIWARAH，IWAMAK.Average-casecompetitiveanalysesforski-rentalproblems［J］.Algorithmica，2005，42（1）：95－107.

［13］馬衛(wèi)民，陳國青.價格連續(xù)型局內(nèi)設(shè)備賃購問題的競爭分析［J］.系統(tǒng)工程理論與實踐，2006（4）：90－96.

［14］LOTKERZ，PATT-SHAMIRB，RAWITZD.Rent，leaseorbuy：randomizedalgorithmsformultislopeskirental［EB/OL］.［2015－07－12］.https：//www.researchgate.net/publication/220994403＿Rent＿Lease＿or＿Buy＿Randomized＿Algorithms＿for＿Multislope＿Ski＿Rental.

［15］張永，張衛(wèi)國，徐維軍.設(shè)備購買價格可變的確定性在線租賃策略［J］.系統(tǒng)工程，2009，27（11）：52－55.

［16］劉斌，辛春林，崔文田.具有線性交易成本的耐用性設(shè)備在線租賃策略分析［J］.管理學(xué)報，2011，8（10）：1549－1552.

［17］徐維軍，徐寅峰，盧致杰.具有幾何分布統(tǒng)計特征的在線租賃競爭分析［J］.預(yù)測，2005，24（2）：46－51.

［18］SLEATORDD，TARJANRE.Amortizedefficiencyoflistupdateandpagingrules［J］.CommunicationsoftheACM，1985，28（2）：202－208.

Optimalityanalysisofrenting-buyingbalanceonlinestrategyfordecreaseofpriceandrent

CHENGLing-yan，HEShi-wei

（SchoolofTrafficandTransportation，BeijingJiaotongUniversity，Beijing100044，China）

Abstract：Weprovethatbuyingstrategyshouldbeappliedonlyifreal-timepriceequalstoaccumulatedrentamounttoobtainapproximatelyoptimalonlinestrategywiththesmallestcompetitiveratiowhoseupper-boundis2underthedecreaseofpurchasepriceandrentwithtimeandindefinitedecisiontime.Weanalyzeserialrelationshipbetweendifferentmarketcrushingtimeandequipmentbuyingtimeandquantitativerelationshipbetweenpurchasepriceandaccumulatedrentforsuchtwocasesasconstantpriceandrentandgeneralsituation.Ourconclusionwillprovideatheoreticalreferencefortheapplicationofrenting-buyingbalancestrategyinpracticalrent-buydecision.

Keywords：onlinealgorithm；onlineleasing；renting-buyingbalancestrategy；competitiveratio

中圖分類號：U294.1；TB114.1

文獻標(biāo)識碼：A

文章編號：1002-4026（2016）01-0076-07

DOI：10.3976/j.issn.1002－4026.2016.01.013

收稿日期：2015-11-03

基金項目：中國鐵路總公司科技研究開發(fā)計劃（2014X010-D）

作者簡介：程玲燕（1992－），女，碩士研究生，研究方向為在線租買決策、運輸組織現(xiàn)代化等。Email：13120824＠bjtu.edu.cn