多階段數(shù)量折扣訂貨模型優(yōu)化與遺傳算法求解*

孫方東 李宗吉

(1.91183部隊(duì) 青島 266102)(2.海軍工程大學(xué)兵器工程系 武漢 430033)

?

多階段數(shù)量折扣訂貨模型優(yōu)化與遺傳算法求解*

孫方東1李宗吉2

(1.91183部隊(duì) 青島 266102)(2.海軍工程大學(xué)兵器工程系 武漢 430033)

針對(duì)現(xiàn)有訂貨批量模型在描述庫存成本上的缺陷,對(duì)其進(jìn)行了修正。應(yīng)用遺傳算法對(duì)修正后的模型進(jìn)行了求解,結(jié)合動(dòng)態(tài)規(guī)劃最優(yōu)性原理,著重優(yōu)化了遺傳算法編碼方案的設(shè)計(jì),確保編碼方案的完備性。經(jīng)實(shí)例驗(yàn)證,該求解方法可有效解決多階段數(shù)量折扣問題,克服了動(dòng)態(tài)規(guī)劃和S-M法的局限性。

遺傳算法; 數(shù)量折扣; 訂貨策略

Class Number TP18

1 引言

供應(yīng)商為刺激消費(fèi)需求,減少產(chǎn)品積壓,加速資金流轉(zhuǎn),通常會(huì)提供數(shù)量折扣,即購買商品的數(shù)量不同,商品單價(jià)也不同,一般情況下購買數(shù)量越多,單價(jià)越低。在這種情況下,從買方的角度,就需確定其經(jīng)濟(jì)合理的訂貨策略使其成本降低。這是一類典型的動(dòng)態(tài)批量問題,其求解的基本思路是建立描述具體問題的線性或非線性規(guī)劃模型,并運(yùn)用一定的算法求解。現(xiàn)有的規(guī)劃模型[5～8]結(jié)構(gòu)均比較相似,但存在對(duì)目標(biāo)函數(shù)中庫存成本表達(dá)不完善的缺陷。

求解算法中比較常用的是Sliver&Meal啟發(fā)式算法(S-M)、拉格朗日松弛解法、動(dòng)態(tài)規(guī)劃法(DOQ)和啟發(fā)式算法[2]。文獻(xiàn)[3～4]雖指出S-M法有可能收斂到局部最優(yōu),并提出了各自的解決方案,但并未從根本上解決此問題。DOQ模型基于對(duì)最優(yōu)解結(jié)構(gòu)屬性的證明,大大縮小了可行解的空間范圍,是求解動(dòng)態(tài)批量問題的最核心和基礎(chǔ)的方法,但DOQ模型對(duì)目標(biāo)函數(shù)和約束條件及問題背景均有一定要求[2]。且隨著多級(jí)多項(xiàng)目多資源問題的引入,動(dòng)態(tài)規(guī)劃作為精確求解方法很難在短時(shí)間內(nèi)取得滿意解。

本文首先修正了現(xiàn)有模型中庫存成本的表達(dá)式,使其更符合實(shí)際情況,進(jìn)而應(yīng)用遺傳算法對(duì)模型進(jìn)行了求解。基于該類問題最優(yōu)解的性質(zhì)[8],結(jié)合動(dòng)態(tài)規(guī)劃最優(yōu)性原理,著重優(yōu)化了遺傳算法編碼方案的的設(shè)計(jì),確保編碼方案可遍歷各可行解,進(jìn)而收斂到全局最優(yōu)。結(jié)合文獻(xiàn)[4,7]中的兩個(gè)案例,進(jìn)行了實(shí)例計(jì)算,計(jì)算結(jié)果表明,本文提出的優(yōu)化算法有更好的效果。

2 模型建立

