论文研究-离散型两斜率在线租赁问题.pdf,  两斜率在线租赁问题是经典的在线租赁问题的一种自然的推广.基于在线租赁问题的研究分为离散时间和连续时间，鉴于已有文献对连续时间情况下两斜率在线租赁问题进行了讨论，本文研究离散时间情况下两斜率在线租赁问题.我们的讨论包括确定性竞争策略和随机性在线策略.关于确定性策略，一个竞争因数为2-[1 （s-1）a]/s的最优策略被给出.对于随机性策略，本文提
1682 系统工程理论与实践 第39卷 离散型两斜率在线租赁问题:一在线投资者需租赁某种价值为s的设备进行生产经营活动,但不知道生 产经营活动能持续多少个租赁期,即租赁设备的时间T1,T2,…,Tn是长度n不确定的租用期构成的时间序 列.他/她租赁设备有以下两种租赁方式: Slope1:租赁没备的租赁费用以每个租赁期1单位货币按租赁期 数的多少累加计算. Slope2:先付部分租约金(1-a)s再以每个租赁期a单位货币按租赁期数的多少累加 计算租赁费而租赁雪橇,其中0≤a<1,我们称其为租约系数.面对不确定的租赁期数n,在线投资者是按 Slope1租赁设备还是按 Slope2租赁设备或是按 Slope1租赁设备一段时间后再转换到 Slope2租赁设备 到活动结束最为划算? 为了方便,我们有时将如上定义的离散型两斜率在线租赁问题简记为( Slope1, Slope2).显然,在离散 型两斜率在线租赁问题中,若租约系数a=0,则这一问题退化为经典的在线租赁问题 作为离散型两斜率在线租赁问题( Slope1, Slope2),若按 Slope1租赁设备,则租赁成本C1(mn)=n;若 按Sope2租赁设备,则租赁成本C2(m)=(1-m)s+mm.按 Slope1租赁设备的成本函数C1t)=t与按 Slope2租赁设备的成本函数C2(t)=(1-a)s+at在t=s处相交.类似于经典的在线租赁问题,这个父点 t=s是离散型两斜率在线租赁间题( Slope I, Slope2)最优离线策略作出一开始就按Sope⊥租赁设备还是 按 Slope2租赁设备的关键时间转换点.因此,离散型两斜礻在线租赁问题( Slope1, Slope2)最优离线策略 如下 最优离线策略:对于离散型两斜率在线租赁冋题(Sope1,Sope2),其最优离线策略是当η<δ时按 lpe1租赁设备,当m≥s时按 Slope2租赁设备,即最优离线成本 n CoPT (1-a)s+am,m≥8 其中,0<a<1,s≥2 3最优确定性在线策略及其竞争比 下面先给出(Sope1, Slope2)的一个确定性在线策略S,然后再求其竞争比并证明最优性 确定性在线策略S:对于离散型两斜率在线租赁问题( Slope1, Slope2),只要活动在持续,在线人在前 s-1期每一期都按 Slope1租赁设备,到了第s期再转而按Sope2租赁设备 定理1对于离散型两斜率在线租赁间题(Sope1, Slope2),确定性在线策略S的竞争比为 R=2 1+(s-1)a 其中,0<a<1,s>2 证明1)如果η<s,则最优离线策略与在线策略S都是按 Slope1租赁设备直到n期结束,而且二者 的成本都等于n,即Cop=Cs=t.于是当n<s时 C 2)如果η≥s时,最优离线策略从一开始就按 Slope2租赁设备直到n期结束,其成本为CoPr (1-α)s+αmη.而在线策略S是先按Slp1租赁设备到s-1期结束,到了第s期再转而按 Slope2租赁 设备直到m期结束,其总成本为CS=8-1+(1-a)s+a(m-s+1).于是, s-1+(1-a)s+a(m-s+1) (s-1)(1-a) (1-a)s+an (1-as+an 由(1)式可见在线策略S的最坏情形是n=s,于是 (1-a)8+31 (s-1)(1-a) + sup C OPT 综合1)和2)两种情形,可知策略S的竞争比是 1+(s-1a R=2 定理1证毕 下面证明在线策略S是该问题最优策略,即下面的定理2. 第7期 胡茂林,等:离散型两斜率在线租赁问题 1683 定理2对于离散型两斜率在线租赁间题( Slope1, Slope2)在线策略S的竞争比是该问题最优竞争比 证明设S′是该问题任意一个不同于S的在线策略并以Bs记其竞争比.则S′与S的相异性表现在 以下四个方面: 1)对于不确定的租赁期数m,策略S′从活动开始一直按Sope1租赁设备直到n期结束. 取n=s2,则最优离线成本为(1-a)s+s2a=s1+(s-1)a],而策略S"的成本为s2.由 1+(s-1)a)_(-1)2(1 可知,对于任意的a∈0,1)及s≥2,有 +(s-1) Rs> 2)对于不确定的租赁期数η,策略S总是从活动开始就按 Slope2租赁设备直到n期结束 令仉=1,则最优离线策略成本为1,而策略S′的成木为(1-a)s+a.由 (1-a)s+a 1+(s-1)a(1-a)s 可知,对于任意的a∈0,1)及s≥2,有 (1-a)s+a +(S a Rs,> 3)对于不确定的租赁期数η,策略S′从廾始先按Sope1租赁设备到π期结束后从η+1期廾始雨按 ope2租赁设备直到n期结束,其中m∈N+且m<8-1 取n=m+1,由于m<s-1,则n≤s-1,因此,最优离线策略的成本为m+1,而策略S′的费用为 n+(1-a)s+a,故而对于任意的a∈0,1)及8≥2,有 m+(1-a)s+a s-1 Rs,> 1+ -1)-2-1+(8-1)a m+1 +1 4)对于不确定的租赁期数η,策略S″从开始先按 Slope1租赁设备到m期结束后从m+1期开始按 lope2租赁设备直到m期结束,其中m∈N+且m>s-1 由于m>8-1.则m≥s.令m=m+1,则n>8,于是最优离线策略的成本为(1-a)s+ma,而策略 S"所花费用为m+(1-a)s+a,因此,对于任意的a∈(0,1)及s≥2,有 m+(1-a)s+a1 1-a)2s-a 1-a)2s Rs≥ (1 a)s+ma (1-a)s+maa(1-a)s+sa >2-1+(8-1a 而当a-0时,有 m+s Rsi> 综合以上四种情况可知,在线策略S′只能得到比策略S的竞争比更大的竞争比,因此在线策略S是该 问题最优策略.定理2证毕. 推论1如果离散型两斜率在线租赁问题( Slope 1. Slope2)中的租约系数a=0,即经典的在线租赁间 题(离散型)的最优确定性策略是从开始租赁设备直到s-1期结東,到了第s期再购买设备,且其最优竞争 比为2-1 4最优随机性在线策略及其竞争比 本节考虑针对遗忘性竞争对手的最优随机性在线租赁策略.所谓随机性在线租赁策略就是对于每个正整 数j在确定性在线策略{S(j)}类上指定一个概率分布{p()}.在这里,对于每个正整数j,我们用( Slope1, Slope2)上的一个概率分布p(j)=(p1(j),p2()来描述一个随机性在线算法,其中p1(j)是在第j个租赁期 按 Slope1租赁设备的概率,p2(j)是在第j个租赁期按 Slope2租赁设备的概率.作为一个有效的随机性算 1.由2)可知,如果个在线策略先按Sope2租赁设备段吋间后再按 Slope1租赁设备直到n期结東,则这一策咯只能获 得比策略S′的竞争比更大的竞争比 1684 系统工程理论与实践 第39卷 法,我们约定对于任意的正整数)P1(j)+p2(元)=1,而且期望租约金是可附加的,即,若在第j个租赁期的 期望租约金为(1-a)sP2(j),则在第j+1期只需附加期望租约金(1-a)l2(j+1)-p2(就可以以概率 p2(+1)沿 Slope2租赁设备.下面我们提岀针对遗忘性竟争对手的风险均衠策略(SBf)并证眀这一策略 是该问题最优随机性在线策略. 风险均衡策略(SB):对于离散型两斜率在线租赁问题( Slope1, Slope2), 1)预设一个目标竞争比R,在前S个租赁期每个n;的开始,若投资者仍需用设备,则考虑以合适的概 率p()沿 Slope2租赁设备.使得到了第j+1期离线对手突然发出不再需用设备的指令仍能保证日标竞 争比R以控制这种“突然停止”带来的风险; 2)由于当?≥8时,不论离线对手给出的m有多么的大,最优离线策略总是沿 Slope2租赁设备,其最 优离线成本的租约金都保持在常数(1-a).因此上作为随忛性在线策略,到了第s期后,为了确保目标竞 争比,其期望成本的租约金部分也应该维持在常数值,即p(s)=p2(s-1)=p2(s+2)= 定理3对于离散型两斜在线租赁问题(Sωpe1, Slope2),设风险均衡策略的目标竞争比是R,则在 每个租赁期以概率 (s-1) (1 P2() s-(s-1)(B-1),j≥S 沿 Slope2租用设备 证明根据风险均衡策略(SBF),只需证明当1<j<§时, P2()= 5 1-a)(s-1) (B-1) (2) 下面我们用数学归纳法证明上式在1<j≤s时成立 当1时,即在第1期η的开始,根据风险均衡策略,为了保证目标竞争比B,以防止在第2期 12及以后都不再需用设备的风险,则沿Sope2以概率p2(1)租赁设备而以概率1-m2(1)沿 Slope1租 赁设备的总的期望成本为1-m(1)+p2(1)(1-a)8+ap2(1),而最优离线花费为1,而且必须满足R 1=20)+2+,于是可得p21)=x-mkm(R-1),即命题对于j=1成立 现假定命题对于任意的j<k≤s成立,即当j<k≤s时 R-1) )(S 当jλ时,即在第k期⌒的开始,根据风险均衡策略.为了保证目标竞争比R,以防止在第k+1期 Ik+1及以后都不再需用设备的风险,则在沿 Slope2以概率p2(k)租赁设备而以概率1-2(k)沿 Slope1 租赁设备的总的期望成本为 1-p2(1)+1-p2(2)+…+1-p2(k)+P2(k)(1-a)s+ap2(1)+ap2(2)+…+ap2(h), 而最优离线花费为k而且必须满足 2(1)+1-P2(2)+…+1-p2(k)+P2(k)(1-a)s+ap2(1)+ap2(2)+…+ap2(k k 整理可得 (1-a)∑=1m2()+k(R-1) k) (1-a)(s-1) 由归纳假设之(3)式有 k-1 (1-a)(s-1) (R-1) (-1) R-1) (1-a)(8-1) (R-1) as y=1 (1-a)(s-1)(1-a)(s-1) (R-1) k-1)(s-1 (1-a)(s-1) 第7期 胡茂林,等:离散型两斜率在线租赁问题 1685 把(5)式代入(4)式可得 (1-a)(s-1)k (B-1) 由归纳法原理知(2)式对一切1<j<S的白然数j成立.定理3证毕 定理4对于离散型两斜率在线租赁问题( Slope1, Slope2),风险均衡策略的竞争比是 s-(1-a)(s-1)s 证明由定理3可知,对于任意的n>s ∑m()+(m-s)D2(s)=∑ S S (s-1) ns-(7+s)(s-1)°R-1 于是,策略SBR的期望成本为 ∑(1-m()+(n-s)(1-D2(s)+p(s)(1-a)s+∑a2()-(n-s)ap2() n+(1-a)2()-(1-a)∑n2()+(n-s)m2(s) (-n)3+n(s-1)° (-1) 而当m≥s时,最优离线策略的成本为(1-a)s+na,从而竞争比 分、m+(=n)s°+n(-1)(R-1) s-⊥ (1-a)s+na 由(6)式谷易解得 由风险均衡策略可知,上式对一切正整数n都成立.定理4证毕 推论2对于离散型两斜率在线租赁间题( Slope I,Sope2),风险均衡策略(SBR)在每个租赁期T ()沿 Slope1租赁设备的概率是 s83+a(s-1) (s-1)3 1<j≤ (1-a)(S-1) (i)沿Sope2租赁设备的概率是 s(s-1)3-(s-1)° P2(j) s9-(s-1),1≤j≤s (1-a)(s-1) 推论3对于离散型两斜率在线租赁问题(Sope1, Slope2),风险均衡策略(SBR)的竞争比随α在区 间0.1)上单调减,且当a=0时竞争比为 B=-(8-1) 推论4对于离散型两斜率在线租赁问题(Sope1, Slope2),风险均衡策略(SBR)的竞争比随8单调 增,且 e lim R= lim S→0 -(1-a)(s-1)se-1+a 定理5对于两斜率在线租赁问题(Sσpe1,Sloυe2)、风險均衡策略(SBR)是该冋题唯一最优策略. 1686 系统工程理论与实践 第39卷 证明设ALG是任意一个不同于SBR的随机性在线算法.下面我们证明算法ALG只能得到比R 更大的竞争比 设{m2(i)}:P2(1),m2(2),……,P2(s),p2(s+1),…是策略SBR实现它的竞争比R时在各租赁期沿 Slope 2租赁设备的概率分布,其中p2(s)=p2(5+1)=…令{n2(i)}:p2(1),n2(2),……,D2(s),p2(s+1),……是算 法ALG在各租赁期沿 Slope2租赁设备的概率分布.由期望租约金的可附加性可知这两个概率分布有以下 性质: 2(1)≤2(2)≤…≤2(8)=m2(s+1)=m2(+2)= p2(1)≤2(2)<…<n2(s)<2(s+1)<m2(s+2)< 由于算法ALG不同于策略SBR,故两个分布列的对应项必不完全相同,记1=min{l2()≠p(1)} 1)如果n2(10)>m2(10),则令n=0,于是有 1(1-n2()+1-m2()+ =)()+>=1mn()+m2(0 OPT j-(1-a)∑12p2()+(1-a)(s-1)p2(i COPT 而 (1-a)∑/1p2(i)+(1-a)(s-1)m2(jo) OPT 从而有 (1-a)(s-1)p2(0)-p2(0)>0 2)如果p2(i)<p2(0),则由概率分布{p2()}与{2(i)}的性质(⑦)与(8)可知j≤s,不妨设j 21)如果自第j=5项后{n2(j)}中存在某些项大于或等于{p2(j)}中的对应项,则令 1 nin{1n2()>p2(),l>8},并由 >-(1-0)>:=1()-(1-0)=p41)+(1-o)(8-1)p0n) 和 段=-(1-)>2()-(1-)>()+(1-)(-1)(i 有 r-R≥-∑(2()-m()+(-1(n(n)-=m2)|>0 22)如果对一切l>s,都有p2()<p2(),则令n=2并由 S 1)∑江1m2(i)-(1-a) p2(i)+(1-a)(8-1)m2(2s) 和 28- 2s-1 ()+(1-a)(s-1)p2(2 COPT 有 R-R (P2()-n2(1)+(s-1)(m2(2s)-p2(2s) OPT F 1-a s(m2s-p2)+(s-1)( 1-a (2(2s)-m2(2s))>0. 综合以上分析可知,算法ALG只能得到一个比B更大的竞争比定理5证毕 至此我们得到了离散型两斜率在线租赁问题最优确定性在线策略和最优随机性在线策略的竞争比(见 图1之圆角矩形框).从图1中可以清晰地看到:无论是经典的在线租赁问题还是两斜率在线租赁问题,离散 第7期 胡茂林,等:离散型两斜率在线租赁问题 1687 型问题的竞争比都优于连续性问题的竞争比.至于多斜率在线租赁问题,目前仅得到了连续性问题竞争比的 上界,事实上其中的随机性竟争比的上界还可以改进到a1+/m(见169);而离散型问题则有待学者们关注 和研究 最优确定最优随机 最优确定最优随机 确定性策随机性策 性策略及性策略及 性簧咯及性策略及 略竞争略竞争 其竞争比其竞争比 其竞争比其竞争比 比上界比上界 2 / e-1+ (k+1-kAe-1 经典的在线 两斜率在线 租赁问题 推 租赁问题 推 k+1斜率在线 租赁问题 最优确定最优随机 最优确定最优随机 最优确定「最优随机 性策略及性策略及 性策略及性策略及 性策略及性策略及 其竞争比其竞争比 其竞争比其竞争比 其竞争比其竞争比 1+(S-1)a 有待将来研究解决 (1-a)s- 图1在线租赁连续性问题和离散型问题主要研究内容和结果 5竞争性能分析与讨论 表1刘出的是参数s取{2,5,12.23,38,55},a取{0,0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9}时离散型两斜 率在线租赁问题最优确定性在线策略和最优随机性在线策略的竞争比!和饣,的值 表1参数s,α取不同值时离散型两斜率在线租赁问题最优确定性在线策略和最优随机性在线策略的竞争比 S 2 5 12 23 38 55 Rr R Rd 0.01.5001.3331.8001.4871.9171.54319571.56219741.5701.9821.574 0.11.4501.2901.7201.4181.8251.4641.8611.4791.8761.4851.8841.448 0.21.4001.2501.6401.3551.7331.3921.7651.4041.7791.4091.7851.412 0.31.3501.2121.5601.2981.64213271.6701.3371.6821.3411.6871.343 0.41.3001.1761.4801.2451.55012681.5741.2751.5841.2781.5891280 0.51.2501.1431.1001.1961.4581.2141.4781.2191.18712221.4911.223 0.61.2001.1111.3201.1511.3671.1641.3831.1681.3891.1701.3931.171 0.71.1501.0811.2401.1101.2751.1181.2871.1211.2921.1221.2951.123 0.81.1001.0531.1161.0701.1841.0761.1911.0771.1951.0781.1961079 0.91.0501.0251.0801.0341.0921.0361.0951.0371.0971.0371.0981.038 5.1确定性在线策略竞争性能分析与讨论 连续性两斜率在线租赁问题的最优确定性竞争比是=2-α.本文定理1给出的离散型两斜率在线租 赁间题的最优确定性竞争比为R=2-+.由于2-a-12-+(-1]=1>0,故而考虑离散性能 比连续性提高决策效率.从推论1可知:当a=0时,R=2-3,即为经典的在线租赁问题的最优竞争比;尽 管两个竞争比2 1+(s-1) 与2--都是随s的减小在减小,但当a>0时,2 1+(s-1)a <2-1,这表明 两斜率在线租赁问题的竞争性能总是优于经典的在线租赁问题的竞争性能,而且这种优异性随着租约系数α 的增大在显著放大.从图2可以直观地看出:离散型两斜率在线租赁问题的最优确定性竞争比不仅随设备的 购买价s的减小或是随租约系数a的增大而单一地减小,而且还随着s在减小的同时a又增大的交互作用 而快速递减,但租约系数a的增大对降低竞争比R起了主导作用.R=2-1+(的这些性态还可以通过 表1清晰地反映出来:如在表1中,当a=0,5分别取2与38时,对应的经典的在线租赁问题的竞争比R 1688 系统工程理论与实践 第39卷 依次录得1.5和1.974;当8=12,a分别取0.2与0.8时.录得的离散型两斜率在线租赁问题的竞争比Ra依 次为1733和1.184:;而当s=2,a=0.9时,对应的离散型两斜率在线租赁间题的竞争比Rt的值仅为1.050 16 1.3 12 1.2 .3 0.6 06 图2离散型两斜率在线租赁问题确定性 图3离散型两斜率在线租赁问题随机性 在线策略竞争性能分析 在线策略竞争性能分析 5.2隃机性在线策略竞争性能分析与讨论 这里先通过一组具体的数值例子来说明参数(s,a)对离散型两斜率在线租赁问题最优随机性策略以及 竞争比的重要影响(见表2) 表2参数(s,a)取不同值时离散型两斜率在线租赁问题最优随机性策略以及竞争比 (5,0.0) (5,0.2) (10,0.0) (10.0.2) (15,0.0)(15,0.2)(15.0.3) p1()p2(j)p1()p2(j)p1(1)p2()p1(j)P2()p1(j)p2()p1(0)p2)P1(1)p2(j) 10.8780.1220.8890.l110.9410.0590.9460.0540.9610.0390.9610.0390.9610.039 30.5350.4650.5770.4230.8010.1990.8200.1800.8730.1270.8860.1140.8910.109 10.0890.9110.6290.3710.6650.3350.7730.2270.7960.2040.8050.195 8 10.0890.9110.2920.7080.3600.6400.5940.4060.6340.3660.6520.348 0000 10.0890.911 0.0970.9030.4530.5470.5070.4930.5300.470 12 10.0890.911 1111 0.0970.9030.2900.7100.3600.6400.3910.609 15 10.089O.9110 0.0970.9030 10.0990.9010.1420.858 16 10.0890.911 0 0.0970.9030 10.0990.9010.1420.858 P1.48741.35531.53531.38691.55101.39711.3310 在表2中,对参数(s,a)的每一组给定值,我们沿其所在的列白上而下看其对应的最优随机性在线策略 的概率分布(m1(j),p2()的取值的变化情况:在租赁活动的初期都是以较大的概率p1(j)沿 Slope租赁设 备而以较小的概率2(j)沿Sope2租赁设备,随着租赁期数j的增大彼消此长,又在条件p(j)+p2(j)=1 的约束下相互制约、相矿均衡.这种彼消此长又相互均衡的态势在它的最优决策时间点j=8达到了一个 长者停长、消者止消的稳定的常数概率分布.当a=0时,即经典的离散型在线租赁问题在最优决策时间点 j=8达到的常概率分布是(1,0),而两斜率离散型在线租赁问题(a>0)在最优决策时间点j=s所录得的 常概率分布再也达不到(1.0),而是随着参数(s,a)的不同而不同 从表2中我们粗略地看到,离散型两斜率在线租赁间题的最优随机性策略SBR的竞争比R随α的增 大或s的减小在不断减小.事实上,这不是偶然的,而是定理3所给出的离散型两斜率在线租赁间题的最优 随机性策略SBR的竞争比R=-0-0及其推论3和推论4的必然结果结合表1和图3,不难看 出这种饣随α或s的变化或者说a或s对饣的影响非常炎似于5.1节中最优确定性策略及其竞争比的情 况.另外由推论4可知,考虑设备使用时间的离散性能够把连续时间情况下由 Lotker等人给出的最优随机 性竞争比a1+a减小到 s8-(1-a)(s-1 6结束语 纵观在线租赁问题研究的进展过程:自 Karlin于1988年和1994年先后介绍了连续时间状态下经典的 第7期 胡茂林,等:离散型两斜率在线租赁问题 1689 在线租赁冋题旳最优确定性策略(竞争比为2)和最优随机性策略(竞争比为。S)以来.学者们对其进行了各 种变形和推广硏究.起初的硏究聚焦于该问题在离散时间状态下确定性策略和随机性策略.在1992年Karp 给出了竞争比为2-的离散时间的最优确定性策略到了1999年 El-Yaniv得到了竞争比为-(-1的 离散型最优随机性策略.可以说在线租赁问题的硏究形成了连续性和离散型两条主线.近些年来,除了在这 两条主线上引入一些经济管理背景、市场因素的变形研究之外,其主要的推广研充是两斜率以及多斜率在线 租赁的研究.关于两斜率在线租赁,其连续性问题已得到了比较完美地解决.基于经典研究在线租赁问题 般按连续性和离散型两条主线进行(如图1),本文硏究了离散型两斜率在线租赁问题,分别得到了其最优确 定性竞争比和最优随机性竞争比2-+。和。,在将来的研究中我们将关注离散型多斜率 在线租赁问题 参考文献 Karlin A R, Manasse MS, Rudolph L, et al. Competitive snoopy caching. Algorithmica, 1988, 3(1):77-119 2 Karlin A R, Manasse M S, McGeoch L A, et al. Competitive randomized algorithms for nonuniform problems(] Algorithmica,1994,11(6):542571 3 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 4 El-Yaniv R, Kaniel R, Linial N Competitive optimal online leasingJ. Algorithmica. 1999, 25(1): 116-140 5 Azar Y, Bartal Y, Feuerstein E, et al. On capital investment[]. Algorithmica, 1999, 25(1):22-36 6 Bejerano Y, Cidon I, Naor J Dynamic session management for static and mobile users: A competitive on-line algorithmic approach(C// Proceedings of the 4th Internalional Workshop On Discrete Algorithns and Methods for Mobile Computing and communications, 2000: 65-74 7 Damaschke P. Nearly optimal strategies for special cases of on-line capital investment[J]. Theoretical Computer Science,2003,302(1-3):35-44. [8 Abshoff S, Kling P, Markarian C, et al. Towards the price of leasing online[J. Journal of Combinatorial Opti mization,2015,24:1-20. 9 Li S, Macker A, Markarian C. et al. Towards flexible demands in online leasing problems. Computing and Combinatorics,2015,9198(5):277-288. [10 Dai W, Dong Y, Zhang X. Competitive analysis of the online financial lease problem J]. European Journal of Operational Research, 2016, 250: 865-873 11 Lotker Z, Patt-Shamir B, Rawitz D Ski rental with two general options[J. Information Processing Letters, 2008 108(1):339422 12 Leve A, Patt-Shamir B Non-additive two-option ski rental[J. Theoretical Computer Science, 2015, 584: 42-52 13陈晓丽,徐维军,复利下二重在线租赁竞争策略及风险补偿模型·系统工程理论与实践,2016,36(9):2284-2292 Chen X L, Xu wJ. Competitive strategy and risk-reward model with compound rate for online fashion A-B leasing problem[J. Systems Engineering-Theory Practice, 2016, 36( 9): 2284-2292 14 Lotker Z, Patt-Shamir B, Rawitz D. Rent, lease or buy: Randomized algorithms for multislope ski rentalJ SIAM Journal On DiscreTe MalheIlalics, 2012, 26(2): 718-736 [15 Fujiwara. H, Kitano T, Fujito T On the best, possible competitive ratio for multislope ski rental[C// Proceedings of the 22th International Conference on Algorithms and Computation, 2011: 541-553 16 Iu M L, Xu wJ. A better bound randomize d algorithms for the multislope ski-rental problemJ. RAIRO Theoretical Informatics and Applications, 2017, 51(16): 91-98