14 "Portfolio" Problem,
Optimal Investment of Resources

1 Introduction

The previous examples illustrated competition and inspection processes in economical, social and ecological problems. Here the optimal investment of available resources is considered. Investment problems depend on the nature of resources to be invested. An important part of any investment problem is a proper definition of utility functions that determine the profit-to-risk relation. Here we consider an illustrative example how to invest some fixed capital in Certificates of Deposit (CD) and Stocks.

The portfolio problem is to maximize the average utility of a wealth. That is obtained by optimal distribution of available capital between different objects with uncertain parameters [Mockus et al., 1997]. Denote by $x_i$ the part of the capital invested into an object $i$. The returned wealth is $y_i=c_i x_i$. Here $c_i=1+\alpha_i$ and $\alpha_i>0$ is an interest rate. Denote by $p_i=1-q_i$ the reliability of investment. Here $q_i$ is the insolvency probability. $u(y)$ is the utility the wealth $y$. Denote by $U(x)$ the expected utility function. $U(x)$ depends on the capital distribution $x=(x_i,...,x_n), \ \sum_i=1,\ x_i \ge 0$. If $y$ is continuous, the expected utility function

$$\begin{eqnarray} U(x)={\bf E} u(y) = \int_0^{\infty} u(y) p(y) dy. \end{eqnarray}$$

Here $p(y)$ is probability density of wealth $y$. If the wealth is discrete $y=y^k,\ k=1,...,M$, the expected utility function

$$\begin{eqnarray} U(x)=\sum_{k=1}^M u(y^k) p(y^k). \end{eqnarray}$$

Here $M$ is the number of discrete values of wealth $y^k$. $p_x(y^k)$ is the probability that the wealth $y^k$ will be returned, if the capital distribution is $x$. We search for such capital distribution $x$ which provides the greatest expected utility of the returned wealth:

$$\begin{eqnarray} \max_x U(x), \\ \sum_{i=1}^n x_i = 1, \\ x_i \ge 0. \nonumber \end{eqnarray}$$

2 Expected Utility

1 Investment in CD

One may define probabilities $p(y^j)$ of discrete values of wealth $y^j,\ j=1,2,....$ by exact expressions. For example,

