網(wǎng)絡優(yōu)化及實例PPT學習教案

1、會計學1網(wǎng)絡優(yōu)化及實例網(wǎng)絡優(yōu)化及實例例：中國郵遞員問題例：中國郵遞員問題(CPP-Chinese Postman Problem)一名郵遞員負責投遞某個街區(qū)的郵件一名郵遞員負責投遞某個街區(qū)的郵件. . 如何設計一條最短如何設計一條最短的投遞路線的投遞路線( (從郵局出發(fā)，經(jīng)過投遞區(qū)內(nèi)每條街道至少一次從郵局出發(fā)，經(jīng)過投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局，最后返回郵局) )？由于這一問題是我國學者？由于這一問題是我國學者管梅谷管梅谷教授教授19601960年首先提出的，所以國際上稱之為中國郵遞員問題年首先提出的，所以國際上稱之為中國郵遞員問題. . 一、網(wǎng)絡優(yōu)化及實例一、網(wǎng)絡優(yōu)化及實例單向？雙向

2、？第1頁/共25頁第2頁/共25頁七橋問題七橋問題答案答案的的是是因為圖中沒有偶度頂點第3頁/共25頁21 nI， TSPTSP（Travel Sales Travel Sales Man ProblemMan Problem）問題）問題例例4 4設有城市集合設有城市集合，城市，城市ij到城到城市市的費用為的費用為，ijcnji, 1,求從指定城市出發(fā)，經(jīng)過所有其他城市恰好求從指定城市出發(fā)，經(jīng)過所有其他城市恰好一次，且使總費用最少的旅行路線。一次，且使總費用最少的旅行路線。第4頁/共25頁枚舉城市數(shù)與計算時間的關系 城市數(shù)城市數(shù) 24 25 26 27 28 29 30 31計算時間計算時間1

3、s 24s 10m 4.3h 4.9d 136.5d10.8a 325a當城市個數(shù)增大到一定數(shù)量時枚舉方法當城市個數(shù)增大到一定數(shù)量時枚舉方法行不通行不通 ! !第5頁/共25頁全國數(shù)學建模競賽題中有一些全國數(shù)學建模競賽題中有一些NPNP困難問題的困難問題的例子，需要用現(xiàn)有的軟件結(jié)合編程進行計算，例子，需要用現(xiàn)有的軟件結(jié)合編程進行計算，這一類近似算法的設計需要較寬的數(shù)學知識這一類近似算法的設計需要較寬的數(shù)學知識面和較強的創(chuàng)新能力面和較強的創(chuàng)新能力數(shù)學建模競賽十分強調(diào)模型與數(shù)學建模競賽十分強調(diào)模型與算法的創(chuàng)新性算法的創(chuàng)新性第6頁/共25頁第7頁/共25頁災情巡視路線災情巡視路線(CUMCM-199

4、8B)多人TSP問題的擴展第8頁/共25頁第9頁/共25頁接下來的工作是要均衡各個巡視小組接下來的工作是要均衡各個巡視小組的工作時間的工作時間（十分復雜的工作?。ㄊ謴碗s的工作！）第10頁/共25頁 設下圖中每一個圓點代表一個區(qū)，連接各圓點的設下圖中每一個圓點代表一個區(qū)，連接各圓點的直線代表公路，粗實線代表交通主干線，曲線代直線代表公路，粗實線代表交通主干線，曲線代表一條河流。隨著城市經(jīng)濟發(fā)展表一條河流。隨著城市經(jīng)濟發(fā)展,為了便利河兩岸為了便利河兩岸的交通，決定在適當?shù)奈恢迷鞓颉＜僭O河流北側(cè)的交通，決定在適當?shù)奈恢迷鞓?。假設河流北側(cè)A到到D段有沿岸公路，河的南側(cè)當前還沒有修建沿段有沿岸公路，

5、河的南側(cè)當前還沒有修建沿岸公路。試分別就以下問題討論：岸公路。試分別就以下問題討論：第11頁/共25頁問題二：河流為圖中曲線，分別討論總建設費問題二：河流為圖中曲線，分別討論總建設費用最小化和以便捷交通為原則的建設方案。用最小化和以便捷交通為原則的建設方案。問題三：如果計劃建兩座橋問題三：如果計劃建兩座橋,地址又該如何選擇地址又該如何選擇？第12頁/共25頁AD第13頁/共25頁常用網(wǎng)絡優(yōu)化算法有常用網(wǎng)絡優(yōu)化算法有復雜問題通常綜合非線性優(yōu)化和多目標規(guī)劃復雜問題通常綜合非線性優(yōu)化和多目標規(guī)劃第14頁/共25頁常用計算機輔助算法有：常用計算機輔助算法有：常用的計算機搜索算法有遺傳算法,模擬退火算法

6、等,需要有一定的算法設計基礎和基本的編程能力第15頁/共25頁第16頁/共25頁算法質(zhì)量關鍵算法質(zhì)量關鍵: 1.精度精度 2. 效能效能第17頁/共25頁第18頁/共25頁A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7鐵路運價表里程300301350351400

7、401450451500運價2023262932 鋼管運輸問題鋼管運輸問題（CUMCM-CUMCM-2000B)2000B)第19頁/共25頁第20頁/共25頁 鋼管運輸問題鋼管運輸問題（CUMCM-CUMCM-2000B)2000B)第21頁/共25頁 鋼管運輸問題鋼管運輸問題（CUMCM-CUMCM-2000B)2000B). 7,.,1, 1 , 0, 0.14,.,1.15,.,1,. 7,.,1,500. .)1 ()1(21 . 0)(151171151151,ifzyjbzyjzyxifSxftszzyyxcpMinijjjjjiijiijijijjjjjjiijijiLINDO/LINGO得到的結(jié)果比得到的結(jié)果比matlab得到的好得到的好cumcm2000b.lg4第22頁/共25頁 算法設計中應該注意的問題算法設計中應該注意的問題1. 1. 線性規(guī)劃是有效算法線性規(guī)劃是有效算法, ,可以線性化的可以線性化的問題不用非線性模型問題不用非線性模型2.2.整數(shù)線性規(guī)劃、二次規(guī)劃及其他非線整數(shù)線性規(guī)劃、二次規(guī)劃及其他非線性規(guī)劃模型除了可以利用數(shù)學軟件求解性規(guī)劃模型除了可以利用數(shù)學軟件求解外外, ,