《网路模型NetworkModels.ppt》由会员分享，可在线阅读，更多相关《网路模型NetworkModels.ppt（46页珍藏版）》请在三一办公上搜索。
1、1,網路模型NetworkModels,Chapter 4,2,給定一個網路，目標為從起始節點(start node)行經可能節點，以最短距離、最少時間或最低成本，最後到達終止節點(terminal node)問題定義(p.265)共有 n個節點,由節點 1開始到終止節點 n.連接節點i 與 j 的弧j為雙向通行(Bi-directional)的，且其距離 dij 為非負的找出連結節點 1 到節點 n，總距離路徑為最短,4.5 最短路徑模型(p.264)The Shortest Path Model,3,找出由Seattle 到 El Paso 距離最短的路徑,FAIRWAY 貨運公司(p.2
2、65),注意：若問題中有雙向的弧時，於兩個節點中，製造兩個反向的弧,4,8,9,7,11,12,1,4,3,6,2,10,5,Salt Lake City,El Paso,Seattle,Boise,Portland,Butte,Cheyenne,Bakersfield,Las Vegas,Albuquerque,Tucson,Phoenix,599,691,497,180,432,345,440,554,621,420,280,432,403,314,893,500,290,116,268,577,5,決策變數,目標=Minimize S dijXij,FAIRWAY 貨運公司(p.266)
3、線性規劃模式,6,6,2,Salt Lake City,1,3,4,Seattle,Boise,Portland,599,497,180,432,345,Butte,卡車駛離 Seattle(the start node)的道路數=1X12+X13+X14=1,卡車駛進El Paso(terminal node)的道路數=1X9,12+X10,12+X11,12=1,卡車駛進某城市的道路數=卡車駛離某城市的道路數.例如,在 Boise(node 4)城市:X14+X34=X46.,限制式:,Non-negativity constraints,7,FAIRWAY 貨運公司 使用模板(p.267
4、),8,The Dijkstras algorithm:找出由“START”節點到所連接節點之最短距離一旦第m個最接近之節點決定(覆蓋)後，則第(m+1)個節點可以容易地被決定(覆蓋)重複此演算法則直到網路上所有節點被決定為止,FAIRWAY 貨運公司 網路模型,9,Dijkstras 演算法說明,(見光碟Supplement CD 5).,10,SEAT.,842,直到所有節點被覆蓋為止,11,Dijkstras algorithm-continued,當所有節點被覆蓋後，最短路線將可以被確認.以後退方式(Backtracking)由終點節點追蹤到起點節點即可找到此最短路線.,12,問題定義
5、(p.268)有一個來源節點(source node)(labeled 1)有一個終止節點(terminal source node)(labeled n)有n-2個中繼節點(labeled 2,3,n-1),其中 流入量=流出量節點i至節點j 之最大流量限制為Cij.,4.6 最大流量問題The Maximal Flow Problem,13,目標：在不超過最大弧容量限制之下，使得由節點1到節點n的總流量最大,最大流量問題,14,UNITED 化學公司生產農藥與草皮保養品有毒原料需要儲存在儲油槽中此公司有運送管線系統，將化學藥品運送至不同生產區緊急計劃中，安全部門必須在最短時間內，將儲油槽中
6、之化學原料經由管線導入安全容器中(見圖4.24).,UNITED 化學公司(p.269),15,計劃昰，決定：應開啟或關閉哪些活門 由儲存槽至安全容器之總運送時間為何?,UNITED 化學公司(p.269),16,UNITED 化學公司網路表示圖形,17,Data,1,7,2,4,6,5,3,化學儲存槽,安全容器,10,8,10,6,1,12,1,4,4,2,2,8,3,3,7,2,由節點2 到 4節點之最大弧容量為8,由節點6 到 3節點之最大弧容量為 4,18,決策變數Xij 由節點 i 至 節點 j 之流量目標函數 Maximize Max X12+X13(使得 node 1之淨流出量為
7、最大),UNITED 化學公司 線性規劃模式,19,限制式(所有中繼節點intermediate node)Flow out from the node-flow into the node=0Node 2:X23+X24+X26-X12-X32=0Node 3:X32+X35+X36-X13-X23-X63=0Node 4:X46+X47-X24-X64=0Node 5:X56+X57-X35-X65=0Node 6:X63+X64+X65+X67-X26-X36-X46-X56=0,UNITED 化學公司 線性規劃模式,20,限制式 continued 流量不能超過弧容量上限X12 10;
8、X13 10;X23 1;X24 8;X26 6;X32 1;X35 15;X36 4;X46 3;X47 7;X56 2;X57 8;X63 4;X64 3;X65 2;X67 2;流量為非負數 All Xij 0,UNITED 化學公司 線性規劃模式,21,UNITED CHEMICAL COMPANY 使用模板(p.271),22,1,2,3,7,10,7,2,8,2,7,5,6,4,3,3,2,8,6,2,(最大流量/最小切割定理)(p.273)最大流量值=最小切割產能總數,切割(cuts)在最大網路中扮演之角色,此切割之最大流量為23,此切割之最大流量為17,7,此切割最大流量17,
9、23,4.7 推銷員網路The Traveling Salesman Problem,問題定義(p.274)有m個節點.由節點i至節點j弧的單位成本為Cij 目標：找出一個循環(cycle)使得通過所有節點之總距離為最短，且不得通過同一個節點兩次,24,推銷員問題The Traveling Salesman Problem,重要性(Importance):許多排程(scheduling application)問題可以用推銷員問題求解範例：:郵差送信路線.通勤巴士路線(School bus routing).軍隊炸彈佈置(Military bombing sorties),25,推銷員問題Th
10、e Traveling Salesman Problem,複雜度(Complexity)推銷員問題以數學方法敘述很麻煩。有20城市之問題，就需要 500,000個線性限制式,26,聯邦緊急事件管理協會(p.274)FEDERAL EMERGENCY MANAGEMENT AGENCY,FEMA總部辦公室為因應地震問題,必須到其他四個地區辦公室巡視 Data辦公室間之往來時間(minutes),27,FEMA推銷員問題網路表示法(p.275),28,30,25,40,35,80,65,45,50,50,40,Home,1,2,3,4,29,FEMA-推銷員問題,求解方法窮舉法：找出所有可能的循環
11、(all possible cycles)M個節點之問題，可能有(m-1)!循環.對稱之問題，實際只有(m-1)!/2循環僅適用於小問題10個節點之問題有181440個循環15個節點之問題有840兆個循環以指派問題(Assignment Problem)與分枝界限法(Branch&Bound)之組合，可以有效解決20 個(m=20)節點以內之推銷員問題,30,可能循環循環總成本 1.H-O1-O2-O3-O4-H210 2.H-O1-O2-O4-O3-H 195 3.H-O1-O3-O2-O3-H 240 4.H-O1-O3-O4-O2-H 200 5.H-O1-O4-O2-O3-H 225
12、6.H-O1-O4-O3-O2-H 200 7.H-O2-O3-O1-O4-H 265 8.H-O2-O1-O3-O4-H 235 9.H-O2-O4-O1-O3-H 25010.H-O2-O1-O4-O3-H 22011.H-O3-O1-O2-O4-H 26012.H-O3-O1-O2-O4-H260,Minimum,對稱之問題，實際只有(m-1)!/2循環FEMA有問題(5-1)!/2=12個可能循環,FEMA問題 所有計算,31,30,25,40,35,80,65,45,50,50,40,Home,1,2,3,4,FEMA 最佳解,32,將“From”節點視為“Workers”節點.將“
13、To”節點視為“Jobs”節點.將“Workers”以最低成本指派給“Jobs”,FEMA 以指派問題模式求解(p.277),33,Data,FEMA 以指派問題模式求解,34,FEMA 指派模型的解,30,25,40,35,80,65,45,50,50,40,Home,1,2,3,4,O3 O4 O3Sub-tour(子路徑）i.e.X34+X43=2,O1 O2 H O1Sub-tour（子路徑）i.e.X12+X2H+XH1=3,35,為避免子途徑(sub-tour)之發生，我們必須加入限制式使得子循環(Cycle)無法產生使得問題變的很大,FEMA 指派模型的解,O1 O2 H O1S
14、ub-tour（子途徑）i.e.X12+X2H+XH1=3,O1 O2 H O1Sub-tour（子路徑）i.e.X12+X2H+XH12,加入3節點(3-node)子途徑限制式,O3 O4 O3Sub-tour(子路徑）i.e.X34+X43=2,加入2節點(2-node)子途徑限制式,O3 O4 O3Sub-tour(子路徑）i.e.X34+X431,36,4.8最小展開樹The Minimal Spanning Tree,最小展開樹之問題(Minimal Spanning Tree)昰一種網路架構，此網路中之所有節點必須互相連結，並且無循環(loop)產生一個展開樹(Spanning T
15、ree)昰以(n-1)個弧來連接n個節點的網路一個網路可以有非常多個展開樹，但只有一個最小展開樹(Minimal Spanning Tree),37,4.8 最小展開樹,問題定義(p.280)有n個節點.由節點i至節點j弧的距離為dij 目標：找出一組弧(Arcs)，能以最短距離將所有節點連接起來成一個展開樹,38,大都會捷運問題THE METROPOLITAN TRANSIT DISTRICT,39,大都會捷運問題THE METROPOLITAN TRANSIT DISTRICT,溫哥華城市計劃興建一捷運系統來連接八個住宅與商業中心捷運公司必須以最少成本將所有地點連接起來,40,大都會捷運問
16、題 網路示意圖,網路示意圖包含:規劃可行路線每條路線最低建築成本,41,5,2,6,4,7,8,1,3,West Side,North Side,University,BusinessDistrict,East Side,ShoppingCenter,South Side,City Center,33,50,30,55,34,28,32,35,39,45,38,43,44,41,37,36,40,42,SPANNING TREE NETWORK PRESENTATION,5,2,6,4,7,8,1,3,West Side,North Side,University,BusinessDistri
17、ct,East Side,ShoppingCenter,South Side,City Center,33,50,30,55,34,28,32,35,39,45,38,43,44,41,37,36,40,43,求解 網路求解(見光碟中補充講義Supplement CD 5)網路算則採用貪婪法”greedy procedure”.The algorithm 第一種形式(version 1)選取最短距離之弧，放入已選取弧之集合(a set of selected arcs)每次反覆中，將下一個最短距離之弧加入已選取弧之集合，但避免產生Cycle重複上列敘述，直到所有節點都被連接起來為止,THE M
18、ETROPOLITAN TRANSIT DISTRICT,44,The algorithm 第二種形式(version 2)選取最短距離之弧，放入已連結弧之集合(a set of connected arcs)每次反覆中，自未選取之弧集合(unselected arcs)中，加入與已連結集合有連結之最短弧，但要避免產生Cycle重複上列敘述，直到所有節點都被連接起來為止請見第二種形式之展示,THE METROPOLITAN TRANSIT DISTRICT,45,ShoppingCenter,Loop,2,6,4,7,8,West Side,North Side,University,Busi
19、nessDistrict,East Side,South Side,City Center,50,30,55,34,28,32,35,39,45,38,43,44,41,37,36,40,Total Cost=$236 million,OPTIMAL SOLUTIONNETWORKREPRESENTATION,5,Loop,Loop,Loop,Loop,Loop,Loop,Loop,Loop,Loop,Loop,Loop,Loop,Loop,Loop,Loop,1,3,33,28,32,30,33,46,ShoppingCenter,4,7,8,West Side,North Side,University,BusinessDistrict,East Side,South Side,City Center,50,30,55,34,28,32,35,39,45,38,43,44,41,37,36,40,Total Cost=$236 million,OPTIMAL SOLUTIONNETWORKREPRESENTATION,5,3,33,1,6,2,
