FREE SOFTWARE FOR DECISION ANALYSIS
A Software Package for Data Envelopment Models
Lidia Angulo Meza
Instituto de Ciências e Tecnologia, Universidade Veiga de Almeida, Rua Ibituruna 108, Maracanã,Rio de Janeiro, Brasil
Luiz Biondi Neto
Depto. de Engenharia Elétrica e de Telecomunicações – Universidade do Estado do Rio de Janeiro, Rua São Francisco
Xavier, 524, Bl. A, Sala 5036, Maracanã, Rio de Janeiro, Brasil
João Carlos Correia Baptista Soares de Mello
Depto. de Engenharia de Produção – Universidade Federal Fluminense, Rua Passo da Pátria, 156, São Domingos, Niterói,
Brasil
Eliane Gonçalves Gomes
Programa de Engenharia de Produção – Universidade Federal do Rio de Janeiro & Embrapa Monitoramento por Satélite,
Av. Dr. Júlio Soares de Arruda, 803, Parque São Quirino, Campinas, SP, Brasil
Pedro Henrique Gouvêa Coelho
Depto. de Engenharia Elétrica e de Telecomunicações – Universidade do Estado do Rio de Janeiro, Rua São Francisco
Xavier, 524, Bl. A, Sala 5036, Maracanã, Rio de Janeiro, Brasil
Keywords: Software, Data Envelopment Analysis.
Abstract: Data Envelopment Analysis is based on linear programming problems (LPP) in order to find the efficiency
of Decision Making Units (DMUs). This process can be computationally intense, as a LPP has to be run
for each unit. Besides, a typical DEA LPP has a large number of redundant constraints concerning the
inefficient DMUs. That results in degenerate LPPs and in some cases, multiple efficient solutions. The
developed work intends to to fill out a gap in current DEA software packages i.e. the lack of a piece of
software capable of producing full results in classic DEA models as well as the capability of using more
advanced DEA models. The software package interface as well as the models and solution algorithms were
implemented in Delphi. Both basic and advanced DEA models are allowed in the package. Besides the main
module that includes the DEA models, there is an additional module containing some models for decision
support such as the multicriteria model called Analytic Hierarchic Process (AHP). The developed piece of
software was coined as FSDA – Free Software for Decision Analysis.
1 INTRODUCTION
Data Envelopment Analysis (DEA) is an approach to
evaluate efficiency that uses Linear Programming
Problems (LPP) whose results assess the
performance of Decision Making Units (DMUs).
In recent years there has been increasi
ng interest
for DEA and its corresponding LPPs. Several real
case applications have led to a need for new
developments in the classic models, the CCR
(Charnes et. al. 1978) and BCC (Banker et al. 1984
models, in order to include new situations. Thus
several researchers have been aware to the results
yielded by the models in terms of efficiency indexes,
benchmarks and targets.
On the other hand, a LPP has to be solved for
each
DMU. So the task for efficiency evaluation can
207
Angulo Meza L., Biondi Neto L., Carlos Correia Baptista Soares de Mello J., Gonçalves Gomes E. and Henrique Gouvêa Coelho P. (2005).
FREE SOFTWARE FOR DECISION ANALYSIS - A Software Package for Data Envelopment Models.
In Proceedings of the Seventh International Conference on Enterprise Information Systems, pages 207-212
DOI: 10.5220/0002548802070212
Copyright
c
SciTePress
be hard and very time consuming without an
adequate specific piece of software, particularly for
a large number of DMUs. Several software packages
were developed so to minimize those problems.
However, in several situations, the results produced
by those packages either are not complete or are not
consistent to the ones produced by other pieces of
software for the same model. That leads to some
questions about the correctness of the computing
implementation of the model in those softwares.
That motivates the need for developing a reliable
software package yielding complete results and
covering new theoretical developments regarding
DEA models. Besides the capability to cover the
classic DEA models and producing complete results,
it also includes advanced models that were not
considered by other DEA software packages
(Angulo-Meza et al., 2003a). The current version of
the software package is presented in Portuguese
language and is called SLAD (Software Livre de
Apoio à Decisão) although a future release in
English is also under development.
The SLAD was written in Delphi 7.0 due mainly
to allow object Pascal coding for writing the
Simplex algorithm to solve LPPs and also to its
capability to deal with graphics.
The developed software package was shown to
be very useful for testing new models and has been
used in many papers written by the authors.
2 DATA ENVELOPMENT
ANALISYS
Data Envelopment Analysis (DEA) was developed
by Charnes et al. (1978) and is a methodology that
uses linear programming for the comparative
evaluation of DMUs efficiencies
The DEA purpose is to compare a certain
number of DMUs performing similar tasks and that
distinguishes themselves in the number of used
inputs and the number of produced outputs. There
are basically two classic DEA models: the Constant
Return Scale (CRS) model also known as CCR
(C
harnes, Cooper and Rhodes, 1978) and the
Variable Return Scale (VRS) model or BCC
(B
anker, Charnes and Cooper, 1984). The first
model considers constant scale returns and the
second one variable scale returns and does not
assume proportionality among inputs and outputs.
Each k
th
DMU, k = 1, ..., n, is considered to be a
production unity that uses n inputs x
ik
, i =1, …, r, to
produce m outputs y
jk
, j =1, …, s. The CCR model
described by (1) maximizes the ratio between a
linear combination of outputs and a linear
combination of inputs with the constraint that for
each DMU that ratio can not be greater than one. So
for a particular DMU o, h
o
is its efficiency; x
io
and
y
jo
are its inputs and outputs and v
i
and u
j
are the
calculated weights for the inputs and outputs.
jivu
nk
xv
yu
xv
yu
h
ij
r
i
iki
s
j
jkj
r
i
ioi
s
j
joj
o
, 0,
,...,1 ,1
subject to
max
1
1
1
1
=
=
=
=
=
=
(1)
After some mathematical manipulations, the
model can be rewritten, yielding in a Linear
Programming Problem (LPP) as shown in (2).
(2)
jivu
nkxvyu
xv
yuh
ij
s
j
r
i
ikijkj
r
i
ioi
s
j
jojo
, 0,
,...,1 , 0
1
subject to
max
11
1
1
=
=
=
∑∑
==
=
=
As a LPP is solved for each DMU, for n DMUs
n LPPs are solved, with r + s decision variables. The
model just presented is the basis for all other DEA
models.
Besides the efficiency index, DEA models yields
for each DMU the variables weights , benchmarks,
and targets for the inefficient DMUs. The last two
elements are determined from the values of the dual
variables i.e. by solving the dual LPPs or by the use
of the complement slack theorem. The set of all
those results defines what we call in this paper
complete results. In recent years, software packages
were developed due to the great interest and the
large number of applications using the DEA
approach. Those programs include mostly basic
models and were developed to avoid the effort of
running separately LPPs without the integration
provided by DEA packages software in order to get
the final evaluation. On the other hand, theoretical
developments have been made and are widely used.
ICEIS 2005 - ARTIFICIAL INTELLIGENCE AND DECISION SUPPORT SYSTEMS
208
For example, weights restrictions (Allen et al, 1997)
allow the inclusion of a priori information, i.e.
subjective aspects can be incorporated within DEA
models that are essentially very objective. Thus the
use of some advanced developments have been
essential for DEA analysis and some software
packages already include some advanced models.
However, in some cases different softwares
running the same model yielded different results or
results not following the model constraints which
make them unreliable. That also happened even for
the basic models. Most software packages show only
efficiency indexes and targets leaving out the
variable weights which might be useful in a deep
assessment of the DMUs and for aid in later
theoretical developments (Angulo-Meza e Lins,
2000).
Such problems motivated the authors to build a
package software in order to produce complete
results involving the basic models CCR and BCC
(input or output oriented, Cooper et al, 2000), with
open code access to check eventual problems or
discrepancies among results and the capability to
include models for new theoretical advanced
developments.
3 THE FSDA – FREE SOFTWARE
FOR DECISION ANALYSIS
A fundamental step for the development of a DEA
software is the setup and choice of the algorithm to
solve the LPPs associated with the problem.
The Simplex algorithm is very popular for
solving LPPs, so is the interior points algorithm
particularly for large scale LPPs. The FSDA uses
the Simplex algorithm for the solution of linear
programming problems.
The Simplex algorithm was created by Dantzig
and published in 1948. Briefly, according to Dantzig
(1963) a linear programming problem can be
reduced to a combinatory problem in such a way that
the method for searching the optimum solution is
performed by testing a sequence of combinations in
which the value of the objective function is
incremented gradually. An optimum solution is
considered to be reached after a certain number of
iterations not greater than the number of constraints
or the number of variables whatever is the largest.
The FSDA uses Kuenzi et al ‘s (Kuenzi et al,
1971) approach that includes a subroutine to avoid
degenerating problems, a common problem in DEA
models due to the typical structure of the involved
LPPs that present a large number of redundant
constraints for the inefficient DMUs. In many cases
that leads to multiple optimal solutions.
Matrices and vectors are used to separate the
values of the coefficients corresponding to the basic
variables (variables that are part of the solution) and
to the non basic variables ( variables which are not
part of the solution and whose values are set to
zero). Moreover, two lists are kept containing those
two variables which are updated at each algorithm
iteration.
The mentioned procedure has two phases for
evaluating the solution of a LPP. The first one
searches an initial basic solution. The second starts
from the initial basic solution found in part one.
Both phases have three steps. The first step
determines the value of a secondary objective
function that will be used in the other two steps and
also a variable that will enter the base.
The second step locates the pivot element taking
into consideration a possible degeneration in the
corresponding LPP. If the pivot element can not be
found a message is sent and the search ends.
The last step updates the matrices in order to
change the set of basic and non basic variables.
There are three possible outcomes for a given
LPP: an optimal solution is achieved, no solution is
achieved, in those cases the LPP is said to be non
limited or no initial vector is possible which means
the LPP is not feasible.
The algorithm used in the FSDA software is now
presented in detail:
Phase 1: Determine an initial
feasible basic solution and check if
that solution is the origin, otherwise
search one.
Step 1: Search a variable to enter
the base of the initial feasible
solution and evaluate a secondary
objective function.
If the current solution is
feasible go to phase 2, otherwise if
there is a variable to be sent into
the base go to step 2, otherwise the
LPP is non feasible and the program
ends and a message is sent to the
user.
Step 2: Locate pivot element if
input go to step 3, otherwise END,
LPP not feasible.
Phase 2: There is an initial basic
solution go to step 1.
Step 1: Search a variable to be in
the base and evaluate the secundary
objective function.
If the current solution is optimum
then END, otherwise if there is a
variable to be in the base go to step
2, otherwise LPP is non limited.
FREE SOFTWARE FOR DECISION ANALYSIS: A Software Package for Data Envelopment Models
209
Step 2: Locate pivot element.
Step 3: Update the sets of basic
and non basic variables and go to
step 1.
It should be stressed that in basic DEA models (CCR
or BCC, whatever orientation) at least one solution
can always be found with a possibility of an infinite
number of optimum solutions which is quite
frequent. In that case, only the first optimum
solution is shown to the user.
In the case of models with restrictions to the
weights, there is a possibility of appearing non
feasible LPPs once the additional constraints can
turn the LPP originally presenting an optimum
solution to a non feasible LPP. In that cases, a
message is sent and the user has the choice of
changing the restriction and repeat the process.
The method for solving the LPPs is unique, what
changes is the format of the LPPs, once a different
LPP is performed for each DEA model. The data
input have to be put in the proper format in a matrix
structure depending on the used model. The data
ordering process in the referred matrix in the
appropriate format is the most difficult part in the
software implementation.
3.1 Software Description
The FSDA( SLAD in Portuguese version) opening
window is shown in Figure 1 and was developed for
Windows platform with Delphi 7.0. It is capable for
dealing with 150 DMUs and 20 inputs or outputs
variables.
Although for other research areas 150 DMUs
might be insufficient for DEA applications that
value is able to deal with large scale situations since
in the literature there are few applications dealing
with more than a 100 DMUs. In most applications
10 variables are sufficient.
The software package allows the data input to be
entered in two ways: directly inside the program
using a table with the choice of the number of
DMUs and variables, and by the use of a txt file
having the data that are loaded to the mentioned
table shown in figure 2. Figure 2 also shows the
possible choices of basic models (CCR or BCC) and
orientation (input or output) covering the basic and
most used models.
Moreover, advanced options are also included in
the software as one of the objectives of the FSDA
package is to allow new DEA developments that
may be chosen along with the model and its
orientation. The user can also the choice of using
weight restrictions, or considering data uncertainty.
The advanced option of weight restrictions leads
the user to an additional window indicating the
number of restrictions to be included in the chosen
model.
The choice of uncertainty in some or all
variables also leads the user to another window,
showing the data input. A DEA analysis with
uncertainties uses variation intervals for some or all
variables of analysis.
Results for any model, advanced or not, are
presented in an additional window as illustrated in
figure 3. That window shows the efficiency indexes
for all DMUs. Besides, additional options are
presented to show other results: inverted frontier,
that expand the results window to include the
efficiency index in the inverted frontier and the
composed index (standard and inverted efficiencies);
the variables weights; the benchmarks of all DMUs
(efficients and inefficients) and the targets for the
DMUs including the slacks and the levels that the
variables have to reach for turning the DMUs
efficients
Figure 1: FSDA (SLAD) Opening Window
ICEIS 2005 - ARTIFICIAL INTELLIGENCE AND DECISION SUPPORT SYSTEMS
210
Figure 2: Options window of FSDA (SLAD).
Figure 3: Results window of FSDA (SLAD).
It should be noted that the results window just
shows the efficiencies of the DMUs whereas the
other results are shown only when asked for by
clicking the appropriate icons on the same window.
That was done for the sake of easing the
visualization of the results once the presentation of
the complete results in one window might be
difficult to interpret the results particularly for a
large number of variables and DMUs.
In the data input window there is another option,
not yet mentioned, that allows the use of
multicriteria models. By choosing that option the
window changes colour to indicate the user the
substitution of the DEA approach for the
multicriteria approach. As this module is under
development, the only available method is the
Analytic Hierarquic Process (AHP) according to
Clímaco et al. (1996), but other methods will be
include in due time.
4 CONCLUSIONS
The growing interest in recent years of DEA
approach for the evaluation of efficiency and the
theoretical developments due to real world
applications have indicated the need of a reliable
software package that involve jointly a friendly user
interface, yielding reliable, consistent and complete
results and having the capability to work with more
advanced models. There are DEA software
packages but the lack of complete and reliable
results in those softwares led to the development of a
FREE SOFTWARE FOR DECISION ANALYSIS: A Software Package for Data Envelopment Models
211
software package that met the demands of the
authors of this paper.
The FSDA (SLAD) was written in Delphi 7.0
and uses the Simplex algorithm to solve the LPPs
required by DEA. The software includes, besides the
classic models, advanced models such as DEA
models with weight restrictions as well as recent
models developed by the authors such as inverted
frontiers and data uncertainties.
The complete results produced by the software
are suitable for a deep analysis of the DMUs and
could also serve as a basis for the development of
new theoretical models.
The performance of the FSDA in large scale
problems has been satisfactory, e. g. the time
response for problems involving 80 DMUs and 7
variables was less than one second.
A great motivation of the FSDA for the authors
is the possibility of including other models in the
package that has been very useful for the authors in
their new developments and in the testing of new
models.
Finally, new models developed by the authors
are under way to be considered in the FSDA such as
the DEA-GSZ model (Lins et al., 2003), as well as
the expansion of the multicriteria module.
REFERENCES
Allen, R., Athanassopoulus, A., Dyson, R.G. et al., 1997.
Weights restrictions and Value judgements in Data
Envelopment Analysis: Evolution, Development and
Future Directions. Annals of Operations Research, 73,
13-34.
Angulo-Meza, L, Lins, M.P.E., 2000. Data Envelopment
Analysis (DEA) using the Frontier Analyst. Pesquisa
Operacional, 19 (2), 287-293. (in Portuguese)
Angulo-Meza, L., Gomes, E.G., Soares de Mello,
J.C.C.B., Biondi Neto, L., 2003b. DEA Border Having
Double Envelopment in the Study of the Evolution of
the Rio-São Paulo Shuttle Service.In: Anais do XVII
Congresso de Pesquisa e Ensino em Transportes, Rio
de Janeiro, RJ,Novembro. (in Portuguese)
Angulo-Meza, L.A., Biondi Neto, L., Soares de Mello,
J.C.C.B., Gomes, E.G., 2003a. SLAD - Integrated
System for Decision Support: A Computational
Implementation of Data Envelopment Analysis
Models. In I Encontro Regional da Sociedade
Brasileira de Pesquisa Operacional, Caderno de
Resumos, 24, Niterói, RJ, Brazil. (abstract in
Portuguese)
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.
Climaco, J.,Antunes, C.H., Alves, M.J.G., 1996.
Multicriteria Support to Decision. Faculdade de
Economia da Universidade de Coimbra e INESC. (in
Portuguese)
Cooper, W.W., Seiford, L.M., Tone, K., 2000. Data
Envelopment Analysis: A Comprehensive Text with
Models, Applications, References and DEA-Solver
Software. Kluwer Academic Publishers, USA.
Dantzig, G.B., 1963. Linear Programming and
Extensions, Princeton, N.J.: Princeton Univesity Press.
Kuenzi, H.P., Tzschach, H.G., Zehnder, C.A., 1971.
Numerical Methods of Mathematical Optimization,
Academic Press, New York.
Lins, M.P.E., Gomes, E.G, Soares de Mello, J.C.C.B.,
Soares de Mello, A.J.R., 2003. Olympic ranking based
on a Zero Sum Gains DEA model. European Journal
of Operational Research, 148 (2), 312-322.
ICEIS 2005 - ARTIFICIAL INTELLIGENCE AND DECISION SUPPORT SYSTEMS
212