Что есть база в математической оптимизации и моделировании бизнес процессов? Целевая функция, ограничения, алгоритмы решения — безусловно, но есть ещё модели. Насмотренность, портфель типовых моделей и умение распознавать их в задаче придают дополнительный импульс процессу решения сложных задач.

Рассмотрим набор из восьми классических постановок, которые нашли применение в решении широкого спектра задач. Материал будет полезен специалистам по математической оптимизации. Управленцы и менеджеры могут найти актуальные сценарии применения математической оптимизации для своих задач.

Введение

В одной из своих предыдущих работ Искусство математического моделирования кратко упомянул про “типовые модели”. Здесь мы рассмотрим более широкий список таких моделей — с их постановками, примерами применения и текущими тенденциями в соответствующих задачах.

Решить большие оптимизационные задачи не всегда удаётся «в лоб» с помощью стандартного набора алгоритмов или солверов. Один из вариантов перевода такой модели в практическое русло — декомпозиция задачи. Портфель типовых моделей позволяет специалисту выстроить ансамбль моделей и выполнить эту декомпозицию эффективно.

Мне встречались описания вакансий, где в требованиях указывается специфический навык: способность находить среди множества запутанных условий ту самую типовую модель. Это абстрактное, нестандартизированное умение, но интуитивно спрос на него существует.

Речь в статье пойдёт о наборе таких классических паттернов в математической оптимизации (с уклоном на линейные постановки).

Задача о рюкзаке (The Knapsack Problem)

Задача о рюкзаке — это фундаментальная задача комбинаторной оптимизации, в которой необходимо выбрать подмножество предметов с максимальной суммарной ценностью, не превышая ограничение по суммарному весу. В наиболее распространенной форме 0/1 рюкзака каждый предмет либо выбирается целиком, либо нет. Стандартная формулировка в виде задачи целочисленного линейного программирования (ЦЛП) выглядит следующим образом:

Обозначения:

• — общее количество предметов;

• — ценность (стоимость) -го предмета;

• — вес -го предмета;

• — максимальная грузоподъёмность рюкзака (ограничение по весу);

• — бинарная переменная выбора предмета, 1 если -ый предмет выбран, 0 в противном случае.

Пояснение к структуре:

1. Целевая функция: мы хотим максимизировать суммарную ценность выбранных предметов.

2. Ограничение по весу: суммарный вес выбранных предметов не должен превышать грузоподъёмность рюкзака .

3. Ограничения на переменные: каждый предмет можно взять только целиком или не брать вовсе, что и определяет тип задачи как 0/1 рюкзак.

Примеры применения

• Оптимизация инвестиционного портфеля. В финансах модель рюкзака применяется для формирования портфеля ценных бумаг. Каждый актив характеризуется ожидаемой доходностью (ценность) и риск-метрикой, например, значением Value at Risk (вес). Задача инвестора — максимизировать доходность при ограничении на совокупный риск портфеля (аналог вместимости рюкзака). Современные алгоритмы позволяют решать многомерные и стохастические варианты этой задачи для крупных фондов.

• Динамическое выделение ресурсов в облачных вычислениях. В дата-центрах задача возникает при распределении ограниченных вычислительных ресурсов (CPU, память, пропускная способность) между конкурирующими задачами или виртуальными машинами. Каждая задача имеет «ценность» (приоритет, SLA) и «вес» (потребление ресурсов). Оптимальное распределение максимизирует общую производительность или прибыль провайдера услуг.

Современные тенденции

Направлениями активных исследований являются разработка эффективных эвристик и метаэвристик для многомерных и нелинейных вариантов задачи, а также интеграция с машинным обучением. Алгоритмы на основе обучения с подкреплением (Reinforcement Learning) используются для принятия решений в динамических средах, где параметры задачи меняются со временем. Продолжается работа над специализированными алгоритмами, превосходящими по скорости общие решатели ЦЛП для крупномасштабных экземпляров задачи.

Задача о назначениях (The Assignment Problem)

