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