康鵬 劉長龍

摘要：本文通過建立標(biāo)準(zhǔn)的平衡利庫權(quán)值數(shù)據(jù)模型，并引入二分圖多重匹配算法，按照“先利庫、后采購”的原則，多層級開展煤礦物資平衡利庫工作。該平衡利庫功能動態(tài)通盤考慮利庫優(yōu)先級、已利庫數(shù)量、剩余數(shù)量等信息，自動推薦最優(yōu)利庫方案，提高利庫的匹配程度，從而實現(xiàn)的全過程平衡利庫。

Abstract： In the materials inventory balance system， the inventory models and multiple matching algorithm for two partite graph are used to manage the inventory dynamically in multi-level based on the considering of priority， quantity and other factors and help to recommend the best inventory plan in multi-level， multi-component， trans-region and whole process.

關(guān)鍵詞：二分圖;多重匹配;平衡利庫;ERP

Key words： bipartite graph;multidimensional matching;inventory balance;ERP

中圖分類號：F251? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻標(biāo)識碼：A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文章編號：1006-4311（2018）36-0029-03

0? 引言

近年來，隨著社會的不斷進步和煤炭需求的飛速發(fā)展，確保煤礦穩(wěn)定高效運行成為各大煤碳公司工作的重中之重。物資管理作為煤礦建設(shè)和生產(chǎn)過程中不可或缺的一個重要環(huán)節(jié)。大型煤碳集團公司的生產(chǎn)設(shè)備分布地域廣泛，導(dǎo)致煤礦企業(yè)在不同煤礦形成多個庫存地點，各級倉庫保管著各類項目物資、檢修物資、搶修物資和可再利用的拆舊物資等，其中不乏長期未使用的結(jié)余物資，這些物資中常常會因為長期保存而導(dǎo)致使用價值降低或報廢，因此大型煤碳企業(yè)如何減少庫存物資儲備，提高庫存物資利用率，一直是煤碳企業(yè)物資管理部門所追求的目標(biāo)。

1? 平衡利庫及存在問題

大型煤碳企業(yè)按照傳統(tǒng)的異地分散的多庫存管理模式，由于倉庫間的信息交互貧乏，不能最大效率利用存庫間的信息資源， 導(dǎo)致形成了多個庫存物資的信息孤島。平衡利庫針對現(xiàn)有庫存和預(yù)計需求情況， 結(jié)合安全庫存量來決定采購數(shù)量， 其中涉及物資需求管理、庫存管理、采購管理等多個環(huán)節(jié)。

以某大型煤炭集團公司為例， ERP系統(tǒng)已穩(wěn)定運行多年，系統(tǒng)中含有大量的可利庫物資，不僅占用了大量的企業(yè)庫存資金，而且對于倉儲管理也增加了很多工作，不利于企業(yè)的正常運營?？紤]到可利庫物資與需求計劃的匹配情況來看，平衡利庫的匹配功能還有待加強，以便能夠更大程度減少庫存物資數(shù)量，為此不僅能夠充分利用現(xiàn)有庫存物資，增加資金流動性，同時也能降低倉庫的運維成本。通過改造現(xiàn)有平衡利庫功能，利用二分圖匹配算法，尋找最佳路徑，實現(xiàn)最大匹配，從而實現(xiàn) “多層級、多環(huán)節(jié)、跨地區(qū)”的全面平衡利庫，提高庫存物資可利用率，優(yōu)先考慮在庫物資滿足需求計劃，合理安排利庫匹配數(shù)據(jù)，實現(xiàn)企業(yè)利益最大化[1-2]。

2? 二分圖及主要算法簡介

二分圖（G）又稱作二部圖，是圖論中的一種特殊模型，其所有頂點可以分為兩個集合（U，V），并且同一集合中所有點都不相連，并且所有的邊都關(guān)聯(lián)在兩個不同的集合中，這種邊稱為二分圖的匹配。

選擇這樣的邊數(shù)最大的子集稱為圖的最大匹配問題，最大匹配的邊數(shù)稱為最大匹配數(shù)。如果一個匹配中，圖中的每個頂點都和圖中某條邊相關(guān)聯(lián)，則稱此匹配為完全匹配，也稱作完備匹配。

最優(yōu)匹配又稱為帶權(quán)最大匹配，是指在帶有權(quán)值邊的二分圖中，求一個匹配使得匹配邊上的權(quán)值和最大。

求最大匹配的最顯而易見的算法是：首先找出全部匹配，然后保留匹配數(shù)最多的那種方案。但是這個算法的計算量為指數(shù)級計算，極其耗時，因此，需要尋求一種更加高效的算法。目前，求一個二分圖的最佳匹配的普遍算法是KM（Kuhn-Munkres）算法，該算法流程如下：

