基于改進多維規(guī)劃的生產(chǎn)材料智慧訂購問題研究

李景晗　任桓君　陳曉藝　王麗莎

摘? 要：目前，在解決生產(chǎn)型企業(yè)對多個供應(yīng)商的最佳訂購方案進行選取問題時，通常使用多目標規(guī)劃或遺傳算法。這些方法效率普遍不高，尤其是對復(fù)雜問題求解耗時很長。為提高求解效率，提出一種基于改進多維動態(tài)規(guī)劃的智慧訂購方案求解方法，該方法以最小生產(chǎn)成本為目標，通過約束最低生產(chǎn)需求和最大供貨量，建立從二維延展至三維的動態(tài)規(guī)劃模型，再對三維模型進行簡化求解。通過實例驗證了該方法的可行性和有效性。對比遺傳算法，改進多維動態(tài)規(guī)劃在運行效率和模型簡練度上有很大優(yōu)勢。

關(guān)鍵詞：動態(tài)規(guī)劃;材料訂購;方案決策;多維規(guī)劃

中圖分類號：TP31? ? ?文獻標識碼：A

Research on Intelligent Ordering of Production Materials

based on Improved Multi-dimensional Planning

LI Jinghan REN Huanjun CHEN Xiaoyi ?WANG Lisha

Abstract： At present， multi-objective planning or genetic algorithm is usually used by production enterprises to solve the problem of selecting the best ordering plan when facing multiple suppliers. These methods are generally inefficient and take a long time especially for solving complex problems. In order to improve the solution efficiency， this paper proposes an intelligent ordering plan solution based on improved multi-dimensional dynamic planning. Taking minimum production cost as the goal， This solution establishes a dynamic planning extending from 2D to 3D by constraining minimum production demand and maximum supply quantity， and then simplifies the solution of the 3D model. The feasibility and effectiveness of the proposed method are verified by an example. Compared with genetic algorithm， the improved multi-dimensional dynamic planning has great advantages in operation efficiency and model simplicity.

Keywords： dynamic planning; material ordering; plan decision; multi-dimensional planning

1? ?引言（Introduction）

為了滿足生產(chǎn)需求和把控供應(yīng)鏈風(fēng)險，部分生產(chǎn)型企業(yè)采用多供應(yīng)商供貨、多次少量訂購的策略采購生產(chǎn)材料。如果對原材料的訂購工作缺乏足夠重視，可能會導(dǎo)致生產(chǎn)活動受到嚴重影響[1]。目前在解決生產(chǎn)型企業(yè)對多個供應(yīng)商的最佳訂購方案進行選取問題時，通常使用多目標規(guī)劃或遺傳算法[2-3]。這些方法雖然可以得出訂購方案，但解決復(fù)雜問題需要大量計算時間。面對這一問題，改進的動態(tài)規(guī)劃模型脫穎而出。在這類單生產(chǎn)企業(yè)、多供應(yīng)商的情景下，已經(jīng)有鄭廣珠等[4]提出了遺傳算法和動態(tài)規(guī)劃的雙層規(guī)劃方法?？紤]到傳統(tǒng)的動態(tài)規(guī)劃算法無法解決這類復(fù)雜問題，我們將傳統(tǒng)的動態(tài)規(guī)劃模型從二維延展至三維，再對三維模型進行簡化求解。相較于其他方法，該方法具有高效、簡潔、邏輯明晰的特點。

2? ?問題描述（Problem description）

企業(yè)每周的產(chǎn)能為2.82萬立方米，每立方米產(chǎn)品需消耗甲類原材料0.6 立方米，或乙類原材料0.66 立方米，或丙類原材料0.72 立方米。原材料的采購成本直接影響企業(yè)的生產(chǎn)效益，實際中甲類和乙類原材料的采購單價分別比丙類原材料高20%和10%。在生產(chǎn)活動中，供應(yīng)商的數(shù)量往往較多，現(xiàn)有50 個以訂購欲望為目標排序的供應(yīng)商，需要根據(jù)實際情況預(yù)測企業(yè)在未來24 周的訂購方案?？紤]到在實際情況中，單個供應(yīng)商的供應(yīng)能力會隨時間改變，所以設(shè)定每個供應(yīng)商的供貨能力、企業(yè)倉庫存貨的數(shù)量以及企業(yè)生產(chǎn)材料的需求量等因素會隨著周數(shù)W的增加而不斷變化?？梢詮娜我夤?yīng)商訂購生產(chǎn)材料，訂購周期為每周一次。

