проблема 1 центра
Проблема 1-центра , также известная как минимаксная проблема или минимаксная проблема местоположения , представляет собой классическую задачу комбинаторной оптимизации при исследовании операций типа расположения объектов . В самом общем случае задача формулируется следующим образом: учитывая набор из n точек спроса, пространство возможных местоположений объекта и функцию для расчета транспортных расходов между объектом и любой точкой спроса, найти местоположение объекта. что минимизирует максимальную стоимость транспортировки до точки спроса.
Существует множество частных случаев задачи, зависящих от выбора местоположения как точек спроса и объектов, так и функции расстояния.
Простой частный случай - это когда возможные местоположения и точки спроса находятся в плоскости с евклидовым расстоянием в качестве стоимости транспортировки ( планарная евклидова задача размещения объектов minmax, евклидова задача 1-центра на плоскости и т. д.). Она также известна как задача наименьшего круга . Ее обобщение на n -мерные евклидовы пространства известно как задача о наименьшем охватывающем шаре . Дальнейшее обобщение ( взвешенное евклидово расположение объекта ) — это когда набор весов присваивается точкам спроса, а стоимость транспортировки представляет собой сумму произведений расстояний на соответствующие веса. Другой особый случай, проблема ближайшей строки , возникает, когда входными данными являются строки , а расстояние до них измеряется с использованием расстояния Хэмминга .
Проблему одного центра можно переформулировать как поиск звезды во взвешенном полном графе , который минимизирует максимальный вес выбранных ребер. Соответствующая задача минимизации максимального веса пути между двумя выбранными вершинами вместо звезды называется проблемой минимаксного пути .
См. также
[ редактировать ]- Минимальное расположение объекта ( проблема с 1-медианой ), при этом геометрическая медиана является особым случаем
- Местоположение объекта Maxmin ( неприятное расположение объекта )
- проблема с k-центром
- проблема k-медианы
Ссылки
[ редактировать ]- Мегиддо, Нимрод (ноябрь 1983 г.). «Взвешенная евклидова задача с 1 центром» (PDF) . Математика исследования операций . 8 (4): 498–504. дои : 10.1287/moor.8.4.498 .
- Фол, Абдельазиз (май 2006 г.). «Задача 1 центра на плоскости с равномерно распределенными точками спроса». Письма об исследованиях операций . 34 (3). Эльзевир: 264–268. дои : 10.1016/j.orl.2005.04.011 .
- Чандрасекаран, Р. (июль 1982 г.). «Взвешенная евклидова задача 1 центра». Письма об исследованиях операций . 1 (3). Эльзевир: 111–112. дои : 10.1016/0167-6377(82)90009-8 .
- Коулбрук, М.; Х. Гутьеррес, С. Алонсо; Дж. Сицилия (декабрь 2002 г.). «Новый алгоритм решения нежелательной задачи одного центра в сетях». Журнал Общества операционных исследований . 53 (12). Журналы Пэлгрейва Макмиллана: 1357–1366. дои : 10.1057/palgrave.jors.2601468 . JSTOR 822725 .
- Буркард, Райнер Э.; Хелидон Доллани (февраль 2002 г.). «Заметки о робастной одноцентровой задаче на деревьях». Анналы исследования операций . 110 (1–4). Издательство Kluwer Academic: 69–82. дои : 10.1023/A:1020711416254 . ISSN 1572-9338 .