Задача про 1-центр
Зада́ча про 1-центр або мініма́ксна зада́ча розмі́щення об'є́ктів — це класична задача комбінаторної оптимізації, задача в дисципліні «дослідження операцій», — частковий випадок задачі про розміщення об'єктів. У найзагальнішому випадку формулюється так:
- Задано множину розташувань споживачів, простір можливих точок розміщення об'єктів (виробництва або обслуговування) і функція вартості перевезення від будь-якої точки можливого розміщення до точки споживання.
- Потрібно знайти оптимальну точку розташування об'єкта, що мінімізує максимальну вартість доставки від об'єкта до споживача.
Простий окремий випадок, коли об'єкти розміщення і точки споживання лежать на площині, а вартістю доставки є евклідова відстань (плана́рна мініма́ксна евклі́дова зада́ча розмі́щення об'є́ктів, евклі́дова зада́ча про 1-центр на площині́), відома також як задача про найменше коло. Її узагальнення на багатовимірні евклідові простори відоме як задача про найменшу обмежувальну сферу. В подальшому узагальненні (зва́жена евклі́дова зада́ча розмі́щення) точкам споживання приписано ваги і ціна транспортування є сумою відстаней, помножених на відповідні ваги. Інший окремий випадок — задача про найближчий рядок[en], коли входом задачі є рядок, а відстань вимірюється як відстань Геммінга.
Існують численні окремі випадки задачі, що залежать як від вибору місця розташування точок споживання і об'єктів виробництва (або обслуговування), так і від вибору функції для обчислення відстані.
- Задача про розміщення об'єктів з мінімізацією суми відстаней (вона ж «задача про 1-медіану») з медіаною множини точок як частковим випадком
- Задача про максимінне розміщення об'єктів (якомога далі, розміщення шкідливих об'єктів)
- Задача про k-центр
- Метод k-медіан
- Nimrod Megiddo. The weighted Euclidean 1-center problem // Mathematics of Operations Research. — Hanover : Institute for Operations Research and the Management Sciences, 1983. — Т. 8, вип. 4 (1 листопада). — С. 498–504. — DOI:. Архівовано з джерела 28 січня 2022. Процитовано 14 березня 2022.
- Abdelaziz Foul. A 1-center problem on the plane with uniformly distributed demand points // Operations Research Letters. — Elsevier, 2006. — Т. 34, вип. 3 (9 лютого). — С. 264–268. — DOI:. Архівовано з джерела 24 вересня 2015. Процитовано 14 березня 2022.
- R. Chandrasekaran. The weighted euclidean 1-center problem // Operations Research Letters. — Elsevier, 1982. — Т. 1, вип. 3 (1 липня). — С. 111–112. — DOI:. Архівовано з джерела 24 вересня 2015. Процитовано 14 березня 2022.
- 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 (9 лютого). — С. 1357–1366. — DOI:.
- 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 (9 лютого). — С. 69–82. — ISSN 1572-9338. — DOI:.
