求解大規模資料包絡分析問題

Abstract

資料包絡分析(data envelopment analysis, DEA)以線性規劃(linear programming, LP)計算求解各受評單位的相對效率(relative efficiency)，一般理論上來說， LP問題的求解是簡單的，然而當問題中的資料量相當大的時候，計算求解的負荷和計算時間將非常可觀。本論文將提出一個演算法使得大規模DEA問題的求解效率能顯著提升，特別的是，本研究提出之演算法能夠將求解DEA問題時之個別LP問題的規模控制在一定範圍內，例如可要求每單一LP問題使用的資料量在300筆以內。因此單一LP問題規模將大幅減小(例如由10,000筆減至300筆)而使計算效率提升，同時也可做為以試用版 (trial version)或免費版軟體(例如AMPL、GAMS)求解任何規模DEA問題的理論基礎。

Data envelopment analysis (DEA) is a method, utilizing linear programming (LP), to compute relative efficiencies of all decision making units (DMUs). Solving LP problems is easy in theory. However, in practice, computational loading cannot be ignored for large-scale data. This thesis proposes an algorithm that significantly improves computational effort for solving large-scale DEA problems. Specifically, the proposed algorithm is able to control the size of individual LP problems, e.g. no more than 300 DMUs are used in every LP problem, for computing relative efficiency. As a result, computational efficiency is improved from LP problem size reduction (e.g. from 10,000 to 300 DMUs). This work can also be the theoretical foundation of using trial version or free software (e.g. AMPL and GAMS) to solve DEA problems in any scale.