Кожний із цих потоків може бути, у свою чергу, розділений на підгрупи відповідно до роду вантажу, типом транспортних засобів і т.п.

Слід зазначити, що потоки, що існують на транспортній мережі, не є незалежними, а тісно пов'язані між собою. Очевидно, наприклад, що для існування вантажопотоку або пасажиропотоку в якій ланки транспортної мережі необхідно, щоб по ньому протікав також потік транспортних засобів.

РОЗДІЛ 2. Транспортні потоки, планування та оптимізація

2.1 Задачі планування незалежних транспортних потоків

Однієї з поширених практичних задач, що зводяться до оптимізації незалежних транспортних потоків, є пошук максимального транспортного потоку з пункту його зародження в пункт поглинання, наприклад визначення максимального потоку вантажів, що може бути перевезений із пункту відправлення в пункт призначення по транспортній мережі з обмеженою пропускною спроможністю.

Ця задача формулюється в такий спосіб.

Задано транспортну мережу G (V, Е), у якій п = |V| - число вершин, а т =| Е| - число дуг. Кожній дузі (i,j) Е поставлено у відповідність невід’ємне число , називане її пропускною спроможністю і відповідною максимальною кількістю одиниць транспортного потоку, що може пройти по дузі.

Вершина s та V, із якої починається переміщення однорідного потоку, називається джерелом, а вершина t V, у якій воно закінчується, - стоком.

Шляхом із s и t в G (V, Е) називається послідовність вершин і дуг, така, що

s ≡ i1;(i1, i2); i2; (i2i3),…,(i_n-1 ,i_n );i_n ≡t...

Однорідним транспортним потоком у мережі G (V, Е) називається множина чисел xij, таких, що

j ≠ s,t

Кількість потоку, що виходять із джерела або входять у стік,

Під задачею про максимальний потік розуміється задача пошуку в G (V, Е) потоку максимального розміру v, що протікає з s у t.

Існує багато різноманітних алгоритмів пошуку максимального потоку. Найбільше поширені з них перераховані в табл. 1 із указівкою джерела й оцінки числа операцій. Уявлення про тривалість обчислень можна одержати з табл..2 [10]

Таблиця.1-Алгоритми пошуку максимального потоку