第八章 Transportation and Assignment problems
運輸問題 (Transportation problem)
雖然有六條算式,但剩下那條可由其他五條組合而得出,所以只有五條限制式
解法
方法一:Northwest Corner Method
直接填滿
方法二:Vogel’s Approximation method
1. 計算penalty "次小-最小"
2. 找到penalty最大,填滿他,刪除其他限制式
3. 重複1.2 直到找到所有值(資源耗盡)
方法三:優化解 the MODI method(uv method)
1. 找到不合的最大值 Cj-Zj "為負"且最小
2. theta取代該值,循環補償誤差
3. 修正值
4. 重複1.2.3. 直到Cj-Zj 皆為正
運輸問題 (Transportation problem) 的特殊題型
Dummy 問題
有時候supply與demand不一定相等,需要設一個dummy變數代表剩餘的資源
Degeneracy (退化解)問題
解出來的變數值有0
Maximum 的運輸問題
1. penalty改算 "最大-次大"
2. Cj-Zj 找正