МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

СХІДНОУКРАЇНСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ

КУРСОВИЙ ПРОЕКТ

Тема:

«Моделювання транспортної мережі»

Вступ

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

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

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

1. Загальні питання побудови моделі транспортної мережі

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

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

Моделювання засноване на розгляді транспортного вузла, як сукупності елементів, що функціонують не по окремості, а у взаємному зв'язку.

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

Складання системи доріг полягає в розташуванні вершин (міст), відповідно до реального положення їх на карті. Після цього вершини з'єднуємо таким чином, щоб вийшла максимальна кількість непересічних ребер. У реальності це дороги, що з'єднують відповідні міста. Кожна дорога має деяку довжину - позитивне речовинне число. Довжина шляху в системі доріг - це сума довжин доріг цього шляху. Поняття шляху, досяжності і замкнутого шляху визначаються для системи доріг аналогічно подібним до понять для графа й орієнтованого графа.

Після одержання мультиграфа, визначаємо за допомогою карти довжину кожної дороги - ребра. На основі отриманих результатів складаємо модель транспортної мережі. Модель транспортної мережі представлена на рис. 1.1.



Рис. 1.1. Модель транспортної мережі

2. Характеристика транспортної мережі, що аналізується

Модель транспортної мережі представлена дев'ятьма містами. Для даного варіанта це: Сарни, Лозова, Житомир, Нікополь, Должанська, Ромодан, Одеса, Шепетівка, Дебальцеве. Залізничні станції, розташовані в цих містах, відносяться до відповідних залізниць. Як відомо, залізнична транспортна мережа України розділена на 6 залізниць: Донецька, Придніпровська, Південна, Південно-Західна, Одеська і Львівська.

До Донецької залізниці відноситься Дебальцеве.

Донецька залізниця охоплює найбільше індустріально розвитий район - Донбас (значна частина території Донецької і Луганської областей). Експлуатаційна довжина дороги 2,9 тис. км.

До Придніпровської залізниці відноситься Нікополь.

Придніпровська залізниця обслуговує частину Нижньої Наддніпрянщини і Кримський півострів - Дніпропетровську, Запорізьку області і Крим. Експлуатаційна довжина дороги 3,2 тис. км. Густота залізничної мережі в Наддніпрянщині у 2-2,5 рази менше, ніж у Донбасі, що зв'язано переважно з меншою насиченістю території заводами, фабриками, шахтами, а також з наявністю в межах дороги річкового транспорту
(р. Дніпро). Основна маса вантажів у Наддніпрянщині перевозиться в трикутнику Дніпропетровськ - Кривої Ріг - Запорожжя. У цих містах розміщені великі підприємства чорної металургії, що споживають багато кам'яного вугілля, залізної руди, допоміжних матеріалів, великі теплові електростанції, коксохімічні і машинобудівні заводи. Тут же знаходяться і великі Криворізький залізорудний і Нікопольський марганцеворудний басейни.

До Південної залізниці відноситься Лозова, Ромодан та Должанська. Південна залізниця обслуговує територію Харківської і Полтавської областей, а також частину території Чернігівської, Сумської, Луганської областей. Експлуатаційна довжина дороги 3,6 тис. км.

Південна дорога забезпечує вихід з Донбасу і Наддніпрянщини на північ і північний захід - убік Москви, Брянська, Гомеля і Києва, а також на північний схід і схід - убік Воронежа і Пензи. Відповідно до цього Південна дорога має три основних вантажонапружених напрямки: центральне, що йде від станції Букіно (з боку Червоного Лиману) через Харківський залізничний вузол на Готню, Льгів і далі на Брянськ і Москву; східне, що йде від станції Слов'яногірськ (також з боку Червоного Лиману) через Куп'янський залізничний вузол на Валуйки, а відтіля через Старий Оскол, Касторну і Єлець на Москву і через Георгиу-Деж на Воронеж і Пензу; західне, що йде від Лозової через Полтавський залізничний вузол на Ромодан, Гребінку і Київ. По всіх цих напрямках з Донбасу йде транзитний потік чорних металів, хімічних вантажів, будівельних матеріалів, машин і промислового устаткування. У минулому істотні далекі перевезення кам'яного вугілля, нині вони обмежуються тільки територією України.

