網(wǎng)絡(luò)優(yōu)化及實(shí)例PPT學(xué)習(xí)教案

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

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

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

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

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

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

7、401450451500運(yùn)價(jià)2023262932 鋼管運(yùn)輸問(wèn)題鋼管運(yùn)輸問(wèn)題（CUMCM-CUMCM-2000B)2000B)第19頁(yè)/共25頁(yè)第20頁(yè)/共25頁(yè) 鋼管運(yùn)輸問(wèn)題鋼管運(yùn)輸問(wèn)題（CUMCM-CUMCM-2000B)2000B)第21頁(yè)/共25頁(yè) 鋼管運(yùn)輸問(wèn)題鋼管運(yùn)輸問(wèn)題（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頁(yè)/共25頁(yè) 算法設(shè)計(jì)中應(yīng)該注意的問(wèn)題算法設(shè)計(jì)中應(yīng)該注意的問(wèn)題1. 1. 線性規(guī)劃是有效算法線性規(guī)劃是有效算法, ,可以線性化的可以線性化的問(wèn)題不用非線性模型問(wèn)題不用非線性模型2.2.整數(shù)線性規(guī)劃、二次規(guī)劃及其他非線整數(shù)線性規(guī)劃、二次規(guī)劃及其他非線性規(guī)劃模型除了可以利用數(shù)學(xué)軟件求解性規(guī)劃模型除了可以利用數(shù)學(xué)軟件求解外外, ,