航材供需平衡調(diào)運(yùn)問題優(yōu)化研究

劉臣宇，李衛(wèi)靈，孫偉奇 （海軍航空大學(xué) 青島校區(qū)，山東 青島266041）

LIU Chenyu, LI Weiling, SUN Weiqi (Naval Aviation University Qingdao Campus, Qingdao 266041, China)

1 航材運(yùn)輸決策主要解決的兩個(gè)方面問題

（1） 運(yùn)輸方式和運(yùn)輸路線的選擇。在一對(duì)收發(fā)點(diǎn)之間存在著多種可供選擇的運(yùn)輸方式及運(yùn)輸路線的情況下，以航材運(yùn)輸?shù)陌踩浴⒓皶r(shí)性和低費(fèi)用為目標(biāo)，綜合考慮、權(quán)衡利弊，選擇合理的運(yùn)輸方式并確定適當(dāng)?shù)倪\(yùn)輸路線。

（2） 合理調(diào)運(yùn)。在多個(gè)發(fā)貨點(diǎn)和收貨點(diǎn)之間組織一類或多類航材的運(yùn)輸活動(dòng)時(shí)，考慮各種客觀條件的限制，制定出合理的運(yùn)輸方案。

2 運(yùn)輸調(diào)運(yùn)模型及其求解

（1） 調(diào)運(yùn)模型

本文主要研究總供應(yīng)量等于總需求量，稱之為供需平衡運(yùn)輸問題。

假設(shè)某種航材有m個(gè)供應(yīng)點(diǎn)，其供應(yīng)量分別為ai（i=1,…,m）；有n個(gè)需求點(diǎn)，需求量分別為bj（j=1,…,n）從第i個(gè)供應(yīng)點(diǎn)向第j個(gè)需求點(diǎn)運(yùn)送單位航材的運(yùn)費(fèi)為Cij，設(shè)Xij為從供應(yīng)點(diǎn)i向需求點(diǎn)j運(yùn)輸航材的數(shù)量，F(xiàn)為運(yùn)輸總費(fèi)用，則數(shù)學(xué)模型為：

（2） 模型求解

上述模型是一個(gè)線性規(guī)劃模型，含有m×n個(gè)未知數(shù)，由平衡條件可將上述m+n個(gè)方程劃為等價(jià)的m+n-1 個(gè)獨(dú)立方程，可用單純形法求解，但基于這類問題的特殊性，也可通過表上作業(yè)法求解。

表1 是一個(gè)供需平衡表，表上作業(yè)法是依據(jù)單位運(yùn)價(jià)表在供需平衡表上進(jìn)行迭代，確定最優(yōu)方案。

既然運(yùn)輸問題是線性規(guī)劃問題的特例，按照線性規(guī)劃的解法是從m×n個(gè)變量先分離出m+n-1 個(gè)獨(dú)立的變量（m+n個(gè)方程只有m+n-1 個(gè)獨(dú)立方程）作為基變量，其它為非基變量進(jìn)行迭代。運(yùn)輸問題的表上作業(yè)法也是基于這個(gè)思想，為此在供需平衡表中引入閉回路的概念。

所謂閉回路就是能排列成閉合回路的變量集合稱。閉回路的每條邊都是水平或垂直的，每個(gè)頂點(diǎn)是兩條相互垂直邊的相連點(diǎn)，每列（行） 若有頂點(diǎn)，必只有兩個(gè)。有了閉回路的概念，根據(jù)線性規(guī)劃求解的方法就可以確定m+n-1 個(gè)變量是否構(gòu)成基的充要條件為：m+n-1個(gè)變量不含閉回路。根據(jù)這個(gè)思路，可確定初始調(diào)運(yùn)方案。方法是：一個(gè)供應(yīng)點(diǎn)的航材假如不能按最小運(yùn)費(fèi)就近供應(yīng)，就考慮次小運(yùn)費(fèi)，這樣就有一個(gè)差額，差額越大，說明不按最小運(yùn)費(fèi)調(diào)運(yùn)時(shí)，運(yùn)費(fèi)增加越多，因此在差額最大處，就采用最小運(yùn)費(fèi)調(diào)運(yùn)。從行差額或列差額中選出最大者，再對(duì)所選擇的最大行（列） 差，選擇其所在行或列中的最小運(yùn)價(jià)元素，就可確定得到滿足的需求點(diǎn)（或供應(yīng)能力不足的供應(yīng)點(diǎn)），去掉得到滿足需求的列（或供應(yīng)能力不足的行），對(duì)已劃去的列（或行） 得到的新的供需平衡表，用同樣的方法進(jìn)行分配，最后可以得到初始調(diào)運(yùn)方案。

