王怡青

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

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

王怡青

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

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

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

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

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

1 問題描述和模型的建立

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

(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—在整個(gè)計(jì)劃范圍T內(nèi)總共的訂貨階段個(gè)數(shù)，Di—第i個(gè)階段內(nèi)對物品的需求量且各個(gè)階段Di不同，Φ—在整個(gè)時(shí)間周期t內(nèi)的資源約束量，是一個(gè)常數(shù)；決策變量有Vi—第i個(gè)階段末的物品庫存量，Qi—第i個(gè)階段初的訂貨量.

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

2 改進(jìn)的WW算法和問題擴(kuò)展

2.1改進(jìn)的WW算法

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

(8)

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

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

(9)

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

2.2問題擴(kuò)展

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

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

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

3 數(shù)值算例

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

表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個(gè)和280個(gè)單位.

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

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

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

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

4 結(jié)束語

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

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

[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ā)式算法實(shí)現(xiàn)變質(zhì)庫存管理模型[J].瓊州學(xué)院學(xué)報(bào)，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