運輸與指派問題 Transportation and Assignment Problems

Presentation on theme: "運輸與指派問題 Transportation and Assignment Problems"— Presentation transcript:

1 運輸與指派問題 Transportation and Assignment Problems
第七章 運輸與指派問題 Transportation and Assignment Problems 作業研究 二版 2009 © 廖慶榮

2 章節大綱 前言 建立運輸問題模式 運輸單形法 建立起始可行基解 轉運問題 指派問題 作業研究 二版 Ch.7 運輸與指派問題

3 7.1 前言 LP特例 運輸問題 & 指派問題 因其LP模式具有特殊結構，故有其獨特求解方法
7.1 前言 LP特例 運輸問題 & 指派問題 因其LP模式具有特殊結構，故有其獨特求解方法 運輸問題（transportation problem） 如何以最低運輸成本，將貨物由來源地送至目的地 指派問題（assignment problem） 如何以最適當的方式做一對一的指派 例如：將n個工作指派給n位人員以獲得最大績效 指派問題亦是運輸問題的特例 作業研究 二版 Ch.7 運輸與指派問題

4 7.2 建立運輸問題模式 典型範例 各工廠應分別運送多少數量至各配銷中心，才能獲致最低的總運輸成本？ 供給及需求單位：1卡車的量
7.2 建立運輸問題模式 典型範例 各工廠應分別運送多少數量至各配銷中心，才能獲致最低的總運輸成本？ 供給及需求單位：1卡車的量 單位運輸成本：千元 作業研究 二版 Ch.7 運輸與指派問題

5 典型範例 LP模式： 作業研究 二版 Ch.7 運輸與指派問題

6 典型範例 /最佳解 作業研究 二版 Ch.7 運輸與指派問題

7 運輸問題係數表 作業研究 二版 Ch.7 運輸與指派問題

8 運輸問題的LP模式 兩類限制式： 任何符合此特殊形式的LP問題，不論其實際意義為何，均可稱為運輸問題
供給限制式（supply constraint） 需求限制式（demand constraint） 任何符合此特殊形式的LP問題，不論其實際意義為何，均可稱為運輸問題 Min 作業研究 二版 Ch.7 運輸與指派問題

9 假設與性質 兩項假設： 運輸成本=單位運輸成本 x 運送數量 整數解性質（integer solution property）
供給等於需求： 若不相等，僅需稍做調整即可 成本成比例性： 運輸成本=單位運輸成本 x 運送數量 整數解性質（integer solution property） 雖然運輸問題是LP問題，但只要所有si與dj均為整數，則不需加上整數限制而成為IP問題，即可自動得到整數解 作業研究 二版 Ch.7 運輸與指派問題

10 特殊情況的處理 總供給大於總需求 總供給小於總需求 加上一個虛目的地（dummy destination）或稱虛行
加上一個虛來源（dummy source）或稱虛列 作業研究 二版 Ch.7 運輸與指派問題

11 特殊情況的處理 限制分配 具下限與上限的需求 有時來源 i 至目的地 j 沒有適當的路徑，或來源 i 所供給的貨物並不符合目的地 j 的需要
作法：讓 （對min問題），即可達到 具下限與上限的需求 需求經常分為兩部分 一部份是必須滿足的最低需求 另一部份則是可額外多出的需求 作法：在所增加的虛列中，讓對應之需求下限的單位成本為M，而讓額外需求的單位成本為0 作業研究 二版 Ch.7 運輸與指派問題

12 範例7.1 /生產與存貨規劃問題 未來一年第1至4季需求 公司本身產能 可轉包給兩家代工工廠 兩家代工工廠的合計產能
35、50、80、20艘遊艇 公司本身產能 38艘/季 可轉包給兩家代工工廠 成本增加3萬元/艘 兩家代工工廠的合計產能 20艘/季 公司可利用存貨調節旺季的需求 存貨成本：1.5萬元/季/艘 作業研究 二版 Ch.7 運輸與指派問題

13 範例7.1 /運輸問題係數表 作業研究 二版 Ch.7 運輸與指派問題

14 範例7.2 作業研究 二版 Ch.7 運輸與指派問題

15 範例7.2 解答： W2的上限： =160 作業研究 二版 Ch.7 運輸與指派問題

16 7.3 運輸單形法 運輸單形法（transportation simplex method）求解程序的四個部分：
7.3 運輸單形法 運輸單形法（transportation simplex method）求解程序的四個部分： 建立起始可行基解（7.4節） 測試最佳性及決定進入變數 決定離開變數 建立下一個可行基解 作業研究 二版 Ch.7 運輸與指派問題

17 2. 測試最佳性及決定進入變數 若以單形法求解，則需轉換如下： 作業研究 二版 Ch.7 運輸與指派問題

18 2. 測試最佳性及決定進入變數 起始單形表： 作業研究 二版 Ch.7 運輸與指派問題

