A neurodynamic scheme to bi-level revenue-based centralized resource allocation models

1 Introduction

Data envelopment analysis (DEA), originally developed by Charnes et al. [8], is a linear programming methodology for assessing relative efficiency and productivity of multiple inputs and outputs DMUs. These DMUs consumes inputs to produce outputs. DEA identifies an efficient frontier such that the DMUs lying on the frontier operate efficiently; otherwise, they are inefficient DMUs. DEA assigns an efficiency score to inefficient units and computes benchmarks for each DMU. Because of the inherent characteristics of DEA, including trade-offs between the inputs/outputs, this approach is widely used for allocation of resources of a large organization to its subordinate DMUs. Many traditional DEA models in resource allocation cited in the literature analyze one unit at a time independently (see [11, 23]).

In many real applications of DEA (such as banking sector, industrial R&D projects, university departments, etc.) there are situations in which all the DMUs operate under the supervision of a central decision maker that decides to determine input resources and output targets for those units. In DEA literature, extensive research already exists concerning applications with resource centralized allocation. Athanassopoulos [3] proposed a target-based resource allocation to link performance measurement and resource allocation in multiunit multilevel organizations. he designed a multilevel planning system for resource allocation and target setting in the provision of public services. Hosseinzadeh Lotfi et al. [39] using the slacks-based measure and the enhanced Russell measure models, and the allocation model, presented a non-radial model for centralized resource allocation in insurance companies. Lozano et al. [42] formulated several centralized DEA models for ports resource allocation, target setting, and capital budgeting.

Although there are a wide variety of centralized DEA-based models for resource allocation (e.g. [1–3, 39–42]), there are few DEA-based CRA models from the revenue efficiency perspective. Nesterenko and Zelenyuk [47] provided a group revenue reallocation efficiency approach to compute how much group revenues may be increased, even if all its DMUs are individually efficient. Extending Lozano et al. [42] models, Fang and Li [22] and Fang [21] presented some centralized models for resource allocation based on revenue efficiency.

Since the computing time needed to solve a DEA problem greatly depends on its dimension and structure, traditional algorithms cannot evaluate the efficiency of large scale data sets. Unlike traditional algorithms, artificial neural networks have massively paralleled distributed computation, fast convergence and robust solution. Therefore, artificial neural networks can be considered as a promising approach to solve the large-scale DEA problems in real time. Tank and Hopfield [54] were the first to introduce the neural network for solving optimization problems. The main feature of these neural networks is that its equilibrium point coincides with the solution of the corresponding optimization problem. In recent years, neural networks for solving mathematical programming problems have attracted attention in the literature [7, 55–60].

In last decade, some researchers dealt with solving the linear bi-level programming problem (LBPP) by neural network approach. For example, based on the approach proposed in [54], Shih et al. [49] developed a recurrent neural network to solve multiobjective and multilevel programming problems. Lan et al. [37] introduced a combined neural network and tabu search hybrid algorithm to solve LBPP. Hu et al. [32] and Lv and Wan [43] presented neural networks based on a perturbed nonlinear complementarity problem (NCP) function for solving LBPP. Based on the theory of nonsmooth analysis, He at al. [31] proposed a neural network to solve LBPP, which was modeled by a nonautonomous differential inclusion.

Motivated by our discussion thus far, in the present paper, merging the usual centralized DEA model based on revenue efficiency and the reallocation cost model, we introduce a novel bi-level CRA model based on revenue efficiency. This bi-level CRA model is hierarchical in the sense that its constraints are defined in part by a second optimization problem. The main novelty of the presented bi-level CRA model lies in its interpretation as a hierarchical game of two decision makers which make their decisions according to an hierarchical order. Also, by using the KKT conditions and the NCP function, a novel neural network is introduced for searching the optimal solution of the proposed bi-level CRA model. This neural network is investigated to be globally stable by constructing a suitable Lyapunov function and the output trajectory is convergent to an optimal solution of the bi-level CRA problem.

The contributions of this paper can be summarized as follows:

In this paper, to provide valuable managerial insights, we extend the usual centralized DEA models by developing a bi-level CRA model that attempts to maximize the total revenue and to minimize the reallocation cost simultaneously.

The paper proceeds as follows. In Section 2, we review the traditional revenue efficiency DEA formulations. A bi-level centralized DEA model based on revenue efficiency for resource reallocation is introduced in Section 3. In Section 4, a neural network model is designed for solving the proposed bi-level CRA model. The convergence and the stability of the proposed neural network are proved in Section 5. Three illustrative examples are given in Section 6. Finally, some conclusions are drawn in Section 7.

