j = 1 2 3 i = 1 0 = c2 3 Если на первой итерации из двух полученных маршрутов (1) выбрать один (например, 1,4 ), то на основе полученной остаточной матрицы с(рис. 7, 5°) в ходе второй итерации будет получен второй маршрут 1,4 (1), что и завершит получение решения.
Приложение Решение задачи коммивояжера размера 10 х модифицированным методом расширения цикла Матрица расстояний с (табл. 1) данного числового примера заимствована из [17], где приведено и оптимальное решение, полученное одним из известных методов:
0 1 =<1,3,7,10,8,6,2,5,4,9,1>, (1 )=1159. (1) Знание оптимального решения позволяет убедиться в том, что и для более общих условий (элементы сij равномерно распределены в диапазоне 0 – 1000) модифицированный МРЦ (раздел 3) с заданной достоверностью обеспечивает получение оптимального решения.
Для проведения расчетов без использования ЭВМ эстафетным методом (рис. 2) вычислены элементы совмещенной матрицы кротчайших маршрутов и их длин ||0 / L0 || (табл. 2). Покажем, что и для k,l k,l рассматриваемого примера существует хотя бы один начальный цикл , приводящий к оптимальному решению при использовании МРЦ (табл. 12) или ММРЦ (табл. 15). Из C10 =45 возможных начальных циклов по крайней мере цикл 1 = <3·5·3> = <3,6,5,4,1,3>, L <3·5·3> = 763, полученный согласно (3.7) и табл. 2, приводит к оптимальному решению, что видно из результатов расчетов, данных в табл. 3.
На первом шаге процесса (табл. 3, t = 1,) в интервал r с границами jr-1, jr последовательно включается каждый элемент G1 и вычисляются соответствующие приращения длины цикла:
t t r, = t =Lt ( ) ( ) r-( )+L 0 -cj.
,j,r jr-1 jr jr-1,, jr Например, для r = 1, (j0;j1) = (3;6) и = 7 имеем 1 1;7 = L1 3,7 +L1 0 - c3,6 = 141+ 422 - 200 = 363, (2) ( ) ( ) ( ) 7,при этом 376 = 3,7 0 = 3,7,5,4,9,6, U 7,что и записано в первой строке табл. 3.
Из (2) видно, что совместно с включенным в интервал (3;6) номером = 7 вошел также номер j = 9, т.е. вошло два активных (не включенных ранее) нмера: n1(1;7) = 2, {1} = {7;9} (табл. 3, строка 1). Далее вычисляется удельный прирост длины цикла (3.9):
t r, = t r, /nt r,, (1;7) = 363/2=181.
( ) ( ) ( ) Вычисление приращений (2) соответствует пункту 40 метода расширения цикла (рис. 3). Структура алгоритма остается такой же и для модифицированного МРЦ, если учесть, что дополнительно в 40 следует вычислить и величину t r,. В строках 2 – 24 (табл. 3) записаны те же ( ) величины для других сочетаний r и.
Минимальному значению 1 соответствует включение элемента 1 = в интервал r1 = 5 ( 1 5;9 =15), (рис. 3, 50). Далее выполняется пересчет (60) ( ) текущих величин, новые значения которых записаны в строке 25 табл. 3.
Если еще не все индексы Gt включены в цикл (-80, т.е. Gt+1 ), то итерация повторяется (t = 2). Исходная информация записана в строке 25 и снова выполняются 3 – 60. В рассматриваемом примере величины t+1 r, ( ) изменятся только для интервалов, смежных с включенным номером 1 = (в строке 25 включенный элемент выделен жирным шрифтом). В строках 26 – 31 записаны результаты для новых интервалов ({r}={5;6}). Для неизменившихся интервалов используется ранее полученная информация, скорректированная в связи с исключением элемента j1 = 9 из правого столбца табл. 3. Исключение индекса j = 9 из правого столбца приведет к исключению строк 3, 7, 11, 15, 19, 23. Элементы 1 r, в строках 1, 14, 16, ( ) 18, 20 увеличатся в связи с уменьшением значения nt+1 r,
( ) ( ) Новые значения удельных приращений находятся по рекуррентной формуле nt r, t+1 r, = t r, ( ) ( )( ).
nt+При выполнении 50 (вместо 2 используется 7 ) на шаге t = минимальным оказывается элемент 2 (1;10) = 127, при этом в интервал r = 1, (3;6) войдут все оставшиеся элементы (табл. 3, строка 4), и процесс построения цикла при данном начальном цикле (k = 3) закончится. В строке 32 записано полученное решение. Это решение сравнивается с предыдущим, и если оно дает худший результат (+90), то формируется новый начальный цикл (100) и т.д., до получения совпадающего решения (+110), что и является условием окончания процесса. Учитывая инвариантность цикла к исходному пункту коммивояжера (подраздел 3.4), полученное решение может быть приведено к виду (1).
В наихудшем случае (рассчитывается C2 вариантов с различными n начальными циклами) оценка требуемого объема элементарных операций увеличится от полинома третьей степени до пятой (C2 < 0,5n2). Однако n универсальность модифицированного МРЦ (возможность решения при 1) в значительной мере компенсирует этот недостаток, не представляющий, впрочем, серьезных трудностей для современных ЭВМ.
2. Кристофидес Н. Теория графов. Алгоритмический подход. – М.:
Мир, 1978.
3. Смирнов Д.В. Методы повышения эффективности функционирования систем передачи данных: Дис. … канд. техн. наук. – Тверь: ТГТУ, 2001. – 156 с.
4. Ford L.R., Fulkerson D.R. Solving the Transportation Problem. – Santa Monica, 1956.
5. Вагнер Г. Основы исследования операций: Т. 1 / Пер. с англ. – М.:
Мир, 1972. – 335 с.
6. Советов Б.Я., Яковлев С.А. Построение сетей интегрального обслуживания. – Л.: Машиностроение, 1990. – 330 с.
7. Майника Э. Алгоритмы оптимизации на сетях и графах. – М.:
Мир, 1981.
8. Васильев Н.С. Математическое моделирование в задачах маршрутизации СПД (многокритериальный подход): Дис. … док. физ.-мат.
наук. – М.: ИВВС; РАН, 1999. – 231 с.
9. Пойа Д. Математическое открытие: Пер. с англ. – М.: Наука, 1970.
– 452 с.
10. Берзин Е.А. Оптимальное распределение ресурсов и элементы синтеза систем. – М.: Сов. радио, 1974. – 303 с.
11. Гмурман В.Е. Теория вероятностей и математическая статистика.
– М.: Высшая школа, 1977. – 479 с.
12. Основы теории оптимального управления / Под ред. В.Ф.
Кротова. – М.: Высшая школа, 1990. – 430 с.
13. Немировский А.С., Юдин Д.Б. Сложность задач и эффективность методов оптимизации. – М.: Наука, 1979. – 389 с.
14. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: МЦНМО, 2002. – 960 с.
15. Клейнрок Л. Теория массового обслуживания. – М.:
Машиностроение, 1979. – 431 с.
16. Клейнрок Л. Вычислительные системы с очередями. – М.: Мир, 1979. – 600 с.
17. Сигал И.Х. Алгоритм решения задачи коммивояжера с оценкой точности // Алгоритмы и алгоритмические языки. – 1973. – Вып. 6. – С. 49 – 61.
18. Берзин Е.А. Оптимальное распределение ресурсов и теория игр. – М.: Радио и связь, 1983. – 183 с.
ОГЛАВЛЕНИЕ ПРЕДИСЛОВИЕ.................................................................................................................... ПРИНЯТЫЕ ОБОЗНАЧЕНИЯ................................................................................................ ВВЕДЕНИЕ............................................................................................................................... 1. НЕКОТОРЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ................................................................. 1.1. Основные понятия и определения.................................................................................................... 2. ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ НА ГРАФЕ.............................................................. 2.1. Постановка задачи................................................................................................................................ 2.2. Эстафетный метод построения кратчайшего пути на графе..................................................... 2.3. Алгоритм эстафетного метода (ЭМ)................................................................................................ 2.4. Оценка эффективности алгоритма................................................................................................... Выводы...........................................................................................................................................................
3. КЛАССИЧЕСКАЯ ЗАДАЧА КОММИВОЯЖЕРА И ЕЕ РЕШЕНИЕ МЕТОДОМ РАСШИРЕНИЯ ЦИКЛА........................................................................................................ 3.1. Постановка классической задачи коммивояжёра ( = 1)....................................................... 3.2. Метод расширения цикла, алгоритм, пример вычисления и эффективность алгоритма... 3.3. Модифицированный метод расширения цикла, примеры вычислений и эффективность метода............................................................................................................................. Выводы........................................................................................................................................................... 4. ОБОБЩЕННАЯ ЗАДАЧА КОММИВОЯЖЕРА............................................................... 4.1. Постановка обобщенной задачи коммивояжера........................................................................... 4.2. Алгоритм решения обобщённой задачи коммивояжера методом расширения цикла при полной матрице расстояний ( = 1) и пример расчёта.......... 4.3. Модифицированный метод расширения цикла и решение обобщенной задачи коммивояжера..................................................................................... 4.4. Решение обобщенной задачи коммивояжера методом последовательного наращивания цикла................................................................................................. Выводы........................................................................................................................................................... 5. СРАВНИТЕЛЬНАЯ ОЦЕНКА РАССМОТРЕННЫХ МЕТОДОВ РЕШЕНИЯ ЗАДАЧ КОММИВОЯЖЕРА................................................................................................................ 5.1. Решение тестового примера задачи коммивояжера методом расширения цикла....................................................................................................................... 5.2. Решение тестового примера задачи коммивояжера модифицированным методом расширения цикла................................................................................ 5.3. Решение тестового примера задачи коммивояжера комбинированным методом расширения цикла................................................................................... 5.4. Решение тестового примера задачи коммивояжера методом последовательного наращивания цикла................................................................................................. 5.5. Решение тестового примера обобщенной задачи коммивояжера методом последовательного наращивания цикла................................................................................ 5.6. Решение тестового примера обобщенной задачи коммивояжера методом расширения цикла....................................................................................................................... 5.7. Решение тестового примера обобщенной задачи коммивояжера модифицированным методом расширения цикла................................................................................ Выводы........................................................................................................................................................... 6. ПРОПУСКНАЯ СПОСОБНОСТЬ СЕТИ.......................................................................... 6.1. Построение маршрута с максимальной пропускной способностью методом улучшения оценок...................................................................................................................... 6.2. Определение максимальной пропускной способности сети..................................................... Выводы......................................................................................................................................................... 7. ПОИСК ОСОБЫХ ТОЧЕК НА ГРАФЕ.......................................................................... 7.1. Поиск точек с минимальной суммарной длиной маршрутов.................................................. 7.2. Учет грузопотоков и грузоподъемности транспортных средств при размещении баз..... 7.3. Поиск минимаксных точек на графе............................................................................................. Выводы......................................................................................................................................................... ЗАКЛЮЧЕНИЕ.................................................................................................................... Приложение 1. Определение пропускной способности сети методом Форда-Фалкерсона и методом улучшения оценок............................................................................................... Приложение 2. Решение задачи коммивояжера размера 10 х 10 модифицированным методом расширения цикла................................................................................................. БИБЛИОГРАФИЧЕСКИЙ СПИСОК................................................................................. Евгений Александрович Берзин ЭЛЕМЕНТАРНЫЕ РЕШЕНИЯ НЕЭЛЕМЕНТАРНЫХ ЗАДАЧ НА ГРАФАХ Учебное пособие Редактор Е.В. Маняшина Корректор Т.С. Синицына Технический редактор Г.В. Комарова Подписано в печать 28.01.Формат 60 х 84 / 16 Бумага писчая Физ. печ. л. 8,5 Усл.-печ. л. 7,9 Уч.-изд. л. 7,Тираж 100 экз. Заказ № 13 Цена 78 руб. 70 коп.
