Transportation 與 Assignment 類型的問題

例: 摘鮮園蔬果公司

摘鮮園蔬果公司在苗粟大湖, 南投國姓, 雲林林內等三處各有一個草莓園。 他們的產品分別送到臺北, 臺中, 臺南, 高雄等四個大都會的賣場去販售。 由於不同的路線有不同的運輸工具, 保存方式, 及簽約條件, 每盒草莓運往各處賣場的成本各不相同。 各產地的供給量 (盒), 各賣場的需求量 (盒) 及各運送組合的成本 (元/盒) 如下表:

臺北 臺中 臺南 高雄 供給量
大湖 25 12 28 35 72
國姓 33 18 38 42 53
林內 34 16 21 26 48
需求量 52 38 29 54 173

試求最佳運送組合, 以達到最低的運輸總成本。

Ans: strawberry.lp; strawberry.ods; strawberry.gnumeric

假設一個運輸問題有 m 個供應點, n 個需求點。 則它共有 mn 個變數, m+n-1 個等號條件。 它的解會有 m+n-1 個 basic variables (基變數), "通常" 這些 basic variables 的值都非 0; 若有 basic variable 出現 0, 則表示此題有退化解。 至於 non-basic variables 一定是 0。

Transportation Problems 的一些變形:

  1. 不存在的運輸途徑: 該路徑的運輸成本可填一個很大的數字, 自然就不會選到它。
  2. 供需不平衡的狀況: 增加一列 (虛擬供應點) 或增加一行 (虛擬需求點) 以達供需平衡。 多出來的這些供需路徑, 運輸成本皆為 0。 若有些真實供應點的所有產品必須出清, 則它們與虛擬需求點之間的運輸成本填入一個很大的數字, 自然就不會選到這些路徑。

關於 Transportation Problems 的一些特性:

  1. Transportation Problems 是 LP 問題的特例; 有較快的解法。
  2. 若 supply 及 demand 都是整數, 則所有的 corner point solutions 自動都是整數解。
  3. 重要! 使用軟體解 transportation problem 時, 千萬不要指定 「要整數解」, 因為 integer programming 類的問題, 計算量超大。

Assignment Problem

  1. Assignment Problems 是 Transportation Problems 的特例;
  2. 每個 source 都是 1, 每個 demand 也都是 1。
  3. 上一節所談的所有特性都適用於此類問題; 有更快的解法。

參考資料

  1. The Transportation Problem
  2. Special Types of LP Problems Transportation Problem
  3. The MODI and VAM Methods of Solving Transportation Problems
  4. Michael Trick 的 線上講義 (pdf 版)
  5. John W. Chinneck 的 線上講義