基于網(wǎng)格自適應(yīng)直接搜索的隨機(jī)庫(kù)存決策模型

昆明理工大學(xué)管理與經(jīng)濟(jì)學(xué)院 薛瀚 黃瓊

作為一類典型的庫(kù)存系統(tǒng)，隨機(jī)庫(kù)存系統(tǒng)由于存在隨機(jī)變量以及變量之間的復(fù)雜線性關(guān)系，不容易通過(guò)解析方法對(duì)其進(jìn)行求解[1]。仿真技術(shù)擅長(zhǎng)于構(gòu)建隨機(jī)性和動(dòng)態(tài)條件下的復(fù)雜系統(tǒng)模型，并進(jìn)行相關(guān)分析。利用仿真技術(shù)能夠盡可能準(zhǔn)確地描述各個(gè)變量之間的關(guān)系，還原現(xiàn)實(shí)世界的復(fù)雜隨機(jī)性，能夠有效地求解隨機(jī)庫(kù)存問(wèn)題[2,3]。

本文優(yōu)化問(wèn)題屬于基于仿真的優(yōu)化問(wèn)題(Simulationbased optimization)，其特征有：由于仿真的復(fù)雜性，目標(biāo)函數(shù)(1)易受到噪聲不同程度的影響；(2)不一定可導(dǎo)和；(3)評(píng)價(jià)過(guò)程耗時(shí)長(zhǎng)[4]。本文將采用網(wǎng)格自適應(yīng)直接搜索進(jìn)行求解。網(wǎng)格自適應(yīng)直接搜索，作為一類直接搜索算法，與隨機(jī)搜索算法相比，具有較強(qiáng)的魯棒性、優(yōu)良的分布式計(jì)算機(jī)制、全局收斂性等優(yōu)點(diǎn)[5]。

本文針對(duì)隨機(jī)需求、隨機(jī)訂貨提前期的隨機(jī)庫(kù)存系統(tǒng)，構(gòu)建了隨機(jī)庫(kù)存決策模型，并提出了一種基于網(wǎng)格自適應(yīng)直接搜索的求解方法。研究實(shí)例表明，模型仿真求解結(jié)果具有穩(wěn)健性且能夠提高系統(tǒng)績(jī)效，從而驗(yàn)證了模型的有效性。

1 問(wèn)題描述及假設(shè)

本文考慮一個(gè)無(wú)限時(shí)間范圍內(nèi)，隨機(jī)需求以及隨機(jī)提前期情形下求解隨機(jī)庫(kù)存系統(tǒng)的最優(yōu)庫(kù)存策略，使系統(tǒng)的平均總成本最小的問(wèn)題。本文中，庫(kù)存系統(tǒng)采用連續(xù)盤點(diǎn)庫(kù)存策略(Q, r)，即當(dāng)系統(tǒng)庫(kù)存位置(庫(kù)存位置=庫(kù)存水平+未到達(dá)的訂貨量)下降到再訂貨點(diǎn)r時(shí)，發(fā)出補(bǔ)貨訂單將庫(kù)存位置補(bǔ)充到Q[6]。同時(shí)，只有當(dāng)系統(tǒng)的庫(kù)存水平大于或等于訂單的需求數(shù)量時(shí)，才滿足訂單需求，否則記入缺貨數(shù)量。綜上，本文的隨機(jī)庫(kù)存決策問(wèn)題可以表述為通過(guò)確定最優(yōu)庫(kù)存策略參數(shù)使得庫(kù)存系統(tǒng)在滿足最小顧客滿意度約束下最小化平均總成本。

本文庫(kù)存系統(tǒng)滿足以下假設(shè)：

(1)單期只出現(xiàn)一個(gè)需求(訂單)；

(2)需求和訂貨提前期是隨機(jī)的，且相互獨(dú)立；

(3)貨物訂單(需求)期初達(dá)到，庫(kù)存滿足則馬上發(fā)貨，若不滿足該訂單量則記入缺貨數(shù)量；

(4)單個(gè)訂貨周期內(nèi)不允許再次訂貨。

2 隨機(jī)庫(kù)存決策模型

如前文所述，本文考慮的隨機(jī)庫(kù)存決策問(wèn)題是通過(guò)求解最優(yōu)的庫(kù)存策略來(lái)最小化系統(tǒng)的平均總成本。按照本文假設(shè)，同時(shí)考慮實(shí)際情況，平均總成本由平均訂貨成本、平均持有成本和平均缺貨成本組成。模型中用到兩個(gè)績(jī)效指標(biāo)：平均總成本和顧客滿意度，平均總成本是主要指標(biāo)，而顧客滿意度是用作約束的指標(biāo)?；谏鲜鲇懻?，隨機(jī)庫(kù)存決策模型(SID)表示如下：

由于本文考慮到隨機(jī)提前期的情況，模型更加現(xiàn)實(shí)并且變得復(fù)雜，難以寫出中間變量的解析式，造成模型解析求解困難。對(duì)此，本文將進(jìn)行仿真建模并采用網(wǎng)格自適應(yīng)直接搜索對(duì)模型進(jìn)行求解。