Это задача поиска паросочетания минимальной (или максимальной) суммарной стоимости между двумя равномощными множествами. Например, между работниками и заданиями, где каждый элемент одного множества назначается ровно одному элементу другого (пример постановки разбирал здесь). Формулировка ЦЛП:

Обозначения:

Пояснение к структуре:

1. Целевая функция: суммарная стоимость всех назначений, которую требуется минимизировать.

2. Ограничение по строкам: гарантирует, что каждый элемент первого множества назначен ровно на один элемент второго множества.

3. Ограничение по столбцам: гарантирует, что каждый элемент второго множества выполняется ровно одним элементом первого множества.

Классический алгоритм решения такой задачи — Венгерский метод.

Примеры применения

• Распределение вычислительных задач в распределенных системах. В гетерогенных вычислительных кластерах (например, для обучения больших моделей ИИ) необходимо назначить тысячи подзадач на серверы с разной производительностью CPU/GPU, памятью и топологией сети. Оптимальное назначение минимизирует общее время выполнения (makespan) и межсерверный трафик.

• Планирование хирургических операций. В крупных больницах модель используется для оптимального назначения хирургических бригад (учитывая специализацию и квалификацию) на операции, а операционных залов на временные слоты. Цель минимизировать простои дорогостоящих ресурсов и общее время ожидания пациентов, учитывая различную продолжительность операций. В 2024 году под эгидой сообщества EURO проводилось соревнование по решению этой задачи. Можно попрактиковать навыки на данных этого конкурса.

Современные тенденции

Актуальные исследования сосредоточены на решении динамических и стохастических версий задачи, где информация о задачах или ресурсах становится известной или меняется в реальном времени. Широко изучается применение языковых моделей (LLM) для автоматического преобразования описания бизнес-задачи на естественном языке в формальную постановку задачи о назначениях, что упрощает её использование специалистами-нематематиками.

Раскраска графов (The Graph Coloring Problem)

Задача состоит в присвоении цветов вершинам графа таким образом, чтобы любые две смежные вершины имели разные цвета, а общее количество использованных цветов было минимальным (хроматическое число). Одна из возможных формулировок ЦЛП:

Обозначения:

Пояснение к структуре:

1. Целевая функция: найти минимальное количество цветов , достаточное для корректной раскраски графа.

2. Ограничение на присвоение цвета: гарантирует, что каждой вершине присвоен ровно один цвет.

3. Ограничение на смежность: обеспечивает правильность раскраски. Никакие две смежные вершины не могут иметь одинаковый цвет.

4. Связь между переменными и : цвет считается использованным, если хотя бы одной вершине присвоен этот цвет.

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

Примеры применения

• Составление расписания телекоммуникационных каналов. В беспроводных сетях (Wi-Fi, сотовые) необходимо назначить частотные каналы базовым станциям так, чтобы станции, работающие на соседних каналах, не создавали взаимных помех. Граф строится по зонам покрытия станций, а цвета соответствуют доступным частотам. Задача усложняется ограниченным спектром и различными требованиями к пропускной способности.

• Регистровая аллокация в компиляторах. Это классическое применение, где переменные программы представляются вершинами графа. Ребро между двумя вершинами проводится, если соответствующие переменные одновременно «живы» (используются) в программе. Цвета соответствуют физическим регистрам процессора. Эффективная раскраска позволяет минимизировать количество обращений к медленной оперативной памяти.

Современные тенденции

Основной фокус на создании точных и эвристических алгоритмов для работы с очень большими графами (социальные сети, веб-граф). Получают развитие гибридные методы, комбинирующие эвристики, машинное обучение для предсказания перспективных ветвей поиска (machine learning guided search) и техники сокращения графа (reduction techniques).

Задача коммивояжера (The Traveling Salesman Problem, TSP)

TSP заключается в нахождении кратчайшего гамильтонова цикла — маршрута, проходящего через все заданные города ровно по одному разу с возвратом в начальный пункт (вариацию задачи разбирал здесь). Существует несколько формулировок ЦЛП, одна из распространенных использует переменные для ребер и ограничения на исключение подциклов (subtour elimination constraints). Для множества городов и расстояний :

