Chapter 4 網路模型 Network Models.

Presentation on theme: "Chapter 4 網路模型 Network Models."— Presentation transcript:

1 Chapter 4 網路模型 Network Models

2 4.1 網路介紹 Introduction 網路問題可以利用下列方式表示 6 節點 Nodes 弧 Arcs
8 9 10 節點 Nodes 弧 Arcs 7 弧上函數Function on Arcs 10

3 4.1網路介紹 Introduction (p. 236) 網路模型之重要性 許多企業問題可以用網路模型表示
因特殊數學結構，網路問題之最佳解為整數解. 網路問題可以有效的以數學演算法求解.

4 4.1 網路介紹 (p. 236~237) 常見網路模型 運輸模型(Transportation Model)
轉運模式(Transshipment Model) 指派模式(Assignment Model) 最短路徑模式 (Shortest Path Model) 最大流量模式 (Max Flow Model) 推銷員模式 (Traveling Salesman Model) 最小展開樹模式 (Minimal Spanning Tree Model)

5 網路專有名詞 Network Terminology (p.238~239)
流量 Flow 兩節點由node i至 node j運送的數量。使用符號如下: Xij = amount of flow Uij =流量上限(產能) Lij = l流量下限(產能) 有向與無向弧 Directed/undirected arcs 流量只有一個方向之弧為有向弧(以箭頭表示) 流量允許兩個方向之弧為無向弧(無箭頭表示). 相鄰節點 Adjacent nodes 存在一弧連接兩節點node i 與 node j 時，此二節點為相鄰節點

6 網路專有名詞 Network Terminology
路徑Path /相連路徑 Connected nodes 路徑乃是一系列連接相鄰節點的弧所構成的集合 兩節點若相連接，則兩節點中存在一條路徑 循環Cycles ：由一點出發，循一條路徑而不重複的經由一條弧回到該點則稱該路徑為「循環」 樹Trees ：一系列節點的一組弧不形成任何Cycles，則這組弧稱為「樹」 展開樹 Spanning Trees ：連接網路中所有節點的樹稱為「展開樹 」 ( 有n個點之展開樹有n -1弧)

7 4.2 運輸問題 (p.240) The Transportation Problem
運輸問題乃是考量將物品由有限的供應起點(Supply Points)運送到有需求的目的地(Demand Points) 所需花費的成本效益的問題

8 運輸問題 The Transportation Problem
模型定義 Problem definition 有 m 個來源(sources) . Source i 有 Si 的供應量 有 n 個目的地(destinations). Destination j 有 Dj 的需求量 Source i 到 Destination j 有單位運輸成本Cij 目標: 使得由來源處運送資源到目的地的總運輸成本為最小

9 Carlton製藥公司 CARLTON PHARMACEUTICALS
此公司有三家工廠分別位於: Cleveland, Detroit, Greensboro. 此公司有四家倉庫分別位於: Boston, Richmond, Atlanta, St. Louis. 公司必須將工廠生產的藥品依照需求運送至各個倉庫，希望能以最經濟之方式運送這些疫苗

10 Carlton製藥公司 資料 Data (Table 4.1) 假設Assumptions (p.242)
單位運輸成本Unit shipping cost,供應量 supply, 需求量demand 假設Assumptions (p.242) 單位運輸成本為固定常數 所有運輸同時發生 運輸物品只發生在來源點與目的地間運送 總供應量 =總需求量. To (Demand Pts) From (Supply Pts) Boston Richmond Atlanta St. Louis Supply Cleveland $35 30 40 32 1200 Detroit 37 40 42 25 1000 Greensboro 40 15 20 28 800 Demand 1100 400 750 750

11 Carlton製藥公司網路運輸模式

12 Destinations Boston Sources Cleveland Richmond Detroit Atlanta
St.Louis Destinations Sources Cleveland Detroit Greensboro D1=1100 37 40 42 32 35 30 25 15 20 28 S1=1200 S2=1000 S3= 800 D2=400 D3=750 D4=750

