3 / 10
А.А. Гурченков, А.С. Есенков, А.П. Тизик, В.И. Цурков
34
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. Естественные науки. 2016. № 6
Целевая функция имеет вид
1 1 1 1
...
max, 0 ,1
.
k k
J J
j
k
c x c x
c x
c
j J
(5)
Задача (1)–(5) является многомерной задачей о ранце с выпуклой матрицей
ограничений общей лестничной структуры — некоторые переменные могут
присутствовать в двух и более ограничениях.
Алгоритм решения задачи (1)–(5).
Обоснование декомпозиции зада-
чи (1)–(5) на множество задач с двумя ограничениями и в конечном счете на мно-
жество задач с одним ограничением в каждой проведено в работе [18]. Лишь один
параметр — полиномиальность необходимого объема вычислений не определен в
работе [18]. Может потребовать бесконечное число итераций для достижения пре-
дельного состояния одномерных задач. Однако, если коэффициенты в целевой
функции исходной задачи — целые числа, то значение целевой функции в опти-
мальном решении по крайней мере на единицу больше значения целевой функции
для любого допустимого решения. Поэтому при достаточно близких значениях не-
скольких коэффициентов в целевой функции одномерной задачи можно полагать
их равными и формировать решение исходной задачи.
Пример 1.
Рассмотрим пример и его решение, являющееся иллюстрацией
изложенного выше:
1 2 3 4 5 6 7
4;
x x x x x x x
(6)
3 4 5 6 7 8 9 10
5;
x x x x x x x x
(7)
5 6 7 8 9 10 11 12 13
6;
x x x x x x x x x
(8)
1
2
3
4
5
6
7
8
4 6 7 9 12 13 14 7
x x x x x x x x
9
10
11
12
13
8 6 4 3 2
max .
x x x x x
(9)
Формируем и решаем задачу с первым и вторым ограничениями (6) и (7):
1 2 3 4 5 6 7
4;
x x x x x x x
(10)
3 4 5 6 7 8 9 10
5;
x x x x x x x x
(11)
1
2
3
4
5
6
7
8
9
10
26 28 7
4 6 7 9 8
4 3
max .
3
3 2
x x x x x
x
x x x x
(12)
Поскольку переменные
1
x
и
2
x
имеются в исходной задаче (6)–(9) только в
одном ограничении, и в этой двумерной задаче (10)–(12) коэффициенты такие
же. Коэффициенты при переменных
3
x
и
4
x
совпадают с исходными. Коэффи-
циенты при переменных
5 6
,
x x
и
7
x
составляют
2 / 3
от исходных, так как в
исходной задаче (6)–(9) они присутствуют в трех ограничениях. Коэффициенты
при переменных
8 9
,
x x
и
10
x
равны половине от исходных, поскольку в исход-
ной задаче (6)–(9) эти переменные присутствуют в двух ограничениях.