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

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

TSP問(wèn)題可以通過(guò)枚舉的方法用計(jì)算機(jī)求解不同的路線共有(n-1)！條枚舉城市數(shù)與計(jì)算時(shí)間的關(guān)系城市數(shù)2425262728293031計(jì)算時(shí)間1s24s10m4.3h4.9d136.5d10.8a325a當(dāng)城市個(gè)數(shù)增大到一定數(shù)量時(shí)枚舉方法行不通

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

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

將問(wèn)題轉(zhuǎn)化為一個(gè)TSP問(wèn)題：再將三點(diǎn)收縮成一點(diǎn)，就得到

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

接下來(lái)的工作是要均衡各個(gè)巡視小組的工作時(shí)間（十分復(fù)雜的工作！）05年杭州電子科技大學(xué)校內(nèi)競(jìng)賽題B題

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

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

2.計(jì)算機(jī)模擬常用計(jì)算機(jī)輔助算法有：常用的計(jì)算機(jī)搜索算法有遺傳算法,模擬退火算法等,需要有一定的算法設(shè)計(jì)基礎(chǔ)和基本的編程能力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張.建立以下問(wèn)題的數(shù)