基于最小体积覆盖凸体的大规模DEA模型计算方法研究

Most of the current methods addressing the large-scale Data Envelopment Analysis (DEA)’s computational problem are limited in two aspects. First, their major objective is to resolve the case of large-scale decision making units (DMUs) and small-scale input/output indicators, and second, their computational efficiency drops rapidly with the gradually rising of the number of input/output indicators. In view of the deficiencies above, this project takes advantage of the classical two-stage method to propose a “novel two-stage algorithm”, and combines DEA and the strategies of the minimum volume enclosing convex bodies, such as balls, ellipsoids, axis-aligned ellipsoids and simplexes. In the first stage all efficient DMUs are classified not only accurately but also efficiently, and in the second stage the efficiencies of inefficient DMUs are computed with the references of the efficient DMUs. .The core of this algorithm is to resort to a few nonlinear programs and a large number of small-scale linear programs to replace a large number of large-scale linear programs. The superiority of this algorithm suggests that the potential of speeding up the computations and realizing breakthroughs in the computation of the large-scale DEA problem. Moreover, this new algorithm could make DEA a complete system both theoretically and methodologically, promote the computational efficiency of large-scale DEA models, and improve the ability of DEA in its analysis of the big data.

针对当前大规模数据包络分析（DEA）模型计算方法的两点不足：（1）只能用于解决决策单元（DMU）数量很大而指标数量很小的问题；（2）计算效率随着指标数量增加而呈现快速下降的趋势，本课题拟设计“新两阶段”算法以改进大规模DEA模型的计算方法。“新两阶段”算法立足传统两阶段法的优势，引入最小体积覆盖凸体技术，选取球、椭球、轴向椭球和单纯形作为凸体的代表分别与DEA结合进行研究。第一阶段旨在准确、高效地识别所有有效DMU，第二阶段则以有效DMU为参考集，计算出所有非有效DMU效率。.该算法以求解少量的大规模非线性凸规划和大量小规模线性规划来代替求解大量的大规模线性规划，最终提升计算效率，有望实现对大规模DEA模型计算的突破。“新两阶段”算法的提出将有助于完善DEA理论和方法体系，直接提升大规模DEA计算方法的效率，并提升其支撑大数据计算和分析的能力。

在大数据背景下，数据包络分析模型（Data Envelopment Analysis，简称DEA）的应用受到了样本规模的限制。针对当前大规模DEA模型计算方法的两点不足：（1）只能用于解决决策单元（DMU）数量很大而指标数量很小的问题；（2）计算效率随着指标数量增加而呈现快速下降的趋势，本课题基于最小体积覆盖椭球技术设计“新两阶段”算法以提升大规模DEA模型的计算效率。.本课题主要研究成果包括以下四个方面。.1. 提出了计算最小体积覆盖椭球问题的高效算法，该算法具有线性收敛速度，数值效果优于经典算法。该项成果已经在《系统工程理论与实践》杂志上发表。.2. 提出了基于最小体积覆盖椭球技术的大规模DEA模型的求解算法。该算法分为两个阶段，在第一阶段提出一种样本集最优划分策略，可以实现经典Build Hull算法的并行处理；在第二阶段利用敏感性分析技术计算所有决策单元的效率值。.3. 相关理论成果的应用。我们将课题相关理论成果应用于财务风险预警和共享单车布局等问题中。这些成果已在《Resources, Conservation, Recycling》、《Annals of Operations Research》等杂志上发表。.4. 依托本项目资助，我们还进行了与项目研究内容相关但并未在项目申请书中提及的工作，包括：提出整数DEA模型等。这些成果已经在《中国管理科学》、《Technological Forecasting and Social Change》等杂志上发表。