| 研究生: |
李政霖 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 )上。在這一篇論文中,我們嘗試比較「單形法求解對偶問題」和「對偶單形法求解原問題」這兩種情況。其重點在於探討兩種演算法的疊代點是否具有一致性。這裡的「一致性」意謂著,由一種演算法所得到的疊代點,經過某些轉換後,會和另一演算法所得到的疊代點有所對應。而這對立的過程,我們在這篇論文中裡會完整地呈現出來。而我們對疊代點是否具有一致性的結果是肯定的,同時我們也導出「對偶單形法求解原問題」其實和「單形法求解對偶問題」是等價的。
[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.