Выпуклые матрицы и многомерная задача о ранце общей лестничной структуры

7 / 10

А.А. Гурченков, А.С. Есенков, А.П. Тизик, В.И. Цурков
38 ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. Естественные науки. 2016. № 6
20. Кузовлев Д.И., Тизик А.П., Тресков Ю.П. Декомпозиционный алгоритм для решения
транспортной задачи с ограниченными пропускными способностями // Мехатроника,
автоматизация, управление. 2012. № 1. С. 45–48.
21. Тизик А.П., Кузовлев Д.И., Соколов А.А. Метод последовательной модификации
функционала для транспортной задачи с дополнительными пунктами производства и
потребления // Вестник ТвГУ. Серия прикладная математика. 2012. № 4. С. 91–98.
Гурченков Анатолий Андреевич — д-р физ.-мат. наук, профессор кафедры «Высшая
математика» МГТУ им. Н.Э. Баумана (Российская Федерация, Москва, 105005, 2-я Бау-
манская ул., д. 5), ведущий научный сотрудник Вычислительного центра им. А.А. До-
родницына ФИЦ «Информатика и управление» РАН (Российская Федерация, Москва,
119333, ул. Вавилова, д. 40).
Есенков Александр Сергеевич — канд. физ.-мат. наук, научный сотрудник Вычисли-
тельного центра им. А.А. Дородницына ФИЦ «Информатика и управление» РАН
(Российская Федерация, Москва, 119333, ул. Вавилова, д. 40).
Тизик Александр Петрович — канд. физ.-мат. наук, старший научный сотрудник Вы-
числительного центра им. А.А. Дородницына ФИЦ «Информатика и управление» РАН
(Российская Федерация, Москва, 119333, ул. Вавилова, д. 40).
Цурков Владимир Иванович — д-р физ.-мат. наук, заведующий отделом Вычислитель-
ного центра им. А.А. Дородницына ФИЦ «Информатика и управление» РАН (Россий-
ская Федерация, Москва, 119333, ул. Вавилова, д. 40).
Просьба ссылаться на эту статью следующим образом:
Гурченков А.А., Есенков А.С., Тизик А.П., Цурков В.И. Выпуклые матрицы и многомер-
ная задача о ранце общей лестничной структуры // Вестник МГТУ им. Н.Э. Баумана.
Сер. Естественные науки. 2016. № 6. C. 32–41. DOI: 10.18698/1812-3368-2016-6-32-41
CONVEX MATRICES AND MULTIDIMENSIONAL KNAPSACK PROBLEM
OF GENERALIZED LADDER STRUCTURE
А.А. Gurchenkov1, 2
А.S. Esenkov2
А.P. Tizik2
V.I. Tsurkov2
1 Bauman Moscow State Technical University, Moscow, Russian Federation
2 Dorodnitsyn Computing Centre, Federal Research Centre Computer Science
and Control, Russian Academy of Sciences, Moscow, Russian Federation
Abstract Keywords
The article deals with solving multidimensional knapsack
problems with the so-called convex constraint matrices —
consisting of zeros and ones in which in each row (or each
column) the ones are consecutive, with no gaps. It is proved
that convex matrices are absolutely unimodular. This allows
for the usual simplex method to be applied to solve such
Knapsack problem, convex
matrix, decomposition, iterative
method