Задача о размещении объектов: различия между версиями

Задачи о размещении объектов рассматривают ситуации, в которых необходимо спланировать местоположение объектов, предназначенных для обслуживания заданного множества клиентов. Цель обычно заключается в минимизации суммы затрат на открытие объектов и затрат на обслуживание их клиентами с учетом различных ограничений – таких как количество и тип клиентов, которых может обслуживать объект. Существует множество вариантов этой задачи, зависящих от структуры стоимостной функции и ограничений, налагаемых на решение. Первые исследования задачи о размещении объектов выполнили Кюн и Гамбергер [35], Балински и Волф [8], Манн [40] и Балински [7]. Обзорные работы представили Краруп и Прузан [34], а также Мирчандани и Фрэнсис [42]. Любопытно отметить, что одним из самых эффективных алгоритмов решения задачи о размещении объектов без ограничений на пропускную способность является прямо-двойственный алгоритм в сочетании с алгоритмом ветвления и границ, предложенный Эрленкоттером [16] еще в 1978 году. Его прямо-двойственная схема близка к техникам, используемым в современной литературе, посвященной алгоритмам аппроксимации.