MODULY EXCELU PRO VÍCEKRITERIÁLNÍ HODNOCENÍ

Spreadsheet Modules for Multicriterial Modeling

mODULY eXCELU PRO VÍCEKRITERIáLNí HODNOCENí

RNDr. Helena Brožová, CSc, Dr. Ing. Tomáš Šubrt, Milan Houška

Adresa autorů:

Katedra operační a systémové analýzy, PEF ČZU

Praha 6, Suchdol

Anotace:

Článek úzce souvisí s širší problematikou matematického modelování v soudobých tabulkových procesorech. Autoři se již několik let zabývají tvorbou doplňkových (Add In) modulů pro Excel zaměřených na řešení úloh operačního výzkumu.

K dnešnímu dni jsou hotovy moduly pro výpočet a analýzu výsledků lineárního optimalizačního modelu, optimalizační dopravní model a celá řada modulů z oblasti vícekriteriálního rozhodování. Se čtyřmi z těchto modulů s tématikou jak vícekriteriální optimalizace tak vícekriteriálního hodnocení variant seznamuje následující text.

Summary:

The process of model creating and solving seems to have large variability, however it includes some common basic steps. Our paper is oriented on possibilities of using spreadsheet system Excel and its programming language for this process.

Till today we have finished and presented modules for Linear Programming and Transportation Problems. On the field of MCDM we would like to present some modules for Multicriterial Programming as well as for Multicriterial Evaluation of Alternatives based on spreadsheet interactive modeling approach mentioned above.

Klíčová slova:

Tabulkový procesor, doplněk, matematické modelování, tabulkový model, vícekriteriální rozhodování, vícekriteriální programování, cílové programování, vícekriteriální hodnocení variant.

Keywords:

Spreadsheet, Add In module, mathematical modeling, spreadsheet table model, multi criteria decision making, multi criteria programming, goal programming, multi attribute evaluation of alternatives.

Introduction

The aim of the following article is to present results of our work on Microsoft Excel modules for multi criteria decision making (modules WGPKOSA, MCAKOSA, PRIAMKOSA and ALOKOSA). These modules together with LINKOSA, SUBKOSA and DUMKOSA belong to the complex of modules for mathematical methods of operations research.

The whole system is based on elementary knowledge of mathematical modeling on spreadsheets. Theoretical principles of model constructions on a spreadsheet were already published in [2,7] and so some conclusions in this article are based on them.

Spreadsheet modeling

A large number of operations research problems are based on matrix oriented mathematical models. Therefore using spreadsheet software products for such types of models seems to be very effective. New spreadsheets have defined hundreds of mathematical functions and a large number of supporting tools for iteration algorithms application (for example Goal Seek or Solver in Excel). Thanks to an universal object oriented programming language Visual Basic for Application, good database support and perfect communication with other windows applications, the process of creating models in this environment seems to be very effective and simple. In accordance with new results on the field of spreadsheet table modeling and with many theoretical research work we are convinced that mathematical modeling on spreadsheet is a very perspective trend.

Therefore, after long experiences with using Excel, Solver and other standard spreadsheet modules for solving mathematical programming problems, we have decided, together with our colleagues from other universities, to create our own system of operations research modules named ORKOSA (KOSA is the abbreviation of the name of our department in Czech) .

Spreadsheet table model

Useful system of data, functions and algorithms constructed in spreadsheet would be defined as a spreadsheet table model. Such model includes as well features of mathematical model as individual features based on its software background. Model elements are represented by spreadsheet cells or ranges and system relations by a great number of formulas and functions. Such model form with special modules for its recalculation and solving provides to every user a large variety of model experiments and model result analysis mostly regardless of mathematical base of the solved problem. Generally it is possible to comprehend a spreadsheet table model as a tool for simplification of model quantification, calculation and result analysis.

Spreadsheet table models with fixed parameters

This model class supposes that all model parameters (for example size or dimension) are predefined in workbook and cannot be modified during model quantification. This models are solvable directly by using spreadsheet formulas or using special module which contents iteration methods.

