臺灣博碩士論文加值系統

最佳解往往是針對某特定問題的模式來說，但模式本身只是問題經過抽象化後的形式，並不是和原來的實際問題完全一樣，且真實問題存在許多無法預知和不確定的因素，所以不能保證確定性模式的最佳解也是真實問題最好的解決方案。因此模式的運用，需要額外的分析工具來提出不同的可行方案，進一步提供決策者判斷和決策的參考。後最佳化分析是得到最佳解後所做的後續分析，敏感度分析則是在後最佳化分析中扮演了重要的角色。另方面，運輸問題是一種具有特殊結構的線性規劃問題，在許多的文獻中受到相當的重視，可應用於與運輸模型相關的不同領域。因此本論文探討運輸問題的敏感度分析，且著重於一次改變一個右手邊參數的敏感度分析。由於運輸問題的特殊結構，也就是平衡條件的限制，我們必須藉由同時擾動原先既有的運輸路徑與虛擬路徑來求得在最佳運送路徑不變之下的可變動範圍。因此，我們修正了輔助擾動的縮減問題應用於運輸問題上，並且發展了兩個以標記演算步驟為基礎的演算方法來求算右手邊參數的敏感度範圍。文中並提出數值範例分別地說明兩種演算方法，其為有效且可行的方式來求算運輸問題中一次改變一個右手邊參數的敏感度分析範圍。

An optimum solution is usually the result of the mathematical model, but what decision makers require are the options in some ranges for them to choose, make decisions and further take actions instead of a definitely exact answer. Accordingly, it is important to perform sensitivity analysis to investigate the effects on the optimum solution. In fact, sensitivity analysis is one of the most important areas in postoptimality analysis. On the other hand, the transportation problem (TP) is an important concern that arises in several contexts and has received much attention in the literature. Therefore, this study investigates the sensitivity analysis of the TP and concentrates on the so-called one-change-at-a-time sensitivity ranges of the right-hand-side elements. Due to the special structure of the TP, i.e., the balanced condition, the sensitivity range is derived by the perturbation between one original shipment and one dummy shipment. Thus, the revised auxiliary perturbed problems are demonstrated to apply on the TP, and we further develop two algorithms based on the Labeling procedure for the sensitivity ranges. The proposed algorithms are divided into two parts for finding the lower bound and the upper bound respectively. Two numerical examples are presented in order to illustrate the two algorithms respectively which are the effective ways for determining the one-change-at-a-time sensitivity range of the right-hand-side elements in the TP.

摘要 i
ABSTRACT ii
誌謝 iii
LIST OF FIGURES v
LIST OF TABLES vi
1. INTRODUCTION 1
1.1 Background 1
1.2 Literature Review 5
1.3 Problem Statement and Definition 9
2. AUXILIARY PERTURBED PROBLEM 13
2.1 Linear Programming Problem 13
2.2 Transportation Problem 15
3. THE PROPOSED LABELING ALGORITHM 22
4. NUMERICAL EXAMPLES 37
4.1 Algorithm A for Determining Sensitivity Range of RHS Elements 37
4.2 Algorithm B for Determining Sensitivity Range of RHS Elements 45
5. CONCLUSION 53
REFERENCES 57

1. Adlakha V. G., H. Arsham, Simplifying teaching the transportation problem, International Journal of Mathematical Education in Science and Technology, 29 (1998) 271-285.
2. Adlakha V. G., H. Arsham, Distribution-routes stability analysis of the transportation problem, Journal of Optimization, 43 (1998) 47-72.
3. Arsham H., A. B. Kahn, Simplex-type algorithm for general transportation problems: An alternative to stepping stone, Journal of Operational Research Society, 40 (1989) 581-590.
4. Arsham H., Postoptimality analysis of the transportation problem, European Journal of Operational Research Society, 43 (1992) 121-139.
5. Badra N. M., Seneitivity analysis of transportation problems, Journal of Applied Science Research, 3 (2007) 668-675.
6. Balinski M. L., R. E. Gomory, A primal method for the assignment and transportation problems, Management Science, 10 (1964) 578-593.
7. Bazaraa M. S., J. J. Jarvis, H. D. Sherali, Linear Programming and Network Flows, 3th ed., 2010, Wiley-Interscience, New York.
8. Dijkstra E. W., A note in two problems in connection with graphs, Numerische Mathematik, 1 (1959) 269-271.
9. Doustdargholi S., A. Derakhshan Asl, V. Abasgholipour, Sensitivity analysis of righthand-side parameter in Transportation Problem, Applied Mathematical Sciences, 3 (2009) 1501-1511.
10. Gal T., Shadow prices and sensitivity analysis in linear programming under degeneracy— A state-of-the art survey, OR Spektrum, 8 (1986) 59-71.
11. Hadigheh A. G., T. Terlaky, Sensitivity analysis in linear optimization: Invariant support set intervals, European Journal of Operational Research Society, 169 (2006) 1158-1175.
12. Hillier F. S., G. J. Lieberman, Introduction to Operations Research, 8th ed., 2005, McGraw-Hill, New York.
13. Koltai T., T. Terlaky, The difference between the managerial and mathematical interpretation of sensitivity analysis results in linear programming, International Journal of Production Economics, 65 (2000) 257-274.
14. Leclerc G., Post-optimal analysis of a degenerate optimal solution to the Hitchcock formulation, Civil Engineering and Environment Systems, 6 (2009) 92-101.
15. Lin C. J., U. P. Wen, Sensitivity analysis of objective function coefficients of the assignment problem, Asia-Pacific Journal of Operation Research, 24 (2007) 203-221.
16. Lin C. J., U. P. Wen, Sensitivity analysis of the optimal assignment problem, European Journal of Operational Research, 149 (2003) 35-46.
17. Lin C. J., U. P. Wen, The labeling algorithm for the fuzzy assignment problem, Fuzzy Set and Systems, 142 (2004) 373-391.
18. Namkoong S., J. H. Rho, J. U. Choi, Development of the tree-based link labeling algorithm for optimal path-finding in urban transportation networks, Mathematical and Computer Modeling, 27 (1998) 51-65.
19. Satty T., S. Gass, Parametric objective function part 1, Journal of the Operational Research Society of America, 2 (1954) 316-319.
20. Sharma R. R. K., K. D. Sharma, A new dual based procedure for the transportation for the transportation problem, European Journal of Operational Research, 122 (2000) 611-624.
21. Wendell R. E., Sensitivity analysis revisited and extended, Decision Sciences, 23 (1992) 1127-1142.
22. Wendell R. E., The tolerance approach to sensitivity analysis in linear programming, Management Science, 31 (1985) 564-578.
23. Ravi N., Wendell R. E., The tolerance approach to sensitivity analysis of matrix coefficients in linear programming: General perturbation, European Journal of Operational Research Society, 36 (1988) 943-950.