2 Preliminaries

In this section, the traditional revenue efficiency model [12] and the CRA model based on revenue efficiency proposed by Fang and Li [22] are briefly discussed. The following notations are employed throughout this paper,

n Number of observed units j , k Indices for observed units J = { 1 , … , n } Set of DMU indices m Number of inputs i Index for inputs I = { 1 , … , m } Complete set of input indices s Number of outputs r Index for outputs R = { 1 , … , s } Set of output indices U Set of un - reallocatable inputs x j Input vector of unit j x ij Value of input i of unit j y j Output vector of unit j y rj Value of output r of unit j x ¯ ik Target for input i of unit k y ¯ rk Target for output r of unit k p Price vector of outputs p rk Price of output r of unit k ( λ 1 k , λ 2 k , … , λ nk ) Vector for projecting unit k

Let us consider a set of DMUs consisting of DMU _j (j ∈ J), with input-output vectors (x _j , y _j ) (j ∈ J), in which x _j  = (x_1j, …, x _mj )  ^T and y _j  = (y_1j, …, y _sj )  ^T . Arranging the data set in matrices X = [x₁, x₂, …, x _n ], X > 0 and Y = [y₁, y₂, …, y _n ], Y > 0, and assuming variable returns to scale (VRS) technology, the production possibility set can be expressed as

T = { ( x , y ) | x ≥ ∑ j = 1 n x j λ j , y ≤ ∑ j = 1 n y j λ j , ∑ j = 1 n λ j = 1 , λ j ≥ 0 , j = 1 , … , n } .

The standard DEA model based on this assumption is called the BCC model [4]. Given the common unit price vector p = (p₁, …, p _s ) for the output y, the maximum revenue for DMU _o is obtained as follows [12]:

max p y s . t . X λ ≤ x o Y λ ≥ y , 1 T λ = 1 , λ ≥ 0 ,(1) where 1 = [ 1 , … , 1 ] T ∈ ℝ n , and λ = (λ₁, …, λ _n )  ^T is a non-negative vector in ℝ n . Let the optimal solution of (1) be (y^*, λ^*). Then, the revenue efficiency of DMU _o is defined by means of the following ratio: R E o ( Revenue Efficiency ) = p y * p y o .

Now, we consider that there is a central decision maker who oversees all the operating units. To allocate the input resources to a set of existing units so that the total output revenue will be maximized, Fang and Li [22] proposed the revenue allocation model based on revenue efficiency as follows:

max φ = ∑ k = 1 n ∑ r = 1 s p rk y ¯ rk + ɛ ∑ i ∉ U ∑ k = 1 n s ik - s . t . ∑ j = 1 n λ jk x ij ≤ x ik , k ∈ J , i ∈ U , ∑ j = 1 n λ jk x ij + s ik - = x ¯ ik , k ∈ J , i ∉ U , ∑ j = 1 n λ jk y rj = y ¯ rk , k ∈ J , r ∈ R , ∑ k = 1 n x ¯ ik = ∑ k = 1 n x ik , i ∈ I , i ∉ U , ∑ j = 1 n λ jk = 1 , k ∈ J , λ jk ≥ 0 , j , k ∈ J ,(2) where s ik - denotes the slack of input i for unit k, and ɛ is a positive non-Archimedean infinitesimal. It must be considered that in most cases there are costs associated with the reallocation on the inputs. Therefore, Fang and Li [22] developed the following model which takes the minimum reallocation cost:

min ξ = ∑ i ∉ U ∑ k = 1 n c ik - γ ik - + ∑ i ∉ U ∑ k = 1 n c ik + γ ik + s . t . ∑ j = 1 n λ jk x ij ≤ x ik , k ∈ J , i ∈ U , ∑ j = 1 n λ jk x ij + s ik - = x ¯ ik , k ∈ J , i ∉ U , ∑ j = 1 n λ jk y rj = y ¯ rk , k ∈ J , r ∈ R , ∑ k = 1 n ∑ r = 1 s p rk y ¯ rk + ɛ ∑ i ∉ U ∑ k = 1 n s ik - = φ * ∑ k = 1 n x ¯ ik = ∑ k = 1 n x ik , i ∈ I , i ∉ U , x ¯ ik + γ ik - - γ ik + = x ik , k ∈ J , i ∉ U , ∑ j = 1 n λ jk = 1 , k ∈ J , λ jk ≥ 0 , γ ik - ≥ 0 , γ ik + ≥ 0 , j , k ∈ J , i ∉ U ,(3) where φ^* is the optimal objective value obtained in the model (2). γ ik - and γ ik + denote the negative deviation and the positive deviation from the current level of input i for DMU _k , respectively, c ik - and c ik + , denote the cost of moving one unit of input i from DMU _k and into DMU _k , respectively.

