Целочисленное программирование

Целочисленное программирование (ЦП; англ. integer programming, IP) — это раздел математической оптимизации, в котором исследуются задачи, где некоторые или все переменные должны принимать только целочисленные значения.

Наиболее изученным частным случаем является целочисленное линейное программирование (ЦЛП; англ. integer linear programming, ILP), где целевая функция и ограничения являются линейными. В отличие от линейного программирования, где переменные могут принимать любые действительные значения, требование целочисленности делает задачи ЦП значительно более сложными для решения.

Целочисленное программирование находит широкое применение в экономике, логистике, планировании производства и других областях, где переменные по своей природе дискретны (например, количество произведённых единиц продукции или число работников).

Определение и терминология

Общая задача целочисленного линейного программирования может быть записана следующим образом:

Найти вектор $x$, который:

максимизирует (или минимизирует) $c^{T}x$

при условиях:

$Ax\le b$

$x\ge 0$

$x\in {\mathbb{\mathbb{Z}}}^n$ (все компоненты вектора $x$ — целые числа)

где $x$ — вектор переменных, $c$ и $b$ — векторы, а $A$ — матрица коэффициентов.

В зависимости от требований к переменным различают следующие типы задач:

• Полностью целочисленное программирование: все переменные должны быть целыми.
• Смешанно-целочисленное программирование (англ. mixed-integer programming, MIP): только часть переменных должны быть целочисленными.
• Булево (0-1) программирование: переменные принимают только значения 0 или 1, что позволяет моделировать логические решения типа «да/нет».

Ключевые свойства и сложность

Вычислительная сложность

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

Связь с линейным программированием (ЛП-релаксация)

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

1. Его можно найти значительно быстрее (за полиномиальное время).
2. Оптимальное значение целевой функции ЛП-релаксации даёт оценку (верхнюю границу для задачи максимизации и нижнюю для минимизации) для оптимального значения исходной целочисленной задачи.

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

Свойство полной унимодулярности

Существует важный класс задач ЦЛП, которые решаются так же легко, как и их ЛП-релаксации. Это задачи, в которых матрица ограничений $A$ является полностью унимодулярной (то есть определитель любой её квадратной подматрицы равен 0, +1 или −1). Если матрица $A$ полностью унимодулярна, а вектор $b$ целочисленный, то все вершины многогранника допустимых решений ЛП-релаксации автоматически будут целочисленными. Следовательно, решение, найденное симплекс-методом, будет целочисленным. Примерами таких задач являются транспортная задача и задача о назначениях.

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

Для решения общих задач ЦП, не обладающих свойством полной унимодулярности, разработаны точные методы, основанные на идеях неявного перебора.

• Метод ветвей и границ (англ. Branch and Bound) — основной точный метод, основанный на систематическом разбиении множества допустимых решений на подмножества (ветвление) и отсечении тех подмножеств, которые заведомо не содержат оптимального решения. Для оценки перспективности подмножеств используется ЛП-релаксация.

• Метод отсекающих плоскостей (метод Гомори; англ. Cutting Plane Method) — итеративный подход, который последовательно добавляет к задаче новые линейные ограничения («отсечения»). Эти отсечения «отрезают» дробные решения ЛП-релаксации, не затрагивая ни одного допустимого целочисленного решения, постепенно приближая область допустимых решений ЛП-релаксации к выпуклой оболочке целочисленных решений.

Современные решатели, как правило, используют гибридные алгоритмы, такие как метод ветвей и отсечений (англ. Branch and Cut), который объединяет преимущества обоих подходов.

Примеры и области применения

Целочисленное программирование позволяет моделировать множество классических задач комбинаторной оптимизации.

• Задача о рюкзаке: классическая задача 0-1 программирования, в которой нужно выбрать набор предметов с максимальной суммарной ценностью, не превышая при этом ограничение на общий вес.
• Задача коммивояжёра: задача поиска кратчайшего маршрута, проходящего через заданный набор городов. Может быть сформулирована как задача целочисленного программирования, где переменные отвечают за включение рёбер графа в итоговый маршрут.

Благодаря своей гибкости, ЦП является одним из наиболее востребованных инструментов в исследовании операций и находит применение в таких областях, как:

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

См. также

• Линейное программирование
• Метод ветвей и границ