作業研究 第五章 運輸與指派問題 林吉仁 著 高立圖書公司出版.

Presentation on theme: "作業研究 第五章 運輸與指派問題 林吉仁 著 高立圖書公司出版."— Presentation transcript:

1 作業研究 第五章 運輸與指派問題 林吉仁 著 高立圖書公司出版

2 5-1運輸問題 運輸問題是特殊結構的線性規劃問題。但一般並不採用線性規劃單體法來求解，而有其他更有效率的演算法。
林吉仁著 5-1運輸問題 運輸問題是特殊結構的線性規劃問題。但一般並不採用線性規劃單體法來求解，而有其他更有效率的演算法。 若有數個供給點以及數個需求點，而欲分配各供給點之供給量以滿足各需求點的需求量，而且使運輸總成本最小，即是所謂的「運輸問題」(Transportation Problem)

3 標準運輸問題 林吉仁著 (供需平衡) 有 m +n 1 個為基變數方格

4 林吉仁著 運輸問題之線性規劃模式 若ai、bj均為整數，必有xij均為整數最佳解

5 5-1-2 運輸單體法 求解運輸問題多採運輸單體法，直接在表格上運算。 運輸簡算法的解法邏輯是起始規則、運算規則、停止規則。
林吉仁著 5-1-2 運輸單體法 求解運輸問題多採運輸單體法，直接在表格上運算。 運輸簡算法的解法邏輯是起始規則、運算規則、停止規則。 起始規則：介紹 (1)西北角法；(2)最小成本法；(3)佛格法 運算規則與停止規則：介紹 (1)階石法，(2)修正分配法(MODI法) 運輸單體法最常採佛格法搭配MODI法

6 起始規則之「西北角法」 西北角法是求運輸問題起始解最簡單的方法，但因未將單位成本納入考慮，所得結果通常較差。
林吉仁著 起始規則之「西北角法」 西北角法是求運輸問題起始解最簡單的方法，但因未將單位成本納入考慮，所得結果通常較差。 西北角法利用運輸單體表中西北角方格的最大分配量來求出起始解。自 x11 方格開始  若 min(S1 , D1)= S1，令 x11 = S1，刪去第一列，並以 D1x11 為第一行的剩餘需求量。若 min(S1 , D1)= S1，令 x11 = S1，刪去第一列，並以 D1x11 為第一行的剩餘需求量。  若 min(S1 , D1)= D1，令 x11 = D1，刪去第一行，並以 S1  x11 為第一列的剩餘供給量。

7 分配 x11 後，在剩下的方格中，反覆進行西北角方格數量的分配，直到無剩餘方格為止，即得一可行起始基解。
林吉仁著 分配 x11 後，在剩下的方格中，反覆進行西北角方格數量的分配，直到無剩餘方格為止，即得一可行起始基解。 設 Si、Dj 分別代表剩餘供給量與剩餘需求量，當 min(Si , Dj)= Si= Dj 時；表示將有退化解 產生，為了避免少了一個基變數方格，雖填入最大分配量後，雖列、行的剩餘量均為0，但勿同時將對應列、行均刪去，應該僅刪去列或僅刪去行。又當 min(Si , Dj)= 0 時，仍須填入0表示該方格的 ( 退化 ) 分配量，以區別基變數方格與非基變數方格。

8 林吉仁著 例題5-1

9 解： ∵ 本題 m = 3 , n = 4，∴ 應有 m +n 1= 6 個基變數方格。
林吉仁著 解： ∵ 本題 m = 3 , n = 4，∴ 應有 m +n 1= 6 個基變數方格。 以下我們將以打叉 () 代表刪去該列 ( 或行 )

10 林吉仁著

11 林吉仁著

12 林吉仁著

13 快速「西北角法」 自 x11 方格開始； (1)若已無剩餘供給量時，往下移一方格； (2)若是已無剩餘需求量，往右移一方格。 記憶：
林吉仁著 快速「西北角法」 自 x11 方格開始； (1)若已無剩餘供給量時，往下移一方格； (2)若是已無剩餘需求量，往右移一方格。 記憶： 列無剩餘，重找一列 → 下移； 行無剩餘，重找一行 → 右移 當遇有退化解時，處理方式同前所述

