航材供需平衡調運問題優化研究

劉臣宇，李衛靈，孫偉奇 （海軍航空大學 青島校區，山東 青島266041）

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

1 航材運輸決策主要解決的兩個方面問題

（1） 運輸方式和運輸路線的選擇。在一對收發點之間存在著多種可供選擇的運輸方式及運輸路線的情況下，以航材運輸的安全性、及時性和低費用為目標，綜合考慮、權衡利弊，選擇合理的運輸方式并確定適當的運輸路線。

（2） 合理調運。在多個發貨點和收貨點之間組織一類或多類航材的運輸活動時，考慮各種客觀條件的限制，制定出合理的運輸方案。

2 運輸調運模型及其求解

（1） 調運模型

本文主要研究總供應量等于總需求量，稱之為供需平衡運輸問題。

假設某種航材有m個供應點，其供應量分別為ai（i=1,…,m）；有n個需求點，需求量分別為bj（j=1,…,n）從第i個供應點向第j個需求點運送單位航材的運費為Cij，設Xij為從供應點i向需求點j運輸航材的數量，F為運輸總費用，則數學模型為：

（2） 模型求解

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

表1 是一個供需平衡表，表上作業法是依據單位運價表在供需平衡表上進行迭代，確定最優方案。

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

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

得到初始調運方案后，要檢驗初始調運方案是否為最優調運方案，方法是應用位勢法。即：應用σij=Cij-ui-vj（其中：σij為非基變量檢驗數，ui,vj為行和列的位勢） 進行檢驗，當所有非基變量（供需平衡表中的空格） 檢驗數σij的值為正數時表明已得到最優解，否則再繼續進行調整。

表1 供需平衡表

表2 單位運價表

3 模型應用

假設從3 個航材倉庫組織貨源發往4 個航材使用單位，航材倉庫供應器材量與各航材使用單位需要量以及各地間單位航材運價見表2。Ai表示航材倉庫，Bj表示航材使用單位。由表2 可以看出，這是一個供需平衡的調運問題。為了使運輸費用最小，必須找出最優運輸方案。

其步驟如下：

（1） 確定初始調運方案

第一步：在單位運價表中計算各行與各列的最小運費與次最小運費的差額，并填寫在表的最右列和最下行，見表3。

表3 初始調運方案

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

（2） 檢驗初始調運方案是否為最優調運方案

表4 為得到的初始調運方案。

應用位勢法判斷該調運方案是否為最優方案。

表4 初始調運方案

表5 調整方案

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

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

對新得到的調運方案再進行檢驗、調整，直到所有的空白檢驗數為非負，對表5 的調運方案進行檢驗，由σij=Cij-（ui+vj）=0，再次確定新ui,vj的值：

根據新得的ui,vj，求出空白檢驗數：

同理有：

即所有空格檢驗數均為非負數，因此上述調運方案為最優方案，其最小目標值為：

4 注意事項

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