Spreadsheet table models with variable parameters

Each model from this class is created by a special module individually according to the type of the solved problem. Every module sets all parameters and automatically constructs and prepares the model for quantification. The parameters cannot be modified during following model quantification and calculation. Also this model class can be divided into two groups as above (models solvable using spreadsheet formulas and models solvable using special module).

Structure of the System ORKOSA

In this time the system ORKOSA includes seven completed modules: Linkosa - linear programming with bothsides variable bounds, Subkosa - analysis of linear model suboptimal solutions, Dumkosa - optimization of two dimensional transportation problems, WGPkosa - weighted goal programming, Mcakosa - multi attribute decision making methods, Priamkosa - heuristic exploration of the discrete set of alternatives and Alokosa - application of method ALOP as described later in this text. These modules are applicable on spreadsheet table models with variable parameters solvable by iteration methods only. All of them operate according to world standard, contain standard and widely used mathematical methods and all their inputs and outputs are provided only using a standard sheet in Excel. All modules communicate via input dialog boxes (mostly with cells and arrays addresses of model components). They are constructed as Add In Tools (files translated to the type of *.XLA) for Excel and their use corresponds with all other standard Excel Add Ins.

WGPkosa

WGPkosa is a tool for solving the weighted goal programming model. The solution found by this module minimizes deviations between the achievement of the goals and their aspiration levels according to their weights and absolute values. The mathematical model is following:

s. t.

where x is vector of variable n is vector of underachievement variables p is vector of overachievement variables u and v are vectors of their weights C is matrix of cost coefficients of objectives t is vector of target values of objectives A is matrix of constraints coefficients b is vector of right hand side d is vector of lower bounds of variables h is vector of upper bounds of variables

The module WGPkosa assumes all input data in one worksheet in the form as in Figure 1. The optimal solution is found using revised simplex method. WGPkosa includes a postoptimization analysis, too. It has four type of answer sheets - Optimal solution includes optimal values of each variables, deviations from target values and final values of each objective, Transformed matrixALFAincludes vectors B-1a,Sensitivity analysis of b and t and Sensitivity analysis of u and v include intervals of solution stability. Analysis of u and v is really important because all compromise solutions can be obtained by changing their values.

Figure 1: WGPkosa - Recommended layout of linear multi objective model on a spreadsheet and WGPkosa Input dialog box.

Alokosa

Alokosa (Aspiration Levels Oriented program) is an interactive procedure for multiobjective linear programming problems, where the decision space is determined by linear constraints and linear objective functions.

The decision maker states aspiration levels for each criteria value. There are three possibilities for his aspiration level values. The problem can have a unique nondominated solution, or can be feasible or infeasible. In case of nondominated problem solution the module Alokosa calculates all objective function and variable values. In case of feasible problem, the module offers to the decision maker (user) proposed changes of his aspiration levels by which a nondominated solution is obtained in the next step. In case of infeasible problem the module Alokosa offers the decision maker necessary changes in his aspiration levels by which the nearest nondominated solution can be found.

All outputs of this module are in the form of interactive spreadsheet and so the user can go back to every partial solution, change his aspiration levels and begin from this point with another solving process.

The module Alokosa works in following steps:

1. The nadir and ideal values of criteria functions of the “model A” are found.

2. The nadir criteria values are stored as basal (first) aspiration levels. Consequently the proposed changes of these levels by which the nondominated solution can be found are calculated. These proposed changes are denoted by vector p in the “model B”.

3. Individual aspiration levels are inputed (proposed changes from last step can be accepted or not) and the model B is calculated with these levels once again. In case of value v > 0 the problem is feasible and new proposed changes (vector p) is calculated. In case of v = 0 the nondominated solution is obtained (p = O). In case of no feasible solution exists the “model C” is solved and the necessary changes of last aspiration levels are denoted by difference p - n.