In this section, we present a bi-level DEA-based model for centralized resource allocation based on revenue efficiency in which the minimum cost of reallocating the inputs is obtained. The upper-level model is concerned with determining the minimum reallocation cost while input resources and output targets are evaluated in the lower-level model. The bi-level programming problem (BPP) corresponding to the linear program (2) and (3) can be described as follows: ( UP ) min γ - , γ + ξ ¯ = ∑ i ∉ U ∑ k = 1 n c ik - γ ik - + ∑ i ∉ U ∑ k = 1 n c ik + γ ik + s . t . x ¯ ik + γ ik - - γ ik + = x ik , k ∈ J , i ∉ U , γ ik - ≥ 0 , γ ik + ≥ 0 , k ∈ J , i ∉ U , ( LP ) max x ¯ , y ¯ , λ φ ¯ = ∑ k = 1 n ∑ r = 1 s p r y ¯ rk s . t . ∑ j = 1 n λ jk x ij ≤ x ¯ ik , i ∈ I , k ∈ J , x ¯ ik ≤ x ik , i ∈ U , k ∈ J , ∑ k = 1 n x ¯ ik ≤ ∑ r = 1 n x ik , i ∉ U , ∑ j = 1 n λ jk y rj ≥ y ¯ rk , r ∈ R , k ∈ J , y ¯ rk ≥ y rk , r ∈ R , k ∈ J , ∑ j = 1 n λ jk = 1 , k ∈ J , λ jk ≥ 0 , j , k ∈ J .(4)

The term (UP) is called the upper level problem and (LP) is called the lower level problem. This bi-level CRA model can be interpreted as an hierarchical game of two decision makers which make their decisions according to an hierarchical order. The first decision maker (referred to as the leader) makes his selection first and communicates it to the second decision maker (referred to as the follower). Then, knowing the choice of the leader, the follower selects his response as an optimal solution of LP problem and gives this back to the leader. Thus, the leader’s task is to determine a best decision. According to this perspective, at the UP, the decision maker has to choose first a vector ( γ ik - , γ ik + ) T , i ∉ U, k ∈ J, to minimize his objective function ξ ¯ ; then under this decision the LP decision maker has to select the decision vector ( x ¯ ik , y ¯ rk , λ jk ) T , j, k ∈ J, r ∈ R, i ∉ U, that maximizes his own objective φ ¯ . The BPP (4) can be reduced to the one-level programming problem by replacing the lower-level problem with its KKT optimality conditions as follows: min ξ ¯ = ∑ i ∉ U ∑ k = 1 n c ik - γ ik - + ∑ i ∉ U ∑ k = 1 n c ik + γ ik + s . t . x ¯ ik + γ ik - - γ ik + = x ik , k ∈ J , i ∉ U , γ ik - ≥ 0 , γ ik + ≥ 0 , k ∈ J , i ∉ U , ∑ i = 1 m v ij x ij - ∑ r = 1 s u rj y rj + δ k ≥ 0 , j , k ∈ J , τ i - v ij ≥ 0 , i ∉ U , j ∈ J , η ij - v ij ≥ 0 , i ∈ U , j ∈ J , u rj - π rj ≥ p r , r ∈ R , j ∈ J , v ik ( x ¯ ik - ∑ j = 1 n λ jk x ij ) = 0 , i ∈ I , k ∈ J , η ik ( x ik - x ¯ ik ) = 0 , i ∈ U , k ∈ J , τ i ( ∑ k = 1 n x ik - ∑ k = 1 n x ¯ ik ) = 0 , i ∉ U , u rk ( ∑ j = 1 n λ jk y rj - y ¯ rk ) = 0 , r ∈ R , k ∈ J , π rk ( y ¯ rk - y rk ) = 0 , r ∈ R , k ∈ J , ∑ j = 1 n λ jk x ij ≤ x ¯ ik , i ∈ I , k ∈ J , x ¯ ik ≤ x ik , i ∈ U , k ∈ J , ∑ k = 1 n x ¯ ik ≤ ∑ k = 1 n x ik , i ∉ U , ∑ j = 1 n λ jk y rj ≥ y ¯ rk , r ∈ R , k ∈ J , y ¯ rk ≥ y rk , r ∈ R , k ∈ J , ∑ j = 1 n λ jk = 1 , k ∈ J , τ i ≥ 0 , v ij ≥ 0 , η ij ≥ 0 , u rj ≥ 0 , π rj ≥ 0 , λ jk ≥ 0 , δ k is free ,(5) where γ k - , γ k + , τ ∈ ℝ m - | U | , v j ∈ ℝ m , η j ∈ ℝ | U | , u j ∈ ℝ s , π j ∈ ℝ s , and δ ∈ ℝ n .

