網路敏感度分析與參數分析

Network Sensitivity Analysis and Parametric Programming

在運輸的領域中，網路模式常被用來定式實際的運輸問題，其主要的原因在網路模式可容易地定式運輸問題，且可據以發展有效的網路演算法以求解實際問題。在分析系統最佳化下的資源使用及定價分析時，網路敏感度分析尤其重要。一般人常直接以單體法所得的對偶解，估計影子價格，然而由於網路問題常具有退化現象，故由此估計的影子價格可能不是正確解。本研究的目的在利用連續最小成本推擠路徑方式，發展有效的數學解法，測試網路在退化情況下，使用單體法估計影子價格的誤差，並測試參數值連續變化下，真正影子價格的變化情形，期能尋求出一規律性，以幫助實務界正確規劃資源及定價。由本研究測試結果，我們發現網路在最佳化時，的確常發生退化現象，而利用單體法所估計的影子價格，的確存在有相當的誤差。在節點供給值與節線上限值的參數分析中，我們發現增加節點供給值或節線上、下限值，目標值之增量將隨著參數值的增加呈階梯式遞增。

Network models have been commonly used in the field of transportationbecause they are efficient ways to formulate transportation problems. Moreover,special algorithms are frequently developed for solving network problems. Whenanalyzing the optimal uses of resources and pricing, sensitivity analyses areimportant tools. Most often, the dual solutions obtained using the simplexmethod are employed for approximating shadow prices. However, these simplex dualsolutions are not necessarily the correct shadow prices when the optimalsolution is degenerate. This research employed successive least cost flowaugmentation paths to find correct shadow prices and to evaluate simplex shadowprices. To help carriers in pricing and operations, we also performed theparametric programming on node supplies and arc upper bounds. The results showthat the optimal solutions are usually degenerate and the simplex shadow pricesare incorrect. For parametric programming on node supplies and arc upper/lowerbounds, we find as they increase the increments of objective function values allincrease in a ladder way.