為了解決上述問題，本文提出了一種基于改進動態(tài)規(guī)劃的生產(chǎn)材料訂購決策方法。

3? 簡化的三維供應(yīng)商選取動態(tài)規(guī)劃模型（Simplified dynamic planning model of 3D supplier selection）

3.1? ?模型建立

傳統(tǒng)的動態(tài)規(guī)劃大多是在二維狀態(tài)變量上實現(xiàn)的，但此問題擁有周數(shù)、供應(yīng)商編號、材料的購置數(shù)量三個狀態(tài)變量，二維模型不能解決該問題。要將模型擴展至三維，就需要引入時間變量作為第三個維度，即以周數(shù)、供應(yīng)商編號、已選貨物量為三維的坐標系，如圖1所示。

3.2? ?模型簡化

由于三維狀態(tài)變量的動態(tài)規(guī)劃在本問題下求解復(fù)雜，不宜直接使用。先在時間不變的前提下，建立以已選貨物量、供應(yīng)商編號為狀態(tài)的二維動態(tài)規(guī)劃，當求得該天在滿足約束條件后成本的最小值時，將周數(shù)W加1，重新進行本次動態(tài)規(guī)劃，從而將三維狀態(tài)變量的動態(tài)規(guī)劃簡化為多個二維狀態(tài)變量的動態(tài)規(guī)劃。

3.3? ?模型定義

（1）動態(tài)規(guī)劃原問題

針對選出的50 個供應(yīng)商，給出未來24 周企業(yè)最經(jīng)濟的材料訂購方案。

（2）動態(tài)規(guī)劃子問題

針對選出的50 個供應(yīng)商，給出未來第W 周企業(yè)最經(jīng)濟的材料訂購方案。

（3）定義狀態(tài)

為未來W 周的最小成本，i為供應(yīng)商編號，k為企業(yè)目前已選貨物量。尤其當

（1）

時就是要求解的原問題。

4? 基于改進動態(tài)規(guī)劃決策模型的實現(xiàn)（Realization of decision model based on improved dynamic planning）

4.1? ?狀態(tài)轉(zhuǎn)移方程約束條件的分析

本問題主要存在兩個約束，分別為生產(chǎn)需求的約束和最大供貨量的約束。其中，生產(chǎn)需求的約束要求為：如果目前已經(jīng)選擇的貨物足夠滿足本周生產(chǎn)需求，那么就不必再購買其他材料;最大供貨量的約束要求為：如果某家供應(yīng)商達到了最大供貨量，那么不能在此供應(yīng)商處繼續(xù)購買，強制轉(zhuǎn)移到下一家供應(yīng)商。

4.2? ? 二維部分的DP數(shù)組狀態(tài)更新

當W固定時，在二維數(shù)組中進行狀態(tài)更新，如圖2所示。此時，狀態(tài)更新一般具有三種方式[5]：

（2）

在本情景中：

（3）

表示從供應(yīng)商i處購買一個貨物。

（4）

表示更改至下一個供應(yīng)商并且購買一個貨物。

（5）

表示轉(zhuǎn)到下一個供應(yīng)商但沒有購買任何貨物。由于要進行擇優(yōu)購買，因此當出現(xiàn)這種情況時即表示滿足約束，跳轉(zhuǎn)至。因此最后一種狀態(tài)轉(zhuǎn)移是不存在的。

由于在更新初始點的狀態(tài)時數(shù)組中不存在任何有效數(shù)值，此時無狀態(tài)轉(zhuǎn)移關(guān)系，因此要對其進行單獨賦值。尤其是當時，狀態(tài)位于邊界，因為此時的狀態(tài)只能從上方轉(zhuǎn)移而來，要對其進行特殊考慮。

4.3? ?三維部分的DP數(shù)組狀態(tài)更新

當滿足的約束條件時，周數(shù)要進行至 周，同時進行下一時間段的狀態(tài)更新，更新原理與4.2部分同理。

