4551
правка
Задача о размещении объектов: различия между версиями
Материал из WEGA
→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 41: | Строка 41: | ||
В k-уровневой задаче о размещении объектов заданы следующие начальные данные: множество клиентов C, k непересекающихся | В k-уровневой задаче о размещении объектов заданы следующие начальные данные: множество клиентов C, k непересекающихся множеств <math>\mathcal{F}_1, ..., \mathcal{F}_k</math> объектов, стоимость открытия каждого объекта и стоимость соединения клиентов и объектов. Задача заключается в соединении каждого клиента j по пути, состоящему из открытых объектов <math>i_1, ... , i_k \;</math>, где <math>i_{\ell} = \mathcal{F}_{\ell}</math>. Стоимость соединения для этого объекта имеет вид <math>c_{ji_1} + c_{i_1 i_2} + ... + c_{i_{k - 1}i_k} \;</math>. Задача заключается в минимизации суммы стоимостей соединений и стоимостей открытия объектов. | ||
Все вышеупомянутые задачи были рассмотрены в работе Шмойса, Тардош и Аардал [ ] за исключением задач max-UFL, о k-центрах и k-медианах. Вариант max-UFL был добавлен по историческим причинам, а задачи о k-центрах и k-медианах включены в силу их богатой истории и близкого родства с задачей UFL. Результаты для задачи о размещении объектов с жесткими ограничениями на пропускную способность упомянуты, поскольку, по крайней мере с точки зрения приложения, эта модель более реалистична по сравнению с версией с мягкими ограничениями, рассмотренной в [51]. Для k-уровневой задачи о размещении объектов Шмойс и др. рассматривали случай k = 2. Здесь рассматривается задача для k общего вида. | Все вышеупомянутые задачи были рассмотрены в работе Шмойса, Тардош и Аардал [15] за исключением задач max-UFL, о k-центрах и k-медианах. Вариант max-UFL был добавлен по историческим причинам, а задачи о k-центрах и k-медианах включены в силу их богатой истории и близкого родства с задачей UFL. Результаты для задачи о размещении объектов с жесткими ограничениями на пропускную способность упомянуты, поскольку, по крайней мере с точки зрения приложения, эта модель более реалистична по сравнению с версией с мягкими ограничениями, рассмотренной в [51]. Для k-уровневой задачи о размещении объектов Шмойс и др. рассматривали случай k = 2. Здесь рассматривается задача для k общего вида. | ||
