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

На рис.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. Дерево ветвлений решений

4.3.1. Общая схема метода «ветвей и границ». Другим широко применяемым для решения задач дискретного програм­мирования методом является метод ветвей и границ . Впервые данный метод для решения ЦЗЛП предложили в 1960 г. Лэнг и Дойг, а его «второе рождение» произошло в 1963 г. в связи с выходом работы Литтла, Мурти, Суини и Кэрел, посвященной решению задачи о коммивояжере .

Вообще говоря, термин «метод ветвей и границ» является соби­рательным и включает в себе целое семейство методов, применяе­мых для решения как линейных, так и нелинейных дискретных задач, объединяемое общими принципами. Кратко изложим их.

Пусть стоит задача:

где D - конечное множество.

Алгоритм является итеративным, и на каждой итерации про­исходит работа с некоторым подмножеством множества D . На­зовем это подмножество текущим и будем обозначать его как D ( q ) , где q - индекс итерации. Перед началом первой итерации в качестве текущего множества выбирается все множество D (D (1) =D ), и для него некоторым способом вычисляется значе­ние верхней оценки для целевой функции max f(x) ≤ ξ( D (1)). Стандартная итерация алгоритма состоит из следующих этапов:

1°. Если можно указать план x (q ) ∊D (q ) , для которого f(x (q ) ) ≤ξ( D (q )), то x (q ) =х* - решение задачи (4.29).

2°. Если такой план не найден, то область определения D (q ) некоторым образом разбивается на подмножества D 1 (q ) , D 2 (q ) , ..., D lq (q ) , удовлетворяющие условиям:

Для каждого подмножества находятся оценки сверху (вер­хние границы) для целевой функции ξD 1 ( q ) , ξD 2 ( q ) , ..., ξD l 1 ( q ) , уточняющие ранее полученную оценку ξD ( q ) , то есть ξD i ( q ) ≤ ξD ( q ) , i ∊1:l q . Возможно одно из двух:

2.1. Если существует такой план х ( q ) , что

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

2.2. Если такой план не найден, то выбирается одно из мно­жеств D i ( q ) , i ∊1:l q (как правило, имеющее наибольшую оценку

Все имеющиеся к текущему моменту концевые подмножества, т. е. те подмножества, которые еще не подверглись процессу дробления, переобозначаются как D 1 ( q +1) , D 2 ( q +1) ,..., D l ( q +1) ( q +1) , после чего процесс повторяется.

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

Конкретные реализации метода ветвей и границ связаны с правилами разбиения на подмножества (правилами ветвления) и построения оценок значений целевых функций на данных под­множествах (границ).

4.3.2. Решение ЦЗЛП методом ветвей и границ. Рас­смотрим применение алгоритма метода ветвей и границ для решения ЦЗЛП (4.2)-(4.3). Как уже упоминалось, через D ( q ) обозначается подмножество множества допустимых планов за­дачи. Перед началом первой итерации (q = 1) в качестве теку­щего множества берется все множество D (D (1) = D ), после чего решается стандартная задача линейного программирования (D (1) , f ). Нетрудно заметить, что она является непрерывным аналогом

исходной задачи (4.2)-(4.3). Если найденный оптималь­ный план (1) содержит только целочисленные компоненты, то он является и оптимальным планом для (4.2)-(4.3): (1) = x* . В противном случае значение f ( (1)) становится оценкой (верх­ней границей) значения целевой функции на множестве D (1) , и мы переходим к выполнению стандартной итерации алгоритма. Опишем входящие в нее этапы.

1) Выбирается некоторая нецелочисленная компонента пла­на k ( q ) . Поскольку в оптимальном плане она должна быть це­лой, то можно наложить ограничения x k ≤ [ k ( q ) ] и x k ≥ [ k ( q ) ]+1. Таким образом, D ( q ) разбивается на подмножества

Графическая интерпретация такого разбиения множества D ( q ) приведена на рис. 4.4.

2) Решаются задачи линейного программирования

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

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

и содержит только целые компоненты, то, значит, найдено ре­шение основной задачи (4.2)-(4.3). В противном случае среди всех концевых подмножеств , полученных как на предыду­щих (D i ( q )), так и на текущем (D 1 ( q ) , D 2 ( q )) этапе, выбирается об­ласть с наибольшей оценкой ξ(D i ( q )). Она становится текущим рассматриваемым подмножеством (D ( q +1)). Далее производится перенумерация концевых множеств и вычислительный процесс итеративно повторяется.

При решении задач (D 1 ( q ) , f ) и (D 2 ( q ) , f ) можно воспользовать­ся результатами решения предыдущей задачи (D ( q ) , f ). Рас­смотрим вариант организации вычислительного процесса на примере задачи ( 1 ( q ) , f ) (для ( 2 ( q ) , f ) он выглядит аналогично с точностью до знаков неравенств).

