特殊型

Transportation Problems

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

Assignment Problems

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

Transshipment Problems

Shortest Path Problems

Maximal Flow Problems

Minimal Cost Flow Problems

幾類網路問題之間的相關性

幾類網路問題之間的相關性

minimal cost flow upper
bound		 trans-
shipment		 supply
demand		 cost
transportation - -
assignment - - 1/-1
transshipment -
shortest path - uniq 1/-1
maximal flow uniq F/-F all 0 but one

參考資料

  1. Hillier and Lieberman. Introduction to Operations Research. Mc Graw Hill.
  2. Michael Trick 的 線上講義 (pdf 版)
  3. John W. Chinneck 的 線上講義