簡易檢索 / 詳目顯示

回結果列表
研究生： 黃明典
Huang, Min-Dien
論文名稱： 以內點潛能推動演算法求解多目標線性規劃問題
An interior potential push algorithm for solving multiobjective linear programming problems
指導教授： 張秀雲
Chang, Shiow-Yun
學位類別： 碩士
Master
系所名稱： 管理學院 - 工業與資訊管理學系
Department of Industrial and Information Management
論文出版年： 2005
畢業學年度： 93
語文別： 英文
論文頁數： 72
外文關鍵詞： Interior-point methods, MOLP, Primal-dual interior MOLP algorithm
相關次數： 點閱：37  下載：0 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • None

    The area of multiobjective linear programming problem (MOLP) has prevailed and attracted a lot of attention for the last thirty years and many approaches or variants were developed to solve these problems. In this thesis, we consider Arbel's algorithm called Primal-Dual Interior Multiple Objective Linear Programming (PDIMOLP) algorithm that generates search directions pointing toward anchoring points. We use Arbel's algorithm as a foundation and make some modifications by adopting fail-safe technique to find an initial efficient point. Moreover, we adopt potential push method into the modified
    algorithm and make some changes in solving nonlinear utility functions that the solution locates at the boundary of the feasible region or inside the feasible region. We make it more effective in solving multiobjective linear programming problems. From the computational results, the proposed modified algorithm performed well to solve the multiobjective linear programming problems.

    TABLE OF CONTENTS ACKNOWLEDGEMENTS : : : : : : : : : : : : : : : i LIST OF TABLES : : : : : : : : : : : : : : : :iii LIST OF FIGURES : : : : : : : : : : : : : : : :iv CHAPTER I. INTRODUCTION . . . . . . . . . . . . . . . . . 1 1.1 Motivation . . . . . . . . . . . . . . . . 2 1.2 Purposes and Organization . . . . . . . . .3 II. LITERATURE REVIEW . . . . . . . . . . . . .5 2.1 Interior-Point Methods and MOLP . . . . . .5 2.2 The Path-following Primal-dual Algorithm . 7 2.3 The Path-following MOLP Primal-dual Algorithm. . . . . . . . . . . . . . . . . . . 12 2.4 Summary . . . . . . . . . . . . . . . . . .21 III. ALGORITHM MODIFICATION AND DEVELOPMENT . .23 3.1 Finding an Initial Efficient Point . . . . 24 3.2 Boundary Behavior . . . . . . . . . . . . .26 3.3 Method to Different Utility Function . . . 31 3.4 Summary of the Modified Algorithm . . . . .35 IV. COMPUTATIONAL RESULTS . . . . . . . . . . .40 4.1 Nonlinear Utility Function . . . . . . . . 40 4.2 The Optimal Solution Inside the Boundary . 53 V. CONCLUSIONS AND FUTURE SUGGESTIONS . . . . .59 REFERENCES . . . . . . . . . . . . . . . . . . 61

    REFERENCES
    1. Abel, A. An interior multiobjective linear programming algorithm. Computers and Operations Research, 20(7), 723-735, 1993a.
    2. Abel, A. A weighted-gradient approach to multiobjective linear programming problems using the analytic hierarchy process. Mathematical and Computer Modeling, 17(4/5), 27-39, 1993b.
    3. Abel, A. Anchoring points and cones of opportunities in interior multiobjective linear programming. Journal of the Operational Research Society, 45(1), 83-96, 1994a.
    4. Abel, A. Using e±cient anchoring points for generating search directions in interior multiobjective linear programming. Journal of the Operational Research Society, 45(3), 330-344, 1994b.
    5. Abel, A. An interior multiple objective primal-dual linear programming algorithm using efficient anchoring points. Journal of the Operational Research Society, 46, 1121-1132, 1995.
    6. Abel, A. An interior multiobjective primal-dual linear programming algorithm based onapproximated gradients and e±cient anchoring points. Computers and Operations Research, 24(4), 353-365, 1997.
    7. Abel, A. and Korhonen, P. Using aspiration levels in an interactive interior multiobjective linear programming algorithm. European Journal of Operational Research,89, 193-201, 1996.
    8. Abel, A. and Oren, S. S. Using approximate gradients in developing an interactive interior primal-dual multiobjective linear programming algorithm. European Journal of Operational Research, 89, 202-211, 1996.
    9. Aghezzaf, B. and Ouaderhman, T. An interactive interior point algorithm for multiobjective linear programming problems. Operations Research Letters, 29, 163-170, 2001.
    10. Cheng, R. W. 1997. An interior algorithm for solving multiobjective linear programming problems. Unpublished master's thesis, Tsing Hua University.
    11. Ecker, J. G. and Hegner, N. S. On computing an initial e±cient extreme point. Journal of the Operational Research Society, 29(10), 1005-1007, 1978.
    12. Ecker, J. G. and Kouada, I. A. Finding e±cient points for linear multiple objective problems. Mathematical programming, 8, 375-377, 1975.
    13. Fang, S. Linear optimization and extensions. Prentice-Hall International Editions, 1993.
    14. Karmarkar, N. A new polynomial-time algorithm for linear programming. Combinatorica, 4(4), 373-395, 1984.
    15. Nash, S. G. and Sofer, A. Linear and nonlinear programming. New York: McGraw-Hill, 1996.
    16. Steuer, R. E. Multiple criteria optimization: theory, computation, and application. New York: Wiley, 1986.
    17. Trafalis, T. B. and Alkahtani, R. M. An interactive analytic trade-o® cutting plane algorithm for multiobjective linear programming. Computers and Industrial Engineering, 37, 649-669, 1999.
    18. Trafalis, T. B., Mishina, T. and Foote, B. L. An interior point multiobjective programming approach for production planning with uncertain information. Computers and Industrial Engineering, 37, 631-648, 1999.
    19. Zeleny, M. Multiple criteria decision making. New York: McGraw-Hill, 1982.

    下載圖示 校內：2008-06-20公開
    校外：2010-06-20公開
    QR CODE