基于不確定圖的網(wǎng)絡(luò)優(yōu)化模型及應(yīng)用研究

發(fā)布時間：2020-07-24 05:16

【摘要】：隨著社會的不斷發(fā)展,圖論與網(wǎng)絡(luò)優(yōu)化的應(yīng)用越來越廣泛,大量的實際問題可抽象為圖與網(wǎng)絡(luò)優(yōu)化的問題。本文主要采用圖論、不確定理論、不確定規(guī)劃、最優(yōu)化理論等知識與方法研究不確定圖及基于不確定圖的網(wǎng)絡(luò)優(yōu)化問題。在深入學習圖論及不確定理論的基礎(chǔ)上,完善了不確定圖的一般概念及相關(guān)性質(zhì)定理的推導(dǎo)與證明,設(shè)計了求解不確定圖連通度的改進Prim算法。根據(jù)不確定規(guī)劃,從三種不同的建模機理,建立了基于不確定圖的六種網(wǎng)絡(luò)優(yōu)化模型,并設(shè)計了它們的求解模擬算法。在應(yīng)用實例中,針對地下物流系統(tǒng)進行了物流節(jié)點的選址及其網(wǎng)絡(luò)路線規(guī)劃。主要工作如下:(1)不確定圖的定義、矩陣表示、及相關(guān)性質(zhì)定理的研究。利用不確定理論將隨機、模糊、粗糙及它們交叉不確定性因素進行了統(tǒng)一。首先,類比邊結(jié)構(gòu)不確定圖的定義,借助鄰接矩陣的形式,提出了不確定圖的定義,它統(tǒng)一了邊結(jié)構(gòu)不確定圖、點結(jié)構(gòu)不確定圖與確定圖的概念。然后,提出了利用不確定測度矩陣對不確定圖進行統(tǒng)一標識,并分別在確定圖和不確定圖兩種情況下,對不確定測度矩陣及鄰接矩陣、關(guān)聯(lián)矩陣進行了對比。其次,分析并證明了不確定圖的階數(shù)、邊數(shù)的性質(zhì)及其不確定分布。最后,基于Prim算法的思想,以不確定圖的階數(shù)的優(yōu)先級為貪心準則,設(shè)計了改進的Prim算法求解不確定圖的連通度,并利用數(shù)值實例驗證了算法的合理性。(2)基于不確定圖的網(wǎng)絡(luò)優(yōu)化模型及算法的研究。首先,在不確定圖的基礎(chǔ)上,分析了基于不確定圖的網(wǎng)絡(luò)的兩種類型:圖結(jié)構(gòu)不確定、圖屬性不確定。接下來,在“圖結(jié)構(gòu)不確定但屬性確定的網(wǎng)絡(luò)”的前提下,進行網(wǎng)絡(luò)優(yōu)化模型的構(gòu)建。然后,根據(jù)不確定規(guī)劃中三大建模機理:期望值規(guī)劃、相關(guān)機會規(guī)劃、機會約束規(guī)劃,分別針對最短路及物流選址問題,建立了基于不確定圖的期望值最短路優(yōu)化模型、最大可能性最短路優(yōu)化模型、α-最短路優(yōu)化模型、及期望值物流選址模型、最大可能性物流選址模型、α-物流選址優(yōu)化模型。其次,從多個角度對構(gòu)建的網(wǎng)絡(luò)優(yōu)化模型進行了對比分析。最后,類比隨機模擬及模糊模擬方法,設(shè)計了求解模型的模擬算法,即通過模擬算法模擬不確定函數(shù)將不確定圖的網(wǎng)絡(luò)優(yōu)化模型轉(zhuǎn)化為確定性網(wǎng)絡(luò)優(yōu)化模型;再用相應(yīng)的算法求解。(3)針對緩解城市交通擁堵的新型系統(tǒng)——地下物流系統(tǒng),進行物流節(jié)點選址及最佳隧道網(wǎng)絡(luò)規(guī)劃的實例研究。首先,基于對不確定圖及不確定圖的網(wǎng)絡(luò)的研究,只要將區(qū)域中心位置看作不確定圖中的頂點、兩物流節(jié)點對應(yīng)的區(qū)域有貨運關(guān)系看作兩頂點間有邊,那么地下物流系統(tǒng)規(guī)劃問題可抽象為不確定圖的網(wǎng)絡(luò)優(yōu)化問題。然后,基于物流節(jié)點不確定,建立不確定圖中頂點和邊的不確定測度的計算模型,利用各區(qū)域的實時交通擁堵指數(shù)刻畫在各區(qū)域被修建地下物流節(jié)點的不確定測度,兩地間的貨運量刻畫邊的不確定測度。最后,構(gòu)建最大可能性物流選址模型,并基于本文設(shè)計的模擬算法及交替選址-分配法對模型求解,解決了地下物流系統(tǒng)的物流節(jié)點選址及最佳隧道網(wǎng)絡(luò)規(guī)劃。
【學位授予單位】：西南石油大學
【學位級別】：碩士
【學位授予年份】：2018
【分類號】：O157.5
【圖文】：