Предположим, что на последнем шаге решения задачи (D ( q ) , f ) был получен оптимальный базис β. Без ограничения общности можно считать, что он состоит из первых m столбцов матрицы задачи. Данное предположение делается исключитель­но для обеспечения наглядности дальнейшего изложения и оче­видно, что его выполнения можно всегда добиться за счет про­стой перенумерации векторов а j . По аналогии с предыдущим параграфом введем обозначения для элементов матрицы задачи (D ( q ) , f ) и ее вектора ограничений относительно базиса :

Тогда система ограничений задачи (D ( q ) , f ) может быть пред­ставлена как

а получаемая на ее основе система ограничений задачи ( 1 ( q ) , f ) как

где х n +1 ≥ 0 - фиктивная переменная, которой соответствует нулевой коэффициент в целевой функции, добавляемая для пре­образования неравенства в строгое равенство.

Очевидно, что 1≤k≤m , т. к. небазисные компоненты опти­мального плана (m +1≤j≤n ) равны нулю, т. е. являются заведо­мо целочисленными. Тогда с учетом сделанных предположений о виде базиса можно записать:

Как видно из (4.39), в k -м столбце имеется всего два отлич­ных от нуля элемента: в k -й и (m +1)-й строках. Если вычесть из (m +1)-го уравнения k -e, то, учитывая, что [ά k ] – ά k =-{ά k }, по­лучим эквивалентную систему:

Проведенные преобразования системы ограничений D 1 ( q ) по­зволили явно выделить сопряженный базис, образуемый столб­цами с номерами 1,..., m , n +1, и соответствующий ему псевдо­план (ά 1 , ..., ά m , 0,...., 0, -{ά k }), т.е. для решения задачи (D 1 ( q ) , f ) может быть применен алгоритм двойственного симплекс-мето­да. Практически вычислительный процесс для данного этапа сводится к преобразованию к симплекс-таблицы, показанному на рис. 4.5.

Для случая задачи (D 2 ( q ) , f ) преобразование симплекс-табли­цы, получаемое на базе аналогичных рассуждений, приведено на рис. 4.6.

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

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

КЛЮЧЕВЫЕ ПОНЯТИЯ

Ø Ø Задачи с неделимостями.

Ø Ø Экстремальные комбинаторные задачи.

Ø Ø Задачи с разрывными целевыми функциями.

Ø Ø Правильное отсечение.

Ø Ø Метод Гомори.

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

КОНТРОЛЬНЫЕ ВОПРОСЫ

4.1. Какие основные проблемы возникают при решении дис­кретных задач?

4.2. Сформулируйте задачу о ранце.

4.3. Какие экономико-математические модели могут быть све­дены к задаче о коммивояжере?

4.4. Приведите пример моделей с разрывными целевыми функ­циями.

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

4.6. Перечислите основные этапы, входящие в «большую» итерацию метода Гомори.

4.7. Какую роль играет алгоритм двойственного симплекс-ме­тода при решении целочисленной

линейной задачи мето­дом Гомори?

4.8. Перечислите принципиальные идеи, лежащие в основе ме­тодов ветвей и границ.

4.9. Как производится построение отсечения при решении це­лочисленной линейной задачи методом

ветвей и границ?

4.10. Опишите схему решения целочисленной задачи линейно­го программирования методом ветвей и

4.11. За счет каких преобразований удается построить сопря­женный базис при добавлении

отсекающего ограничения?

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

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

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

Ветвление производится последовательным введением дополнительных ограничений. Пусть x k – целочисленная переменная, значение которой в оптимальном решении получилось дробным. Интервал [β k ] ≤ x k ≤ [β k ]+1 не содержит целочисленных компонентов решения. Поэтому допустимое целое значение x k должно удовлетворять одному из неравенств x k ≥[β k ]+1 или x k ≤[β k ]. Это и есть дополнительные ограничения. Введение их в методе ветвей и границ на каждом шаге порождает две не связанные между собой подзадачи. Каждая подзадача решается как задача линейного программирования с исходной целевой функцией. После конечного числа шагов будет найдено целочисленное оптимальное решение.

Применение метода ветвей и границ рассмотрим на конкретном примере.

Пример 1. Методом ветвей и границ F(x) = 2x 1 + 3x 2 при ограничениях

3x 1 +4x 2 ≤24

2x 1 +5x 2 ≤22

x 1,2 ≥0 - целые

1-й шаг метода ветвей и границ. с отброшенными условиями целочисленности с помощью симплекс-метода (табл. 1 – 3).

По данным табл. 3 запишем оптимальное нецелое решение

		; x * 2 =2	4	; F max =16	6
			7		7

Таблица 1 - симплекс-таблица для задачи ЛП

Таблица 2 - симплекс-таблица для задачи ЛП

Таблица 3 - симплекс-таблица для задачи ЛП