Обслуговуючи в основному центри обробної промисловості, Південна дорога довгі роки мала пасивний вантажообіг: вона відправляла в 1,5 рази менше вантажів, чим одержувала. Швидкий ріст видобутку залізної руди на рудниках і кар'єрах Курської магнітної аномалії призвів до активізації її вантажообіга. Серед вантажів, що відправляються Південною дорогою перше місце займає залізна руда. Далі йдуть будівельні матеріали (будівельне каміння і вапно), нафтопродукти, цукровий буряк.

У структурі ввезених вантажів представлені будівельні матеріали, кам'яне вугілля, нафтопродукти, чорні метали, цукровий буряк і хлібні вантажі. Найбільш значне навантаження вантажів у межах дороги мають станції, що обслуговують Курську магнітну аномалію і відправляють залізну руду (Лебеді, і ін.), а також Харків (машини, металовироби, брухт чорних металів), Кременчук і Ахтирка. Найбільші станції прибуття вантажів - станції Харківського залізничного вузла (кам'яне вугілля, чорні метали, мінерально-будівельні матеріали), Полтава, Суми, Бєлгород і Кременчук.

Головне місце у вантажній транспортній роботі дороги займає Харківський вузол, у якому сходяться 8 магістральних залізничних напрямків, 4 з яких (на Бєлгород, Куп'янськ, Червоний Лиман і Лозову) електрифіковані. У структурі вантажообігу Харківського вузла головне місце займає транзит. У місцевій роботі переважає прибуття вантажів над відправленням. Найбільша вантажна станція вузла - Індустріальна. Вона обслуговує машинобудівні заводи Харкова.

До Південно-Західної залізниці відносяться Житомир та Шепетівка.

Південно-Західна залізниця обслуговує північні області України - Хмельницьку, Вінницьку, Житомирську, Київську, Чернігівську і частково Сумську. Експлуатаційна довжина дороги 4,7 тис. км. Основний кістяк магістральної мережі Південно-Західної дороги був побудований у дореволюційний час. У радянський період відбувалося випрямлення і посилення окремих напрямків, будувалися під'їзні колії до промислових центрів, що розвиваються, новим цукровим заводам, родовищам будівельних матеріалів. Було поліпшено транспортно-географічне положення Чернігова (будівництво залізничних виходів до Гомеля і на захід до Ковелю і Бреста) і Житомира (створення прямого виходу на Наддніпрянщину).

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

Головна лінія Південно-Західної дороги - напрямок Хутір Михайлівський - Конотоп - Бахмач - Ніжин - Київ - Казатин - Вінниця - Жмеринка - Хмельницький - Тернопіль, що представляє собою частину Транс'європейської залізничної магістралі Москва - Київ - Львів - Прага. До Жмеринки вона електрифікована. Починаючи зі станції Дарниця (Київ), ця магістраль має значний вантажопотік, що складається з кам'яного вугілля, чорних металів, хімічних продуктів і машин Донбасу і Харкова, до яких зі станції Фастів додається потік залізної руди і чорних металів Наддніпрянщини. Частина цих транзитних вантажів з головної магістралі відволікається на рівнобіжний напрямок Казатин - Шепетовка - Здолбунов - Рівне - Львів. Для вивозу експортних вантажів на Брест важливе значення має лінія Шепетовка - Здолбунов - Рівне - Луцьк - Ковель.

У загальному обсязі робіт дороги 3/5 складає транзит. Головні транзитні вантажі - залізна руда, нафтопродукти, кам'яне вугілля, чорні метали, хліб і ліс.

Південно-Західна дорога, що обслуговує територію з розвитою обробною промисловістю й інтенсивним сільським господарством, має пасивний вантажообіг: відправлення вантажів з її станцій менше прибуття. Серед вантажів, що відправляються, на першому місці знаходяться мінеральні будівельні матеріали (майже 45% усього відправлення), головним чином будівельний камінь і виробні матеріали (граніт, мармур, лабрадорит), що добуваються в ряді районів Українського кристалічного масиву (Житомирська, Київська і Вінницька області). Істотна, у відправленні вантажів, частка продукції харчової промисловості (цукор, борошно, комбікорм) і сільського господарства (цукровий буряк), а в прибутті - кам'яного вугілля, лісових вантажів, нафтопродуктів і чорних металів.

Станцій з великим відправленням вантажів на Південно-Західній дорозі небагато. Виділяється лише Київський залізничний вузол, що відправляє велику кількість будівельного піску. Тут же відбувається перевалка на залізницю кам'яного вугілля, перевезеного з Донбасу по Дніпру. Найбільші станції прибуття вантажів (кам'яне вугілля, мінерально-будівельні матеріали, чорні метали, сільськогосподарські продукти) - станції Київського залізничного вузла, Вінниця, Чернігів, Житомир і Біла Церква.

