Please enable JavaScript.
Coggle requires JavaScript to display documents.
運輸問題與指派問題 - Coggle Diagram
運輸問題與指派問題
線性規劃問題的特殊型式。
因為具有大量的限制式與決策變數,不會採用傳統單體法求解,而會使用更有效率的演算方法。
運輸問題-->運輸單體法(transportation simplex method)
指派問題-->匈牙利法(Hungarian method)。
運輸問題
-
-
求出最佳解
修正分配法(modified distribution method, MODI)
步驟:
(1)令任意ui,vj為0,算出其他ui,vj
(2)算出NBV,都≥0,即最佳(習慣上都會轉成Max問題)
(3)非最佳解,就進行運輸單體法運算
(4)選擇最負進入,踏BV構成迴路,「+」「-」「+」「-」
(5)「-」最小退出,產生的新表,再進行判斷。
ui, vj隨著令為0的地方不同,算出來的就會不一樣,ui, vj都是實數系,答案不唯一
若題目要考偶題變數,那一定會給定表格,不然算出來的都不一樣。
-
-
轉運問題
一開始先模型平衡,總供給=總需求因為供給節點可以當需求節點,反之亦然,所以每個節點除了他們原本的角色之外,變成可以轉運
換句話說,以供給節點為例,它能供給的不再只有原本的量,而是變成整個系統的量,再加上他自己的量。
-