Графическая интерпретация задачи приведена на рис. 1. Здесь ОДЗП представлена четырехугольником ABCD, а координаты вершины С совпадают с x * 1 и x * 2 . Обе переменные в оптимальном решении являются нецелыми, поэтому любая из них может быть выбрана в качестве переменной, инициирующей процесс ветвления.

Пусть это будет x 2 . Выбор x 2 порождает две подзадачи (2 и 3), одна из них получается путем добавления ограничения x 2 ≥3 к исходной задаче, а другая – путем добавления ограничения x 2 ≤2. При этом ОДЗП разбивается на две заштрихованные области (рис. 1), а полоса значений 2 < x 2 < 3 исключается из рассмотрения. Однако множество допустимых целочисленных решений сохраняется, порожденные подзадачи содержат все целочисленные решения исходной задачи.

Рисунок 1 - графическая интерпритация решения примера методом ветвей и границ

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

Пусть вначале решается подзадача 3 с дополнительным ограничением x 2 ≤2 или x 2 + x 5 = 2 . Из табл. 3 для переменной x 2 справедливо следующее выражение -2/7x 3 +3/7x 4 +x 2 =18/7 или x 2 =18/7+2/7x 3 -3/7x 4 , тогда 2/7x 3 -3/7x 4 +x 5 =-4/7 . Включаем ограничение в табл. 3, при этом получим новую таблицу (табл. 4).

Осуществляя оптимизацию решения, переходим к табл. 5, которой соответствует решение

		; x * 2 =2	; F max =16	2
				3

Переменная x 1 нецелая, поэтому ветвление необходимо продолжить; при этом возникают подзадачи 4 и 5 с ограничениями x 1 ≤5 и x 1 ≥6 соответственно. Полоса значений 5 < x 1 < 6 исключается из рассмотрения.

Таблица 5 - симплекс-таблица для задачи ЛП

3-й шаг метода ветвей и границ. Решаются подзадачи 4 и 5. Из рис. 1 видно, что оптимальное целочисленное решение подзадачи 4 достигается в вершине К с координатами x * 1 =5, x * 2 =2, однако это не означает, что найден оптимум исходной задачи. Причиной такого вывода являются еще не решенные подзадачи 3 и 5, которые также могут дать целочисленные решения. Найденное целочисленное решение F = 16 определяет нижнюю границу значений целевой функции, т.е. меньше этого значения оно быть не должно.

Подзадача 5 предполагает введение дополнительного ограничения x 1 ≥6 в подзадачу 3 . Графическое решение на рис. 1 определяет вершину L с координатами x * 1 =6, x * 2 =3/2 , в которой достигается оптимальное решение подзадачи 5: F max = 16.5 . Дальнейшее ветвление в этом направлении осуществлять нецелесообразно, так как большего, чем 16, целого значения функции цели получить невозможно. Ветвление подзадачи 5 в лучшем случае приведёт к другому целочисленному решению, в котором F = 16.

4-й шаг метода ветвей и границ. Исследуется подзадача 2 с ограничением x 2 ≥3, находится её оптимальное решение, которое соответствует вершине М (рис. 1) с координатами x * 1 =3.5, x * 2 =3. Значение функции цели при этом F max =16, которое не превышает найденного ранее решения. Таким образом, поиск вдоль ветви x 2 ≥3 следует прекратить.

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

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

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

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

Таблица 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. Это огромный прогресс по сравнению с полным перебором. Кроме того, алгоритмы типа ветвей и границ являются, если нет возможности доводить их до конца, эффективными эвристическими процедурами.

Рассмотрим задачу дискретного программирования в общем виде:

Найти -вектор неизвестных, D- конечное

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

Идея метода состоит в разбиении D на непересекающиеся подмножества Di (эта процедура называется ветвлением) и вычислении верхней и нижней границ целевой функции на каждом из подмножеств. Нижнюю границу будем обозначать Н, а верхнюю Е. Соответственно Hi Eo, то это подмножество не содержит точку оптимума и может быть исключено из дальнейшего рассмотрения. Если верхняя граница Ei H заменяем Н на min Hi. Если Е=Н, то задача решена, иначе надо продолжить процедуру ветвления и вычисления верхней и нижней границ. При этом разбиению на очередном шаге могут подвергаться все или только некоторые подмножества до достижения равенства верхней и нижней границ, причём не на отдельном подмножестве, а для допустимой области в целом.

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

Схему динамического программирования при движении от начальной точке к конечной (рис. 5.1) можно представлять как процедуру ветвления.

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

Рис. 5.1.

Теперь подмножествами Di являются множества траекторий, каждая из которых проходит через соответствующую i-ую точку.

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

Эффективность такого подхода зависит от точности получаемых оценок, т.е. от Ei - Hi, и от затрат времени на их вычисление.

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

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