The Optimal Working Solutions for The Specific Parts of The Financial Service Systems

Vladimir Simovic, Zlatko Golubic

University of Zagreb, Police College,

Avenija Gojka Suska 1, HR - 10000 Zagreb

The Republic of Croatia

Tel: +385 1 239 1341; Fax: +385 1 239 1415

E-mail:

Miljenko Crnjac

University of Osijek, Economic Faculty in Osijek

Gajev Trg 7, HR - 31000 Osijek

The Republic of Croatia

Tel: +385 31 211 605, +385 31 224 400/43; Fax: +385 31 211 604

E-mail:

ABSTRACT:Objective of this work is to explain the OR modelling concept that was analytically used for the organisation of specific parts of the financial service systems. Solution for that OR modelling concept was the specific application of procedure well known as the transportation simplex method. The same concept can be used as good analytical solution not only for production and optimal distribution of usual financial documentation, but also as a part of production and distribution service for the electronic payment duties (for Certifying Authorities, Third Trust Party, etc.) needed for applications of digital signature or similar procedures. This analytical work was done for development of the financial service systems of the various connected parts of the financial and governmental institutions of the Republic of Croatia. These problems are connected also with the development of the financial service systems of the electronic markets.

Keywords: applied transportation simplex method, financial service systems

1INTRODUCTION

The conventional Operations Research (OR) goal, optimal decision making, can be adequate for achieving the best system design and developing information on behaviour of a specific parts for a whole system of the financial analytical services. This work is short explanation of the main OR concepts and results that are accomplished during the processes of analysis and application of specific linear programming solutions, which are mainly based on a streamlined simplex method for the transportation problem. Also here are some important details about “the applied analytical algorithm of a streamlined transportation simplex method” and useful experiences about “the analytical application of a streamlined transportation simplex method”. An illustrative example is presented at the end of this article.

2A STREAMLINED TRANSPORTATION SIMPLEX METHOD AND PROBLEM

2.1 Insight in the analytical application of a streamlined transportation simplex method

The analytical application of a streamlined transportation simplex method emphasizes the wide applicability of specific linear programming methods and solutions in the world of the financial analytical services. Transportation problem, as one specific type of linear programming problems, received this name because a lot of its applications involve determining how to optimally transport goods or services, but some important applications actually have nothing to do with transportation directly. It is well known that the assignment problem is another type of linear programming problem and it can be viewed as a special type of transportation problem. Also the transportation and the assignment problem are actually special cases of the minimum cost flow problem. Although applications of the transportation and the assignment problems usually requires a very large number of coefficients in constraints (and variables), most of the coefficients in the constraints are zeros, and other nonzero coefficients appear in a distinctive pattern. These special structures (the coefficients in the constraints are zeros, and other nonzero coefficients appear in a distinctive pattern) of the problem have result that it has been possible to relatively easy develop special streamlined algorithms. This streamlined procedure can be referred as the transportation simplex method.

2.2 Terminology and notation used with mathematically based model formulation

The following mathematically based model formulation with extension of standard terminology and notation is usuallyused:

general transportation
problem = / the general model for the transportation problem is one specific type of linear programming problems with lot of applications involving determining how to optimally transport goods or services, and which use less specific terms for components then the prototype example
m sources i = / any group of supply centres i (e.g., various kinds of the financial analytical teams) from which a supply of si units (any supply of commodity: goods or services; e.g., various financial analytical services) are distributed with minimal total distribution cost (e.g., sums in various currencies, like HRK) to any group of receiving centres, where i = 1, 2, … , m
n destinations j = / any group of receiving centres j (e.g., various complexity of the financial analytical jobs) at which a demand of dj units (any demand for commodity: goods or services; e.g., various financial analytical services) are received with minimal total distribution cost (e.g., sums in various currencies, like HRK) from any group of supply centres, where j = 1, 2, … , n
distributed unit cost
cij = / denotes the cost per unit distributed, with a basic assumption that the cost of distributing units from source i to destination j is directly proportional to the number distributed
z = / total distribution cost
xij = / number (integer value) of distributed units (e.g., financial analytical services) from source i to destination j, where
(i = 1, 2, … , m; j = 1, 2, … , n)
integer solution property = / for a transportation problem where every si and djhave an integer value, all the basic variables (allocations) in every basic feasible (BF) solution (including an optimal one) also have integer values
feasible solution property
= / a sufficient and necessary condition for a transportation problem to have any feasible solution is that .
system must be in balance
condition = / the constraints require that , or total supply must equal the total demand (where either si or dj represents a bound rather then exact requirement, and where a factitious (dummy) source or destination can be usefully used)
liner programming
formulation of the
transportation problem
solution = / minimize , subject to:
for i = 1, 2, … , m, for j = 1, 2, … , n,
and , for all i and j.
prototype example = / an illustrative example, with real integer values given for coefficients in constraints (and variables), which have practical solution (e.g., for the applied analytical algorithm of a streamlined transportation simplex method) and represents useful experience (e.g., about the analytical application of a streamlined transportation simplex method)
ui = / multiple of original row i that has been (directly or indirectly) subtracted from original row 0 by the simplex method during all iterations leading to the current simplex matrix (table)
vj = / multiple of original row m+j that has been (directly or indirectly) subtracted from original row 0 by the simplex method during all iterations leading to the current simplex matrix (table)

