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

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