EssayAI
Блог
Блог
Математика и алгоритмы

Метод ветвей и границ в целочисленном программировании

8 ноября 2026Время чтения: 8 минут
#метод ветвей и границ#целочисленное программирование#оптимизация#линейное программирование#LP релаксация
Метод ветвей и границ в целочисленном программировании

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

Постановка задачи и смысл целочисленности

Пусть xx и yy - количество изделий двух видов, а прибыль от единицы равна соответственно 3 и 2 условным единицам. Требуется найти

max⁡z=3x+2y\max z=3x+2y

при ограничениях ресурсов

2x+y≤4,x+2y≤4,x,y∈Z≥0.2x+y\le 4,\qquad x+2y\le 4,\qquad x,y\in\mathbb Z_{\ge 0}.

Первое изделие расходует две единицы первого ресурса и одну второго; второе - наоборот. Каждого ресурса имеется четыре единицы. Пара (2,0)(2,0) допустима: расходы равны четырём и двум, прибыль - шести. Но сразу утверждать, что лучшего плана нет, нельзя: это только найденный кандидат. Нужна оценка всех остальных планов.

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

LP-релаксация даёт верхнюю границу

Сначала временно разрешим xx и yy быть любыми неотрицательными числами. Полученная задача называется LP-релаксацией. Её допустимая область содержит все целочисленные планы и, кроме них, дробные точки. Поэтому при максимизации оптимум релаксации не меньше истинного целого оптимума: это верхняя граница, а не обязательно достижимая целая прибыль.

Пересечение двух ресурсных прямых находится из системы 2x+y=42x+y=4, x+2y=4x+2y=4: получаем x=y=4/3x=y=4/3. Там прибыль равна 20/3≈6,6720/3\approx 6{,}67. Эта точка оптимальна для релаксации: взвесим первое ограничение коэффициентом 4/34/3, второе - 1/31/3 и сложим. Получится 3x+2y≤20/33x+2y\le 20/3, причём в точке пересечения равенство достигается. Так оценка проверяется независимо от графика.

Допустимая область с целыми точками: LP-оптимум 20/3 и целочисленный оптимум 6
Допустимая область с целыми точками: LP-оптимум 20/3 и целочисленный оптимум 6

Дробный план нельзя принимать как ответ исходной задачи. Округление (4/3,4/3)(4/3,4/3) до (1,1)(1,1) допустимо, но прибыль 5, тогда как план (2,0)(2,0) приносит 6. В другой задаче округление может даже нарушить ограничения. Разницу между значением релаксации и целым оптимумом называют абсолютным разрывом: здесь он составляет 20/3−6=2/320/3-6=2/3.

Ветвление по дробной переменной

В корне дерева LP-решение имеет x=4/3x=4/3. Любое целое xx удовлетворяет ровно одному из условий x≤1x\le 1 или x≥2x\ge 2. Добавим первое условие в левую подзадачу, второе - в правую. Дробная точка корня исключается из обеих ветвей, но ни один исходный целый план не теряется. Каждая ветвь наследует все исходные ограничения.

Золотой маркер проходит от LP-релаксации к ветви x ≥ 2: целое решение со значением 6 позволяет сравнить рекорд с верхней границей другой ветви.

Для произвольного дробного значения xj∗x_j^* аналогичное разбиение задают условиями xj≤⌊xj∗⌋x_j\le\lfloor x_j^*\rfloor и xj≥⌈xj∗⌉x_j\ge\lceil x_j^*\rceil. Квадратные скобки здесь обозначают округление вниз и вверх. Выбор дробной переменной и порядок обхода могут менять размер дерева, но не правило сохранения всех целых кандидатов.

Решаем обе подзадачи

В левой ветви x≤1x\le 1. Её LP-оптимум равен 66 и достигается в дробной точке (1,3/2)(1,3/2). Доказать границу можно из равенства 3x+2y=(x+2y)+2x3x+2y=(x+2y)+2x: используя x+2y≤4x+2y\le4 и x≤1x\le1, получаем 3x+2y≤63x+2y\le6. Таким образом, целая прибыль в этой ветви не может превысить 6.

В правой ветви x≥2x\ge2. Из 2x+y≤42x+y\le4 и y≥0y\ge0 следует x=2x=2, y=0y=0. Это решение целое, допустимое и имеет значение 6. Оно становится рекордом - лучшим найденным допустимым целым решением. Его значение служит нижней границей глобального максимума: оптимум не может быть меньше уже достигнутого результата.

Теперь сравнение завершает поиск. Слева верхняя граница равна 6, справа найден допустимый план со значением 6. Левая ветвь не способна улучшить рекорд, поэтому её можно отсечь. Ответ: z∗=6z^*=6 при (x,y)=(2,0)(x,y)=(2,0). Если требуется перечислить все оптимальные планы, ветви с границей, равной рекорду, нельзя автоматически отбрасывать: в них могут находиться другие решения с той же прибылью.

