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

Задача о 1-центре или минимаксная задача размещения объектов — это классическая задача комбинаторной оптимизации, задача в дисциплине «исследование операций», — частный случай задачи о размещении объектов. В наиболее общем случае формулируется следующим образом:

Задано множество местоположений потребителей, пространство возможных точек размещения объектов (производства или обслуживания) и функция стоимости перевозки от любой точки возможного размещения до точки потребления

Нужно найти оптимальную точку расположения объектов, минимизирующее максимальную стоимость доставки от объекта до потребителя.

Простой частный случай, когда объекты размещения и точки потребления находятся на плоскости, а стоимостью доставки является евклидово расстояние (планарная минимаксная евклидова задача размещения объектов, евклидова задача о 1-центре на плоскости), известна также как задача о наименьшей окружности. Её обобщение на многомерные евклидовы пространства известно как задача о наименьшей ограничивающей сфере. В дальнейшем обобщении (взвешенная евклидова задача размещения) точкам потребления приписаны веса и цена транспортировки является суммой расстояний, умноженных на соответствующие веса. Другой частный случай — задача о ближайшей строке, когда входом задачи служит строка, а расстояние измеряется как расстояние Хэмминга.

Существуют многочисленные частные случаи задачи, зависящие как от выбора местоположения точек потребления и объектов производства (или обслуживания), так и от выбора функции, вычисляющей расстояние.