運輸問題與指派問題
線性規劃問題的特殊型式。
因為具有大量的限制式與決策變數，不會採用傳統單體法求解，而會使用更有效率的演算方法。
運輸問題-->運輸單體法(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
一對一指派
因為有嚴重退化解
採用匈牙利法
被指派對象與工作數目必須相同，若不相等，必須平衡，增加虛擬列或行，所以平衡後，必為方陣