跳到主要內容

臺灣博碩士論文加值系統

(44.200.27.215) 您好!臺灣時間:2024/04/13 17:50
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:藍坤銘
研究生(外文):Kuen-Ming Lan
論文名稱:霍普菲爾網路法求解二階線性規劃問題
論文名稱(外文):Hopfield Neural Networks Approaches for Solving Bilevel Linear Programming Problems
指導教授:溫于平溫于平引用關係時序時時序時引用關係
指導教授(外文):Ue-Pyng WenHsu-Shih Shih
學位類別:博士
校院名稱:國立清華大學
系所名稱:工業工程與工程管理學系
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2008
畢業學年度:96
語文別:英文
論文頁數:94
中文關鍵詞:霍普菲爾類神經網路二階線性規劃問題多階規劃問題供應鏈規劃
外文關鍵詞:Hopfield neural networksbilevel linear programming problemsmultilevel programming problemssupply chain planning
相關次數:
  • 被引用被引用:1
  • 點閱點閱:537
  • 評分評分:
  • 下載下載:79
  • 收藏至我的研究室書目清單書目收藏:1
This study exploits Hopfield neural networks (HNN) with branch and bound (B&B) tree and tabu strategy for solving bilevel linear programming and bilevel linear decentralized programming (BLP) problems, which are the special cases of multilevel linear programming (MLP) problems. MLP is a useful model to manage a decentralized planning process of hierarchical organizations in the real world. The model includes both levels having conflicting goals and separated controlled decisions which are difficult to obtain an optimal solution. The newly developed HNN approaches are efficient tools to manipulate the optimization model with parallel processing, and are especially suitable for large size problems. Therefore, two types of hybrid HNN approaches, with a B&B tree or Tabu strategy, are developed to attack BLP problems. In addition, some discussions on parameter settings, transfer functions, learning rates, and etc. are also discussed for ease of using HNN approaches. Finally, some typical examples are demonstrated and an application of supply chain planning is also investigated.
CONTENTS
ABSTRACT i
中文摘要 ii
誌 謝 iii
CONTENTS iv
LIST OF TABLES vi
LIST OF FIGURES vii
Chapter 1 INTRODUCTION 1
1.1 Background and Motivation 1
1.2 The Neural Network (NN) Approach 3
1.3 Overview 4
Chapter 2 BILEVEL LINEAR PROGRAMMING PROBLEMS 6
2.1 BLP Definitions 6
2.2 BLP Optimality and Complexity 8
2.3 BLP Applications and Extend Formulations 11
2.4 Algorithms 13
2.5 Summary 14
Chapter 3 NEURAL NETWORK APPROACHES FOR OPTIMIZATION 17
3.1 General Function and Basic Aspect for HNNs 19
3.2 Classifications of Hopfield Networks 21
3.2.1 Discrete Hopfield Networks 22
3.2.2 Continuous Hopfield Networks 23
3.3 Methods of Hopfield Networks 24
3.3.1 Penalty Function Methods 25
3.3.2 Lagrange Multiplier Related Methods 33
3.3.3 Primal and Dual Methods 39
3.4 Summary 43
Chapter 4 A HYBRID HNN APPROACH WITH BRANCH AND BOUND TREE 46
4.1 Branch and Bound Method in BLP Problem 46
4.2 The Proposed Hybrid HNN Method with B&B Tree 47
4.3 Illustrated Examples 49
4.4 Summary 55
Chapter 5 A HYBRID HNN APPROACH WITH TABU STRATEGY 56
5.1 Tabu Strategy in BLP Problem 56
5.2 The Proposed Hybrid HNN Method with Tabu Strategy 58
5.3 Illustrated Examples 60
5.4 Summary 71
Chapter 6 AN APPLICATION ON SUPPLY CHAIN PLANNING 72
6.1 Introduction 72
6.2 Problem Descriptions 73
6.3 Computational Results 77
6.4 Summary 82
Chapter 7 CONCLUSIONS AND FUTURE SYUDIES 83
7.1 Summary 83
7.2 Future Studies 84
REFERENCES 86
APPENDIX 95
Aboudi R and Jornsten K (1994). “Tabu search for general zero-one integer programs using the pivot and complement heuristic”. Journal of Computing 6: 82-93.
Amouzegar MA and Moshirvaziri K (1999). “Determining optimal pollution control policies: an application of bilevel programming”. European Journal of Operational Research 119:100–120.
Anandalingam G (1988). “A mathematical programming model of decentralized multi-level systems”. Journal of Operational Research Society 39: 1021-1033.
Anandalingam G and Apprey V (1991). “Multilevel programming and conflict resolution”. European Journal of Operational Research 51:233–247.
Anandalingam G and Friesz TL (1992). “Hierarchical Optimization: An Introduction”. Annals of Operations Research 34: 1-11.
Aourid M and Kaminska B (1996). “Minimization of the 0-1 linear programming problem under linear constraints by using neural networks: synthesis and analysis”. IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications 43: 421-425.
Balakrishnan S, Kannan PS, Aravindan C and Subathra P (2003). “On-line emission and economic load dispatch using adaptive Hopfield neural network”. Applied Soft Computing 2: 297-305.
Bard JF and Falk JE (1982). “An explicit solution to the multi-level programming problem”. Computers and Operations Research 9: 77-100.
Bard JF (1983). “Coordination of a multidivisional organization through two levels of management”. OMEGA 11: 457-468.
Bard JF and Moore JT (1990). “A branch and bound algorithm for the bilevel programming problem” SIAM Journal of Scientific and Statistical Computing 11: 281-292.
Bard JF (1991). “Technical note: some properties of the bilevel programming problem”. Journal of Operation Theory and Applications 68: 371-378.
Bard, J. F. (1998). Practical Bilevel Optimization, Kluwer, London.
Bard JF, Plummer JC and Sourie JC (2000). “A bilevel programming approach to determining tax credits for biofuel production”. European Journal of Operational Research 120: 30-46.
Bazaraa MS, Sherali HD and Shetty CM (2006). Nonlinear Programming Theory and Algorithms 3/E, John-Wiley and Sons, New York.
Bazaraa MS, Jarvis JJ and Sherali HD (2005) Linear Programming and Network Flows 3/E, John-Wiley and Sons, New York.
Ben-Ayed O, Boyce D and Blair C (1988). “A general bilevel linear programming formulation of the network design problem”. Transportation Research 22B: 311-318.
Ben-Ayed O and Blair CE (1990). “Computational difficulties of bilevel linear programming”. Operations Research 38: 556-560.
Ben-Ayed O, Blair C, Boyce D and LeBlanc L (1992). “Construction of a real-world bulevel linear programming model of the highway design problem”. Annals of Operations Research 34: 219-254.
Ben-Ayed O (1993). “Bilevel linear programming”. Computers and Operations Research 20: 485-501.
Bialas WF and Karwab MH (1982). “On two-level optimization”. IEEE Transactions on Automatic Control 27: 211-214.
Bialas WF and Karwan MH (1984). “Two-level linear programming”. Management Science 30: 1004-1020.
Blair C (1992). “The computational complexity of multi-level linear problems”. Annals of Operations Research 34: 13-19.
Bose S and Pekny JF (2000). “A model predictive framework for planning and scheduling problem: A case study of consumer goods supply chain”. Computers and Chemical Engineering 24, 329–335.
Breiner A and Avriel M (1999). “Two-stage approach for quantitative policy analysis using bilevel programming”. Journal of Optimization Theory and Applications 100: 15-27.
Brotcorne L, Labbè M, Marcotte P and Savard G (2000). “A bilevel model and solution algorithm for a freight traffic setting problem”. Transportation Science 34: 289-302.
Bruck J and San J (1988). “A Study on Neural Networks”. International Journal of Intelligent Systems 3: 59-75.
Burke LI and Ignizio JP (1992). “Neural network and operations research: an overview”. Computers and Operations Research, 19: 179-189.
Candler W, Fortuny-Amat J and McCarl B (1981). “The potential role of multilevel programming in agricultural economics”. American Journal of Agricultural Economics 63: 521-531.
Candler W and Townsley R (1982). “A linear two-level programming problem” Computers and Operations Research 9: 59-76.
Chong EKP, Hui S and Żak SH (1999). “An analysis of a class of neural networks for solving linear programming problems”. IEEE Transactions on Automatic Control 44: 1995-2006.
Cichocki A and Unbehauen R (1993). Neural Networks for Optimization and Signal Processing, John Wiley, NY.
Clarke P and Westerberg A (1990a). “Bilevel programming for steady-state chemical process design - I. Fundamentals and algorithms”. Computers and Chemical Engineering 14:87–98.
Clarke P and Westerberg A (1990b). “Bilevel programming for steady-state chemical process design – Ⅱ. Performance study for nondegenerate problems”. Computers and Chemical Engineering 14:99-110.
Dempe S (2003). “Annotated Bibliography on Bilevel Programming and Mathematical Programs with Equilibrium Constraints”. Optimization 52: 333-359.
Deng X (1998). “Complexity issues in bilevel linear programming”. In Migdalas, Pardalos PM and Väbrand P, editors, Multilevel Optimization: Algorithms and Applications 149-164. Kluwer Academic Publishers, Dordrecht.
Effati S and Baymain M (2005). “A new nonlinear neural network for solving convex nonlinear programming problems”. Applied Mathematics and Computation 168: 1370-1379.
Effati S and Nazemi AR (2006). “Neural network models and its application for solving linear and quadratic programming problems”. Applied Mathematics and Computation 173: 305-331.
Fortuny-Amat J and McCarl B (1981). “A representation and economic interpretation of a two-level programming problem” Journal of the Operational Research Society 32: 783-792.
Gao J and Liu B (2005). “Fuzzy multilevel programming with a hybrid intelligent algorithm”. Computers and Mathematics with Applications 49: 1539-1548.
Gen M, Ida K, and Kobuchi R (1998). “Neural network technique for fuzzy multiobjective linear programming”. Computers and Industrial Engineering 35: 543-546.
Gendron B and Cranic TG (1994). “Parallel Branch-and-Bound Algorithms: Survey and Synthesis”, Operations Research 42: 1042-1066.
Girard A, Sanso B and Dadjo L (2001). “A tabu search algorithm for access network design”. Annals of Operations Research 106: 229-262.
Gjerdrum J, Shah N and Papageorgiou LG (2001). “Transfer prices for multienterprise supply chain optimization”. Industrial and Engineering Chemistry Research 40, 1650–1660.
Glazos MP, Hui S and Żak SH (1998). “Sliding modes in solving convex programming problems”. SIAM Journal on Control and Optimization 36: 680-697.
Glover F and Laguna M (1997). Tabu Search, Boston: Kluwer Academic Publishers.
Goicoechea A, Hanson DR and Duckstein L (1982). “Multiobjective Decision Analysis with Engineering and Business Application” John-Wiley, NY.
Gupta A and Maranas CD (2000). “A two-stage modeling and solution framework for multisite midterm planning under uncertainty”. Industrial and Engineering Chemistry Research 39: 3799–3813.
Gupta A, Maranas CD and McDonald CM (2000). “Mid-term supply chain planning under demand uncertainty: Customer demand satisfaction and inventory management”. Computers and Chemical Engineering 24: 2613–2621.
Ham FM and Kostanic I (2001). Principles of Neurocomputing for Science and Engineering, McGraw-Hill, NY.
Hansen P, Jaurmard B and Savard G (1992). “New branch-and-bound rules for linear bilevel programming”. SIAM Journal on Scientific and Statistical Computing 13: 1194-1217.
Hasam G-O and Nezam M-A (2006). “An efficient simplified neural network for solving linear and quadratic programming problems”. Applied Mathematics and Computation 175: 452-464.
Hejazi SR, Memariani A, Jahanshahloo G and Sepehri MM (2002). “Linear bilevel programming solution by genetic algorithm”. Computers and Operations Research 29: 1913-1925.
Hillier FS and Lieberman GJ (2000). Introduction to Operations Research, 7th edition, The McGraw-Hill Companies, Inc., New York.
Hobbs B and Nelson S (1992). “A nonlinear bilevel model for analysis of electric utility demand-side planning issues”. Annals of Operations Research 34:255–274.
Hopfield JJ and Tank DW (1985). “Neural computation of decisions in optimization problems”. Biological Cybernetics 52: 141-152.
Huang CC (2007). “Application of particle swarm optimization to solve linear bilevel programming”. Master’s Thesis, Department of Industrial and Engineering Management, National Taipei University of Technology.
Hwang CL and Masud ASM (1979). “Multiple Objectives Decision Making: Methods and Applications”. Springer-Verlag, Berlin.
Hwang CL, Paidy SR, Yoon K and Masud ASM (1980). “Mathematical programming with multiple objectives: a tutorial”. Computers and Operations Research 7: 5-31.
Jeroslow RG (1985). “The polynomial hierarchy and a simple model for competitive analysis”. Mathematical Programming 32: 146-164.
Júdice JJ and Faustino A (1992). “A sequential LCP method for bilevel linear programming”. Annals of Operations Research 34: 89–106.
Kaufmann A and Henry-Labordere A (1977). Integer and Mixed Programming: Theory and Applications, Academic Press, New York.
Kennedy MP and Chua LO (1988). “Neural networks for nonlinear programming”. IEEE Transportation Circuits System 35: 554–562.
Kim T and Shu S (1988). “Toward developing a national transportation planning model: a bilevel programming approach for Korea”. Annals of Regional Science 22: 65-80.
Knox J (1994). “Tabu search performance on the symmetrical travel salesman problem”. Computers and Operations Research 21: 867-876.
Labbè M, Marcotte P and Savard G (1998a). “A bilevel model of taxation and its application to optimal highway pricing”. Management Science 44: 1608-1622.
Labbè M, Marcotte P and Savard G (1998b). “On a class of bilevel programs”. In di Pillo D and Gianessi F, editors, Nonlinear Optimization and Applications 2: 1-24.
Laguna M, Barnes JW and Glover F (1991). “Tabu search method for a single-machine scheduling problem”. Journal of Intelligence Manufacturing 2: 63-74.
Lai YJ (1994). “TOPSIS for MODM”. European Journal of Operational Research 76: 486-500.
Lan KM, Wen UP, Shih HS and Lee ES (2007). “A hybrid neural network approach to bilevel programming problems” Applied Mathematics Letters 20: 880-884.
Leblanc L and Boyce D (1986). “A bilevel programming algorithm for exact solution of the network design problem with user-optimal flows”. Transportation Research 20B: 259-265.
Lee ES and Li RJ (1993). “Fuzzy multiple objective programming and compromise programming with Pareto optimum”. Fuzzy Sets and Systems 53: 275-288.
Lee ES and Shih HS (2001). “Fuzzy and Multi-Level Decision Making: An Interactive Computational Approach” Springer-Verlag, London, UK.
Lee HL, Padmanabhan V and Whang S (1997). “The bullwhip effect in supply-chains”. Sloan Management Review 38: 93–102.
Li SX, Huang Z, Zhu J and Chau PYK (2002). “Cooperative advertising, game theory and manufacturer-retailer supply chains”. Omega, 2002: 347-357.
Lingo (Extended 6.0), Premier Modeling Tool, Lindo Systems Inc., Chicago, IL (2000).
Liu YH and Hart SM (1995). “Solving a bilevel linear program when the inner decision maker controls few variables”. European Journal of Operational Research 81: 644-651.
Løkketangen A and Glover F (1998). “Solving zero-one mixed integer programming problems using tabu search”. European Journal of Operational Research 106: 624-658.
Looi CK (1992). “Neural network methods in combinatorial optimization”. Computers and Operations Research 19: 191-208.
Luh PB, Chang TS and Ning T (1987). “Pricing problems with a continuum of customers as stochastic Stackelberg games”. Journal of Optimization Theory and Applications 55: 119-131.
Maa CY and Shanblatt MA (1992). “Linear and quadratic programming neural network analysis”. IEEE Transaction on Neural Networks 3: 380–394.
Malek A and Tari A (2005). “Primal-dual solution for the linear programming problems using neural networks”. Applied Mathematics and Computation 167: 198-211.
Marcotte P (1988). “A note on a bilevel programming algorithm by LeBlanc and Boyce”. Transportation Research 22B: 233-237.
Marcotte P and Marquis G (1992). “Efficient implementation of heuristic for the continuous network design problem”. Annals of Operations Research 34: 163-176.
MATLAB (Release 11), The MathWorks Inc., Natick, MA, (2000).
Mavrotas G and Diakoulaki D (1998). “A branch and bound algorithm for mixed zero-one multiple objective linear programming”. European Journal of Operational Research 107: 530-541.
McDonald CM and Karimi IA (1997). “Planning and scheduling of parallel semicontinuous processes. Part 1. Production planning”. Industrial and Engineering Chemistry Research 36: 2691–2700.
Migdalas A (1995). “Bulevel programming in traffic planning: models, methods and challenge”. Journal of Global Optimization 8: 209-215.
Önal H, Darmawan DH and Ⅲ SHJ (1995). “A multilevel analysis of agricultural credit distribution in East Java, Indonesia”. Computers and Operations Research 22:227-236.
Perea-Lopez E, Grossmann IE, Ydstie E and Tahmassebi T (2000). “Dynamic modeling and classical control theory for supply chain management”. Computers and Chemical Engineering 24: 1143–1149.
Rajesh J, Kapil G, Hari SK, Jayaraman VK and Kulkarni BD (2003). “A tabu search based approach for solving a class of bilevel programming problems in chemical engineering”. Journal of Heuristic 9: 307-319.
Rodríguez-Vázquez A, Domínguez-Castro R, Rueda A, Huertas JL and Sánchez-Sinencio E (1988). “Switched-capacitor neural networks for linear programming”. Electronics Letters 24: 496–498.
Ronald ED, David AK and Martin W (1971). “A branch-and-bound algorithm for zero-one mixed integer programming problems”. Operations Research 19: 1036-1044.
Sahin HK and Ciric RA (1998). “A dual temperature simulated annealing approach for solving bilevel programming problem” Computers and Chemical Engineering 23: 11-25.
Sakawa M, Nishizaki I and Umura Y (2001). “Interactive fuzzy programming for multi-level linear programming problems with fuzzy parameters”. Fuzzy Sets and Systems 117: 95-111.
Sharda R (1994). “Neural networks for the MS/OR analyst: an application bibliography”. Interfaces 24: 116-130.
Shee DY, Tang T-I and Tzeng GH (2000), “Modeling the supply-demand integration in electronic commerce: a bi-level programming approach”. Journal of Electronic Commerce Research, 1: 79-93.
Sherali HD, Soyster AL and Murphy FH (1983). “Stackelberg-nash-cournot equilibria: characterizations and computations” Operations Research 31: 253-276.
Shih HS (1995), Fuzzy Multi-level Optimization. Ph.D. Dissertation, Department of Industrial and Manufacturing Systems Engineering, Kansas State University, Manhattan, Kansas, USA.
Shih HS, Lai YJ and Lee ES (1996). “Fuzzy approach for multi-level mathematical programming problems”. Computers and Operations Research 23: 73-91.
Shih HS, Wen UP, Lee ES, Lan KM and Hsiao HC (2004). “A Neural Network Approach to Multiobjective and Multilevel Programming Problems”. Computers and Mathematics with Applications 48: 95-108.
Shu S and Kim T (1992). “Solving nonlinear bilevel programming models of the equilibrium network design problem: a comparative review”. Annals of Operations Research 34: 203-218.
Silva IN, Amaral WC and Arruda LV (2005). “Design and analysis of an efficient neural network model for solving nonlinear optimization problems”. International Journal of Systems Science 36: 833-843.
Smith KA (1999). “Neural networks for combinatorial optimization: a review on more than a decade of research” INFORMS Journal on Computing 11: 15-34.
Smith KA and Gupta JND (2000). “Neural networks in business: techniques and applications for the operations research”. Computers and Operations research 27: 1023-1044.
Sun M, Stam A and Steuer RE (1996). “Solving multiple objective programming problems using feed-forward artificial neural networks: the interactive FFANN procedure”. Management Science 42: 835-849.
Sun M, Stam A and Steuer RE (1996). “Interactive multiple objective programming using Techebycheff programs and artificial neural networks”. Computers and Operations Research 27: 601-620.
Tank DW and Hopfield JJ (1986). “Simple neural optimization networks: an A/D converter, signal decision network and a linear programming circuit”. IEEE Transactions on Circuits Systems 33: 533–541.
Tobin R and Friesz T (1986). “Spatial competition facility location models: definition, formulation and solution approach”. Annals of Operations Research 6: 49-74.
Tsiakis P, Shah N and Pantelides CC (2001). “Design of multi-echelon supply chain networks under demand uncertainty”. Industrial and Engineering Chemistry Research 40: 3585–3604.
Tuy H, Migdalas A and Värbrand P (1994). “A quasiconcave minimization method for solving linear two-level programs”. Journal of Global Optimization 4:243–263.
Tuy H and Ghannadan S (1998). “A new branch and bound method for bilevel linear programs”. In Migdalas A, Pardalos P and Värbrand P,editors, Multilevel Optimization: Algorithms and Applications, 231–249, Kluwer Academic Publishers, Dordrecht.
Vicente LN and Calamai PH (1994). “Bilevel and multilevel programming: a bibliography review”. Journal of Global Optimization 5: 291-306.
Vicente LN, Savard G and Júdice J (1994). “Descent approaches for quadratic bilevel programming”. Journal of Optimization Theory and Applications 81: 379-399.
Walsh MP, Flynn ME and O’Malley MJ (1998). “Augmented Hopfield network for mixed integer programming”. IEEE Transactions on Neural Networks 10: 456–458.
Wang S and Lootsma FA (1994). “A hierarchical optimization model of resource allocation”. Optimization 28: 351-365.
Wang J (1996). “A recurrent neural network for solving the shortest path problem”. IEEE Transactions on Circuits and Systems-Ⅰ: Fundamental Theory and Applications 43: 482-486.
Wang J (1997). “Primal and dual assignment networks”. IEEE Transactions on Neural Networks 8: 784-790.
Wang J (1998). “Primal and dual neural networks for shortest-path routing”. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans 28: 864-869.
Watta PB and Hassoun MH (1996). “A coupled gradient network approach for static and temporal mixed-integer optimization”. IEEE Transactions on Neural Networks 7: 578–593.
Wen, UP and Hsu ST (1991). “Linear bi-level programming problems-a review”. Journal of Operations Research Society 42: 125-133.
Wen UP and Huang AD (1996a). “A simple tabu search method to solve the mixed-integer linear bilevel programming problem”. European Journal of Operational Research 88: 563-571.
Wen UP and Huang AD (1996b). “A tabu search approach for solving the linear bilevel programming problem”. Journal of the Chinese Institute of Industrial Engineers 13: 113-119.
Weng WT and Wen UP (2000) “A primal-dual interior point algorithm for solving bilevel programming problems”. Asia-Pacific Journal of Operational Research 17: 213-231.
Wu AI and Tam PKS (1999). “A neural network methodology and strategy of quadratic optimization”. Neural Computing and Applications 8: 283-289.
Wu XY, Xia YS, Li J and Chen WK (1996). “A high-performance neural network for splving linear and quadratic programming problems”. IEEE Transactions on Neural Network 7: 643-651.
Xia Y and Wang J (1995). “Neural network for solving linear programming problem with bound variables”. IEEE Transactions on Neural Networks 6: 515–519.
Xia Y (1997). “Neural network for solving extended linear programming problems”. IEEE Transactions on Neural Networks 8: 803-806.
Yan H and Lam WH (1996). “Optimal road tolls under conditions of queuing and congestion”. Transportation Research 30A: 319-332.
Yang H and Bell MGH (2001). “Transportation bilevel programming problems: Recent methodological advances”. Transportation Research 35B: 1-4.
Zhang S and Constantinides AG (1992). “Lagrange programming neural networks”. IEEE Transactions on Circuits Systems 39: 441–452.
Zhang HC and Huang SH (1995). “Applications of neural networks in manufacturing: a state-of-the-art survey”. International Journal of Production Research 33: 705-728.
Zhou Z, Cheng S and Hua B (2000). “Supply chain optimization of continuous process industries with sustainability considerations”. Computers and Chemical Engineering 24: 1151–1158.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top