二分圖多重匹配算法在煤礦物資平衡利庫(kù)中的研究

康鵬 劉長(zhǎng)龍

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

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)鍵詞：二分圖;多重匹配;平衡利庫(kù);ERP

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

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

0? 引言

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

1? 平衡利庫(kù)及存在問(wèn)題

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

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

2? 二分圖及主要算法簡(jiǎn)介

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

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

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

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

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

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

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

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

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

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

3.1 平衡利庫(kù)功能需求分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4? 平衡利庫(kù)功能實(shí)現(xiàn)

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

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

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

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

參考文獻(xiàn)：

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

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

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