Please enable JavaScript.

Coggle requires JavaScript to display documents.

運輸問題與指派問題 - Coggle Diagram

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