有關不確定條件下的最短路徑問題的分析(已修改)
2025-04-06 03:53 本頁面
【正文】 關于不確定條件下的最短路徑問題的研究摘 要：在利用最短路模型解決問題時，由于天氣、運輸條件以及時間段等原因，網(wǎng)絡中弧的權值經(jīng)常很難給出確切的值。對傳統(tǒng)的最短路徑優(yōu)化模型提出了挑戰(zhàn)，也為最短路徑優(yōu)化模型的進一步發(fā)展提供了新的機遇。本文主要就不確定條件下最短路徑問題進行研究，介紹了一種不確定條件下最短路徑問題隨機優(yōu)化模型――有約束的期望最短路徑模型，利用結合隨機模擬方法和遺傳算法的混合智能算法進行求解。通過系統(tǒng)的學習不確定條件下的最短路徑問題的解決方法，開拓了思路，對自己運用系統(tǒng)思維解決自己研究方向的問題有很大的啟發(fā)。關鍵字：網(wǎng)絡優(yōu)化；不確定最短路徑問題；系統(tǒng)思維一、引言最短路徑問題是指在網(wǎng)絡中尋找節(jié)點間具有最小長度(或最小費用)的路徑，具有重要的理論和實際應用意義。一方面，它可以直接應用于許多實際問題，如各種管道的鋪設，線路安排等。另一方面，它也常被利用為解決其他一些優(yōu)化問題的工具，是網(wǎng)絡優(yōu)化中的一個基本而又重要的問題。因此運籌界、工業(yè)界的學者對最短路徑及其變形問題就算法和應用等方面進行了廣泛的研究。然而在很多具體的應用中，我們遇到的信息，存在著客觀的或者人為的不確定性，這種不確定性的表現(xiàn)形式是多種多樣的，例如隨機性、模糊性等。在利用最短路徑模型解決問題時，由于天氣、運輸條件以及時間段等原因，網(wǎng)絡中弧的權值經(jīng)常很難給出確切的估計，這樣只能根據(jù)歷史數(shù)據(jù)獲得其概率分布情況，即這些數(shù)據(jù)是隨機的。但是隨機性只是不確定性的一個方面，對于一些情況，譬如缺少歷史數(shù)據(jù)、或者歷史數(shù)據(jù)不可靠時，這些數(shù)據(jù)只能由專家根據(jù)自己的經(jīng)驗給出主觀的估計，譬如通過該條路徑的時間大概是3小時，流經(jīng)該線路需時40分鐘左右，這樣表征弧上權值的量也因此而模糊起來，此時利用最短路徑模型解決實際問題必須考慮這種不確定性。雖然對于不確定條件下的最短路徑問題，學者們可通過研究動態(tài)隨機網(wǎng)絡中路徑的分布函數(shù)以及期望值來研究網(wǎng)絡問題，給出了分布函數(shù)為某一類型的求解方法，并沒有考慮不同的決策要求，或者是分布函數(shù)為一般情況時的求解方法。至于模糊最短路徑問題，最早由Dubois和Prade[1，2]在1980年首次提出，他們根據(jù)模糊集理論中的最大、最小值算子和Zadeh擴展原理，來求模糊最短路的長度，但由于模糊運算的特點，經(jīng)過多次運算得到的模糊長度有時候并不能和某條路徑對應上。有的學者根據(jù)多準則決策理論求非被支配解路徑集合，但當網(wǎng)絡較大時，該集合就會很大，對于決策者從中選擇滿意的方案就會很困難。因此，在不確定條件下建立模型給出算法，為決策者提供有價值的方案，具有重要的意義。二、問題描述為了對最短
黨政相關相關推薦
鄂ICP備17016276號-1