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

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

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

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

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

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

Див. також

• Задача про розміщення об'єктів з мінімізацією суми відстаней (вона ж «задача про 1-медіану») з медіаною множини точок як частковим випадком
• Задача про максимінне розміщення об'єктів (якомога далі, розміщення шкідливих об'єктів)
• Задача про k-центр
• Метод k-медіан