Алгоритмическая схема метода

МЕТОД ВЕТВЕЙ И ГРАНИЦ

Общая схема метода

Рассмотрим задачу дискретной оптимизации вида

             (1)                                           

где  - некоторое конечное множество из . 

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

1) построение дерева допустимых вариантов;

2) составление оценочных задач;

3) определение правила обхода дерева вариантов;

4)  отбрасывание “неперспективных” множеств вариантов;

5) проверка критерия останова.

Рассмотрим подробно каждый из указанных модулей.

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

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

2) Оценкой функции  задачи (1) на множестве  называется такое число , что . Для получения оценок составляется оценочная задача, решение которой используется для вычисления соответствующей оценки. К оценочным задачам предъявляются следующие требования: с одной стороны, их решение не должно занимать много времени. Но вместе с тем оценки, полученные с их помощью должны быть как можно точнее (т.е. разность не должна быть слишком большой). Такие требования объясняются тем, что именно оценки используются при отбрасывании неперспективных множеств (следовательно, при сокращении перебора). При составлении оценочных задач можно воспользоваться универсальным правилом: отбросить в исходной задаче наиболее “тяжелые” (трудновыполнимые) ограничения (например, требование целочисленности). Получаемые оценки должны обладать монотонностью в том смысле, что оценки подмножеств не должны быть меньше оценки  разветвленного множества (то есть если , то должно быть выполнено условие .

3) Правило обхода дерева вариантов в процессе работы алгоритма называют стратегией обхода дерева. Существует множество различных стратегий. Наиболее распространенными являются три из них.

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

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

c) Смешанная стратегия. В этом случае для продвижения “вниз по дереву” используется односторонний обход дерева вариантов, а при “подъеме вверх” ищется множество с минимальной оценкой.

4) Будем называть множество неперспективным, если относительно него принимается решение о выбрасывании его из дальнейшего рассмотрения. Отбрасывание множеств в ходе решения обеспечивает сокращение перебора. Исключение множеств вариантов из дальнейшего рассмотрения производится с помощью оценок этих множеств и рекорда. Рекордом (или рекордным значением)называют значение целевой функции в “лучшей” (доставляющей наименьшее значение) из полученных допустимых точек. Для определения начального рекорда рекомендуется воспользоваться каким-либо приближенным алгоритмом или другой априорной информацией, если она имеется. По ходу решения задачи рекорд обновляется. Справедливо следующее утверждение. Если оценка некоторого подмножества больше имеющегося рекорда, то среди точек данного подмножества нет  решения задачи. Это утверждение позволяет сформулировать основное правило сокращения перебора: если оценка множества больше рекордного значения, то такое множество вариантов выбрасывается из дальнейшего рассмотрения. Отметим, что множество может не подвергаться последующему ветвлению и по другим причинам: если при решении оценочной задачи на данном множестве была получена точка, являющаяся допустимой в исходной задаче, или если допустимое множество оценочной задачи пусто.

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

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

УПРАЖНЕНИЯ

1. Докажите свойство монотонности оценок в условиях, при которых ветвление и составление оценочных задач осуществляется по правилам, указанным в п.п. 1 и 2.

2. Предложите другие стратегии обхода дерева вариантов.

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

4. В предложенной алгоритмической схеме отыскивается одно решение, даже если решение в задаче не единственно. Где происходит потеря решения? Исправьте алгоритм таким образом, чтобы появилась возможность отыскания всех решений задачи.

 

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

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

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

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

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

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

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

Пусть - множество всех возможных маршрутов.

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

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

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

УПРАЖНЕНИЯ

1. Предложите другие стратегии ветвления в задаче коммивояжера.

2. Решите задачу коммивояжера с матрицей:

a)                                                                                                                                  b)

+	3	93	13	33	9	57
4	+	77	42	21	16	34
45	17	+	36	16	28	25
39	90	80	+	56	7	91
28	46	88	33	+	25	57
3	88	18	46	92	+	7
44	26	33	27	84	39	+

+	27	43	16	30	26
7	+	16	1	30	25
20	13	+	35	5	0
21	16	25	+	18	18
12	46	27	48	+	5
23	5	5	9	5	+

 С =              C=

                            

 

             

Ответ: 1-4-6-7-3-5-2-1, L= 126.                      Ответ: 4-3-5-6-2-1-4, L= 63.

c)                                                              d)

+	14	9	8	10	6
10	+	7	4	11	5
11	10	+	10	20	11
12	4	4	+	9	4
13	10	9	7	+	10
11	9	8	3	4	+

+	4	10	13	4	8
2	+	9	7	6	7
8	5	+	5	5	9
5	8	5	+	7	10
6	4	4	9	+	4
5	1	4	8	3	+

 

 С =  С =     С =              

 

       

      Ответ: 3-1-6-5-4-2-3, L= 39.                        Ответ: 2-1-5-3-4-6-2, L= 26.

 

 

Пример.

 

        

 

Полагаем R= .

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

Так как точка не целочисленная, осуществляем ветвление (например, по первой координате): , .

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

Так как целочисленного решения опять не получено, осуществляем ветвления множества : , .

Решаем оценочные задачи на множествах  и . Получаем , , , .

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

Решаем оценочные задачи на множествах  и . Получаем , ,  Ø.

Получено целочисленное решение. Происходит смена рекорда R=-5. Множества ,  и  выбрасываем из рассмотрения как неперспективные (их оценки превышают или равны рекордному значению).

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

Дерево вариантов в данной задаче имеет вид:

 

                                                              

 

                                                                        

                              

                        

                                                             

                              

 

 

                   

 

УПРАЖНЕНИЯ

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

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

