最小費用最大流理論在救災物資運輸模型中的應用

洪玲玲

摘 要：在保證救災物資快速調運的情況下且滿足各受災地的需求，使總的費用最小。根據實際情況建立相應的運輸問題的數學模型，用最小費用最大流理論求解。當給出問題中所涉及的所有參數的具體數值，該模型就可以用Mathematica或者LINDO軟件來求解，得到問題的最優救災物資調運方案，該問題具有很好的通用性和實用性。

關鍵詞：最小費用最大流；救災物資；運輸規劃

一、問題的背景

我國是自然災害多發的國家之一。因此嚴重的自然災害一旦發生，就需要緊急調運大量的救災物資，用于搶險救災，所以如何快速調運就是一個需要研究的實際問題。在實際中，各種物資的儲存地與受災地的位置不同、距離不同，物資的需求量也不同，有時或許還需要經過中轉站等情況。當然，在救災物資的調運過程中，包括運輸和中轉等都是需要成本的。于是，怎么樣才能在保證快速調運的情況下，使總的費用最小。

二、問題的提出

因某地區發生了嚴重的自然災害，需要緊急調運一批救災物資，現在所掌握的情況是共有位于m個不同地方的倉庫存有該種物資，并且第i個倉庫的儲存量為ai（i=1，2，…m），根據不同受災地的實際需求，共有n個受災地需要這些物資，且第j個受災地的需求量為bj（j=1，2，…n）。已知要將這批救災物資從各個儲存倉庫運送到各受災地時途中都需要經過個中轉站之一，每啟用一次第個中轉站（無論轉運量多少）均發生固定費用fk（k=1，2，…p），且已知在要求的時間內第k個中轉站的最大轉運量為ck（k=1，2，…p），用dik和ekj分別表示從第i個儲存倉庫到第k個中轉站和從第個中轉站到第j個受災地的運輸費用。現在的問題是如何確定一個方案來快速調運這批救災物資，使得總的費用最少。

三、問題的分析

對問題進行分析可知，這個問題是一個比較復雜的有中轉站的運輸問題。在該問題中所產生的費用來自3個方面，即從各個儲存地到某個中轉站的運輸費用、從中轉站到各個受災地的運輸費用和每個中轉站的啟用費用，因此這個問題的優化目標為3個方面費用之和的最小化。為了建立問題的數學模型引入如下的決策變量：用xik表示從第i個儲存倉庫到第k個中轉站的轉運物資數量；用yki表示從第k個中轉站到第j個受災地的運輸物資數量；用lk表示0-1變量，當啟用第k個中轉站時取值為1，當不啟用第k個中轉站時取值為0.

四、模型的建立與求解

（一）模型的建立。

（二）模型求解。求解該不平衡的運輸問題有兩種方法。一是用運輸單純形法，二是用網絡流中的最小費用最大流思想。在這里主要介紹最小費用最大流求解運輸問題。

最小費用最大流的實質：將問題轉化為最短路問題求解，即能求解救災物資的快速調運問題。

定義：設f是一個可行流，如果存在一條從發點vs到收點vt的鏈，滿足：（1）所有前向弧上fij0，則該鏈稱為增廣鏈，記為μ，前向弧集合記為μ+，后向弧集合記為μ-。定理：設f是最小費用流，而μ是關于f的所有增廣鏈中費用最小的一條，則在μ上對f進行調整后所得到的新流仍是最小費用流。

五、模型的評價

這里給出了具有一般意義的運輸規劃模型，如果能夠給出問題中的所有參數的具體數值，該模型就可以用Mathematica或者LINDO軟件來求解，得到問題的最優救災物資的調運方案。該問題具有很好的通用性和實用性，在實際中可以根據災情的變化及最低需求量來改變運輸方案。

參考文獻：

[1] 熊偉. 運籌學[M]. 北京：機械工業出版社，2009.9.

[2] 邱攀，胡圣能. 網絡流理論在地震救災物資運輸模型中的應用[J]. 物流科技，2010年第三期.