Двухэтапный алгоритм решения задачи выбора портфеля ан-
тирисковых программ.
За основу метода решения нами взят алго-
ритм редукции переменных, предложенный в работе [13] для одномер-
ной задачи с одним ограничением вида (11), эффективность которого
подтверждена многочисленными вычислительными экспериментами.
Процесс решения задачи разбивается на два этапа: первый – редук-
ция переменных, ведущая к значительному сокращению размерности
задачи, и второй – определение оптимальных значений оставшихся
(нерудицированных) переменных за счет эффективного использова-
ния динамического программирования.
Рассмотрим эти этапы для блочной задачи (10)–(14) более де-
тально.
Для редукции переменных прежде всего перенумеруем элемен-
ты
k
= 1
, . . . , K
таким образом, чтобы (
p
k
/a
k
)
≥
(
p
k
+1
/a
k
+1
)
;
k
= 1
, . . . , K
−
1
.
Обозначим через
P
оптимальное значение целевой функции зада-
чи при условии, что переменные
y
k
не булевы, а принимают значения
0
≤
y
k
≤
1
. Значение
P
легко определяется стандартными методами
линейного программирования. Величина [
P
] является верхней грани-
цей оптимального решения основной задачи (здесь [
P
] — целая часть
P
).
Определим любое допустимое решение, последовательно присва-
ивая
y
k
= 1
, начиная с
k
= 1
, до тех пор, пока выполняются ограни-
чения (11)–(13), а затем, пробуя дополнить этот набор следующими
элементами с учетом этих же ограничений.
Пусть
P
0
наилучшее значение целевой функции исходной задачи
с булевыми переменными, известное к данному шагу (это так называ-
емый текущий рекорд). Идея редукционного алгоритма состоит в том,
что вначале всем переменным
y
k
поочередно присваивается значение
нуль и подсчитывается соответствующее значение верхней границы
оптимального решения исходной задачи при фиксированном значении
k
-й переменной
P
(
k
)
. Очевидно, что если [
P
(
k
)]
< P
0
, т.е. даже
верхняя граница оптимального решения исходной задачи при фикси-
рованном значении меньше уже имеющегося целочисленного реше-
ния, то существует оптимальное целочисленное решение задачи, в
котором переменная
y
k
= 1
. Затем переменным
y
k
поочередно присва-
ивается значение единицы и также подсчитывается соответствующее
значение верхней границы оптимального решения при фиксированном
значении
k
-й переменной
P
(
k
)
. Очевидно, что если
[
P
(
k
)]
< P
0
, то
существует оптимальное целочисленное решение задачи, в котором
переменная
y
k
= 0
.
Эти значения переменных фиксируются; тогда говорим, что пе-
ременные редуцируются. На каждом шаге
k
= 1
, . . . ,
2
K
проводится
попытка улучшения рекорда
P
0
.
132 ISSN 0236-3941. Вестник МГТУ им. Н.Э. Баумана. Сер. “Машиностроение”. 2014. № 3
