动态时间的最值问题

动态时间的最值问题

0带需求时间窗口的动态批量由于经济批发模式与实际的经济生产和流通密切相关，近年来，许多科学家首次提出了不同形式的动态批发模式。1958年，which和whiti首次提出了单一产品和多个时期的动态经济批发模式。从那时起，许多科学家在耿基模型上进行了深入研究和广泛开发。1989年，lee首次提出了具有需求时间窗口的动态批发方法。如果不允许缺陷，可以获得o（t2）的多时间算法。如果允许缺陷，请获取o（t3）的多时间算法。2004年，lee研究了单个批发商的一级经济批发模式。它不仅考虑了单位运输能力的限制，还规定了供应商的最低运输能力，因此提出了一种计算复杂性为o（n4）的多时性算法。2005年，lee等人将这个问题推广到许多产品的情况。2006年，h永年等人进一步研究了这个问题。如果允许缺货，请将条件排除在ptpt-1和pt-pt-1的条件下，并获得计算时间为汤川的多时性算法。2004年，jaruphongsa等人考虑了三个阶段供应链中需求时间窗口的经济批发方法。2007年，jaruphongsa提出了一个复杂的时间算法，该算法的计算复杂性为o（t5）。2008年，鲁奎等人研究了外部运输能力的适应性经济批发方法，并提出了一种启发性算法。根据。本文首次提出了具有价格折扣和需求时间窗口的经济批量问题.在不允许缺货的情况下,考虑在每一个补货期,供应商根据零售商的进货数量的多少给予一定的价格折扣,其交货期在一定的时间窗口.利用动态规划算法,提出了OmT2多项式时间算法.1交易成本计算中的机构设计相关符号说明如下:T表示整个生产(销售)期内的周期数;n表示在T时期的需求个数;di表示第i个需求的需求量,i∈{1,2···n};[Ei,Li]表示第i个需求的需求时间窗口,Ei表示最早交货期,Li表示最晚交货期;D(s,t)表示最早交货期在[s,t]之间的需求量之和;A(s,t)表示最晚交货期在[s,t]之间的需求量之和;Dt表示最晚交货期在t时期的需求量;It表示t时期末的库存量;ht表示在t时期单位产品的库存费用;h(s,t)表示从s时期到t时期单位产品的库存费用;Kt表示在t时期补货时的固定成本;xt表示t时期的补货量;ri表示折扣率(0<ri<1,ri<ri+1,i∈{1,2···m});Ni表示折扣点,i∈{1,2···m};at表示在t时期无价格折扣时的单位产品的价格;pt表示在t时期有价格折扣时的单位产品的价格.根据以上定义,此问题的数学模型可表示为:假设如下:(1)Ni+1(1-ri+1)Ni(1-ri);(2)htat+1.2补货期的生成在介绍多项式算法之前,我们先介绍一些关于此问题最优解的性质及定理.性质2.1在最优情形下,若在t时期满足,则xt>0.性质2.2在最优情形下,若t1<t2<······<tr是连续的补货期,那么在tj时期补货来满足tjLi<tj+1的所有需求.性质2.3在最优情形下,若s时期为补货期,且满足sLit(1s<tT)之间时期的需求,则在此时期的补货量为断点Nk,k=1,2,···,m或A(s,t)-Is-1.证明以下分两种情况考虑:(1)若从时期s+1到T之间无补货期,显然xs=A(s,t)-Is-1.(2)若在时期s还存在补货期t,不妨设xs∈(Nu-1,Nu),u=1,2,···,m,可在s时期减少一单位的补货量,而在t时期增加一单位的补货量,得到一个新的可行解V,即xs=xs-1,xt=xt+1.令ru,rv分别为零售商在s,T时期的折扣率.那么,性质2.4在最优情形下,若s时期为补货期,且满足sLit(1s<tT)之间时期的需求,若A(s,t)-Is-1∈[Nu-1,Nu),u=1,2,···m,则xs=Nu或xs=A(s,t)-Is-1.证明(1)若从时期s+1到T之间无补货期,显然xs=A(s,t)-Is-1.(2)若s时期之后还存在补货期t,则分以下两种情况考虑:①假设xsNu-1,则由,得Is=xs-(A(s,t)-Is-1)<0.这与不允许缺货矛盾.②假设xs>Nu,不妨设xs=Nu+q,(q1),则可在s时期减少Nu+q-Nu的进货量,而在t时期增加相同数量的进货量,同时保持其他时期的进货情况不变,得到新的可行解V.即:xs=Nu,xt=xt+Nu+q-Nu.则这与最优解矛盾.3计算复杂性的算法令C(s,t)为零售商在s时期进行补货,并且满足最晚交货期Li在时期s,t(sLit)之间的所有需求di的最小费用.F(t)为满足Lit的所有需求di的最小费用.则,其中F(0)=0,很明显F(T)为最优解.如果C(s,t)的值已知,那么计算F(T)的计算复杂性为OT2.下面的任务是计算C(s,t)的值.以下分两种情况讨论:(1)若时期s不是最后一个补货期,也就是从时期t+1到T之间还有补货期,根据性质2.4,若A(s,t)-Is-1∈[Nu-1,Nu),u=1,2,······m,那么xs=Nu,(2)若时期s是最后一个补货期,也就是从时期t+1到T之间没有补货期,根据性质2.4,xs=A(s,T)-Is-1,则C(s,t)=C(s,T)=Ks+as·(1-ru)·(A(s,t)-Is-1)+hs·B(s+1,T).很明显计算C(s,t)的复杂性为OmT2,从而我们提出的整个算法的计算复杂性为OmT2.本文考虑了在不允许缺货的情况下,具有多个价格折扣点的带有需求时间窗口的经济批量问题,得到了计算复杂性为OmT2的多项式时间算法.对允许缺货的情况下,作者以后将继续考虑.4pt的计算例题T=4,n=3,[E1,L1]=,[E2,L2]=,[E3,L3]=,d1=8,d2=15,d3=12对于t=1,···4,at=10,Kt=10,ht=12.当0xt<5时,有pt=10;当5xt<10时,有pt=10×(1-10%);当10