王怡青

(華北水利水電大學 軟件學院，河南 鄭州 450045)

資源能力受限的需求非平穩(wěn)有限階段訂貨模型

王怡青

(華北水利水電大學 軟件學院，河南 鄭州 450045)

通過對Wagner-Whitin方法的約束條件擴展，得到了改進的Wagner-Whitin方法，使其能夠解決資源能力受限的需求非平穩(wěn)訂貨問題.對無資源受限的需求非平穩(wěn)訂貨、資源約束恒定的需求非平穩(wěn)訂貨和資源約束周期變化的需求非平穩(wěn)訂貨3種情況進行實例仿真和數(shù)值分析，得出在無資源約束時訂貨成本最小，隨著資源約束量限度的增加，訂貨成本會階段性減少等結(jié)論.

資源能力受限；需求非平穩(wěn)；Wagner-Whitin；有限階段訂貨

訂貨批量問題[1]是企業(yè)在制定訂貨計劃時，確定在給定計劃范圍T內(nèi)的各個訂貨時間段的物資訂貨量問題.EOQ經(jīng)濟訂貨模型[2]是解決該問題的著名方法，但前提是物資的需求量恒定不變.企業(yè)在制定物資供應計劃的過程中，會先參考由其他部門提供的物資需求計劃，此時的物資需求計劃往往都是隨著工程進度不斷變化的，這時便不能用經(jīng)典的EOQ經(jīng)濟訂貨模型來制定相應的訂貨計劃.對于這種需求非平穩(wěn)的訂貨問題，1958年, Wagner和Whitin提出了動態(tài)批量問題的動態(tài)規(guī)劃算法即Wagner-Whitin方法[3-4](以下簡稱WW算法)，它是解決此類問題的最優(yōu)方法.但在有些情況下，會出現(xiàn)資源緊張或供應商供應能力不足的情況，此時企業(yè)在制定供應計劃時會考慮資源能力的約束，而WW算法只能解決無資源約束下的需求非平穩(wěn)訂貨問題.

本研究的主要工作就是在WW算法的基礎上進行新的約束條件擴展得到改進的WW算法，使其能夠解決有資源約束的需求非平穩(wěn)訂貨問題.同時，考慮到實際的資源約束情況，對資源約束進行分類研究，即資源約束恒定和資源約束周期變化兩種情況，分別給出相應的算法.結(jié)合實例進行計算機仿真，對幾種情況進行比較和數(shù)值分析，得出一般性的結(jié)論.

1 問題描述和模型的建立

先考慮資源能力約束恒定的情況，能力受限的資源非平穩(wěn)訂貨問題的數(shù)學模型如下：

(1)

s.t.V0=0,Vi=0.

(2)

(3)

0≤Qi≤Φ,i=1,2,…,t.

(4)

(5)

Hi(Vi)=vrVi.

(6)

Qi為整數(shù),i=1,2,…,t.

(7)

其中,已知量有t—在整個計劃范圍T內(nèi)總共的訂貨階段個數(shù)，Di—第i個階段內(nèi)對物品的需求量且各個階段Di不同，Φ—在整個時間周期t內(nèi)的資源約束量，是一個常數(shù)；決策變量有Vi—第i個階段末的物品庫存量，Qi—第i個階段初的訂貨量.

模型中,式(1)為目標函數(shù)，即總費用成本F(t)最小，包括整個訂貨時間周期t內(nèi)的訂貨費和存儲費；式(2)代表初始和終結(jié)庫存量約束，即要求初始和結(jié)束周期的庫存為0狀態(tài)；式(3)代表庫存量約束，即不允許缺貨；式(4)代表資源能力約束，即每次訂貨量都不得超過Φ；式(5)為第i階段的訂貨費，不隨訂貨量Qi變化；式(6)為第i階段的存儲費，它與單個周期內(nèi)的庫存量Vi成正比，其中vr為單位庫存成本；式(7)保證訂貨量符合實際情況.

2 改進的WW算法和問題擴展

2.1改進的WW算法

在無資源約束的情況下，由WW算法可得到最優(yōu)解,其目標函數(shù)遞推方程為

(8)

WW算法只考慮了無資源能力約束時的訂貨，增加資源能力約束后便不能用來求解.對其進行改進，增加約束條件，在新的求解范圍內(nèi)對目標函數(shù)繼續(xù)運用動態(tài)規(guī)劃的思想進行求解，得到改進的WW方法.具體如下：

同上，用動態(tài)規(guī)劃遞推原理選擇合適的訂貨點q0，如式(9)所示,且q0∈[q′，t]，使F(t)最小，

(9)

經(jīng)過計算,可以得到此算法的計算復雜度為O(T2).

2.2問題擴展

在實際訂貨問題中,還可能會遇到資源能力約束不為常量的情況，即約束量會隨著訂貨時段的推移周期變化.設一次資源能力變化的周期為T，已知Φ(1)，Φ(2)，…，Φ(T),則可行的訂貨時段集合為

此時,目標函數(shù)遞推式變?yōu)?/p>

同上,在可行訂貨時段Q內(nèi)，根據(jù)動態(tài)規(guī)劃遞推法，選擇合適的訂貨點q0，使總費用F(t)最小.

3 數(shù)值算例

