Presentation is loading. Please wait.

Presentation is loading. Please wait.

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

Similar presentations


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 林吉仁著


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

Similar presentations


Ads by Google