14 林吉仁著 例題5-2 以下是以西北角法求得退化運輸問題之起始解 (單位成本省略)的問題與解答，請自行參考練習

15 起始規則之「最小成本法 」 最小成本法 (Least cost rule) 所選的基變數方格是 ( 未刪去 ) 方格中的單位成本最小方格。
林吉仁著 起始規則之「最小成本法 」 最小成本法 (Least cost rule) 所選的基變數方格是 ( 未刪去 ) 方格中的單位成本最小方格。 如果最小成本方格不只一個可任取其一 當遇有退化解產生時，理論上可任選刪去列或行，但通常是刪去成本較高者 其他處理方式均同西北角法 最小成本法因考慮了單位成本，通常可獲得比西北角法更好的起始解，即總運輸成本較小

16 林吉仁著 例題5-3

17 解： 林吉仁著

18 林吉仁著

19 林吉仁著

20 起始規則之「佛格法」 佛格法 (VAM) 又稱差額法
林吉仁著 起始規則之「佛格法」 佛格法 (VAM) 又稱差額法 佛格法是先算出每列、每行未刪去方格中最小的兩單位成本的差額，然後選出具最大差額的列(或行)，以該列(或行)的最小成本方格為基變數方格，分配其量，刪去該列(或行)。反覆進行 當最大差額不只一個，可任取其一。 退化解的處理亦同西北角法、最小成本法

21 林吉仁著 例題5-4

22 林吉仁著 解：

23 林吉仁著

24 林吉仁著

25 林吉仁著 運算規則與停止規則 之「階石法」 1. 每一非基變數恰對應一條閉回路。閉回路是指：由非基變數方格出發，踩著基變數方格(階石)，並以階石為轉角點，沿水平─鉛直─水平─ 鉛直…的線段前進，回到原來的非基變數方格 2. 每一非基變數方格也對應一個邊際成本Qij。而Qij是閉回路上正負相間單位成本的和。 即 Qij = cij cij*+ci’j*  …

26 5.以Qij最負值方格為調入變數，並求出其閉回路，再設定調出變數與分配調整值，而修正分配得到一組新而更佳的基解。回到步驟 2.
林吉仁著 3.求出所有非基變數方格的Qij 4. 若所有Qij0則已達最佳解，否則到步驟 5. 5.以Qij最負值方格為調入變數，並求出其閉回路，再設定調出變數與分配調整值，而修正分配得到一組新而更佳的基解。回到步驟 2. =min(xij*,…) ；(i,j*)閉回路奇數步方格

27 例題5-5 林吉仁著

28 林吉仁著 解：

29 林吉仁著 例題5-6 請以例題5-3的基解為起始(重列如下)，以階石法求出該問題的最佳解

30 解： 林吉仁著

31 林吉仁著

32 運算規則與停止規則之「MODI法」 1. 已得起始解(利用佛格法)。 2. 以 ui+vj=cij 求出所有ui 、vj 值
林吉仁著 運算規則與停止規則之「MODI法」 1. 已得起始解(利用佛格法)。 2. 以 ui+vj=cij 求出所有ui 、vj 值 3. 以Qij=cijui vj求出所有非基變數方格的Qij 4. 若所有Qij0則已達最佳解，否則到步驟 5. 5. 以Qij最小值方格為調入變數，並求出其閉回路，再設定調出變數與分配調整值，而修正分配得到一組新而更佳的基解。回到步驟 2.

33 林吉仁著 例題5-7

34 林吉仁著 解：

35 林吉仁著

36 林吉仁著

37 林吉仁著

38 林吉仁著

39 林吉仁著

