147494 (Моделювання транспортної мережі), страница 3
Описание файла
Документ из архива "Моделювання транспортної мережі", который расположен в категории "". Всё это находится в предмете "транспорт" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "транспорт" в общих файлах.
Онлайн просмотр документа "147494"
Текст 3 страницы из документа "147494"
15
Постійна
12
[172,15]
Постійна
2
[237,15]
Постійна
21
[512,15]
Постійна
31
[801,21]
Постійна
23
[810,12]
Постійна
22
[933,2]
Тимчасова
22
[810+535,23]= [1345,23]
Тимчасова
38
[992,31]
Тимчасова
38
[810+929,23]= [1739,23]
Тимчасова
3
[810+1045,23]= [1855,23]
Тимчасова
Тимчасовий статус мітки [933,2] вузла 22 заміняється на постійний (U22=933).
Крок 7. З вузла 22 можна досягти вузлів 38, 3. Після обчислення міток одержимо наступний їх список:
Вузол
Мітка
Статус мітки
15
Постійна
12
[172,15]
Постійна
2
[237,15]
Постійна
21
[512,15]
Постійна
31
[801,21]
Постійна
23
[810,12]
Постійна
22
[933,2]
Постійна
38
[992,31]
Тимчасова
38
[933+427,22]= [1360,22]
Тимчасова
3
[1855,23]
Тимчасова
3
[933+938,22]= [1871,22]
Тимчасова
Тимчасовий статус мітки [992,31] вузла 38 заміняється на постійний (U38=992).
Крок 8. З вузла 38 можна досягти вузла 3. Після обчислення міток одержимо наступний їх список:
Вузол
Мітка
Статус мітки
15
Постійна
12
[172,15]
Постійна
2
[237,15]
Постійна
21
[512,15]
Постійна
31
[801,21]
Постійна
23
[810,12]
Постійна
22
[933,2]
Постійна
38
[992,31]
Постійна
3
[1855,23]
Тимчасова
3
[992+116,38]= [1108,38]
Тимчасова
На останньому кроці знайдено найкоротшу відстань для вузла 3 – [1108.38]. Таким чином статус мітки вузла 3 змінюється на постійний.
Кінцевий результат міток має такий вигляд:
Вузол
Мітка
Статус мітки
15
Постійна
12
[172,15]
Постійна
2
[237,15]
Постійна
21
[512,15]
Постійна
31
[801,21]
Постійна
23
[810,12]
Постійна
22
[933,2]
Постійна
38
[992,31]
Постійна
3
[1108,38]
Постійна
Найкоротший шлях між вузлом 15 і будь-яким іншим вузлом визначається починаючи з вузла призначення шляхом проходження їх у зворотному напрямку за допомогою інформації, представленої в постійних мітках. Найкоротший маршрут між вузлами 15 і 3 має таку послідовність вузлів: (3)→ [1108.38] →(38)→ [992.31] →(31)→ [801.21] →(21)→ (15).
Таким чином, одержуємо шлях загальною довжиною 1108 км.
4. Задача про максимальний потік (алгоритм Форда-Фалкерсона)
Рішення задачі складається з підготовчого етапу і кінцевого числа кроків, на кожнім з яких відбувається припустиме збільшення потоку. На підготовчому етапі формується матриця пропускних здатностей дуг мережі.
Таблиця 4.1. Матриця пропускних здатностей дуг мережі
| 15 | 12 | 2 | 21 | 31 | 23 | 22 | 38 | 3 | |
| 15 | - | 10 | 10 | 10- | |||||
| 12 | 7 | - | 7 | 7 | 7 | ||||
| 2 | 13 | 13 | - | 13 | 13 | 13 | |||
| 21 | 18+ | 18 | - | 18- | |||||
| 31 | 22 | 22+ | - | 22 | 22- | ||||
| 23 | 22 | - | 22 | 22 | 22 | ||||
| 22 | 21 | 21 | 21 | 21 | - | 21 | 21 | ||
| 38 | 28+ | 28 | 28 | - | 28- | ||||
| 3 | 7 | 7 | 7+ | - |
По табл. 4.1. знаходимо шлях l1=(15,21,31,38) зі станції 15 у 3 з позитивною пропускною здатністю. Елементи цього шляху 
позначаємо знаком «мінус», а симетричні 
– знаком «плюс». Визначаємо пропускну здатність знайденого шляху, що дорівнює найменшій з пропускних здатностей дуг: C1= min {10,18,22,28}=10.
Визначаються залишкові пропускні здатності дуг знайденого шляху і симетричних йому дуг. Для цього з елементів 
табл. 4.1. віднімаємо 
, а до елементів 
додаємо . У результаті одержимо нову табл. 4.2 зі зміненими пропускними здатностями.
Таблиця 4.2. Матриця пропускних здатностей дуг мережі
| 15 | 12 | 2 | 21 | 31 | 23 | 22 | 38 | 3 | |
| 15 | - | 10 | 10- | 0 | |||||
| 12 | 7 | - | 7 | 7 | 7 | ||||
| 2 | 13+ | 13 | - | 13 | 13 | 13- | |||
| 21 | 28 | 18 | - | 8 | |||||
| 31 | 22 | 32 | - | 22 | 12 | ||||
| 23 | 22 | - | 22 | 22 | 22 | ||||
| 22 | 21 | 21+ | 21 | 21 | - | 21 | 21- | ||
| 38 | 38 | 28 | 28 | - | 18 | ||||
| 3 | 7 | 7+ | 17 | - |
Позначаємо стовпці табл. 4.2, знаходимо другий шлях l2=(15,2,22) зі станції 15 у 3, і розставляємо знаки. Визначаємо пропускну здатність знайденого шляху, що дорівнює найменшій з пропускних здатностей дуг:
C2= min {10,13,21}=10.
Змінимо пропускні здатності позначених дуг на 
(табл. 4.3).
Таблиця 4.3. Матриця пропускних здатностей дуг мережі
| 15 | 12 | 2 | 21 | 31 | 23 | 22 | 38 | 3 | |
| 15 | - | 10- | 0 | 0 | |||||
| 12 | 7+ | - | 7 | 7- | 7 | ||||
| 2 | 23 | 13 | - | 13 | 13 | 3 | |||
| 21 | 28 | 18 | - | 8 | |||||
| 31 | 22 | 32 | - | 22 | 12 | ||||
| 23 | 22+ | - | 22 | 22 | 22- | ||||
| 22 | 21 | 31 | 21 | 21 | - | 21 | 11 | ||
| 38 | 38 | 28 | 28 | - | 18 | ||||
| 3 | 7+ | 17 | 17 | - |
Позначивши стовпці знаходимоl3=(15,12,23).
Величина потоку по шляху 
: C3= min {10,7,22,}=7.
Розрахувавши нові пропускні здатності дуг, приходимо до табл. 4.4.
Таблиця 4.4. Матриця пропускних здатностей дуг мережі
| 15 | 12 | 2 | 21 | 31 | 23 | 22 | 38 | 3 | |
| 15 | - | 3- | 0 | 0 | |||||
| 12 | 14+ | - | 7 | 0 | 7- | ||||
| 2 | 23 | 13 | - | 13 | 13 | 3 | |||
| 21 | 28 | 18 | - | 8 | |||||
| 31 | 22 | 32 | - | 22 | 12 | ||||
| 23 | 29 | - | 22 | 22 | 15 | ||||
| 22 | 21+ | 31 | 21 | 21 | - | 21 | 11- | ||
| 38 | 38 | 28 | 28 | - | 18 | ||||
| 3 | 14 | 17+ | 17 | - |
Позначивши стовпці знаходимоl4=(15,12,22).
Величина потоку по шляхуl4: C4= min {3,7,11}=3.
Розрахувавши нові пропускні здатності дуг, приходимо до табл. 4.5
Таблиця 4.5. Матриця пропускних здатностей дуг мережі
| 15 | 12 | 2 | 21 | 31 | 23 | 22 | 38 | 3 | |
| 15 | - | 0 | 0 | 0 | |||||
| 12 | 17 | - | 7 | 0 | 4 | ||||
| 2 | 23 | 13 | - | 13 | 13 | 3 | |||
| 21 | 28 | 18 | - | 8 | |||||
| 31 | 22 | 32 | - | 22 | 12 | ||||
| 23 | 29 | - | 22 | 22 | 15 | ||||
| 22 | 24 | 31 | 21 | 21 | - | 21 | 8 | ||
| 38 | 38 | 28 | 28 | - | 18 | ||||
| 3 | 14 | 20 | 17 | - |
Переглядаючи рядки і позначаючи стовпці переконуємося в тім, що рядок 15 позначити неможливо. Отже, більше не існує жодного шляху з позитивною пропускною здатністю з вершини 15 у вершину 3.