由此得到的狀態(tài)轉(zhuǎn)移方程為：

（6）

其中，表示供應(yīng)商提供的材料的單價，A、B、C代表不同優(yōu)先級的供應(yīng)商。

該動態(tài)規(guī)劃的流程圖如圖3所示。

5? ?程序設(shè)計實現(xiàn)（Program design and implementation）

在實際編程的狀態(tài)轉(zhuǎn)移過程中，除了要考慮狀態(tài)轉(zhuǎn)移方程和約束條件，還需要考慮其他一系列量的變化，主要包括上一狀態(tài)的位置信息、已選擇貨物的總生產(chǎn)量、此狀態(tài)累計各供應(yīng)商供貨量。在每次狀態(tài)更新時需要同步更新信息，由于程序采用了結(jié)構(gòu)體的數(shù)據(jù)存儲方式，可以方便地實現(xiàn)上述過程。

如果狀態(tài)轉(zhuǎn)移方程的前者為最小值，則用的值更新上一狀態(tài)的位置信息;用狀態(tài)的貨物總生產(chǎn)量與目前購買商品可生產(chǎn)量之和更新已選擇貨物的總生產(chǎn)量;通過自增目前供應(yīng)商對應(yīng)的存儲量來更新累計各供應(yīng)商供貨量。

如果后者為最小值，則用的值更新上一狀態(tài)的位置信息;用狀態(tài)的貨物總生產(chǎn)量與目前購買商品可生產(chǎn)量之和更新已選擇貨物的總生產(chǎn)量;通過自增目前供應(yīng)商對應(yīng)的存儲量來更新累計各供應(yīng)商供貨量[6-7]。

程序流程圖如圖4所示。

6? ?結(jié)果分析（Result analysis）

將實驗所用的24 家運營商的數(shù)據(jù)分析帶入，為該企業(yè)制定未來24 周每周最經(jīng)濟的原材料訂購方案，并記錄程序運行時間。程序運行結(jié)果中的每一行代表一周，每一列代表一個供應(yīng)商，數(shù)字表示這一周該供應(yīng)商的采購量。由于數(shù)據(jù)量過大，僅展示某次運行的部分結(jié)果，如圖5所示。

圖6為程序運行十次的時間記錄。

程序平均運行時間為1.778 秒，且浮動不顯著。前文提到，本文提出的模型需要解決的一個重要問題就是節(jié)約時間，這也是本文提出方法的目的之一。對比雷紹雍等[8]的基于遺傳算法的裝備采購決策模型，本文方法的程序運行效率有很大優(yōu)勢。從本文的論述過程中可以看出：本文模型具有結(jié)構(gòu)簡練、冗余少和邏輯清晰的特點。

這項成果不但可以幫助生產(chǎn)型企業(yè)在快節(jié)奏、短周期的生產(chǎn)活動中快速做出訂購決策，還有利于加強企業(yè)對供應(yīng)鏈的把控，減少風(fēng)險，調(diào)高抵御風(fēng)險的閾值，最終增加利潤。

7? 可使用場景及優(yōu)勢分析（Available scenarios and advantage analysis）

7.1? ?無人零售

無人零售領(lǐng)域的核心企業(yè)能否高效整合無人零售終端的供應(yīng)鏈網(wǎng)絡(luò)，既影響著消費者的購物體驗，也影響著無人零售模式的長遠發(fā)展[9]。但無人零售終端往往使用低性能的設(shè)備，比如自動柜員機、自動售貨機等，機器性能的局限導(dǎo)致無人零售終端很難使用復(fù)雜模型預(yù)測供貨。本模型先通過現(xiàn)有技術(shù)檢測每個貨物的庫存量和消耗量，再輸入針對使用場景的定制程序。程序可以快速計算出補貨需求和補貨時機并反饋給維護人員。生產(chǎn)材料智慧訂購模型的高效性和低性能要求可以避免因為設(shè)備性能低導(dǎo)致的宕機。這項應(yīng)用也有利于無人零售終端的供應(yīng)鏈資源整合優(yōu)化。

7.2? ?醫(yī)藥采購