訂貨批量問題屬于多周期規(guī)劃問題,將規(guī)劃期分成不同的時(shí)間周期,基于不同周期的需求,綜合權(quán)衡購買成本、訂貨準(zhǔn)備成本和庫存成本。優(yōu)化目標(biāo)為在恰當(dāng)?shù)臅r(shí)間購買恰當(dāng)數(shù)量的產(chǎn)品,使相關(guān)總成本最小。設(shè)周期性檢查庫存,只在期初訂貨,其訂貨量為xi,提前期固定,不允許缺貨。計(jì)劃時(shí)段為n個(gè)周期,計(jì)劃期開始時(shí)和結(jié)束時(shí)庫存都為零。成本包括購買成本、訂貨成本和庫存成本。已有文獻(xiàn)[5～8]在建立該問題的模型時(shí),目標(biāo)函數(shù)多采用如下所示的形式:

(1)

式(1)中及下文將用到的各符號(hào)代表的物理意義如表1所示。

表1 各符號(hào)物理意義

目標(biāo)函數(shù)中第一項(xiàng)為購買成本,第二項(xiàng)為庫存管理成本,第三項(xiàng)為訂貨成本?？疾焓?1)中的庫存管理成本,該表示方法規(guī)定了庫存管理成本僅由期末剩余的庫存所決定,而沒有考慮逐步消耗的備件同樣會(huì)帶來管理成本,這顯然是不合理的?？紤]一個(gè)極端情形,設(shè)第i時(shí)間段開始時(shí)的訂貨在期末恰好用完,該時(shí)間段庫存Ii=0,則庫存管理成本為零,顯然不符合實(shí)際。因此用hi·Ii計(jì)算庫存管理成本是不合適的。

圖1 物資消耗過程

考察物資消耗過程如圖1所示。

(2)

考慮一種較特殊的情形,備件消耗速度不變,這在短周期內(nèi)是可以接受的。設(shè)第i時(shí)間段內(nèi)需求為di,則由需求引起的平均庫存為di/2,加上未消耗完的庫存即為該時(shí)間段的總體平均庫存水平,庫存成本為hi·(Ii+di/2),本文即在該種情形下建立模型。

（1）無雙重支付的情形。假設(shè)A有1枚比特幣，要將其轉(zhuǎn)給B。A首先構(gòu)造一筆交易Tx1：使用私鑰簽署該筆交易，并將交易單Tx1廣播出去。其他實(shí)體收到信息后，通過UTXO索引計(jì)算A是否有能力支付1枚比特幣，如果有能力支付，則認(rèn)為此次交易是合法。最后，A的錢包地址減少1枚比特幣，B的錢包地址增加1枚比特幣。

重新建立模型如下:

Ii=Ii-1+xi-di

∑xi=∑di

(3)

訂貨序列x={xi,i=1,2,…,n}即為決策變量。

3 算法設(shè)計(jì)

1) 最優(yōu)解的性質(zhì)

2) 應(yīng)用遺傳算法求解的思路

遺傳算法的操作對(duì)象是與決策變量相對(duì)應(yīng)的編碼,問題的關(guān)鍵在于選取合適的操作變量,構(gòu)造合理的編碼方案,使得編碼方案具有完備性和非冗余性,即遺傳算法空間中的染色體能對(duì)應(yīng)所有問題空間中的候選解,并盡可能縮小尋優(yōu)空間。文獻(xiàn)[6]提出將每期的訂貨量作為操作變量,采用實(shí)值編碼方案。該方案物理意義明確,但問題實(shí)質(zhì)上是只有第一期和最后一期為再生點(diǎn)的特殊情況。同時(shí)產(chǎn)生隨機(jī)個(gè)體的方法會(huì)產(chǎn)生大量無意義的冗余方案,造成了計(jì)算資源的浪費(fèi)。文獻(xiàn)[7]將Y(xi)作為操作變量,采用二進(jìn)制編碼。不存在折扣時(shí),Y(xi)與訂貨量存在一一對(duì)應(yīng)的關(guān)系,可以方便的進(jìn)行轉(zhuǎn)化,不失為一種具備完備性和非冗余性的好方法。本文中的第一個(gè)案例,即采取該方案得到了理想的結(jié)果。但存在折扣時(shí),決策變量訂貨量有可能是折扣點(diǎn),也有可能是實(shí)際需求量,與Y(xi)沒有一一對(duì)應(yīng)關(guān)系,因此該編碼方案不能解決存在折扣的問題。其提出的案例雖然帶有折扣,但實(shí)際按照無折扣進(jìn)行近似優(yōu)化,得到的結(jié)果不一定是最優(yōu)。本文在實(shí)例計(jì)算中對(duì)其中的一個(gè)案例進(jìn)行重新優(yōu)化,得到了更為理想的結(jié)果。

