Дипломная работа: Математична модель транспортної системи підприємства

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

Розмірність загальнотранспортної мережі є надзвичайно велика. Наприклад, тільки на залізничній мережі число станцій нараховує декілька тисяч. При полігоні в 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

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

Відмінність даної задач від попередньої полягає в тому, що для кожної дуги (i,j)  Е задана вартість  переміщення одиниці транспортного потоку і необхідно знайти потік заданого розміру v із джерела s у стік t, що мінімізує зважену суму потоків

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

Очевидно, можна замість 0() використовувати оцінку 0(). У [5] запропонована модифікація алгоритму дефекту з оцінкою числа операцій 0 ().

Алгоритми пошуку потоку мінімальної вартості застосовуються для рішення задач у дуже великих мережах. У роботах [11, 12] повідомляється про рішення прямими алгоритмами задач із 20000 вершин 450 000 дуг, а в [13] - про рішення однієї задачі з 3000 вершин і 35 000 дуг за 97 с на IВМ-360/67 і іншої задачі з 5000 вершин та 15 000 дуг за 113 с.

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

Кожній дузі (i, j) мереж поставлена у відповідність її довжина , або тривалість проходження одиниці транспортного потоку, що у загальному випадку може бути позитивним негативним числом.

У ряді відомих алгоритмів робиться додаткове припущення про те, що G (V, Е) не містить циклів негативно довжини.

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

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

Таблиця 3 - Оцінки числа операцій алгоритмів

Автор алгоритму	Оцінка числа операцій	Автор алгоритму		Оцінка числа операцій
Найкоротший шлях між двома вершинами		Найкоротш шляхи між усіма парами вершин
Беллман [14] Дийкстра [15] Беллман-Форд [16]	0(n2) 0(m log n) 0(m n)	Дийкстра [17] Спира [18] Флойд-Варшал [19,20] Фридман [21]	0(mn log n) 0(n2(log n)2) 0(n2) 0(n)2,5

Метод Белмана. Скористаємося рівнянням Белмана для визначення найкоротшого шляху між вершинами 1 і n. Визначимо  - довжину найкоротшого шляху з вихідної вершини 1 у вершину j за умови, що вершини пронумеровані числами 1, 2, 3,..., п. Шлях найкоротшої довжини знаходиться з такого рівняння:

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9