一. 運輸問題

設有 m 個產地 A_1, , cdots,, A_m 其產量（供應量）分別為 S_i；n 個銷地 B_1, , cdots , , B_n , 其銷量（需求量)分別為 D_j ；從產地 A_i 運往銷地 B_j 的運費為 c_{ij} . 假設產銷平衡，問如何安排運輸方案能使總運費最小？

這就是經典的運輸問題，設從 A_i 運往 B_j 的運量為 x_{ij} (決策變數），則建立運輸模型：min ~~ f=sum_{i=1}^{m} sum_{j=1}^{n} c_{i j} x_{i j} \ s.t. quad sum_{j=1}^{n} x_{i j}=S_{i}, quad i=1, cdots m \ qquad ~~~sum_{i=1}^{m} x_{i j}=D_{j}, quad j=1, cdots, n \ qquad qquad ~~~~~~ x_{i j} geq 0, quad i=1, cdots, m; ; j=1, cdots n

其中，約束條件 1 表示從 i 地運出量等於 i 地的供應量；約束條件 2 表示運往 j 地的運量等於 j 地的需求量。

運輸問題是特殊的線性規劃問題，筆算適合用變種的單純形法—表上作業法。

表上作業法，首先要求出初始可行解（即滿足約束條件的初始調運方案），這通常有兩種演算法：最小元素法、Vogel法。

二. 最小元素法

最小元素法的基本思想是就近供應，即從運價表中最小的運價開始確定產銷關係，依此

類推，一直到給出基本方案為止。

演算法步驟：

Matlab實現：

function B = MinElement(A,S,D)
%實現按最小元素法生成運輸問題的初始基可行解
%A為運價矩陣, S為供應向量, D為需求向量
%返回B為初始可行調運方案
M = 10000; %足夠大數, 大於所有運價
[m,n] = size(A);
B = zeros(m,n) * NaN; %存放結果
while true
[~,I] = min(A(:));
[Ir,Ic] = ind2sub([m,n],I); %最小元索引, 確定供應位置
%進行調運
if S(Ir) > D(Ic) %若供應大於需求
B(Ir,Ic) = D(Ic);
S(Ir) = S(Ir) - D(Ic);
D(Ic) = 0;
A(:,Ic) = M;
elseif S(Ir) < D(Ic) %若供應小於需求
B(Ir,Ic) = S(Ir);
D(Ic) = D(Ic) - S(Ir);
S(Ir) = 0;
A(Ir,:) = M;
else %若供應等於需求
B(Ir,Ic) = S(Ir);
S(Ir) = 0;
D(Ic) = 0;
A(Ir,:) = M;
A(:,Ic) = M;
if min(min(A)) == M
break
else
ind = find(isnan(B(:,Ic)));
B(ind(1),Ic) = 0; %補0
end
end
end

注：由於 0 有時候也是基解元素，故用NaN表示非基空格；另外，該函數對於計算過程中，同時劃去一行一列需要補 0 的情形也能實現。

代碼測試：

A = [3 11 3 10; 1 9 2 8; 7 4 10 5]; %運價矩陣
S = [7 4 9]; %供應
D = [3 6 5 6]; %需求

%用最小元素法求初始調運方案
Bm = MinElement(A,S,D)
cm = sum(sum(A .* Bm, omitnan)) %總運費

運行結果：

再測試一組需要補 0 的：

A = [4 10 4 4; 7 7 3 8; 1 2 10 6]; %運價矩陣
S = [20; 15; 15]; %供應
D = [5 10 25 10]; %需求

Bm0 = MinElement(A,S,D)
cm0 = sum(sum(A .* Bm0, omitnan)) %總運費

運行結果：

主要參考文獻

胡運全，運籌學基礎及應用，第六版

百度文庫，運輸問題-表上作業法 wenku.baidu.com/view/1f

————————————————————

原創作品，版權所有，轉載請註明，禁止出版盜用。


推薦閱讀：
相關文章