183501 (596674), страница 2
Текст из файла (страница 2)
Рис 1.2 Фрагмент мережі
Для аналізованого планового періоду відомо кількість вантажу, що потрібно відправити або доставити в ті або інші вузли мережі G (К, А). Перевезення і перевалювання вантажів здійснюється по дугах А мережі, пропускні спроможності яких обмежені. Вони вимірюються кількістю вантажу або транспортних засобів, що може бути переміщене по ним у період планування. На дугах, що відповідають перевезенням, ці обмеження виникають внаслідок обмежених можливостей ділянок перевезень, а на дугах перевалювання - внаслідок обмеженої переробної спроможності вантажно-розвантажувальних устроїв. Для кожної дуги мережі задані розміри, що виражають питомі грошові витрати і прибутки від перевезення (або перевалювання) одиниці вантажу відповідного роду визначеним видом транспорту. Якщо даний вантаж не може перевозитися по якийсь дузі, то вартість його перевезення покладається рівної достатньо великому позитивному числу, а прибуток від перевезення - достатньо великому негативному числу.
Рахується також, що задані пропускні спроможності вузлів транспортної мережі, що є слідством обмеженої ємності складів і власної обмеженої можливості транспортного вузла по переробці транспортних засобів і вантажів.
Розмірність загальнотранспортної мережі є надзвичайно велика. Наприклад, тільки на залізничній мережі число станцій нараховує декілька тисяч. При полігоні в 1000 пунктів, кожні два з який пов'язані тільки одною дугою (у дійсності їх може бути і більше), число маршрутів складає біля мільйона. У масштабах країни число вершин і дуг графа, що подає транспортну мережу, значно вище.
Внаслідок надзвичайно великої розмірності мережі G (K, А) важливими проблемами, що виникають при оптимальному планування перевезень, є агрегировання (об'єднання вузлів мережі і дуг) із метою скорочення їхні числа і декомпозиція (розбивка мережі G (K, A) на підмережі) із метою скорочення розмірності рішення кожної окремої задачі.
Найкращої є мережа, у якій виділені всі постачальники і споживачі вантажів. Теоретично це підвищує точність планових розрахунків. Проте число постачальників і споживачів може досягати десятків, а й навіть сотень тисяч, що робить розрахунок перевезень по такій мережі неможливим без агрегування.
Найбільше прийнятним варто вважати агрегування постачальників і споживачів по адміністративно-територіальній ознаці. Це може означати, що в якості пункту споживання (або виробництва) приймається або адміністративний центр регіону (області), або деякий умовний пункт. При цьому за основу можна прийняти існуючий розподіл транспортної мережі на мережі економічних районів, областей. Основу єдиної транспортної мережі складає магістральна мережа, по якій відбувається обмін продукцією між економічними районами (регіонами). Вона є мережею достатньо високого ступеня агрегування, а більш низьким ступенем укрупнення є магістральна мережа значного економічного району, у якому обмін вантажами здійснюється між низовими територіально-виробничими комплексами. Мережею третього порядку розукрупнення може бути місцева транспортна мережа, що подає собою сукупність шляхів повідомлення економічних підрайонів між господарськими пунктами.
Чим більше період планування, тим більше укрупненої повинна бути транспортна мережа. Відповідно до цого поточне планування переважно має справа з магістральними міжрайонними і внутрішніми мережами, а оперативне планування - із внутрішніми і місцевої транспортними мережами.
На основних видах транспорту, крім трубопровідного, транспортний процес має дискретний характер, тобто визначена кількість вантажів (пасажирів) і рухливого складу відправляються в окремі моменти часу.
У тих випадках, коли розмір періоду планування значно перевищує тривалості - транспортних операцій, можна не враховувати позицію кожного що переміщається об'єкта в окремі моменти часу і перейти до розгляду деякого стаціонарного безупинного транспортного потоку.
При оперативному плануванні і регулюванні тривалість транспортних операцій стає порівнянної з періодом планування і регулювання, і необхідно розглядати динамічні потоки вантажів, пасажирів і транспортних засобів.
Всі транспортні потоки, що існують на транспортній мережі, діляться на декілька основних груп: потоки вантажів, потоки контейнерів, у яких знаходяться вантажі, потоки транспортних засобів, пасажиропотоки і т.д.
На залізничному транспорті існують такі потоки:
-
вантажів;
-
пасажирів;
-
вагонів, що обслуговують перевезення вантажу на всьому протязі залізничної частини перевезення до перевалювання на інший вид транспорту (за винятком залізничного порома) або пункту розаантаження;
-
локомотивів, що можуть змінюватися й у середині залізничного етапу перевезення в зв'язку з переформуванням вантажних поїздів, переходом поїзда на ділянку з іншим видом тяги, на пар і т.д.;
-
контейнерів, шлях проходження яких при прямих і змішаних перевезеннях (без розвантаження з контейнерів або навантаження в них у проміжних пунктах) збігається з потоком вантажів. Проте на відміну від вантажу контейнери повинні бути відправлені обернуті з іншим вантажем або порожняком. Це ставиться і до інших видів тари, що підлягає поверненню, а також до контейнерів.
На водяному транспорті існують потоки вантажів, контейнерів, пасажирів, самохідних барж, несамохідних барж і буксирів.
На автомобільному і повітряному транспорті існують потоки автомобілів і літальних апаратів, контейнерів і вантажів.
На трубопровідному транспорті існує поки тільки потік вантажів, але з упровадженням пневматичних і інших трубопроводів поряд із потоком вантажів буде існувати і потік тари.
Кожний із цих потоків може бути, у свою чергу, розділений на підгрупи відповідно до роду вантажу, типом транспортних засобів і т.п.
Слід зазначити, що потоки, що існують на транспортній мережі, не є незалежними, а тісно пов'язані між собою. Очевидно, наприклад, що для існування вантажопотоку або пасажиропотоку в якій ланки транспортної мережі необхідно, щоб по ньому протікав також потік транспортних засобів.
РОЗДІЛ 2. Транспортні потоки, планування та оптимізація
2.1 Задачі планування незалежних транспортних потоків
Однієї з поширених практичних задач, що зводяться до оптимізації незалежних транспортних потоків, є пошук максимального транспортного потоку з пункту його зародження в пункт поглинання, наприклад визначення максимального потоку вантажів, що може бути перевезений із пункту відправлення в пункт призначення по транспортній мережі з обмеженою пропускною спроможністю.
Ця задача формулюється в такий спосіб.
Задано транспортну мережу G (V, Е), у якій п = |V| - число вершин, а т =| Е| - число дуг. Кожній дузі (i,j) 
Е поставлено у відповідність невід’ємне число 
, називане її пропускною спроможністю і відповідною максимальною кількістю одиниць транспортного потоку, що може пройти по дузі.
Вершина s та V, із якої починається переміщення однорідного потоку, називається джерелом, а вершина t V, у якій воно закінчується, - стоком.
Шляхом із s и t в G (V, Е) називається послідовність вершин і дуг, така, що
s ≡ i1;(i1, i2); i2; (i2i3),…,(in-1,in);in≡t...
Однорідним транспортним потоком у мережі G (V, Е) називається множина чисел xij, таких, що
j ≠ s,t
Кількість потоку, що виходять із джерела або входять у стік,
Під задачею про максимальний потік розуміється задача пошуку в G (V, Е) потоку максимального розміру v, що протікає з s у t.
Існує багато різноманітних алгоритмів пошуку максимального потоку. Найбільше поширені з них перераховані в табл. 1 із указівкою джерела й оцінки числа операцій. Уявлення про тривалість обчислень можна одержати з табл..2 [10]
Таблиця.1-Алгоритми пошуку максимального потоку
| Автор алгоритму | Помилка в загальному випадку | m=n | m=n2 | k=m+n | |
| Форд-Фалкенсон Эдмонс-Карп Диниц Карзанов Черкаський Галил | [4] [5] [6] [7] [8] [9] | 0(vm) 0( 0( 0( 0( 0( | 0( 0( 0( 0( 0( | 0( 0( 0( 0( 0( | 0( 0( 0( 0( 0( |
)
)
)
)
)
)
)
)
)
)
)
)
)Таблиця.2-Тривалість обчислень
| Число вершин | Число дуг | Алгоритм Форда-Фалкенсона, модифікація Эдмонса-Карпа, c | Алгоритм Диница, c | Алгоритм Карзанова, c | Алгоритм Черкаського, c | |
| 100 200 300 400 500 600 700 800 900 1000 | 500 1000 1500 2000 2500 3000 3500 4000 4500 5000 | 17,0 68,3 154,7 285,1 - - - - - - | 4,2 9,6 14,3 20,0 24,9 41,0 41,7 46,7 57,3 54,5 | 5,3 11,8 17,7 24,8 30,0 48,0 50,9 59,6 69,7 66,9 | 2,7 7,4 9,4 14,7 22,7 14,1 24,5 34,5 38,4 43,5 | |
Більш загальною задачею оптимізації однорідного транспортного потоку є задача пошуку такого потоку на транспортній мережі, витрати на переміщення якого є мінімальними. До задачі подібного роду зводяться, наприклад, задача визначення обсягів і шляхів доставки вантажів із пунктів відправлення в пункти призначення, що забезпечують мінімум транспортних витрат, а також задача визначення маршрутів прямування і кількості, використовуваних транспортних засобів, при яких загальні експлуатаційні витрати на одну перевізку вантажів мінімальні.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
