運輸論法

基本內容

運輸問題：人們在從事生產活動中，不可避免地要進行物資調運工作。如某時期內將生產基地的煤、鋼鐵、糧食等各類物資，分別運到需要這些物資的地區，根據各地的生產量和需要量及各地之間的運輸費用，如何制定一個運輸方案，使總的運輸費用最小。這樣的問題稱為運輸問題。

適用範圍

有些問題表面上與運輸問題沒有多大關係，也可以建立與運輸問題形式相同的數學模型。現已發現的運輸型問題有以下6類：①一般運輸問題，又稱希契科克運輸問題，簡稱H問題。②網路運輸問題，又稱圖上運輸問題，簡稱T問題。③最大流量問題,簡稱F問題。④最短路徑問題，簡稱S問題。⑤任務分配問題，又稱指派問題,簡稱A問題。⑥生產計畫問題，又稱日程計畫問題，簡稱CPS問題。如把產地稱為源（發點），銷地稱為匯(收點)，則任務分配問題、生產計畫問題等運輸型問題的模型也可以歸納成類似上述形式。

求解過程

表上作業法的基本思想是：先設法給出一個初始方案,然後根據確定的判別準則對初始方案進行檢查、調整、改進，直至求出最優方案。表上作業法是求解運輸問題的一種簡化方法，實質是單純形法。具體步驟如下：
1.找初始基可行解。即在 (m

n) 產銷平衡表上給出m+n -1個數字格，不能構成閉迴路，且行和等於產量，列和等於銷售量；
2.求非基變數檢驗數。在表上求出空格的檢驗數，判別是否達到最優解。如果達到最優解，則停止計算，否則轉入下一步；
3.確定換入變數和換出變數，找出新的基可行解，在表上用閉迴路法進行調整。
4.重複2、3步，直到求得最優解為止。
確定初始基可行解

① 方法一：最小元素法

基本思想：就近供應。即從單位運價表中最小的運價開始確定產銷關係，依次類推，直到給出初始方案為止。兩種特殊情況：1.多個元素同時最小，任選一個作基變數。2.對於最小元素，發現該元素所在行的剩餘產量等於該元素所在列的剩餘銷售量。這時在產銷平衡表相應的位置填上一個數，而在單位運價表中就要同時划去一行和一列。為了使調運方案中有數字的格仍為（m + n –1）個，需要在同時划去的行或列的任一空格位置添上一個“0”，這個“0”表示該變數是基變數，只不過它取值為0，即此時的調運方案是一個退化的基可行解。

②方法二：伏格爾法

一產地的產品，假如不能按最小運費就近供應，就考慮次小運費。這就有一個差額，差額越大，說明不能按最小運費調運時，運費增加就越多。因此，對於差額最大處，就優先採用最小運費調運。

③方法三：西北角法

西北角法的基本思想是給運輸表中左上角的變數分配運輸量以確定產銷關係。

最優解的判別

目標函式是要求最小化，所以當所有的非基變數檢驗數全都大於等於 0 時為最優解。求空格檢驗數。
①方法一：閉迴路法

這種方法需要對每一個空格尋找一條閉迴路，並根據閉迴路求出每個空格的檢驗數。當運輸問題中m和n較大時，計算檢驗數的工作量很大。

② 方法二：位勢法

先對初始調運方案求出位勢，然後求各空格的檢驗數。當所有的檢驗數均為非負時，就得到最優方案。如果出現負的檢驗數，則從檢驗數為負的空格出發，作閉迴路，重新計算檢驗數，作進一步調整。用位勢法求檢驗數就是對偶問題的表上作業法。

	A	B	C	D
甲	15	20	9	10
乙	12	16	10	12

	A	B	C	D	產量
甲	15	20	9	10	2
乙	12	16	10	12	2
	1	1	1	1

運輸論法

基本介紹

基本內容

適用範圍

求解過程

舉例

相關詞條

熱門詞條