# 臺灣博碩士論文加值系統

(3.238.204.167) 您好！臺灣時間：2022/08/13 11:00 :::

### 詳目顯示 : Twitter • 被引用:1
• 點閱:167
• 評分:     • 下載:0
• 書目收藏:2
 線性二階規劃（bilevel linear programming）問題是多階規劃問題的特例之一，它是處理分權式決策問題的一種數學模式。在線性二階規劃問題中，雖然高階與低階目標函數都是線性函數，且限制式解集合是凸集合， 然而一般而言，它的理性反應解集合（亦稱為可行解集合）是非凸集合， 因此，線性二階規劃問題是歸類為非線性最佳化問題。 在此論文中，我們以仿射比例內點主演算法（primal affine scaling algorithm）及主對偶（primal-dual）演算法為基礎，建立了求解線性二階規劃問題的內點演算法。我們進而求解隨機產生之線性二階規劃問題，以驗證演算法的正確性與有效性。測試結果顯示，與其它演算法比較，我們所建立之內點演算法非常適合求解較大型的線性二階規劃問題。 另一方面，只要些許的修訂，我們所建立的內點演算法也可以用來求解多目標規劃問題中的有效解集合線性最佳化（linear optimization over the efficient set）問題。經由求解隨機產生之有效解集合線性最佳化問題，結果顯示我們所建立的內點演算法不但正確、有效，而且比其它演算法更適合求解較大型的問題。
 Linear bilevel programming (BLP) problem is a special case of multilevel programming problem, which is a mathematical programming model for decentralized decision problems. In a linear BLP problem, the higher and the lower levels objective functions are both linear functions and the constraints region is a convex set, however, the rational reaction set (or, the feasible set) is generally nonconvex. Hence the linear BLP problem is mathematically classified as a nonlinear optimization problem. In this dissertation, based on primal and primal-dual affine scaling algorithms, we develop interior point algorithms for solving linear BLP problems. We test the accuracy and efficiency of the proposed algorithms by solving randomly generated problems. The computational results show that the interior point method is suitable for solving relatively larger scale linear BLP problems. On the other hand, after modification, the proposed interior point algorithm also provides an effective and accurate approach to solve linear optimization over the efficient set (OES) problems. The computational results also show that the modified algorithm can solve relatively larger scale linear OES problems.
 1 Introduction 1 1.1 Problem Definition . . . . . . . . . . . . . . . . . . . 1 1.2 General Properties and Complexity . . . . . . . . . . . 3 1.3 Applications and Existing Algorithms . . . . . . . . . . 5 1.4 Overview . . . . . . . . . . . . . . . . . . . . . . . . 8 2 The Related Problems 11 2.1 Multiple Objective Linear Programming . . . . . . . . . 11 2.2 Linear Optimization over the Efficient Set. . . . . . . 12 2.3 The Equivalency Between Linear BLP Problem and Linear OES Problem . . . . . . . . . . . . . . . . . . . . . . 16 3 Affine Scaling Algorithms 19 3.1 Primal Affine Scaling Algorithm . . . . . . . . . . . . 19 3.1.1 Ideas of Primal Affine Scaling Algorithm. . . . . . 20 3.1.2 Starting and Terminating the Algorithm. . . . . . . 22 3.1.3 Algorithmic Procedure . . . . . . . . . . . . . . . 24 3.2 Primal-Dual Affine Scaling Algorithm. . . . . . . . . . 25 3.2.1 Ideas of Primal-Dual Affine Scaling Algorithm . . . 26 3.2.2 Algorithmic Procedure . . . . . . . . . . . . . . . 29 4 A Primal Affine Scaling Algorithm for Solving Linear BLP Problems 30 4.1 Characteristics of the Reformulated Problems. . . . . . 30 4.2 Ideas of the Proposed Algorithm . . . . . . . . . . . . 32 4.3 The Proposed Algorithm. . . . . . . . . . . . . . . . . 37 4.4 A Numerical Example . . . . . . . . . . . . . . . . . . 39 4.5 Computational Experience. . . . . . . . . . . . . . . . 43 4.6 Discussion . . . . . . . . . . . . . . . . . . . . . . 46 5 A Primal-Dual Affine Scaling Algorithm for Solving Linear BLP Problems 48 5.1 Ideas of the Proposed Algorithm . . . . . . . . . . . . 48 5.2 The Proposed Algorithm. . . . . . . . . . . . . . . . . 50 5.3 An Illustrative Example . . . . . . . . . . . . . . . . 53 5.4 Computational Experience. . . . . . . . . . . . . . . . 57 5.5 Discussion. . . . . . . . . . . . . . . . . . . . . . . 61 6 A Modified Algorithm for Solving Linear OES Problems 63 6.1 Ideas of the Modified Algorithm . . . . . . . . . . . . 63 6.2 The Modified Algorithm. . . . . . . . . . . . . . . . . 65 6.3 A Numerical Example . . . . . . . . . . . . . . . . . . 68 6.4 Computational Experience. . . . . . . . . . . . . . . . 72 6.5 Discussion. . . . . . . . . . . . . . . . . . . . . . . 75 7 Conclusion 77 7.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . 77 7.2 Future Research . . . . . . . . . . . . . . . . . . . . 78 Bibliography 80 Appendix 89 國圖紙本論文     top 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室   