網(wǎng)絡(luò)優(yōu)化及實(shí)例課件

網(wǎng)絡(luò)優(yōu)化與優(yōu)化算法網(wǎng)絡(luò)優(yōu)化及實(shí)例例：中國(guó)郵遞員問題(CPP-ChinesePostmanProblem)一名郵遞員負(fù)責(zé)投遞某個(gè)街區(qū)的郵件.如何設(shè)計(jì)一條最短的投遞路線(從郵局出發(fā)，經(jīng)過投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局)？由于這一問題是我國(guó)學(xué)者管梅谷教授1960年首先提出的，所以國(guó)際上稱之為中國(guó)郵遞員問題.一、網(wǎng)絡(luò)優(yōu)化及實(shí)例單向？雙向？網(wǎng)絡(luò)優(yōu)化及實(shí)例歐拉把哥尼斯堡七橋問題轉(zhuǎn)化為一個(gè)圖論上的問題：給定一個(gè)圖，問是否存在點(diǎn)不重的環(huán)游？網(wǎng)絡(luò)優(yōu)化及實(shí)例七橋問題答案的是否定的因?yàn)閳D中沒有偶度頂點(diǎn)網(wǎng)絡(luò)優(yōu)化及實(shí)例有些問題目前找不到現(xiàn)成的軟件也沒有快速求解最優(yōu)解的方法TSP（TravelSalesManProblem）問題例4設(shè)有城市集合，城市到城市的費(fèi)用為求從指定城市出發(fā)，經(jīng)過所有其他城市恰好一次，且使總費(fèi)用最少的旅行路線。網(wǎng)絡(luò)優(yōu)化及實(shí)例

TSP問題可以通過枚舉的方法用計(jì)算機(jī)求解不同的路線共有(n-1)！條枚舉城市數(shù)與計(jì)算時(shí)間的關(guān)系

城市數(shù)2425262728293031計(jì)算時(shí)間1s24s10m4.3h4.9d136.5d10.8a325a當(dāng)城市個(gè)數(shù)增大到一定數(shù)量時(shí)枚舉方法行不通

!網(wǎng)絡(luò)優(yōu)化及實(shí)例二、最優(yōu)算法與近似算法有一些問題在計(jì)算復(fù)雜性上被稱做NP困難問題,對(duì)這一類問題尋找快速的近似算法是十分有意義的。全國(guó)數(shù)學(xué)建模競(jìng)賽題中有一些NP困難問題的例子，需要用現(xiàn)有的軟件結(jié)合編程進(jìn)行計(jì)算，這一類近似算法的設(shè)計(jì)需要較寬的數(shù)學(xué)知識(shí)面和較強(qiáng)的創(chuàng)新能力數(shù)學(xué)建模競(jìng)賽十分強(qiáng)調(diào)模型與算法的創(chuàng)新性網(wǎng)絡(luò)優(yōu)化及實(shí)例如：98年競(jìng)賽題B題是TSP問題

的一個(gè)變形從縣城出發(fā)分三個(gè)小組巡視受災(zāi)的地區(qū)各地的災(zāi)情，已知每個(gè)村鎮(zhèn)所需要的停留時(shí)間以及行車速度，問如何設(shè)計(jì)各組的巡視路線才能以最快的速度掌握整個(gè)地區(qū)全部的受災(zāi)情況？網(wǎng)絡(luò)優(yōu)化及實(shí)例災(zāi)情巡視路線(CUMCM-1998B)多人TSP問題的擴(kuò)展網(wǎng)絡(luò)優(yōu)化及實(shí)例考慮用一個(gè)圖來代替縣城結(jié)點(diǎn)，

將問題轉(zhuǎn)化為一個(gè)TSP問題：網(wǎng)絡(luò)優(yōu)化及實(shí)例再將三點(diǎn)收縮成一點(diǎn)，就得到

一個(gè)三個(gè)巡視組的TSP巡視路線

接下來的工作是要均衡各個(gè)巡視小組的工作時(shí)間（十分復(fù)雜的工作?。┚W(wǎng)絡(luò)優(yōu)化及實(shí)例05年杭州電子科技大學(xué)校內(nèi)競(jìng)賽題B題

是一個(gè)網(wǎng)絡(luò)優(yōu)化問題橋梁選址問題