3 基于網(wǎng)格自適應(yīng)直接搜索的模型求解

網(wǎng)格自適應(yīng)直接搜索(Mesh Adaptive Direct Search,MADS)[5]是模式搜索(Pattern Search)方法的一類，通過(guò)允許變量空間中方向的漸近緊致集的局部搜索，它擴(kuò)展了廣義模式搜索(GPS)。其具有以下優(yōu)勢(shì)：(1)容易拓展與應(yīng)用；(2)求導(dǎo)困難和有限差分不可靠的情況下仍然有效；(3)具有比得上線搜索算法和信賴域算法的全局收斂性質(zhì)[7]。選擇最大代數(shù)和網(wǎng)格閥值作為網(wǎng)格自適應(yīng)直接搜索的停止條件，當(dāng)算法的運(yùn)行代數(shù)超過(guò)最大代數(shù)或者網(wǎng)格尺寸低于網(wǎng)格閥值時(shí)，算法結(jié)束并輸出最優(yōu)結(jié)果。

本文采用美國(guó)MathWorks公司開(kāi)發(fā)的商業(yè)數(shù)學(xué)軟件MATLAB?實(shí)現(xiàn)MADS對(duì)控制策略優(yōu)化模型的優(yōu)化求解，其擁有強(qiáng)大的數(shù)值計(jì)算性能，并且能夠通過(guò)各種工具箱擴(kuò)展功能。

4 實(shí)例仿真及結(jié)果分析

本文以某企業(yè)作為實(shí)證對(duì)象。該企業(yè)的產(chǎn)品在100周內(nèi)的需求量如表1所示，100次訂貨提前期統(tǒng)計(jì)數(shù)據(jù)如表2所示，而該產(chǎn)品每周的單位訂貨成本為單位庫(kù)存持有成本為單位缺貨成本為最小顧客滿意度。MADS的最大代數(shù)為60，網(wǎng)格閥值為1e-06。

表1 產(chǎn)品每周需求量統(tǒng)計(jì)表

表2 產(chǎn)品每周訂貨提前期統(tǒng)計(jì)表

MADS的優(yōu)化求解過(guò)程如圖1和圖2所示。從圖1可以看到目標(biāo)函數(shù)值隨著算法迭代過(guò)程不斷地減小，而從圖2可以看到當(dāng)目標(biāo)函數(shù)值得到提高時(shí)網(wǎng)格尺寸在擴(kuò)大，否則雖小，且可以知道算法停止是由于網(wǎng)格尺寸低于網(wǎng)格閥值(1e-06)。SID的優(yōu)化求解結(jié)果見(jiàn)表3。利用MADS對(duì)SID進(jìn)行優(yōu)化求解，目標(biāo)函數(shù)值 取得了一個(gè)滿意的優(yōu)化值，而指標(biāo) 也滿足了大于85%的約束。

圖1 目標(biāo)函數(shù)值變化過(guò)程

圖2 網(wǎng)格尺寸變化過(guò)程

表3 優(yōu)化求解結(jié)果

5 結(jié)語(yǔ)

本文基于網(wǎng)格自適應(yīng)直接搜索，研究了不確定市場(chǎng)需求和訂貨提前期條件下的庫(kù)存決策問(wèn)題。首先建立隨機(jī)庫(kù)存決策模型；然后提出一種基于網(wǎng)格自適應(yīng)直接搜索的求解方法；最后進(jìn)行仿真求解并驗(yàn)證了模型解的收斂性。本文的貢獻(xiàn)在于，一方面豐富了隨機(jī)庫(kù)存決策問(wèn)題的研究，另一方面提出了一種基于網(wǎng)格自適應(yīng)直接搜索算法的求解方法，對(duì)存在隨機(jī)因素的復(fù)雜系統(tǒng)管理決策具有較好的借鑒意義。

[1] 胡運(yùn)權(quán),郭耀煌.運(yùn)籌學(xué)教程[M].北京:清華大學(xué)出版社,2007.

[2] 胡幼華,潘蔭榮,孫強(qiáng).FIFO存貯隊(duì)列管理的隨機(jī)庫(kù)存系統(tǒng)的仿真模型[J].華東師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2003(03).

[3] 姜昌華,胡幼華.基于遺傳算法的隨機(jī)(s，S)庫(kù)存系統(tǒng)仿真優(yōu)化[J].華東師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2006(03).

[4] Deng G.Simulation-based optimization[D].UNIVERSITY OF WISCONSIN MADISON,2007.

[5] Audet C,Dennis Jr J E.Mesh adaptive direct search algorithms for constrained optimization[J].SIAM Journal on optimization,2006,17(1).

[6] 馮穎,張炎治.隨機(jī)需求下考慮訂貨提前期的易變質(zhì)產(chǎn)品(r,Q)庫(kù)存策略研究[J].中國(guó)管理科學(xué),2012(S2).

[7] Lewis R M,Torczon V,Trosset M W.Why pattern search works[R].Institute for computer applications in Science and engineering hampton va,1998.