$$\begin{eqnarray} p(y^0)& = &\prod_{i} q_i, \nonumber\\ p(y^1)& = &p_1 \prod_{i ... .....& & ..................................................\nonumber \end{eqnarray}$$

Here
$y^0=0,\ y^1=a_1 x_1,\ y^2=a_2 x_2,\ y^n= a_n x_n,\\ y^{n+1}=a_1 x_1+a_2 x_2,\ y^{n+2}=a_1 x_1 + a_3 x_3$. From expression (14.5)

$$\begin{eqnarray} U(x)= \sum_{k=1}^M u(y^k) p(y^k). \end{eqnarray}$$

Here $M$ is the number of different values of wealth $y$.

One determines $U(x)$ approximately by the Monte Carlo approach:

$$\begin{eqnarray} U_K(x)= 1/K \sum_{k=1}^K u(y^k). \end{eqnarray}$$

Here

$$\begin{eqnarray} y^k= \sum_{i=1}^n y_i^k , \end{eqnarray}$$

where

$$\begin{eqnarray} y_i^k&=&\cases {c_i x_i, &if $\eta_i^k \in [0,p_i]$\ \cr 0, &otherwise.\cr} \end{eqnarray}$$

Here $K$ is the number of Monte Carlo samples. $\eta_i^k$ is a random number uniformly distributed on the unit interval. In this case

$$\begin{eqnarray} U(x)= \lim_{K \to \infty} U_K(x). \nonumber \end{eqnarray}$$

2 Investment in CD and Stocks

Investing in CD, the interests $\alpha_i$ are defined by contracts. Only the reliabilities $p_i,\ i=1,...,n$ of banks are uncertain. Investing in stocks, in addition to reliabilities $p_i,\ i=n+j, \ j=1,...,m$ of companies, their future stock rates are uncertain, too. The predicted stock rates are defined by a coefficient $a_i$ that shows the relation between the present and the predicted stock rates. The prediction "horizon" is supposed to be the same as the maturity time of CD.

To simplify the model suppose that one predicts $L$ different values of relative stock rates $a_i^l,\ l=1,...,L$ with corresponding estimated probabilities
$p_i^l,\ \sum_{l=1}^L p_i^l=1,\ p_i^l \ge 0$.
In this case, one may define probabilities $p(y^i)$ of discrete values of wealth $y^i,\ i=1,...,n+m$ by exact expressions. The expressions for CD remains the same. Therefore, we shall consider only stocks assuming that $n=0$ and $L=2$. Then

$$\begin{eqnarray} p(y^0)& = &\prod_{i } q_i, \nonumber\\ p(y^1)& = &p_1 p_1^1 \p... ......& &..................................................\nonumber \end{eqnarray}$$

Here
$y^0=0,\ y^1=a_1^1 x_1,\ y^2=a_1^2 x_1,\ y^3=a_2^1 x_2, y^4=a_2^2 x_2,\\ \ y^{2... ...{2n}= a_n^2 x_n, \ y^{2n+1}=a_1^1 x_1+a_2^1 x_2, \ y^{2n+2}=a_1^2 x_1+a_2^2 x_2$. The reliabilities $p_i$, the stock rate predictions $a_i^l$ and their estimated probabilities $p_i^l$ are defined by experts, possibly, with the help of time series models such as ARMA (see Section 15). For example, maximal values of multi-step prediction are considered as "optimistic" estimates. The minimal values- as "pessimistic" ones. The average values of multi-step prediction are regarded as "realistic" estimates.

Here is a simplest illustration were $n=m=1$ and $L=2$. In this case from (14.5) (14.10) the probabilities $p(y^k)$ of wealth returns $y^k,\ k=0,...,5$ are

$$\begin{eqnarray} p(y^0)& = &q_1 q_2, \nonumber\\ p(y^1)& = &p_1 q_2, \nonumber\... ...= &p_2 p_2^1 p_1, \nonumber\\ p(y^5)& = &p_2 p_2^2 p_1.\nonumber \end{eqnarray}$$

Here
$y^0=0,\ y_1= a_1 x_1\ y^2=a_2^1 x_2,\ y^3=a_2^2 x_2, \\ y^4=a_1 x_1+ a_2^1 x_2,\ y^5=a_1 x_1+ a_2^2 x_2$.

3 Optimal Portfolio, Special Cases

The optimal portfolio depends on the utility function $u(y)$. Consider, for example, the optimal portfolio for three different utility functions.

The first utility function is linear

$$\begin{eqnarray} u(y)= c y. \end{eqnarray}$$

This function is for "rich" persons. Rich persons want to maximize the average wealth. They are not emotional about accidental losses or gains. In the linear case (14.11), the optimal portfolio is to invest all the capital in an object with the highest product $p_ic_i$.

The second utility function is for "prudent" persons which averse risk

$$\begin{eqnarray} u(y)=&\cases {0, &if $0 \le y < a$\ \cr 1, &if $a \le y \le c$,\cr}. \end{eqnarray}$$

Here $a$ is a risk threshold. $c=\max_i c_i x_i$ denotes the maximal return of invested capital (see expression (14.4)). If $a= 1/m\ min_i\ c_i x_i$ then, in the risk-averse case (14.12), an optimal decision is $x_i^*=1/m,\ i=1,...,m$. Here one divides the capital equally between all the objects.

The third utility function is for "risky" persons. Risky persons are ready to risk for the great win $c$.

$$\begin{eqnarray} u(y)=&\cases {0, &if $0 \le y <c$, \cr 1, &if $ y = c$. \cr} \end{eqnarray}$$

Here one invests all the capital in the object with highest wealth return. Therefore, $x_i=1$, if $c_i=\max_j c_j=c$.

These examples are abstract. An average person behaves "risky," if only a small part of his resources is involved. The same person behaves prudently, if all his wealth is at stake. There is a point $r$ between areas of risky and prudent behavior. At this point an average person behaves like the "rich" one. Here is an example

$$\begin{eqnarray} u(y) < y,\ if\ 0 \le y < r, \\ u(y)=y,\ if\ y= r, \nonumber\\ u(y) > y,\ if\ r < y \le c. \nonumber \end{eqnarray}$$

Here $r$ is a boundary point between risky and prudent areas.

4 Optimal Insurance

In this section the optimal insurance is regarded as a special case of optimal investment. Then the expected utility at the end of the next year

$$\begin{eqnarray} U(x)=\sum_{k=1}^M u(y^k) p(y^k) , \end{eqnarray}$$

where $p(y^k)$ is a probability to own next year the wealth $y^k$,
$u(y^k)$ is an utility function of the wealth $y^k$.
Supose that
$y^k=\sum_{i=1}^m c_i (x_i)$
and

$$\begin{eqnarray} c_i(x_i)&=&\cases {z_i- a_i x_i, &jei $\delta_i=1$\ \cr (1-a_i) x_i, &jei $\delta_i=0$,\cr}. \end{eqnarray}$$

Here $z_i$ is the value of the object $i$ ,
the product $a_i x_i$ denotes insurance charge of the object $i$.
$x_i \le z_i$ is insurance policy of the object $i$.
$\delta_i=1$, if the object $i$ survives,
$\delta_i=0$, if not.
$p_i=P\{\delta_i=1\}$ is a survival probability of the object $i$ .
For example:
$p(y^1)=p_1 \prod_{i \neq 1} (1-p_i)$,
$y^1=c_1( x_1)+\sum_{i=2}^m c_i(x_i)$,
where
$c_1(x_1)= z_1-a_1 x_1,\\ c_i(x_i)=(1-a_i)x_i, \ i=2,...,m$.

5 Utility Functions

Utility functions $u(y)$ are different for different persons and organizations. An individual utility function is defined by a lottery
$L(A,B,p)=\{pA+(1-p)B\}$. Here $p$ is the probability to win the best event $A$.
$(1-p)$ is the probability to get the worst one $B$. Denote by $C$ the "ticket price" of this lottery. There are two possible decisions:

• keep the ticket money $C$,
• bay a ticket and risk losing this money while hoping to win a greater wealth $A$ with probability $p$.

Denote by $p(C)$ a "hesitation" probability, when one cannot decide which decision to prefer. One defines the "hesitation" probability $p(C)$ by this condition

$$\begin{eqnarray} L(A,B,C,p(C))=[C \approx \{p(C) A + (1-p(C)) B\}]. \end{eqnarray}$$

Here the symbol $\approx$ denotes the "hesitation." If utilities $u(A)=1$ and $u(B)=0$, the utility of the "ticket" $C$ is equal to the hesitation probability $u(C)=p(C)$ [Fishburn, 1964].

Suppose, for example, that event $C$ is to keep all the investment capital, $y=1$, in a safe; no risk, no profit. Assume that the event $A$ means doubling the capital, $y=2$. The event $B$ means losing all the capital, $y=0$.

Denote by $p(1)$ the hesitation probability. Then
$u(1)= u(0)+p(1)(u(2)-u(0))$. If $u(0)=0$ and $u(2)=1$ then the utility of the capital $u(1)=p(1)$. Here one obtained capital utilities at three points: $y=0,\ y=1$, and $y=2$.

To define a reasonable approximation of the utility function $u(y)$, we need at least two additional points. For example, points $y=0.5$ and $y=1.5$. One defines the corresponding utilities by the hesitation probabilities $p(0.5)$ and $p(1.5)$. These are obtained by two hesitation lotteries

$$\begin{eqnarray} L(1.0,0.0,0.5,p(0.5))= \\ \nonumber [(y=0.5) \approx \{p(0.5)(y=1) +(1-p(0.5))(y= 0) \}] \nonumber \end{eqnarray}$$

and

$$\begin{eqnarray} L(2.0,1.0,1.5,p(1.5))=\\ \nonumber [(y=1.0) \approx \{p(1.5)(y=2.0) +(1-p(1.5))(y=1) \}]. \nonumber \end{eqnarray}$$

Here one obtains utility values
$u(0)=0,\ u(0.5)=p(0.5), \ u(1)=p(1),\ u(1.5)=u(1) + p(1.5) (u(2)-u(1))\ u(2)=1$. The remaining capital utility values are defined by the linear interpolation

$$\begin{eqnarray} u(y)=u(y_i) + p(y_i) (u(y_{i+1}) - u(y_i)),\ \ y_i \le y <y_{i+1}, \\ i=0,1,...,4. \nonumber \end{eqnarray}$$

In consulting offices, the "psychological tests" defining capital utilities are not always convenient. Then one of the four "typical" utility functions can be selected. The typical utility functions represent the risky, the average, the rich and the prudent persons. The selection depends on observable personal traits.

The same capital utility function (14.14) could be used for all customers. Then one defines customer differences by different border points, namely:
$r_{prudent} < r_{average} < r_{rich} <r_{risky}$ (see Figure 14.2).

6 Software Example

1 Running the Program

The software [Petrikis and Juodgalvyte, 1997] is on the web-site (see Section 4) and is run by Internet

1. open the line 'GMJ1' on the 'Software systems' page (see Figure 3.1),
2. start the applet,
3. open the 'Methods' menu, choose the method and its parameters (see Figure 14.1),
4. open the 'Tasks' menu, chose the task 'Portfolio',
5. select the character : prudent, rich, risky, average (see Figure 14.2),
6. select the method: Monte Carlo, Deterministic (see Figure 14.2),
7. fix the predicted stock rates by updating or keeping the default values determined using ARMA model (see Figure 14.2),
8. click at the 'Operation' label at the top of page,
9. click at the 'Run' button at the bottom of page,
10. read results of the optimal investment, where 'Iteration' means the number of iterations to reach the optimal investment, 'F(x)' shows the expected utility with the minus sign, the following lines show the relative investments (see Figure 14.3),
11. open the 'convergence' window (see Figure 14.4) which show how the best utility depends on the iteration number,
12. open the 'projection' window (see Figure 14.5) showing how the utility depends on the first variable,
13. open the 'spectrum' window showing how a frequency of utilities depends on the iteration number.

Figure 14.1: The control window.

Figure 14.2: The input fields.

Figure 14.3: The output field.

Figure 14.4: The convergence window.

Figure 14.5: The projection window.

The example of predicted stock rate of Vilnius Bankas is presented in the file 'onestep?VB.txt'.

2 A Set of Utility Functions

Nine approximation points are used: $yk[i]=0.25*i,\ i=0,...,8$. Four utility functions are available. They differ at the approximation points. They represent different persons.

prudent person

: $f[0]=0.0,\ f[1]=0.3,\ f[2]=0.5,\ f[3]=0.7,\ f[4]=0.8,\ f[5]=0.85,\ f[6]=0.9,\ f[7]=0.95,\ f[8]=1.0$,

risky person

: $f[0]=0.0,\ f[1]=0.1,\ f[2]=0.2,\ f[3]=0.25,\ f[4]=0.3,\ f[5]=0.4,\ f[6]=0.7,\ f[7]=0.9,\ f[8]=1.0$,

rich person

: $f[0]=0.0,\ f[1]=0.125,\ f[2]=0.25,\ f[3]=0.325,\ f[4]=0.5,\ f[5]=0.625,\ f[6]=0.75,\ f[7]=0.875,\ f[8]=1.0$,

average person

$f[0]=0.0,\ f[1]=0.1,\ f[2]=0.2,\ f[3]=0.25,\ f[4]=0.5,\ f[5]=0.7,\ f[6]=0.85,\ f[7]=0.95,\ f[8]=1.0$.

Users select one of them.

3 Predicting Investment Results

Two investment possibilities are considered: Certificates of Deposit (CD) and shares. Considering CD, the two parameters should be fixed: the interest and the reliability (bank's survival probability). These parameters are defined in the file $Portfolio.java$. Considering shares, only one parameter is used, the predicted stock rate at the time of CD maturity. That is correct, if the investor is confident about the predicted stock rates at the maturity time. The default values of expected changes of stock rates are zero. The predicted stock rates are given in the files like this one: $onestep?VB.txt$.

Input file = VB.txt
Pradzia = 26.000000 Prognoze = 30.297932 </BODY></HTML>

Here 'VB' denotes the Vilnius Bank stock rates. 'Pradzia' denotes the rates now. 'Prognoze' denotes the predicted rates. The difference between predicted and present stock rates, divided by the present stock rate and expressed in percents, is considered as a "stock interest." That is an important simplification. However, it helps to consider both shares and CD in the same way. That is convenient for calculations.

Predicted rates in $VB.txt$ files are obtained by the ARMA model using the Vilnius Bank data. The predicted values can be changed manually by clicking and writing on the corresponding fields of the 'Tasks' page.

4 Data

The stock rates of the following major Lithuanian joint-stock companies, including the banks, are considered.

Bank "Vilniaus Bankas"

: data file VB.txt,

Bank "Snoras"

: data file Snoras.txt,

Bank "Hermis"

: data file Hermis.txt,

Savings bank "LTB"

: data file LTB.txt,

Agricultural bank "LZUB"

: data file LZUB.txt,

Bank "Siauliu Bankas"

: data file Siauliu.txt,

Economic bank "Ukio Bankas"

data file Ukio.txt,

Dairy "Rokiskio Suris"

: data file Rokiskio.txt,

Brewery "Kalnapilis"

data file Kalnapilis.txt,

Dairy "Birzu Pienas"

: data file BirzuAB.txt.

The first record of the data files shows closing rates on January 01, 1998. The last record defines closing rates on November 14, 1998. Two hundred twenty nine sessions of Lithuanian stock exchange are recorded in the data. Using this data ARMA model makes ninty day predictions what corresponds to three month CD.

5 Results

Optimization results are in Tables 14.1, 14.2, and 14.3. Tables 14.1 and 14.2 both are for a prudent person. Table 14.1 is obtained by the Monte Carlo method. Table 14.2 shows results of the deterministic method. Table 14.3 is obtained by the deterministic method for a risky person.

The "Optimal investment" column is just a copy of the output field (see Figure 14.3). The output field represents optimal values of internal variables. The internal variables are proportional to the optimal parts of the capital. Actual optimal parts are obtained by normalization and are shown in the "Optimal part" column.

Table 14.1: Monte Carlo method. Prudent person. Optimal portfolio obtained after 892 iterations. The utility is 0.773.

Company	Optimal investment	Optimal part
Vilniaus Bankas, CD	0.157	0.0251
Snoras, CD	0.354	0.0566
Hermis, CD	0.402	0.0643
Litimpex, CD	0.724	0,1159
Ukio Bankas, CD	0.334	0.0535
Siauliu Bankas, CD	0.842	0.1348
Medicinos Bankas, CD	0.096	0.0153
State bonds	0.318	0.0509
Vilniaus Bankas, shares	0.626	0.1002
Snoras, shares	0.677	0.1083
Hermis, shares	0.293	0.0469
Ukio Bankas, shares	0.466	0.0746
Siauliu Bankas, shares	0.461	0.0738
Rokiskio Suris, shares	0.108	0.0169
Birzu Pienas, shares	0.061	0.0097
Kalnapilis, shares	0.146	0.02337

Table 14.2: Exact o method. Prudent person. Optimal portfolio obtained after 892 iterations. The utility is 0.776.

Company	Optimal investment	Optimal part
Vilniaus Bankas, CD	0.699	0.0755
Snoras, CD	0.453	0.0489
Hermis, CD	0.836	0.904
Litimpex, CD	0.795	0,0859
Ukio Bankas, CD	0.366	0.0395
Siauliu Bankas, CD	0.783	0.0846
Medicinos Bankas, CD	0.926	0.1001
State bonds	0.589	0.0636
Vilniaus Bankas, shares	0.937	0.1001
Snoras, shares	0.361	0.0390
Hermis, shares	0.343	0.0370
Ukio Bankas, shares	0.002	0.0002
Siauliu Bankas, shares	0.944	0.1020
Rokiskio Suris, shares	0.760	0.0822
Birzu Pienas, shares	0.07	0.00075
Kalnapilis, shares	0.052	0.0056

Tables 14.1 and 14.2 show that the optimal distribution of capital obtained by the approximate method differ from that defined by the exact one. This is important disadvantage of the approximate Monte Carlo method. Note, that the best values of utility functions are close for both methods. They are 0.773, for the Monte Carlo method, and 0.776, for the deterministic one. This means that the optimal values of utility functions are not very sensitive to moderate changes in the capital distribution. The reason is that here investment alternatives are not too different.

Table 14.3: Exact method. Risky person. Optimal investment obtained after 159 iterations. The utility is 0.291.

Company	Optimal investment	Optimal part
Vilniaus Bankas, CD	0.907	0.107
Snoras, CD	0.083	0.0098
Hermis, CD	0.857	0.101
Litimpex, CD	0.438	0,0517
Ukio Bankas, CD	0.024	0.00283
Siauliu Bankas, CD	0.737	0.0870
Medicinos Bankas, CD	0.739	0.872
State bonds	0.656	0.0774
Vilniaus Bankas, shares	0.762	0.0899
Snoras, shares	0.179	0.0211
Hermis, shares	0.894	0.1055
Ukio Bankas, shares	0.451	0.0532
Siauliu Bankas, shares	0.098	0.011
Rokiskio Suris, shares	0.946	0.112
Birzu Pienas, shares	0.019	0.00224
Kalnapilis, shares	0.076	0.0089

Comparing Table 14.2 representing the prudent person and Table 14.3 representing the risky one, we see differences. The best value of utility function is equal to 0.776, for the "prudent." It is equal to 0.291, for the "risky." This difference is explained by assumptions made to normalize utility functions. The normalization assumes that the maximal utility is a unit and the minimal one is zero. Therefore, the best value of utility function of the risky person happens to be less then that of the prudent one. However, lower utilities does not mean that risky persons are getting less satisfaction. One needs more sophisticated normalization techniques to compare correctly the satisfaction scales of different persons by their utility functions.

6 Future Developments

The first step is to drop the "confidence" assumption that one predicts the stock rates exactly. To do this, the variance of the predicted stock rates should be included into the updated Portfolio Model.

The important future task is the sensibility analysis. For example, by considering three scenarios: pessimistic, optimistic and realistic. In the pessimistic scenario lower probabilities $p_i$ for CD's and lower interest rates for stocks are considered. In the optimistic case one sets higher values for these parameters. The realistic case is in the middle. Important task is to represent visually the "stability" of securities . If the optimal values of some securities are not too different in all three scenarios, they are considered as stable.

7 Minimization of Road Accident Damages

Here we consider an illustrative example how to invest some fixed capital to minimize the damages of the road accidents. The problem is split in two stages.
In the first stage, the resources are distributed between groups of accidents defined by their causes.
In the second stage, the geographical distribution of funds inside a single group is regarded. The four causes of road accidents are considered:

• intoxication,
• speeding,
• ignoring safety belts,
• bad roads- "black spots."

Denote by $x_i$ a part of the funds spent to reduce accidents related to the cause $i$. In this section, we shall assume for simplicity that the total amount of funds is unit. Here index $i=1$ denotes intoxication, $i=2$ means speeding, $i=3$ denotes safety belts, and $i=4$ denotes black spots.

Denote by $y_i=y_i(x_i),\ i=1,..,4$ the expected number of accidents in relation to the part of funds $x_i$. Suppose that

$$\begin{eqnarray} y_i=y_i(x_i)= c_i e^{-a_i x_i}, \end{eqnarray}$$

where

$$\begin{eqnarray} (c_i,a_i)= arg\ \min_{(c, a)} \sum_{k=1}^K(c e^{-a x_i^k}-N_i^k)^2. \end{eqnarray}$$

Here $N_i^k$ is the actual number of accidents when the part of funds was $x_i^k$.

1 Distribution Between Groups

Denote the estimate of expected losses from all four groups of accidents when the distribution of funds between causes are defined by the vector $x=(x_i,\ i=1,...,4)$

$$\begin{eqnarray} u(x)=\sum_{i=1}^4 h_i y_i(x_i). \end{eqnarray}$$

Here $h_i$ is the estimate of expected damages of an accident of the group $i$. If data is available, then $h_i$ is just average value. If not, then $h_i$ is some expert estimate.

2 Geographical Distribution

The distribution between black spots will be regarded. Denote the distribution vextor by $x=(x_i,\ i=1,...,m)$, where $m$ is a number of black spots. $x_i$ is the part of funds invested to improve the black spot $i$. Denote by $y_i=y_i(x_i),\ i=1,..,m$ the expected number of accidents in relation to the part of funds $x_i$.

$$\begin{eqnarray} y_i=c_i e^{-a_i x_i}, \end{eqnarray}$$

where

$$\begin{eqnarray} (c_i,a_i)= arg\ \min_{(c, a)} \sum_{k=1}^K(c e^{-a x_i^k}-N_i^k)^2. \end{eqnarray}$$

Here $N_i^k$ is the actual number of accidents at the black spot $i$ when the part of funds was $x_i^k$.

3 Definition of Optimal Investment

The formal definition is

$$\begin{eqnarray} x^*= arg \ \min_{x} u(x) \\ u(x)=\sum_{i=1}^m h_i y_i, \\ \sum_{i=1}^m x_i =1,\\ x=(x_i,\ i=1,...,m),\ ,x_i \ge 0. \end{eqnarray}$$

Here $h_i$ is the estimate of expected damages of an accident at the black spot $i$. If data is available, then $h_i$ is just average value. If not, then $h_i$ is some expert estimate.

The direct minimization of the $m$-dimensional utility function (14.27) is difficult if $m$ is large. In the case (14.27) the dynamic programming is an appropriate optimization technique.

4 Dynamic Programming

The dynamic programming is a conventional technique to optimize sequential decisions [Bellman, 1957]. Applying the dynamic programming to specific problems, one develops specific algorithms, as usual.

1 Bellman's Equations

One starts from the last black spot $m$ defining by $v$ a part of funds left for the spot $m$. Then

$$\begin{eqnarray} u_m(v)=h_m y_m(v) \\ v_m(v)=v\\ u_{m-i}(v)=\min_{0 \le v \le ... ...0 \le v \le 1} (h_{m-i} y_{m-i}(v)+u_{m-i+1}(v)), \\ i=1,...,m-1 \end{eqnarray}$$

Here the relation $u_{m-i}(v)$ shows how the maximal utility that can be obtained if the part of funds $v$ designated for the set of black spots starting from $m-i$ is distributed in the best possible way. The relation $v_{m-i}(v)$ shows how the optimal part of funds for the $m-i$ black spot depends on the part of funds designated for the set of black spots starting from $m-i$. Here $i=1,...,m-1$.

Reurrent equations (14.32) and (14.33) define the optimal parts of funds $v_{m-i}(v)$ as a function of $v$. The actual optimal values of these funds $x^*$ are obtained by substitutions assuming that the total amount of funds is unit.

$$\begin{eqnarray} x_1^*=v_1(1)\\ x_2^*=v_2(1-x_1^*)\\ x_3^*=v_3(1-x_1^*-x_2^*)\... ............. \nonumber \\ x_m^*=v_m(1-x_1^*-x_2^*- ...-x_{m-1}^*). \end{eqnarray}$$

The minimization of the road accidents is just a good ilustration. Similar procedures can be used in many other problems of optimal distribution of funds.