運輸問題

　　一類具有特殊結構的線性規劃問題。由於運輸問題約束方程組的係數矩陣是完全麼模的，即所有的子行列式為0或±1，存在著比單純形法更簡單的特殊解法。對於規模不太大的運輸問題可用圖上作業法或表上作業法求解。這類問題的典型提法是，為瞭把某種產品從若幹個產地調運到若幹個銷地，已知每個產地的供應量和每個銷地的需求量，如何在許多可行的調運方案中，確定一個總運輸費或總運輸量最少的方案。

　　運輸型問題　具有上述特點的線性規劃問題通常被稱為運輸型問題。現已發現的運輸型問題有以下6類:①一般運輸問題,又稱希契科克運輸問題，簡稱H問題。②網絡運輸問題，又稱圖上運輸問題,簡稱T問題。③最大流量問題,簡稱F問題。④最短路徑問題,簡稱S問題。⑤任務分配問題，又稱指派問題,簡稱A問題。⑥生產計劃問題，又稱日程計劃問題,簡稱CPS問題。其中一般運輸問題、任務分配問題和生產計劃問題通常都可以用表上作業法求解，而網絡運輸問題、最大流量問題和最短路徑問題一般可用圖上作業法或網絡技術求解。

　　運輸模型　設某種物資有m個產地A₁,A₂，…,A_m，供應量分別為a₁，ɑ₂，…，ɑ_m個單位,聯合供應n個銷地B₁，B₂,…,B_n,需求量分別為b₁，b₂,…,b_n個單位。從產地A_i向銷地B_j運輸一個單位物資的費用為c_ij，求怎樣調運物資才能使運輸費用最少。記從產地A_i到銷地B_j的運輸量為x_ij，列運輸表（見表）。

運輸表

　　運輸問題的數學模型是：

式中min 表示求極小值，s.t.表示“約束條件為”。當ɑ_i，b_j 滿足條件

時稱為產銷平衡的運輸問題，否則稱為產銷不平衡的運輸問題。產銷不平衡的運輸問題可以通過增加一個假想產地或假想銷地，化成產銷平衡的運輸問題。如把產地稱為源（發點），銷地稱為匯(收點)，則任務分配問題、生產計劃問題等運輸型問題的模型也可以歸納成類似上述形式。運輸模型約束方程組的系數矩陣為如下形式：　

　　這是(m＋n)×mn的矩陣，每一列的元素中隻有2個1，其餘均為0。可以證明A的秩≤(m＋n－1)。

　　運輸問題的解法　運輸問題可用表上作業法求解。圖中示出用表上作業法求解運輸問題的全過程。初始基本可行解的求法有三種：①左上角法。它的基本思想是給運輸表中左上角的變量分配運輸量以確定產銷關系。②小元素法，或最小成本法。它的基本思想是就近供應，即從運輸表中運價最小的格子開始分配運輸量以確定產銷關系。③元素差額法,又稱沃格爾近似法，簡稱VAM法。它是從運輸表中各行和各列的最小元素和次小元素的差額來確定產銷關系。改進初始基本可行解的方法有兩種：①閉回路法。這種方法需要對每一個空格尋找一條閉回路，並根據閉回路求出每個空格的檢驗數。當運輸問題中m 和n 較大時，計算檢驗數的工作量很大。②位勢法，或乘數法。先對初始調運方案求出位勢，然後求各空格的檢驗數。當所有的檢驗數均為非負時，就得到最優方案。如果出現負的檢驗數，則從檢驗數為負的空格出發，作閉回路，重新計算檢驗數，作進一步調整。用位勢法求檢驗數就是對偶問題的表上作業法。

　　

參考書目

　林同曾主編:《運籌學》,機械工業出版社,北京,1986。