In this section, using the idea of the perturbed Fischer-Burmeister function [25, 33], we construct a smooth approximation of the KKT transformation of the bi-level CRA model (4). Following this smoothing method, we introduce a novel neurodynamic model for solving MPCC (5).

Definition 4.1. A function φ : ℝ 2 → ℝ is said to be an NCP function if it satisfies φ ( a , b ) = 0 ⇔ a ≥ 0 , b ≥ 0 , ab = 0 .

Various NCP functions have been devised [34, 51]. The Fischer-Burmeister (FB) function is one of the most popular NCP functions, which is defined by φ FB ( a , b ) = a 2 + b 2 + ɛ - a - b .

The perturbed FB function is a generalization of the FB function, which is defined by φ FB ɛ ( a , b ) = a 2 + b 2 + ɛ - a - b , ɛ → 0 + .

This function is continuously differentiable everywhere. Moreover, φ FB ɛ ( a , b ) = 0 ⇔ a > 0 , b > 0 , ab = ɛ 2 ,(6) for every ɛ > 0. Using the perturbed FB function, the problem (5) can be restated as follows

min ξ ¯ = ∑ i ∉ U ∑ k = 1 n c ik - γ ik - + ∑ i ∉ U ∑ k = 1 n c ik + γ ik + s . t . x ¯ ik + γ ik - - γ ik + = x ik , k ∈ J , i ∉ U , ∑ i = 1 m v ij x ij - ∑ r = 1 s u rj y rj + δ k ≥ 0 , k ∈ J , j ∈ J , τ i - v ij ≥ 0 , i ∉ U , j ∈ J , η ij - v ij ≥ 0 , i ∈ U , j ∈ J , u rj - π rj ≥ p r , r ∈ R , j ∈ J , ( v ik 2 + ( x ¯ ik - ∑ j = 1 n λ jk x ij ) 2 + ɛ ) 1 / 2 - v ik - ( x ¯ ik - ∑ j = 1 n λ jk x ij ) = 0 , i ∈ I , k ∈ J ,

( η ik 2 + ( x ik - x ¯ ik ) 2 + ɛ ) 1 / 2 - η ik - ( x ik - x ¯ ik ) = 0 , i ∈ U , k ∈ J , ( τ i 2 + ( ∑ k = 1 n x ik - ∑ k = 1 n x ¯ ik ) 2 + ɛ ) 1 / 2 - τ i - ( ∑ k = 1 n x ik - ∑ k = 1 n x ¯ ik ) = 0 , i ∉ U , ( u rk 2 + ( ∑ j = 1 n λ jk y rj - y ¯ rk ) 2 + ɛ ) 1 / 2 - u rk - ( ∑ j = 1 n λ jk y rj - y ¯ rk ) = 0 , r ∈ R , k ∈ J , ( π rk 2 + ( y ¯ rk - y rk ) 2 + ɛ ) 1 / 2 - π rk - ( y ¯ rk - y rk ) = 0 , r ∈ R , k ∈ J , ( μ jk 2 + λ jk 2 + ɛ ) 1 / 2 - μ jk - λ jk = 0 , j , k ∈ J , ∑ j = 1 n λ jk = 1 , k ∈ J , δ k is free , γ ik - ≥ 0 , γ ik + ≥ 0 , k ∈ J , i ∉ U .(7)

