(3.232.129.123) 您好!臺灣時間:2021/02/26 21:40
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:陳本立
研究生(外文):CHEN,BEN-LI
論文名稱:零壹整數規劃問題新解法之研究:位置搜尋法之建立輿評估
論文名稱(外文):A location search algorithm of 0-1 integer programming problems
指導教授:韓復華韓復華引用關係楊維邦楊維邦引用關係
指導教授(外文):HAN,FU-HUAYANG,WEI-BANG
學位類別:碩士
校院名稱:國立交通大學
系所名稱:資訊科學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:1990
畢業學年度:78
語文別:中文
論文頁數:101
中文關鍵詞:位置搜尋法建立評估零壹整數規劃問題雙元整數規劃問題分枝定限
外文關鍵詞:BALAS演算法(LOCATION-SEARCH-ALGORITHM)(BRANCH-AND-BOUND)
相關次數:
  • 被引用被引用:2
  • 點閱點閱:174
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
本研究係針對雙元整數規劃問題,提出一種新的演算方法。雙元整數規劃問題是一個
具有特殊形式的線性規劃問題,它限制所有的雙數值只能是0或1。此類問題之應用極
廣,舉凡集合涵蓋(Set Covering)或集合分割(Set Partitioning)或其他路網(Netwo
rk)、路徑(Routing)等類型的問題皆屬之。另外整數規劃問題亦可依一定的方式轉換
成雙元整數規劃問題,因此求解雙元整數規劃問題之演算法一直是重要的研究課題。
本研究提出之「位置搜尋法」(Location Search Algorithm) 係採用分技定限(Branc
h and Bound)的架構去設計一個新的求解雙元整數規劃問題的演算法,但捨棄傳統BA
LAS 演算法以變數值為0或1作分枝依據的方式, 而改以零壹數值出現的位置作為設計
新演算法的依據。其在搜尋過程中,考慮限制式條件約束可行解零或壹出現位置的分
枝範圍,然後依縱向搜尋(Depth First Search)之原則巡迴(Traverse)所有的分枝。
在巡迴的過程中運用分枝定限的架構,如此可避免巡迴所有的可能組合。
位置搜尋法和BALAS 演算法皆為加法性演算法,且在架構上十分相似,因此本研究用
BALAS 演算法作為新演算法的比較評估依據,以進一步膫解新演算法之特性。
依據840 個演算例題及9 個實例的測試結果顯示;當係數矩陣中之元素皆為正時或係
數矩陣之密度大時,位置搜尋法之解題效率優于BALAS 演算法。又根據結果分析顯示
:位置搜尋法第一次搜尋所得之可行解與最佳解比較,平均誤差在9%以內;位置搜尋
法平均只搜尋二至三個可行解便可得最佳解,因此位置搜尋法亦可作為求近似解之啟
發式方法架構。
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