Задача о 1-центре или минимаксная задача размещения объектов — это классическая задача комбинаторной оптимизации, задача в дисциплине «исследование операций», — частный случай задачи о размещении объектов. В наиболее общем случае формулируется следующим образом:
- Задано множество местоположений потребителей, пространство возможных точек размещения объектов (производства или обслуживания) и функция стоимости перевозки от любой точки возможного размещения до точки потребления
- Нужно найти оптимальную точку расположения объектов, минимизирующее максимальную стоимость доставки от объекта до потребителя.
Простой частный случай, когда объекты размещения и точки потребления находятся на плоскости, а стоимостью доставки является евклидово расстояние (планарная минимаксная евклидова задача размещения объектов, евклидова задача о 1-центре на плоскости), известна также как задача о наименьшей окружности. Её обобщение на многомерные евклидовы пространства известно как задача о наименьшей ограничивающей сфере. В дальнейшем обобщении (взвешенная евклидова задача размещения) точкам потребления приписаны веса и цена транспортировки является суммой расстояний, умноженных на соответствующие веса. Другой частный случай — задача о ближайшей строке[en], когда входом задачи служит строка, а расстояние измеряется как расстояние Хэмминга.
Существуют многочисленные частные случаи задачи, зависящие как от выбора местоположения точек потребления и объектов производства (или обслуживания), так и от выбора функции, вычисляющей расстояние.
См. также
- Задача о размещении объектов с минимизацией суммы расстояний (она же «Задача о 1-медиане») с медианой множества точек[en] в качестве частного случая
- Задача о максиминном размещении объектов (как можно дальше, размещение вредных объектов)
- Задача о k-центре
- Задача о k-медиане
Примечания
Литература
- Nimrod Megiddo. The weighted Euclidean 1-center problem // Mathematics of Operations Research. — Hanover: Institute for Operations Research and the Management Sciences. — Т. 8, вып. 4. — С. 498–504. — DOI:10.1287/moor.8.4.498.
- Abdelaziz Foul. A 1-center problem on the plane with uniformly distributed demand points // Operations Research Letters. — Elsevier, 2006. — Т. 34, вып. 3. — С. 264–268. — DOI:10.1016/j.orl.2005.04.011.
- R. Chandrasekaran. The weighted euclidean 1-center problem // Operations Research Letters. — Elsevier, July 1982. — Т. 1, вып. 3. — С. 111–112. — DOI:10.1016/0167-6377(82)90009-8.
- M. Colebrook, S. Alonso Gutiérrez, J. Sicilia. A New Algorithm for the Undesirable 1-Center Problem on Networks // Journal of the Operational Research Society. — Palgrave Macmillan Journals, 2002. — Т. 53, вып. 12. — С. 1357–1366. — DOI:10.1057/palgrave.jors.2601468.
- Rainer E. Burkard, Helidon Dollani. A Note on the Robust 1-Center Problem on Trees // Annals of Operations Research. — Kluwer Academic Publishers, 2002. — Т. 110, вып. 1-4. — С. 69–82. — ISSN 1572-9338. — DOI:10.1023/A:1020711416254.
 | Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .