簡易檢索 / 詳目顯示

研究生: 李政霖
Lee, Cheng-Lin
論文名稱: 單形法與對偶單形法的新探討
The Revisit of Primal Simplex Method and Dual Simplex Method
指導教授: 許瑞麟
Sheu, Ruey-Lin
學位類別: 碩士
Master
系所名稱: 理學院 - 數學系應用數學碩博士班
Department of Mathematics
論文出版年: 2003
畢業學年度: 91
語文別: 中文
論文頁數: 55
中文關鍵詞: 單形法對偶單形法
外文關鍵詞: K-K-T condition
相關次數: 點閱:43下載:4
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 在教科書中,單形法 ( Primal Simplex Method ) 與對偶單形法 ( Dual Simplex Method ) 是解決線性規劃問題的兩種最基本也最重要的方法,但是這兩種方法均是作用在原問題 ( primal problem )上。在這一篇論文中,我們嘗試比較「單形法求解對偶問題」和「對偶單形法求解原問題」這兩種情況。其重點在於探討兩種演算法的疊代點是否具有一致性。這裡的「一致性」意謂著,由一種演算法所得到的疊代點,經過某些轉換後,會和另一演算法所得到的疊代點有所對應。而這對立的過程,我們在這篇論文中裡會完整地呈現出來。而我們對疊代點是否具有一致性的結果是肯定的,同時我們也導出「對偶單形法求解原問題」其實和「單形法求解對偶問題」是等價的。

    第一章 簡介 2 第二章 單形法與對偶單形法的疊代過程 4 第一節 單形法 4 第二節 對偶單形法 5 第三章 比較「單形法求解對偶問題」與「對偶單形法求解原問題」兩者之間的關係 8 第一節 對偶問題變成為線性規劃問題的標準型式 8 第二節 找出一組起始點 9 第三節 基本解滿足原問題的可行性 10 第四節 討論疊代過程 12 第一小節 討論K-K-T condition中的可行性 12 第二小節 討論基本變數變換 13 第五節 解釋「對偶單形法求解原問題 」和「單形法求解對偶問題 」兩者的一致性 16 第四章 比較「單形法求解原問題」與「對偶單形法求解對偶問題」兩者之間的關係 21 第一節 找出一組初始解 21 第二節 討論疊代過程 23 第一小節 討論K-K-T condition中的可行性 23 第二小節 討論基本變數變換 25 第三節 解釋「單形法來求解問題 」和「對偶單形法求解問題 兩者的一致性 27 第五章 數值結果 30 總結 49 參考書目 50 附錄一:利用MATLAB寫單形法的程式. 52 附錄二:利用MATLAB寫對偶單形法的程式 54

    [1] 錢頌迪, 作業研究修訂版,清華大學作業研究教材編寫組,儒林出版社, 1992。
    [2] Fang, S. C. and Puthenpura, S., Linear Optimization and Extensions: Theory and Algorithms. AT&T., 1993。
    [3] Murty, K. G., Linear programming. John Wiely & Sons, 1983。
    [4] 李曉玲, Primal與Dual Simplex Method之關係及其在Generalized Linear Multiplicative Programming上的應用, 碩士論文。
    [5] Lenstra, J. K. , Rinnooy Kan, A. H.G., Schrijver, A., History of mathematical programming : a collection of personal reminiscences, CWI, Amsterdam, c1991。
    [6] Luenberger, D. G., Linear and nonlinear programming, Addison-Wesley, Massachusetts, 1984。
    [7] Karloff, H., Linear programming, Birkhauser, Boston, 1991。
    [8] Papadimitriou, C. H., Combinatorial optimization:algorithms and complexity, Prentice Hall, Englewood Cliffs, N.J., 1982。
    [9] Dantzig, G. B., Linear programming, Springer, New York, 1997。
    [10] Hillier, F. S. and Lieberman, G. J., Introduction to operations research, McGraw-Hill, New York, 1995。
    [11] Bazaraa, M. S., Nonlinear programming: theory and algorithms, Wiley, New York, 1993.
    [12] Borgwardt, K. H., The simplex method, a probabilistic analysis, Springer-Verlag, Berlin, New York, 1987.
    [13] Walsh, G. R., An introduction to linear programming, Wiley, Chichester, New York, 1985.
    [14] Thie, Paul R., An introduction to linear programming and game theory, Wiley, New York, 1979.
    [15] Campbell, Hugh G., An introduction to matrices, vectors, and linear programming, Appleton-Century-Crofts, New York, 1965.
    [16] Frazer, J. Ronald, Applied linear programming, Prentice-Hall, Englewood Cliffs, N.J., 1968.
    [17] Bunday, Brian D., Basic linear programming, E. Arnold, London, 1984.
    [18] Dahleh, Munther A. and Diaz-Bobillo, Ignacio J., Control of uncertain systems : a linear programming approach, Prentice Hall, Englewood Cliffs, N.J., 1995.
    [19] Throsby, C. D., Elementary linear programming, Random House, New York, 1970.
    [20] Kolman, Bernard, and Robert E. Beck., Elementary linear programming with applications, Academic Press, San Diego, 1995.
    [21] Luenberger, David G., Introduction to linear and nonlinear programming, Addison-Wesley Pub. Co., Reading, Mass, 1973.
    [22] Strum, Jay E., Introduction to linear programming, Holden-Day, San Francisco, 1972.
    [23] Darst, Richard B., Introduction to linear programming :/applications and extensions, M. Dekker, New York, 1991.
    [24] Campbell, Hugh G., Linear algebra with applications :/including linear programming, Appleton-Century-Crofts, New York, 1971.
    [25] Zionts, Stanley, Linear and integer programming, Prentice-Hall, Englewood Cliffs, N.J., 1974.

    下載圖示 校內:立即公開
    校外:2003-07-31公開
    QR CODE