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

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

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

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

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