Том 8, серия 2, номер 1, 2001 г., Стр. 70-87

УДК 519.854.2
А. В. Панюков
Задача размещения прямоугольных объектов с минимальной стоимостью связывающей сети

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

Панюков А. В. ¹
1. Южно-Уральский государственный университет,
пр. Ленина, 76, 454080 Челябинск, Россия
е-mail: panyukov@inf.susu.ac.ru

Статья поступила 26 июня 2000 г.
Исправленный вариант — 22 ноября 2000 г.