Курсовая работа выбор параметров контроля с использованием метода динамического программирования и метода ветвей и границ.

Здравствуй, Хабр! Реализовывая различные алгоритмы для нахождения гамильтонова цикла с наименьшей стоимостью, я наткнулся на публикацию , предлагающую свой вариант. Попробовав в деле, я получил неправильный ответ:

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

Под катом вас будет ждать исправленный алгоритм и онлайн-калькулятор.

Сам метод, опубликованный Литтлом, Мерти, Суини, Кэрелом в 1963 г. применим ко многим NP-полным задачам, и представляет собой очень теоритеризованный материал, который без хороших знаний английского языка и математики сразу не применишь к нашей задаче коммивояжера.

Кратко о методе - это полный перебор всех возможных вариантов с отсеиванием явно неоптимальных решений.

Исправленный алгоритм, для нахождения действительно минимального маршрута

Алгоритм состоит из двух этапов:

Первый этап

Приведение матрицы затрат и вычисление нижней оценки стоимости маршрута r.

1. Вычисляем наименьший элемент в каждой строке (константа приведения для строки)
2. Переходим к новой матрице затрат, вычитая из каждой строки ее константу приведения
3. Вычисляем наименьший элемент в каждом столбце (константа приведения для столбца)
4. Переходим к новой матрице затрат, вычитая из каждого столбца его константу приведения.
Как результат имеем матрицу затрат, в которой в каждой строчке и в каждом столбце имеется хотя бы один нулевой элемент.
5. Вычисляем границу на данном этапе как сумму констант приведения для столбцов и строк (данная граница будет являться стоимостью, меньше которой невозможно построить искомый маршрут)

Второй (основной) этап

1.Вычисление штрафа за неиспользование для каждого нулевого элемента приведенной матрицы затрат.
Штраф за неиспользование элемента с индексом (h,k) в матрице, означает, что это ребро не включается в наш маршрут, а значит минимальная стоимость «неиспользования» этого ребра равна сумме минимальных элементов в строке h и столбце k.

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

2. Теперь наше множество S разбиваем на множества - содержащие ребро с максимальным штрафом(S w) и не содержащие это ребро(S w/o).
3. Вычисление оценок затрат для маршрутов, входящих в каждое из этих множеств.
а) Для множества S w/o все просто: раз мы не берем соответствующее ребро c максимальным штрафом(h,k), то для него оценка затрат равна оценки затрат множества S + штраф за неиспользование ребра (h,k)
б) При вычислении затрат для множества S w примем во внимание, что раз ребро (h,k) входит в маршрут, то значит ребро (k,h) в маршрут входить не может, поэтому в матрице затрат пишем c(k,h)=infinity, а так как из пункта h мы «уже ушли», а в пункт k мы «уже пришли», то ни одно ребро, выходящее из h, и ни одно ребро, приходящее в k, уже использоваться не могут, поэтому вычеркиваем из матрицы затрат строку h и столбец k. После этого приводим матрицу, и тогда оценка затрат для S w равна сумме оценки затрат для S и r(h,k), где r(h,k) - сумма констант приведения для измененной матрицы затрат.
4. Из всех неразбитых множеств выбирается то, которое имеет наименьшую оценку.

Так продолжаем, пока в матрице затрат не останется одна не вычеркнутая строка и один не вычеркнутый столбец.

Небольшая оптимизация - подключаем эвристику

Да, правда, почему бы нам не ввести эвристику? Ведь в алгоритме ветвей и границ мы фактически строим дерево, в узлах которого решаем брать ребро (h,k) или нет, и вешаем двух детей - Sw(h,k) и Sw/o(h,k). Но лучший вариант для следующей итерации выбираем только по оценке. Так давайте выбирать лучший не только по оценке, но и по глубине в дереве, т.к. чем глубже выбранный элемент, тем ближе он к концу подсчета. Тем самым мы сможем наконец дождаться ответа.

Теперь, собственно, об ошибках в той публикации

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

Доказательство

Вернемся к картинке в начале поста:

А вот решение с исправленным алгоритмом:

Ответ: путь:3=>4=>2=>1=>5=>3 длина: 41
Как видите, включая ребро 5:2 в решение будет ошибкой. Что и требовалось доказать

График сравнения метода ветвей и границ и потраченного времени для случайной таблицы от 5х5 до 10х10:


График максимального и минимального потраченного времени для матриц от 5х5 до 66х66.


Попробовать с подробным решением можно

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

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

Таблица 2

Таблица 3

Таблица 4

Изложим алгоритм Литтла на примере 1 предыдущего раздела. Повторно запишем матрицу:

Нам будет удобнее трактовать С ij как стоимость проезда из города i в город j. Допустим, что добрый мэр города j издал указ выплачивать каждому въехавшему в город коммивояжеру 5 долларов. Это означает, что любой тур подешевеет на 5 долларов, поскольку в любом туре нужно въехать в город j. Но поскольку все туры равномерно подешевели, то прежний минимальный тур будет и теперь стоить меньше всех. Добрый же поступок мэра можно представить как уменьшение всех чисел j-го столбца матрицы С на 5. Если бы мэр хотел спровадить коммивояжеров из j-го города и установил награду за выезд в размере 10 долларов, это можно было бы выразить вычитанием 10 из всех элементов j-й той строки. Это снова бы изменило стоимость каждого тура, но минимальный тур остался бы минимальным. Итак, доказана следующая лемма.

Вычитая любую константу из всех элементов любой строки или столбца матрицы С, мы оставляем минимальный тур минимальным.

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

Прочерки по диагонали означают, что из города i в город i ходить нельзя. Заметим, что сумма констант приведения по строкам равна 27, сумма по столбцам 7, сумма сумм равна 34.

Тур можно задать системой из шести подчеркнутых (выделенных другим цветом) элементов матрицы С, например, такой, как показано на табл. 2. Подчеркивание элемента означает, что в туре из i-го элемента идут именно в j-тый. Для тура из шести городов подчеркнутых элементов должно быть шесть, так как в туре из шести городов есть шесть ребер. Каждый столбец должен содержать ровно один подчеркнутый элемент (в каждый город коммивояжер въехал один раз), в каждой строке должен быть ровно один подчеркнутый элемент (из каждого города коммивояжер выехал один раз); кроме того, подчеркнутые элементы должны описывать один тур, а не несколько меньших циклов. Сумма чисел подчеркнутых элементов есть стоимость тура. На табл. 2 стоимость равна 36, это тот минимальный тур, который получен лексикографическим перебором.

Теперь будем рассуждать от приведенной матрицы на табл. 2. Если в ней удастся построить правильную систему подчеркнутых элементов, т.е. систему, удовлетворяющую трем вышеописанным требованиям, и этими подчеркнутыми элементами будут только нули, то ясно, что для этой матрицы мы получим минимальный тур. Но он же будет минимальным и для исходной матрицы С, только для того, чтобы получить правильную стоимость тура, нужно будет обратно прибавить все константы приведения, и стоимость тура изменится с 0 до 34. Таким образом, минимальный тур не может быть меньше 34. Мы получили оценку снизу для всех туров.

Теперь приступим к ветвлению. Для этого проделаем шаг оценки нулей. Рассмотрим нуль в клетке (1,2) приведенной матрицы. Он означает, что цена перехода из города 1 в город 2 равна 0. А если мы не пойдем из города 1 в город 2? Тогда все равно нужно въехать в город 2 за цены, указанные во втором столбце; дешевле всего за 1 (из города 6). Далее, все равно надо будет выехать из города 1 за цену, указанную в первой строке; дешевле всего в город 3 за 0. Суммируя эти два минимума, имеем 1+0=1: если не ехать «по нулю» из города 1 в город 2, то надо заплатить не меньше 1. Это и есть оценка нуля. Оценки всех нулей поставлены на табл. 5 правее и выше нуля (оценки нуля, равные нулю, не ставились).

Выберем максимальную из этих оценок (в примере есть несколько оценок, равных единице, выберем первую из них, в клетке (1,2)).

Итак, выбрано нулевое ребро (1,2). Разобьем все туры на два класса - включающие ребро (1,2) и не включающие ребро (1,2). Про второй класс можно сказать, что придется приплатить еще 1, так что туры этого класса стоят 35 или больше.