13 Carlton製藥公司 – Linear Programming Model (p.243)
模式結構如下： 最小化 <總運輸成本> ST [各Source運出的數量] <= [該Source之總供應量] [各目的地destination收到之數量] = [目的地的總需求量] [運輸量為非負值] 決策變數 Decision variables Xij =由 plant i 運往 warehouse j 的數量 其中 i=1 (Cleveland), 2 (Detroit), 3 (Greensboro) j=1 (Boston), 2 (Richmond), 3 (Atlanta), 4(St.Louis)

14 The Supply Constraint 供應限制式
Cleveland S1=1200 X11 X12 X13 X14 Supply from Cleveland X11+X12+X13+X14 = The Supply Constraint 供應限制式 Detroit S2=1000 X21 X22 X23 X24 Supply from Detroit X21+X22+X23+X24 = Boston Greensboro S3= 800 X31 X32 X33 X34 Supply from Greensboro X31+X32+X33+X34 = D1=1100 Richmond D2=400 Atlanta D3=750 St.Louis D4=750

15 Carlton製藥公司– 完整數學模式 一個供應節點總運送量不能超 過該節點的供應量.. 各目的地收到之總數量必須等於 該目的地的總需求量
= 各目的地收到之總數量必須等於 該目的地的總需求量

16 Carlton製藥公司 Spreadsheet
=SUMPRODUCT(B7:E9,B15:E17) =SUM(B7:E7) 拖曳至 cells G8:G9 =SUM(B7:B9) 拖曳至 cells C11:E11

17 Carlton製藥公司 Spreadsheet
MINIMIZE 總成本 運送量 滿足需求量且未超過供應量

18 Carlton製藥公司 Spreadsheet – 求解報告
12條路線中，最佳解只使用了6個(Why??)

19 Carlton製藥公司(p. 246) Spreadsheet – 敏感度分析報告
縮減成本 位於Cleveland與Atlanta間之單位成本需至少減少$5, 才能成為經濟上可利用 此路線在目前成本結構下，運送每單位會增加成本$5

20 Carlton製藥公司 (p. 246) Spreadsheet – 敏感度分析報告
Allowable Increase/Decrease 最佳範圍[35-5,35+2] =[30,37] 位於Cleveland與Atlanta間之單位成本增加量不多於 $2 或減少量不多於 $5，將不會影響目前最佳解

21 Carlton製藥公司 (p. 247) Spreadsheet – 敏感度分析報告
影價 Shadow prices 對工廠而言，影價透露該工廠每增加一單位產品的生產所產生的總成本的降低量 例如，Cleveland工廠的影價= -$2,表示若Cleveland工廠多生產一 單位疫苗將使總成本減少$2.

22 Carlton製藥公司 (p. 247) Spreadsheet – 敏感度分析報告
影價 Shadow prices 對倉庫而言，影價透露該倉庫每減少一單位疫苗的需求所產生的總成本的降低量 例如， Boston倉庫影價= $37,表示若Boston倉庫若減少一 單位疫苗需求將使總成本減少$37.

23 Shipments on a Blocked Route Xij = 0
運輸模式修改 1. 障礙路徑 (Blocked routes) – 特定運送路徑受阻礙或不能使用 解救方式 (Remedies): 指定該路徑一個很大的目標函數係數 (Cij = 1,000,000) 加入一個限制式於 Excel solver (Xij = 0) Shipments on a Blocked Route Xij = 0

24 運輸模式修改 障礙路徑 (Blocked routes) – 特定運送路徑受阻礙或不能使用 解救方式 (Remedies):
不要將代表障礙路徑的儲存格(e.g. C9) 放入 Changing cells中 只有將可行路徑設定於 Changing Cells Cell C9 不被包含在其中 Shipments from Greensboro to Richmond are prohibited

25 運輸模式修改 2. 最小運輸量 (Minimum shipment) – 有些路徑限制最小運輸量
解救方式 (Remedies): 加入一個限制式 (Xij ³ B) 到 Excel Solver 3. 最大運輸量 (Maximum shipment) – 有些路徑限制最大運輸量 加入一個限制式 (Xij £ B) 到 Excel Solver p.s. 若不想自己製作試算表，可使用光碟中的模板(Template) network.xls 來解決所有之流量模式 (p.249)

