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

Вначале будет представлен алгоритм решения задачи UFL, а затем перечислены результаты, которые могут быть получены за счет адаптации алгоритма к другим задачам.

Алгоритм выполняет LP-релаксацию, а затем в два этапа модифицирует полученное дробное решение. Первый этап, называемый ''фильтрацией'', предназначен для ограничения стоимости соединения каждого клиента с самым удаленным объектом, частично обслуживающим его. Для этого переменные <math>y_i \;</math>, обозначающие стоимость открытия объектов, пропорционально увеличиваются на константную величину, а затем переменные <math>x_{ij} \;</math>, обозначающие стоимость соединения, корректируются для использования ближайших возможных объектов.