Что касается первого класса, то в нем надо рассмотреть матрицу на табл. 6 с вычеркнутой первой строкой и вторым столбцом.

Таблица 5

Таблица 7

Дополнительно в уменьшенной матрице поставлен запрет в клетке (2,1), т.к. выбрано ребро (1,2) и замыкать преждевременно тур ребром (2,1) нельзя. Уменьшенную матрицу можно привести на 1 по первому столбцу, так что каждый тур, ей отвечающий, стоит не меньше 35. Результат наших ветвлений и получения оценок показан на рис. 6.

Кружки представляют классы: верхний кружок - класс всех туров; нижний левый - класс всех туров, включающих ребро (1,2); нижний правый - класс всех туров, не включающих ребро (1,2). Числа над кружками - оценки снизу.

Продолжим ветвление в положительную сторону: влево - вниз. Для этого оценим нули в уменьшенной матрице C на табл. 7. Максимальная оценка в клетке (3,1) равна 3. Таким образом, оценка для правой нижней вершины на рис. 7 есть 35+3=38. Для оценки левой нижней вершины на рис. 7 нужно вычеркнуть из матрицы C еще строку 3 и столбец 1, получив матрицу C[(1,2), (3,1)] на табл. 8. В эту матрицу нужно поставить запрет в клетку (2,3), так как уже построен фрагмент тура из ребер (1,2) и (3,1), т.е. , и нужно запретить преждевременное замыкание (2,3). Эта матрица приводится по столбцу на 1 (табл. 9), таким образом, каждый тур соответствующего класса (т.е. тур, содержащий ребра (1,2) и (3,1)) стоит 36 и более.

Таблица 9

Таблица 11

Оцениваем теперь нули в приведенной матрице C[(1,2), (3,1)] нуль с максимальной оценкой 3 находится в клетке (6,5). Отрицательный вариант имеет оценку 38+3=41. Для получения оценки положительного варианта убираем строчку 6 и столбец 5, ставим запрет в клетку (5,6), см. табл. 10. Эта матрица неприводима. Следовательно, оценка положительного варианта не увеличивается (рис. 8).

Оценивая нули в матрице на табл. 10, получаем ветвление по выбору ребра (2,6), отрицательный вариант получает оценку 36+3=39, а для получения оценки положительного варианта вычеркиваем вторую строку и шестой столбец, получая матрицу на табл. 11.

В матрицу надо добавить запрет в клетку (5,3), ибо уже построен фрагмент тура и надо запретить преждевременный возврат (5,3). Теперь, когда осталась матрица 2х2 с запретами по диагонали, достраиваем тур ребрами (4,3) и (5,4). Мы не зря ветвились, по положительным вариантам. Сейчас получен тур: 1>2>6>5>4>3>1 стоимостью в 36. При достижении низа по дереву перебора класс туров сузился до одного тура, а оценка снизу превратилась в точную стоимость.

Итак, все классы, имеющие оценку 36 и выше, лучшего тура не содержат. Поэтому соответствующие вершины вычеркиваются. Вычеркиваются также вершины, оба потомка которой вычеркнуты. Мы колоссально сократили полный перебор. Осталось проверить, не содержит ли лучшего тура класс, соответствующий матрице С , т.е. приведенной матрице С с запретом в клетке 1,2, приведенной на 1 по столбцу (что дало оценку 34+1=35). Оценка нулей дает 3 для нуля в клетке (1,3), так что оценка отрицательного варианта 35+3 превосходит стоимость уже полученного тура 36 и отрицательный вариант отсекается.

Для получения оценки положительного варианта исключаем из матрицы первую строку и третий столбец, ставим запрет (3,1) и получаем матрицу. Эта матрица приводится по четвертой строке на 1, оценка класса достигает 36 и кружок зачеркивается. Поскольку у вершины «все» убиты оба потомка, она убивается тоже. Вершин не осталось, перебор окончен. Мы получили тот же минимальный тур, который показан подчеркиванием на табл. 2.

