Math Meth Oper Res (2004) 60:15–28 DOI 10.1007/s001860300338
On regular and parametric data envelopment analysis* L. Neralic´# , O. Steinz #
Faculty of Economics, University of Zagreb, 10000 Zagreb, Croatia Department of Mathematics – C, Aachen University, 52056 Aachen, Germany, (e-mail:
[email protected]) z
Manuscript received: January 2003/Final version received: December 2003
Abstract. We give a generic regularity condition under which each weakly efficient decision making unit in the CCR model of data envelopment analysis is also CCR-efficient. Then we interpret the problem of finding maximal parameters which preserve efficiency of CCR-efficient DMUs under directional perturbations as a general semi-infinite optimization problem and use a recently suggested numerical method for this problem class to calculate maximal directionally efficient DMUs. As a practical example we investigate the efficiency of Croatian banks under additive perturbations. Key words: Semi-infinite programming, Bilevel optimization, Constraint qualification, Multi-objective programming, Production planning AMS subject classification: 90C31, 90C34, 90C29, 90B30. 1 Introduction The CCR ratio model for data envelopment analysis was proposed by Charnes, Cooper, and Rhodes in [4] in order to determine relative efficiencies for a finite number of decision-making units (DMUs). Each DMU processes a given set of inputs into a given set of outputs, where prices of inputs and outputs are assumed to be unknown. The relative efficiency of a given DMU is defined via a multi-objective programming problem that determines how well the DMU accomplishes the task of processing little
This research was partly supported by the MZT grant 0067010 of the Republic of Croatia This author was supported by the German Academic Exchange Service (DAAD) and by the Faculty of Economics at the University of Zagreb. z
16
L. Neralic´, O. Stein
amounts of inputs into large amounts of outputs. For an introduction to data envelopment analysis we refer to [3] and [10]. Along with the ‘invariant multiplicative model’ ([5]) and the ‘additive model’ ([2]), the CCR ratio model is one approach to reformulate this multicriteria problem as a standard finite optimization problem. In [6], where a duality theory and the connection to Pareto-Koopmans efficiency are elaborated, the CCR ratio model is extended to the case of infinitely many DMUs, leading to the reformulation of the multi-objective problem as a standard semi-infinite problem. In [14] this approach is further pursued, and a numerical method is presented to find a DMU of maximal efficiency. Semi-infinite optimization also plays an important role when data perturbation of finitely many DMUs are investigated, as we shall show in the present article. The literature on parametric data envelopment analysis is vast. A major task is the determination of all parametric changes of outputs and inputs of DMUs so that one or all efficient or inefficient DMUs stay efficient or inefficient, respectively. For the case of parametric changes of one efficient DMU in the additive model a subset of such efficiency preserving parameters is given in [7], for changes of all DMUs and efficiency and inefficiency preservation of all DMUs an analogous investigation is carried out in [19]. For the CCR model sufficient conditions for efficiency preservation of one DMU under perturbation of its inputs and outputs are given in [8], whereas the same question for simultaneous perturbations of all DMUs is treated in [18]. For overviews about other approaches to sensitivity analysis in data envelopment analysis we refer to [9] and to [10, Chapter 9]. As we shall show in this article, the set of parameters which preserve efficiency can be interpreted as the feasible set of a so-called general semiinfinite optimization problem. Theory and methods for this problem class are elaborated in [20]. The analysis and numerical treatment of the semiinfinite formulation of parametric data envelopment analysis is facilitated when one does not have to distinguish between weak efficiency and CCRefficiency of a decision making unit. In fact, we show that each weakly efficient DMU is also CCR-efficient if the considered DMUs are in general position. The article is organized as follows. In Section 2 we introduce some basic notation concerning the CCR ratio model and its reformulations in multiplier and envelopment form, as well as the definitions of weak and CCRefficiency. Section 3 gives equivalent reformulations of the multiplier and envelopment models in a form which is symmetric in outputs and inputs. These formulations are not only better suited to understand the subsequent regularity condition, but they also lead to better numerical performance in our tests and they may be of interest for other investigations of the CCR model. A regularity condition for data envelopment analysis is introduced in Section 4. We show why problems that satisfy this regularity condition are actually in general position, and that each of their weakly efficient DMUs is also CCR-efficient. In Section 5 we derive the general semi-infinite reformulation of parametric data envelopment analysis. Our numerical examples in Section 6 include an investigation of the efficiency of Croatian commercial banks under simultaneous additive perturbations of inputs and outputs.
On regular and parametric DEA
17
2 Basic notation In the CCR ratio model of data envelopment analysis, the value of the following optimization problem is interpreted as the relative efficiency of a decision-making unit DMU0 : s X
FP0 : max u;v
r¼1 m X
ur yr0 vi xi0
i¼1 s P
ur yrj r¼1 s:t: X 1; m vi xij
j ¼ 1; :::; n;
u; v 0
i¼1
where n2N:
number of DMUs
m2N: s2N:
number of inputs number of outputs
xij > 0 :
amount of input i for DMU j; 1 i m; 1 j n
yrj > 0 :
amount of output r for DMU j; 1 r s; 1 j n
and u 2 Rs , v 2 Rm . Note that DMU0 is one of the decision making units 1 to n, so that the objective function of FP0 is bounded from above by one. Upon identification of DMU j with the vector of its outputs and (negative) inputs, Yj Pj ¼ , FP0 can equivalently be written as (for a proof cf. e.g. [10]) Xj LP0 : max u> Y0 u;v
s:t:
v> X0 ¼1
u> Yj v> Xj 0;
j ¼ 1; :::; n;
u; v 0 : u For a more compact notation we introduce the vector w ¼ 2 Rsþm and v the matrices X ¼ ðX1 ; :::; Xn Þ; Y ¼ ðY1 ; :::; Yn Þ; P ¼ ðP1 ; :::; Pn Þ as well as Y I 0 A¼ ¼ ðP j IÞ; X 0 I where I and 0 in the definition of A denote identity and zero matrices of appropriate dimensions, respectively. With this notation LP0 takes the form
L. Neralic´, O. Stein
18
LP0 : max w> w
Y0 0
s:t:
w>
0 X0
¼ 1;
w> A 0 :
It is not hard to see that the linear programming dual of LP0 is given by 0 1 k @ sþ A þ h 0 ¼ Y0 ; k; sþ ; s 0 ; DLP0 : min h s:t: A X0 0 k;sþ ;s ;h s where k 2 Rn , sþ 2 Rs , s 2 Rm , and h 2 R. We note that LP0 is called the ‘multiplier model’, whereas DLP0 is referred to as the ‘envelopment model’. Efficiency of DMU0 can either be defined in terms of the multiplier or the envelopment model. Following [10] we start with the envelopment model. Definition 2.1. (i) DMU0 is called weakly efficient if the optimal value of DLP0 equals 1. (ii) DMU0 is called CCR-efficient if it is weakly efficient, and if all solution points of DLP0 possess vanishing slack variables sþ and s . (iii) DMU0 is called inefficient if it is not weakly efficient. We note that weak efficiency is also known as radial, technical or Farrell efficiency, whereas CCR-efficiency is also called Pareto-Koopmans efficiency. The relation of these efficiency notions with the corresponding notions in multiobjective (linear) programming has been studied by several authors. The equivalence between CCR-efficiency and nondominated solutions of a corresponding multiobjective program is shown in [22], whereas the connections between weak efficiency concepts are studied in, e.g., [6] and [16]. Example 2.2. Consider the four DMUs with two inputs and one (normalized) output from Table 1. The input data Xj ; j ¼ 1; :::; 4 are depicted in Figure 1. Straightforward calculations show that DMU1 and DMU2 are CCR-efficient, DMU3 is inefficient, and DMU4 is weakly efficient, but not CCR-efficient. An alternative characterization of the efficiency notions is possible in terms of the multiplier model. Theorem 2.3. (i) DMU0 is weakly efficient if and only if the optimal value of LP0 is 1. (ii) DMU0 is CCR-efficient if and only if it is weakly efficient, and if there exists a positive solution w? > 0 of LP0
Table 1. Outputs and inputs for Example 2.2 j
1
2
3
4
Yj
1
1
1
1
Xj
1 4
3 1
4 2
5 1
On regular and parametric DEA
19
X1 X3 X2
X4 Fig. 1. Data points for Example 2.2
Proof. Part (i) follows immediately form the strong duality theorem of linear programming, and part (ii) is due to the strong complementarity theorem. For details see [10]. h 3 Symmetric models The problems LP0 and DLP0 which are used to determine the efficiency properties of DMU0 clearly are not symmetric in the inputs X0 and outputs Y0 . However, our subsequent results about a regularity condition are more transparent when LP0 and DLP0 are first replaced by the following symmetric models. We call SLP0 : max w> P0 w
s.t.
w> e ¼ 1;
w> A 0
the symmetric multiplier model, and its dual 0 1 k @ sþ A þ he ¼ P0 ; k; sþ ; s 0 SDLP0 : min h s.t. A k;sþ ;s ;h s the symmetric envelopment model. Here e denotes the all-one vector of appropriate dimension. Let k0 be the component of the vector k corresponding to the column P0 in P . Setting k0 ¼ 1 and all remaining variables of SDLP0 to zero yields a feasible point, and the optimal value of SDLP0 does certainly not exceed zero. Furthermore, the constraints X k s þ he ¼ X0 ; k; s 0 together with X 0 imply he X0 , so that h is bounded from below by mini¼1;:::;m xi0 on the feasible set of SDLP0 . Consequently both SLP0 and DSLP0 are solvable, and their optimal values coincide. Also note that the feasible set of SLP0 is a subset of the standard simplex in Rsþm as each feasible point satisfies w 0 and w> e ¼ 1. Proposition 3.1. (i) DMU0 is weakly efficient if and only if the optimal value of SLP0 is 0. (ii) DMU0 is CCR-efficient if and only if it is weakly efficient, and if there exists a positive solution w? > 0 of SLP0 . Proof. By Theorem 2.3(i) DMU0 is weakly efficient if and only if the optimal value of LP0 is 1, i.e. if and only if the set 0 sþm > Y0 > W1 ¼ f w 2 R j w ¼ 1; w ¼ 1; w> A 0 g X0 0
L. Neralic´, O. Stein
20
is non-empty. On the other hand, the optimal value of SLP0 vanishes if and only if the set Y 0 W2 ¼ f w 2 Rsþm j w> 0 w> ¼ 0; w> e ¼ 1; w> A 0 g X0 0 is non-empty. Let W1 be non-void. A chosen point w 2 W1 has to satisfy w 0 and w 6¼ 0, so that w> e > 0. Then the point ðw> eÞ1 w lies in W2 . Now let W2 be non-void. Since a chosen point w> ¼ ðu> ; v> Þ 2 W2 has to be non-zero, at least one of the vectors u; v is non-zero. The positivity of Y0 and X0 hence implies that at least one of the terms u> Y0 and v> X0 is positive. Since they are equal, both of them are positive with a :¼ u> Y0 ¼ v> X0 > 0. The point a1 w lies in W1 . This shows that W1 and W2 are either both empty or both nonempty and, thus, part (i) of the assertion. The same arguments show that W1 contains a point w > 0 if and only if W2 contains such a point, which proves part (ii). h Analogous efficiency characterizations are of course possible in terms of the symmetric envelopment model SDLP0 : Corollary 3.2. (i) DMU0 is weakly efficient if and only if the optimal value of SDLP0 is 0. (ii) DMU0 is CCR-efficient if and only if it is weakly efficient, and if all solution points of SDLP0 possess vanishing slack variables sþ and s . 4 A regularity condition As noted before, DMU4 from Example 2.2 is weakly efficient but not CCRefficient. Now consider a small perturbation of the inputs of DMU4 in the form 5 X4 ðeÞ ¼ ; 1þe leading to the perturbed DMU4 ðeÞ. It is not hard to see that for e > 0 the DMU4 ðeÞ is inefficient, whereas for e < 0 it is CCR-efficient. This means that the efficiency type of DMU4 ð0Þ is not stable. The example suggests that stability is more typical than instability. In fact, if the data which define the DMUs are in ‘general position’, each weakly efficient DMU will also be CCRefficient. Definition 4.1. DMU1 ..., DMUn are said to be in general position if the following regularity condition (RC) holds: each ðs þ mÞ ðs þ mÞ submatrix of the ðs þ mÞ ðn þ s þ mÞ)matrix Y I 0 A ¼ X 0 I is non-singular. In Example 2.2 we have s þ m ¼ 3, n ¼ 4, and the matrix
On regular and parametric DEA
0
1 A ¼ @ 1 4
1 3 1
1 4 2
21
1 5 1
1 0 0 1 0 0
1 0 0 A: 1
Since the second, fourth, and sixth column of A form a singular matrix, the DMUs of Example 2.2 are not in general position. Theorem 4.2. Let DMU1 , ..., DMUn be in general position. Then a DMU0 is weakly efficient if and only if it is CCR-efficient. Proof. Clearly a CCR-efficient DMU0 is also weakly efficient. Now let DMU0 be weakly efficient. Then by Proposition 3.1(i) the set W2 ¼ f w 2 Rsþm j w> P0 ¼ 0; w> e ¼ 1; w> A 0 g 2 W2 . Note that the first equality is non-empty, i.e. there exists a point w constraint in W2 coincides with one of the inequality constraints. Hence, with the matrix A0 which results from A by deletion of the column P0 , the nonempty set W2 coincides with W3 ¼ f w 2 Rsþm j w> P0 ¼ 0; w> e ¼ 1; w> A0 0 g By Proposition 3.1(ii) it suffices to show that W3 does not only contain the but also a point w? > 0. point w denote the matrix which is formed by the columns of A0 which Let A00 ðwÞ i.e. w > A00 ðwÞ ¼ 0. correspond to the inequalities w> A0 0 that are active at w, 0 has at least s þ m 1 columns. Then the vector P0 Assume that A0 ðwÞ together with the columns of A00 ðwÞ can form at least one ðs þ mÞ ðs þ mÞsubmatrix of A. By the regularity condition the corre ¼ 0 only possess the trivial solution sponding equalities w> P0 ¼ 0; w> A00 ðwÞ which contradicts the remaining restriction w> e ¼ 1 in W3 . Consequently at most s þ m 2 inequality constraints are active at w. Let us now consider the equation z> ð P0
A00 ðwÞ
e Þ ¼ ð0; e> ; 0Þ :
ð1Þ
Assume that the columns of the system matrix in (1) are linearly dependent. First note that the system matrix can possess at most s þ m columns. By the regularity condition linearly dependent columns are thus only possible if e is contained in the span of the remaining columns, i.e. there is a vector f such that e ¼ ðP0
f: A00 ðwÞÞ
ð2Þ >
from the left yields a contradiction, so that the Multiplication of (2) with w system matrix of (1) has linearly independent columns. As a consequence, (1) possesses a solution z. þ tz with a non-negative scalar t. Then we have wðtÞ> P0 ¼ 0 Let wðtÞ :¼ w > ¼ te < 0 for all and wðtÞ e ¼ 1 for all t 0. Moreover it is wðtÞ> A00 ðwÞ remain inactive for t > 0, and the non-active inequality constraints at w sufficiently small t > 0 by continuity. Consequently, for some sufficiently small t > 0 the point w? :¼ wðtÞ satisfies w? 2 W3 and ðw? Þ> A0 < 0. In parh ticular it is w? > 0. This shows the assertion.
L. Neralic´, O. Stein
22
In order to stress that the regularity condition RC is in fact a generic condition we add the following topological consideration. For M; N 2 N and R minðM; N Þ let us define the set of ðM N Þmatrices of rank R, n o MN ¼ A 2 R rankðAÞ ¼ R : RMN R Moreover, for M; N 2 N, R minðM; N Þ, I f1; :::; Mg and maxðR þ jIj M; 0Þ S minðR; jIjÞ we let n o ðMjIjÞN MN ðIÞ RMN ¼ A 2 R 2 R A ; R;I;S R RS where the matrix AðIÞ results from A by deletion of the rows with indices in I. Observe that the above restrictions on S follow from the trivial relations 0 R S M jIj and R jIj R S R . Proposition 4.3. is a smooth manifold of codimension ðM RÞ ðN RÞ in (i) The set RMN R RMN . is a smooth manifold of codimension (ii) The set RMN R;I;S ðM RÞ ðN RÞ þ S ðM R þ S jIjÞ in RMN . Proof. The proof of part (i) can be found in [15]. For part (ii) see [20].
h
By Proposition 4.3(i) the matrix A from the regularity condition RC lies in a smooth manifold of full dimension if and only if A has (full) rank s þ m. Taking an ðs þ mÞ ðs þ mÞ submatrix of the matrix A in the regularity condition RC corresponds to the deletion of n rows of A> . Assume that then the rank drops from s þ m to s þ m S with some S 0. Then A lies in a smooth manifold of codimension S 2 in view of Proposition 4.3(ii). Hence under RC the matrix A is contained in the intersection of finitely many fulldimensional smooth manifolds, so that its entries are in general position. 5 A semi-infinite reformulation of parametric data envelopment analysis Throughout this section let the regularity condition RC hold. Then by Corollary 3.2(i) and Theorem 4.2 a decision making unit DMU0 is CCR-efficient if and only if the optimal value of SDLP0 vanishes. As we have seen in Section 3, the optimal value of SDLP0 does not exceed zero. Hence, the condition of a vanishing optimal value of SDPL0 is equivalent to its non-negativity. Furthermore we clearly can delete the slack variables in SDPL0 by transforming the equality constraint to an inequality constraint. These observations yield the following characterization of CCR-efficiency. Lemma 5.1. DMU0 is CCR-efficient if and only if minf hj P k þ he P0 ; k 0 g 0; h;k
where h 2 R and k 2 Rn .
ð3Þ
On regular and parametric DEA
23
In the following we will concentrate on perturbations of the vector P0 which enters condition (3) not only as the right-hand side of the first inequality constraint, but also via the matrix P . In order to make this dependence more transparent we write P 0 for the matrix which results from P by deletion of the column P0 , and we partition the vector k accordingly into k0 and k0 . The characterization (3) of CCR-efficiency can then be written equivalently as minf hj P 0 k0 þ ðk0 1ÞP0 þ he 0 ; k 0 g 0: h;k
ð4Þ
vector Consider now some DMU0 , characterized by its output/input Y0 DY0 P0 ¼ , as well as an additive perturbation DP0 ¼ that leads X0 DX0 to a new decision making unit P0 þ DP0 . By E0 let us denote the set of perturbations DP0 such that P0 þ DP0 is CCR-efficient. In view of (4) this set can be written as E0 ¼ f DP0 2 Rs Rm j
min
ðh;kÞ2KðDP0 Þ
h 0g
¼ f DP0 2 Rs Rm j h 0 for all ðh; kÞ 2 KðDP0 Þ g
ð5Þ
with KðDP0 Þ ¼ f ðh; kÞ 2 R Rn j P 0 k0 þ ðk0 1ÞðP0 þ DP0 Þ þ he 0 ; k 0 g : This description of the set E0 is called semi-infinite, as the vector DP0 is finitedimensional, but constrained by infinitely many inequality constraints. For an introduction to standard semi-infinite optimization we refer to [11] and [12]. In a standard semi-infinite constraint, however, the set K in (5) would not be allowed to depend on the decision vector DP0 . In the more general situation of (5) we speak of general semi-infinite optimization. For an introduction to theory and methods for general semi-infinite optimization problems, we refer to [20]. Since E0 is only the feasible set of a general semi-infinite optimization problem, we can add some objective function f in the variable DP0 to obtain the problem GSIP : max f ðDP0 Þ DP0
s.t.
DP0 2 E0 :
Depending on the choice of the perturbation vector DP0 and the objective function f the problem GSIP admits the investigation of a wide range of questions in parametric data envelopment analysis. In the following we will concentrate on the situation where directional perturbations are considered, i.e. it is DP0 ¼ a DP0 with a fixed direction DP0 and a scalar a. Then we can ask for the set of a 2 R such that P0 ðaÞ ¼ P0 þ a DP0 is CCR-efficient, i.e. for the set A0 ¼ f a 2 Rj a DP0 2 E0 g ¼ f a 2 Rj h 0 for all ðh;kÞ 2 Kða DP0 Þ g : Depending on whether or not P0 itself is an efficient or an inefficient DMU it makes sense to consider different optimization problems over the feasible set A0 .
L. Neralic´, O. Stein
24
DY0 If P0 is CCR-efficient we may choose a direction DP0 ¼ 0 and ask DX0 for the maximal parameter a 0 such that P0 þ a DP0 is still CCR-efficient, i.e. we have to solve the problem max a s.t. h 0 for all ðh; kÞ 2 Kða DP0 Þ: a
Note that a ¼ 0 is feasible for this problem, so that the constraint a 0 is redundant. Moreover, a numerical method for the solution of this problem can be started with the initial value a ¼ 0. If, on the other hand, P0 is inefficient we can choose a direction DY0 DP0 ¼ 0 and search for the minimal parameter a 0 such that DX0 P0 þ a DP0 becomes CCR-efficient, i.e. we determine the projection of P0 to the efficiency frontier along the direction DP0 . In this case we solve the problem min a s.t. h 0 for all ðh; kÞ 2 Kða DP0 Þ; a
where the constraint a 0 is again redundant as A0 contains only positive values. 6 Numerical results For our first numerical example, Table 2 gives a modified version of the problem from Example 2.2 with a perturbation such that the data are in general position. Table 2. Outputs and inputs for the modified Example 2.2 j
1
2
3
4
Yj
1
1
1
1
Xj
1 4
3 1
4 2
5 1:5
Table 3. Results for DMU1 with P1 =(1, )1 ,)4)> Perturbation DP1 0 1 0 @ 1 A 0 0 1 0 @ 1 A 1 0 1 0 @ 0 A 1
maximal a 2
2
þ1
Optimal P1 ðaÞ 0 1 1 @ 3 A 4 0 1 1 @ 3 A 6 –
On regular and parametric DEA
25
Table 4. Results for DMU2 with P2 ¼ ð1; 3; 1Þ> Perturbation DP2 0
maximal a
Optimal P2 ðaÞ
þ1
–
1
0 @ 1 A 0
0
1 0 @ 1 A 1 0 1 0 @ 0 A 1
1 1 @ 4 A 2
0
1 0 1.6667
1 1 @ 3 A 2:6667
Table 5. Results for DMU3 with P3 ¼ ð1; 4; 2Þ> Perturbation DP3 0 1 0 @1A 0 0 1 0 @1A 1 0 1 0 @0A 1
minimal a
Optimal P3 ðaÞ 0
1 1 @ 2:3333 A 2
1.6667
0
1 1 @ 3 A 1
1
0
1 1 @ 4 A 1
1
Table 6. Results for DMU4 with P4 ¼ ð1; 5; 1:5Þ Perturbation DP4 0 1 0 @1A 0 0 1 0 @1A 1 0 1 0 @0A 1
minimal a
optimal P4 ðaÞ 0
2.3333
1 1 @ 2:6667 A 1:5 0
0.5
1 1 @ 4:5 A 1 0
0.5
1 1 @ 5 A 1
It is not hard to verify geometrically that the numerical results correspond actually to the global maximizers and minimizers of the respective general semi-infinite optimization problems. This example also illustrates that at the
L. Neralic´, O. Stein
26 Table 7. Efficiency of Croatian banks under additive perturbations DMU
eff.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
n n y n n n y n n y n n y n n n y n n n n n n n y n n y n y n n n n n n n n n n n y n n n y n n
a 1080.94 1316.91 3009.65 108.27 218.08 369.00 233.81 417.61 4825.47 1558.90 4495.22 13289.36 908.49 1448.52 3719.87 81.91 944.48 7149.31 1214.14 1484.18 1139.50 3211.74 127.18 490.06 701.49 4113.24 499.00 51.41 2582.46 34.59 34162.00 980.71 3491.77 6185.80 9346.17 878.55 1925.36 1482.54 8395.47 187.99 4557.92 5184.94 891.61 66.58 6303.78 414.60 42340.54 717.38
optimal solutions the problem structure is such that the data are not in general position. This is an intrinsic property of data envelopment analysis. On the other hand, for feasible values of a arbitrary close to the optimum, the data are typically in general position, so that the calculated optima represent
On regular and parametric DEA
27
least upper bounds and greatest lower bounds, respectively, for CCR-efficient or inefficient DMUs. Having these observations in mind, we turn to our second numerical example which involves a significantly larger data set. In fact, the data were used in the recent efficiency investigation [13] of Croatian commercial banks, carried out by the Croatian National Bank. Each row of Table 7 corresponds to one of 48 Croatian banks which serve as decision making units. We use four inputs, namely interest and related costs, commissions for services and related costs, labor-related administrative costs (gross wages), and capitalrelated administrative costs (amortization, office maintenance, office supplies etc.). The first output denotes interest and related revenues, and the second output models non-interest revenues (commissions for provisions of services and related revenues). The data were measured in the year 1998 and range in magnitude between 102 and 106 . For each efficient bank we calculate the maximal efficiency-preserving perturbation along the direction e ¼ ð1; 1; 1; 1; 1; 1Þ> , whereas for the inefficient banks the minimal perturbation in direction þe is determined which leads to efficiency. The corresponding maximal or minimal a’s are given in the last column of Table 7. Judging on the basis of directional perturbations along this special direction it turns out that there are major differences between the efficient banks. In fact, the DMUs 3 and 42 can be perturbed by an amount which is about one hundred times larger than the amount for DMUs 28 and 30. On the other hand, the inefficient DMUs 16 and 44 are by three magnitudes closer to efficiency (along our special direction) than DMUs 31 and 47. We emphasize that the investigation of directional perturbations does not determine the distance of a DMU to the efficiency frontier in some norm (for such approaches see, e.g., the survey in [9]). Rather it is tailored for the case when dependencies between perturbations of inputs and outputs are to be modeled. As mentioned before, our method does not only apply to directional perturbations of the data, and it may also be used to study simultaneous perturbations of all involved DMUs. Moreover, our approach can be adapted to other models in data envelopment analysis like the so-called BCC model, as introduced by Banker, Charnes, and Cooper ([1]), or the additive model ([2]). These topics will be subject of future research. Acknowldegements. We express our thanks to Igor Jemric´ and Boris Vujcˇic´ for providing the data for the efficiency analysis of Croatian banks, and to the anonymous referees for their precise and substantial remarks.
References [1] Banker RD, Charnes A, Cooper WW (1984) Some models for estimating technical and scale inefficiencies in data envelopment analysis. Management Science 30:1078–1092 [2] Charnes A, Cooper WW, Golany B, Seiford L, Stutz J (1985) Foundations of data envelopment analysis for Pareto-Koopmans efficient empirical production functions. Journal of Econometrics 30:91–107 [3] Charnes A, Cooper WW, Lewin AY, Seiford LM (1994) Data Envelopment Analysis: Theory, Methodology, and Applications. Kluwer, Boston
28
L. Neralic´, O. Stein
[4] Charnes A, Cooper WW, Rhodes E (1978) Measuring the efficiency of decision-making units. European Journal of Operational Research 2:429–444 [5] Charnes A, Cooper WW, Seiford L, Stutz J (1983) Invariant multiplicative efficiency and piecewise Cobb-Douglas envelopments. Operations Research Letters 2:101–105 [6] Charnes A, Cooper WW, Wei QL (1987) A semi-infinite multicriteria programming approach to data envelopment analysis with infinitely many decision-making units. Research Report CCS 551, Center for Cybernetic Studies, University of Texas [7] Charnes A, Neralic´ L (1990) Sensitivity analysis of the additive model in data envelopment analysis. European Journal of Operational Research, 48:332–341. [8] Charnes A, Neralic´ L (1992) Sensitivity in data envelopment analysis. III. Glasnik Matematicˇki, 27:191–201 [9] Cooper WW, Li S, Seiford LM, Tone K, Thrall RM, Zhu J (2001) Sensitivity and stability analysis in DEA: some recent developments. Journal of Productivity Analysis 15:217–246 [10] Cooper WW, Seiford LM, Tone K (2000) Data Envelopment Analysis: A Comprehensive Text with Models, Applications, References and DEA-Solver Software. Kluwer, Boston [11] Goberna MA, Lo´pez MA (1998) Linear semi-infinite optimization. Wiley, Chichester [12] Hettich R, Kortanek KO (1993) Semi-infinite programming: theory, methods, and applications. SIAM Review 35:380–429 [13] Jemric´ I, Vujcˇic´ B (2002) Efficiency of banks in Croatia: a DEA approach. Comparative Economic Studies, XLIV:169–193 [14] Jess A, Jongen HTh, Neralic´ L, Stein O (2001) A semi-infinite programming model in data envelopment analysis. Optimization, 49:369–385 [15] Jongen HTh, Jonker P, Twilt F (2000) Nonlinear Optimization in Finite Dimensions. Kluwer, Dordrecht [16] Joro T, Korhonen P, Wallenius J (1998) Structural comparison of data envelopment analysis and multiple objective linear programming. Management Science 44:962–970 [17] Lo´pez MA, Pastor JT (1999) A semi-infinite programming approach to DEA, Preprint [18] Neralic´ L (2000) Sensitivity in data envelopment analysis for arbitrary perturbations of all data in the Charnes-Cooper-Rhodes model. In: Guddat J, Hirabayashi R, Jongen HTh, Twilt F (eds): Parametric Optimization and Related Topics V, Peter Lang, Frankfurt am Main, 143–163 [19] Neralic´ L (2001) Preservation of efficiency and inefficiency classification in data envelopment analysis, Preprint [20] Stein O (2003) Bi-level Strategies in Semi-infinite Programming. Kluwer, Boston [21] Thompson R, Dharmapala PS, Thrall R Sensitivity analysis of efficiency measures with applications to Kansas farming and Illinois coal mining. in: [3]:393–422 [22] Yu G, Wei Q, Brockett P (1996) A generalized data envelopment analysis model: a unification and extension of existing methods for efficiency analysis of decision making units. Annals of Operations Research 66:47–89
