---
title: "Методы ветвей и границ"
source: "https://systems-analysis.info/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%B2%D0%B5%D1%82%D0%B2%D0%B5%D0%B9_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86"
wiki: "systems-analysis.info/wiki"
article: "Методы_ветвей_и_границ"
language: "ru"
categories:
  - "Категория:Russian"
  - "Категория:Исследование операций"
revision_id: 296
wiki_created_at: 2026-09-06T22:06:45Z
wiki_modified_at: 2026-09-06T22:06:45Z
downloaded_at: 2026-09-07T22:18:55Z
---

# Методы ветвей и границ

**Метод ветвей и границ** (англ. *Branch and Bound*, сокр. **B&B** или **BnB**) — это общая парадигма построения точных алгоритмов для решения задач дискретной и комбинаторной оптимизации, в частности NP-трудных задач<sup>[\[1\]](https://systems-analysis.info/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%B2%D0%B5%D1%82%D0%B2%D0%B5%D0%B9_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86#cite_note-en-wiki-bnb-1)</sup>. Метод представляет собой стратегию направленного перебора, в которой всё множество допустимых решений последовательно разбивается на подмножества (**ветвление**), и для каждого из них вычисляются оценки (**границы**) значения целевой функции. Эти оценки позволяют отбрасывать (отсекать) те подмножества, которые заведомо не содержат оптимальных решений, что существенно сокращает пространство поиска<sup>[\[2\]](https://systems-analysis.info/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%B2%D0%B5%D1%82%D0%B2%D0%B5%D0%B9_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86#cite_note-ru-wiki-bnb-2)</sup>.

Метод был впервые предложен А. Лэнд и А. Дойг в 1960 году для решения задач [целочисленного программирования](https://systems-analysis.info/wiki/%D0%A6%D0%B5%D0%BB%D0%BE%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 "Целочисленное программирование")<sup>[\[3\]](https://systems-analysis.info/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%B2%D0%B5%D1%82%D0%B2%D0%B5%D0%B9_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86#cite_note-land-doig-1960-3)</sup>. С тех пор он стал одним из наиболее фундаментальных подходов в [исследовании операций](https://systems-analysis.info/wiki/%D0%98%D1%81%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BE%D0%BF%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D0%B9 "Исследование операций") и компьютерных науках. Ключевая особенность метода — его гибкость: он является не конкретным алгоритмом, а высокоуровневой стратегической схемой (фреймворком), адаптивной к структуре решаемой задачи.

## Ключевые компоненты метода

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

- **Ветвление** (англ. *Branching*) — это процесс рекурсивного разделения текущего множества допустимых решений $S_{i}$ на несколько меньших, как правило, непересекающихся подмножеств $S_{i1},S_{i2},\ldots,S_{ik}$. Каждое такое подмножество соответствует новой подзадаче и представляется в виде дочернего узла в дереве поиска. Например, в задачах целочисленного программирования ветвление часто производят по переменной, имеющей дробное значение в решении ЛП-релаксации.

<!-- -->

- **Оценка границ** (англ. *Bounding*) — для каждого узла дерева поиска (т.е. для каждой подзадачи) вычисляется оценка значения целевой функции. Для задачи минимизации это **нижняя граница** (*lower bound*), которая является гарантированной оценкой снизу для любого решения в данном подмножестве. Чаще всего эта оценка получается путём решения *релаксации* исходной подзадачи — упрощённой версии, в которой некоторые сложные ограничения (например, целочисленности) временно игнорируются. Наиболее распространённой является ЛП-релаксация.

<!-- -->

- **Отсечение** (англ. *Pruning*) — это процесс исключения из рассмотрения узлов (и соответствующих им целых поддеревьев), которые заведомо не могут содержать оптимального решения. Узел отсекается в одном из следующих случаев:

1.  **Отсечение по границе**: Нижняя граница для данного узла оказывается не лучше (т.е. больше или равна для задачи минимизации), чем значение лучшего на данный момент найденного допустимого решения, называемого **рекордом** (*incumbent*).
2.  **Отсечение по допустимости**: Решение релаксации узла является допустимым для исходной задачи (например, все переменные целочисленны). Это решение сравнивается с текущим рекордом и, если оно лучше, рекорд обновляется. Дальнейшее ветвление из этого узла не требуется.
3.  **Отсечение по неразрешимости**: Подзадача, соответствующая узлу, не имеет допустимых решений.

## Общий алгоритм

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

1.  **Инициализация:** Найти начальное допустимое решение (например, с помощью эвристики) и установить его значение как начальную верхнюю границу (рекорд) $U$. Создать очередь активных узлов $Q$, содержащую корневой узел (исходную задачу).
2.  **Основной цикл:** Пока очередь $Q$ не пуста:
    - Выбрать узел из $Q$ в соответствии со стратегией поиска (например, поиск в глубину или по наилучшей оценке).
    - Решить релаксацию для этого узла, получив нижнюю границу $L$.
    - **Отсечь** узел, если $L \geq U$.
    - Если решение релаксации допустимо для исходной задачи, обновить рекорд: $U\leftarrow L$.
    - Если узел не отсечён и решение не является допустимым, выполнить **ветвление**, разделив его на дочерние узлы, и добавить их в очередь $Q$.
3.  **Завершение:** Когда очередь $Q$ становится пустой, алгоритм завершается. Найденное решение, соответствующее рекорду $U$, является глобально оптимальным.

## Ключевые свойства и теоремы

- **Корректность и сходимость:** Алгоритм гарантированно находит глобально оптимальное решение за конечное число шагов, если множество допустимых решений конечно, а процедура ветвления является конвергентной (то есть, при рекурсивном разбиении подмножества «стягиваются» к точкам)<sup>[\[4\]](https://systems-analysis.info/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%B2%D0%B5%D1%82%D0%B2%D0%B5%D0%B9_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86#cite_note-conitzer-duke-4)</sup>.
- **Стратегия поиска:** Эффективность алгоритма сильно зависит от стратегии выбора следующего узла для ветвления (например, поиск в глубину, поиск в ширину, поиск по наилучшей оценке) и от выбора переменной для ветвления. Современные решатели часто используют гибридные стратегии<sup>[\[5\]](https://systems-analysis.info/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%B2%D0%B5%D1%82%D0%B2%D0%B5%D0%B9_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86#cite_note-maudet-danoy-2024-5)</sup>.

## Примеры

- **[Задача целочисленного программирования](https://systems-analysis.info/wiki/%D0%A6%D0%B5%D0%BB%D0%BE%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 "Целочисленное программирование")**: Классическое приложение метода. В качестве релаксации используется [линейное программирование](https://systems-analysis.info/wiki/%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 "Линейное программирование"). Ветвление происходит по дробной переменной $x_{j}$, создавая две подзадачи с дополнительными ограничениями $x_{j} \leq \lfloor x_{j}^{\ast}\rfloor$ и $x_{j} \geq \lceil x_{j}^{\ast}\rceil$.
- **Задача коммивояжёра**: Пространство решений — все возможные гамильтоновы циклы в графе. Ветвление может осуществляться по рёбрам (включить/исключить ребро из маршрута). В качестве нижних границ могут использоваться решения более простых задач, таких как задача о назначениях или построение минимального остовного дерева<sup>[\[6\]](https://systems-analysis.info/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%B2%D0%B5%D1%82%D0%B2%D0%B5%D0%B9_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86#cite_note-little-1963-6)</sup>.

## Связанные понятия и применения

- **Метод ветвей и отсечений** (*Branch-and-Cut*): Гибридный метод, объединяющий B&B с методом отсекающих плоскостей. На каждом узле дерева поиска, помимо решения релаксации, генерируются дополнительные неравенства (отсечения), которые усиливают нижнюю границу, что приводит к более эффективному отсечению ветвей.
- **Поиск с возвратом** (*Backtracking*): Метод ветвей и границ можно рассматривать как обобщение этого алгоритма для задач оптимизации.
- **Альфа-бета-отсечение**: Концептуальная аналогия, используемая в игровых деревьях для отсечения заведомо проигрышных ветвей.

## См. также

- [Целочисленное программирование](https://systems-analysis.info/wiki/%D0%A6%D0%B5%D0%BB%D0%BE%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 "Целочисленное программирование")
- [Комбинаторная оптимизация](https://systems-analysis.info/wiki/%D0%9A%D0%BE%D0%BC%D0%B1%D0%B8%D0%BD%D0%B0%D1%82%D0%BE%D1%80%D0%BD%D0%B0%D1%8F_%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F "Комбинаторная оптимизация")
- [Задача коммивояжёра](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D1%91%D1%80%D0%B0 "Задача коммивояжёра")
- [Оптимальное решение](https://systems-analysis.info/wiki/%D0%9E%D0%BF%D1%82%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B5_%D1%80%D0%B5%D1%88%D0%B5%D0%BD%D0%B8%D0%B5 "Оптимальное решение")
- [Исследование операций](https://systems-analysis.info/wiki/%D0%98%D1%81%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BE%D0%BF%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D0%B9 "Исследование операций")

## Примечания

1.  <span id="cite_note-en-wiki-bnb-1">[↑](https://systems-analysis.info/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%B2%D0%B5%D1%82%D0%B2%D0%B5%D0%B9_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86#cite_ref-en-wiki-bnb_1-0) Wikipedia contributors. (2025). Branch and bound. In *Wikipedia, The Free Encyclopedia*. Retrieved 2025-10-26, from <a href="https://en.wikipedia.org/wiki/Branch_and_bound" class="external free" rel="nofollow">https://en.wikipedia.org/wiki/Branch_and_bound</a></span>
2.  <span id="cite_note-ru-wiki-bnb-2">[↑](https://systems-analysis.info/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%B2%D0%B5%D1%82%D0%B2%D0%B5%D0%B9_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86#cite_ref-ru-wiki-bnb_2-0) Wikipedia contributors. (2023). Метод ветвей и границ. In *Русская Википедия*. Retrieved 2025-10-26, from <a href="https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ" class="external free" rel="nofollow">https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ</a></span>
3.  <span id="cite_note-land-doig-1960-3">[↑](https://systems-analysis.info/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%B2%D0%B5%D1%82%D0%B2%D0%B5%D0%B9_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86#cite_ref-land-doig-1960_3-0) Land, A. H.; Doig, A. G. (1960). An automatic method of solving discrete programming problems. *Econometrica*, 28(3), 497–520. DOI: 10.2307/1910129. URL: <a href="https://www.jstor.org/stable/1910129" class="external free" rel="nofollow">https://www.jstor.org/stable/1910129</a></span>
4.  <span id="cite_note-conitzer-duke-4">[↑](https://systems-analysis.info/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%B2%D0%B5%D1%82%D0%B2%D0%B5%D0%B9_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86#cite_ref-conitzer-duke_4-0) Conitzer, V. (2008). *Solving (mixed) integer programs using branch and bound*. Duke University, Department of Computer Science. URL: <a href="https://courses.cs.duke.edu/spring08/cps296.2/branch_and_bound.pdf" class="external free" rel="nofollow">https://courses.cs.duke.edu/spring08/cps296.2/branch_and_bound.pdf</a></span>
5.  <span id="cite_note-maudet-danoy-2024-5">[↑](https://systems-analysis.info/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%B2%D0%B5%D1%82%D0%B2%D0%B5%D0%B9_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86#cite_ref-maudet-danoy-2024_5-0) Maudet, G.; Danoy, G. (2024). Search Strategy Generation for Branch and Bound Using Genetic Programming. *arXiv preprint arXiv:2412.09444*. DOI: 10.48550/arXiv.2412.09444. URL: <a href="https://arxiv.org/abs/2412.09444" class="external free" rel="nofollow">https://arxiv.org/abs/2412.09444</a></span>
6.  <span id="cite_note-little-1963-6">[↑](https://systems-analysis.info/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%B2%D0%B5%D1%82%D0%B2%D0%B5%D0%B9_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86#cite_ref-little-1963_6-0) Little, J. D. C.; Murty, K. G.; Sweeney, D. W.; Karel, C. (1963). An Algorithm for the Traveling Salesman Problem. *Operations Research*, 11(6), 972–989. DOI: 10.1287/opre.11.6.972. URL: <a href="https://dspace.mit.edu/bitstream/handle/1721.1/46907/branchboundmetho00litt.pdf" class="external free" rel="nofollow">https://dspace.mit.edu/bitstream/handle/1721.1/46907/branchboundmetho00litt.pdf</a></span>