A polynomial-time algorithm to determine BCC efficient frontier without solving a mathematical programming problem

Document Type : Original Article

Authors

1 Department of Mathematics, Central Tehran Branch, Islamic Azad University, Tehran, Iran

2 Faculty of Management Sciences, Central Tehran Branch, Islamic Azad University, Tehran, Iran

Abstract

In this paper, we restrict our attention to the efficient frontier of the BCC model, where the BCC model is a well-known basic model in Data Envelopment Analysis (DEA). We here assume that each Decision Making Unit (DMU) has one input and one output. In order to obtain BCC efficient frontier, the paper proposes a polynomial-time algorithm of complexity bonded by  to produce well-behaved affine functions. The produced functions are then used to determine a point-wise minimum of a finite number of affine functions. It will be shown that by finding this function, we in fact also determine the efficient frontier of the BCC model. The main advantage of this approach is ability to achieve the efficient frontier, without solving a mathematical programming problem. Also, all of the Pareto efficient DMUs, as BCC-efficient DMUs, can be easily obtained using the proposed algorithm. A numerical example is presented to explain the use and effectiveness of the proposed algorithm.

Keywords


Amirteimoori, A., & Kordrostami, S. (2012). Generating strong defining hyperplanes of the production possibility set in data envelopment analysis. Applied Mathematics Letters, 25(3), 605-609.
Banker, R. D., Charnes, A., & Cooper, W. W. (1984). Some models for estimating technical and scale inefficiencies in data envelopment analysis. Management science, 30(9), 1078-1092.
Charnes, A., Cooper, W. W., & Rhodes, E. (1978). Measuring the efficiency of decision making units. European journal of operational research, 2(6), 429-444.
Cooper, W. W., Seiford, L. M., & Tone, K. (2006). Introduction to Data Envelopment Analysis, Applications References and DEA-Solver Software. Kluwer Academic Publishers.
Lotfi, F. H., Jahanshahloo, G. R., Mozaffari, M. R., & Gerami, J. (2011). Finding DEA-efficient hyperplanes using MOLP efficient faces. Journal of Computational and Applied Mathematics, 235(5), 1227-1231.
Jahanshahloo, G. R., Lotfi, F. H., & Zohrehbandian, M. (2005). Finding the piecewise linear frontier production function in data envelopment analysis. Applied Mathematics and Computation, 163(1), 483-488.
Jahanshahloo, G. R., Lotfi, F. H., Rezai, H. Z., & Balf, F. R. (2007). Finding strong defining hyperplanes of production possibility set. European Journal of Operational Research, 177(1), 42-54. G.R.
Jahanshahloo, G. R., Shirzadi, A., & Mirdehghan, S. M. (2009). Finding strong defining hyperplanes of PPS using multiplier form. European Journal of Operational Research, 194(3), 933-938. G.R.
Korhonen, P. (1997). Searching the efficient frontier in data envelopment analysis. IIASA. IR-97-79. P.
Murty, K. G. Linear programming. john Wily 1983.
Yu, G., Wei, Q., Brockett, P., & Zhou, L. (1996). Construction of all DEA efficient surfaces of the production possibility set under the generalized data envelopment analysis model. European Journal of Operational Research, 95(3), 491-510.