Задача про 1-центр

Зада́ча про 1-центр або мініма́ксна зада́ча розмі́щення об'є́ктів — це класична задача комбінаторної оптимізації, задача в дисципліні «дослідження операцій», — частковий випадок задачі про розміщення об'єктів. У найзагальнішому випадку формулюється так:

Задано множину розташувань споживачів, простір можливих точок розміщення об'єктів (виробництва або обслуговування) і функція вартості перевезення від будь-якої точки можливого розміщення до точки споживання.

Потрібно знайти оптимальну точку розташування об'єкта, що мінімізує максимальну вартість доставки від об'єкта до споживача.

Простий окремий випадок, коли об'єкти розміщення і точки споживання лежать на площині, а вартістю доставки є евклідова відстань (плана́рна мініма́ксна евклі́дова зада́ча розмі́щення об'є́ктів, евклі́дова зада́ча про 1-центр на площині́), відома також як задача про найменше коло. Її узагальнення на багатовимірні евклідові простори відоме як задача про найменшу обмежувальну сферу. В подальшому узагальненні (зва́жена евклі́дова зада́ча розмі́щення) точкам споживання приписано ваги і ціна транспортування є сумою відстаней, помножених на відповідні ваги. Інший окремий випадок — задача про найближчий рядок, коли входом задачі є рядок, а відстань вимірюється як відстань Геммінга.

Існують численні окремі випадки задачі, що залежать як від вибору місця розташування точок споживання і об'єктів виробництва (або обслуговування), так і від вибору функції для обчислення відстані.

Див. також

• Задача про розміщення об'єктів з мінімізацією суми відстаней (вона ж «задача про 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:10.1287/moor.8.4.498. Архівовано з джерела 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 (21 квітня). — С. 264–268. — DOI:10.1016/j.orl.2005.04.011. Архівовано з джерела 24 вересня 2015. Процитовано 14 березня 2022.
• R. Chandrasekaran. The weighted euclidean 1-center problem // Operations Research Letters. — Elsevier, 1982. — Т. 1, вип. 3 (1 липня). — С. 111–112. — DOI:10.1016/0167-6377(82)90009-8. Архівовано з джерела 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 (21 квітня). — С. 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 (21 квітня). — С. 69–82. — ISSN 1572-9338. — DOI:10.1023/A:1020711416254.