加性网络DEA模型是一种高度非线性规划问题, 具有较高的求解难度, 使用已有的启发式算法无法获得精确解, 且在大数据环境下耗费计算资源大, 求解速度慢. 为解决这些问题, 本文主要做了两个方面的工作. 首先, 针对该模型求解精度问题, 本文提出了一种二次分式规划问题求解方法, 将模型分解为有限次二次规划求解问题, 并从理论上证明了该方法可以得到该模型的精确解; 随后, 针对大数据环境下模型求解速度慢的问题, 本文对模型约束进行优化, 在可行域不变的情况下缩减约束数量, 减少计算资源消耗, 以提高该模型的求解速度. 数值案例的验证结果显示, 本文所提出的方法可以有效提高加性两阶段DEA模型的计算精度与速度.
Abstract
Additive network DEA model is one kind of highly nonlinear programming problem, which is difficult to be solved directly. The existing heuristic algorithm cannot be applied to obtain the exact solution of the model, and will consumes a lot of computing resources and times in the big data environment. In order to solve these two issues, the presented study mainly does two aspects of work. Firstly, aiming at the issue of solving precision of the model, a solving method of quadratic fractional programming is proposed in this study, which decomposes the model into a finite quadratic programming, and it is proved theoretically that the presented method can be applied to obtain the exact solution of the model. Then, in view of the issue of the slow solving speed in the big data environment, this work optimized the model's constraints by reducing the number of constraints and the consumption of computing resources while the feasible region remained unchanged, so as to improve the solving speed of the model. The numerical case results show that the proposed method can effectively improve both of the calculation accuracy and speed of the additive two-stages DEA model.
关键词
数据包络分析 /
两阶段 /
大数据 /
最优化求解
{{custom_keyword}} /
Key words
data envelopment analysis /
two-stages /
big data /
optimal solution
{{custom_keyword}} /
中图分类号：
C934
{{custom_clc.code}}
({{custom_clc.text}})
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1] Ali A I. Streamlined computation for data envelopment analysis[J]. European Journal of Operational Research, 1993, 64(1): 61-67.
[2] Dulá J H, Helgason R V. A new procedure for identifying the frame of the convex hull of a finite collection of points in multidimensional space[J]. European Journal of Operational Research, 1996, 92(2): 352-367.
[3] Dulá J H, Helgason R V, University S M, et al. An algorithm for identifying the frame of a pointed finite conical hull[J]. ORSA Journal on Computing, 1998, 10(3): 323-330.
[4] Barr R S, Durchholz M L. Parallel and hierarchical decomposition approaches for solving large-scale data envelopment analysis models[J]. Annals of Operations Research, 1997, 73: 339-372.
[5] Zhu Q, Wu J, Song M. Efficiency evaluation based on data envelopment analysis in the big data context[J]. Computers & Operations Research, 2018, 98(1): 291-300.
[6] Dulá J H. A method for data envelopment analysis[J]. INFORMS Journal on Computing, 2011, 23(2): 284-296.
[7] Dulá J H, López F J. DEA with streaming data[J]. Omega, 2013, 41(1): 41-47.
[8] Dulá J H, Thrall R M. A computational framework for accelerating DEA[J]. Journal of Productivity Analysis, 2001, 16(1): 63-78.
[9] Chen W, Cho W. A procedure for large-scale DEA computations[J]. Computers and Operations Research, 2009, 36(6): 1813-1824.
[10] Chen W, Lai S. Determining radial efficiency with a large data set by solving small-size linear programs[J]. Annals of Operations Research, 2017, 250(1): 147-166.
[11] Zhu J. DEA under big data: Data enabled analytics and network data envelopment analysis[J]. Annals of Operations Research, 2022, 309(2): 761-783.
[12] Khezrimotlagh D, Zhu J, Cook W, et al. Data envelopment analysis and big data[J]. European Journal of Operational Research, 2019, 274(3): 1047-1054.
[13] Badiezadeh T, Saen R F, Samavati T. Assessing sustainability of supply chains by double frontier network DEA: A big data approach[J]. Computers & Operations Research, 2018, 98: 284-290.
[14] Chu J F, Wu J, Song M L. An SBM-DEA model with parallel computing design for environmental efficiency evaluation in the big data context: A transportation system application[J]. Annals of Operations Research, 2018, 270(1-2): 105-124.
[15] Song M L, Fisher R, Wang J L, et al. Environmental performance evaluation with big data: Theories and methods[J]. Annals of Operations Research, 2018, 270(1-2): 459-472.
[16] Wu J, Pan Y H, Zhou Z X. Assessing environmental performance with big data: A DEA model with multiple data resources[J]. Computers & Industrial Engineering, 2023, 177: 109041.
[17] Charnes A, Cooper W W. Programming with linear fractional functionals[J]. Naval Research Logistics, 1962, 9(3-4): 181-186.
[18] Zhang L, Chen Y. Equivalent solutions to additive two-stage network data envelopment analysis[J]. European Journal of Operational Research, 2018, 264(3): 1189-1191.
[19] Chen K, Zhu J. Second order cone programming approach to two-stage network data envelopment analysis[J]. European Journal of Operational Research, 2017, 262(1): 231-238.
[20] Chen K, Cook W D, Zhu J. A conic relaxation model for searching for the global optimum of network data envelopment analysis[J]. European Journal of Operational Research, 2020, 280(1): 242-253.
[21] Dinkelbach W. On nonlinear fractional programming[J]. Management Science, 1967, 13(1): 492-498.
[22] Boyd S, Vandenberghe L. Convex Optimization[M]. Cambridge: Cambridge University Press, 2004.
[23] Wei Q, Yan H. A method of transferring polyhedron between the intersection-form and the sum-form[J]. Computers & Mathematics with Applications: An International Journal, 2001, 41(10-11): 1327-1342.
[24] 魏权龄, 汪俊, 闫洪. 无界凸多面体由"和形式"向"交形式"的转化[J]. 系统工程理论与实践, 2004, 24(3): 87-90. Wei Q L, Wang J, Yan H. The method of transferring the unbounded polyhedron of sum-form to its intersection-form[J]. Systems Engineering—Theory & Practice, 2004, 24(3): 87-90.
[25] 杜廷松, 费浦生, 蹇继贵. 非凸二次规划全局极小问题的新型分枝定界算法[J]. 计算机工程与应用, 2008(17): 49-52. Du T S, Fei P S, Jian J G. New branch and bound algorithm for nonconvex quadratic programming global minimization[J]. Computer Engineering and Applications, 2008(17): 49-52.
[26] Vandenbussche D, Nemhauser G L. A branch-and-cut algorithm for nonconvex quadratic programs with box constraints[J]. Mathematical Programming, 2005, 102(3): 559-575.
[27] 王杉林. 非凸二次规划问题的一个全局优化方法[J]. 重庆师范大学学报(自然科学版), 2015, 32(3): 17-22. Wang S L. A global optimization methods for non-convex quadratic programming[J]. Journal of Chongqing Normal University (Natural Science), 2015, 32(3): 17-22.
[28] Ali A I. Streamlined computation for data envelopment analysis[J]. European Journal of Operational Research, 1993, 64(1): 61-67.
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}
基金
国家自然科学基金(72201130, 71971074, 72188101, 72171122)
{{custom_fund}}
PDF(468 KB)
