Выберу в качестве примера задачу оптимального размещения (и настройки мощности) наземных базовых станций/антенн для обеспечения требуемого уровня приёма на заданной территории — классическая прикладная задача, в которой геометрия (расположение и охватываемые области) определяет всё решение.

1) Формулировка прикладной задачи (конкретный вариант)

Дано: область A ⊂ R^2 (территория покрытия) или конечное множество точек спроса D = {p_i ∈ R^2, w_i ≥ 0} (пользователи/населённость с весами). Требуемый минимум уровня сигнала S_min.Перечень потенциальных мест для установки антенн S = {s_j^0} (или разрешено ставить антенны в произвольной точке области).Модель распространения: пороговая модель с радиусом покрытия r_j (точка p покрыта антенной j, если ||p − s_j|| ≤ r_j). Радиус связан с передаваемой мощностью P_j через закон затухания, например r_j = c·P_j^{1/α} (α — показатель затухания).Стоимость установки: фиксированная стоимость C_fix за антенну плюс стоимость мощности C_p(P_j) (например ∝ P_j).Цель (варианты):
a) Минимизировать общую стоимость при условии полного покрытия: минимизировать ∑_j (C_fix·y_j + C_p(P_j)) при условии, что каждый p_i покрыт: ∀i, ∑_j y_j·I(||p_i−s_j||≤r_j) ≥ 1.
b) При фиксированном бюджете (или числе антенн k) максимизировать долю покрытия или суммарный вес покрытых точек.
c) Минимизировать максимальное расстояние от точки спроса до ближайшей антенны (p‑center): minimize R s.t. ∀i ∃j: ||p_i − s_j|| ≤ R.

2) Математическая модель (дискретный кандидатный набор)
Пусть S = {s_j} — конечный набор кандидатных площадок. Введём бинарные переменные y_j ∈ {0,1} (установлена ли антенна в s_j) и, при фиксированном радиусе r (одинаковом для всех), параметры покрытия:

Покрытие точки i условием ∑_{j: ||p_i−s_j|| ≤ r} y_j ≥ 1.
Задача минимизации числа антенн (Set Cover):
minimize ∑_j yj
s.t. ∀i: ∑{j: d_{ij} ≤ r} y_j ≥ 1, y_j ∈ {0,1}.
Если радиусы r_j переменные и связаны с мощностью P_j, можно ввести непрерывные P_j ≥ 0 и ввести булевы y_j, с ограничением P_j ≤ M·yj, и покрытие как I(d{ij} ≤ c·P_j^{1/α}) — нелинейно и дискретно; часто используют предустановленные уровни мощности (пороговые) и дискретизацию.

Вариант p‑center (выбрать ≤ p базовых станций):
переменные x_{ij} ∈ {0,1} (точка i обслуживается станцией j), y_j ∈ {0,1}
minimize R
s.t. ∑j x{ij} = 1 ∀i
x_{ij} ≤ yj ∀i,j
if x{ij}=1 then d{ij} ≤ R (реализуется через d{ij}·x_{ij} ≤ R)
∑_j yj ≤ p
x{ij}, y_j ∈ {0,1}

p‑median (минимизация суммарных расстояний):
minimize ∑_i w_i ∑j d{ij} x_{ij}
s.t. ∑j x{ij} = 1, x_{ij} ≤ y_j, ∑_j y_j = p.

3) Свойства и сложность

Set cover и p‑median, p‑center — NP‑трудные (комбинаторные) задачи. Для небольшого числа точек/кандидатов можно применять MILP-решатели (branch-and-bound).Непрерывный вариант (позиции s_j непрерывны, радиусы/мощности переменные) — нелинейная, в общем не выпуклая задача глобальной оптимизации.

4) Методы решения

А. Аналитические и геометрические наблюдения (упрощённые случаи)

Для равномерного плотного покрытия бесконечной плоскости оптимальная схема равных кругов — гексагональная (шестиугольная) решётка; это даёт конструктивную схему при однородной нагрузке и одинаковых антеннах.Для p‑median в непрерывном случае (один центр, p=1) задача 1‑median (Weber problem): единственная точка, минимизирующая ∑ w_i ||p_i − s||, решается итеративно алгоритмом Вайзфельда (Weiszfeld).Для p‑center (минимакс) геометрические свойства позволяют выполнять поиск по радиусу R и проверять возможность покрытия через диск-покрытие (линейный поиск + проверка допустимости).

B. Точные численные методы

