顧桓瑜

摘要：如何裝載商品使經(jīng)濟(jì)利益最大化是物流配載裝箱問(wèn)題中劃分出的子問(wèn)題。該子問(wèn)題被抽象為0-1背包問(wèn)題，根據(jù)動(dòng)態(tài)規(guī)劃算法建立數(shù)學(xué)模型，分析其優(yōu)點(diǎn)，并用JAVA語(yǔ)言得以實(shí)現(xiàn)。最后給出測(cè)試實(shí)例，得出動(dòng)態(tài)規(guī)劃法具有高效性的特點(diǎn)，該算法可以廣泛使用于物流領(lǐng)域。

關(guān)鍵詞：動(dòng)態(tài)規(guī)劃；裝載問(wèn)題；JAVA語(yǔ)言

中圖分類號(hào)：TP31 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）10-2401-03

Abstract： How to load goods to get maximum economic benefits by manufacturers is a sub-problem divided from logistics distribution.In this paper，the sub-problem is abstracted a 0-1 knapsack problem.We create a mathematical model based on dynamic programming algorithm，and analyze the advantages of the algorithm.Then we use JAVA language to solve the problem.After setting some test datum， the final results show that the dynamic programming method has efficiency，and can be applied widely.

Key words： Dynamic programming； Loading problems； JAVA language

隨著經(jīng)濟(jì)的不斷發(fā)展，各廠商在滿足客戶需求的條件下，利用物流技術(shù)，從備貨、裝箱、配送、存儲(chǔ)等物流配載技術(shù)網(wǎng)中尋求省時(shí)省力的方法，使得資源使用效率得到提高，同時(shí)降低了廠商的成本[1]。

問(wèn)題提出：某廠商每周向校園超市運(yùn)輸一次商品，在小型貨車容量不變且不能超載的約束下，如何裝載商品，使產(chǎn)生的經(jīng)濟(jì)效益最大化？該問(wèn)題是廠家所關(guān)心的，也是本文的關(guān)注點(diǎn)。運(yùn)用動(dòng)態(tài)規(guī)劃方法解決此問(wèn)題，能夠較好地控制企業(yè)的人力資源成本和運(yùn)輸成本，從而提高商業(yè)的競(jìng)爭(zhēng)力。

1 動(dòng)態(tài)規(guī)劃算法簡(jiǎn)介

動(dòng)態(tài)規(guī)劃（dynamic programming）[2]產(chǎn)生于20世紀(jì)50年代，由美國(guó)數(shù)學(xué)家R.E.Bellman等人提出。動(dòng)態(tài)規(guī)劃的思想是把一個(gè)問(wèn)題劃分為具有相關(guān)性的若干子問(wèn)題來(lái)解決，并將各個(gè)子問(wèn)題求解答案和求解方法進(jìn)行保存。如果在之后的處理過(guò)程中還需要用到已解決的子問(wèn)題，則直接調(diào)用答案，從而避免重復(fù)的計(jì)算，節(jié)省了時(shí)間。

在解決實(shí)際問(wèn)題中，我們需要?jiǎng)討B(tài)規(guī)劃出適當(dāng)?shù)募s束條件和遞推關(guān)系，并在各單階段中尋找互相聯(lián)系的因素，依次將每一階段所得的最優(yōu)結(jié)果進(jìn)行存儲(chǔ)。這種階段劃分、自下向上的求解方式需要建立表或數(shù)組才能有效實(shí)施。如圖1所示：

基于動(dòng)態(tài)規(guī)劃法解決的問(wèn)題需要滿足一定的條件，例如：（1）滿足無(wú)后效性，即子問(wèn)題的下一狀態(tài)只與現(xiàn)在狀態(tài)有關(guān)；（2）滿足最優(yōu)性子結(jié)構(gòu)，得出子問(wèn)題的最優(yōu)解；（3）原問(wèn)題可以劃分出多個(gè)擁有關(guān)聯(lián)的子問(wèn)題[3]。

2 模型的建立

廠商向校園超市運(yùn)輸商品的問(wèn)題：已知廠商共有N件商品，每件商品擁有固定的Id號(hào)，Id=i的商品重量為Wi，產(chǎn)生的經(jīng)濟(jì)效益為Vi，貨車的最大載重量為N?，F(xiàn)假設(shè)一個(gè)n維向量Xi=（X1，X2，...Xn）∈{0，1}n，當(dāng)Xi=1時(shí)表明相應(yīng)Id的商品裝入車中；當(dāng)Xi=0時(shí)表明商品未裝入車中。最終得出的結(jié)果為[maxi=1nViXi]，即最大效益值，約束條件為[maxi=1nWiXi]≤N。貨車的載重量是有限的，在這個(gè)上限內(nèi)盡可能裝下商品使經(jīng)濟(jì)效益越高越好。通過(guò)以上分析，此問(wèn)題恰好可以抽象為一個(gè)重量集合、經(jīng)濟(jì)效益集合與貨車載重量分別是Wi={W1，W2，...Wn}，Vi={V1，V2，...Vn}和N的0-1KP問(wèn)題。

在0-1背包問(wèn)題中，物品價(jià)值與體積不隨背包容量的變化而變化[4]。舉例說(shuō)明：假設(shè)有N=3個(gè)物品，總?cè)萘繛?0，體積V[i]={2，4，6}分別對(duì)應(yīng)價(jià)值P[i]={3，7，4}，設(shè)數(shù)組B[i][j]，表示在背包容量為j的條件下，放入第i個(gè)物品后的最大價(jià)值。如下表1所示：

動(dòng)態(tài)規(guī)劃算法易于編程的實(shí)現(xiàn)，雖然需要一定的空間存儲(chǔ)其產(chǎn)生的結(jié)果，但是它的高效性能在測(cè)試中體現(xiàn)出來(lái)。

4 測(cè)試數(shù)據(jù)

假設(shè)廠商貨車載重量為上述的1534，他們所建Commodity表中總共有50件商品，其Id、weight、value的數(shù)據(jù)分別如下所示：

最終得出經(jīng)濟(jì)效益最大值為1904，如圖3所示。

5 結(jié)束語(yǔ)

本文從實(shí)際出發(fā)，給出廠商向校園超市運(yùn)輸商品時(shí)的裝載問(wèn)題，結(jié)合一個(gè)有效的算法——?jiǎng)討B(tài)規(guī)劃算法，利用JAVA語(yǔ)言得以實(shí)現(xiàn)。動(dòng)態(tài)規(guī)劃法有較好的效率和速度，不僅能用于解決裝箱問(wèn)題，而且能夠運(yùn)用于物流配載中的路徑規(guī)劃、資源分配等實(shí)際問(wèn)題，優(yōu)化了企業(yè)資源管理，提高經(jīng)濟(jì)效益，降低資源成本，能夠應(yīng)用于更多的科學(xué)領(lǐng)域中。

參考文獻(xiàn)：

[1] 謝天保，雷西玲，席文玲.物流配送中心配載車輛調(diào)度問(wèn)題研究[J].計(jì)算機(jī)工程與應(yīng)用，2010，36：237-240.

[2] 陳大偉，孫瑞志，向勇，史銀雪.基于流程模式的工作流靜態(tài)規(guī)劃方法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2011（1）：129-132，137.

[3] 厲洋峰.動(dòng)態(tài)規(guī)劃及其在數(shù)學(xué)模型中的應(yīng)用[J].中國(guó)新技術(shù)新產(chǎn)品，2009（16）：244-245.

[4] 王凌，王圣堯，方晨.一種求解多維背包問(wèn)題的混合分布估計(jì)算法[J].控制與決策，2011（8）：1121-1125.