設(shè)下圖中每一個(gè)圓點(diǎn)代表一個(gè)區(qū)，連接各圓點(diǎn)的直線代表公路，粗實(shí)線代表交通主干線，曲線代表一條河流。隨著城市經(jīng)濟(jì)發(fā)展,為了便利河兩岸的交通，決定在適當(dāng)?shù)奈恢迷鞓颉＜僭O(shè)河流北側(cè)A到D段有沿岸公路，河的南側(cè)當(dāng)前還沒有修建沿岸公路。試分別就以下問題討論：網(wǎng)絡(luò)優(yōu)化及實(shí)例問題一：河流為東西向的水平直線，各區(qū)規(guī)模大致相同。1.總建設(shè)費(fèi)用最低的橋梁位置和與之配套的公路設(shè)計(jì)方案；2.以便捷交通為原則的最佳橋梁位置和公路設(shè)計(jì)方案。問題二：河流為圖中曲線，分別討論總建設(shè)費(fèi)用最小化和以便捷交通為原則的建設(shè)方案。問題三：如果計(jì)劃建兩座橋,地址又該如何選擇？網(wǎng)絡(luò)優(yōu)化及實(shí)例問題四：如果各地的人口數(shù)不同，又該怎樣選擇合理的橋梁位置？AD網(wǎng)絡(luò)優(yōu)化及實(shí)例1.最小生成樹算法2.最短路算法3.網(wǎng)絡(luò)流算法4.匹配問題算法常用網(wǎng)絡(luò)優(yōu)化算法有復(fù)雜問題通常綜合非線性優(yōu)化和多目標(biāo)規(guī)劃網(wǎng)絡(luò)優(yōu)化及實(shí)例1.計(jì)算機(jī)搜索算法

2.計(jì)算機(jī)模擬常用計(jì)算機(jī)輔助算法有：常用的計(jì)算機(jī)搜索算法有遺傳算法,模擬退火算法等,需要有一定的算法設(shè)計(jì)基礎(chǔ)和基本的編程能力網(wǎng)絡(luò)優(yōu)化及實(shí)例05年全國(guó)競(jìng)賽題B題:DVD的在線租賃1.對(duì)100個(gè)會(huì)員的訂單和已有的DVD數(shù)量,如何分配才可以盡可能滿足要求?某網(wǎng)站提供DVD租賃服務(wù),根據(jù)以往數(shù)據(jù),有40%會(huì)員每月租賃一次,60%會(huì)員每月租賃兩次.規(guī)定每次租賃的DVD數(shù)量為3張.建立以下問題的數(shù)學(xué)模型:2.經(jīng)過網(wǎng)上調(diào)查,已有1000個(gè)會(huì)員的需求數(shù)據(jù),對(duì)總數(shù)n個(gè)會(huì)員,應(yīng)購(gòu)買各種新DVD多少?gòu)埐拍芤?5%的概率滿足需求?3.對(duì)給出的十萬個(gè)會(huì)員數(shù)據(jù)及DVD數(shù)量,求具體的分配方案.網(wǎng)絡(luò)優(yōu)化及實(shí)例1.DVD租賃問題可以用整數(shù)規(guī)劃求解2.會(huì)員數(shù)據(jù)信息量大,Lingo軟件可以與Excel表鏈接3.隨機(jī)數(shù)據(jù)可以利用概率統(tǒng)計(jì)知識(shí)進(jìn)行預(yù)處理,也可以建立隨機(jī)規(guī)劃模型4.會(huì)員滿意度可以用計(jì)算機(jī)隨機(jī)模擬方法估計(jì)5.會(huì)員數(shù)任意大時(shí),整數(shù)規(guī)劃不是一個(gè)快速算法,可以考慮建立一個(gè)諸如遺傳算法或蟻群算法之類的快速(近似)算法算法質(zhì)量關(guān)鍵:1.精度

2.

效能網(wǎng)絡(luò)優(yōu)化及實(shí)例網(wǎng)絡(luò)優(yōu)化及實(shí)例A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7鐵路運(yùn)價(jià)表里程≤300301～350351～400401～450451～500…運(yùn)價(jià)2023262932…

鋼管運(yùn)輸問題（CUMCM-2000B)網(wǎng)絡(luò)優(yōu)化及實(shí)例網(wǎng)絡(luò)優(yōu)化及實(shí)例常用解法:二次規(guī)劃先計(jì)算最小運(yùn)費(fèi)矩陣兩種運(yùn)輸方式（鐵路／公路）混合最短路問題是普通最短路問題的變種，需要自己設(shè)計(jì)算法

鋼管運(yùn)輸問題（CUMCM-2000B)網(wǎng)絡(luò)優(yōu)化及實(shí)例fi表示鋼廠i是否使用；xij是從鋼廠i運(yùn)到節(jié)點(diǎn)j的鋼管量yj是從節(jié)點(diǎn)j向左鋪設(shè)的鋼管量；zj是向右鋪設(shè)的鋼管量

鋼管運(yùn)輸問題（CUMCM-2000B)LINDO/LINGO得到的結(jié)果比matlab得到的好cumcm2000b.lg4網(wǎng)絡(luò)優(yōu)化及實(shí)例

算法設(shè)計(jì)中應(yīng)該注意的問題1.線性規(guī)劃是有效算法,可以線性化的問題不用非線性模型2.整數(shù)線性規(guī)劃、二次規(guī)劃及其他非線性規(guī)劃模型除了可以利用數(shù)學(xué)軟件求解外,討論問題推廣時(shí)應(yīng)設(shè)計(jì)快速近似算法3.一題多