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

В задаче UFL заданы множество <math>\mathcal{F}</math> из <math>n_f \;</math> ''объектов'' и множество <math>\mathcal{C} \;</math> из <math>n_c \;</math> ''клиентов'' (которые также могут называться ''городами'' или ''точками спроса''). Каждому объекту i 2 F назначена стоимость открытия этого объекта fi. Кроме того, для каждого объекта i 2 F и клиента j 2 C задана стоимость соединения cij. Задача заключается в открытии подмножества объектов и соединении каждого клиента с открытым объектом таким образом, чтобы общая стоимость была минимальной. Заметим, что после определения множества открытых объектов оптимальным является соединение каждого клиента с открытым объектом, имеющее минимальную стоимость. Таким образом, задача заключается в нахождении множества SC F, минимизирующего значение Pi2S fi + Pj2C mmies{c;j}. Это определение и определения других вариантов задачи о размещении объектов далее будут предполагать единичный спрос у каждого клиента. Обобщение определений до случая с заданным спросом у каждого отдельного клиента является тривиальным. Задачу UFL можно сформулировать в виде следующей целочисленной программы, предложенной Балински [ ]. Пусть yi, i 2 F равно 1 в случае, если объект открыт, и 0 в противном случае. Пусть xij, i 2 F, j 2 C – доля клиента j, назначенная объекту i.