У межах дороги залізничний транспорт широко взаємодіє з річковим. Найважливіші перевалочні пункти змішаних залізнично-водних перевезень - Київ і Чернігів. У Києві з Дніпровського річкового шляху на залізницю перевантажують кам'яне вугілля, будівельний пісок, сільськогосподарські продукти, у Чернігові перевалюють з р. Десни мінеральні будівельні матеріали.

До Львівської залізниці відносяться Сарни. Львівська залізниця обслуговує територію Львівської, Івано-Франківської, Тернопільської, Чернівецької, Закарпатської, Волинської і Ровенської областей. Її експлуатаційна довжина 4,5 тис. км.

Густа залізнична мережа в західних областях України склалася до возз'єднання їх з Радянською Україною. Але це були в основному технічно слабкооснащені і малозавантажені лінії. У радянський період докорінно реконструювали основну залізничну магістраль Західної України: Рівне - Львів - Стрий - Чоп, що обслуговує основний потік зовнішньоторговельних вантажів між Україною, Чехією, Угорщиною й Австрією. Ця магістраль електрифікована. Були споруджені також залізничні виходи зі Львівсько-Волинського басейну на північ (Ковель і Луцьк) і південь (убік Львова), що забезпечили вивіз львівсько-волинського кам'яного вугілля (місцеве паливо) у сусідні області України і Білорусії. Електрифікація залізничної ділянки Львів - Мостиска II дозволила створити ще одну Транс'європейську магістраль: Москва - Київ - Львів - Краків - Варшава.

Для місцевих перевезень використовуються лінії Львів - Самбор - Ужгород, Львів - Івано-Франківськ - Коломия (по цій лінії йде потік львівсько-волинських вугіль на Бурштинську ГРЕС) і Дрогобич - Стрий - Тернопіль.

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

В внутрідорожньому вантажообігу головну роль грають кам'яне вугілля, в основному зі Львівсько-Волинського басейну і частково з Донбасу, мінеральні будівельні матеріали, нафтопродукти, чорні метали, машини, зерно, борошно і цукровий буряк. У відправленні вантажів різко домінують кам'яне вугілля Львівсько-Волинського басейну, нафтопродукти і мінеральні будівельні матеріали. Відправляються також лісові вантажі з карпатських і поліських областей, цукровий буряк і машини головним чином зі Львова.

