Лекции по методам оптимизации - файл

Лекции по методам оптимизации
скачать (38.5 kb.)
Доступные файлы (2):
noname144kb.15.09.2000 12:55скачать
noname197kb.25.05.2005 19:34скачать


Бельский Аркадий Александрович. Вычислительная математика. Часть 2. Лекция 1


Вычислительная математика
Специальность ПО
5-й семестр
Конспект лекций
Лекция 1

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

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

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

предположим, что имеется вещественно-значная функция на множе-стве подмножеств множества M со следующими двумя свойствами:

1)для (здесь - множество, состоящее из един-ственного элемента );

2) если и , то .

В этих условиях можно организовать перебор элементов множества M с целью минимизации функции на этом множестве так:

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

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

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

Предположим, что ; тогда для любого элемента m множе-ства M, принадлежащего множеству , будут верны неравенства

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

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

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

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

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

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

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

пусть - полный ориентированный граф и -

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

Пусть конкретный состав множества вершин и

- весовая матрица данного орграфа, т.е.

,

причем для любого .

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

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

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

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

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

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

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

множеству  всех обходов коммивояжера сопоставлено чис-ло () и матрица M1.

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

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

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

Теперь выберем между множествами и то, на

котором минимальна функция  (т.е. то из множеств, которому соответствует меньшее из чисел () и ().

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

следующей лекции на конкретном примере.

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

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

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


Бельский Аркадий Александрович. Вычислительная математика. Часть 2. Лекция 1



Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации