動(dòng)態(tài)時(shí)間的最值問(wèn)題

動(dòng)態(tài)時(shí)間的最值問(wèn)題

0帶需求時(shí)間窗口的動(dòng)態(tài)批量由于經(jīng)濟(jì)批發(fā)模式與實(shí)際的經(jīng)濟(jì)生產(chǎn)和流通密切相關(guān)，近年來(lái)，許多科學(xué)家首次提出了不同形式的動(dòng)態(tài)批發(fā)模式。1958年，which和whiti首次提出了單一產(chǎn)品和多個(gè)時(shí)期的動(dòng)態(tài)經(jīng)濟(jì)批發(fā)模式。從那時(shí)起，許多科學(xué)家在耿基模型上進(jìn)行了深入研究和廣泛開發(fā)。1989年，lee首次提出了具有需求時(shí)間窗口的動(dòng)態(tài)批發(fā)方法。如果不允許缺陷，可以獲得o（t2）的多時(shí)間算法。如果允許缺陷，請(qǐng)獲取o（t3）的多時(shí)間算法。2004年，lee研究了單個(gè)批發(fā)商的一級(jí)經(jīng)濟(jì)批發(fā)模式。它不僅考慮了單位運(yùn)輸能力的限制，還規(guī)定了供應(yīng)商的最低運(yùn)輸能力，因此提出了一種計(jì)算復(fù)雜性為o（n4）的多時(shí)性算法。2005年，lee等人將這個(gè)問(wèn)題推廣到許多產(chǎn)品的情況。2006年，h永年等人進(jìn)一步研究了這個(gè)問(wèn)題。如果允許缺貨，請(qǐng)將條件排除在ptpt-1和pt-pt-1的條件下，并獲得計(jì)算時(shí)間為湯川的多時(shí)性算法。2004年，jaruphongsa等人考慮了三個(gè)階段供應(yīng)鏈中需求時(shí)間窗口的經(jīng)濟(jì)批發(fā)方法。2007年，jaruphongsa提出了一個(gè)復(fù)雜的時(shí)間算法，該算法的計(jì)算復(fù)雜性為o（t5）。2008年，魯奎等人研究了外部運(yùn)輸能力的適應(yīng)性經(jīng)濟(jì)批發(fā)方法，并提出了一種啟發(fā)性算法。根據(jù)。本文首次提出了具有價(jià)格折扣和需求時(shí)間窗口的經(jīng)濟(jì)批量問(wèn)題.在不允許缺貨的情況下,考慮在每一個(gè)補(bǔ)貨期,供應(yīng)商根據(jù)零售商的進(jìn)貨數(shù)量的多少給予一定的價(jià)格折扣,其交貨期在一定的時(shí)間窗口.利用動(dòng)態(tài)規(guī)劃算法,提出了OmT2多項(xiàng)式時(shí)間算法.1交易成本計(jì)算中的機(jī)構(gòu)設(shè)計(jì)相關(guān)符號(hào)說(shuō)明如下:T表示整個(gè)生產(chǎn)(銷售)期內(nèi)的周期數(shù);n表示在T時(shí)期的需求個(gè)數(shù);di表示第i個(gè)需求的需求量,i∈{1,2···n};[Ei,Li]表示第i個(gè)需求的需求時(shí)間窗口,Ei表示最早交貨期,Li表示最晚交貨期;D(s,t)表示最早交貨期在[s,t]之間的需求量之和;A(s,t)表示最晚交貨期在[s,t]之間的需求量之和;Dt表示最晚交貨期在t時(shí)期的需求量;It表示t時(shí)期末的庫(kù)存量;ht表示在t時(shí)期單位產(chǎn)品的庫(kù)存費(fèi)用;h(s,t)表示從s時(shí)期到t時(shí)期單位產(chǎn)品的庫(kù)存費(fèi)用;Kt表示在t時(shí)期補(bǔ)貨時(shí)的固定成本;xt表示t時(shí)期的補(bǔ)貨量;ri表示折扣率(0<ri<1,ri<ri+1,i∈{1,2···m});Ni表示折扣點(diǎn),i∈{1,2···m};at表示在t時(shí)期無(wú)價(jià)格折扣時(shí)的單位產(chǎn)品的價(jià)格;pt表示在t時(shí)期有價(jià)格折扣時(shí)的單位產(chǎn)品的價(jià)格.根據(jù)以上定義,此問(wèn)題的數(shù)學(xué)模型可表示為:假設(shè)如下:(1)Ni+1(1-ri+1)Ni(1-ri);(2)htat+1.2補(bǔ)貨期的生成在介紹多項(xiàng)式算法之前,我們先介紹一些關(guān)于此問(wèn)題最優(yōu)解的性質(zhì)及定理.性質(zhì)2.1在最優(yōu)情形下,若在t時(shí)期滿足,則xt>0.性質(zhì)2.2在最優(yōu)情形下,若t1<t2<······<tr是連續(xù)的補(bǔ)貨期,那么在tj時(shí)期補(bǔ)貨來(lái)滿足tjLi<tj+1的所有需求.性質(zhì)2.3在最優(yōu)情形下,若s時(shí)期為補(bǔ)貨期,且滿足sLit(1s<tT)之間時(shí)期的需求,則在此時(shí)期的補(bǔ)貨量為斷點(diǎn)Nk,k=1,2,···,m或A(s,t)-Is-1.證明以下分兩種情況考慮:(1)若從時(shí)期s+1到T之間無(wú)補(bǔ)貨期,顯然xs=A(s,t)-Is-1.(2)若在時(shí)期s還存在補(bǔ)貨期t,不妨設(shè)xs∈(Nu-1,Nu),u=1,2,···,m,可在s時(shí)期減少一單位的補(bǔ)貨量,而在t時(shí)期增加一單位的補(bǔ)貨量,得到一個(gè)新的可行解V,即xs=xs-1,xt=xt+1.令ru,rv分別為零售商在s,T時(shí)期的折扣率.那么,性質(zhì)2.4在最優(yōu)情形下,若s時(shí)期為補(bǔ)貨期,且滿足sLit(1s<tT)之間時(shí)期的需求,若A(s,t)-Is-1∈[Nu-1,Nu),u=1,2,···m,則xs=Nu或xs=A(s,t)-Is-1.證明(1)若從時(shí)期s+1到T之間無(wú)補(bǔ)貨期,顯然xs=A(s,t)-Is-1.(2)若s時(shí)期之后還存在補(bǔ)貨期t,則分以下兩種情況考慮:①假設(shè)xsNu-1,則由,得Is=xs-(A(s,t)-Is-1)<0.這與不允許缺貨矛盾.②假設(shè)xs>Nu,不妨設(shè)xs=Nu+q,(q1),則可在s時(shí)期減少Nu+q-Nu的進(jìn)貨量,而在t時(shí)期增加相同數(shù)量的進(jìn)貨量,同時(shí)保持其他時(shí)期的進(jìn)貨情況不變,得到新的可行解V.即:xs=Nu,xt=xt+Nu+q-Nu.則這與最優(yōu)解矛盾.3計(jì)算復(fù)雜性的算法令C(s,t)為零售商在s時(shí)期進(jìn)行補(bǔ)貨,并且滿足最晚交貨期Li在時(shí)期s,t(sLit)之間的所有需求di的最小費(fèi)用.F(t)為滿足Lit的所有需求di的最小費(fèi)用.則,其中F(0)=0,很明顯F(T)為最優(yōu)解.如果C(s,t)的值已知,那么計(jì)算F(T)的計(jì)算復(fù)雜性為OT2.下面的任務(wù)是計(jì)算C(s,t)的值.以下分兩種情況討論:(1)若時(shí)期s不是最后一個(gè)補(bǔ)貨期,也就是從時(shí)期t+1到T之間還有補(bǔ)貨期,根據(jù)性質(zhì)2.4,若A(s,t)-Is-1∈[Nu-1,Nu),u=1,2,······m,那么xs=Nu,(2)若時(shí)期s是最后一個(gè)補(bǔ)貨期,也就是從時(shí)期t+1到T之間沒有補(bǔ)貨期,根據(jù)性質(zhì)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).很明顯計(jì)算C(s,t)的復(fù)雜性為OmT2,從而我們提出的整個(gè)算法的計(jì)算復(fù)雜性為OmT2.本文考慮了在不允許缺貨的情況下,具有多個(gè)價(jià)格折扣點(diǎn)的帶有需求時(shí)間窗口的經(jīng)濟(jì)批量問(wèn)題,得到了計(jì)算復(fù)雜性為OmT2的多項(xiàng)式時(shí)間算法.對(duì)允許缺貨的情況下,作者以后將繼續(xù)考慮.4pt的計(jì)算例題T=4,n=3,[E1,L1]=,[E2,L2]=,[E3,L3]=,d1=8,d2=15,d3=12對(duì)于t=1,···4,at=10,Kt=10,ht=12.當(dāng)0xt<5時(shí),有pt=10;當(dāng)5xt<10時(shí),有pt=10×(1-10%);當(dāng)10