26 MONTPELIER 滑雪公司 (p.250) 使用運輸模式解決生產排程問題
Montpelier 計畫生產第三季(July, August, September)滑雪產品 生產產能與單位成本逐月改變 (表4.2) 公司可以以正常生產時間或加班方式生產生產 加班產能為正常產能之50% 生產水準應滿足預計需求量(demand forecasts)與季末(9月30日)庫存需求(end-of-quarter inventory requirement) 公司應安排一個最低成本的生產排程

27 MONTPELIER 滑雪公司 (p.251) Data:
起始庫存量(Initial inventory,七月份開始) = 200 pairs 期末庫存需求(Ending inventory required,九月底)=1200 pairs 下一季(十月份起)生產產能= 正常時間 400 pairs. =加班時間 200 pairs 庫存成本(Holding cost)為生產成本的 3%(每月,每雙) 本季生產產能與單位成本如下

28 需求分析 (Analysis of demand)
MONTPELIER 滑雪公司 Initial inventory 需求分析 (Analysis of demand) Net demand in July = = 200 pairs Net demand in August = 600 Net demand in September = = 2200 pairs 供給分析(Analysis of Supplies) 生產產能視為供應量 兩種供應量 Set 1- 正常時間供應 (production capacity) Set 2 –加班時間供應 In house inventory Forecasted demand

29 MONTPELIER 滑雪公司 單位成本Unit Cost= [單位製造成本Unit Production Cost ]
單位成本分析 (Analysis of Unit costs) 單位成本Unit Cost= [單位製造成本Unit Production Cost ] +[單位庫存成本Unit Holding Cost ]*[庫存月數] Example: A unit produced in July in regular time and sold in September costs 25+ (3%)(25)(2 months) = $26.50

30 網路表示 Production Month/period Month sold +M 37 +M 26 26.78 +M 29 +M 32
July R/T July R/T 25 25.75 26.50 1000 200 July July O/T 500 30 30.90 31.80 +M 37 +M 26 26.78 +M 29 Aug. R/T +M 32 32.96 800 Aug. 600 Demand Production Capacity Aug. O/T 400 Sept. 2200 Sept. R/T 400 300 Sept. O/T 200

31 MONTPELIER SKI COMPANY - Spreadsheet
(P.254頁表II5中存貨成本之計算方式) $0.75*(1000-0)+$0.9*( )=$1,020(July) $0.75*(1000-0)+$0.78*800=$1,374(August) ………….

32 MONTPELIER 滑雪公司 結論 Inventory + Production - Demand
In July 產量(1000 pairs in R/T, and 500 pairs in O/T). 七月底庫存量 = 1300 In August,產量(800 pairs in R/T, and 300 in O/T) 八月底額外庫存量= – 600=500 pairs. In September,產量400 pairs (clearly in R/T). 九月底庫存量=( ) = 1200 Inventory + Production - Demand

33 4.3 限制產能轉運問題 The Capacitated Transshipment Model
有時運輸的發生昰先將物品運送至轉運節點(Transshipment nodes)再送往目的地. 轉運節點 獨立之中繼點，本身無供應或需求 或其他的供應點或需求點 運輸問題弧上之流量有上限限制時稱為「限制產能轉運模式」

34 限制產能轉運問題 線性規劃模式: 決策變數：弧上流量(Flow on arcs) 目標函數：總運送成本最小 限制式：
供應點(Supply Node) – 淨流出量不能超過供應量 中繼點(Intermediate Node) –淨流出量=0 或 流出量=流入量 需求點(Demand node) –淨流入量等於需求量 弧容量限制：弧流量不能超過弧容量上限

35 DEPOT MAX(麥斯倉庫) A General Network Problem
Depot Max 有六家店舖在 Washington D.C. 地區

36 DEPOT MAX 5 6 在 Falls Church (FC) 與 Bethesda (BA)
DATA: -12 5 FC -13 6 BA

37 DEPOT MAX 在 Alexandria (AA) and Chevy Chase (CC)兩家店面可以分別提供 10 與 17單位 產品 DATA: -12 +10 1 5 FC AA -13 +15 2 6 BA CC

38 DEPOT MAX 在Fairfax (FX) 與 Georgetown (GN) 兩家店面為轉運節點：本身無供應量或需求量. DATA: -12 FX +10 1 3 5 FC AA Depot Max 希望以最小的成本將產品運送至FC and BA GN -13 +15 2 4 6 BA CC

