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

В задаче 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>. Задача заключается в открытии подмножества объектов и соединении каждого клиента с открытым объектом таким образом, чтобы общая стоимость была минимальной. Заметим, что после определения множества открытых объектов оптимальным является соединение каждого клиента с открытым объектом, имеющее минимальную стоимость. Таким образом, задача заключается в нахождении множества <math>S \subseteq \mathcal{F}</math>, минимизирующего значение <math>\sum_{i \in S} f_i + \sum_{j \in C} min_{i \in S} \{ c_{ij} \}</math>. Это определение и определения других вариантов задачи о размещении объектов далее будут предполагать единичный спрос у каждого клиента. Обобщение определений до случая с заданным спросом у каждого отдельного клиента является тривиальным. Задачу UFL можно сформулировать в виде следующей целочисленной программы, предложенной Балински [7]. Пусть <math>y_i, i \in \mathcal{F},</math> равно 1 в случае, если объект открыт, и 0 в противном случае. <math>Пусть x_{ij}, i \in \mathcal{F}, j \in \mathcal{C}</math>, – доля клиента j, назначенная объекту i.

(1) <math>min \sum_{i \in \mathcal{F}} f_i y_i + \sum_{i \in \mathcal{F}} \sum_{j \in \mathcal{C}} c_{ij} x_{ij}</math>

 

(2) при условии <math>\sum_{i \in \mathcal{F}} x_{ij} = 1</math> для всех <math>j \in \mathcal{C}</math>,