Mixed Integer Linear Programming (MILP): дискретизировать радиусы/уровни мощности и использовать бинарные переменные; применимо при конечном наборе кандидатов и ограниченных размерах.Mixed Integer Nonlinear Programming (MINLP): для нелинейной зависимости радиуса от мощности — решатели MINLP (BARON, Couenne) для малых инстансов.Для p‑median и p‑center существуют специализированные MILP‑формулировки и готовые решатели.

C. Эвристики и метаэвристики (практически всегда нужны для больших задач)

Greedy set cover: итеративно ставить антенну, покрывающую максимум оставшихся точек; аппроксимация ln n для set cover.Клистеризация + локальная оптимизация: разбить D на p кластеров (k‑means по весам), установить станцию в центроиде кластера и локально оптимизировать положение/мощность.Local search / Swap / Add‑Drop: начать с некоторого набора площадок и выполнять обмены (swap), добавления/удаления для улучшения.Metaheuristics: генетические алгоритмы, имитация отжига, табу‑поиск, particle swarm — хорошо работают для непрерывных позиций и параметров мощности.Комбинированные схемы: сначала грубая дискретизация + жадный выбор, затем непрерывная донастройка позиций с использованием градиентных методов или эвристик.

D. Специализированные проверки и ускорения (геометрия)

Проверка покрытия множества точек конкретным набором дисков — задача вычисления объединённой площади дисков и теста вхождения точек; используется алгоритм сканирования/сегментов для оценки качества.Использование Voronoi‑разбиения: при фиксированных центрах можно быстро определить, какие точки к какому центру ближе; при оптимизации положения можно минимизировать функционал, зависящий от Voronoi‑кластеров (к‑means / Lagrange методы).При однородной плотности и равных радиусах рекомендуемая сетка размещения — гексагональная; это разумная эвристика как старт.

5) Геометрические упрощения и когда их уместно применять

Дискретизация территории (решётка) вместо непрерывной модели: уменьшает ИП‑размер, переводит задачу в Set Cover / MIP. Уместно, если территорию можно аппроксимировать сеткой с приемлемой точностью.Сведение к задачам на множествах точек (D): если нагрузка сосредоточена в узлах (города, вышки), проще работать с конечным набором точек, нежели с непрерывной областью.Округление/агрегация: агрегация близких пользователей в кластер с весом — существенно сокращает размер задачи.Считать антенны изотропными (круговое покрытие) и игнорировать интерференцию — даёт простую модель покрытия; подходит для ранних стадий проектирования, но плоха при высокой плотности.Плоская модель (евклидова метрика) вместо учёта рельефа/зданий — применима в открытой местности.Фиксация числа уровней мощности (дискретизация P) превращает MINLP в MILP.

6) Практический рабочий процесс (рекомендация)

Шаг 1: выбор модели (точечный спрос vs непрерывная область; дискретные площадки vs свободные позиции; учитывать/не учитывать интерференцию).Шаг 2: предобработка: агрегация точек, генерация кандидатов, дискретизация мощностей.Шаг 3: применять быструю эвристику (greedy / кластеризация + k‑means) для получения начального решения.Шаг 4: локальная оптимизация (swap, continuous refinement: градиент для положений антенн, Weiszfeld‑типные итерации или метод Ньютона при дифференцируемом функционале).Шаг 5: при необходимости — запуск метаэвристики (GA/SA) для поиска глобально лучшего решения.Шаг 6: верификация с более точной моделью распространения и учёт помех, затем итеративная корректировка.

7) Примеры специальных упрощений/решений

Если нужно минимальное число антенн однотипных радиусов r для покрытия дискретного множества точек — задача set cover: применим жадный алгоритм (good practical performance) или ILP для точного решения малыми размерами.Если число антенн фиксировано p и требуется минимизировать максимальное расстояние (p‑center) — можно бинарно искать R и для заданного R проверить существование покрытия (бипартидная проверка/сет‑покрытие с радиусом R).Для непрерывного размещения при больших p использовать к‑means для инициализации и затем локальное уточнение центров.

8) Заключение — компромиссы

Точная оптимизация (MILP/MINLP) обеспечивает лучшее качество, но масштабируется плохо; эвристики даёт быстрое и часто практически приемлемое решение.Геометрические упрощения (дискретизация, агрегация, круговая модель) позволяют перейти к решаемым формулировкам, но вводят аппроксимацию; важно проверять итоговое решение на более точной физической модели распространения.

Если хотите, могу:

Сформулировать конкретную MILP‑модель для вашего входного набора данных (дайте координаты точек спроса и кандидатов).Привести готовый пример кода (Python + PuLP/OR‑Tools / или эвристика k‑means + local search).Рассмотреть вариант с направленными (секторными) антеннами и учётом интерференции.