Лекция: Задачи размещения

Имеется множество возможных мест размещения средств обслуживания клиентов и множество клиентов. Затраты на размещение средства обслуживания в месте составляют ( ). Каждый клиент характеризуется спросом на услуги средства обслуживания, причем полная стоимость удовлетворения спроса клиента с помощью средства обслуживания, размещенного в, равна. Задача ДО состоит в выборе мест размещения средств обслуживания и последующем назначении клиентов этим средствам обслуживания, минимизирующем общую стоимость.

Введем бинарные переменные :

и непрерывные переменные, где ‑ доля спроса клиента, которая удовлетворяется средством обслуживания, размещенным в .

Задача размещения с неограниченной пропускной способностью имеет вид задачи ДО:

при ограничениях

(спрос клиента должен быть удовлетворен)

(клиент может обслуживаться средством обслуживания, размещенным в .)

В задаче размещения с ограниченной пропускной способностью предполагается, что средство обслуживания, размещенное в, имеет пропускную способность, а клиент имеет спрос; ‑ количество услуг, которые клиент получает от средства обслуживания; ‑ удельная стоимость услуг.

Модель представляет собой следующую задачу ДО:

при ограничениях

(спрос клиента должен быть удовлетворен),

(клиенты могут обслуживаться средством обслуживания, размещенным в ),