For notational convenience, introducing G ( w ) = ( - ∑ i = 1 m v ij x ij + ∑ r = 1 s u rj y rj - δ k , k , j ∈ J - τ i + v ij , i ∉ U , j ∈ J - η ij + v ij , i ∈ U , j ∈ J p r - u rj + π rj , r ∈ R , j ∈ J - γ - - γ + ) , H ( w ) = ( x ¯ ik + γ ik - - γ ik + - x ik , k ∈ J , i ∉ U φ FB ɛ ( v ik , x ¯ ik - ∑ j = 1 n λ jk x ij ) , i ∈ I , k ∈ J φ FB ɛ ( η ik , x ik - x ¯ ik ) , i ∈ U , k ∈ J φ FB ɛ ( τ i , ∑ k = 1 n x ik - ∑ k = 1 n x ¯ ik ) , i ∉ U φ FB ɛ ( u rk , ∑ j = 1 n λ jk y rj - y ¯ rk ) , r ∈ R , k ∈ J φ FB ɛ ( π rk , ( y ¯ rk - y rk ) ) , r ∈ R , k ∈ J φ FB ɛ ( μ jk , λ jk ) , j , k ∈ J ∑ j = 1 n λ jk - 1 , k ∈ J ) , w = ( λ k T , x ¯ k T , y ¯ k T , γ k - T , γ k + T , u j T , ν j T , η j T , τ T , π T , δ T , μ k T ) T ∈ ℝ q , where q = n (2n + 3s + 1 - |U|) + m (4n + 1) - |U|, the problem (7) can be rewritten as the following equivalent problem: min ξ ¯ ( w ) = ∑ i ∉ U ∑ k = 1 n c ik - γ ik - + ∑ i ∉ U ∑ k = 1 n c ik + γ ik + s . t . G l ( w ) ≤ 0 , l = 1 , … , p 1 , H o ( w ) = 0 , o = 1 , … , p 2 ,(8) where p₁ = n (n + 3m + s - 2|U|) and p₂ = m (2n + 1) + n (2s + n + 1) - |U|.

Definition 4.2. Let w′ be a feasible point of (8) and denote L = {l : G _l  (w′) =0, l = 1, …, p₁}. w′ is said to be a regular point to the above problem (8) if the gradient vectors ∇H _o  (w′), o = 1, …, p₂, and ∇G _l  (w′), l ∈ L are linearly independent.

Theorem 4.1. (Dempe [13]) Let {(w)  ^ɛ } be a sequence of solutions to problem (8). Suppose the sequence {(w)  ^ɛ } converges to some w ¯ for ɛ → 0. If w ¯ is the regular point of the problem (8), then w ¯ solves the problem (5).

Now, consider the Lagrangian function associated with (8) as follows: L ( w , α , β ) = ξ ¯ ( w ) + ∑ l = 1 p 1 β l G l ( w ) + ∑ o = 1 p 2 α o H o ( w ) , where the terms α, β are referred as Lagrange multipliers. Let w′ be a regular point, and also feasible to the problem (8). Using saddle point theorem [5], there exist ( α , β ) ∈ ℝ p 1 + p 2 with β ≥ 0, such that the following KKT optimality conditions are satisfied at (w′, α, β):

∇ ξ ¯ ( w ′ ) + ∇ G ( w ′ ) T β + ∇ H ( w ′ ) T α = 0 , G ( w ′ ) ≤ 0 , H ( w ′ ) = 0 , β T G ( w ′ ) = 0 , w ≥ 0 , β ≥ 0 .(9)

Lemma 4.1. w ^* is a KKT point of (8) as ɛ → 0⁺ if and only if z^* = (w^{* T} , α^{* T} , β^{* T} )  ^T satisfies κ ( z ) = [ ∇ ξ ¯ ( w ) + ∇ G ( w ) T β + ∇ H ( w ) T α - H ( w ) φ FB ɛ ( β , - G ( w ) ) ] = 0 .(10)

Proof Letting κ (z^*) =0 we obtain ∇ ξ ¯ ( w * ) + ∇ G ( w * ) T β * + ∇ H ( w * ) T α * = 0 ,(11) H ( w * ) = 0 ,(12) φ FB ɛ ( β * , - G ( w * ) ) = 0 . Using (6), the equality φ FB ɛ ( β * , - G ( w * ) ) = 0 leads to β * ≥ 0 , G ( w * ) ≤ 0 , β * T G ( w * ) = 0 , as ɛ → 0 + .(13) Combining (11)–(13) it is easily seen that z^* = (w^{* T} , α^{* T} , β^{* T} )  ^T satisfies the KKT conditions (9). The proof of the converse is obvious. □

Consider the following unconstrained smooth minimization problem:

min E ( z ) = 1 2 ∥ κ ( z ) ∥ 2 ,(14) where z = (w ^T , α ^T , β ^T )  ^T , and E (z) is a continuously differentiable merit function. Using Definition 4.1 and Lemma 4.1, it is obvious that finding a point of the system (9) can be thought of as equivalent to solving the above problem (14).

Now, we describe a gradient neural network for solving problem (8) whose state variable is defined by the following continuous-time dynamical system:

dz ( t ) dt = - Λ ∇ E ( z ) , z ( t 0 ) = z 0 ,(15) where Λ > 0 which is to scale the convergence rate of (15). The hardware implementation of the proposed neurodynamic model (15) can be indicated as a simplified block diagram without the penalty parameter in Figure  1.

OPEN IN VIEWER

Fig.1

Schematic block diagram of the neurodynamic model (15).

In this section, we study the stability and convergence properties of the proposed neurodynamic model (15). First, we review some basic definitions and lemmas.

Definition 5.1. Take the following dynamical system x ̇ = F ( x ( t ) ) , x ( t 0 ) = x 0 ∈ ℝ n ,(16) where F is a function from ℝ n into ℝ n , x^* is called an equilibrium point of (16) if F ( x * ) = 0 . If there is a neighborhood Ψ * ⊆ ℝ n of x^* such that F ( x * ) = 0 and F ( x * ) ≠ 0 , ∀x∈ Ψ^* ∖ { x^* }, then x^* is called an isolated equilibrium point.

Definition 5.2. (Lyapunov Function) Let Ψ ⊆ ℝ n be an open neighborhood of x ¯ . A continuously differentiable function V : ℝ n → ℝ is said to be a Lyapunov function at the state x ¯ over the set Ψ for (16) if

V ( x ¯ ) = 0 , V ( x ) > 0 , ∀ x ∈ Ψ ∖ { x ¯ } .

Definition 5.3. (Lyapunov Stability) Let x (t) be a solution of (16). An isolated equilibrium point x^* is Lyapunov stable if for any x₀ = x (t₀) and any ɛ > 0 there exist a δ > 0 so that if ∥x (t₀) - x^* ∥ < δ then ∥x (t) - x^* ∥ < ɛ, for t ≥ t₀.

Definition 5.4. (Asymptotic Stability) An isolated equilibrium point x^* is said to be asymptotic stable if in addition to being Lyapunov stable, it has the property that if ∥x (t₀) - x^* ∥ < δ, then x (t) → x^* as t→ + ∞.

Lemma 5.1. (Miller and Michel [45])

An isolated equilibrium point x^* of (16) is Lyapunov stable if there exists a Lyapunov function over some neighborhood Ψ^* of x^*.

Definition 5.5. Let X^* be the set of equilibrium points of (16). The dynamic system (16) is said to converge globally to X^* if irrespective of the initial point, the trajectory of the dynamic system x (t) satisfies lim t → ∞ dist ( x ( t ) , X * ) = 0 , where dist ( x ( t ) , X * ) = inf y ∈ Ψ * ∥ x - y ∥ .

Lemma 5.2. If A is n × n nonsingular matrix, then the homogeneous system AX = 0 has only the trivial solution X = 0.

Lemma 5.3. Let z ∈ ℝ q + p 1 + p 2 be any given triple. If

Then the jacobian matrix ∇κ (z) is nonsingular.

Proof. Using [53, Proposition 3.2] and [52, Proposition 3.3], ∇κ (z) has the following structure:

∇ κ ( z ) = [ ∇ ww 2 L ( w , α , β ) - ∇ H ( w ) ( - diag { ∇ G l φ FB ɛ ( β l , - G l ( w ) ) } l = 1 p 1 ) ∇ G ( w ) ∇ H ( w ) T ∇ G ( w ) T 0 p 2 × p 2 0 p 2 × p 1 0 p 1 × p 2 - diag { ∇ β l φ FB ɛ ( β l , - G l ( w ) ) } l = 1 p 1 ] .(17)

By [52, Theorem 3.1] we deduce that ∇κ (z) is nonsingular.□

We now study the relationship between the equilibrium point of (15) and the optimal solution of the problem (8).

Theorem 5.1

Proof.

Noting Lemma 4.1, if w^* is a KKT point of the problem (8), then it is clear that κ (z^*) =0. By the chain rule we have

∇ E ( z ) = ∇ ( κ ( z ) ) T κ ( z ) , where ∇ (κ (z)) is the Jacobian matrix of κ (z). This yields ∇E (z^*) =0, i.e. z^* is an equilibrium point of the neural network (15).

Theorem 5.2. Let z^* be an isolated equilibrium point of the neural network (15). Then z^* is asymptotically stable.

Proof. First, applying the definition of E (z), Lemma 4.1 and Theorem 5.1 optimequi give E (z) ≥0 and E (z^*) =0. Because z^* is an isolated equilibrium point of (15), there exists a neighborhood Ω * ⊆ ℝ q + p 1 + p 2 of z^* such that ∇ E ( z * ) = 0 and ∇ E ( z ) ≠ 0 , ∀ z ∈ Ω * ∖ { z * } .

To prove that E (z) is a Lyapunov function over the set Ω^* for (15), we need to show that E (z) >0 for any z ∈ Ω^* ∖ {z^*}. Suppose, by contradiction, that there exists a z′ ∈ Ω^* ∖ {z^*} such that E (z′) = 0. Then, we deduce that ∇E (z′) = 0, i.e., is also an equilibrium point of (15). This contradicts the assumption that z^* is an isolated equilibrium point in Ω^*. Furthermore, by the definition of E (z) and (15), it follows that dE ( z ( t ) ) dt = [ ∇ E ( z ( t ) ) ] T dz ( t ) dt = - Λ ∥ ∇ E ( z ( t ) ) ∥ 2 ≤ 0 , and dE ( z ( t ) ) dt < 0 , ∀ z ( t ) ∈ Ω * ∖ { z * } . This, along with Definition 5.2 and Lemma 5.1, shows that E (z) is a Lyapunov function and z^* is asymptotically stable. □

Theorem 5.3. Suppose that z = z (t, z₀) is a trajectory of (15) in which the initial point is z₀ = z (0, z₀) and the level set L ( z 0 ) = { z ∈ ℝ q + p 1 + p 2 | E ( z ) ≤ E ( z 0 ) } is bounded. Then

Proof. (i) Let z^* be an equilibrium point of the neural network (15), which means that ∇E (z^*) =0. Differentiating E (z) along the trajectory z (t, z₀) , (t ≥ 0), we have d E ( z ( t ) ) dt = [ ∇ E ( z ( t ) ) ] T dz dt = - Λ ∥ ∇ E ( z ( t ) ) ∥ 2 ≤ 0 ,(18) so, E (z) is monotone nonincreasing along the trajectory z = z (t, z₀) , (t ≥ 0). Hence Φ⁺ (z₀) ⊆ L (z₀), which means that Φ⁺ (z₀) = {z (t, z₀) | t ≥ 0} is bounded.

(ii) From part (i), Φ⁺ (z₀) = {z (t, z₀) | t ≥ 0} is bound. Considering strictly increasing sequence { t ¯ n } , 0 ≤ t ¯ 1 ≤ . . . ≤ t ¯ n ≤ . . . , t ¯ n → + ∞ , we have { z ( t ¯ n , z 0 ) } is a bounded sequence composed of infinite points. Hence, there exists a convergent subsequence { t n } ⊆ { t ¯ n } , t n → + ∞ such that lim n → + ∞ z ( t n , z 0 ) = z ¯ , where z ¯ satisfies d E ( z ( t ) ) dt = 0 . By the LaSalle’s invariant principle [36, Theorem 4.4], we have z ¯ ∈ M , where M is the largest invariant set in S = { z ( t , z 0 ) | d E ( z ( t , z 0 ) ) dt = 0 } . From (15) and (18), it follows that dw dt = 0 , d α dt = 0 and d β dt = 0 ⇔ d E ( z ( t ) ) dt = 0 . Thus z ¯ ∈ Z * by M ⊆ S ⊆ Z^*, where Z^* is the optimal point set of (8). Therfore, for any initial state z₀, the trajectory z (t, z₀) of neural network (15) converges to z ¯ , where z ¯ is the optimal solution of (8). This completes the proof.□

The following corollary is an immediate consequence of Theorems 5.2 and 5.3.

Corollary 5.1.Let Z * = { ( w * T , α * T , β * T ) T } be the optimal point set of (8). Then the neurodynamic model (15) for solving (8) is globally asymptotically stable and is convergent to the unique equilibrium point Z * = ( w * T , α * T , β * T ) T.

To illustrate the applicability and efficiency of the proposed approach, in this section, we use simulated data borrowed from [14, 40]. To show further the accuracy of the proposed model (4) and the neural network (15), we compare the obtained results in this article by the results in [22], through the following examples. The simulation is carried out in GAMS 24.1.3 and Matlab R2014a, the ordinary differential equation solver engaged is ode45.

