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

Предложен способ иерархической декомпозиции задачи размещения прямоугольных объектов с минимальной стоимостью связывающей их сети на задачу оптимального упорядочения (верхний уровень) и двух задач построения оптимального потока (нижний уровень). Получены следующие результаты: 1) найдены необходимые и достаточные условия локального экстремума и предложен алгоритм построения локально-оптимальных решений; 2) для задач большой размерности предложен алгоритм решения, основанный на случайном поиске, эвристике и рассмотренном методе декомпозиции; 3) для поиска глобального экстремума предложен алгоритм по схеме метода ветвей и границ. Библиогр. 27.