Alokosa - model A	where x is vector of variables A is matrix of constraints coefficients b is vector of right hand side d is vector of lower bounds of variables h is vector of upper bounds of variables z is vector of objective function values C is matrix of cost coefficients of objectives
Alokosa - model B	where x ,A, b, d, h, C see “model A” p = (pi) is vector of aspiration levels overachievement y is vector of criteria aspiration levels v is subsidiary objective function is optimal value of i-th objective function of the “model A” k is number of objective functions
Alokosa - model C	where x ,A, b, d, h, C see “model A” p, pi, y, ,k see “model B” n = (ni) is vector of aspiration levels underachievement

Both recommended layout of the model on a spreadsheet and input dialog boxes are very similar to WGPkosa models.

PRIAMKosa

PRIAMKosa is a procedure for multicriteria decision problems with the discrete set of decision alternatives. Principally it is based on former program (method) named PRIAM - “Programme utilisant lintelligence Artificielle en Multicriterie” [5]. The method PRIAM relies on heuristic exploration of the alternative set. The decision maker chooses a direction along which the procedure progresses. The heuristic information is the number of alternatives which remain feasible at the satisfaction level.

This procedure automatically constructs a decision tree, where the root of the tree represents nadir aspiration levels of all criteria and branches of the tree represent a path of tentative nodes. Every tentative node contains user defined aspiration levels and a set of acceptable alternatives. In case of there is only one acceptable alternative, the user obtains a nondominated one. In case of there is more than one acceptable alternative, the user can change his aspiration levels according to the number of acceptable alternatives. In case of the set of acceptable alternative is empty, the user must choose the nearest one by solving problem:

where k is number of criteria is the optimal value of i-th objective zi(x) is the i-th criterion value of current alternative X is the discrete set of decision alternatives yi(s) is the current i-th aspiration level (in s- th step)

If the decision maker doesnt want to return to the current node he can mark it as imperative one and this node is eliminated from the decision tree.

MCAKosa

At present time the module MCAKosa includes four basic methods of multi attribute evaluation of alternatives: Weighted Sum Method, method TOPSIS, ORESTE and ELECTRE I. Necessary input data are: decision matrix and type of attributes. Input data layout are shown in Figure 4.

Figure 4: MCAKosa - Recommended layout of input data

The decision maker can solve each problem consequently using all included methods. New method implementation doesnt need any changes in input boxes. It is very easy to compare the results of all methods together, because all their outputs (excluding method ELECTRE I because its output provides another type of information) could be stored on the only one result sheet. Another possibility is to create individual sheets with some more analytical information according to the character of currently used method. Figure 5 illustrates a solution of multi attributes evaluation of alternatives by three methods. According to the methods character there are presented global evaluation of every alternative and the alternative ordering.

Figure 5: MCAKosa - Example of a Results Sheet

Conclusion

In this time the authors have some experiences with modeling in Windows oriented software especially in Excel and with making modules for various types of models in Visual Basic for Applications. The idea of spreadsheet table models with modules for their solving seems to be a very perspective way for Operations Research applications in theory and practice as well. Using similar tools is very user friendly and their computational possibilities are very powerful.

References

1. Brožová, H., Marangon, F.: Uno strumento informatico in ambiente MS Excel per lanalisi a molti objectivi. La gestione delle risorse agro-ambientali, working paper University of Udine, 1997.

2. Brožová, H., Šubrt, T.: System of Operations Resarch Modules for Excel In: Proceedings of the Mathematical Methods in Economics Symposium, VŠB-TU Ostrava, 1997.

3. Cohon, J.L., Multiobjective Programming and Planning, Academic Press, New York San Francisco London, 1978.

4. Hwang, C.L.,: Multiple Attribute Decision Making, Springer Verlag, Berlin Heidelberg New York, 1981

5. Fiala, P.: Problem Solving Methods in Multicriteria analysis, Diskusionsbeitrag Nr. 181, Feruniversitaet Hagen, 1991

6. Gigch, J.: System design modeling and metamodeling, Plenum Press, New York, 1991.

7. Šubrt, T., Brožová, H.: Modeling and Metamodeling in MS Windows In: Proceedings of the MME95 Symposium, VŠB-TU Ostrava,1995.