[轉(zhuǎn)]2018研究生數(shù)學(xué)建模競賽B題-光傳送網(wǎng)建模與價(jià)值評(píng)估-競賽總結(jié)

這道賽題是有關(guān)通信方面的賽題,初步讀題,感到第一問和第二問關(guān)系不大,第二問和第三問關(guān)系也不大,不過第一問和第三問有比較緊密的順承關(guān)系.

1-1

第一問主要討論在光纖通信環(huán)境下,與光信號(hào)傳輸有關(guān)的調(diào)制解調(diào)的誤碼率問題.在題設(shè)條件中,糾前誤碼率(BER)只與信噪比(SNR)有關(guān).因此題目要求我們建立數(shù)學(xué)模型描述兩者的關(guān)系.

對(duì)于該問題有兩種思路:

建立機(jī)理模型

也就是通過對(duì)光纖中的入纖信號(hào),與信號(hào)噪聲進(jìn)行概率描述,然后推導(dǎo)出出纖信號(hào)的概率描述,從而通過對(duì)概率密度函數(shù)的二重積分,直接計(jì)算出兩者的解析關(guān)系.

實(shí)驗(yàn)?zāi)Ｐ?/p>

也就是使用計(jì)算機(jī)仿真的方式,通過大量的實(shí)驗(yàn),模擬信號(hào)輸入,編碼,噪聲輸入,解碼,計(jì)算誤碼率的過程,對(duì)誤碼率進(jìn)行計(jì)算.根據(jù)大數(shù)定律,大量實(shí)驗(yàn)的結(jié)果會(huì)趨近于第一種思路的機(jī)理模型的解.

兩種方法的比較

第一種方法有著更強(qiáng)的數(shù)學(xué)要求,但是推到的結(jié)果顯示,最后的結(jié)果是一個(gè)正態(tài)分布函數(shù)的二重積分的加權(quán)和.計(jì)算這個(gè)函數(shù)的積分其實(shí)十分困難,還是要借助數(shù)值計(jì)算的工具或者查表.無法有效的得到一條表達(dá)式.

第二種方法較容易實(shí)現(xiàn),但是在試驗(yàn)次數(shù)較小的情況下,得到的曲線會(huì)引入較大誤差.造成求解曲線的不平滑.因此得到平滑的曲線需要花費(fèi)較大的計(jì)算時(shí)間.在我的電腦上計(jì)算時(shí)間大概有半個(gè)小時(shí).

在這里給出一張求解圖.

1-2

第二問主要是對(duì)整個(gè)傳輸?shù)墓饴愤M(jìn)行建模,要考慮光在線纜中引入的噪聲,光放大器引入的噪聲,光在線纜中的功率衰減等因素,結(jié)合上文中算出的一個(gè)參數(shù)求解傳輸鏈路的段數(shù).

在這里給出模型和結(jié)果.

結(jié)果

2-1

第二問似乎與第一問沒有必然的聯(lián)系,這是一個(gè)整數(shù)規(guī)劃的問題,特別是在第一問中,這個(gè)證書規(guī)劃非常的純粹,因此可以直接建立整數(shù)規(guī)劃的模型,使用相應(yīng)的求解器進(jìn)行求解.

我們將問題直接轉(zhuǎn)化成了MIP問題,然后使用GUROBI工具進(jìn)行求解.

轉(zhuǎn)化成的問題如下圖.

其中Cij 表示 i 節(jié)點(diǎn)與 j 節(jié)點(diǎn)之間的傳輸容量,可依據(jù)節(jié)點(diǎn)間的距離選擇相應(yīng)的傳輸格式,從而判斷傳輸容量的大小况脆。本文認(rèn)為,若要使網(wǎng)絡(luò)價(jià)值最大化,必須要以容量利用率最大為標(biāo)準(zhǔn)來分配傳輸格式硝全。

λ ij 表示 i 節(jié)點(diǎn)與 j 節(jié)點(diǎn)之間鏈路的權(quán)重,M 為光傳輸網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)。

H i ,H j 分別表示 i 節(jié)點(diǎn)和 j 節(jié)點(diǎn)的人口數(shù)赡艰。當(dāng)所有節(jié)點(diǎn)的鏈接情況由決策

信息R ij 確定時(shí),目標(biāo)函數(shù)值中相應(yīng)的未知變量可進(jìn)一步求出并確定目標(biāo)函數(shù)值.

約束中限制了網(wǎng)絡(luò)連接數(shù),和孤立鏈路數(shù)量.

值得一題的是孤立鏈路這個(gè)約束.