Порядок обработки узлов в этом примере выбран для удобства: сначала мы нашли целый план в правой ветви, а затем сравнили с ним левую оценку. Если начать слева, её дробное решение не будет рекордом и ветвь придётся сохранить открытой либо разделить ещё раз. Позднее найденный план справа всё равно позволит закрыть оставшиеся узлы с оценкой не выше 6. Порядок влияет на объём работы, но не превращает допустимый план в доказанный оптимум без проверки границ.

Когда узел можно закрыть

Для задачи на максимум стандартные причины завершить обработку узла таковы:

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

Иначе узел ветвят дальше. До появления первого допустимого целого плана отсечение по рекорду недоступно: дробная точка релаксации сама по себе рекордом не является. Если нужна только одна оптимальная точка, равенство границы и рекорда достаточно для отсечения; если нужен полный набор оптимумов, равенство обрабатывают отдельно.

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

Как читать дерево и оценивать разрыв

Узел - это подзадача вместе с ограничениями, накопленными по пути от корня. Рёбра - дополнительные условия, а число у узла - оценка его оптимума, полученная из релаксации. Нельзя сравнивать границы, забывая, к каким ветвям они относятся. Когда все узлы закрыты и рекорд существует, он является доказанным оптимумом; если все узлы закрыты без рекорда, исходная целочисленная модель несовместна.

При досрочной остановке по времени рекорд остаётся допустимым решением, но не обязательно оптимальным. Лучшая верхняя граница среди открытых узлов вместе с рекордом ограничивает неизвестный оптимум. Например, до завершения корня в нашей задаче допустимое значение 6 и LP-граница 20/320/3 дают интервал [6,20/3][6,20/3]. Абсолютный разрыв здесь 2/32/3; относительный разрыв зависит от принятого определения и знаменателя, поэтому его нужно читать вместе с документацией решателя.

Практика и связь с другими методами

Ветвление не гарантирует маленького дерева: в худшем случае приходится исследовать экспоненциально много узлов. Качество LP-оценок, выбор переменной, порядок узлов и раннее нахождение хорошего рекорда сильно влияют на время. Современные решатели также используют отсекающие плоскости и эвристики; описание сочетания LP-границ и ветвления есть в документации SCIP. В вычислениях с плавающей точкой проверяют допуски решателя, а не сравнивают дробные значения с целыми без погрешности.

Та же стратегия применяется к задаче коммивояжёра, но там ветви могут задаваться включением или исключением ребра, а границу получают иначе. Для некоторых дискретных моделей удобнее динамическое программирование: оно переиспользует ответы перекрывающихся подзадач. Например, задача о рюкзаке допускает табличное решение, тогда как ветви и границы используют оценки для исключения областей поиска. Выбор зависит от структуры модели и ограничений ресурсов.

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

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

Частые ошибки

  • Округлять LP-оптимум и считать его доказанным ответом. Округлённая точка может быть недопустимой или неоптимальной.
  • Путать рекорд с границей релаксации. Рекорд обязан быть допустимым целым решением, а LP-оценка может быть дробной.
  • Менять знак отсечения при минимизации. Сначала определите, ограничивает ли число результат сверху или снизу.
  • Терять часть решений при разбиении. Ветви должны покрывать все целые значения выбранной переменной и наследовать ограничения родителей.
  • Объявлять досрочный рекорд оптимальным. Пока живой узел может его улучшить, доказательства нет.

FAQ

Нужно ли решать LP в каждом узле?
В классическом варианте используют LP-релаксацию каждого рассматриваемого узла, хотя на практике узел иногда закрывается предварительными проверками, а оценки могут усиливаться другими методами.

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

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

Коротко

LP-релаксация расширяет допустимое множество и даёт оценку; ветвление делит целые решения на подзадачи; рекорд позволяет отсекать те из них, которые не улучшат ответ. В примере граница корня равна 20/320/3, а рекорд и граница оставшейся ветви равны 6, поэтому максимум доказан.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Метод минимального элемента: транспортная задача

Метод минимального элемента: транспортная задача

Метод минимального элемента в транспортной задаче: пошаговый алгоритм начального плана, таблица тарифов, критерий оптимальности. Примеры и частые ошибки.

17 июня 20266 минут
Метод ветвей и границ: задача коммивояжёра по шагам

Метод ветвей и границ: задача коммивояжёра по шагам

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

24 марта 20267 минут
Метод угловых точек в линейном программировании

Метод угловых точек в линейном программировании

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

8 ноября 20268 минут
Экономико-математические методы анализа: виды и пример

Экономико-математические методы анализа: виды и пример

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

7 ноября 20269 минут
Метод Ньютона в оптимизации: формула и пример

Метод Ньютона в оптимизации: формула и пример

Метод Ньютона для поиска минимума: как построить квадратичную модель, вычислить шаг по градиенту и гессиану и проверить условия сходимости на примере.

8 ноября 20268 минут
Бинарный поиск по ответу: метод и примеры задач

Бинарный поиск по ответу: метод и примеры задач

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

11 июня 20267 минут