Обозначения:

Пояснение к структуре:

1. Целевая функция: минимизируется общая длина (стоимость) маршрута, т.е. сумма расстояний по всем рёбрам, включённых в маршрут.

2. Ограничения на исходящие рёбра: из каждого города выходит ровно одно ребро. Коммивояжёр должен уехать из каждого города ровно один раз.

3. Ограничения на входящие рёбра: в каждый город входит ровно одно ребро. Коммивояжёр должен приехать в каждый город ровно один раз.

4. Ограничения на исключение подциклов: это ключевое ограничение, предотвращающее появление отдельных замкнутых циклов (подциклов), не охватывающих все города. Для любого подмножества городов (не пустого, не всего множества и не одноэлементного) количество рёбер маршрута, соединяющих города внутри , не должно превышать . Это гарантирует, что внутри не может образоваться отдельный цикл — все города должны быть частью одного большого цикла. Число таких ограничений экспоненциально растёт с , что делает задачу сложной для прямого решения методами линейного программирования.

Комментарии:

• Из‑за огромного числа ограничений на подциклы (их ) на практике их добавляют итеративно: сначала решают задачу без них, затем проверяют решение на наличие подциклов и добавляют соответствующие ограничения для найденных подциклов, повторяя процесс до получения одного цикла. Реализацию разбирал в статье.

• Существуют другие способы исключения подциклов (например, с использованием дополнительных переменных «потенциалов» ), но приведённая выше является одной из самых классических и понятных.

Примеры применения

• Логистика «последней мили» и маршрутизация дронов. Помимо классического планирования маршрутов для фур, TSP и её обобщения (Vehicle Routing Problem, VRP) критически важны для оптимизации доставки дронами или робо-курьерами в условиях плотной городской застройки. Учитываются ограничения по весу, времени полета батареи, зоны с ограниченным доступом.

• Проектирование и тестирование микрочипов. В электронной промышленности задача возникает при определении оптимальной траектории движения лазера для резки или сверления печатных плат, а также при планировании порядка тестирования тысяч микросхем на одном кристалле кремния для минимизации времени обработки.

Современные тенденции

Область переживает революцию благодаря интеграции с глубоким обучением. Графовые нейронные сети (GNN) и обучение с подкреплением используются для генерации качественных эвристических решений за доли секунды, что важно для динамической маршрутизации. Исследуются также квантовые и квантово-вдохновленные алгоритмы для поиска приближенных решений сложных экземпляров.

Задача о покрытии множества (The Set Covering Problem)

Дано универсальное множество и семейство его подмножеств , каждое с определенной стоимостью. Требуется выбрать подсемейство минимальной суммарной стоимости, объединение которого покрывает все элементы . Формулировка ЦЛП:

Расшифровка обозначений:

Пояснение к структуре:

1. Целевая функция: найти подсемейство подмножеств минимальной суммарной стоимости, объединение которых покрывает все элементы .

2. Ограничения покрытия: гарантируют, что каждый элемент универсального множества покрыт хотя бы одним выбранным подмножеством.

Комментарии:

• При решении расслабленной задачи (когда ) оптимальное значение целевой функции даёт нижнюю оценку для целочисленной задачи.

• Из‑за сложности задачи часто используются жадные алгоритмы, которые на каждом шаге выбирают подмножество с наилучшим соотношением «стоимость / число новых покрываемых элементов».

• Задача о покрытии тесно связана с задачей о точном покрытии (где каждый элемент должен покрываться ровно один раз, рассмотрим далее) и задачей о максимальном покрытии (где нужно покрыть максимальное число элементов фиксированным числом подмножеств).

Примеры применения

• Размещение инфраструктуры экстренного реагирования. Определение минимального количества и мест размещения пожарных депо, станций скорой помощи или пунктов выдачи гуманитарной помощи для обеспечения покрытия всех районов в пределах заданного времени доезда. Модели часто дополняются вероятностными ограничениями (Maximal Covering Location Problem).

