4 / 8
B.N. Korobets
138
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. Естественные науки. 2016. № 6
The algorithm for solving this task comprises two stages. First, we need to deter-
mine minimum costs
s
ij
required to achieve scores
j
= 1, 2, 3 for each area
i
. If the exis-
ting score is equal to 1, then
s
i
1
represents the cost of maintaining the existing RL for
this area (below we will assume that these costs are known).
Second, the resulting score
s
ij
,
1, 3,
1, ,
j
i
m
is used to achieve the required
comprehensive score at minimum costs. Let us discuss the algorithms to solve these
problems.
Stage I.
At the first stage, solve
m
problems (for each area). Describe the relevant
problem, omitting the area index. Assume without loss of generality that the existing
RL score is 1 (below the global level).
Determine the increase in the RL required to achieve scores 2 and 3. If the existing
level is equal to
W
0
<
A
1
, then the required increases are:
0
1
1
;
A W
0
2
2
.
A W
Let
x
i
= 1 if project I is included in the technological development programme for
the area in question; otherwise,
x
i
= 0. Let us examine the following problem:
min
i i
i
x с
(1)
with the following limitation
2
.
i i
i
x w
(2)
This is a classic knapsack problem that has efficient solutions for integer-valued
parameters (e. g. dichotomic programming [9]).
Note that the solution to problem (1), (2) with the right-hand side equal to
2
also provides for optimal solutions at smaller values of the right-hand side, specifically
at
1
.
Therefore, by solving the problem, we will get minimum costs
s
2
and
s
3
(as no-
ted above, costs
s
1
are assumed to be known).
Examine the following example. There are five projects nominated to be included
in the technological development programme. Their data are given below:
i
……..
1
2
3
4
5
s
i
…….
3
4
5
4
6
w
i
……
7
6
5
7
8
Let
A
1
= 30,
A
2
= 40, and
W
0
= 15. Therefore,
1
15,
2
25.
Problem
3
x
1
+ 4
x
2
+ 5
x
3
+ 4
x
4
+ 6
x
5
min
with the following limitation
7
x
1
+ 6
x
2
+ 5
x
3
+ 6
x
4
+ 8
x
5
25.