①初始化可行頂標(biāo)的值;

②用匈牙利算法尋找完備匹配;

③若未找到完備匹配則修改可行頂標(biāo)的值;

④重復(fù)②③直到找到相等子圖的完備匹配為止。

匈牙利算法基于Hall定理中充分性證明的思想，它是二分圖匹配最常見的算法，該算法的核心就是尋找增廣路徑，然后用增廣路徑求二分圖最大匹配的算法。

3? 基于平衡利庫的二分圖多重匹配算法

3.1 平衡利庫功能需求分析

根據(jù)實際調(diào)研結(jié)果，某煤碳集團公司的平衡利庫需求主要包括以下幾方面要求。按照組織結(jié)構(gòu)和地域就近原則。煤礦范疇內(nèi)優(yōu)先平衡利庫，再考慮全公司范圍內(nèi)的平衡利庫。常用的消耗類物資只在本地煤礦進行利庫。其他大型物資根據(jù)不同物資可能有不同的利庫范圍。根據(jù)當(dāng)前用戶操作權(quán)限控制可利庫范圍。

系統(tǒng)要求分析煤礦物資倉儲特點，通盤考慮庫存現(xiàn)有量、安全庫存量，深入研究庫存物資品類、安全庫存、可互替參數(shù)、平衡范圍、調(diào)配距離、運輸方式、堆放養(yǎng)護條件、維護保管年限、淘汰率等利庫影響因素，形成多維度物資平衡利庫的二分圖最優(yōu)匹配算法模型。模擬監(jiān)控實際采購業(yè)務(wù)運轉(zhuǎn)情形，跟蹤業(yè)務(wù)變化，抽象新因子，修正模型，促進模型優(yōu)化。透過該算法，制定調(diào)配原則，實現(xiàn)物資需求計劃自動匹配調(diào)整、增加積壓物資消耗，具體匹配架構(gòu)如圖2所示。

3.2 二分圖多重匹配算法設(shè)計

根據(jù)平衡利庫的需求，主要輸入數(shù)據(jù)包括平衡利庫的初始數(shù)據(jù)、物資需求計劃集、可利庫庫存物資集、當(dāng)前用戶利庫需求等，通過二分圖多重匹配算法能夠計算出平衡利庫最優(yōu)匹配結(jié)果，并根據(jù)倉庫間利庫物資的數(shù)量自動生成倉庫物資調(diào)撥單，系統(tǒng)業(yè)務(wù)流程圖如圖3所示。

根據(jù)平衡利庫的需求，主要輸入數(shù)據(jù)包括平衡利庫的初始數(shù)據(jù)、物資需求計劃集、可利庫庫存物資集、當(dāng)前用戶利庫需求等，通過二分圖多重匹配算法能夠計算出平衡利庫最優(yōu)匹配結(jié)果，并根據(jù)倉庫間利庫物資的數(shù)量自動生成倉庫物資調(diào)撥單。

根據(jù)實際平衡利庫的需求以及工作情況，定義平衡利庫的級別分為五個層次，定義為利庫級別表，高級別利庫可以兼容低級別的利庫范圍。根據(jù)需求需要對不同的物資類型有利庫范圍的限制，因此需要根據(jù)物資類型定義可利庫范圍，定義為物資利庫級別表，高級別利庫可以兼容低級別的利庫范圍?？紤]地域交通等原因，需要記錄倉庫間允許平衡利庫權(quán)值的基礎(chǔ)數(shù)據(jù)，定義為倉庫間利庫級別表。

根據(jù)信息系統(tǒng)可以隨時獲取不同倉庫有可平衡利庫的物資集，可利庫物資集包括所在倉庫、物資類型、數(shù)量、單價等信息。在實際工作中，匯總物資需求計劃之后獲得物資需求計劃集，物資需求計劃集包括需求單位、計劃入庫倉庫、物資類型、需求數(shù)量等信息。根據(jù)需求計劃集的物資類型進行分組，即可遍歷需求計劃集的不同物資類型，即可獲取某類型的物資需求計劃集，設(shè)為物資A的需求計劃集。根據(jù)物資利庫級別表、倉庫間利庫級別表、用戶當(dāng)前平衡利庫等級可獲取所有倉庫間該類型物資的可利庫路徑，再根據(jù)可平衡利庫物資表，即能獲取到物資A的需求計劃集與可平衡利庫物資的邊權(quán)矩陣。根據(jù)邊權(quán)矩陣關(guān)系、庫存數(shù)量、需求數(shù)量即可根據(jù)二分圖多維匹配算法獲取到最優(yōu)匹配結(jié)果。