39 DEPOT MAX 1 3 FC 2 4 BA DATA: 5 10 20 6 15 12 7 11 可能路線與運送單位成本如下圖所列
-12 FX +10 1 3 FC FC AA GN -13 +17 2 4 BA BA CC

40 DEPOT MAX Data(資料) 不同路線有最大產上限 不同路線有不同運送單位成本

41 DEPOT MAX – Types of constraints(限制式類型)
5 10 20 6 15 12 7 11 -12 +10 1 3 5 供應節點(Supply nodes) [節點淨流出量] < = [節點供應量] X12 + X13 + X15 - X <= 10 (Node 1) X21 + X24 - X <= 17 (Node 2) 中繼轉運節點(Intermediate transshipment nodes) [節點總流出量] = [節點總流入量] X34+X35 = X (Node3) X46 = X24 + X34 (Node 4) 7 需求節點(Demand nodes) [節點總流入量] = [需求節點量] X15 + X35 +X65 - X56 = 12 (Node 5) X46 +X56 - X = (Node 6) 2 4 6 -13 +17

42 All variables are non-negative
DEPOT MAX 完整數學模式 Min 5X X X X X X34 + 7X X X56 + 7X65 S.T. X12 + X13 + X15 – X £ 10 - X X21 + X £ 17 – X X34 + X = 0 – X24 – X X = 0 – X – X35 + X56 - X65 = -12 -X46 – X56 + X65 = -13 X12 £ 3; X15 £ 6; X21 £ 7; X24 £ 10; X34 £ 8; X35 £ 8; X46 £ 17; X56 £ 7; X65 £ 5 All variables are non-negative

43 DEPOT MAX – 試算表 ( P.258) 課本數據有誤，請訂正

44 4.4 指派問題 The Assignment Problem (p.259)
問題定義 m 位員工被指派到 m 項工作 Cij 為員工 i 從事工作 j 的單位成本. 目標：指派每位員工一份工作且每份工作皆被執行而使的總成本最小(或總利潤最大).

45 波爾司頓電子公司 BALLSTON ELECTRONICS (p.260)
有五種電子產品在五條生產線生產，每種產品皆需要被檢查。 每條生產線之產品運送至每一個檢查站所需要的時間也不一樣。 管理者希望決定(生產線─檢查區)的指派方式，以使得總搬運時間最小.

46 波爾司頓電子公司 BALLSTON ELECTRONICS
資料: 生產線運送至檢查區之搬運時間

47 波爾司頓電子公司 網路表示方式

48 1 2 3 4 5 生產線 檢查區 A B C D E S1=1 S2=1 S3=1 S4=1 S5=1 D1=1 D2=1 D3=1 D4=1 D5=1

49 BALLSTON ELECTRONICS – 線性規劃模式
Min 10X11 + 4X12 + … X X55 S.T. X11 + X12 + X13 + X14 + X15 = 1 X21 + X … X25 = 1 … … … … X51 + X52+ X53 + X54 + X55 = 1 All the variables are non-negative

50 BALLSTON ELECTRONICS – 電腦求解 (p.262)
窮舉法無法有效求解 當 m=5, m! = 120 指派方式 當 m=8, m! > 40,000 指派方式 匈牙利法(Hungarian method) 提供有效求解方式

51 BALLSTON ELECTRONICS – 以運輸問題模式之試算表解
=SUMPRODUCT(B7:F11,B17:F217) =SUM(B7:F7) Drag to cells H8:H12 =SUM(B7:B11) Drag to cells C13:F13

52 BALLSTON ELECTRONICS – 以運輸問題模式之試算表解
每個檢查區皆有產品被檢查 每條生產線接被指派

53 BALLSTON ELECTRONICS – 指派問題模板

54 指派問題模型修正- Modifications
不平衡指派問題 (Unbalanced problem): # of supply nodes ≠ # of demand nodes. 禁止指派(Prohibitive assignments) 某特定供應節點不能被指派到特定需求節點 多重指派(Multiple assignments) 某特定供應節點可以被指派到一個以上特定需求節點. 極大化指派問題 (A maximization assignment problem)