Example 1.In this example, to illustrate further the validity of the proposed approach, a single-input, single-output, with seven DMUs dataset from [40] will be used. We can formulate CRA model based on revenue efficiency as the bi-level programming problem (4). Assume that the output price is p = 10 and the reallocation cost of inputs is c ik - = c ik + = 0.5 for i = 1 and k = 1, . . . , 7. The proposed neural network in (15) is used to solve this problem by letting Λ = 1 and ɛ = 0.01. In Figure 2(a), it can be found that the output state trajectory of the neurodynamic model (15) is convergent to the optimal solution with the random initial points and Λ = 1. Figure 2(b) also depicts the convergence behavior of l₂-norm error ∥z (t) - z^* ∥ ₂ based on the model (15) with a random initial point. Table 1 summarizes data and results of resources reallocation using the Fang and Li’s approach [22] and the proposed bi-level model (4). By comparing the results, we observe that the ratio of the total output production to the total input consumption of projection points for the proposed approach is equal to 1.9424, while for the Fang and Li’s approach it is equal to 1.8816. Also, the proposed approach and the Fang and Li’s approach are compared in Table 2 in terms of CCR efficiency score. As shown in Table 2, in the results obtained from the Fang and Li’s model, five units are efficient while according to the results of our model, DMU 4 is the only one that is efficient. Thus, it seems that the proposed model is more rigorous than the Fang and Li’s model. From the managerial point of view, our model represents a more realistic performance of the units and can reduce the requirements of the ranking. It is straightforward to see that the new results by the proposed approach are more suitable.

OPEN IN VIEWER

Fig.2

(a) Transient behaviors of (x ^T , y ^T )  ^T of the neurodynamic model (15) with a random initial vector point and Λ = 1 in Example 1, (b) Convergence behavior of the output trajectory norm error based on (15) with a random initial point and Λ = 1 in Example 1.

Example 2.In this example, we apply our approach to a real world dataset consisting of 20 fast-food restaurants from [14]. Table 3 exhibits the dataset for 20 fast-food restaurants in terms of two inputs, man-hours and shop size, and five outputs identified as the sales of meat dishes, vegetables dishes, soup, noodles and beverages. The output price vector is p = (32, 15, 10, 6, 3)  ^T and the reallocation cost of a man-hour per 10³h is 1. The current total revenue is 2926.35. Because these fast food restaurants belong to the same organization, a central decision-maker can simultaneously supervise all the operating units. Noting that the input shop size is a non-reallocatable variable, we assume that the central decision maker can reallocate the man-hour resources among these 20 fast-food restaurants to maximize the total revenue. The results from model (2) and (3) are displayed in Table 4. The total revenue is 3105.36.

The proposed neural network (15) is now employed to solve the bi-level model (4). Theorems 5.2 and 5.3 and Corollary 5.1 assure that the neurodynamic (15) converges to w^*. Figure 3 displays the transient behavior of state trajectories (x₁, y₁, y₂, y₃, y₄, y₅)  ^T based on the proposed neural network (15) for DMU 1 and DMU 4 with random initial points and Λ = 1. The results of the bi-level model (4) and the proposed neural network (15) are shown in Table 5. The total revenue is 3116.26 and increases by 3116.26/2926.35 - 1 =6.49% and 0.35% compared with the original total revenue and the total revenue in the Fang and Li’s model (2), respectively. As mentioned previously, in realistic problems, a cost of the inputs reallocation is incurred. The results show the minimum reallocation cost of the Fang and Li’s model (2) is equal to ξ^* = 1.08, while for the proposed bi-level CRA model (4) we get ξ^* = 0.98. Therefore, it is seen that the proposed model is more suitable in terms of the total revenue and the minimum reallocation cost. Table 6 provides a comparison of the two approaches in terms of CCR efficiency score. It can be seen that the proposed model not only has fewer efficient DUMs, but also has lower average efficiency than the Fang and Li’s model. So, the results of the proposed model are more consistent with reality.

OPEN IN VIEWER

Fig.3

Transient behaviors of (x₁, y₁, y₂, y₃, y₄, y₅)  ^T of the neurodynamic model (15) for (a) DMU 1 and (b) DMU 4 with the random initial vector points and Λ = 1 in Example 2.

Example 3.In this example, we analyze dataset consisting of 20 DMUs from [24, 27]. Two output variables and two input variables are considered. Table 7 lists these 20 DMUs with their inputs and output values. As in [24, 47], assume that the output vector price is p = (1, 0.1)  ^T . The current total revenue of 20 DMUs is 1 (1441.29) +0.1 (2033.18) =1644.61. We assume that the central decision-maker aims to reallocate current overall resources so as to maximize the total output revenue produced by all the DMUs. Assuming c ik - = c ik + = 0.5 for i = 1, 2 and k = 1, . . . , 20, to obtain the minimum cost of the inputs reallocation, we apply the Fang and Li’s model (2) and (3). The results are shown in Table 8. The total revenue after the resource reallocation is 1 (2108.21) +0.1 (2531.832) =2361.3932.