Chapter 7 運輸問題與指派問題.

Presentation on theme: "Chapter 7 運輸問題與指派問題."— Presentation transcript:

1 Chapter 7 運輸問題與指派問題

2 7.1　緒言 企業管理者經常會遇到特殊形式的線性規劃，運輸問題 (transportation problem) 和指派問題 (assignment problem) 就是其中最常見的兩種。 所謂「運輸問題」，是指由數個供應點將物品運送至數個需求點的問題。

3 7.2 運輸問題的標準架構 運輸問題有如下基本假設： 求解過程有下列主要步驟： 運送的貨物為同質 (亦即，無論起點與終點，貨物相同)。
7.2　運輸問題的標準架構 運輸問題有如下基本假設： 運送的貨物為同質 (亦即，無論起點與終點，貨物相同)。 無論運貨數量多寡，每單位運輸成本都相同。 各起點與各終點之間的運輸路線只有一條。 求解過程有下列主要步驟： 求初始基本可行解。 為最優性測試初始解。 持續改進次優解。

4

5

6

7 7.3　運輸問題的初始基本可行解

8 7.3.1　西北角法

9 7.3.2　最佳空格法

10 7.3.3　佛格爾法 另外一個強而有力的方法是處置「第一差額」(first differences) 的佛格爾法 (Vogel’s approximation method, VAM) 或稱「差額法」。所謂「第一差額」是指行或列中最低成本與次低成本相差的值。VAM的想法是著重於成本相對性的懲罰。如果解題者未能在每一行與列將所有供應量和需求量放在成本最低的位置，則必須受罰。在找到有最高罰款 (penalty value) 的行或列後，解題者盡可能指派運送量於最低成本的位置，而後再次評估所剩空位的罰款，重複進行這種程序，直到得出一個可行解。

11 7.4　最優解的驗證

12 7.4.1　踏石法 (環路法) (1,3)(2,3)(2,2)(1,2) 淨影響： =-30

13 將西北法的結果，經由踏石法修正後，與VAM法結果一樣

14 大規模題目要用踏石法很困難

15 7.6　指派問題 指派問題中所有的供應與需求均等於1，即將個來源和目的地形成1對1的關係，使成本最低或總利潤最大。

16 7.7　指派問題的解法 指派問題可以採取如下三種方法之一解題： 運輸問題求解。 窮舉法。 匈牙利法。

17 窮舉法

18

19

20

21

22 7.8　匈牙利法

23

24

25

26

27

28

29

30

31

32

33

34

35

36