4551
правка
Задача о размещении объектов: различия между версиями
Материал из WEGA
→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 39: | Строка 39: | ||
В ''задаче с ограничениями на пропускную способность'' для всех <math>i \in \mathcal{F}</math> добавляется ограничение на пропускную способность <math>\sum_{j \in C} x_{ij} \le u_i y_i</math>. Важно различать случаи ''с возможностью разделения'' и с его ''невозможностью'', а также случаи с ''мягким'' и ''жестким ограничением на пропускную способность''. В случае с возможностью разделения имеем <math>x \ge 0 \;</math>, что позволяет обслуживать клиента при помощи нескольких депо; в случае с невозможностью разделения необходимо выполнение <math>x \in \{ 0, 1 \}^{n_f \times b_c}</math>. Если каждый объект может быть открыт не более одного раза (т. е. <math>y_i \in \{ 0, 1 \} \;</math>), ограничения называются жесткими; если в задаче допускается открытие объекта i любое количество r раз для обслуживания <math>ru_i \;</math> клиентов, ограничения называются мягкими. | В ''задаче с ограничениями на пропускную способность'' для всех <math>i \in \mathcal{F}</math> добавляется ограничение на пропускную способность <math>\sum_{j \in C} x_{ij} \le u_i y_i</math>. Важно различать случаи ''с возможностью разделения'' и с его ''невозможностью'', а также случаи с ''мягким'' и ''жестким ограничением на пропускную способность''. В случае с возможностью разделения имеем <math>x \ge 0 \;</math>, что позволяет обслуживать клиента при помощи нескольких депо; в случае с невозможностью разделения необходимо выполнение <math>x \in \{ 0, 1 \}^{n_f \times b_c}</math>. Если каждый объект может быть открыт не более одного раза (т. е. <math>y_i \in \{ 0, 1 \} \;</math>), ограничения называются жесткими; если в задаче допускается открытие объекта i любое количество r раз для обслуживания <math>ru_i \;</math> клиентов, ограничения называются мягкими. | ||
В k-уровневой задаче о размещении объектов заданы следующие начальные данные: множество клиентов C, k непересекающихся множество F 1... F k объектов, стоимость открытия каждого объекта и стоимость соединения клиентов и объектов. Задача заключается в соединении каждого клиента j по пути, состоящему из открытых объектов i1,...,ik, с ii 2 Уц. Стоимость соединения для этого объекта имеет вид cji1 + ci1i2 + • • • + Cik_xik. Задача заключается в минимизации суммы стоимостей соединений и стоимостей открытия объектов. | |||
Все вышеупомянутые задачи были рассмотрены в работе Шмойса, Тардош и Аардал [ ] за исключением задач max-UFL, о k-центрах и k-медианах. Вариант max-UFL был добавлен по историческим причинам, а задачи о k-центрах и k-медианах включены в силу их богатой истории и близкого родства с задачей UFL. Результаты для задачи о размещении объектов с жесткими ограничениями на пропускную способность упомянуты, поскольку, по крайней мере с точки зрения приложения, эта модель более реалистична по сравнению с версией с мягкими ограничениями, рассмотренной в [51]. Для k-уровневой задачи о размещении объектов Шмойс и др. рассматривали случай k = 2. Здесь рассматривается задача для k общего вида. | |||
Также существуют различные варианты задачи о размещении объектов, не упоминавшиеся выше. Можно привести такие примеры задач, как размещение объектов с ограничением числом K [33], универсальное размещение объектов [24, 38], размещение объектов в онлайновом режиме [3, 18, 41], отказоустойчивое размещение объектов [28, 30, 54], размещение объектов при наличии выбросов [12, 28], размещение объектов для нескольких товарных потоков [48], размещение объектов с приоритетами [37, 48], размещение объектов с иерархической стоимостью объектов [52], стохастическое размещение объектов [23, 37, 46], размещение объектов с подключением [53], размещение объектов с балансировкой нагрузки [22, 32, 37], размещение объектов с вогнутой функций затрат [24], размещение объектов с ограничением на количество кабелей [37, 47]. | |||
== Основные результаты == | |||