本文的編碼方案如下:

設(shè)有兩個(gè)相鄰的再生點(diǎn)Zj、Zk,構(gòu)造算法如下:

Step 1:i=1:length(j+1:k)

if length(j+1:k)=1,則j+1期訂貨量為實(shí)際需求量;

if length(j+1:k)>1,進(jìn)入step 2;

Step 2:按照帶折扣問題可行解的性質(zhì),對(duì)每一階段產(chǎn)生一個(gè)可行解矩陣,代表該階段所有的子策略?？尚薪饩仃嚸恳恍袨橐粋€(gè)可行解,其中第一行可行解的最后一次訂貨小于最小的折扣點(diǎn),則第l行可行解的最后一次訂貨是第一行可行解最后l次訂貨量之和。以某一階段中有三個(gè)訂貨點(diǎn)為例,可能的可行解矩陣結(jié)構(gòu)如下所示:

其中x1、x2、x3是三個(gè)訂貨量不為零的訂貨點(diǎn),訂貨點(diǎn)的訂貨量須滿足最優(yōu)解性質(zhì)。此時(shí)問題的關(guān)鍵為如何實(shí)現(xiàn)第一行解的構(gòu)造,本文中第一行可行解的產(chǎn)生程序框圖如圖2所示。

圖2 第一行解產(chǎn)生程序框圖

4 實(shí)例計(jì)算

例1首先考察無折扣時(shí)的優(yōu)化策略,取文獻(xiàn)[4]中應(yīng)用S-M法優(yōu)化訂貨策略的案例,簡(jiǎn)便起見,僅取其數(shù)據(jù),并去掉量綱。其需求數(shù)據(jù)如表3所示,其中訂貨費(fèi)用為1200,儲(chǔ)存費(fèi)用為50。

表3 物資需求數(shù)據(jù)

分別應(yīng)用動(dòng)態(tài)規(guī)劃和遺傳算法進(jìn)行優(yōu)化,計(jì)算結(jié)果如表4所示。

表4 訂貨策略優(yōu)化結(jié)果

DOQ及遺傳算法優(yōu)化策略的到貨點(diǎn)在周期1、4、7,訂貨數(shù)量分別為12、24、17,得到總成本費(fèi)用為8000。S-M法得到的優(yōu)化策略到貨點(diǎn)分別為1、4、8,訂貨數(shù)量分別為12、27、14總成本費(fèi)用為8250。說明本文提出的方法不僅是有效的,而且優(yōu)于S-M法,能收斂到全局最優(yōu)。

由于帶折扣問題涉及多個(gè)變化的參數(shù),狀態(tài)空間龐大,難以采用動(dòng)態(tài)規(guī)劃法驗(yàn)證本文提出的方法是否收斂到全局最優(yōu),故本節(jié)選取文獻(xiàn)[7]中案例,對(duì)同一案例進(jìn)行優(yōu)化,進(jìn)而比較兩者結(jié)果。

例2取文獻(xiàn)[7]中的案例,同樣取其數(shù)據(jù),去掉量綱。其中產(chǎn)品1的需求為[50,45,35,60],折扣點(diǎn)為[100,300],單價(jià)分別為[12,10,8],訂貨成本分別為[10,11,12,10],儲(chǔ)存成本為[0.5,0.4,0.6,0.5]。文獻(xiàn)[7]中的方法一與本文提出的方法二計(jì)算結(jié)果對(duì)比如表5所示。

表5 計(jì)算結(jié)果對(duì)比

