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

1 / 10

32 ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. Естественные науки. 2016. № 6
УДК 519.9 DOI: 10.18698/1812-3368-2016-6-32-41
ВЫПУКЛЫЕ МАТРИЦЫ И МНОГОМЕРНАЯ ЗАДАЧА
О РАНЦЕ ОБЩЕЙ ЛЕСТНИЧНОЙ СТРУКТУРЫ
А.А. Гурченков1, 2
А.С. Есенков2
А.П. Тизик2
В.И. Цурков2
1 МГТУ им. Н.Э. Баумана, Москва, Российская Федерация
2 Вычислительный центр им. А.А. Дородницына ФИЦ «Информатика и управление»
РАН, Москва, Российская Федерация
Аннотация Ключевые слова
Рассмотрены многомерные задачи о ранце с так называе-
мыми выпуклыми матрицами ограничений — матрица-
ми, состоящими из нулей и единиц, в которых в каждой
строке (или в каждом столбце) единицы идут подряд, без
пропусков. Доказано, что выпуклые матрицы абсолютно
унимодулярны. Это позволяет применить для решения
таких задач обычный симплекс-метод. Для многомерных
задач о ранце с выпуклыми матрицами ограничений
общей лестничной структуры предложен декомпозици-
онный метод решения, что дает возможность значитель-
но увеличить размерность решаемых задач. Декомпози-
ции подвергаются как ограничения, так и целевая функ-
ция. В общем случае цикл итераций состоит из решения
всевозможных задач о ранце с двумя ограничениями,
имеющими хотя бы одну общую переменную. После
решения задачи о ранце с двумя ограничениями ее экви-
валентно (изменением коэффициентов целевой функции
для общих переменных) заменяют совокупностью двух
задач о ранце с одним ограничением каждая. Метод обла-
дает дополнительным достоинством: в нем не накапли-
ваются погрешности вычислений, так как в каждом цикле
коэффициенты целевой функции восстанавливают свое
значение. Приведен численный пример, иллюстрирую-
щий предложенный метод
Задача о ранце, выпуклая
матрица, декомпозиция,
итерационный метод
Поступила в редакцию 13.07.2016
©МГТУ им. Н.Э. Баумана, 2016
Введение. При решении различных оптимизационных задач возникают случаи,
когда в пределах одного и того же ограничения ненулевые коэффициенты при
неизвестных совпадают друг с другом. Такие матрицы можно полагать состоя-
щими из нулей и единиц.
Определение 1. Матрицу, состоящую из нулей и единиц, назовем выпуклой по
строкам, если в каждой ее строке сначала идут подряд нули (возможно, ни одного),
далее — единицы (возможно, до конца строки), затем до конца строки — нули.