Follows (an algorithmically) explanation how in general with (un-streamlined) simplex method the transportation problem can be set up in tabular (matrix) form. First, after constructing the table of constraint coefficients, converting the objective function to maximization form, and using “Big M method” to introduce artificial variables z1, z2, … , zm+n into the m+n respective equality constraints. Because of that we are introducing the matrix (cost and requirements table) of constraint coefficients, where aij is the coefficient of the jth variable in the ith functional constraint, where coefficient entries equal to zero are indicated by leaving their column partitions of the matrix blank. The only one adjustment has to be made before the first iteration of the simplex method is to algebraically eliminate the nonzero coefficients of the initial (artificial) basic variables in row 0. After any subsequent iteration, row 0 then would have the original simplex matrix (table) form when simplex method is applied to transportation problem, where uiand vj are dual variables. Also, if xijis a non-basic variable, cij - ui - vj is interpreted as the rate at which Z (as a total distribution cost) will change as xijis increased.

Consequently, the transportation simplex method obtains the same information in much simpler ways. No artificial variables are needed for constructing an initial BF solution, because a simple and convenient procedure with several variations is available. By calculating the current values of uiand vj directly, the current row 0 can be obtained without using any other row. Each basic variable must have a coefficient of zero in row 0, the current values of uiand vj are obtained by solving the set of equations cij - ui - vj = 0 for each i and j such that xijis a basic variable, which can be done in straightforward way. The leaving basic variable can be identified in a simpler way without explicitly using the coefficients of the entering basic variable. Special structure of the problem makes it easy to see how the solution must change as the entering basic variable is increased. The resulting new BF solution can be obtained immediately without any algebraic manipulation on the row of the simplex matrix (table). Almost the entire simplex matrix and the maintaining work can be eliminated. Convention is that, since all non-basic variables are automatically zero, the current BF solution is fully identified by recording just the values of the basic variables. Streamlined transportation simplex method efficiency is better then the simplex is. For a transportation problem with m sources and n destinations the simplex matrix (table) has m+n+1 rows and (m+1) (n+1) columns (excluding all left to the xijcolumns), but streamlined transportation simplex matrix (table) has only m rows and n columns (excluding the two extra informational rows andcolumns). It is very significant fact for solving medium (m=10 and n=100) and larger transportation problems.

2.3 The applied analytical algorithm of a streamlined transportation simplex method

The applied analytical algorithm of a streamlined transportation simplex method has three main steps:

-Initialisation

-Optimality test

-Iteration

As a first main step, initialisation is process of construction an initial BF solution by the two well-known alternative criteria and one comparison procedure. A first alternative criterion is “the Vogel’s Approximation Method” (VAM), and second is “the Russell’s Approximation Method” (RAM).

(Remark: There is also a third alternative criterion “the Northwest Corner Rule” (NCR), which is quick and easy, but it pays no attention to unit costs cij, and to find a good initial BF solution, consequently the NCR solutions are far for optimal.) As a first alternative criterion the VAM is very popular, hands can easily implement it. The VAM pays attention to unit costs cij effectively, because the difference represents the minimum extra unit cost incurred by failing to make an allocation to the cell having the smallest unit cost in that row or column. A second alternative criterion the RAM is another really excellent criterion, which can bee easily implemented by a computer, and which has usually better solutions for large problems then the VAM. Also, the RAM is patterned directly after first step for the transportation simplex method, and mainly simplifies the overall computer code. A comparison procedure is two phase process. A first phase is process of applying both alternative criterions (VAM and RAM). A second phase is decision process, in which decision must be to use the alternative criterion with better results. Go to a second step, the optimality test.

As a second main step, optimality test is process based on fact that “a BF solution is optimal if and only if cij - ui - vj 0 for every (i, j) such that xij is non-basic”. During this process derivation of uiand vj must be done by selecting the row having the largest number of allocations, settings its ui = 0, and then solving the set of equations cij = ui + vjfor each (i, j) such that xij is basic. If cij - ui - vj 0 for every (i, j) such that xij is non-basic, then the current solution is optimal, so stop. Otherwise go to iteration step.

As a third main step for this streamlined version, iteration is process of three phases. In first phase iteration must determine an entering basic variable, in second leaving basic variable, and then in third phase identify the resulting new BF solution. During first phase, since cij - ui - vjrepresents the rate at which the objective function will change as the non-basic variable xij is increased, the entering basic variable must have a negative cij - ui - vjvalue to decrease the total cost Z. Thus to chose between the candidates, select the one having the larger (in absolute terms) negative value of cij - ui - vjto be the entering basic variable. During second phase, increasing the entering basic variable from zero sets off a chain reaction of compensating changes in other basic allocations (variables), in order to continue satisfying the supply and demand constraints. The first basic variable to be decreased to zero then becomes the leaving basic variable. In the case of a tie for the donor cell having the smallest allocation, any one can be chosen arbitrary to provide the leaving basic variable. During last-third phase, the new BF solution is identified simply by adding the value of the leaving basic variable (before any change) to the allocation for each recipient cell and subtracting this same amount from the allocation for each donor cell.