19 2. 測試最佳性及決定進入變數 根據單形表的矩陣形式： 因此，NBV 的Z列係數為 作業研究 二版 Ch.7 運輸與指派問題

20 2. 測試最佳性及決定進入變數 人工變數 的Z列係數則為 此外，因主要問題與其互補對偶問題的目標函數值相等，所以
作業研究 二版 Ch.7 運輸與指派問題

21 2. 測試最佳性及決定進入變數 因此可得運輸問題之LP模式的Z列： 接下來，我們討論如何決定 與 ，以便快速地計算
接下來，我們討論如何決定 與 ，以便快速地計算 ，以簡化最佳性測試及決定進入變數程序 因不需人工變數，故不需考慮人工變數的Z列係數 作業研究 二版 Ch.7 運輸與指派問題

22 運輸單形表需要多少個基變數？ 考慮以下2 x 2的情況： 此四個限制式中，其中一個是多餘的 因此對於 的運輸單形表，基變數的個數為 個
因此對於 的運輸單形表，基變數的個數為 個 作業研究 二版 Ch.7 運輸與指派問題

23 如何快速決定與 ui與vj 如何快速決定與 ui與vj
對於BV， 因有(m+n-1)個BV，故有(m+n-1)個方程式 另一方面，ui 與vj的總數為m+n，所以可讓其一ui = 0 因此，我們可利用運輸單形表中的BV，快速地得到 所有ui 與vj，然後再計算所有NBV的 若所有 ，則為最佳解 否則，我們選擇最負值為進入變數。 作業研究 二版 Ch.7 運輸與指派問題

24 7.3 運輸單形法 決定離開變數 建立下一個可行基解 結論 當決定進入變數後，可根據BV建立一條階石路徑，由此路徑可輕易地判斷離開變數
7.3 運輸單形法 決定離開變數 當決定進入變數後，可根據BV建立一條階石路徑，由此路徑可輕易地判斷離開變數 建立下一個可行基解 當決定進入變數及離開變數後，讓所有在階石路徑上的BV加上或減去離開變數之值，即可快速地得到下一個BFS 結論 根據以上四個部分的分析，單形表的Z列係數已可由運輸單形表取得，單形表的限制式係數亦已不再需要，因此已完全可用運輸單形表取代單形表 作業研究 二版 Ch.7 運輸與指派問題

25 運輸單形法與單形法的比較 兩者運算表比較： 例如 運輸單形表：(m+1)列x (n+1)行 單形表：(m+n+1)列x (mxn+m+n)行
對於10個來源、10個目的地的問題 運輸單形表：12 x 12 單形表：21 x 120 此外，運輸單形法不需使用人工變數 作業研究 二版 Ch.7 運輸與指派問題

26 運輸單形法的步驟（對min問題） 起始步驟：建立起始BFS 最佳性測試：
讓具有最多指派之列的ui=0，並根據以下公式，決定所有的ui及vj： 計算所有非基變數的 ，若均為非負值，則為最佳解；否則繼續 作業研究 二版 Ch.7 運輸與指派問題

27 運輸單形法的步驟（對min問題） 迭代步驟： 決定進入變數：選擇具最負 的NBV
決定離開變數：建立階石路徑，並分別標示「-」與「+」。在「-」的BV中，選擇最小的BV為離開變數。若為平手，則任選其一 產生新的BFS：所有標示「+」的BV加上離開變數之值，所有標示「-」的BV減去該離開變數之值。 返回最佳性測試 作業研究 二版 Ch.7 運輸與指派問題

28 範例7.3 /表1 作業研究 二版 Ch.7 運輸與指派問題

29 範例7.3 /表2 作業研究 二版 Ch.7 運輸與指派問題

30 範例7.3 /表3 作業研究 二版 Ch.7 運輸與指派問題

31 範例7.3 /表4 (opt) 作業研究 二版 Ch.7 運輸與指派問題

32 計算邊際成本兩個方法 計算 的兩個方法 乘數法（method of multipliers）或修正分配法（modified distribution method；MODI），即以上的方法 階石角法（stepping stone method）：對於每一個NBV，利用BV找出一條階石路徑，然後依此路徑運送1單位，而計算出其 作業研究 二版 Ch.7 運輸與指派問題

33 Max問題的處理 轉換法 直接法：改變相關步驟： 將原問題轉換為min問題處理 作法：讓 ，且最佳解的 最佳性測試：
作法：讓 ，且最佳解的 直接法：改變相關步驟： 最佳性測試： 計算所有NBV的 ，若均為非正值，則得到最佳解；否則繼續 決定進入變數：選擇具最大 的NBV為進入變數 作業研究 二版 Ch.7 運輸與指派問題

34 求解過程的特殊的情況 退化解（degeneracy） 多重最佳解（multiple optimal solutions）
含有BV=0的BFS 處理原則：始終維持n+m-1個BV 多重最佳解（multiple optimal solutions） 在最佳運輸單形表中，有任何NBV的 作業研究 二版 Ch.7 運輸與指派問題