• Минимизация тестов в аппаратном и программном обеспечении. В инженерии качества задача возникает при выборе минимального набора тестовых случаев, который покрывает все требуемые функциональные сценарии, состояния системы или участки кода (покрытие ветвей).

Современные тенденции

Разрабатываются эффективные эвристики и приближенные алгоритмы для крупномасштабных задач, таких как покрытие в сетях 5G/6G (размещение базовых станций) и задачи лотерейного покрытия (lotto set covering). Растет интерес к robust и stochastic set covering, учитывающим неопределенность в параметрах задачи, например, в спросе на услуги.

Задача разбиения множества (The Set Partitioning Problem)

Близкая к задаче о покрытии, но с более строгим условием: каждый элемент универсального множества должен быть покрыт ровно одним выбранным подмножеством. Это ключевое отличие делает модель идеальной для задач, где ресурсы нельзя делить или дублировать. Пример реальной задачи разбирал в статье Разделяй и запускай: делим тестовый стенд между департаментами. Формулировка ЦЛП:

Обозначения:

Пояснение к структуре:

1. Целевая функция: найти подсемейство подмножеств минимальной суммарной стоимости, объединение которых образует разбиение множества .

2. Ограничения разбиения: гарантируют, что каждый элемент универсального множества принадлежит ровно одному выбранному подмножеству.

Комментарии:

• В отличие от задачи о покрытии, задача разбиения может не иметь допустимого решения. Например, если в семействе нет подмножеств, содержащих какой‑то элемент , или если все подмножества, содержащие , пересекаются с другими обязательными подмножествами так, что условие «ровно один раз» невозможно выполнить.

• Любое допустимое решение задачи разбиения является также допустимым решением задачи покрытия (но не наоборот). Поэтому оптимальное значение целевой функции для задачи разбиения всегда не меньше, чем для задачи покрытия на тех же данных.

Примеры применения

• Планирование экипажей в авиации (Crew Pairing). Это одно из самых известных и экономически значимых применений. Множество рейсов (элементы U) необходимо разбить на «вахты» (pairings) — последовательности рейсов, выполняемые одним экипажем в рамках рабочей смены с соблюдением норм отдыха. Каждая возможная вахта это подмножество . Задача — выбрать набор вахт (подмножеств) минимальной стоимости, покрывающий все рейсы ровно по одному разу.

• Формирование избирательных округов. При проектировании границ избирательных округов территория (набор избирательных участков) должна быть разбита на округа так, чтобы каждый участок принадлежал ровно одному округу, с соблюдением условий по численности населения и компактности формы.

Современные тенденции

Основные усилия направлены на решение стохастических и динамических версий задачи, например, для учета отмен и задержек рейсов при планировании экипажей. Используются методы декомпозиции (column generation) в сочетании с машинным обучением для ускорения генерации перспективных столбцов (вахт) в крупномасштабных задачах.

Транспортная задача (The Transportation Problem)

Частный и исторически один из первых случаев линейного программирования. Имеется m поставщиков с запасами и потребителей со спросом . Известна стоимость перевозки единицы груза от к . Необходимо найти план перевозок минимальной суммарной стоимости, удовлетворяющий спрос и предложение. Формулировка ЛП:

Обозначения:

Пояснение к структуре:

1. Целевая функция: найти план перевозок , минимизирующий общие транспортные расходы.

2. Ограничения по предложению: гарантируют, что весь запас каждого поставщика будет вывезен.

3. Ограничения по спросу: обеспечивают полное удовлетворение спроса каждого потребителя.

Комментарии:

• Условие баланса. Для существования допустимого решения необходимо выполнение условия баланса:

Если суммарное предложение не равно суммарному спросу, задача называется несбалансированной. Её можно привести к сбалансированной путём введения фиктивного поставщика или потребителя с нулевыми стоимостями перевозок.

• Несмотря на то что переменные могут быть дробными, транспортная задача всегда имеет оптимальное решение с целочисленными значениями, если все и целые. Это важное свойство упрощает практическое применение.

