WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 11 | 12 ||

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) в значительной мере компенсирует этот недостаток, не представляющий, впрочем, серьезных трудностей для современных ЭВМ.

Таблица 1. c = cij, =j = 1 2 3 4 5 6 7 8 9 i = 1 0 921 56 977 34 11 45 56 101 2 259 0 416 675 91 766 857 622 479 3 580 680 0 260 940 200 141 341 482 4 303 125 428 0 554 982 536 518 54 5 625 197 822 19 0 842 861 702 563 6 829 94 923 17 940 0 957 896 853 7 601 350 952 302 253 555 0 808 363 8 535 707 242 948 190 139 329 0 468 9 264 61 325 386 711 96 807 903 0 10 614 324 938 263 201 464 665 129 794 ij/Lij Таблица 2.

j = 1 2 3 4 5 6 7 8 9 1,6,4,1,1 1,6,2 1,3 1,6,4 1,5 1,6 1,7 1,8 1,i = 0 105 56 28 34 11 45 56 2,1 2,2 2,1,3 2,5,4 2,5 2,5,4,9,6 2,1,7 2,10,8 2,5,4,9 2,259 0 315 110 91 260 304 230 164 3,6,4,1 3,6,2 3,3 3,6,4 3,6,2,5 3,6 3,7 3,8 3,6,4,9 3,7,520 294 0 217 385 200 141 341 271 4,1 4,9,2 4,1,3 4,4 4,9,2,5 4,9,6 4,1,7 4,9,2,10,8 4,9 4,9,2,303 115 359 0 206 150 348 345 54 5,4,1 5,4,9,2 5,4,1,3 5,4 5,5 5,4,9,6 5,4,1,7 5,4,9,2,10,8 5,4,9 5,4,9,2,322 134 378 19 0 169 367 364 73 6,4,1 6,2 6,4,1,3 6,4 6,2,5 6,6 6,4,1,7 6,2,10,8 6,4,9 6,2,320 94 376 17 185 0 365 324 71 7,5,4,1 7,2 7,10,8,3 7,5,4 7,5 7,5,4,9,6 7,7 7,10,8 7,5,4,9 7,575 350 543 272 253 422 0 301 326 8,6,4,1 8,6,2 8,3 8,6,4 8,5 8,6 8,7 8,8 8,6,4,9 8,6,2,459 233 242 156 190 139 329 0 210 9,1 9,2 9,1,3 9,6,4 9,2,5 9,6 9,1,7 9,2,10,8 9,9 9,2,264 61 320 113 152 96 309 291 0 10,5,4,1 10,2 10,8,3 10,5,4 10,5 10,8,6 10,8,7 10,8 10,5,4,9 10,523 324 371 220 201 268 458 129 274 Таблица t=1: L1 3,6,2,5,4,1,3 = 763, G1 = 7,8,9,{ } t № r jr-1, jr t r, { } jr-1 jr ( ) t nt 1 1 7 3;6 3,7,5,4,9,6 141+422-200=363 2 181 7,2 1 8 3;6 3,8,6 341+139-200=280 1 280 3 1 9 3;6 3,6,4,9,6 271+96-200=167 1 167 4 1 10 3;6 3,7,10,8,6 313+268-200=381 3 127 7,8,5 2 7 6;2 6,4,1,7,2 365+350-94=621 1 621 6 2 8 6;2 6,2,10,8,6,2 324+233-94=463 2 231 8,7 2 9 6;2 6,4,9,2 71+61-94=38 1 38 8 2 10 6;2 6,2,10,2 195+324-94=425 1 425 9 3 7 2;5 2,1,7,5 304+253-91=466 1 466 10 3 8 2;5 2,10,8,5 230+190-91=329 2 164 8,11 3 9 2;5 2,5,4,9,2,5 164+152-91=225 1 225 12 3 10 2;5 2,10,5 101+201-91=211 1 211 13 4 7 5;4 5,4,1,7,5,4 367+272-19=620 1 620 14 4 8 5;4 5,4,9,2,10,8,6,4 364+156-19=501 3 167 8,9,15 4 9 5;4 5,4,9,6,4 73+113-19=167 1 167 16 4 10 5;4 5,4,9,2,10,5,4 235+220-19=436 2 218 9,17 5 7 4;1 4,1,7,5,4,1 348+575-303=620 1 620 18 5 8 4;1 4,9,2,10,8,6,4,1 345+459-303=501 3 167 8,9,19 5 9 4;1 4,9,1 54+265-303=15 1 15 20 5 10 4;1 4,9,2,10,5,4,1 216+523-303=436 2 218 9,21 6 7 1;3 1,7,10,8,3 45+543-56=532 3 177 7,8,22 6 8 1;3 1,8,3 56+242-56=242 1 242 23 6 9 1;3 1,6,4,9,1,3 82+320-56=346 1 346 24 6 10 1;3 1,10,8,3 157+371-56=472 2 236 8,t=2: L2 3,6,2,5,4,9,1,3 = 778, G2 = 7,8,{ } 26 5 7 4;9 4,1,7,5,4,9 348+326-54=620 1 620 27 5 8 4;9 4,9,2,10,8,6,4,9 345+210-54=501 2 250 8,28 5 10 4;9 4,9,2,10,5,4,9 216+274-54=436 1 436 29 6 7 9;1 9,1,7,5,4,1 309+575-264=620 1 620 30 6 8 9;1 9,2,10,8,6,4,1 291+459-264=486 2 243 8,31 6 10 9;1 9,2,10,5,4,1 162+523-264=421 1 421 0 3 = 3,7,10,8,6,2,5,4,9,1,3, L 3 = 778 + 381 = 1159, G3 = ( ) БИБЛИОГРАФИЧЕСКИЙ СПИСОК 1. Берж К. Теория графов и её применение. – М.: ИИЛ, 1962. – 316 с.

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 коп.

Pages:     | 1 |   ...   | 11 | 12 ||






















© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.