分式運輸問題之型一與型二敏感度分析

Type I and Type II Sensitivity Analysis of the Fractional Transportation Problem

陳尹儒(Yin-Ju Chen)

指導教授 ： 溫于平 ； 林吉仁

國立清華大學/工學院/工業工程與工程管理學系/碩士(2012年)

摘要

本論文之探討主題為分式運輸問題的敏感度分析。在傳統運輸問題之敏感度分析，以往研究僅討論擾動各成本係數下對於原問題之影響，而在現實環境中，除了考量成本之角度外，也必須同時考量公司之收益，因此分式運輸問題之敏感度分析將更符合實際案例之應用。另一方面，在傳統型一敏感度分析之內容，即為維持在原問題最佳解之基底不改變狀況下，計算該問題之參數擾動範圍的敏感度分析，然而若原問題具有退化之情形，此時將必須使用型二敏感度分析來處理該問題，該分析方法則為在保持目前最佳運輸量不變之情況下，計算該問題之參數擾動範圍的敏感度分析。因此，本論文發展出應用於分式運輸問題敏感度分析之標記演算法，該演算法分為兩部分，分別是處理退化及非退化兩類型之分式運輸問題；此外，分式運輸問題之目標函數為兩線性函數之比率，我們可以分別處理分子係數與分母係數之擾動。我們將發展四種演算法去處理類似問題，本文以一數值範例來說明所提出的演算法，最後再以一實際問題來說明各參數變動對於實際問題之經濟意義。

關鍵字

分式運輸問題 ； 敏感度分析 ； 退化 ； 標記演算法

並列摘要

This thesis concentrates on sensitivity analysis of the fractional transportation problem (FTP). Sensitivity analysis of the conventional transportation problem only discusses about the influence of perturbing cost coefficients. In the real environment, however, the company should take not only the cost point of view but also the profit into consideration. Hence, sensitivity analysis of the FTP is more practical for application of real-world problem. On the other hand, traditional type I sensitivity analysis is to determine the perturbation range in which the current optimal basis remains optimal. Note that degeneracy may occur in FTPs, so we have to use type II sensitivity analysis to deal with degenerate problems rather than type I sensitivity analysis. Type II sensitivity analysis is to determine the perturbation range in which the current optimal basis solutions with positive value still positive. Therefore, this thesis develops the labeling algorithm for solving the sensitivity analysis of the FTP. The proposed algorithms are divided into two parts for dealing with non-degenerate and degenerate FTP respectively. In addition, due to the objective function of the FTP is a ratio of two linear functions, we can deal with the perturbation of numerator coefficients and denominator coefficients respectively. Four algorithms will be developed for solving the related problems. Furthermore, a numerical example is presented to demonstrate the proposed algorithms and illustrate the economic interpretation of perturbation.

並列關鍵字

Fractional transportation problem ； Sensitivity analysis ； Degeneracy ； Labeling algorithm

參考文獻

Gupta, A. & Puri, M. C. (1995). Maximizing pseudoconvex transportation problem: a special type. OR Spektrum, 17, 27-30.

Hadigheh, A. G. & Terlaky, T. (2006). Sensitivity analysis in linear optimization: Invariant support set intervals. European Journal of Operational Research, 169, 1158-1175.

Jain, M., Singh, P. & Saxena P. K. (2009). An optimizing algorithm for multiple objective fractional time transportation problem. International Advance Computing Conference 2009, 0, 266-271.

Joshi, V. D. & Gupta, N. (2010). On a paradox in linear plus linear fractional transportation problem. Matematika, 26(2), 167-178.

Koltai, T. & Terlaky, T. (2000). The difference between managerial and mathematical interpretation of sensitivity analysis results in linear programming. International Journal of Production Economics, 65, 257-274.