可以看到,本文提出的方法得到的總費(fèi)用較少。進(jìn)一步分析結(jié)果,本文的計(jì)算結(jié)果導(dǎo)致一次性大量訂貨,觀察儲(chǔ)存成本與單價(jià),發(fā)現(xiàn)產(chǎn)品1的儲(chǔ)存成本僅占單價(jià)的5%,一次性大量訂貨是可以接受的,若考慮其他資源的約束,如資金、庫存容量等限制,則要另外建立模型加以分析,就本案例,本文提出的解決方法是較優(yōu)的。

5 結(jié)語

本文首先對(duì)帶折扣批量訂貨問題模型進(jìn)行了修正,使其更符合實(shí)際情況。進(jìn)而基于該類問題最優(yōu)解的性質(zhì),應(yīng)用遺傳算法對(duì)該問題進(jìn)行了求解,結(jié)合動(dòng)態(tài)規(guī)劃最優(yōu)性原理,著重優(yōu)化了編碼方案的設(shè)計(jì),確保算法可收斂到全局最優(yōu)。同時(shí)遺傳算法作為啟發(fā)式算法,在求解大型問題時(shí)比動(dòng)態(tài)規(guī)劃法有更好的尋優(yōu)速度。此外,遺傳算法構(gòu)造簡(jiǎn)單,可方便地進(jìn)行拓展以解決更復(fù)雜的問題。計(jì)算結(jié)果也驗(yàn)證了本文提出的方法的有效性,可對(duì)工程實(shí)踐給予指導(dǎo)。

[1] 徐健騰,張慶普.多供應(yīng)商的動(dòng)態(tài)批量問題研究[J].哈爾濱工程大學(xué)學(xué)報(bào),2010,31(4):451-456.

[2] 王海英,等.基于動(dòng)態(tài)規(guī)劃方法的動(dòng)態(tài)批量問題研究[J].科技進(jìn)步與對(duì)策,2009,26(4):162-165.

[3] 金錫萬.多階段需求不均衡時(shí)的一種庫存控制模型-兼評(píng)Silver&Meal啟發(fā)式算法I[J].物流技術(shù),1995(6):15-18.

[4] 唐納德·沃爾特斯著.李習(xí)文,李斌譯.庫存控制與管理[M].北京:機(jī)械工業(yè)出版社,2005:82-86.

[5] 唐立新,楊自厚,王夢(mèng)光,等.CIMS中帶多資源的CLSP問題的遺傳啟發(fā)式算法[J].系統(tǒng)工程理論與實(shí)踐,1997(4):39-44.

[6] 王建忠,杜綱.基于遺傳算法的數(shù)量折扣訂貨模型求解[J].河北工業(yè)大學(xué)學(xué)報(bào),2006,35(2):81-85.

[7] 田俊峰,楊梅.數(shù)量折扣條件下的動(dòng)態(tài)訂貨批量?jī)?yōu)化[J].西南交通大學(xué)學(xué)報(bào),2004,39(5):595-599.

[8] 徐健騰,張慶普.多供應(yīng)商的動(dòng)態(tài)批量問題研究[J].哈爾濱工程大學(xué)學(xué)報(bào),2010,31(4):451-457.

[9] Shittu, E. (2003). Applying genetic algorithms to the deterministic time-varying fixed quantity lot sizing problem[D]. Masters Thesis. Cairo, Egypt: The American University in Cairo.

[10] Lotfi Gaafar. Applying genetic algorithms to dynamic lot sizing with batch ordering[J]. Computers & Industrial Engineering,2006(51):433-444.

Optimization for Multi-period Ordering Model with Quantity Discount and Solving Based on GA

SUN Fangdong1LI Zongji2

(1. No. 91183 Troops of PLA, Qingdao 266102) (2. Naval Research Institute of New Weaponry Technology & Application, Naval University of Engineering, Wuhan 430033)

The model describing the ordering problem with quantity discount is modified to be true of the reality. And a method was proposed based on Genetic Algorithms, especially the coding method is optimized to get the best result. Using certain numerical examples, the method is proved to be effecter than S-M and DOQ.

GA, quantity discount, order tactics

2015年6月11日,

2015年7月26日

孫方東,男,助理工程師,研究方向:水中兵器動(dòng)力推進(jìn)技術(shù)。

TP18

10.3969/j.issn.1672-9730.2015.12.031