上述算法采用C語言實現(xiàn).為了對比3種情況對訂貨策略和庫存量的影響，采用t=12總周期的需求非平穩(wěn)的數(shù)值算例，分別對其進行了仿真，計算結(jié)果分見表1至表4.其中,表1至表3為3種情況的具體訂貨策略，表4為3種情況的最終成本及其他標準的比較.

表1 無資源約束情況下的訂貨策略和庫存量Tab.1 The ordering strategy and inventory with unconstrained of resource

表2 資源約束恒定情況下的訂貨策略和庫存量Tab.2 The ordering strategy and inventory with constant capacitated of resource

注：資源約束恒定量分別為270個和280個單位.

表3 資源約束周期變化情況下的訂貨策略和庫存量Tab.3 The ordering strategy and inventory with periodical changed capacitated of resource

注：資源約束量周期變化為{250,280,200,350,300}，每次變化持續(xù)的單位階段長度T為 { 3，2，4，1，2}.

表1和表2表明：

(1)資源約束量的最小值要能夠滿足當前階段的需求量.具體地說，當資源約束量恒定時，其最小限度要能夠滿足整個計劃范圍內(nèi)的最大需求量；當資源約束量呈周期性變化時，資源約束量要能夠滿足其自身持續(xù)時間內(nèi)的最大需求量，否則無法由改進的WW算法求得結(jié)果.這是由于WW算法本身的前提是最低滿足一個階段的需求量，如果這個條件得不到滿足，動態(tài)規(guī)劃的遞推條件就不能滿足，則無法求解.

(3)存在資源能力約束時(不論恒定或周期變化)，只要資源約束量能夠滿足在無資源約束時所得到的訂貨策略中的最大訂貨量(如此例中在無約束時得到的最大訂貨量為283)，則不論之后資源約束量再如何變大，將不對最后結(jié)果有影響，即得到的訂貨成本和訂貨策略都相同，且均為最優(yōu)值(和無約束情況的結(jié)果相同).這是由于在有資源約束量存在的情況下，一旦資源約束量滿足了無資源約束時所需訂貨量的最大值，則在整個計劃周期內(nèi)，其他階段所需的訂貨量都會被滿足，此時訂貨點的選擇范圍又完全等同于無約束情況，故所得的最終結(jié)果和無約束相同，之后不受資源約束量的影響.

表4 3種情況的計算結(jié)果比較Tab.4 The comparison of the three cases’ calculation results

由表4可知,無資源約束時的訂貨總成本最小；資源約束增加后，總費用成本相應增加.這3種情況下,WW算法所得的結(jié)果均為最優(yōu)值，所得訂貨策略最佳.

4 結(jié)束語

針對資源能力受限的需求非平穩(wěn)訂貨問題進行了研究，通過對經(jīng)典Wagner-Whitin方法進行新的約束條件擴展，使其可以解決該類訂貨問題.同時,分別對資源約束恒定和資源約束周期變化的兩種情況予以討論，提出了相應的數(shù)學模型和解決方法.通過對3種情況的實例仿真分析，可以看出無資源約束時的訂貨成本最?。划敶嬖谫Y源約束量時，隨著約束量限度的增加，訂貨成本減少，但當約束增加到一定程度時，對最后總費用成本沒有影響.

由Wagner-Whitin方法來解決無資源約束和存在資源約束的需求非平穩(wěn)的訂貨問題，所得的結(jié)果都是最優(yōu)解和最優(yōu)訂貨策略.但其計算復雜度比較大，而類似Silver-Meal的啟發(fā)式方法[5]的計算量就相對偏小，求解結(jié)果在某些情況下與Wagner-Whitin方法接近，在后續(xù)的工作中將對這些問題進行深入探討.

[1] Chuda B,Janny M Y L.Inventory lot-sizing with supplier selection[J].Computers & Operations Research,2005(32):1-14.

[2] Silver E A,Peterson R.Decision Systems for Inventory Management and Production Planning[M].New York: John Wiley & Sons,1985.

[3] Wagner H M,Whitin T M.Dynamic version of the economic lot size model[J].Management Science,1958(5):89-96.

[4] 張鯤，滕國庫.巧用Wagner-whitin和啟發(fā)式算法實現(xiàn)變質(zhì)庫存管理模型[J].瓊州學院學報，2009(5):38-40.

[5] Silver E A,Meal H C.A heuristic for selecting lot size quantities for the case of a deterministic time varying rate and discrete opportunities for replenishment[J].Production and Inventory Management,1973(14):64-74.

Limitedstagesuppliesreplenishmentmodelwithresourceconstrainedandvariabledemand

WANG Yi-qing

(SchoolofSoftware,NorthChinaUniversityofWaterResourcesandElectricPower,Zhengzhou450045,China)

This paper studies the limited stage supplies replenishment model with resource constrained and variable demand. We extend the constraints of Wagner-Whitin model so that the improved algorithm can solve the problem. Based on computational experiments and numerical analysis of three conditions of the supplies replenishment problem with variable demand-uncapacitated, constant capacitated, and periodical changed capacitated, we conclude that the cost is minimum when there is no restriction on resource , and the cost will decrease discretely with the increasing restriction.

resource capacitated; variable demand; Wagner-Whitin; limited stage

2014-05-15

王怡青(1983-)，女，河南許昌人，助教，碩士，主要從事系統(tǒng)工程與商業(yè)智能方面的研究.

TP311

A

1674-330X(2014)03-0044-04