得到初始調(diào)運(yùn)方案后，要檢驗(yàn)初始調(diào)運(yùn)方案是否為最優(yōu)調(diào)運(yùn)方案，方法是應(yīng)用位勢法。即：應(yīng)用σij=Cij-ui-vj（其中：σij為非基變量檢驗(yàn)數(shù)，ui,vj為行和列的位勢） 進(jìn)行檢驗(yàn)，當(dāng)所有非基變量（供需平衡表中的空格） 檢驗(yàn)數(shù)σij的值為正數(shù)時(shí)表明已得到最優(yōu)解，否則再繼續(xù)進(jìn)行調(diào)整。

表1 供需平衡表

表2 單位運(yùn)價(jià)表

3 模型應(yīng)用

假設(shè)從3 個(gè)航材倉庫組織貨源發(fā)往4 個(gè)航材使用單位，航材倉庫供應(yīng)器材量與各航材使用單位需要量以及各地間單位航材運(yùn)價(jià)見表2。Ai表示航材倉庫，Bj表示航材使用單位。由表2 可以看出，這是一個(gè)供需平衡的調(diào)運(yùn)問題。為了使運(yùn)輸費(fèi)用最小，必須找出最優(yōu)運(yùn)輸方案。

其步驟如下：

（1） 確定初始調(diào)運(yùn)方案

第一步：在單位運(yùn)價(jià)表中計(jì)算各行與各列的最小運(yùn)費(fèi)與次最小運(yùn)費(fèi)的差額，并填寫在表的最右列和最下行，見表3。

表3 初始調(diào)運(yùn)方案

第二步：從行差額或列差額中選出最大者，再對(duì)所選擇的最大行（列） 差，選擇其所在行或列中的最小運(yùn)價(jià)元素（如行差中最大為5，選最小元素為2），于是可確定A1供應(yīng)點(diǎn)的航材運(yùn)往需點(diǎn)B1，由于B1的需求為3,A1的供應(yīng)能力為9，B1的需求得到滿足，去掉B1的需求量這一列（若A1的供應(yīng)能力小于B1的需求量，則去掉A1這一行），以示B1已不再參與航材的分配。對(duì)已劃去的列（或行） 得到的新的供需平衡表用同樣的方法進(jìn)行分配，最后得到的數(shù)字為表3 中帶括號(hào)的數(shù)字，即為初始調(diào)運(yùn)方案。

（2） 檢驗(yàn)初始調(diào)運(yùn)方案是否為最優(yōu)調(diào)運(yùn)方案

表4 為得到的初始調(diào)運(yùn)方案。

應(yīng)用位勢法判斷該調(diào)運(yùn)方案是否為最優(yōu)方案。

表4 初始調(diào)運(yùn)方案

表5 調(diào)整方案

空白（非基變量） 檢驗(yàn)數(shù)σ22為負(fù)數(shù)，所以上述初始調(diào)運(yùn)方案不是最優(yōu)方案，需進(jìn)行調(diào)整。X22（=y）為換入變量，X22作為第一個(gè)頂點(diǎn)，以基變量中的點(diǎn)作為其他頂點(diǎn)構(gòu)造閉回路為：X22,X12,X14,X24，其偶數(shù)頂點(diǎn)為X12,X24，調(diào)整量為min（X12,X24）=min（5,5 ）=5，以X12（或X24） 為換出變量，在閉回路中奇數(shù)頂點(diǎn)加上調(diào)整量，偶數(shù)頂點(diǎn)減去調(diào)整量，得新的調(diào)運(yùn)方案如表5 所示。

值得注意的是，在此X12已作為換出變量，調(diào)運(yùn)量為0，不能填在調(diào)運(yùn)方案表中，而X24雖然調(diào)運(yùn)量為0，但X24是作為基變量出現(xiàn)在調(diào)運(yùn)方案中的，必須填上（否則新基變量就少于m+n-1 個(gè)）。

對(duì)新得到的調(diào)運(yùn)方案再進(jìn)行檢驗(yàn)、調(diào)整，直到所有的空白檢驗(yàn)數(shù)為非負(fù)，對(duì)表5 的調(diào)運(yùn)方案進(jìn)行檢驗(yàn)，由σij=Cij-（ui+vj）=0，再次確定新ui,vj的值：

根據(jù)新得的ui,vj，求出空白檢驗(yàn)數(shù)：

同理有：

即所有空格檢驗(yàn)數(shù)均為非負(fù)數(shù)，因此上述調(diào)運(yùn)方案為最優(yōu)方案，其最小目標(biāo)值為：

4 注意事項(xiàng)

在確定初始調(diào)運(yùn)方案時(shí)，當(dāng)確定Ai調(diào)給Bj時(shí)，如果存在ai=bj，則確定調(diào)運(yùn)量為ai，同時(shí)劃去Ai行與Bj列，并在Ai行（或Bji列） 任意一空格填上數(shù)字0，保證基變量的個(gè)數(shù)為m+n-1 個(gè)；如表中只剩下一個(gè)未劃去的運(yùn)價(jià)元素時(shí)，只填一個(gè)調(diào)運(yùn)量，劃去該行和該列。此時(shí)共劃去m+n條線，填入m+n-1 個(gè)數(shù)，即給出m+n-1 個(gè)基變量。