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

Рассмотрены многомерные задачи о ранце с так называемыми выпуклыми матрицами ограничений - матрицами, состоящими из нулей и единиц, в которых в каждой строке (или в каждом столбце) единицы идут подряд, без пропусков. Доказано, что выпуклые матрицы абсолютно унимодулярны. Это позволяет применить для решения таких задач обычный симплекс-метод. Для многомерных задач о ранце с выпуклыми матрицами ограничений общей лестничной структуры предложен декомпозиционный метод решения, что дает возможность значительно увеличить размерность решаемых задач. Декомпозиции подвергаются как ограничения, так и целевая функция. В общем случае цикл итераций состоит из решения всевозможных задач о ранце с двумя ограничениями, имеющими хотя бы одну общую переменную. После решения задачи о ранце с двумя ограничениями ее эквивалентно (изменением коэффициентов целевой функции для общих переменных) заменяют совокупностью двух задач о ранце с одним ограничением каждая. Метод обладает дополнительным достоинством: в нем не накапливаются погрешности вычислений, так как в каждом цикле коэффициенты целевой функции восстанавливают свое значение. Приведен численный пример, иллюстрирующий предложенный метод.

Литература

[1] Таха Х. Введение в исследование операций. М.: Вильямс, 2001.

[2] Кагиров Р.Р. Многомерная задача о рюкзаке: новые методы решения // Вестник Сибирского государственного аэрокосмического университета им. академика М.Ф. Решетнева. 2007. Вып. 3. С. 16-20.

[3] Федорин А.Н. Многокритериальные задачи ранцевого типа: разработка и сравнительный анализ алгоритмов. Автореферат дис. ... канд. техн. наук. Н. Новгород, 2010.

[4] Думбадзе Л.Г. Разработка методов и алгоритмов в задачах оптимального использования и развития сетей. Автореферат дис. ... канд. физ.-мат. наук. М., 2007.

[5] Батищев Д.И., Коган Д.И., Лейкин М.В. Алгоритмы синтеза решений для многокритериальной многомерной задачи о ранце // Информационные технологии. 2004. № 1.

[6] Мамедов К.Ш., Мамедов Н.Н. Алгоритмы построения гарантированного решения и гарантированного приближенного решения многомерной задачи о ранце // Проблемы управления и информатики. 2014. № 5. С. 30-37.

[7] Корбут А.А., Сигал И.Х. Точные и жадные решения задачи о ранце: отношение значений целевых функций // Известия РАН. Теория и системы управления. 2010. № 5. С. 79-86.

[8] Галимьянова Н.Н., Корбут А.А., Сигал И.Х. Отношения оптимальных значений целевых функций задачи о ранце и ее линейной релаксации // Известия РАН. Теория и системы управления. 2009. № 6. С. 62-69.

[9] Дюбин Г.Н., Корбут А.А. Поведение в среднем жадных алгоритмов для минимизационной задачи о ранце - общие распределения коэффициентов // Журнал вычислительной математики и математической физики. 2008. Т. 48. № 9. С. 1556-1570.

[10] Дюбин Г.Н., Корбут А.А. Жадные алгоритмы для минимизационной задачи о ранце: поведение в среднем // Известия РАН. Теория и системы управления. 2008. № 1. С. 18-28.

[11] Davis T.A., Hager W.W., Hungerford J.T. An efficient hybrid algorithm for the separable convex quadratic Knapsack problem // ACM Transactions on Mathematical Software (TOMS). 2016. Vol. 42. No. 3.

[12] Caprara A., Furini F., Malaguti E., Traversi E. Solving the temporal Knapsack problem via recursive Dantzig - Wolfe reformulation // Information Processing Letters. 2016. Vol. 116. No. 5. P. 379-386.

[13] Cunha J.O., Simonetti L., Lucena A. Lagrangian heuristics for the quadratic Knapsack problem // Computational Optimization and Applications. 2016. Vol. 63. No. 1. P. 97-120.

[14] Peng B., Liu M., Lu Z., Kochengber G., Wang H. An ejection chain approach for the quadratic multiple Knapsack problem // European Journal of Operational Research. 2016. Vol. 253. No. 2. P. 328-336.

[15] Qin J., Xu X., Wu Q., Cheng T.C.E. Hybridization of tabu search with feasible and infeasible local searches for the quadratic multiple Knapsack problem // Computers & Operations Research. 2016. Vol. 66. P. 199-214.

[16] Taylor R. Approximation of the quadratic Knapsack problem // Operations Research Letters. 2016. Vol. 44. No. 4. P. 495-497.

[17] Haddar B., Khemakhem M., Hanafi S., Wilbaut C. A hybrid quantum particle swarm optimization for the multidimensional Knapsack problem // Engineering Applications of Artificial Intelligence. 2016. Vol. 55. P. 1-13.

[18] Dumbadze L.G., Tizik A.P. Many-dimensional Knapsack problem of a special ladder structure // Известия РАН. Теория и системы управления. 1996. № 4. С. 119-122.

[19] Есенков А.С., Леонов В.Ю., Тизик А.П., Цурков В.И. Нелинейная целочисленная транспортная задача с дополнительными пунктами производства и потребления // Известия РАН. Теория и системы управления. 2015. № 1. С. 88-94.

[20] Кузовлев Д.И., Тизик А.П., Тресков Ю.П. Декомпозиционный алгоритм для решения транспортной задачи с ограниченными пропускными способностями // Мехатроника, автоматизация, управление. 2012. № 1. С. 45-48.

[21] Тизик А.П., Кузовлев Д.И., Соколов А.А. Метод последовательной модификации функционала для транспортной задачи с дополнительными пунктами производства и потребления // Вестник ТвГУ. Серия прикладная математика. 2012. № 4. С. 91-98.