Shortly, these three phases of iteration are:

- 1st determine the entering basic variable: Select the non-basic variable xijhaving the largest
(in absolute terms) negative value of cij - ui - vj.

- 2nd determine the leaving basic variable: Identify the chain reaction required to retain feasibility
when the entering basic variable is increased. From the donor cells, select the basic variable
having the smallest value.

- 3rd determine the new BF solution: Add the value of the leaving basic variable to the
allocation for each recipient cell. Subtract this value from the allocation for each donor cell.

This way of solving the applied analytical algorithm of a streamlined transportation simplex method was also based on the computer-based algorithm with interactive modelling design that was prepared with the program «MathProg», which is McGraw-Hill modular developed program for various analytical solutions (see pp. 947-950 and accompanied disks in [6]). That design can be controlled with modular analytical programs solutions (designed in Fortran’77, Fortran’90 and Lahey language, and supported with C++ source code for: DOS, QuickWin, Windows’95, Windows’98, Xwindow’X11 and NT Windows) taken from Springer-Verlag Compact Disk (see pp. 595-608 and accompanied CD in [4]).

3ILLUSTRATIVE EXAMPLE

3.1 The optimal working solutions for the financial analytical service system

In Croatian case, the financial analytical service system conventionally looks like a large “agency” that administers distribution of various financial analytical services throughout the whole Intranet or secure part of Internet in Croatia. Sometimes that service must be purchased from various and different types of financial analytical teams for various analytical job destinations, which have a different level of job complexity, also. For example, suppose that the sources are in fact five different types of financial analytical teams (m = 5), and that we have six various customers or analytical job destinations (n = 6) that have also a significantly different level of complexity of their financial analytical jobs. This large “financial analytical service agency” gives various financial analytical services from various sources to various customers at different analytical job destinations; throughout the Intranet or Internet, or whole WAN (wide area network). Also, suppose that it is possible to supply any of these six financial analytical service destinations from any of five sources, with the exception that no provision has been made to supply 3rd and 4th analytical job destination with 4th and 5th team service (or specific analytical product). Reason can be typical financial analytical service incompatibility with large complexity of the specific analytical job at destination. The cost of supplying service is different because it depends upon both the source of the analytical service (type of a team) and the destination of the specific financial analytical job (level of job complexity). Different values for the variable cost per one hour of analytical work (here are given in HRK) for each combination of a team type and level of job complexity are given in Table 1.

Table 1. Data for the illustrative example of the financial analytical system

With five sources (m=5) and six destinations (n=6)

Cost Per Unit Distributed
(one hour of analytical work in HRK)
Destination (analytical job)
Source Team / 1 / 2 / 3 / 4 / 5 / 6 / Supply
1 / 130 / 140 / 60 / 90 / 90 / 100 / 6
2 / 70 / 80 / 40 / 50 / 60 / 70 / 3
3 / 60 / 80 / 30 / 50 / 40 / 50 / 2
4 / 100 / 100 / - / - / 60 / 70 / 2
5 / 100 / 90 / - / - / 50 / 50 / 3
Needed / 7 / 3 / 2 / 0 / 0 / 0 / Minimum
Requested / 7 / 5 / 2 /  / 1 / 2 / Maximum

The analytical management is now faced with the problem of how to allocate the available analytical service during the (suppose) whole analytical day, with these minimums of needs and also these maximums requests. The amounts of available service from these five types of analytical teams are given in the rightmost (supply) column of Table 1. The analytical management is committed to provide a certain minimum of service amount to meet the essential need of each analytical job (destination), but with the exception of 4th, 5th and 6th job, which have been almost independent from outsourcing of analytical service (as shown, zeros in the minimum needed row of the table). Also, requested maximum row indicates that 1st and 3rd job needs no more than minimum service amount, but 2nd job needs 2 hours of analytical work more, 5th job as much as 1 hour more, 6th job up to 2 hours more, and 4th job needs as much at it can get (). Management wishes to allocate all the available service from the five source analytical teams to the six analytical jobs in such a way as to at least meet the essential needs of each analytical job while minimising the total cost to the whole “financial analytical service agency”. Now, formulation of proper analytical form for Table 1 is very important analytical step. The only one difficulty is that it is not quite clear what the demands at the destination should be. The service amount to be reached at each destination (except 1st and 3rd job) actually represents a decision variable, with both a lower bound (minimum) and an upper bound (maximum). This upper bound is the service amount requested unless the request exceeds the total supply remaining after the minimum needs of the other financial analytical jobs are met, in which case this remaining supply becomes the upper bound. Thus insatiably thirsty 4th analytical job has an upper bound of: