Решение задачи коммивояжера с помощью метода ветвей и границ. Метод ветвей и границ

Требуется решить следующую задачу:

max 2х 1 + х 2

5х 1 + 2х 2 10

3х 1 + 8х 2 13

Вначале решим эту задачу графически без ограниченийцелочисленности. Решение может быть найдено как симплекс-методом, так и графически. Найдем его графически (рисунок 4). Координаты точки оптимума можно найти, решив систему уравнений: 5х 1 + 2х 2 = 10 х 1 =27/17

3х 1 + 8х 2 = 13 х 2 =35/34

Х G = (27/17;35/34), z G =143/34

Рисунок 4 - Графическое решение задачи без ограничений целочиелейности

Начнем строить дерево, первая вершина которого будет соответствовать всей ОДП нецелочисленной задачи (G), а ее оценка будет равна z G (рис.5).

Рисунок 5 - Схема метода ветвей и границ

Полученный план не является целочисленным, поэтому возьмем его произвольную нецелочисленную компоненту, например, первую (х 1 Z; [х 1 ] = = 1) и разобьем ОДП на две части следующим образом:

G 1 ={XG: х 1 1}

G 2 ={XG: х 1 2}

Это означает, что в область G 1 войдут все точки из G, у которых абсцисса не больше 1, а в G 2 - у которых она не меньше 2. Точки с дробными значениями абсциссы от 1 до 2 исключены из рассмотрения.

Изобразим эти области на графике (рисунок 6).

Из рисунка 6 видно, что G 2 представляет собой одну точку Х G 2 =(2;0), следовательно, на этом множестве оптимум задачи равен 4 ( 2 =4).

План Х G 2 является целочисленным, следовательно, решение целочисленной задачи уже, возможно, найдено. Однако, следует еще найти оценку множества G 1 |. Она может оказаться не менее 4 (но обязательно не более 143/34). Если это так, то нужно проверить, не является ли целочисленным решение задачи на G 1. Если оно целое, то является решением задачи, а если нет, то процесс решения необходимо продолжить, разбивая G 1

Рисунок 6 - Разбиение множества на части

На G 1 точку оптимума можно найти, решив систему уравнений:

х 1 = 1 х 1 =1

3х 1 + 8х 2 = 13 х 2 =5/4

Х G 1 = (1; 5/4), z G =13/4

Оценка меньше 4, следовательно, решением задачи является Х * =Х G 2 =(2;0),z * =4.

3.4 Решение задачи целочисленного линейного программирования методом ветвей и границ с помощью ппп «Система деловых задач»

ЗЦЛП можно решить с помощью пакета прикладных программ “Quantitative Systems for Business” ("Система деловых задач") . Соответствующая программа запускается файлом intlprog.ехе. Она решает как частично, так и полностью целочисленные задачи линейного программирования с числом переменных и ограничений до 20, используя метод ветвей и границ. В том числе решаются и задачи с булевыми переменными (т.е. с переменными, которые могут принимать одно из двух значений - 0 или 1; как, например, в задаче о назначениях ). По умолчанию все переменные неотрицательны. Программа позволяет ввести целочисленные границы для переменных, не включая их в общее число ограничений. По умолчанию нижняя граница 0, а верхняя 32000. Если необходимо установить нецелочисленные границы, их вводят, как обычные ограничения.

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

Режим 2 (ввод новой задачи) включает три этапа. На первом этапе осуществляют ввод информации о размерности задачи, направлении экстремизации и именах переменных (по умолчанию XI, Х2,..., Хn).

На втором этапе необходимо определить, являются ли все переменные целочисленными, являются ли все переменные булевыми, и будут ли вводиться границы для переменных. При ответе «нет» на первый вопрос или «да» на третий, выводится таблица (рисунок 7):

Введите предел и границы для переменных

(По умолчанию значения нижней границы 0 и верхней границы 32000)

№ перем. Имя Предел (I/C) Нижняя гр. Верхняя гр.

1 X 1 <0 > <0 >

2 X 2 <0 > <0 >

Рисунок 7 - Определение пределов и границ

Установив I (integer) в столбце «Предел», на переменную накладывают ограничение целочисленности. В противном случае (С, continuous) -переменная может принимать и нецелые значения, т.е. является непрерывной.

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

На третьем этапе вводятся коэффициенты при переменных и знаки в ограничениях.

В меню решений имеется возможность исправить целочисленную погрешность (по умолчанию она 0,001).

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

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

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

При этом на каждой итерации выводится информация о текущих целочисленных границах (определяющих рассматриваемое подмножество), оптимальном плане нецелочисленной задачи, о том, является ли он целочисленным, о значении целевой функции (ЦФ) на нем и о величинах ZL или ZU. Для задачи на максимум выводится значение нижней границы ZL, а на минимум верхней ZU. До тех пор, пока не найдено какое-нибудь целое решение, ZL =-1*10 20 , а ZU = 1*10 20 .

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

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

Поясним это на примере (рис.8):

max 3х 1 + 2х 2

7х 1 + 5х 2 35

9х 1 + 4х 2 36

На первой итерации найдено нецелочисленное решение Х=(2,353; 3,706). Вся ОДП (множество G) разбивается на два подмножества - G 1 и G 2 следующим образом:

G 1 ={XG: х 1 3}

G 2 ={XG: х 1 2}.

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

На пятой итерации на подмножестве G 5 найдено целочисленное решение, которому соответствует значение целевой функции 12. На следующей итерации это значение присваивается величине ZL, которая до этого была равна -1*10 20 . Соответствующий план запоминается - он может оказаться оптимальным. Но на шестой итерации снова получен целочисленный план, целевая функция на котором равна 13 (больше 12) - ZL снова изменяется, запоминается новый план.

После этого, на седьмой итерации, переходят к рассмотрению подмножества G 2 , которое разбивают на G 7 и G 8 .

На тринадцатой итерации (подмножество G 14) снова найдено целочисленное решение Х=(0; 7), целевая функция на нем равна 14. Снова изменяется ZL и запоминается соответствующий план.

План, найденный на четырнадцатой итерации, также является целочисленным, но его не запоминают, так как 13<14 (ZL=14). План, найденный на пятнадцатой итерации, тоже, к сожалению, не запоминается, так как 1414, а программа ставит своей целью найти хотя бы одно решение.

Наличие других оптимальных планов здесь игнорируется.

Таким образом, решение Х=(0; 7) получено за 15 итераций.

Отметим, что если бы использовался более эффективный вариант метода ветвей и границ, схема которого описана в методических указаниях, то после второй итерации произошел бы сразу переход к седьмой. В самом деле, если рассматривать значения целевой функции на соответствующих планах в качестве оценки подмножеств, то оценка G 2 выше. Поэтому итерации с 3-ей по 6-ю оказываются лишними, и общее число итераций могло быть равно 11.

Начало развитию подхода, получившего название метод ветвей и границ, положила работа Ленд и Дойг (1960). Это, скорее, даже не метод, а концепция или процедурная оболочка, на основе которой стали разрабатывать алгоритмы решения целочисленных задач различной природы. Ценность предложенной идеи стала особенно заметна после появления первого точного алгоритма решения задачи коммивояжера, построенного по схеме ветвей и границ (Литтл с соавторами, 1963). Метод можно применять как к полностью, так и частично целочисленным задачам.

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

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

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

Очевидно, что если, например,V 22 окажется хуже рекорда илиD 22 =, правая ветвь обрывается (говорят также, что она прозондирована). Если же оценкаV 22 будет лучше Z , производится ветвление: множествоD 22 разбивается на 2 подмножества. Решение завершится, когда все ветви будут прозондированы.

Вид оценки зависит от направленности критерия: при максимизации используется верхняя оценка, при минимизации – нижняя. Последующее изложение метода будет относиться к задаче на максимум.

Для алгоритмической реализации схемы ветвей и границ необходимо решить два основополагающих вопроса:

Каким образом разбивать перспективное множество на подмножества;

Как определять верхнюю оценку критерия на рассматриваемом множестве.

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

Пусть известен диапазон возможных значений j -й переменной

0  х j  d j ,

которая в непрерывном оптимальном решении оказалась нецелочисленной и равной x j * . Тогда целочисленное значение этой переменной может достигаться либо в интервале 0  х j 
,либо в интервале
+1 х j  d j , где
- целая часть (рис. 7.6).

Это соответствует разбиению непрерывного множестваD н на два непересекающихся подмножества D 1 н и D 2 н , объединение которых не равно D н . В то же время такое разбиение целочисленного множества удовлетворяет соотношениям (7.9). При этом целочисленные множества, как исходное, так и порожденные, включены в соответствующие непрерывные множества. Следовательно, поиск целочисленного решения на непрерывном множестве даст тот же результат, что и на целочисленном. Легко увидеть, что приведенное выделение подинтервалов по одной переменной приводит к разбиению исходного множества на два подмножества при любом числе переменных.

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

Выбор начального значения рекорда зависит от ситуации:

если известно какое-либо целочисленное значение, то рекорд принимается равным критерию в этом решении;

при положительности всех коэффициентов критерия можно взять нулевое значение рекорда;

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

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

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

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

Пример 7.3 . Применим алгоритм ветвей и границ к задаче

L= 9x 1 + 5x 2  max;

3x 1 - 6x 2  1;

5x 1 +2x 2  28;

 x j  0 , целые.

Отбрасывая условие цедочисленности, получаем непрерывную задачу, которую помещаем в список задач. Так как коэффициенты критерия положительны, начальное значение рекорда принимаем равным нулю. Берем из списка единственную задачу и решаем ее. Получаем оптимальное решение в вершине А (рис. 7.7):x 1 * =4,72; x 2 * =2,19 . Ветвление производим по переменнойx 1 . Добавляя к решенной задаче ограничение x 1 4, образуем задачу 2, а добавление x 1 5 дает задачу 3. Допустимые множества новых задач покзаны на рис. 7.7. Эти задачи помещаем в список задач. Решение задачи 2 достигается в точке В, а задачи 3 – в С. Весь ход решения исходной задачи представлен в виде дерева решений на рис. 7.10. Порядок решения задач из списка отражает счетчик итераций k . На 3-й итерации (задача 4) получено целочисленное решение со значением критерия 41 (точка D нарис. 7.8). Поэтому изменяется рекорд: Z =41.Задача 6 имеет нецелочисленное решение (вершина Е на рис. 7.9), задача 8 – целочисленное решение в точкеF. В результате после 7-й итерации рекорд становится равным 50.

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

Из приведенного дерева решений видно, что число задач в списке могло быть меньше при другом порядке решения задач. Действительно, если бы сначала были решены задачи правой ветви с рекордом Z= 50, то после решения задачи 2 не произошло бы ветвления, так как верхняя оценка оказалась бы ниже рекорда (V=L * =45,17<50).

Естественно возникает вопрос: а как на числе задач и дереве решений может отразиться выбор другой переменной для ветвления? Так, в нашем примере если после 1-й итерации произвести ветвление по переменнойx 2 , то получим дерево, показанное на рис. 7.11. Оно содержит на 2 задачи больше, чем на рис. 7.10. Конечно, оно может быть также другим при ином порядке решения задач.

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

Из алгоритма и приведенного примера следует, что ветвь обрывается по одной из трех причин:

неразрешимость задачи;

задача имеет целочисленное решение;

верхняя оценка не больше рекорда.

Теперь сделаем ряд замечаний относительно метода ветвей и границ. Как уже отмечалось, в базовом алгоритме не оговариваются правила выбора задачи и переменной. В большинстве программных реализаций метода используются правила, основанные на эвристических оценках перспективности задач и переменных. В некоторых пакетах, например, "ЛП в АСУ" предлагается несколько вариантов управления процессом решения: от автоматического до ручного, в котором пользователь может сам делать выбор как задачи, так и переменной. Кроме того, алгоритмы, основанные на методе ветвей и границ, могут существенно отличаться в связи с учетом особенностей класса задач. Например, для задачи коммивояжера, определение оценки значительно упрощено (не требуется решать непрерывную линейную задачу).

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

накопление ошибок менее значительное, так как решение идет по разным ветвям;

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

при решении непрерывных задач размеры симплекс-таблиц не увеличиваются.

Недостатки метода ветвей и границ:

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

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

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

Введение

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

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

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

1. Историческая справка

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

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

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

2. Описание метода

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

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

При применении метода ветвей и границ к каждой конкретной задаче в первую очередь должны быть определены две важнейшие его процедуры: 1) ветвления множества возможных решений; 2) вычисления нижних и верхних оценок целевой функции.

2.1 Правила ветвления

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

1. ветвление множества допустимых решений исходной задачи D;

2. ветвление множества D" получаемого из D путем снятия условия целочисленности на переменные.

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

Второй способ ветвления - более универсальный, чем первый. Для осуществления ветвления некоторой области D i " этим способом на D i " решается оптимизационная задача с целевой функцией исходной задачи и действительными переменными.

Ветвление осуществляется, если в оптимальном решении значение хотя бы одной целочисленной по исходной постановке задача переменной не является целочисленным. Среди этих переменных выбирается одна, например j - я. Обозначим ее значение в найденном оптимальном решении x 0 [j]. Говорят, что ветвление осуществляется по переменной x[j]. Область D i " разделяется на две подобласти D i1 " и D i2 " следующим образом:

где ] - целая часть значения x 0 [j]

На рис. 2 условно дана геометрическая интерпретация такого ветвления.

Рис. 2. Геометрическая интерпретация ветвления

Видно, что при этом из области D i " удаляется часть между плоскостями вновь введенных ограничений. Так как переменная x[j] по условиям области допустимых решений исходной задачи - целочисленная, то из подобласти допустимых решений исходной задачи. D i (D i D i ") при таком изъятии не исключается ни одного решения.

2.2 Формирование нижних и верхних оценок целевой функции

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

где х - вектор оптимизационных переменных, среди которых часть действительных, а часть целочисленных; f(x) - в общем случае нелинейная целевая функция; D - область допустимых решений задачи дискретного программирования общего вида.

Нижние оценки целевой дикции в зависимости от выбранного способа ветвления могут определяться либо для подобластей D i D либо для подобластей D i " D" (D i " и D" получены из соответствующих множеств D i и D путем снятия условий целочисленности на дискретные переменные).
Нижней оценкой целевой функции f(x) на множестве D i (или D i ") будем называть величину:

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

На рис. 3 показан такой идеальный случай, когда нижние оценки (соединены ломаной штрихпунктирной линией) правильно отражают соотношения между действительными минимальными значениями f(x) (соединены штриховой линией) для четырех подмножеств допустимых решений D 1 , D 2 , D 3 , D 4 .

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

Определенная таким образом о i является нижней оценкой f(x) на D i (или D i "), так как D i D i ".

Если при решении задачи (4) установлено, что, то для общности будем полагать, что.

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

Совместно с нижней оценкой в методе ветвей и границ используются верхние оценки f(x). Как правило, вычисляют лишь одно значение верхней оценки, которую определяют как значение целевой функции для лучшего найденного допустимого решения исходной задачи. Такую верхнюю оценку иногда называют рекордом. Если же можно для решаемой задачи достаточно просто и точно получить верхние оценки f(x) для отдельных множеств, образующихся при ветвлении, то их необходимо использовать в методе для уменьшения вычислительной сложности процесса решения. При использовании единой верхней оценки ее первоначальное значение обычно полагают равным бесконечности (), если, конечно, из априорных соображений не известно ни одного допустимого решения исходной задачи. При нахождении первого допустимого решения:

Затем при определении более лучшего допустимого решения верхнюю оценку корректируют:

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

2.3 Алгоритм метода ветвей и границ

Основные правила алгоритма могут быть сформулированы следующим образом:

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

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

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

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

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

2.4 Решение задачи методом ветвей и границ

Целые .

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

Если среди компонент этого плана нет дробных чисел, то тем самым найдено искомое решение данной задачи.

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

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

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

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

- целые .

Целые .

Возможны четыре случая при решении этой пары задач:

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

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

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

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

Таким образом, при решении задачи получаем схему:

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

2. Составляет дополнительные ограничения на дробную компоненту плана.

3. Находим решение двух задач с ограничениями на компоненту.

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

Пример

Найдем решение задачи

Целые .

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

Рассмотрим следующую пару задач:

Задача №1

изадача №2

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

вторая - неразрешима.

Проверяем на целочисленность план первой задачи. Это условие не выполняется, поэтому строим следующие задачи:

Задача №1.1

и задача №1.2

Задача №1.2 неразрешима, а задача №1.1 имеет оптимальный план, на котором значение целевой функции.

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

3. Решение задачи коммивояжера методом ветвей и границ

Рассмотрим теперь класс прикладных задач оптимизации. Метод ветвей и границ используется в очень многих из них. Предлагается рассмотреть одну из самых популярных задач - задача коммивояжера. Вот ее формулировка. Имеется несколько городов, соединенных некоторым образом дорогами с известной длиной; требуется установить, имеется ли путь, двигаясь по которому можно побывать в каждом городе только один раз и при этом вернуться в город, откуда путь был начат («обход коммивояжера»), и, если таковой путь имеется, установить кратчайший из таких путей.

3.1 Постановка задачи

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

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

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

пусть - полный ориентированный граф и - весовая функция; найти простой остовный ориентированный цикл («цикл коммивояжера») минимального веса.

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

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

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

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

Наконец, слова привести матрицу означают, что матрица сначала приводится по строкам, а потом приводится по столбцам.

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

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

Первый шаг . Фиксируем множество всех обходов коммивояжера (т.е. всех простых ориентированных остовных циклов). Поскольку граф - полный, это множество заведомо не пусто. Сопоставим ему число, которое будет играть роль значения на этом множестве оценочной функции: это число равно сумме констант приведения данной матрицы весов ребер графа. Если множество всех обходов коммивояжера обозначить через G, то сумму констант приведения матрицы весов обозначим через j(G). Приведенную матрицу весов данного графа следует запомнить; обозначим ее через M 1 ; таким образом, итог первого шага:

множеству G всех обходов коммивояжера сопоставлено чис-ло j(G) и матрица M 1 .

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

Сопоставим множеству следующую матрицу M 1,1: в матрице M 1 заменим на Ґ число в клетке. Затем в полученной матрице вычеркнем строку номер i и столбец номер j, причем у оставшихся строк и столбцов сохраним их исходные номера. Наконец, приведем эту последнюю матрицу и запомним сумму констант приведения. Полученная приведенная матрица и будет матрицей M 1,1 ; только что запомненную сумму констант приведения прибавим к j(G) и результат, обозначаемый в дальнейшем через j(), сопоставим множеству.

Теперь множеству тоже сопоставим некую матрицу M 1,2 . Для этого в матрице M 1 заменим на Ґ число в клетке и полученную в результате матрицу приведем. Сумму констант приведения запомним, а полученную матрицу обозначим через M 1,2 . Прибавим запомненную сумму констант приведения к числу j(G) и полученное число, обозначаемое в дальнейшем через j(), сопоставим множеству.

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

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

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

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

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

После этого осуществляется улучшение рекорда вплоть до получения окончательного ответа.

3.2 Условие задачи

Студенту Иванову поручили разнести некоторые важные документы из 12-ого корпуса. Но, как назло, у него на это очень мало времени, да и еще надо вернуться обратно. Нужно найти кротчайший путь. Расстояния между объектами даны в таблице

3.3 Математическая модель задачи

Для решения задачи присвоим каждому пункту маршрута определенный номер: 12-ый корпус - 1, Белый дом - 2, КРК «Премьер» - 3, Администрация - 4 и 5-ый корпус - 5. Соответственно общее количество пунктов. Далее введем альтернативных переменных, принимающих значение 0, если переход из i-того пункта в j-тый не входит в маршрут и 1 в противном случае. Условия прибытия в каждый пункт и выхода из каждого пункта только по одному разу выражаются равенствами (8) и (9).

Для обеспечения непрерывности маршрута вводятся дополнительно n переменных и дополнительных ограничений (10).

Суммарная протяженность маршрута F , которую необходимо минимизировать, запишется в следующем виде:

В нашем случае эти условия запишутся в следующем виде:

3.4 Решение задачи методом ветвей и границ

задача коммивояжер ветвь граница

1) Анализ множества D.

Найдем оценку снизу Н . Для этого определяем матрицу минимальных расстояний по строкам (1 где расстояние минимально в строке).

Аналогично определяем матрицу минимальных расстояний по столбцам.

Выберем начальный план: . Тогда верхняя оценка:

Очевидно, что, где означает переход из первого пункта в j-тый. Рассмотрим эти подмножества по порядку.

2) Анализ подмножества D 12 .

3) Анализ подмножества D 13 .

4) Анализ подмножества D 14 .

5) Анализ подмножества D 15 .

6) Отсев неперспективных подмножеств.

Подмножества D 13 и D 15 неперспективные. Т.к. , но, то далее будем рассматривать подмножество D 14 .

7) Анализ подмножества D 142 .

8) Анализ подмножества D 143 .

9) Анализ подмножества D 145 .

10) Отсев неперспективных подмножеств

Подмножество D 143 неперспективное. Т.к. , но, то далее будем рассматривать подмножество D 145 .

11) Анализ подмножества D 1452 .

12) Анализ подмножества D 1453 .

Оптимальное решение: .

Таким образом, маршрут студента: 12-ый корпус - Администрация - 5-ый корпус - Белый дом - КРК Премьер - 12-ый корпус.

Список литературы

1. Абрамов Л.А., Капустин В.Ф. Математическое программирование. - Л.: Изд-во ЛГУ, 1981. -328 с.

2. Алексеев О.Г. Комплексное применение методов дискретной оптимизации. - М.: Наука, 1987. -294 с.

3. Корбут А.А., Финкелгейн Ю.Ю. Дискретное программирование. М.: Наука. 1969. -240 с

4. Кузнецов Ю.Н. и др. Математическое программирование: Учебное пособие. - 2-е изд., перераб и доп. - М.: Высшая школа, 1980. -300 с.

5. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. - М.: Мир, 1985. -213 с.

Подобные документы

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

задача , добавлен 24.07.2009


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

контрольная работа , добавлен 07.06.2011


Методы решения задачи коммивояжера. Математическая модель задачи коммивояжера. Алгоритм Литтла для нахождения минимального гамильтонова контура для графа с n вершинами. Решение задачи коммивояжера с помощью алгоритма Крускала и "деревянного" алгоритма.

курсовая работа , добавлен 30.04.2011


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

курсовая работа , добавлен 18.06.2011


Математическая модель задачи. Решение транспортной задачи методом потенциалов. Значение целевой функции. Система, состоящая из 7 уравнений с 8-ю неизвестными. Решение задач графическим методом. Выделение полуплоскости, соответствующей неравенству.

контрольная работа , добавлен 12.06.2011


Теория динамического программирования. Понятие об оптимальной подструктуре. Независимое и полностью зависимое множество вершин. Задача о поиске максимального независимого множества в дереве. Алгоритм Брона-Кербоша как метод ветвей, границ для поиска клик.

реферат , добавлен 09.10.2012


Решение двойственной задачи с помощью первой основной теоремы теории двойственности, графическим и симплексным методом. Математическая модель транспортной задачи, расчет опорного плана перевозок методами северо-западного угла и минимального элемента.

контрольная работа , добавлен 27.11.2011


Постановка задачи коммивояжера и основные алгоритмы решения. Маршруты и пути. Понятия транспортной сети. Понятие увеличивающая дуга, цепь, разрез. Алгоритм Флойда-Уоршелл. Решение задачи аналитическим методом. Создание приложения для решения задачи.

курсовая работа , добавлен 08.10.2015


Решение первой задачи, уравнения Пуассона, функция Грина. Краевые задачи для уравнения Лапласа. Постановка краевых задач. Функции Грина для задачи Дирихле: трехмерный и двумерный случай. Решение задачи Неймана с помощью функции Грина, реализация на ЭВМ.

курсовая работа , добавлен 25.11.2011


Последовательность решения линейной краевой задачи. Особенности метода прогонки. Алгоритм метода конечных разностей: построение сетки в заданной области, замена дифференциального оператора. Решение СЛАУ методом Гаусса, конечно-разностные уравнения.

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

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

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

Рассмотрим реализацию метода ветвей и границ для задачи коммивояжёра и задачи о рюкзаке.

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

Пример.

Пусть в задаче коммивояжера задана следующая матрица стоимостей переездов

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

.

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

,

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

Суммируя элементы и , получим константу приведения:

.

Находим степени нулей для приведенной по строкам и столбцам матрицы. Для этого мысленно нули в матице заменяем на знак и находим сумму минимальных элементов строки и столбца, соответствующих этому нулю. Записываем ее в правом верхнем углу клетки:

.

Выбираем дугу , для которой степень нулевого элемента достигает максимального значения

Разбиваем множество всех допустимых маршрутов на два подмножества:

– подмножество, содержащее дугу ;

– подмножество, не содержащее дугу

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

Рассмотрим следующую задачу целочисленного линейного программирования. Максимизировать при ограничениях

На рис.1 пространство допустимых решений задачи целочисленного линейного программирования представлено точками. Соответствующая начальная задача линейного программирования (обозначим ее ЛП0) получается путем отбрасывания условия целочисленности. Ее оптимальным решением будет =3.75, =1.25, z=23.75.

Рис.1.

Так как оптимальное решение задачи ЛП0 не удовлетворяет условия целочисленности, метод ветвей и границ изменяет пространство решений задачи линейного программирования так, что в конечном счете получается оптимальное решение задачи целочисленного линейного программирования. Для этого сначала выбирается одна из целочисленных переменных, значение которой в оптимальном решении задачи ЛП0 не является целочисленным. Например, выбирая (=3.75), замечаем, что область 3 ? ?4 пространства допустимых решений задачи ЛП0 не содержит целочисленных значений переменной и, следовательно, может быть исключена из рассмотрения, как бесперспективная. Это эквивалентно замене исходной задачи ЛП0 двумя новыми задачами линейного программирования ЛП1 и ЛП2, которые определяются следующим образом:

Пространство допустимых решений ЛП1 = пространство допустимых решений ЛП0 + (), пространство допустимых решений ЛП2 = пространство допустимых решений ЛП0 + ().

На рис.2 изображены пространства допустимы решений задач ЛП1 И ЛП2 . Оба пространства содержат все допустимые решения исходной задачи ЦЛП. Это обозначает, что задачи ЛП1 и ЛП2 «не потеряют» решения начальной задачи ЛП0.

Рис.2.

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

Новые ограничения и взаимоисключаемы, так что задачи ЛП1 и ЛП2 необходимо рассматривать как независимые задачи линейного программирования, что и показано на Рис.3. Дихотомизация задач ЛП - основа концепции ветвления в методе ветвей и границ. В этом случае называется переменной ветвления.

Рис.3.

Оптимальное решение задачи ЦЛП находятся в пространстве допустимых решений либо в ЛП1, либо в ЛП2. Следовательно, обе подзадачи должны быть решены. Выбираем сначала задачу ЛП1 (выбор произволен), имеющую дополнительное ограничение?3.

Максимизировать при ограничениях

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

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

При значении нижней границы исследуем ЛП2. Так как в задачи ЛП0 оптимальное значение целевой функции равно 23.75 и вес ее коэффициенты являются целыми числами, то невозможно получить целочисленное решение задачи ЛП2, которое будет лучше имеющегося. В результате мы отбрасываем подзадачу ЛП2 и считаем ее прозондированной.

Реализация метода ветвей и границ завершена, так как обе подзадачи ЛП1 и ЛП2 прозондированы. Следовательно, мы заключаем, что оптимальным решением задачи ЦЛП является решение, соответствующей нижней границе, а именно, и.

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

Рис.4. Дерево ветвлений решений