Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Сигал И.Х. -> "Введение в прикладное дискретное программирование " -> 34

Введение в прикладное дискретное программирование - Сигал И.Х.

Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование — М.: ФИЗМАТЛИТ, 2003. — 240 c.
ISBN 5-9221-0377-6
Скачать (прямая ссылка): vvedenievprikladnoeprogrammirovanie2003.djvu
Предыдущая << 1 .. 28 29 30 31 32 33 < 34 > 35 36 37 38 39 40 .. 84 >> Следующая


3.4.5. Пример. Завершим решение примера. Удалив в матрице множества (1,4) первую строку и четвертый столбец и положив С41 = M, получим матрицу расстояний, из которой после приведения получим другую матрицу:

1 2 3 5 6 1 2 3 5 б
2 1 M 15 29 24 2 0 M 15 29 24
3 15 13 M 5 0 3 14 13 M 5 0
4 M 0 9 2 2 А M M Q о о
5 2 41 22 M 0 Ч: 0 и
6 13 0 0 0 M 5 1 41 22 M 0
h 1 = 1 6 12 0 0 0 M

Гз = 2

В первой из представленных матриц минимальный элемент в первом столбце равен 1; выполнив процедуру приведения, получим а = 1, поэтому для z Є (1,4) получаем в соответствии с (3.4.3) l(z) > 48 +

+ 1 = 49. Вычислим величины

Hj- ”21

— 16, #36 — 5, #42 — 2, #56 — 2,

&62 — 0, #63 = 9, #65 = 2, максимальное значение равно #21. Множество (1,4) разбиваем на два: (2,1) и (2,1). Переходы (2,1) и (1,4) образуют связный путь (2,1,4), поэтому в матрице множества (2,1) полагаем С42 = М. Полученную матрицу приводим, а = 2, тогда для z Є (2,1) получаем l(z) > 49 + 2 = 51. Для z Є (2,1) в соответствии с

(3.4.2) получаем l(z) > 49 + 16 = 65, это означает, что множество (2,1) исключаем из дальнейшего рассмотрения. В матрице множества (2,1) удаляем вторую строку и первый столбец, получим

2 3 5 6
3 13 M 5 0
4 M 7 0 0
5 41 22 M 0
6 0 0 0 M

2 3 5
3 13 M 5
4 M 7 0
6 0 0 M

гі = 5

2 3 5
3 8 M 0
4 M 7 0
6 0 M 0 M

Определяем величины Qij'.

#36 = 5, #45 = 0, #46 = 0, #56 = 22, #62 = 13, #63 = 7, #65 = О, максимальное значение равно #56- Множество (2,1) разбиваем на два: (5, 6) и (5, 6). Для z Є (5, 6) получаем l(z) > 51+22 = 73, это множество можно отсеять. Для Z Є (5,6) удаляем пятую строку и шестой столбец и полагаем Сб5 = М. Полученную матрицу приводим, а = 5; для z Є (5,6) получаем l(z) > 51 + 5 = 56. Определяем величины #^:

#35 = 8, #45 = 7, #62 = 8, #63 = 7.

Выбираем #35 = 8 и разбиваем множество (5,6) на два: (3,5) и (3,5). Для z Є (3, 5) получаем l(z) > 56 + 8 = 64, это множество пока отсеять нельзя. Для множества (3, 5) реализуем запрет подцикла в связном пу-
Гл. 3. Метод ветвей и границ

99

ти (3, 5, 6), полагая Сбз = M. Удалив третью строку и пятый столбец, получаем

2 3 2 3
4 M 7 п = 7 4 M 0
6 0 M 6 0 M

При этом а = 7 для z Є (3,5) получаем l(z) > 56 + 7 = 63. Из последней матрицы 2x2 получаем два перехода с нулевой длиной:

(6,2) и (4,3). Дерево ветвления с оценками показано на рис. 3.10.

После получения нулевых переходов конструируем маршрут Zo = = (1,4,3,5,6,2,1), l(zo) = 63, и вершина с оценкой 64 отбрасывается. Задача решена. Для ее решения выполнено пять ветвлений и решено десять оценочных подзадач.

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

7*
100

Разд. II. Комбинаторные методы решения задач

3.4.6. Пример решения симметричной задачи. Приведем результат решения симметричной задачи коммивояжера (? = Cjі) для следующей матрицы:

1 2 3 4 5 6
1 M 2 2 3 3 3
2 2 M 1 1 1 3
3 2 1 M 3 3 3
4 3 1 3 M 3 3
5 3 1 3 3 M 1
6 3 3 3 3 1 M

Оптимальное решение есть zо = (1,3,2,4,6,5,1), Z(^o) = 11. Дерево ветвления представлено на рис. 3.11.

Рис. 3.11

Из анализа дерева видно, что после получения вершины (6, 5) с оценкой 10 необходимо вернуться к вершине (2,4) с оценкой 9; после получения вершины (1,4) с оценкой 10 возвращаемся к вершине (6,5) и, произведя ветвление, получаем вершину (1,3), а затем вершину (3,2) с оценкой 11 и снова возвращаемся к вершине (1,4). Получив вершины (5,2) и (5,2) с оценками 12, возвращаемся к вершине (3, 2), и, дойдя до вершин (4, 6) и (5,1) с длиной маршрута Z(^o) = = 11, завершаем процесс.

В данном примере правило «идите вправо» также дает оптимальное решение, но после получения множества с оценкой 11 необходимо вернуться к множеству (2,4) с оценкой 9 и выполнить еще два ветвления.

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

101

3.4.7. Замечание о приведении матрицы расстояний. Существуют два способа приведения матриц расстояний:

1) сначала приведение по строкам, а затем по столбцам;

2) сначала приведение по столбцам, а затем по строкам.
Предыдущая << 1 .. 28 29 30 31 32 33 < 34 > 35 36 37 38 39 40 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100