Obtaining all extreme rays of a special cone using spanning trees in a complete digraph: Application in DEA
提出一种新方法，通过枚举完全有向图中的所有生成树来获取交集形式锥的所有极射线，无需求解数学规划问题，并应用于DEA中成本效率下界的计算。
This paper presents a new method which can be used in two different situations: Firstly, for converting certain polyhedral cones of intersection form to cones of sum form, this method identifies all the extreme rays of a cone of intersection form by enumerating all spanning trees in a complete digraph without solving any mathematical programming problems. Secondly, in the existing data envelopment analysis models, the lower bound of cost efficiency measure can be calculated by using weights restrictions in the form of input cone assurance region. In such cases, all vertices are obtained by enumerating all potential bases. In fact, for determining the lower bound of cost efficiency measure, the vertices of a polyhedral set should be calculated. Because obtaining all vertices by enumerating all potential bases is not actually affordable, in this paper we obtain the vertices by enumerating all spanning trees in a complete digraph. This method has computational advantages over the previous ones. At the end of this paper, two numerical examples are provided to demonstrate the advantage of the proposed method.