晏榆洋 張浩 帥培

摘 要：當(dāng)今，世界經(jīng)濟(jì)形成命運(yùn)共同體，各國(guó)各地的貿(mào)易往來(lái)非常頻繁。物流產(chǎn)業(yè)作為供應(yīng)鏈的重要組成部分，也迎來(lái)快速發(fā)展。研究運(yùn)輸網(wǎng)絡(luò)最大流問(wèn)題成為許多學(xué)者關(guān)注的焦點(diǎn)?，F(xiàn)實(shí)生產(chǎn)生活中，某地區(qū)有一公司需將貨物從配送中心運(yùn)送至倉(cāng)庫(kù)儲(chǔ)存，在運(yùn)輸過(guò)程中，物流車會(huì)遇到若干個(gè)路口，因?yàn)槊慷温烦痰能囕v承載量和目前平均通過(guò)量各有不同，因此，文章通過(guò)建立規(guī)劃建模求解，得出貨物運(yùn)輸效率最大的研究結(jié)果，以期在實(shí)際物流運(yùn)輸環(huán)節(jié)中節(jié)約大量的成本。

關(guān)鍵詞：供應(yīng)鏈；網(wǎng)絡(luò)最大流；線性規(guī)劃模型；方案研究

中圖分類號(hào)：F275；U491文獻(xiàn)標(biāo)志碼：ADOI：10.13714/j.cnki.1002-3100.2024.08.002

Abstract： Today， the world economy is a community of shared future， and trade between countries and regions is very frequent. As an important part of the supply chain， the logistics industry has also ushered in rapid development. Research on the maximum flow problem of transportation networks has become a problem for many scholars to study. In real life， a company in a certain region needs to transport goods from the distribution center to the warehouse for storage. During the transportation process， the logistics vehicle will encounter several intersections. Because the vehicle capacity and current average throughput of each section of the road are different， this article establishes a planning modeling solution to obtain the research result of maximizing the efficiency of goods transportation， which can save a lot of costs in practical logistics transportation.

Key words： supply chain; network maximum flow; linear programming model; program research

1 ? ?問(wèn)題背景

在日常生活中，許許多多的系統(tǒng)都涉及到流量問(wèn)題。例如，運(yùn)輸系統(tǒng)中有車輛流量，供水系統(tǒng)中有水流量，控制系統(tǒng)中有信息流量，金融系統(tǒng)中有現(xiàn)金流量等。網(wǎng)絡(luò)流量是指在指定的時(shí)間段內(nèi)通過(guò)道路某一地點(diǎn)或某一車道的實(shí)體數(shù)量。網(wǎng)絡(luò)最大流問(wèn)題是一種組合最優(yōu)化問(wèn)題，就是要討論如何充分利用現(xiàn)有資源，使運(yùn)輸?shù)牧髁孔畲螅_(dá)到最佳的效果。在交通網(wǎng)絡(luò)系統(tǒng)中，路段或道路可以用邊來(lái)刻畫(huà)，流量就是路段的車流量，容量就是路段可承受的最大車流量。網(wǎng)絡(luò)最大流問(wèn)題就是求從配送中心可以發(fā)多少車輛，同時(shí)還要不超過(guò)任何一條車輛途經(jīng)路段的容量限制，而且每個(gè)節(jié)點(diǎn)的進(jìn)出流量守恒。學(xué)者張豐等[1]研究解決了無(wú)環(huán)路的網(wǎng)絡(luò)最大流問(wèn)題，給出一種運(yùn)用最小截原理來(lái)求解的圖上作業(yè)法及該算法的理論依據(jù)與證明，并通過(guò)舉例說(shuō)明該算法的簡(jiǎn)便性與有效性。該算法能直觀地求出最大流和最小截，比使用教材上提到的其他方法節(jié)省大量計(jì)算時(shí)間。郭鑫龍[2]研究如何在這些限制條件下，盡可能地提高對(duì)網(wǎng)絡(luò)的利用率，減小資源消耗，通過(guò)對(duì)幾種最大流算法進(jìn)行介紹，并分析比較各自性能，以便在特定的應(yīng)用環(huán)境下選用合適的網(wǎng)絡(luò)最大流算法來(lái)解決相應(yīng)的問(wèn)題。謝凡榮[3]為了便于建立與網(wǎng)絡(luò)最大流問(wèn)題有關(guān)的決策支持系統(tǒng)，給出一個(gè)求解網(wǎng)絡(luò)最大流問(wèn)題的數(shù)值算法，證明算法的理論依據(jù)，并舉例說(shuō)明算法的應(yīng)用。該算法能求出網(wǎng)絡(luò)最大流和最小截，并具有易于編程、收斂性好等優(yōu)點(diǎn)，大量數(shù)值實(shí)驗(yàn)表明該算法非常實(shí)用有效。張超等[4]給了一個(gè)基于Ford-Fulkerson算法求最大流的思路，對(duì)有流量需求的分品種容量限制的運(yùn)輸網(wǎng)絡(luò)構(gòu)造最大流算法，將有流量需求的轉(zhuǎn)運(yùn)節(jié)點(diǎn)分為轉(zhuǎn)運(yùn)節(jié)點(diǎn)和匯節(jié)點(diǎn)，同時(shí)構(gòu)建單源單匯，尋找增流鏈進(jìn)行流量調(diào)整。同時(shí)，通過(guò)示例對(duì)算法進(jìn)行驗(yàn)證，計(jì)算滿足流量需求和分品種容量限制的運(yùn)輸網(wǎng)絡(luò)的最大流。