40 5-1-3特殊運輸問題 運輸問題的各種特殊情形之處理 退化解：指有基變數為0，影響求解效率 多重最佳解：Qij0單一最佳解；
林吉仁著 5-1-3特殊運輸問題 運輸問題的各種特殊情形之處理 退化解：指有基變數為0，影響求解效率 多重最佳解：Qij0單一最佳解；  Qij0多重最佳解 限制運送：令該cij= M ()

41 林吉仁著 最大化問題 當運輸問題中的單位成本 cij 換成單位利潤 pij 時，就成了最大化問題了。求解最大化問題只要先將 pij改成pij，即可按一般運輸單體法加以求解。

42 林吉仁著 例題5-8

43 林吉仁著 解： 因目標為最大化，先將各單位利潤 pij 乘上負號 (其餘解題過程請見課本)

44 5-1-3-5不平衡運輸問題 當總供給量與總需求量不相等時，稱為不平衡運輸問題
林吉仁著 不平衡運輸問題 當總供給量與總需求量不相等時，稱為不平衡運輸問題 求解時，總供給量大於總需求量  ，虛設一個需求量  的終點；總需求量大於總供給量  ，虛設一個供給量  的起點 多虛設出的方格單位運輸成本一般為0。若不欲某些方格有分配量，可令其單位成本為 M 以一般運輸單體法加以求解即可 虛設起點所供給的量，表供應不足；虛設終點的量，表供應過剩

45 林吉仁著 例題5-9

46 林吉仁著 解：

47 林吉仁著

48 林吉仁著

49 林吉仁著

50 林吉仁著

51 林吉仁著 例題5-10 彈性需求量問題

52 解： 林吉仁著

53 林吉仁著

54 林吉仁著 例題5-11應用運輸問題解生產排程 某製鞋廠預測未來三個月的需求量如下：第一個月需求量200，第二個月需求量310，第三個月需求量240。在正常工時下每雙鞋的成本為7元，加工工時下每雙鞋的成本為11元，而每個月正常工時的生產上限是200雙鞋子，加工工時的生產上限是100雙鞋子。又每雙鞋子每個月的庫存成本是2元。請利用平衡運輸模式描述此問題 ( 不須求解 )，使得滿足未來三個月的需求量下，總成本最小。

55 解： 林吉仁著

56 5-1-3-8 轉運問題 轉運問題(Transshipment Problem)是運輸問題的擴充。
林吉仁著 轉運問題 轉運問題(Transshipment Problem)是運輸問題的擴充。 在運輸問題節點只單純有貨物流出(供給)、或只有貨物流入(需求)，但如果節點既有貨物流出、也有貨物流入，此節點稱為轉運點，而問題變成轉運問題了。 沒有供給量，沒有需求量的轉運點稱為純轉運點。

57 建構轉運問題模式 建立轉運供需表的步驟如下： 1. 建立平衡的運輸供需表，令 。 2. 增設扮演起點角色的點於列；增設扮演終點角色的點於行。
林吉仁著 建構轉運問題模式 建立轉運供需表的步驟如下： 1. 建立平衡的運輸供需表，令 。 2. 增設扮演起點角色的點於列；增設扮演終點角色的點於行。 3. 填入各路徑的單位成本。本站到本站的單位成本為 0。 4. 可供轉運的起點供給量加T；可供轉運的終點需求量也加T ；而所有新增的點其量 ( 無論是供給量或需求量 ) 均為T 。 　　建立了轉運供需表即可視為運輸問題加以求解。

58 例題5-12 林吉仁著

59 解： 林吉仁著 列出轉運供需表並解得最佳解如下： ∴ 最低總運輸成本 391 並得下運輸簡圖

60 林吉仁著 運輸簡圖 (簡圖中不考慮表中本站至本站的運送量)

61 5-2指派問題 指派問題是特殊結構的LP問題、0-1規劃問題、運輸問題。
林吉仁著 5-2指派問題 指派問題是特殊結構的LP問題、0-1規劃問題、運輸問題。 假設有 n 件不同工作，n 位人員。而所謂指派問題 (Assignment Problem) 就是研究如何將 n 件工作以一對一方式分派給 n 位人員，而使得總成本最小 ( 或總利潤最大 ) 解指派問題常用匈牙利法

