Личный кабинет
Подробное описание документа
Выпуклые матрицы и многомерная задача о ранце общей лестничной структуры / Гурченков А. А., Есенков А. С., Тизик А. П., Цурков В. И. - URL: https://vestniken.bmstu.ru/catalog/math/diff/725.html (дата обращения: 11.03.2026). - DOI 10.18698/1812-3368-2016-6-32-41 // Вестник МГТУ им. Н. Э. Баумана. Сер. Естественные науки. - 2016. - № 6. -
Скачать документ
Рассмотрены многомерные задачи о ранце с так называемыми выпуклыми матрицами ограничений - матрицами, состоящими из нулей и единиц, в которых в каждой строке (или в каждом столбце) единицы идут подряд, без пропусков. Доказано, что выпуклые матрицы абсолютно унимодулярны. Это позволяет применить для решения таких задач обычный симплекс-метод. Для многомерных задач о ранце с выпуклыми матрицами ограничений общей лестничной структуры предложен декомпозиционный метод решения, что дает возможность значительно увеличить размерность решаемых задач. Декомпозиции подвергаются как ограничения, так и целевая функция. В общем случае цикл итераций состоит из решения всевозможных задач о ранце с двумя ограничениями, имеющими хотя бы одну общую переменную. После решения задачи о ранце с двумя ограничениями ее эквивалентно (изменением коэффициентов целевой функции для общих переменных) заменяют совокупностью двух задач о ранце с одним ограничением каждая. Метод обладает дополнительным достоинством: в нем не накапливаются погрешности вычислений, так как в каждом цикле коэффициенты целевой функции восстанавливают свое значение. Приведен численный пример, иллюстрирующий предложенный метод.
Статья опубликована в следующих изданиях
№ 6. - 2016.