現(xiàn)實(shí)生產(chǎn)生活中，某地區(qū)有一公司需要將貨物從配送中心運(yùn)送至倉(cāng)庫(kù)儲(chǔ)存，在運(yùn)輸過(guò)程中，物流車會(huì)遇到若干個(gè)路口，因?yàn)槊慷温烦痰能囕v承載量和目前平均通過(guò)量各有不同，因此，本文通過(guò)建立規(guī)劃建模求解，得出貨物運(yùn)輸效率最大的研究方法就顯得非常有意義[3]。當(dāng)前，在某市東部區(qū)域有一公司的配送中心，將派出運(yùn)輸車把貨物送到本市西部區(qū)域倉(cāng)庫(kù)儲(chǔ)存，其交通線路圖如圖1所示。

根據(jù)該市交通運(yùn)輸部門(mén)統(tǒng)計(jì)，配送中心到倉(cāng)庫(kù)各交通路口的最大允許車流量和日平均車流量如表1所示，括號(hào)里第一個(gè)數(shù)字代表該公路最大允許的車流量（路段容量），第二個(gè)數(shù)字表示當(dāng)下的車流量。

2 ? ?問(wèn)題分析

根據(jù)上述實(shí)際問(wèn)題分析，不妨將該問(wèn)題轉(zhuǎn)化為數(shù)學(xué)問(wèn)題處理。該運(yùn)輸問(wèn)題的處理和解決屬于優(yōu)化模型中的線性規(guī)劃模型，目標(biāo)顯然是運(yùn)輸網(wǎng)絡(luò)流入量或流出量最大。在運(yùn)輸過(guò)程中，不妨把這7個(gè)地理位置看成是7個(gè)網(wǎng)絡(luò)流節(jié)點(diǎn)，配送中心看成是起點(diǎn)，倉(cāng)庫(kù)看成是運(yùn)輸?shù)慕K點(diǎn)。同時(shí)，滿足4個(gè)約束條件。一是每個(gè)路段通行的最大流量不大于路段容量，那么12條路段就可以得到12個(gè)約束條件。二是滿足流量守恒約束條件，每個(gè)路口流入的車流量等于該路口流出的車流量。即路口1流入的車流量等于該路口流出的車流量，路口2流入的車流量等于該路口流出的車流量，路口3流入的車流量等于該路口流出的車流量，路口4流入的車流量等于該路口流出的車流量，路口5流入的車流量等于該路口流出的車流量。三是整個(gè)網(wǎng)絡(luò)流入量的和與流出量的和相等。四是每個(gè)路段上的流量一定是非負(fù)的[4]。然后利用Lingo軟件解除最優(yōu)解，得到運(yùn)輸問(wèn)題的處理和解決最優(yōu)方案。

3 ? ?模型的建立與求解

3.1 ? ?模型建立準(zhǔn)備

將配送中心、倉(cāng)庫(kù)、路口1、路口2、路口3、路口4、路口5用數(shù)學(xué)符號(hào)表示，如表2所示。

不妨將配送中心到倉(cāng)庫(kù)交通線路和配送中心到倉(cāng)庫(kù)各交通路口的最大允許的車流量及日平均車流量用運(yùn)輸網(wǎng)絡(luò)圖表示，如圖2所示。其中，括號(hào)里第一個(gè)數(shù)字代表該公路最大允許的車流量（路段容量），第二個(gè)數(shù)字表示當(dāng)下的車流量，箭頭表示車輛運(yùn)行的方向。

3.2 ? ?模型建立

為使網(wǎng)絡(luò)流入量和或流出量和最大，綜合考慮路段最大流量約束、每段路流量守恒約束以及整個(gè)網(wǎng)絡(luò)流量約束，建立如下規(guī)劃模型。

3.2.1 ? ?目標(biāo)函數(shù)的確定

設(shè)fij（i=1，2，3，4，5，6，7；j=1，2，3，4，5，6，7）表示各路段邊的最大流量為決策變量。建立線性規(guī)劃模型，選擇流入量和的最大化為問(wèn)題目標(biāo)，則目標(biāo)函數(shù)為：

max z=f12+f13。

式中：max z表示網(wǎng)絡(luò)流入量和或流出量和最大，f12表示配送中心到路口1的最大流量，f13表示配送中心到路口2的最大流量。

