- 學位論文
大規模線性規劃用於變數上限約束問題
The Large Scale Linear Programming Problems with Variable Upper Bound
若您是本文的作者，可授權文章由華藝線上圖書館中協助推廣。
摘要
變數上限值約束的線性規劃模式。利用變數上限值問題其係數矩陣具有 構，因此我們以Dantzig-Wolfe分解演算法為主幹，使得空間儲存 翩A並 發展了快速求解子問題的秩樞軸法則，以便能提升求解原問題的速 olfe 方法已有現成的軟體，故只需將其略加修改便能使用，不須重 畯戔擘s這 個快速求解子問題的法則至更一般的變數上限約束。影價向量 W劃後的分 析是非常重要的，故透過Karush-Kuhn-Tucker條件我們便可快 B理捨入誤 差累積的問題與上述的需求，我們提出了一個包含估計最佳解近似值的三 階段演算法。我們於文末以一數值範例來佐證我們的言論。
並列摘要
This Research focuses on solving the large scale linear programming problems with variable upper bound. Such linear programming problems have special block structures in their coefficient matrices so that the famous Dantzig-Wolfe decomposition method can be applied to solve. In our research, we shall propose an efficient way-rank pivot rules, which, we believe, is new, for Dantzig-Wolfe decomposition method to solve subproblems efficiently. We also demonstrate how to obtain the optimal shadow prices from the Karush-Kuhn-Tucker Conditions. On the other hand, together with Dantzig-Wolfe decomposition method, we propose a three-phase algorithm to avoid the accumulation of round-off errors during the iterative processes. Examples will be employed to show the complete process of solving such problems.
延伸閱讀
- Yao, G. C. (2015). 利用線性規劃針對非線性多項式函數在隨機電路上之合成的研究 [master's thesis, National Tsing Hua University]. Airiti Library. https://www.airitilibrary.com/Article/Detail?DocID=U0016-1802201617063311
- Wu, K. Y. (2006). 參數化探索單形型法求解線性限制最佳化問題. 工業工程學刊, 23(3), 215-221. https://doi.org/10.29977/JCIIE.200605.0005
- 林威成（2015）。具設限反應之多變量線性混合效應模型及其應用〔碩士論文，逢甲大學〕。華藝線上圖書館。https://doi.org/10.6341/fcu.M0216378
- Wang, J. R., & Yang, Y. L. (2010). Optimal Control of Linear Impulsive Antiperiodic Boundary Value Problem on Infinite Dimensional Spaces. Discrete Dynamics in Nature and Society, 2010(), 1141-1156. https://doi.org/10.1155/2010/673013
- ZASLAVSKI, A. J. (1998). EXISTENCE AND UNIFORM BOUNDEDNESS OF OPTIMAL SOLUTIONS OF VARIATIONAL PROBLEMS. Abstract and Applied Analysis, 1998(), 265-292. https://doi.org/10.1155/S1085337598000566