在一開始我們解出的解如下圖:

可以看到,得到的解并不是一個(gè)連通的圖.但是作為一個(gè)光纖網(wǎng)絡(luò)來說,必然要求我們解出一個(gè)連通圖.因此我們加入了孤立鏈路這個(gè)新的約束.

這個(gè)約束可以保證所有組成的集合(全集和空集除外)都與其他點(diǎn)是連通的.加入當(dāng)前約束后得到的解如下圖所示.

對(duì)于33條鏈路的是這樣的.

2-2

第二問考慮到中轉(zhuǎn)節(jié)點(diǎn)的問題,最初考慮在第一問的基礎(chǔ)上進(jìn)行拓展,為每條路段增加一個(gè)分配變量,也就是在這些變量中描述當(dāng)前路段的資源是否進(jìn)行分配,分配給誰.

然后通過增加約束條件約束分配必須滿足題設(shè)需求.但是求解過程發(fā)現(xiàn)這樣的求解占用太多資源.因此我們考慮將問題轉(zhuǎn)化成為了一個(gè)層次優(yōu)化的問題.在描述這個(gè)問題前,我們通過一些數(shù)學(xué)推導(dǎo)將問題稍作簡化.

首先,中轉(zhuǎn)通信的可行性分析.

一條線路進(jìn)行中轉(zhuǎn)的可行性,主要是由引入這些中轉(zhuǎn)是否會(huì)帶來目標(biāo)(網(wǎng)絡(luò)價(jià)值)的提升判斷的.

如果引入這些中轉(zhuǎn)可以將網(wǎng)絡(luò)價(jià)值進(jìn)行提升,那么系統(tǒng)將義不容辭的引入這些中轉(zhuǎn)通信,如果不能,中轉(zhuǎn)通信將一定不會(huì)被引入.

因此在引入的價(jià)值該如何度量呢?

看下圖:

也就是說,當(dāng)權(quán)重保持不變的情況下. 引入中轉(zhuǎn)通信完全歸結(jié)為節(jié)點(diǎn)的人口問題,對(duì)于三個(gè)節(jié)點(diǎn)的判斷來說.當(dāng)中間點(diǎn)城市的人口數(shù)足夠小的情況下,引入中間節(jié)點(diǎn)通信是有好處的.

下面我們來進(jìn)行更加復(fù)雜的分析.

當(dāng)有多個(gè)城市需要占用同一個(gè)節(jié)點(diǎn)中轉(zhuǎn)時(shí),節(jié)點(diǎn)將為哪一個(gè)城市服務(wù)的問題.這個(gè)問題同樣該從網(wǎng)絡(luò)價(jià)值的角度分析.就是說我們要比較為誰服務(wù)可以獲得更多的網(wǎng)絡(luò)價(jià)值.

但是這個(gè)問題就沒有前面的問題那樣純粹了,因?yàn)檫@將變成一個(gè)整體性的問題.也是一個(gè)規(guī)劃問題.為了有效解決這個(gè)問題,本文件問題描述為一個(gè)兩層的最優(yōu)化問題的嵌套.

頂層的最優(yōu)化問題負(fù)責(zé)尋找最優(yōu)的網(wǎng)絡(luò)路徑,也就是像問題2-1一樣的規(guī)劃問題.第二個(gè)最優(yōu)化問題在上層給出的路徑的基礎(chǔ)上尋找一個(gè)最優(yōu)化的網(wǎng)絡(luò)配置,配置最優(yōu)化的中轉(zhuǎn)節(jié)點(diǎn)情況.

在這種情況下,我們本文采用兩層的架構(gòu),第一層使用遺傳算法作為框架,第二層使用約束式求解器GUROBI.

2-3 第三問是自由式的問題,因此在這里不做分享

第三問由于太直接,沒有太好的方法進(jìn)行求解,所以直接上了遺傳算法.

沒有什么有效的數(shù)學(xué)模型可以將問題化簡,大家有興趣可以直接看我的代碼.

代碼:

問題求解的正確性我還沒有作進(jìn)一步的考證,

在這里發(fā)表一些想法只做討論用.

代碼我已經(jīng)上傳到了github:?https://github.com/zangzelin/2018-Graduate-Mathematical-Modeling-Competition-B

希望覺得有幫助的同學(xué),star 一下

---恢復(fù)內(nèi)容結(jié)束---

# 2018研究生數(shù)學(xué)建模競賽B題-光傳送網(wǎng)建模與價(jià)值評(píng)估-競賽總結(jié)

1-1