3.2.2 ? ?每個(gè)路段要求的最大流量不大于路段容量，12個(gè)路段有12個(gè)約束條件

f12≤13 ? ? ?f36≤5

f13≤9 ? ? ? ?f45≤13

f24≤6 ? ? ? ?f46≤4

f25≤5 ? ? ? ?f47≤4

f32≤4 ? ? ? ?f57≤9

f34≤5 ? ? ? ?f67≤10

3.2.3 ? ?每段路流量守恒約束

f12+f23=f24+f25

f13=f32+f34+f36

f24+f34=f45+f46+f47

f25+f45=f57

f36+f46=f67

3.2.4 ? ?整個(gè)網(wǎng)絡(luò)流入量的和要與流出量的和相等，也是遵循流量守恒定律

f57+f47+f67=f12+f13

3.2.5 ? ?每個(gè)路段上的流量非負(fù)約束

fij≥0，i=1，2，3，4，5，6，7；j=1，2，3，4，5，6，7

綜上所述，運(yùn)輸網(wǎng)絡(luò)最大流的模型如下。

max z=f12+f13

f12+f13=f24+f25

f13=f32+f34+f36

f24+f34=f45+f46+f47

f25+f45=f57

f36+f46=f67

f57+f47+f67=f12+f13

f12≤13 ? ? ?f36≤5

f13≤9 ? ? ? ?f45≤13

f24≤6 ? ? ? ?f46≤4

f25≤5 ? ? ? ?f47≤4

f32≤4 ? ? ? ?f57≤9

f34≤5 ? ? ? ?f67≤10

3.3 ? ?模型的求解

對(duì)于上述規(guī)劃模型，可以使用Lingo軟件編程求解。解得z=20，即網(wǎng)絡(luò)最大流為20，也就是說(shuō)如果該區(qū)域流入量大于20，網(wǎng)絡(luò)可能發(fā)生擁堵，只要小于20，就能保證不堵車。另外，解得f12=11，f13=9，f24=6，f25=5，f34=4，f36=5，f45=2，f46=4，f47=4，f57=7，f67=9。即配送中心到路口1的最大流量為11，路口1到路口2的最大流量為9，路口1到路口3的最大流量為6，路口1到路口4的最大流量為5，路口2到路口3的最大流量為4，路口2到路口5的最大流量為5，路口3到路口4的最大流量為2，路口3到路口5的最大流量為4，路口3到路口6的最大流量為4，路口4到路口6的最大流量為7，路口5到倉(cāng)庫(kù)的最大流量為9。由于整體網(wǎng)絡(luò)中的流量守恒和相互約束等因素，各路段求出的流量盡管都小于或者等于路段容量，但是已經(jīng)是該路段的最大流量[5]。

4 ? ?結(jié)果分析與推廣

本文建立的模型與實(shí)際緊密聯(lián)合，結(jié)合實(shí)際建立規(guī)劃建模求解，其模型的結(jié)果與實(shí)際相符，這使模型貼近實(shí)際，通用性、推廣性較強(qiáng)；模型原理簡(jiǎn)單明了，容易理解與運(yùn)用；模型的建立根據(jù)實(shí)際問(wèn)題要求，得到的模型可信度較高[6]。當(dāng)然，該線性規(guī)劃模型還可以有其他很多解法，比如可以用EXCEL來(lái)解，先構(gòu)建模型框架，將目標(biāo)函數(shù)和約束條件依次放入EXCEL中，然后運(yùn)用規(guī)劃求解工具求解，選擇求解方法為“單純線性規(guī)劃”，即可求解到結(jié)果。比較幾種方法，建立規(guī)劃模型不失為一種較為理想的解決問(wèn)題的方法。

參考文獻(xiàn)：

[1] 張豐，羅罕勛．一類網(wǎng)絡(luò)最大流問(wèn)題的簡(jiǎn)便算法[J]．中國(guó)科技信息，2009（7）：265-266.

[2] 郭鑫龍．幾類求解最大流問(wèn)題算法在運(yùn)輸問(wèn)題中的應(yīng)用[J]．電子制作，2015（18）：50.

[3] 謝凡榮．求解網(wǎng)絡(luò)最大流問(wèn)題的一個(gè)算法[J]．運(yùn)籌與管理，2004（4）：37-40.

[4] 張超，胡振威．有流量需求和分品種容量限制的運(yùn)輸網(wǎng)絡(luò)最大流算法[J]．交通運(yùn)輸工程與信息學(xué)報(bào)，2017，15（3）：121-127.

[5] 韓中庚．?dāng)?shù)學(xué)建模實(shí)用教程[M]．北京：高等教育出版社，2012．

[6] 孫君，鐘茂林，楊葉勇，等．供應(yīng)鏈數(shù)據(jù)分析[M]．北京：清華大學(xué)出版社，2021.