Найбільшими станціями прибуття вантажів є станції Чоп і Мостиска, що виконують операції з експортними вантажами, а також станції Дрогобич, Надвірна, Добротвор, Львів і Рівне. Велика кількість вантажів відправляють станції Іванче, Селець і Гірник (кам'яне вугілля), Здолбунов, Миколаїв і Клесов (мінерально-будівельні матеріали).

До Одеської залізниці відносяться станції Херсон і Кіровоград. Одеська залізниця обслуговує територію Одеської, Миколаївської, Херсонської, Кіровоградської і Черкаської областей. Її експлуатаційна довжина 4,2 тис. км.

В даний час найбільш завантажені лінії Одеської залізниці, що йдуть до морських портів (від Вінниці і Черкас до Одеси й Іллічевська, від Знаменки, Дніпропетровська і Донецька до Миколаєва і Херсона). Широтні лінії невеликого протягу, що обслуговують переважно сільськогосподарські райони (імені Тараса Шевченко - Цветково - Христиновка - Зятьковци - Вапнярка - Ямпіль, Чорноліська - Помошна - Борщі, Миколаїв - Колосовка - Роздільна - Кучурган), менш завантажені. У цілому вантажонапруженість дороги значно нижче загальномережевої.

Головними вантажами, що перевозяться в напрямку до Одеси, Іллічевську і Південному, є нафтопродукти, кам'яне вугілля, чорні метали і мінеральні будівельні матеріали. Частина з них переробляється і споживається в Одесі - самому великому промисловому центрі українського Причорномор'я, а велика частина перевантажується на морський транспорт і йде на експорт. У зворотному напрямку з Іллічевська й Одеси перевозять цукор-сирець, машини і металовироби, тропічні фрукти.

У напрямку Миколаївських і Херсонського морських портів з Наддніпрянщини і Донбасу випливають кам'яне вугілля, нафтопродукти, чорні метали, залізна руда і цемент, а в зворотному напрямку - нафтопродукти і хлібні вантажі, а також глинозем.

Експортні перевезення вантажів дуже впливають на структуру вантажообігу Одеської дороги: вона має триразове перевищення прибуття над відправленням. Серед вантажів прибуття переважають нафтові (сира нафта, що йде на переробку на Одеський і Херсонський заводи, топковий мазут, дизельне паливо для судів морського флоту), кам'яне вугілля і будівельні матеріали. Відправляє Одеська дорога нафтопродукти, мінеральні будівельні матеріали і кам'яне вугілля.

Найбільші станції прибуття: Одеса, Рени, Миколаїв, Іллічевськ і Херсон, відправлення - Пантаєвка (буре вугілля Дніпропетровського басейну в Кіровоградській області), Одеса і Херсон.

Одеська дорога широко взаємодіє з іншими видами транспорту - морським (у портах Одеса, Іллічевськ, Південний, Миколаїв і Херсон), річковим (у портах Ізмаїл на Дунаєві, Херсон і Черкаси на Дніпру) і автомобільним. Між портом Іллічевськ і болгарський порт Варна регулярно курсують морські залізничні пароми.

У районі тяжіння дороги протікає Дніпро. По ньому перевозять: униз - зернові вантажі, мінерально-будівельні матеріали, нагору - нафтові вантажі.

Станція Гомель відноситься до Білоруської залізниці.

3 Теоретичні положення з організації моделювання транспортних мереж

Задачу пошуку найкоротшого шляху між джерелом і стоком (початковий і кінцевий пункти мережі) можна вирішити за допомогою алгоритму Дейкстри. Алгоритм Дейкстри розроблений для знаходження найкоротшого шляху між заданим вихідним вузлом і будь-яким іншим вузлом мережі.

У процесі виконання цього алгоритму при переході від вузла до наступного вузла використовується спеціальна процедура позначки ребер. Позначимо через найкоротшу відстань від вихідного вузла 1 до вузла , через - довжину ребра . Тоді для вузла визначимо мітку в такий спосіб:

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

Розрахункова схема алгоритму складається з наступних кроків.

Крок 0. Вихідному вузлу (вузол 1) привласнюється мітка . Думаємо .

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

б) Якщо усі вузли мають постійні мітки, процес обчислень закінчується. У противному випадку вибирається мітка з найменшим значенням відстані серед усіх тимчасових міток (якщо таких міток декілька, то вибір довільний). Думаємо і повторюємо крок .

