幾個(gè)組合優(yōu)化問題的研究.pdf

1、山東大學(xué)博士學(xué)位論文幾個(gè)組合優(yōu)化問題的研究姓名：董振寧申請(qǐng)學(xué)位級(jí)別：博士專業(yè)：運(yùn)籌學(xué)與控制論指導(dǎo)教師：劉家壯20040325山東大學(xué)博￡學(xué)位論文隨機(jī)時(shí)間依賴網(wǎng)絡(luò)上的最短路問題設(shè)計(jì)的ESP和KESP苒法，連續(xù)時(shí)間網(wǎng)絡(luò)上的最小費(fèi)用流問題的增廣流算法都是啟發(fā)式算法；遺傳算法簡(jiǎn)稱GA，是一種借鑒生物界自然選擇和自然遺傳機(jī)制的高度并行、隨機(jī)、自適應(yīng)的搜索方法，由于遺傳算法的尋優(yōu)過程是從大量的點(diǎn)構(gòu)成的種群開始平行進(jìn)行、逐步優(yōu)化，避免了局部?jī)?yōu)化結(jié)果的

2、產(chǎn)生，并且，遺傳算法不要求函數(shù)滿足可導(dǎo)性質(zhì)，因此遺傳算法常用來解決傳統(tǒng)搜索方法解決不了或很難解決的問題。計(jì)算結(jié)果與最優(yōu)結(jié)果差別一般也很小，但是計(jì)算時(shí)間相對(duì)較長(zhǎng)，而且無法從理論上保證計(jì)算結(jié)果的好壞本文為帶容量限制的帶固定費(fèi)用的最小費(fèi)用流問題設(shè)計(jì)的算法就是遺傳算法。第二章研究隨機(jī)時(shí)間依賴網(wǎng)絡(luò)上的最短路問題在確定性網(wǎng)絡(luò)中，最短路問題已經(jīng)被深入地研究，并被證明有著廣泛的用途在這些問題中，所有邊的長(zhǎng)度都是常數(shù)，目標(biāo)是尋找一條路，使其經(jīng)過的邊的總長(zhǎng)

3、度最小Dijkstra在文獻(xiàn)[25】中給出了一個(gè)時(shí)間復(fù)雜性為O(n2)的多項(xiàng)式算法隨著實(shí)踐的發(fā)展，越來越多的應(yīng)用領(lǐng)域提出了邊上的費(fèi)用是隨機(jī)變量的最短路問題比如在城市交通中，由于堵車、車輛的多少、路上行人及自行車的多少都會(huì)影響到車輛的行駛速度，而這些因素又無法確定，因而汽車需要多長(zhǎng)時(shí)間才能夠通過一條街就無法提前獲知。但是我們通過以往的經(jīng)驗(yàn)或者歷史資料知道通過每一條街所需8寸f日I的概率分布，這樣的問題稱為隨機(jī)網(wǎng)絡(luò)上的最短路問題。根據(jù)邊長(zhǎng)被

4、確定的早晚的不同，隨機(jī)網(wǎng)絡(luò)中的最短路問題大致分為三種情況，1987年【26]GAndreatta便詳細(xì)論述了這三種情況之間的區(qū)別1986年，RandolphWHall【36]首先研究了時(shí)間依賴的隨機(jī)網(wǎng)絡(luò)上的最短路問題，但是沒有給出算法。1998年，EliseDMillerHooks和HaniSMahmassanif37]研究了邊權(quán)是時(shí)間依賴的離散時(shí)間變量的網(wǎng)絡(luò)，給出了最小可能時(shí)間的最優(yōu)路徑算法以及相關(guān)概率的下界，但是當(dāng)路徑由3條以上弧組