35 7.4 建立起始可行基解 四個方法 後三個方法的步驟係針對min問題。若為max問題，則需轉換 西北角法 最低成本法 Vogel近似法
7.4 建立起始可行基解 四個方法 西北角法 northwest corner rule 最低成本法 minimum cost method Vogel近似法 Vogel’s approximation method；VAM Russell近似法 Russell’s approximation method；RAM 後三個方法的步驟係針對min問題。若為max問題，則需轉換 作業研究 二版 Ch.7 運輸與指派問題

36 西北角法 由西北角開始，其步驟如下： 作業研究 二版 Ch.7 運輸與指派問題

37 範例7.4 /西北角法的應用 作業研究 二版 Ch.7 運輸與指派問題

38 最低成本法 尋找具最低單位成本的路徑進行指派，步驟如下： 作業研究 二版 Ch.7 運輸與指派問題

39 範例7.5 /最低成本法的應用：表1 作業研究 二版 Ch.7 運輸與指派問題

40 範例7.5 /最低成本法的應用：表2 作業研究 二版 Ch.7 運輸與指派問題

41 範例7.5 /最低成本法的應用：表3 作業研究 二版 Ch.7 運輸與指派問題

42 範例7.5 /最低成本法的應用：表4&5 作業研究 二版 Ch.7 運輸與指派問題

43 Vogel近似法 基本想法：避免高成本的指派。 步驟： 作業研究 二版 Ch.7 運輸與指派問題

44 範例7.6 /VAM的應用：表1 作業研究 二版 Ch.7 運輸與指派問題

45 範例7.6 /VAM的應用：表2 作業研究 二版 Ch.7 運輸與指派問題

46 範例7.6 /VAM的應用：表3 作業研究 二版 Ch.7 運輸與指派問題

47 範例7.6 /VAM的應用：表4&5 作業研究 二版 Ch.7 運輸與指派問題

48 Russell近似法 步驟： 作業研究 二版 Ch.7 運輸與指派問題

49 範例7.7 /RAM的應用：表1 作業研究 二版 Ch.7 運輸與指派問題

50 範例7.7 /RAM的應用：表2 作業研究 二版 Ch.7 運輸與指派問題

51 範例7.7 /RAM的應用：表3 作業研究 二版 Ch.7 運輸與指派問題

52 範例7.7 /RAM的應用：表4 作業研究 二版 Ch.7 運輸與指派問題

53 7.5 轉運問題 轉運問題（transshipment problem） 轉換步驟： 具有轉運點（來源、目的地、或純轉運點）的運輸問題
7.5 轉運問題 轉運問題（transshipment problem） 具有轉運點（來源、目的地、或純轉運點）的運輸問題 轉運問題可以轉換為運輸問題處理 轉換步驟： 所有轉運點是來源，亦是目的地 轉運點 i 的 所有轉運點的供給與需求，需額外加上總供給量 各轉運點的轉運量可計算如下： 轉運點 i 的轉運量 = 總供給量 作業研究 二版 Ch.7 運輸與指派問題

54 範例7.8 /轉運問題 原始資料 作業研究 二版 Ch.7 運輸與指派問題

55 範例7.8 /轉運問題 轉換後的資料 作業研究 二版 Ch.7 運輸與指派問題

56 範例7.8 /轉運問題 最佳解 作業研究 二版 Ch.7 運輸與指派問題

57 7.6 指派問題 (assignment problem)
問題： 如何以最適當的方式做一對一的指派 例如：將n個工作指派給n位人員以獲得最大績效 求解方法 單形法 運輸單形法 指派問題運輸問題特例（當m=n，且各供給與需求均為1） 匈牙利法（Hungarian method）：最有效率 作業研究 二版 Ch.7 運輸與指派問題

58 指派問題成本表 n x n 的方陣 作業研究 二版 Ch.7 運輸與指派問題

59 特殊情況的處理 列數大於行數 列數小於行數 限制分配 加上虛行，且虛行的成本均為零 加上虛列，且虛列的成本均為零 讓其成本為M
作業研究 二版 Ch.7 運輸與指派問題

60 匈牙利法 由單形法衍生而來 步驟（對min問題）： 建立成本表：須為方陣 簡化行：決定每一行最小值，並將該行的每個數字減去該最小值 簡化列：
最佳性測試：使用最少的水平或垂直線刪除所有0。若線條數等於列數，則停止，並進行最適當的指派；否則繼續 進一步簡化成本表： 在所有未被線條劃到的數字中，決定其最小值 所有未被線條劃到的數字，減去該最小值 所有同時被水平與垂直線劃到的數字，加上該最小值 返回步驟4 作業研究 二版 Ch.7 運輸與指派問題

61 範例7.9 /匈牙利法的應用：表1&2 作業研究 二版 Ch.7 運輸與指派問題

62 範例7.9 /匈牙利法的應用：表3-5 作業研究 二版 Ch.7 運輸與指派問題