Аннотация:
В статье рассматривается модификация хорошо известной задачи о $p$-медиане, в которой количество медиан является переменной величиной. Рассматривается постановка данной задачи, а также реализуется эвристический метод нахождения нижних оценок ее оптимального значения.
Ключевые слова:задача о $p$-медиане; релаксация Лагранжа; нижние оценки; субградиентный алгоритм.