• Для решения транспортной задачи разработаны специализированные алгоритмы, более эффективные, чем общий симплекс‑метод:

  • метод северо‑западного угла (для построения начального опорного плана);

  • метод потенциалов (для поиска оптимального решения);

  • метод наименьшей стоимости (для улучшения начального плана).

• Модель применима не только к физическим перевозкам, но и к задачам распределения ресурсов, назначения мощностей, планирования производства и т.д.

• В статье Искусство создания эффективных математических моделей упоминал постановку с точки зрения отсутствия гэпа между вещественной и целочисленной постановки, что обеспечивает быструю сходимость к оптимальному целочисленному решению.

Примеры применения

• Балансировка нагрузки в энергосистемах. Задача применяется для оптимального распределения потоков электроэнергии между генерирующими станциями и узлами потребления с минимальными потерями в сети, учитывая переменную стоимость производства на разных типах станций (ТЭЦ, ГЭС, ВИЭ).

• Глобальная оптимизация цепочек поставок. Модель лежит в основе планирования потоков сырья, компонентов и готовой продукции между заводами, распределительными центрами и розничными точками по всему миру. В современных условиях она расширяется до многоэтапных, многопродуктовых моделей с учетом тарифов, квот и ограничений на пропускную способность.

Современные тенденции

Интеграция с системами реального времени на основе IoT-датчиков позволяет динамически обновлять параметры спроса и предложения. Развиваются устойчивые (sustainable) модели, включающие в целевую функцию минимизацию углеродного следа от перевозок.

Задача о максимальной клике (Maximum Clique Problem)

Клика — это подмножество вершин графа, все пары которых соединены ребрами. Задача заключается в нахождении клики максимального размера в данном графе. Формулировка ЦЛП на максимум:

Обозначения:

Пояснение к структуре:

1. Целевая функция: найти подмножество вершин максимального размера, образующее клику, т.е. максимизировать количество вершин, входящих в клику.

2. Ограничения на несмежность: гарантируют, что в клику не попадут две вершины, не соединённые ребром.

Комментарии:

• Иногда задачу формулируют через дополнение графа: поиск максимальной клики в графе эквивалентен поиску максимального независимого множества в дополнении графа .

• Хроматическое число. Размер максимальной клики () является нижней оценкой хроматического числа графа (): .

• Дей и Санков описывали задачу построения эволюционных деревьев как поиск максимальных клик в графе, где вершины представляют характеристики, а рёбра — возможность их совместной эволюции

Примеры применения

• Выявление сообществ и анализ влияния в социальных сетях. Максимальные клики могут соответствовать тесным, высокоинтерактивным группам пользователей (например, круг доверия). Их выявление используется для таргетированного маркетинга, обнаружения ботов или анализа распространения информации.

• Биоинформатика и анализ биологических сетей. В сетях белково-белкового взаимодействия (PPI) или генетических сетях клики часто соответствуют функциональным модулям или комплексам белков, совместно участвующим в определенном клеточном процессе. Их обнаружение помогает в понимании биологических механизмов.

Современные тенденции

Несмотря на вычислительную сложность, разрабатываются всё более эффективные точные алгоритмы (branch-and-bound) и эвристики для работы с большими реальными графами. Активно используются методы редукции графа (kernelization) и параллельные вычисления.

Заключение

Выбор базовой модели формирует фундамент для всего оптимизационного решения. Инвестиции в подбор типовых моделей на старте могут с лихвой оправдать затраты времени на разработку общего решения.

Сейчас ИИ‑ассистенты позволяют быстро получить обзор применяемых типовых моделей для решения той или иной задачи. Это углубляет экспертизу и помогает определить стратегию решения более эффективно. Однако комбинирование моделей в ансамбли для решения задач по‑прежнему остаётся в руках специалиста.

Представил восемь достаточно распространённых моделей. Спектр их применения широк, поэтому выделил современные тенденции по каждой из них. Никогда не знаешь, что пригодится в реальных условиях. Этот список позволит расширить арсенал инструментов или взглянуть на задачу с другой стороны.