Моделювання транспортної мережі
Проміжні
вузли шляху
від вузла
до вузла
визначаємо
по матриці
.
Нехай
,
тоді маємо
шлях
.
Якщо далі
і
,
тоді вважаємо,
що весь шлях
визначений,
тому що знайдені
всі проміжні
вузли. У противному
випадку повторюємо
описану процедуру
для шляхів від
вузла
до вузла
і від вузла
до вузла
.
При аналізі транспортних мереж часто виникає задача визначення максимального потоку, що може пропустити дана мережа, а також задача розподілу цього потоку по дугах мережі.
З математичної
точки зору
задача про
максимальний
потік формулюється
в такий спосіб:
при заданій
конфігурації
мережі і відомої
пропускної
здатності
знайти ненегативні
значення
,
що задовольняють
умовам і, що
максимізують
функцію
,
тобто

Алгоритм
для знаходження
максимального
потоку був
запропонований
Фордом і Фалкерсоном
і полягає в
поступовому
збільшенні
потоку, що
пропускається
по мережі, доти,
поки він не
стане найбільшим.
Алгоритм заснований
на теоремі
Форда-фалкерсона:
у будь-якій
транспортній
мережі максимальний
потік із джерела
в стік
,
дорівнює мінімальній
пропускній
здатності
розрізу, що
відокремлює
від
.
Крок 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. Після обчислення міток одержимо наступний їх список:
| Вузол | Мітка | Статус мітки |
| 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.
Заключний крок. Віднімаючи з елементів табл. 4.1 відповідні елементи табл. 4.6, одержимо табл. 4.6.
Таблиця 4.6. Матриця пропускних здатностей дуг мережі
|
15 |
12 |
2 |
21 |
31 |
23 |
22 |
38 |
3 |
|
|
15 |
- | 10 | 10 | 10 | |||||
|
12 |
-10 | - | 7 | 3 | |||||
|
2 |
-10 | - | 10 | ||||||
|
21 |
-10 | - | 10 | ||||||
|
31 |
-10 | - | 10 | ||||||
|
23 |
-7 | - | 7 | ||||||
|
22 |
-3 | -10 | - | 13 | |||||
|
38 |
-10 | - | 10 | ||||||
|
3 |
-7 | -13 | -10 | - |
Позитивні
елементи цієї
таблиці характеризують
величини дугових
потоків. Величина
максимального
потоку дорівнює
сумі елементів
15-го рядка табл.
4.1 або сумі елементів
3-го стовпця.
Усі дуги розрізу
є насиченими.
Транспортну мережу загалом можна розглядати як систему, що складається з неоднорідних пристроїв або елементів різної складності, що взаємодіють з транспортними потоками потягів, автомобілів, літаків і т.д.
Встановлений окремо для кожної лінії оптимальний план розвитку не завжди доцільний, з огляду на її взаємодію з усією мережею, а іноді навіть практично не може бути реалізований. Зміна технічного оснащення однієї лінії вимагає економічно раціонального перерозподілу потоків на мережі. Отже, одночасно з розвитком пропускної здатності необхідно визначити оптимальний потік, що направляється на лінію, у кожний рік її експлуатації.
Деякі способи посилення пропускної здатності в той або інший конкретний плановий період виявляються найбільш ефективними на значному числі ліній. Найчастіше це ті способи, що безпосередньо зв'язані з реалізацією основних напрямків технічного прогресу на транспорті. Здійснення їх жадає від народного господарства значної витрати тих або інших ресурсів, від чого різко зростає дефіцит останніх. Таким чином, плануючи терміни посилення ліній, необхідно враховувати обмеженість матеріальних і грошових ресурсів, виділюваних на переоснащення залізничного транспорту. Це ставить на чергу задачу оптимізації розвитку пропускної здатності сукупності декількох ліній або навіть мережі в цілому. Вирішити неї в першому наближенні можна оптимізацією розвитку окремих локалізованих систем – груп ліній з однотипними найбільш ймовірними способами посилення пропускної здатності, а також ліній, зв'язаних загальним вантажопотоком, що розподіляється по них у залежності від рівня технічного оснащення.
Як видно, деякі ділянки мережі завантажені цілком, а деякі не задіяні в перевізному процесі взагалі. Виходом зі сформованої ситуації, для даної транспортної системи, є підвищення пропускних здатностей таких ліній: 10–7 і 10–15. Ще одним способом зменшення навантаження на дані ділянки може стати розподіл загального обсягу перевезень між залізничним і автомобільним транспортом у місцевому повідомленні (якщо сумарні приведені витрати на транспортування автомобільним транспортом не перевищують витрати на транспортування залізничним транспортом). Дані заходи до деякої міри «розвантажать» напружені ділянки і ділянки, що лімітують, транспортної мережі.
Література
Моделирование транспортных систем. Персианов В.А., Скалов К.Ю., Усков Н.С., М-изд-во «Транспорт» 1992 г., – 209 с.
Нелинейные сетевые транспортные задачи. Левит Б.Ю., Лившиц В.Н. Институт комплексных транспортных проблем. Изд-во «Транспорт», 2002 – 257 с.
Левин Д.Ю. Оптимизация потоков поездов. – М.: Транспорт, 1988. – 175 с.
Хорафас Д.Н. Системы и моделирование. Перевод с англ. Изд-во «Мир», М., 1967.
Хейт Ф. Математическая теория транспортных потоков. Перевод с англ. Изд-во «Мир», М., 1966.
Нестеров Е.П. Транспортные задачи линейного программирования. М.: Изд-во «Транспорт», – 1971.