(54.236.58.220) 您好!臺灣時間:2021/02/28 08:57
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:楊惠娟
研究生(外文):YANG,HUI-JUAN
論文名稱:找線性規劃中靠近最佳解之可行解的方法
論文名稱(外文):Finding a feasible solution near the optimal one for linear programming
指導教授:曾怜玉曾怜玉引用關係
指導教授(外文):ZENG,LIN-YU
學位類別:碩士
校院名稱:逢甲大學
系所名稱:應用數學研究所
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
論文出版年:1990
畢業學年度:78
語文別:中文
論文頁數:58
中文關鍵詞:線性規劃反覆簡算法靠近最佳解起始解
外文關鍵詞:LP問題(LINEAR PROGRAMMING)(ITERATIVE)(SIMPLEX METHOD)
相關次數:
  • 被引用被引用:0
  • 點閱點閱:216
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
線性規劃 (Linear programming, 簡稱LP) , 應用非常廣泛, 其普遍應用于軍事, 產
業經濟、運輸, 能資源分配、社會問題, ……等一般領域, 其重要性顯而可見。而最
常用來解 LP 問題的方法是簡算法 (Simplex Method) , 自發展出來到現在四十餘年
, 仍為實務上所廣為使用。它是一反覆 (iterative)求解的程序, 每一步驟為些簡單
的計算, 但其最壞的情況下, 反覆之次數是指數形式的。因而我們想提供給簡算法一
較好的起始可行解, 如此可以減少反覆之次數, 執行效率就更高了, 最壞的情況就不
致于發生了。
本研究的目的,就是想找到一較靠近最佳解之可行解, 提供為Simplex Method 的起始
解。研究結果, 我們提出一方法于 O( )時間內可找到 LP 問題的一可行解; 第四
章我們提出一方法, 使用 O(mn)的時間, 由此可行解出發, 找到一較靠近最佳解之可
行解。此較靠近最佳解之可行解, 除了可提供給簡算法較好的起始解外, 還可提供給
其他的演算法一好的起始可行解。
我們的方法, 是隨意取一點 , 若 點是在polytope 上, 即為一可行解; 但若 是在
polytope外, 則拉到 polytope 之面上于 過 p點, 取—2 維平面, 切 Polytope ,
在切出來之 convex polygon 上找出最低點 q; 再過此最低點 q取另—2 維平面切po
lytope, 找出切面之最低點; ……; 如此反覆幾次后, 我們便可以找到一蠻靠近最佳
點之一可行點了。

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