目前在我國基層藥店，有時由于供應(yīng)采購不及時會發(fā)生藥品短缺的情況。生產(chǎn)材料智慧訂購模型可以平衡需求量、積壓量和保質(zhì)期三者的關(guān)系，達到藥店利益最大化，病人也可以及時足量地購買藥品。這其實也可以為醫(yī)藥采購云平臺的實現(xiàn)[10]奠定基礎(chǔ)。

7.3? ?中小制造業(yè)輔助決策

新型冠狀病毒肺炎疫情對我國的制造業(yè)造成了一定影響，對生產(chǎn)型企業(yè)提出了新的要求。生產(chǎn)型企業(yè)要生存，就必須拋棄原先的粗放式經(jīng)營概念，對供應(yīng)鏈和庫存的把控要更加精準，建立更加科學(xué)的供應(yīng)體系。這就必然要解決生產(chǎn)材料的訂購決策問題。針對中小型企業(yè)往往難以負擔大型運算設(shè)備，并且訂購決策具有較大的即時性，生產(chǎn)材料智慧訂購模型可以很好地完成這項需求。

7.4? ?其他應(yīng)用

生產(chǎn)材料智慧訂購模型的應(yīng)用是非常廣泛的，除了上文提到的場景外，還可以在智慧農(nóng)業(yè)、小微快餐食品行業(yè)等場景中發(fā)揮作用。

8? ?結(jié)論（Conclusion）

針對生產(chǎn)型企業(yè)的生產(chǎn)材料智慧訂購問題，本文提出了基于改進多維規(guī)劃的解決方法。先建立從二維延展至三維的動態(tài)規(guī)劃模型，再對模型做出局部簡化。該模型在運算單供貨商及24 家供貨商且供貨量隨時間變化的復(fù)雜情景中，其程序平均運行時間為1.778 秒。實驗結(jié)果直接體現(xiàn)出該方法的高效性。由于條件限制，本文取得的企業(yè)數(shù)據(jù)是有限的，要證明算法的普適性還需要進一步的研究。

參考文獻（References）

[1] 馮瑞華，萬勇.歐盟關(guān)鍵原材料需求與供應(yīng)風(fēng)險分析[J].新材料產(chǎn)業(yè)，2021（1）：20-23.

[2] 鐘映竑，張培新.基于FTOPSIS和模糊多目標規(guī)劃的多產(chǎn)品低碳供應(yīng)商選擇方法研究[J].科技管理研究，2014，34（22）：

223-226.

[3] 魏萌.基于改進遺傳算法的原材料智能采購系統(tǒng)的研究與實現(xiàn)[D].沈陽：遼寧大學(xué)，2021.

[4] 鄭廣珠，楊曉英，張瑞敏，等.基于雙層規(guī)劃的多供應(yīng)商物料配送期量優(yōu)化[J].計算機應(yīng)用與軟件，2021，38（7）：87-92.

[5] BELLMAN R. The theory of dynamic programming[J]. Bulletin of the American Mathematical Society， 1954， 60（6）：503-515.

[6] HOWARD R A. Dynamic programming[J]. Management Science， 1966， 12（5）：317-348.

[7] HO W， XU X， DEY P K. Multi-criteria decision making approaches for supplier evaluation and selection： A literature review[J]. European Journal of Operational Research， 2010， 202（1）：16-24.

[8] 雷紹雍，劉靖旭.基于遺傳算法的裝備采購決策優(yōu)化研究[J].中國管理科學(xué)，2020，28（10）：194-200.

[9] 鎖立賽，姚建明，周佳輝.基于顧客需求偏好的面向無人零售終端的供應(yīng)鏈資源整合優(yōu)化研究[J].中國管理科學(xué)，2021，

29（10）：84-95.

[10] 孫朋.基于SaaS模式的醫(yī)藥采購云平臺設(shè)計與實現(xiàn)[D].南京：東南大學(xué)，2019.

作者簡介：

李景晗（2001-），男，本科生.研究領(lǐng)域：計算機與決策分析.

任桓君（2001-），男，本科生.研究領(lǐng)域：土木工程.

陳曉藝（2001-），女，本科生.研究領(lǐng)域：管理科學(xué)與工程.

王麗莎（1980-），女，博士，副教授.研究領(lǐng)域：微分方程及其數(shù)值離散系統(tǒng)的動力學(xué)性質(zhì)研究.本文通信作者.