147494 (Моделювання транспортної мережі), страница 2
Описание файла
Документ из архива "Моделювання транспортної мережі", который расположен в категории "". Всё это находится в предмете "транспорт" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "транспорт" в общих файлах.
Онлайн просмотр документа "147494"
Текст 2 страницы из документа "147494"
Одеська дорога широко взаємодіє з іншими видами транспорту – морським (у портах Одеса, Іллічевськ, Південний, Миколаїв і Херсон), річковим (у портах Ізмаїл на Дунаєві, Херсон і Черкаси на Дніпру) і автомобільним. Між портом Іллічевськ і болгарський порт Варна регулярно курсують морські залізничні пароми.
У районі тяжіння дороги протікає Дніпро. По ньому перевозять: униз – зернові вантажі, мінерально-будівельні матеріали, нагору – нафтові вантажі.
Станція Гомель відноситься до Білоруської залізниці.
-
Теоретичні положення з організації моделювання транспортних мереж
Задачу пошуку найкоротшого шляху між джерелом і стоком (початковий і кінцевий пункти мережі) можна вирішити за допомогою алгоритму Дейкстри. Алгоритм Дейкстри розроблений для знаходження найкоротшого шляху між заданим вихідним вузлом і будь-яким іншим вузлом мережі.
У процесі виконання цього алгоритму при переході від вузла до наступного вузла використовується спеціальна процедура позначки ребер. Позначимо через найкоротшу відстань від вихідного вузла 1 до вузла , через – довжину ребра . Тоді для вузла визначимо мітку в такий спосіб:
Мітки вузлів в алгоритмі Дейкстри можуть бути двох типів: тимчасові і постійні. Тимчасова мітка згодом може бути замінена на іншу тимчасову, якщо буде знайдений більш короткий шлях до даного вузла. Коли ж стане очевидним, що не існує більш короткого шляху від вихідного вузла до даного, статус тимчасової мітки змінюється на постійний.
Розрахункова схема алгоритму складається з наступних кроків.
Крок 0. Вихідному вузлу (вузол 1) привласнюється мітка . Думаємо .
Крок i. а) Обчислюються тимчасові мітки для усіх вузлів , які можна досягти безпосередньо з вузла , і які не мають постійних міток. Якщо вузол уже має мітку , отриману від іншого вузла , і якщо , тоді мітка заміняється на .
б) Якщо усі вузли мають постійні мітки, процес обчислень закінчується. У противному випадку вибирається мітка з найменшим значенням відстані серед усіх тимчасових міток (якщо таких міток декілька, то вибір довільний). Думаємо і повторюємо крок .
Задача визначення найкоротших відстаней між елементами транспортної мережі (Алгоритм Флойда).
Дана задача вирішується за допомогою алгоритму Флойда.
Цей алгоритм більш загальний у порівнянні з алгоритмом Дейкстри, тому що він знаходить найкоротші шляхи між будь-якими двома вузлами мережі. У цьому алгоритмі мережа представлена у виді квадратної матриці з рядками і стовпцями. Елемент дорівнює відстані від вузла до вузла , що має кінцеве значення, якщо існує дуга , і дорівнює нескінченності в противному випадку.
Покажемо спочатку основну ідею методу Флойда. Нехай є три вузли і задані відстані між ними (рис. 3.1). Якщо виконується нерівність , то доцільно замінити шлях шляхом . Така заміна (далі її будемо умовно називати трикутним оператором) виконується систематично в процесі виконання алгоритму Флойда.
Рис. 3.1. Трикутний оператор
Алгоритм Флойда вимагає виконання наступних дій.
Крок 0. Визначаємо початкову матрицю відстаней і матрицю послідовності вузлів . Діагональні елементи обох матриць позначаються знаком «–», що показує, що ці елементи в обчисленнях не беруть участь. Думаємо :
Рис. 3.2. Початкова ситуація
Основний крок k. Задаємо рядок і стовпець як ведучий рядок і ведучий стовпець. Розглядаємо можливість застосування трикутного оператора до всіх елементів матриці . Якщо виконується нерівність , тоді виконуємо наступні дії:
-
створюємо матрицю шляхом заміни в матриці елемента на суму ,
-
створюємо матрицю шляхом заміни в матриці елемента на . Думаємо і повторюємо крок .
Пояснимо дії, виконувані на -м кроці алгоритму, представивши матрицю так, як вона показана на рис 3.3. На цьому рисунку рядок і стовпець є ведучими. Рядок – будь-який рядок з номером від 1 до , а рядок – довільний рядок з номером від до . Аналогічно стовпець представляє будь-як стовпець з номером від 1 до , стовпець – довільний стовпець з номером від до . Трикутний оператор виконується в такий спосіб. Якщо сума елементів ведучих рядка і стовпця (показаних у квадратах) менше елементів, що знаходяться в перетинанні стовпця і рядка (показаних у кружках), що відповідають розглянутим ведучим елементам, то відстань (елемент у кружку) заміняється на суму відстаней, представлених ведучими елементами:
Рис. 3.3. Ілюстрація алгоритму Флойда
Після реалізації кроків алгоритму визначення по матрицях і найкоротшому шляху між вузлами і виконується за наступними правилами.
-
Відстань між вузлами і дорівнює елементові в матриці .
-
Проміжні вузли шляху від вузла до вузла визначаємо по матриці . Нехай , тоді маємо шлях . Якщо далі і , тоді вважаємо, що весь шлях визначений, тому що знайдені всі проміжні вузли. У противному випадку повторюємо описану процедуру для шляхів від вузла до вузла і від вузла до вузла .
При аналізі транспортних мереж часто виникає задача визначення максимального потоку, що може пропустити дана мережа, а також задача розподілу цього потоку по дугах мережі.
З математичної точки зору задача про максимальний потік формулюється в такий спосіб: при заданій конфігурації мережі і відомої пропускної здатності знайти ненегативні значення , що задовольняють умовам і, що максимізують функцію , тобто
Алгоритм для знаходження максимального потоку був запропонований Фордом і Фалкерсоном і полягає в поступовому збільшенні потоку, що пропускається по мережі, доти, поки він не стане найбільшим. Алгоритм заснований на теоремі Форда-фалкерсона: у будь-якій транспортній мережі максимальний потік із джерела в стік , дорівнює мінімальній пропускній здатності розрізу, що відокремлює від .
Крок 0. Призначаємо вузлові 15 постійну мітку [0, -].
Крок 1. З вузла 15 можна досягти вузлів 21 2 12. Обчислюємо мітки для цих вузлів, у результаті одержуємо наступну таблицю міток:
Вузол
Мітка
Статус мітки
15
Постійна
21
[512,15]
Тимчасова
2
[237,15]
Тимчасова
Серед вузлів 21, 2, 12, вузол 12 має найменше значення відстані (U12=172). Тому статус мітки цього вузла змінюється на «постійна».
Крок 2. З вузла 12 можна потрапити у вузли 2, 23, 22. Одержуємо наступний список вузлів.
Тимчасовий статус мітки [237,15] вузла 2 заміняється на постійний (U2=237).
Крок 3. З вузла 2 можна досягти вузлів 21, 22, 31. Після обчислення міток одержимо наступний їх список:
Вузол
Мітка
Статус мітки
15
Постійна
12
[172,15]
Постійна
2
[237,15]
Постійна
21
[512,15]
Тимчасова
21
[370+512,2]=[882,2]
Тимчасова
22
[1009,12]
Тимчасова
22
[696+237,2]=[933,2]
Тимчасова
23
[810,12]
Тимчасова
31
[655+237,2]=[892,2]
Тимчасова
Тимчасовий статус мітки [512,15] вузла 21 заміняється на постійний (U21=512).
Крок 4. З вузла 21 можна досягти вузлів 31. Після обчислення міток одержимо наступний їх список:
Вузол
Мітка
Статус мітки
15
Постійна
12
[172,15]
Постійна
2
[237,15]
Постійна
21
[512,15]
Постійна
22
[933,2]
Тимчасова
23
[810,12]
Тимчасова
31
[892,2]
Тимчасова
31
[512+289,21]= [801,21]
Тимчасова
Тимчасовий статус мітки [801,21] вузла 31 заміняється на постійний (U31=801).
Крок 5. З вузла 31 можна досягти вузлів 22, 38. Після обчислення міток одержимо наступний їх список:
Вузол
Мітка
Статус мітки
15
Постійна
12
[172,15]
Постійна
2
[237,15]
Постійна
21
[512,15]
Постійна
31
[801,21]
Постійна
22
[933,2]
Тимчасова
22
[801+237,31]= [1038,31]
Тимчасова
23
[810,12]
Тимчасова
38
[801+197,31]= [992,31]
Тимчасова
Тимчасовий статус мітки [810,12] вузла 23 заміняється на постійний (U23=810).
Крок 6. З вузла 23 можна досягти вузла 22, 38, 3. Після обчислення міток одержимо наступний їх список:
Вузол
Мітка
Статус мітки