Удовлетворительных теоретических оценок быстродействия алгоритма Литтла и родственных алгоритмов нет, но практика показывает, что на современных ЭВМ они часто позволяют решить ЗК с n = 100. Это огромный прогресс по сравнению с полным перебором. Кроме того, алгоритмы типа ветвей и границ являются, если нет возможности доводить их до конца, эффективными эвристическими процедурами.

Впервые метод ветвей и границ был предложен в 1960 г. в работе Лэнд и Дойг применительно к задаче целочисленного линейного программирования. Однако эта работа не оказала заметного непосредственного влияния на развитие дискретного программирования. Фактически «второе рождение» метода ветвей и границ связано с работой Литтла, Мурти, Суини и Кэрел , посвященной задаче коммивояжера; в этой же работе было впервые предложено и общепринятое теперь название метода «метод ветвей и границ». Начиная с этого момента появляется весьма большое число работ, посвященных методу ветвей и границ и различным его модификациям. Столь большой успех (да еще применительно к «классически трудной» задаче о коммивояжере) объясняется тем, что Литтл, Мурти, Суини и Кэрел первыми обратили внимание на широту возможностей метода ветвей и границ, отметили важность использования специфики задачи и сами весьма удачно этой спецификой воспользовались.

В § 1 настоящей главы излагается общая идея метода ветвей и границ; в § 2 - алгоритм Лэнд и Дойг для задачи целочисленного линейного программирования, в § 3 - метод Литтла и др. авторов для задачи коммивояжера.

§ 1. Идея метода ветвей и границ

1.1. Рассмотрим задачу дискретного программирования в следующей общей форме.

Минимизировать

при условии

Здесь G - некоторое конечное множество.

1.2. В основе метода ветвей и границ лежат следующие построения, позволяющие в ряде случаев существенно уменьшить объем перебора.

I. Вычисление нижней границы (оценки).

Часто удается найти нижнюю границу (оценку) целевой функции на множестве планов (или на некотором его подмножестве т. е. такое число что для имеет место

(соответственно для имеет место Разбиение на подмножества (ветвление). Реализация метода связана с постепенным разбиением множества планов на дерево подмножеств (ветвлением). Ветвление происходит по следующей многошаговой схеме.

0-й шаг. Имеется множество Некоторым способом оно разбивается на конечное число (обычно не пересекающихся) подмножестве шаг Имеются множества , еще не подвергавгпиеся ветвлению. По некоторому правилу (указанному ниже) среди них выбирается множество и разбивается на конечное число подмножеств:

Еще не подвергавшиеся разбиению множества

заново обозначаются через

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

III. Пересчет оценок. Если множество то, очевидно,

Поэтому, разбивая в процессе решения некоторое множество на подмножества

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

IV. Вычисление планов. Для конкретных задач могут быть указаны различные способы нахождения планов в последовательно разветвляемых подмножествах. Любой такой способ существенно опирается на специфику задачи.

V. Признак оптимальности. Пусть

и план X принадлежит некоторому подмножеству Если при этом

то X - оптимальный план задачи (1.1) - (1.2).

Доказательство непосредственно следует из определения оценки.

Обычно этот признак применяется на некотором этапе ветвления (т. е., говоря формально, при ; см. п. II).

VI. Оценка точности приближенного решения. Пусть

Если X - некоторый план исходной задачи (т. е. ), то

Доказательство и здесь сразу следует из определения оценки.

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

1.3. Изложим формальную схему метода ветвей и границ.

0-й шаг. Вычисляем оценку . Если при этом удается найти такой план X, что

то X - оптимальный план.

Если оптимальный план не найден, то по некоторому способу разбиваем множество на конечное число подмножеств

и переходим к шагу.

1-й шаг. Вычисляем оценки Если при этом удается найти такой план X, что для некоторого и

то X - оптимальный план.

Если же оптимальный план не найден, то выбираем «наиболее перспективное» для дальнейшего разбиения множество по следующему правилу:

Разбиваем множество на несколько (обычно не пересекающихся) подмножеств.

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

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

Алгоритм решения:

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

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

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

Найдем решение задач линейного программирования (I) и (II). Очевидно, здесь возможен один из следующих четырех случаев:

• 1. Одна из задач неразрешима, а другая имеет целочисленный оптимальный план. Тогда этот план и значение целевой функции на нем и дают решение исходной задачи.
• 2. Одна из задач неразрешима, а другая имеет оптимальный план, среди компонент которого есть дробные числа. Тогда рассматриваем вторую задачу и в ее оптимальном плане выбираем одну из компонент, значение которой равно дробному числу, и строим две задачи, аналогичные задачам (I) и (II).
• 3. Обе задачи разрешимы. Одна из задач имеет оптимальный целочисленный план, а в оптимальном плане другой задачи есть дробные числа. Тогда вычисляем значения целевой функции на этих планах и сравниваем их между собой. Если на целочисленном оптимальном плане значение целевой функции больше или равно ее значению на плане, среди компонент которого есть дробные числа, то данный целочисленный план является оптимальным для исходной задачи и он вместе со значением целевой функции на нем дает искомое решение.

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

4. Обе задачи разрешимы, и среди оптимальных планов обеих задач есть дробные числа. Тогда вычисляем значение целевой функции на данных оптимальных планах и рассматриваем ту из задач, для которой значение целевой функции является наибольшим. В оптимальном плане этой задачи выбираем одну из компонент, значение которой является дробным числом, и строим две задачи, аналогичные (I) и (II).

Таким образом, описанный выше итерационный процесс может быть представлен в виде некоторого дерева, на котором исходная вершина отвечает оптимальному плану Х 0 задачи (1)-(3), а каждая соединенная с ней ветвью вершина отвечает оптимальным планам задач (I) и (II). Каждая из этих вершин имеет свои ветвления. При этом на каждом шаге выбирается та вершина, для которой значение функции является наибольшим. Если на некотором шаге будет получен план, имеющий целочисленные компоненты, и значение функции на нем окажется больше или равно, чем значение функции в других возможных для ветвления вершинах, то данный план является оптимальным планом исходной задачи целочисленного программирования и значение целевой функции на нем является максимальным.

Итак, процесс нахождения решения задачи целочисленного программирования (1)-(4) методом ветвей и границ включает следующие основные этапы:

• 1. Находят решение задачи линейного программирования (1)-(3).
• 2. Составляют дополнительные ограничения для одной из переменных, значение которой в оптимальном плане задачи (1)-(3) является дробным числом.
• 3. Находят решение задач (I) и (II), которые получаются из задачи (1)-(3) в результате присоединения дополнительных ограничений.
• 4. В случае необходимости составляют дополнительные ограничения для переменной, значение которой является дробным, формулируют задачи, аналогичные задачам (I) и (II), и находят их решение. Итерационный процесс продолжают до тех пор, пока не будет найдена вершина, соответствующая целочисленному плану задачи (1)-(3) и такая, что значение функции в этой вершине больше или равно значению функции в других возможных для ветвления вершинах.

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

целочисленный программирование задача коммивояжер ранец

Метод ветвей и границ − один из комбинаторных методов. В отличие от метода Гомори применим как к полностью, так и частично целочисленнным задачам.

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

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

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

или
, или

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

Очевидно, что возможен один из следующих четырех случаев.

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

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

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

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

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

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

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

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

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

Пример . Найти методом ветвей и границ решение задачи целочисленного программирования

Решение . Находим оптимальный план сформулированной задачи симплексным методом без учета целочисленности переменных, а именно решаем задачу 1.

Оптимальный план задачи 1 линейного программирования

при
.

Для исходной задачи, с учетом целочисленности переменных, полученное решение не является оптимальным.

Для поиска целочисленного оптимального решения разделим интервал изменения переменной x 1 на две области, а именно x 1  и x 1 = 10 , и разобьем заданную задачу на две новые задачи.

Нижняя граница линейной функции не изменилась: Z 0 = 0. Решаем одну из задач, например задачу 3, симплексным методом. Получаем, что условия задачи противоречивы.

Решаем задачу 2 симплексным методом. Получаем оптимальный целочисленный план поставленной задачи 2, который является также оптимальным планом задачи 1:

при
.

Таким образом, в результате одного ветвления задачи было найдено ее оптимальное решение.