3.3 基于平衡利庫的二分圖多重匹配算法實現(xiàn)

由于平衡利庫必須確保物資類型精確匹配，因此對于可利庫的物資集以及需求物資集根據(jù)物資類型進行分類，針對每類物資分別進行利庫，為描述簡單，以下算法假設(shè)針對每種相同物資A進行匹配?；跈?quán)矩陣關(guān)系、庫存數(shù)量、需求數(shù)量，以及根據(jù)當(dāng)前用戶利庫級別，通過二分圖多重匹配算法能夠獲取到平衡利庫結(jié)果集。

①根據(jù)物資需求計劃集按照倉庫進行分組，并根據(jù)原始路徑集的權(quán)值進行排序。

②假設(shè)當(dāng)前平衡利庫結(jié)果為權(quán)值乘以利庫數(shù)量的結(jié)果之和為最大，即當(dāng)前利庫結(jié)果為最優(yōu)的情況，如果按照順序增加一條可利庫路徑以后，利庫結(jié)果仍舊為最優(yōu)結(jié)果，直到增加完所有路徑即可獲取最優(yōu)匹配結(jié)果。具體步驟如下：

1）根據(jù)當(dāng)前需要利庫的路徑取當(dāng)前利庫的倉庫，從該倉庫出發(fā)，根據(jù)可斷開利庫關(guān)系以及斷開后可再利庫的路徑，直到損失的權(quán)值大于當(dāng)前利庫路徑的權(quán)值為止。

2）根據(jù)權(quán)重損失最少的關(guān)系獲取該路徑可以利庫的最大數(shù)量，如果可斷開關(guān)系的利庫最大數(shù)量大于等于需要利庫關(guān)系的數(shù)量完成利庫，否則執(zhí)行第三步。

3）根據(jù)可以利庫的最大數(shù)量現(xiàn)行利庫，調(diào)整需要利庫路徑的需求數(shù)量，重復(fù)執(zhí)行第一步，直到需要利庫數(shù)量為0或者權(quán)重衰減數(shù)據(jù)集為空。

4? 平衡利庫功能實現(xiàn)

基于二分圖多重匹配算法的平衡利庫功能根據(jù)物資分類確定利庫范圍以及根據(jù)運輸成本確定利庫權(quán)重等因素，確定可利庫匹配關(guān)系的邊權(quán)矩陣基礎(chǔ)數(shù)據(jù)。界定合理的利庫物資范圍，制定利庫地域優(yōu)選級別和原則，實現(xiàn)二分圖多重匹配算法，將單一數(shù)量滿足匹配改造成累計數(shù)匹配，通盤考慮優(yōu)先級、已占用數(shù)量、剩余數(shù)量等信息，并且自動推薦最優(yōu)利庫方案，提高利庫的匹配程度?；贏BAP語言開發(fā)設(shè)計平衡利庫功能以及界面，能夠根據(jù)用戶要求動態(tài)設(shè)置利庫級別以及利庫物資范圍，在操作上實現(xiàn)一鍵執(zhí)行利庫功能，提高界面操作便捷性。系統(tǒng)實現(xiàn)界面如圖4所示。

5? 結(jié)語

基于二分圖多重匹配算法的平衡利庫功能實現(xiàn)平衡利庫按最優(yōu)方式自動匹配物資需求計劃與可利庫物資的關(guān)系，根據(jù)煤碳公司要求實現(xiàn)多級智能利庫，極大提高利庫的匹配程度，減少人工利庫的差錯。

由于能夠自動實現(xiàn)物資需求計劃與可利庫物資之間的多對多的多重匹配，充分利用煤碳公司庫存積壓物資，能夠提升現(xiàn)有積壓庫存物資利用率。優(yōu)化現(xiàn)有平衡利庫功能以及利庫流程，實現(xiàn)一鍵式利庫，同時實現(xiàn)可視化平衡利庫結(jié)果以及自動進行平衡利庫調(diào)撥。

參考文獻：

[1]方泉，康永，董子玉.基于ERP的電力物資平衡利庫系統(tǒng)[J].計算機系統(tǒng)應(yīng)用，2014（23）：70-73.

[2]孫波.淺談物資管理在現(xiàn)代企業(yè)管理中重要作用[J].煤礦現(xiàn)代化，2008（2）：65-66.

[3]王譽霖.加強物資管理 提高經(jīng)濟效益[J].核經(jīng)濟研究，1997（02）.