運輸問題與指派問題
線性規劃問題的特殊型式。
因為具有大量的限制式與決策變數,不會採用傳統單體法求解,而會使用更有效率的演算方法。
運輸問題-->運輸單體法(transportation simplex method)
指派問題-->匈牙利法(Hungarian method)。
運輸問題
運輸問題模式:
一定是極小化總成本
供給需求都是等號限制式
總供給=總需求
(1)線性規劃模式:
滿足此特殊線性規劃,皆可稱為運輸問題
(2)運輸表格:必須滿足總供給=總需求,供需不平衡需加入虛擬行/列,成本是0
(3)整數解特性
(4)矩陣形式
(5)對偶問題
(6)BV個數:n+m-1
(7)退化解:BV個數不足,要設BV為0
(8)多重解
(9)利潤要轉成成本
建模題目:
當需求有Min/Max,要切成2塊放入運輸表
4種找起始解的方法
西北角法(northwest corner method)
最小成本法(Least cost method)
Vogel法(Vogel's approximation method)
考試沒指定方法,都用此,比較簡單且好做,起始解也不錯
一個step,一張表
有考慮到隱形成本,算出來的解,都會是最好的。
口訣:小大小
一個step,一張表
Russell法(Russell approximation method)
作法複雜,結果也沒有Vogel好
考試專用
Vogel≥最小成本≥Russell>西北角起始解找得越好,求最佳解越快
求出最佳解
修正分配法(modified distribution method, MODI)
步驟:
(1)令任意ui,vj為0,算出其他ui,vj
(2)算出NBV,都≥0,即最佳(習慣上都會轉成Max問題)
(3)非最佳解,就進行運輸單體法運算
(4)選擇最負進入,踏BV構成迴路,「+」「-」「+」「-」
(5)「-」最小退出,產生的新表,再進行判斷。
ui, vj隨著令為0的地方不同,算出來的就會不一樣,ui, vj都是實數系,答案不唯一
若題目要考偶題變數,那一定會給定表格,不然算出來的都不一樣。
令BV越多的列/行,比較有效率
5-9
單純建構LP model而已,就不用特別去平衡,直接做就好,哪個部分比較多,他的限制式就用「≦」
5-10
運輸問題的敏感度分析
5-11
是生管的整體規劃,而且就是用運輸問題來求解,所以考在OR很合理。
M不管減什麼,都是M
轉運問題
指派問題
一開始先模型平衡,總供給=總需求因為供給節點可以當需求節點,反之亦然,所以每個節點除了他們原本的角色之外,變成可以轉運
換句話說,以供給節點為例,它能供給的不再只有原本的量,而是變成整個系統的量,再加上他自己的量。
運輸問題的特例
需求量供給量都是1
一對一指派
因為有嚴重退化解
採用匈牙利法
被指派對象與工作數目必須相同,若不相等,必須平衡,增加虛擬列或行,所以平衡後,必為方陣