Задача о рюкзаке для прямоугольных предметов с ограничением на расположение центра тяжести

Имеется множество предметов прямоугольной формы с заданными шириной, длиной и массой и большой прямоугольник (рюкзак) с известными шириной и длиной. Требуется выбрать такое подмножество предметов и найти их расположение в рюкзаке без взаимных пересечений, чтобы минимизировать свободное место в рюкзаке. Центр тяжести упакованных предметов не должен уклоняться от геометрического центра рюкзака по обеим координатам больше заданного порога. Мы представляем решение задачи в виде перестановки предметов и используем известный skyline алгоритм в роли декодирующей процедуры. Ограничение на расположение центра тяжести включается в целевую функцию в виде штрафа. Чтобы найти наилучшую перестановку, используется алгоритм имитации отжига. Для генерации соседних решений два предмета меняются местами в перестановке, а при нарушении ограничений используется специальное правило для сдвига центра тяжести в нужную сторону. Обсуждаются результаты численных экспериментов для примеров с известными оптимальными решениями. Табл. 2, ил. 3, библиогр. 14.