Задача визначення найкоротших відстаней між елементами транспортної мережі (Алгоритм Флойда).

Дана задача вирішується за допомогою алгоритму Флойда.

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

Покажемо спочатку основну ідею методу Флойда. Нехай є три вузли і задані відстані між ними (рис. 3.1). Якщо виконується нерівність , то доцільно замінити шлях шляхом . Така заміна (далі її будемо умовно називати трикутним оператором) виконується систематично в процесі виконання алгоритму Флойда.

Рис. 3.1. Трикутний оператор

Алгоритм Флойда вимагає виконання наступних дій.

Крок 0. Визначаємо початкову матрицю відстаней і матрицю послідовності вузлів . Діагональні елементи обох матриць позначаються знаком «-», що показує, що ці елементи в обчисленнях не беруть участь. Думаємо :

Рис. 3.2. Початкова ситуація

Основний крок k. Задаємо рядок і стовпець як ведучий рядок і ведучий стовпець. Розглядаємо можливість застосування трикутного оператора до всіх елементів матриці . Якщо виконується нерівність , тоді виконуємо наступні дії:

· створюємо матрицю шляхом заміни в матриці елемента на суму ,

· створюємо матрицю шляхом заміни в матриці елемента на . Думаємо і повторюємо крок .

Пояснимо дії, виконувані на -м кроці алгоритму, представивши матрицю так, як вона показана на рис 3.3. На цьому рисунку рядок і стовпець є ведучими. Рядок - будь-який рядок з номером від 1 до , а рядок - довільний рядок з номером від до . Аналогічно стовпець представляє будь-як стовпець з номером від 1 до , стовпець - довільний стовпець з номером від до . Трикутний оператор виконується в такий спосіб. Якщо сума елементів ведучих рядка і стовпця (показаних у квадратах) менше елементів, що знаходяться в перетинанні стовпця і рядка (показаних у кружках), що відповідають розглянутим ведучим елементам, то відстань (елемент у кружку) заміняється на суму відстаней, представлених ведучими елементами:

Рис. 3.3. Ілюстрація алгоритму Флойда

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

1. Відстань між вузлами і дорівнює елементові в матриці .

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

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

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

Алгоритм для знаходження максимального потоку був запропонований Фордом і Фалкерсоном і полягає в поступовому збільшенні потоку, що пропускається по мережі, доти, поки він не стане найбільшим. Алгоритм заснований на теоремі Форда-фалкерсона: у будь-якій транспортній мережі максимальний потік із джерела в стік , дорівнює мінімальній пропускній здатності розрізу, що відокремлює від .

Крок 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. Ще одним способом зменшення навантаження на дані ділянки може стати розподіл загального обсягу перевезень між залізничним і автомобільним транспортом у місцевому повідомленні (якщо сумарні приведені витрати на транспортування автомобільним транспортом не перевищують витрати на транспортування залізничним транспортом). Дані заходи до деякої міри «розвантажать» напружені ділянки і ділянки, що лімітують, транспортної мережі.

Література

1. Моделирование транспортных систем. Персианов В.А., Скалов К.Ю., Усков Н.С., М-изд-во «Транспорт» 1992 г., - 209 с.

2. Нелинейные сетевые транспортные задачи. Левит Б.Ю., Лившиц В.Н. Институт комплексных транспортных проблем. Изд-во «Транспорт», 2002 - 257 с.

3. Левин Д.Ю. Оптимизация потоков поездов. - М.: Транспорт, 1988. - 175 с.

4. Хорафас Д.Н. Системы и моделирование. Перевод с англ. Изд-во «Мир», М., 1967.

5. Хейт Ф. Математическая теория транспортных потоков. Перевод с англ. Изд-во «Мир», М., 1966.

6. Нестеров Е.П. Транспортные задачи линейного программирования. М.: Изд-во «Транспорт», - 1971.