簡易檢索 / 詳目顯示
| 研究生： |
莊照明 |
|---|---|
| 論文名稱： |
背包問題之研究 |
| 指導教授： | 姚興台 |
| 學位類別： |
碩士
Master |
| 系所名稱： |
商學院 - 統計學系 Department of Statistics |
| 論文出版年： | 1984 |
| 畢業學年度： | 72 |
| 語文別： | 中文 |
| 論文頁數： | 101 |
| 相關次數： | 點閱：295 下載：0 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
第一章 緒論1
第一節 前言1
第二節 研究動機與目的1
第三節 內容結構2
第二章 背包問題5
第一節 簡介5
第二節 求解法則6
第三節 週期性質16
第四節 將整數規劃問題化為背包問題20
第五節 背包問題在裁紙問題上之應用24
第三章 0 - 1背包問題31
第一節 縮減法則32
第二節 分支定界法36
第三節 將0 - 1背包問題應用到一般化的分派問題43
第四節 電腦實例47
第四節 摺疊的0 - 1背包問題57
第一節 簡介57
第二節 一些定理59
第三節 求解決則65
第四節 實例68
第五章 連續的摺疊背包問題71
第一節 簡介71
第二節 一些性質72
第三節 分解定理78
第四節 子問題及其一些性質80
第五節 求解法則89
第六節 實例92
第六章 結論與建議95
註解97
參考資料99
1. Balas. E. “An additive algorithm for solving linear programs with zero-one variables”, Oper. Res. 13 ( 1965 ) : 517-546.
2. Cabot, V. A. “ An enumeration algorithm for knapsack problems ” , Oper. Res. 18 ( 1970 ) : 306-311.
3. Cooper. L. & D. I. Steinberg, Methods and Applications of Linear Programming, Philadelphia, London, Toronto, (1974 ).
4. Dantzig, G. B. “Discrete variable extremum problems ” , Oper. Res. 5 ( 1957 ) 266-277.
5. Denardo, E. V. Dynamic Programming : Models and Applications, Prentice-Hall, Englewood Cliffs, New Jersey, ( 1982 ).
6. Garfinkel, R. & G. Nemhauser, Integer Programming , J. Wiley, New York, ( 1970 ).
7. Gilmore. P. C. & R. E. Gomory, “ A linear programming approach to the cutting stock problem ” , Oper. Res. 11 ( 1961 ) : 849-859.
8. Greenberg, H. & R. L. Hegerich, “ A branch search algorithm for the knapsack problem ” , Management Sci. 16 ( 1971 ) : 327-332.
9. Hu. T. C. Integer Programming and Network Flows, Addison-Wesley, Reading, Massachusetts, ( 1969 ).
10. Ingargiola, G. P. & J. F. Korsh, “ Reduction algorithm for zero-one single knapsack problems” , Management Sci. 20 ( 1973 ) 460-463.
11. Kolesar, P. J. “ A branch and bonnd algorithm for the knapsack problem ”, Management Sci. 22 ( 1967 ) : 723-735.
12. Posner, M. E. “The decomposition of nonlinear problems”, Mathematical Programming. 15 ( 1978 ) : 360-362.
13. Posner. M. E. “The continuous collapsing knapsack problem” , Mathematical Programming 26 ( 1983 ) : 76-86.
14. Posner, M. E. & M. Guignard, “The 0-1 collapsing knapsack problem” , Mathematical Programming 15 ( 1978 ) : 155- 161.
15. Rochafellar, R. T. , Convex Analysis, Princeton U. Press, N. J. ( 1969 ).
16. Ross, C. T. “ A branch and bound algorithm for the generalized assignment problem ”, Mathematical Programming 8 ( 1975 ) : 91-103.
17. Taha, H. A., Integer Programming : Theory, Applications, and Computations, University of Arkansas Fayetteville. Arkansas, ( 1975 ).
(限達賢圖書館四樓資訊教室A單機使用)