3. Решить ЦЗЛП:

                  

Ответ: =(2,4)              Ответ: =(7,4)                 Ответ: =(2,5)

  

      

 

ЗАДАЧА

О НАЗНАЧЕНИЯХ.

ВЕНГЕРСКИЙ

МЕТОД РЕШЕНИЯ

Венгерский метод

 

Алгоритм венгерского метода включает в себя 4 этапа.

Приведение матрицы.

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

2. Получение новых нулей при .

3. Отыскание n независимых нулей  при .

Рассмотрим каждый этап подробнее.

Этап 1.

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

1.

2.

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

Пример 1. Пусть

2	1	2	1	0
1	3	5	7	4
2	7	8	6	9
1	5	4	7	8
1	3	4	9	10

 

 

С=

Легко проверить, что

2	0	0	0	0
0	1	2	5	3
0	4	4	3	7
0	3	1	5	7
0	1	1	7	9

 

2	1	2	1	0
0	2	4	6	3
0	5	6	4	7
0	4	3	6	7
0	2	3	8	9

 

=                                 , A =,

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

Этап 2.

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

Теорема 3. Максимальное число независимых нулей равно минимальному суммарному числу горизонтальных и вертикальных линий (строк и столбцов), которыми можно зачеркнуть все нулевые элементы приведенной матрицы.

Пример 2. Пусть имеется приведенная матрица из примера 1.

2	0	0	0	0
0	1	2	5	3
0	4	4	3	7
0	3	1	5	7
0	1	1	7	9

 

 

=

                                     

 

 

Все ее нули содержат 1-я горизонталь и 1-я вертикаль, следовательно, здесь k =2 < 5. При решении задачи о назначениях будем проводить указанные линии, в результате чего некоторые элементы окажутся зачеркнутыми, другие - зачеркнутыми дважды и остальные - незачеркнутыми.

Этап 3.

 Обозначим через  элемент приведенной матрицы , зачеркнутый r раз (r =0, 1, 2) на 2-м этапе, и положим , где минимум берется по всем i, j, т.е. ищется наименьший из незачеркнутых элементов матрицы . Построим матрицу , проведя пересчет элементов матрицы  следующим образом:

a) из элементов  вычитается значение ;

b) элементы  остаются без изменения;

c) к элементам  прибавляется значение .

Такие преобразования являются следствием применения Теоремы 1, согласно

которой задача с новой матрицей   оказывается эквивалентной исходной и,

кроме того, элементы этой новой матрицы неотрицательны.

Если  оказалась неприведенной матрицей, то следует перейти к этапу 1.

Если же - приведенная матрица, то переходят к этапу 2.

Пример 3. Взяв матрицу  из примера 2, пересчитаем ее элементы

при , в итоге получим приведенную матрицу

 

3	0	0	0	0
0	0	1	4	2
0	3	3	2	6
0	2	0	4	6
0	0	0	6	8

=

 

Все ее нули содержат, например, 1-я горизонталь и три вертикали: 1-я, 2-я, 3-я. Следовательно, здесь k =4 < 5 и .   

Еще один пересчет дает приведенную матрицу

5	2	2	0	0
0	0	1	2	0
0	3	3	0	4
0	2	0	2	4
0	0	0	4	6

 

=

 

Здесь уже k=n= 5.

Этап 4.

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

1. В результате удается выбрать n независимых нулей. ОСТАНОВ. Выписать ответ.

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

Пример 4. Взяв матрицу  из примера 3, замечаем, что независимыми

здесь будут нули с индексами (1, 5), (2, 2), (3, 4), (4, 3), (5, 1). Это

означает, что ответом в задаче о назначениях с матрицей C из примера 1

является матрица назначений вида

0	0	0	0	1
0	1	0	0	0
0	0	0	1	0
0	0	1	0	0
1	0	0	0	0

,;;; для которой .

 

Важно отметить, что наряду с указанными, здесь будут также независимыми нули с индексами (1, 4), (2, 5), (3, 1), (4, 3), (5, 2). Следовательно, эта задача о назначениях имеет еще один ответ- матрицу назначений вида

0	0	0	1	0
0	0	0	0	1
1	0	0	0	0
0	0	1	0	0
0	1	0	0	0

 , причем .

 

 

УПРАЖНЕНИЯ

1. Является ли данная матрица приведенной? Укажите количество в ней независимых нулей.

а)                                               в)

2	0	0	0	0
0	1	2	5	3
0	4	4	3	7
0	3	1	5	7
0	1	1	7	9

0	1	3	2	4
1	-1	6	0	3
3	0	-4	3	8
2	5	0	-5	7
4	3	8	7	0

 

пп =                            бьбьбю =

 

2. Решите задачу о назначениях с матрицей С вида:

а)                                    в)                                          c)

2	3	4	2	4	0
3	5	6	7	4	3
6	7	2	6	2	6
3	5	7	4	3	1
8	3	5	2	1	2
1	5	6	4	9	1

2	2	1	2	1	0
1	3	5	6	9	4
2	7	8	5	3	6
1	5	4	7	8	3
1	3	4	9	5	6
2	4	6	5	3	1

3	4	2	1	3	0
4	3	6	7	3	4
7	6	2	6	3	5
1	4	7	8	3	2
3	2	4	8	4	6
1	6	5	4	9	2

 

=                           б ь =       mdhs =     

 

f

 

 

 

МЕТОДЫ ОТСЕЧЕНИЙ

  Первый алгоритм Гомори

Рассмотрим целочисленную задачу линейного программирования в следующей форме:

            (1)

               (2)                            

            (3)                                                               

               (4)

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