62 5-2-1匈牙利法(目標min) 匈牙利法步驟： 列出成本矩陣。若是利潤矩陣 ( 求 Max)，則每一元素均乘負號
林吉仁著 5-2-1匈牙利法(目標min) 匈牙利法步驟： 列出成本矩陣。若是利潤矩陣 ( 求 Max)，則每一元素均乘負號 檢查是否為方陣。若非方陣，適當地加入一 ( 或數 ) 列或行，以形成方陣 ( 設 nn)。而新加入元素值均為0，除非有不欲被指派的元素 成本方陣中，各列減該列最小值，接著又各行減該行最小值，得簡化方陣

63 利用簡化方陣中的0元素來分派，已指派的0元素以□框起來。指派時的原則有：
林吉仁著 利用簡化方陣中的0元素來分派，已指派的0元素以□框起來。指派時的原則有： 自僅 ( 剩 ) 有一個0的列或行開始，框起該0元素，並刪去該0的所在列與所在行。反覆進行。 若每一列、行均有一個以上的0元素，則自有 ( 剩 ) 最少0元素的列或行任框一個0，再回到 (1)。 指派時，作者建議應自第1列，第2列，… 最後一列，第1行，… 最後一行，反覆地、有系統地來找尋可指派的0元素。而這也正是可指派數的最大值。(註：在論文中有故意拼湊出的例外之例子，教科書中則都成立)

64 若 p = n，則已達最佳解。並可對照原始成本矩陣求得最小總成本
若 p  n，則以最少直線數 ( 即 p 條直線 ) 劃去簡化方陣中所有0元素。所謂直線是指鉛直線與水平線，不包含斜線 找出“最少線數”劃去所有的0。步驟： (a)無 的列打勾 () (b)有打勾列，其0所在行打勾； (c)有打勾行，其 所在列打勾 (d)重覆 (b)、(c) 直到沒有新的打勾行、列為止 (e)沒有打勾的列劃橫線，有打勾的行劃縱線， 即得劃去所有0的最少線數 林吉仁著

65 ※有時候，若不欲 (i, j) 元素被指派，只要將其成本設為大 M( 利潤設為 M ) 即可
林吉仁著 若未被劃去的元素中最小值為 a，則 (1)未被劃去者減 a (2)被劃一次者不變 (3)被劃兩次者加 a 可得新的簡化方陣，並回到步驟 4. ※有時候，若不欲 (i, j) 元素被指派，只要將其成本設為大 M( 利潤設為 M ) 即可

66 林吉仁著 例 5-13 假設有四位技工，四件欲在不同工作母機上加工的工件，因技工專長不同，完成各工件的所費成本亦不同，如下表。請分派每位技工恰加工一件工件，而使所費總成本最小

67 林吉仁著 解：

68 林吉仁著

69 林吉仁著

70 林吉仁著

71 林吉仁著

72 林吉仁著 例 5-14

73 林吉仁著 解：

74 林吉仁著 例題5-15 某房屋仲介業者手邊有六件案子 ( 六棟房屋 )，而有五位購屋者，各願購買一棟房子。每位購屋者對各棟房屋願意出的價格不同，所以仲介者賣房子給各購屋者的預期利潤也不同，如下表所示。問仲介者該如何來分派售屋案 ( 那棟房屋賣給那位購屋者 )，以使得總預期利潤最大？

75 解： 林吉仁著

76 林吉仁著

77 林吉仁著

78 例題5-16 游泳教練欲自5名選手中選出四名來參加400米混合四式接力。選手各泳式的成績如下表，請問教練該如何安排以使接力成績最佳。
林吉仁著 例題5-16 游泳教練欲自5名選手中選出四名來參加400米混合四式接力。選手各泳式的成績如下表，請問教練該如何安排以使接力成績最佳。

79 解： 林吉仁著

80 林吉仁著

81 林吉仁著