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

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

Моделлю транспортної мережі єдиної транспортної системи країни може служити граф G (K, А), множина вершин K якого являють собою транспортні вузли (станції, порти і т.п.), а множина дуг А — ділянки шляхів переміщення транспортних потоків (потоків рухливого складу, вантажів, пасажирів ) із пунктів відправлення в пункти призначення. Вершини мережі відповідають пунктам виробництва і споживання продукції, складам для збереження вантажів і пунктам зосередження транспортних засобів. Дугам мережі приписані такі характеристики, як протяжність, пропускна спроможність, витрати на переміщення транспортних засобів і т.п. Якщо переміщення транспортних засобів між пунктами може відбуватися тільки в однім напрямку, дуга транспортної мережі називається орієнтованой, у противному випадку — неорієнтованой.

Для зображення вершин (або вузлів) орієнтованих і неорієнотованих дуг використовуються відповідно кружки, лінії зі стрілками і лінії без стрілк. У більшості випадків можна замінити одну неориєнтовану дугу двома орієнтованими і напроти спрямованими дугами. У зв'язку з розподілом єдиної транспортної системи України на підсистеми, що відповідають окремим видам транспорту, транспортна мережа G(К, А) розпадається на ряд окремих підмереж Gм (Км, Ам), що обслуговуються різноманітними видами транспорту М = 1,...,<img width=«21» height=«20» src=«ref-1_863006072-107.coolpic» v:shapes="_x0000_i1025">. Ці підмережі мають загальні вершини, що подають транспортні вузли, у яких відбувається перевалювання вантажів з одного виду транспорту на інший. Для зручності побудови моделей планування перевезень вантажів кожний вузол реальної транспортної мережі, у якому відбувається взаємодія декількох видів транспорту, можна уявити в графі G (K, А) у виді декількох вершин, кожна з який відповідає виду транспорту. Ці вершини сполучені між собою парою напроти орієнтованих дуг, що означають перевалювання вантажів з одного виду транспорту на інший [1]. Як приклад на рис. 1.1, а приведена схема загально транспортного вузла, у якому взаємодіють три види транспорту (залізничний, автомобільний і річковий), на рис… 1.1, б — його уявлення в мережі G (K, А), де можливе перевалювання вантажів позначений штриховими стрілками.


<img width=«534» height=«330» src=«ref-1_863006179-7475.coolpic» v:shapes="_x0000_i1026">

Рис 1.1. Мережа загальнотранспортного вузла
У загальному випадку транспортна мережа являє собою мультиграф (граф із декількома дугами між одною парою вершин), що містить цикли.

Приклад фрагмента мережі G (K, А) для трьох видів транспорту приведений на рис.1.2. Вершини, у яких зароджуються транспортні потоки, називаються «джерелами», а вершини, у яких вони поглинаються, — «стоками». Окремі об'єкти, що переміщаються, або «протікають», із пунктів зародження транспортних потоків у пункти їхній поглинання, називаються «одиницями потоку». Будемо використовувати символ <img width=«48» height=«24» src=«ref-1_863013654-143.coolpic» v:shapes="_x0000_i1027">для позначення вершини i = 1,...,n « графа G (K, А) і символ (i, j) <img width=«13» height=«13» src=«ref-1_863013797-84.coolpic» v:shapes="_x0000_i1028"> А для позначення орієнтованої дуги, що веде з <img width=«16» height=«24» src=«ref-1_863013881-98.coolpic» v:shapes="_x0000_i1029">, до <img width=«19» height=«25» src=«ref-1_863013979-104.coolpic» v:shapes="_x0000_i1030">-. Упорядкована послідовність вершин і спрямованих дуг мережі <img width=«16» height=«23» src=«ref-1_863014083-98.coolpic» v:shapes="_x0000_i1031"> (1, 2), <img width=«19» height=«23» src=«ref-1_863014181-102.coolpic» v:shapes="_x0000_i1032">, (2, 3),..., <img width=«27» height=«24» src=«ref-1_863014283-114.coolpic» v:shapes="_x0000_i1033">, ( n-1, n),<img width=«19» height=«24» src=«ref-1_863014397-102.coolpic» v:shapes="_x0000_i1034">, така, що кінець попередньої дуги є початком наступної, називається шляхом (або маршрутом), що веде з вершини <img width=«16» height=«23» src=«ref-1_863014083-98.coolpic» v:shapes="_x0000_i1035"> у вершину <img width=«19» height=«24» src=«ref-1_863014397-102.coolpic» v:shapes="_x0000_i1036">. При <img width=«49» height=«24» src=«ref-1_863014699-142.coolpic» v:shapes="_x0000_i1037">послідовність називається орієнтованим циклом або кільцевим маршрутом. Якщо будь-які дві вершини мережі можна з'єднати шляхом, те мережа називається зв`язаною. Якщо мережа не є зв`язаною, те її можна розбити на зв'язкові підмережі або компоненти зв`язані. Прикладом незв'язної транспортної мережі може служити підсікти шляхів повідомлень річкового транспорту, що складає з декількох не з`єднаних річкових басейнів.
<img width=«594» height=«223» src=«ref-1_863014841-4378.coolpic» v:shapes="_x0000_s1040 _x0000_s1058 _x0000_s1039 _x0000_s1056 _x0000_s1038 _x0000_s1035 _x0000_s1037 _x0000_s1062 _x0000_s1063 _x0000_s1071 _x0000_s1070 _x0000_s1036 _x0000_s1055 _x0000_s1048 _x0000_s1047 _x0000_s1057 _x0000_s1046 _x0000_s1054 _x0000_s1034 _x0000_s1033 _x0000_s1032 _x0000_s1045 _x0000_s1044 _x0000_s1053 _x0000_s1041 _x0000_s1052 _x0000_s1051 _x0000_s1068 _x0000_s1067 _x0000_s1061 _x0000_s1066 _x0000_s1065 _x0000_s1069 _x0000_s1072 _x0000_s1043 _x0000_s1031 _x0000_s1030 _x0000_s1029 _x0000_s1050 _x0000_s1049 _x0000_s1042 _x0000_s1060 _x0000_s1059 _x0000_s1064">



Рис 1.2 Фрагмент мережі
Для аналізованого планового періоду відомо кількість вантажу, що потрібно відправити або доставити в ті або інші вузли мережі G (К, А). Перевезення і перевалювання вантажів здійснюється по дугах А мережі, пропускні спроможності яких обмежені. Вони вимірюються кількістю вантажу або транспортних засобів, що може бути переміщене по ним у період планування. На дугах, що відповідають перевезенням, ці обмеження виникають внаслідок обмежених можливостей ділянок перевезень, а на дугах перевалювання — внаслідок обмеженої переробної спроможності вантажно-розвантажувальних устроїв. Для кожної дуги мережі задані розміри, що виражають питомі грошові витрати і прибутки від перевезення (або перевалювання) одиниці вантажу відповідного роду визначеним видом транспорту. Якщо даний вантаж не може перевозитися по якийсь дузі, то вартість його перевезення покладається рівної достатньо великому позитивному числу, а прибуток від перевезення — достатньо великому негативному числу.

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

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

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

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

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

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

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

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

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

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

На залізничному транспорті існують такі потоки:

-          вантажів;

-          пасажирів;

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

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

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

На водяному транспорті існують потоки вантажів, контейнерів, пасажирів, самохідних барж, несамохідних барж і буксирів.

На автомобільному і повітряному транспорті існують потоки автомобілів і літальних апаратів, контейнерів і вантажів.

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

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

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

    продолжение
--PAGE_BREAK--РОЗДІЛ 2. Транспортні потоки, планування та оптимізація 2.1 Задачі планування незалежних транспортних потоків


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

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

Задано транспортну мережу G (V, Е), у якій п = |V| — число вершин, а т =| Е| — число дуг. Кожній дузі (i,j) <img width=«18» height=«18» src=«ref-1_863019219-144.coolpic» v:shapes="_x0000_i1038"> Е поставлено у відповідність невід’ємнечисло <img width=«19» height=«25» src=«ref-1_863019363-106.coolpic» v:shapes="_x0000_i1039">, називане її пропускною спроможністю і відповідною максимальною кількістю одиниць транспортного потоку, що може пройти по дузі.

Вершина s та V, із якої починається переміщення однорідного потоку, називається джерелом, а вершина t <img width=«13» height=«13» src=«ref-1_863013797-84.coolpic» v:shapes="_x0000_i1040">V, у якій воно закінчується, — стоком.

Шляхом із s и t в G (V, Е) називається послідовність вершин і дуг, така, що
s ≡ i1;(i1, i2); i2; (i2i3),…,(in-1,in);in≡t...
Однорідним транспортним потоком у мережі G (V, Е) називається множина чисел xij, таких, що
<img width=«131» height=«37» src=«ref-1_863019553-476.coolpic» v:shapes="_x0000_i1041"> j ≠ s,t

<img width=«140» height=«25» src=«ref-1_863020029-278.coolpic» v:shapes="_x0000_i1042">


Кількість потоку, що виходять із джерела або входять у стік,
<img width=«220» height=«37» src=«ref-1_863020307-718.coolpic» v:shapes="_x0000_i1043">
Під задачею про максимальний потік розуміється задача пошуку в 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(<img width=«32» height=«21» src=«ref-1_863021025-121.coolpic» v:shapes="_x0000_i1044">)

0(<img width=«36» height=«21» src=«ref-1_863021146-124.coolpic» v:shapes="_x0000_i1045">)

0(<img width=«19» height=«21» src=«ref-1_863021270-100.coolpic» v:shapes="_x0000_i1046">)

0(<img width=«45» height=«24» src=«ref-1_863021370-153.coolpic» v:shapes="_x0000_i1047">)

0(<img width=«53» height=«21» src=«ref-1_863021523-153.coolpic» v:shapes="_x0000_i1048">)



0(<img width=«19» height=«21» src=«ref-1_863021270-100.coolpic» v:shapes="_x0000_i1049">)

0(<img width=«19» height=«21» src=«ref-1_863021270-100.coolpic» v:shapes="_x0000_i1050">)

0(<img width=«19» height=«21» src=«ref-1_863021270-100.coolpic» v:shapes="_x0000_i1051">)

0(<img width=«28» height=«21» src=«ref-1_863021976-115.coolpic» v:shapes="_x0000_i1052">)

0(<img width=«27» height=«21» src=«ref-1_863022091-114.coolpic» v:shapes="_x0000_i1053">)



0(<img width=«19» height=«21» src=«ref-1_863022205-100.coolpic» v:shapes="_x0000_i1054">)

0(<img width=«19» height=«21» src=«ref-1_863022305-101.coolpic» v:shapes="_x0000_i1055">)

0(<img width=«19» height=«21» src=«ref-1_863021270-100.coolpic» v:shapes="_x0000_i1056">)

0(<img width=«19» height=«21» src=«ref-1_863022506-101.coolpic» v:shapes="_x0000_i1057">)

0(<img width=«19» height=«21» src=«ref-1_863021270-100.coolpic» v:shapes="_x0000_i1058">)



0(<img width=«19» height=«21» src=«ref-1_863022707-102.coolpic» v:shapes="_x0000_i1059">)

0(<img width=«19» height=«21» src=«ref-1_863022707-102.coolpic» v:shapes="_x0000_i1060">)

0(<img width=«19» height=«21» src=«ref-1_863022707-102.coolpic» v:shapes="_x0000_i1061">)

0(<img width=«28» height=«21» src=«ref-1_863023013-116.coolpic» v:shapes="_x0000_i1062">)

0(<img width=«28» height=«21» src=«ref-1_863023129-117.coolpic» v:shapes="_x0000_i1063">)



Таблиця.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) <img width=«13» height=«13» src=«ref-1_863013797-84.coolpic» v:shapes="_x0000_i1064"> Е задана вартість <img width=«19» height=«25» src=«ref-1_863023330-99.coolpic» v:shapes="_x0000_i1065"> переміщення одиниці транспортного потоку і необхідно знайти потік заданого розміру v із джерела s у стік t, що мінімізує зважену суму потоків

Для рішення цієї задачі запропонована множина різноманітних алгоритмів і їхніх узагальнень. Серед. них алгоритми, засновані на застосуванні прямих і двоїстих симплекс-алгоритмів лінійного програмування й алгоритмів пошуку найкоротших шляхів. Одним із поширених алгоритмів є так називаний алгоритм дефекту [4], що дозволяє вирішувати задач про потік мінімальної вартості достатньо загального виду. Число операцій алгоритму дефекту оцінюється як 0(<img width=«37» height=«25» src=«ref-1_863023429-139.coolpic» v:shapes="_x0000_i1066">), де число К0, обумовлене на перших ітераціях алгоритму, не перевищує <img width=«41» height=«24» src=«ref-1_863023568-137.coolpic» v:shapes="_x0000_i1067">, п — число вершин мережі, т — число її дуг, а
<img width=«117» height=«37» src=«ref-1_863023705-556.coolpic» v:shapes="_x0000_i1068">
Очевидно, можна замість 0(<img width=«37» height=«25» src=«ref-1_863023429-139.coolpic» v:shapes="_x0000_i1069">) використовувати оцінку 0(<img width=«96» height=«23» src=«ref-1_863024400-73.coolpic» v:shapes="_x0000_i1070">). У [5] запропонована модифікація алгоритму дефекту з оцінкою числа операцій 0 (<img width=«112» height=«25» src=«ref-1_863024473-254.coolpic» v:shapes="_x0000_i1071">).

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

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

Кожній дузі (i, j) мережі поставлена у відповідність її довжина <img width=«16» height=«25» src=«ref-1_863024727-100.coolpic» v:shapes="_x0000_i1072">, або тривалість проходження одиниці транспортного потоку, що у загальному випадку може бути позитивним і негативним числом.

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

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

Проте у розрахунковому відношенні більш ефективними виявилися спеціальні, так називані комбінаторні алгоритми, аналізовані в даному розділі. У цих алгоритмах вихідні дані подані у виді списків дуг, тобто для кожної вершини дається список тих дуг (i, j), що інцидентні їй, разом із їхніми довжинами <img width=«16» height=«25» src=«ref-1_863024727-100.coolpic» v:shapes="_x0000_i1073">. Оцінки числа операцій алгоритмів приведені в табл. 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. Визначимо <img width=«19» height=«25» src=«ref-1_863024927-100.coolpic» v:shapes="_x0000_i1074">  — довжину найкоротшого шляху з вихідної вершини 1 у вершину j за умови, що вершини пронумеровані числами 1, 2, 3,..., п. Шлях найкоротшої довжини знаходиться з такого рівняння:
<img width=«151» height=«45» src=«ref-1_863025027-705.coolpic» v:shapes="_x0000_i1075">j=2,3,…,n;uj=0
У результаті розрахунків знаходиться (якщо воно існує) дерево найкоротших відстаней із коренем у вершині 1, у якому довжина єдиного шляху з 1 у j дорівнює uj, j=2, 3,..., п.

Алгоритми Дийкстра. Роздивимося мережу G (V, Е), у котрої довжини lijусіх дуг позитивні. Тоді відомий алгоритм Дийкстра може бути записаний у такий спосіб.

Крок 0. Покласти
<img width=«47» height=«23» src=«ref-1_863025732-138.coolpic» v:shapes="_x0000_i1076">

  <img width=«89» height=«73» src=«ref-1_863025870-541.coolpic» v:shapes="_x0000_i1077"> 

S={1,2,3…,n}
Крок 1. Знайти<img width=«44» height=«19» src=«ref-1_863026411-128.coolpic» v:shapes="_x0000_i1078">, для котрого = <img width=«72» height=«36» src=«ref-1_863026539-342.coolpic» v:shapes="_x0000_i1079"><img width=«12» height=«35» src=«ref-1_863026881-73.coolpic» v:shapes="_x0000_i1080">, якщо uk =+<img width=«16» height=«13» src=«ref-1_863026954-88.coolpic» v:shapes="_x0000_i1081"> — стіп; не існує шляху у вершини, що залишилася в S. Положимо S = S — {k}. Якщо S = <img width=«17» height=«19» src=«ref-1_863027042-97.coolpic» v:shapes="_x0000_i1082">  — стіп; обчислення закінчені.

Крок 2. Покласти <img width=«19» height=«25» src=«ref-1_863024927-100.coolpic» v:shapes="_x0000_i1083"> = min{<img width=«69» height=«25» src=«ref-1_863027239-179.coolpic» v:shapes="_x0000_i1084">} для всіх (k, j) <img width=«13» height=«13» src=«ref-1_863013797-84.coolpic» v:shapes="_x0000_i1085"> Е. Перейти до кроку 1.

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

Якщо припустити, що мережа G (V, Е) є ациклічний тобто не містить циклів, то в ній можна пронумерувати вершини так, що для кожної дуги з i у j виконується умова i < j. Очевидно, таке упорядкування може бути виконане за 0 (т) операцій. Тоді для приклада рівняння Белмана можуть бути вирішені простим обчисленням: и1 = 0, и2 залежить тільки від и1, и3 залежить від и1, и2, иj залежить від и1, и2,..., иj-1 і т.д. Таким чином, рішення може бути отримане за 0 (т) операцій.

Метод Белмана — Форда. Роздивимося мережу G (V, Е), у котрої або відсутні цикли, або довжини дуг ненегативні. Метод послідовних наближень, запропонований Белманом і Фордом, складається в такому.

Нехай uj(k) — довжина найкоротшого шляху від вихідної вершини до вершини j за умови, що шлях містить не більш ніж k дуг. Спочатку положимо
<img width=«128» height=«60» src=«ref-1_863027502-595.coolpic» v:shapes="_x0000_i1086">
Тоді <img width=«205» height=«27» src=«ref-1_863028097-589.coolpic» v:shapes="_x0000_i1087"> та <img width=«68» height=«27» src=«ref-1_863028686-179.coolpic» v:shapes="_x0000_i1088">. Для дуг k = 2, 3,...,n- 1 необхідно 0 (n) ітерацій. Кожна ітерація потребує 0 (m) операцій. Отже, метод потребує 0 (т п) операцій. Зауважимо, що для плоских графів потрібно 0 (<img width=«19» height=«21» src=«ref-1_863022506-101.coolpic» v:shapes="_x0000_i1089">) операцій.

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

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

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

Будемо шукати найкоротші шляхи між вершинами в мережі з позитивними і негативними довжинами дуг, починаючи з вершини 1. Очевидно, буде потрібно 0 (тп) обчислень для того, щоб знайти найкоротші шляхи з вершини 1 у всі інші вершини. Замінимо довжину кожної дуги <img width=«16» height=«25» src=«ref-1_863024727-100.coolpic» v:shapes="_x0000_i1090"> на <img width=«131» height=«27» src=«ref-1_863029066-257.coolpic» v:shapes="_x0000_i1091">. Довжина шляху з i у j, визначена за значеннями <img width=«16» height=«27» src=«ref-1_863029323-104.coolpic» v:shapes="_x0000_i1092">, відрізняється від щирої довжини на константу <img width=«47» height=«25» src=«ref-1_863029427-134.coolpic» v:shapes="_x0000_i1093">. Отже, рішення задачі визначення всіх найкоротших пар шляхів із довжинами <img width=«16» height=«25» src=«ref-1_863024727-100.coolpic» v:shapes="_x0000_i1094"> є рішенням вихідної задачі. Оскільки тепер усі довжини дуг невід’ємних, можна застосувати метод Дийкстра для кожній з останніх п — 1 задач. У результаті вся задача буде вирішена за 0 (<img width=«57» height=«21» src=«ref-1_863029661-160.coolpic» v:shapes="_x0000_i1095">) операцій, а для плоского графа за 0 (<img width=«55» height=«24» src=«ref-1_863029821-159.coolpic» v:shapes="_x0000_i1096">) операцій. У [18] запропонований алгоритм для невід’ємних дуг мережі G (V, Е), у якому очікуване число обчислень дорівнює 0 (<img width=«69» height=«24» src=«ref-1_863029980-191.coolpic» v:shapes="_x0000_i1097">).

Нехай мережа G (V, Е) складається з неорієнтованих дуг і ми хочемо знайти найкоротший шлях між двома визначеними вершинами. Якщо всі довжини дуг невід’ємних, те можна замінити кожну неорієнтованих дугу парою симетричних орієнтованих дуг (i,j) і (j, i) із <img width=«47» height=«25» src=«ref-1_863030171-145.coolpic» v:shapes="_x0000_i1098">і застосувати будь-який із зазначених вище алгоритмів.

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

У загальному випадку можна скористатися, наприклад, методом Белмана- Форда для визначення існування циклу негативної довжини в G (V, Е). Якщо мережа є сильнозв`язною, то цикл негативної довжини існує тоді і тільки тоді, коли uj(n) < uj(n-1) для деякої вершини j. Мережа може бути перевірена на існування негативного циклу за 0 (тп) операцій.


    продолжение
--PAGE_BREAK--2.2           Узагальнені задачі про потоки


У розглянутих вище задачах передбачалося, що однорідний транспортний потік, що виходить із дуги (i, j) <img width=«13» height=«13» src=«ref-1_863013797-84.coolpic» v:shapes="_x0000_i1099"> Е, дорівнює потокові, що входить у цю дугу. Проте в ряді практичних ситуацій це припущення не виконується. Наприклад, при транспортуванні вантажів може відбуватися їхнє псування або втрата (наприклад, вивітрювання), що призводить до зменшення потоку під час його переміщення по дузі (i, j) транспортної мережі G (V, Е).

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

Будемо вважати, що якщо в будь-яку дугу (i, j) <img width=«13» height=«13» src=«ref-1_863013797-84.coolpic» v:shapes="_x0000_i1100"> Е з вершини i виходить <img width=«19» height=«25» src=«ref-1_863030484-100.coolpic» v:shapes="_x0000_i1101"> одиниць потоку, то з цієї дуги у вершину j увійде <img width=«35» height=«25» src=«ref-1_863030584-135.coolpic» v:shapes="_x0000_i1102">одиниць потоку. Розмір <img width=«19» height=«25» src=«ref-1_863030719-107.coolpic» v:shapes="_x0000_i1103"> має назву коефіцієнта підсилення або просто посиленням дуги (i, j).

Якщо <img width=«19» height=«25» src=«ref-1_863030719-107.coolpic» v:shapes="_x0000_i1104"> > 1, то потік по дузі (i, j) посилюється. Якщо<img width=«19» height=«25» src=«ref-1_863030719-107.coolpic» v:shapes="_x0000_i1105"> = 1, то потік по дузі (i, j) залишається незмінним. Якщо 0 <<img width=«19» height=«25» src=«ref-1_863030719-107.coolpic» v:shapes="_x0000_i1106"> < 1, то потік по дузі (i, j) скорочується (частково поглинається). Якщо <img width=«19» height=«25» src=«ref-1_863030719-107.coolpic» v:shapes="_x0000_i1107">= 0, то потік по дузі (i, j) губиться (поглинається цілком) і дана дуга звичайно розглядається як стік. Якщо <img width=«19» height=«25» src=«ref-1_863030719-107.coolpic» v:shapes="_x0000_i1108">< 0, то для кожної одиниці потоку, що входить у вершину i, повинно потрапити <img width=«19» height=«25» src=«ref-1_863030719-107.coolpic» v:shapes="_x0000_i1109"> одиниць потоку у вершину j, тобто в даному випадку дуга (i, j) може розглядатися яка влаштувала попит на потік.

Узагальнена задача про транспортний потік мінімальної вартості на мережі G (V, Е) може бути сформульована як задача лінійного програмування такого виду:
<img width=«243» height=«140» src=«ref-1_863031468-1305.coolpic» v:shapes="_x0000_i1110">
де vs — чистий вхідної потік у s, а vt — чистий вихідний потік із t.

Для рішення задач оптимізації транспортних потоків останнім часом розроблена так називана теорія мережного програмування -інтенсивно що розвивається область математичного програмування [22].

Мережне програмування значно розширило межа рішення великомасштабних оптимізаційних транспортних задач. Спеціально розроблені мережні алгоритми дозволяють вирішувати задача значно швидше, чим самі зроблені універсальні методи математичного програмування. Нові мережні алгоритми явилися подальшим розвитком прямого симплекс-методу для рішення задач лінійного програмування.

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

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

Все це дозволило істотно зробити процес обчислень дешевшим за рахунок скорочення часу обчислення й обсягу використовуваної пам'яті ЕОМ.

Мережні алгоритми виявилися також дуже ефективними і для рішення таких окремих випадків задач про транспортні потоки на мережі G (V, Е), як задача про призначення і транспортна.

Був проведений обчислювальний експеримент, у процесі якого дорівнювалася стандартна програма рішення задачі лінійного програмування AРЕХ-III із мережними програмами на ЕОМ СDС CYВЕR-74 [23].

Результати експерименту за рішенням задачі про призначення, транспортної задачі, задача про потік мінімальної вартості й узагальненої задачі про потік приведені в табл. 4.
Таблиця 4 -задача про потік мінімальної вартості й узагальненої задачі про потік

Тип задачі

Кіл-ть рівнянь

Кіл-ть змінних

Линійне програмування

Мережеві методы

Часрішення, с

Вартість, $

Час рішення, с

Вартість, $

Задача про призначення

400

400

1500

2250

231,85

336,37

41,73

60,55

1,16

1,34

0,21

0,24

Транспортна задача

200

200

200

1350

1500

2000

105,68

124,53

164,94

19,02

22,42

29,69

0,94

1,07

1,21

0,17

0,19

0,22

Задача про поток мінімальной вартості

400

1000

1306

2900

174,83

833,63

31,47

150,05

1,51

5,28

0,27

0,95

Узагальнена задача

100

100

100

250

250

500

1000

1000

1000

1000

4000

4000

5000

6000

62,65

62,65

94,72

453,02

742,61

1044,34*

1633,64**

11,28

14,57

17,05

81,54

133,67

186,98*

294,06**

7,51

7,29

9,70

16,65

14,74

22,55

50,22

1,35

1,31

1,75

3,00

2,65

4,06

9,04
    продолжение
--PAGE_BREAK--2.3           Багатопродуктові потоки


Розглядалися до цих пір задачах транспортні потоки різноманітних видів (наприклад, що відповідають різноманітним типам транспортних засобів або різних вантажів) оптимізувати незалежно друг від друга або були зведені до деякого однорідного транспортного потоку. Більш загальною задачею є оптимізація сукупності транспортних потоків декількох видів з урахуванням наявності обмежень на загальну пропускну спроможність ланок транспортної мережі. Ця задача може бути сформульована у виді так називаної «задачі про багатопродуктовий потік» на мережі G (V, Е), що є задачею лінійного програмування спеціального виду.

Розмір потоку k-го продукту по дузі (i,j) <img width=«13» height=«13» src=«ref-1_863013797-84.coolpic» v:shapes="_x0000_i1111"><img width=«12» height=«23» src=«ref-1_863032857-73.coolpic» v:shapes="_x0000_i1112">Е визначимо через, <img width=«20» height=«27» src=«ref-1_863032930-113.coolpic» v:shapes="_x0000_i1113"> а вартість переміщення одиниці k-го продукту по дузі (i, j) — через <img width=«19» height=«27» src=«ref-1_863033043-109.coolpic» v:shapes="_x0000_i1114"> (k = 1,2,...,K).

Кожний із продуктів k має одне джерело <img width=«17» height=«24» src=«ref-1_863033152-94.coolpic» v:shapes="_x0000_i1115"> <img width=«13» height=«13» src=«ref-1_863013797-84.coolpic» v:shapes="_x0000_i1116">V і один стік <img width=«15» height=«24» src=«ref-1_863033330-95.coolpic» v:shapes="_x0000_i1117"> <img width=«13» height=«13» src=«ref-1_863013797-84.coolpic» v:shapes="_x0000_i1118">V, причому попит k-го продукту <img width=«17» height=«24» src=«ref-1_863033509-94.coolpic» v:shapes="_x0000_i1119"> у рядку <img width=«15» height=«24» src=«ref-1_863033330-95.coolpic» v:shapes="_x0000_i1120"> дорівнює пропозиції цього ж продукту в джерелі <img width=«17» height=«24» src=«ref-1_863033152-94.coolpic» v:shapes="_x0000_i1121">.

Задача про багатопродуктовий потік мінімальної вартості складається в тому, щоб знайти такі значення <img width=«20» height=«27» src=«ref-1_863032930-113.coolpic» v:shapes="_x0000_i1122">(i,j)<img width=«13» height=«13» src=«ref-1_863013797-84.coolpic» v:shapes="_x0000_i1123"> Е, k = 1, 2,…К щоб
    <img width=«189» height=«125» src=«ref-1_863033989-1185.coolpic» v:shapes="_x0000_i1124">


2.4 Задача планування перевезень як задача оптимізації взаємозалежних потоків на мережі

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

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

Незважаючи на те що існування взаємозалежних потоків на транспортній мережі є об'єктивною реальністю, цей факт не найшов явного відображення у відомих математичних моделях перевезень. У роботах, присвячених цій проблемі, або оптимізується один із потоків, або різноманітні потоки прямо або побічно відображається один з одним. У більшості робіт (наприклад, [12 — 17]) розглядається окремий випадок, коли потоки вантажів зафіксована і задача планування перевезень зводитися до задачі оптимального розподілення транспортних засобів по напрямках перевезень. У роботі [24], навпаки, розглядається задача оптимального розподілу потоків вантажів по транспортних мережах різноманітних видів транспорту без урахування переміщень транспортних засобів.

У ряді робіт (наприклад, [14 — 17]) розглядаються більш загальні задачі, у яких наявність потоку вантажів враховується непрямою уявою шляхом виділення потоків навантажених і порожніх транспортних засобів.

Постановка задачі оптимізації потоків на транспортній мережі, що у явному виді враховує наявність взаємозв'язку між потоками, запропонована в [18]. Проблема оптимізації взаємозалежних транспортних потоків розглянута на прикладі задача оптимізації двох основних потоків на транспортній мережі: потоку вантажів і потоку транспортних засобів, що є окремим випадком задачі (5) — (11).

Сформульована в [18] задача оптимізації двох взаємозалежних потоків на мережі полягає в такому.

Задано спрямованого графа без петель G (K, А), де K — множина вершин, А — множина дуг, що складається з <img width=«21» height=«20» src=«ref-1_863006072-107.coolpic» v:shapes="_x0000_i1125"> підграфів <img width=«96» height=«24» src=«ref-1_863035281-244.coolpic» v:shapes="_x0000_i1126">пов'язаних загальними вершинами <img width=«27» height=«25» src=«ref-1_863035525-124.coolpic» v:shapes="_x0000_i1127">.

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


<img width=«207» height=«206» src=«ref-1_863035649-979.coolpic» v:shapes="_x0000_s1076 _x0000_s1077 _x0000_s1088 _x0000_s1087 _x0000_s1079 _x0000_s1086 _x0000_s1085"> <img width=«245» height=«198» src=«ref-1_863036628-1284.coolpic» v:shapes="_x0000_s1078 _x0000_s1089 _x0000_s1084 _x0000_s1083 _x0000_s1082 _x0000_s1081 _x0000_s1080">


<img width=«45» height=«44» src=«ref-1_863037912-306.coolpic» hspace=«12» alt=«Овал: 3» v:shapes="_x0000_s1090"><img width=«534» height=«222» src=«ref-1_863038218-2688.coolpic» v:shapes="_x0000_s1091 _x0000_s1100 _x0000_s1101 _x0000_s1098 _x0000_s1108 _x0000_s1099 _x0000_s1107 _x0000_s1103 _x0000_s1109 _x0000_s1106 _x0000_s1092 _x0000_s1094 _x0000_s1093 _x0000_s1104 _x0000_s1105 _x0000_s1102 _x0000_s1097 _x0000_s1096 _x0000_s1095">



<img width=«109» height=«3» src=«ref-1_863040906-83.coolpic» v:shapes="_x0000_s1110"> Повторний потік \ Первинний потік

  <img width=«109» height=«3» src=«ref-1_863040989-99.coolpic» v:shapes="_x0000_s1112"> 1-й тип

<img width=«118» height=«3» src=«ref-1_863041088-102.coolpic» v:shapes="_x0000_s1113"> 2-й тип

<img width=«109» height=«3» src=«ref-1_863041190-94.coolpic» v:shapes="_x0000_s1114"> 3-й тип

  <img width=«107» height=«2» src=«ref-1_863041284-91.coolpic» v:shapes="_x0000_s1116"> 1-й тип

<img width=«107» height=«2» src=«ref-1_863041375-91.coolpic» v:shapes="_x0000_s1117"> 2-й тип

<img width=«107» height=«2» src=«ref-1_863041466-88.coolpic» v:shapes="_x0000_s1118"> 3-й тип

Рис. 2.1-Первинний і вторинний потоки
Потоки не є однорідними: на графі може існувати <img width=«15» height=«17» src=«ref-1_863041554-89.coolpic» v:shapes="_x0000_i1130"> видів повторного потоку і <img width=«19» height=«17» src=«ref-1_863041643-97.coolpic» v:shapes="_x0000_i1131"> типів первинного потоку. При цьому повторний потік може протікати від джерел до стоків будь-якими припустимими шляхами, тоді як кожний тип первинного потоку може існувати лише на визначеному підграфі <img width=«28» height=«24» src=«ref-1_863041740-125.coolpic» v:shapes="_x0000_i1132"> (відповідно до цого всі типи первинного потоку 1,..., <img width=«19» height=«17» src=«ref-1_863041643-97.coolpic» v:shapes="_x0000_i1133"> розділені на групи <img width=«23» height=«23» src=«ref-1_863041962-109.coolpic» v:shapes="_x0000_i1134">, М =<img width=«32» height=«27» src=«ref-1_863042071-132.coolpic» v:shapes="_x0000_i1135"> невзаємозамінює типів).

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

Первинний потік <img width=«29» height=«33» src=«ref-1_863042203-241.coolpic» v:shapes="_x0000_i1136"> m-го типу по дузі (i, j) <img width=«13» height=«13» src=«ref-1_863013797-84.coolpic» v:shapes="_x0000_i1137"> <img width=«27» height=«24» src=«ref-1_863042528-123.coolpic» v:shapes="_x0000_i1138">, М =<img width=«32» height=«27» src=«ref-1_863042071-132.coolpic» v:shapes="_x0000_i1139">, складається з потоків «активної» <img width=«30» height=«30» src=«ref-1_863042783-138.coolpic» v:shapes="_x0000_i1140"> і «пасивної» <img width=«31» height=«30» src=«ref-1_863042921-137.coolpic» v:shapes="_x0000_i1141"> складових:
    продолжение
--PAGE_BREAK--<img width=«320» height=«39» src=«ref-1_863043058-753.coolpic» v:shapes="_x0000_i1142">


Розмір активної складового <img width=«30» height=«30» src=«ref-1_863042783-138.coolpic» v:shapes="_x0000_i1143">первинного потоку визначає розмір повторного потоку <img width=«30» height=«30» src=«ref-1_863043949-137.coolpic» v:shapes="_x0000_i1144"> по цій дузі, наявність пасивної складової <img width=«31» height=«30» src=«ref-1_863042921-137.coolpic» v:shapes="_x0000_i1145">обумовлена вимогою зберігання первинного потоку m-го виду.

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

Залежність між первинним і повторним потоками виражається в тому. що розмір повторного потоку <img width=«30» height=«30» src=«ref-1_863043949-137.coolpic» v:shapes="_x0000_i1146"> по якийсь дузі (i, j) пропорційна активним складових різноманітних типів первинного потоку, що протікають по дузі:

Залежність між первинним і повторним потоками не є взаємно однозначної:

1) той самий повторний потік може підтримуватися різноманітними комбінаціями активних складових різноманітних типів первинного потоку;

2) повторний потік може протікати від джерел до стоків будь-якими шляхами, тоді як кожний тип первинного потоку може існувати лише на визначеному підграфі;

3) у процесі свого переміщення від джерела до стоку повторний потік може підтримуватися різноманітними типами первинного потоку, що переміняють один одного в проміжних вершинах (наприклад, на — дузі (7, 2) (див. мал. 3.4) повторний потік підтримується активної складового первинного потоку першого типу, а на дузі (2, 3) — активної складового первинного потоку другого типу);

4) первинний потік може існувати й у тих дугах, у яких повторний потік відсутніх (як, наприклад, у дузі (4, 5) на мал. 2.1).

На відміну від задачі (5) — (11) припускається лише часткове перетворення потоків різноманітних типів продуктів і без їхнього посилення або ослаблення: відмінні від нуля і рівні одиниці лише ті з коефіцієнтів перетворення, що зв'язують активну і пасивну складові того самого типу первинного потоку. Ці складові можуть переходити друг у друга у вершинах <img width=«59» height=«28» src=«ref-1_863044360-170.coolpic» v:shapes="_x0000_i1147">, наприклад на початку і по закінченні робіт (зокрема, при навантаженні і розвантаженні потік порожніх транспортних засобів перетворюється в потік навантажених і навпаки) або при зміні одних ресурсів на інші (зокрема, при перевалюванні вантажів із транспортних засобів одного типу на транспортні засоби іншого типу).

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

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

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

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

Максимізувати
<img width=«143» height=«46» src=«ref-1_863044530-745.coolpic» v:shapes="_x0000_i1148"> (3)
  (де <img width=«41» height=«27» src=«ref-1_863045275-145.coolpic» v:shapes="_x0000_i1149">- корисний ефект від переміщення одиниці повторного потоку і витрати на переміщення одиниці первинного потоку m-ого типу <img width=«57» height=«26» src=«ref-1_863045420-156.coolpic» v:shapes="_x0000_i1150"> подугах (i, j)<img width=«13» height=«13» src=«ref-1_863013797-84.coolpic» v:shapes="_x0000_i1151"> A графа) при виконанні звичайних умов зберігання кожного з потоків, що проходять через вершину i графа:
    <img width=«240» height=«189» src=«ref-1_863045660-1795.coolpic» v:shapes="_x0000_i1152"><img width=«57» height=«25» src=«ref-1_863047455-153.coolpic» v:shapes="_x0000_i1153"> (6)
де <img width=«27» height=«25» src=«ref-1_863047608-119.coolpic» v:shapes="_x0000_i1154">,<img width=«24» height=«25» src=«ref-1_863047727-116.coolpic» v:shapes="_x0000_i1155"> — попит і пропозиції для первинного і повторного потоків Ks+I, Ks-I, Ks+II і Ks-II — джерела і стоки для первинного і повторного потоків відповідно, а також обмежень на пропускну спроможність дуг
<img width=«140» height=«40» src=«ref-1_863047843-553.coolpic» v:shapes="_x0000_i1156"> (8)
і особливих обмежень, що відбивають розподіл первинного потоку на активну і пасивну складові
<img width=«223» height=«28» src=«ref-1_863048396-426.coolpic» v:shapes="_x0000_i1157"> (9)
і залежність повторного потоку від активних складових різноманітних типів первинного потоку
<img width=«201» height=«40» src=«ref-1_863048822-591.coolpic» v:shapes="_x0000_i1158"> (10)
Крім того, повинні виконуватися умови невід’ємності
<img width=«215» height=«30» src=«ref-1_863049413-447.coolpic» v:shapes="_x0000_i1159">. (11)
Як неважко бачити, основною особливістю, що відрізняє дану задачу від звичайних задач про багатопродуктові потоки мінімальної вартості [24], є наявність специфічних обмежень (9), (10).

Розглянута задача може бути зведена до традиційних задач про потоки в мережах лише в деяких окремих випадках. Одним із найбільше істотних умов для цього є виконання вимоги, щоб перетворення активної складової в пасивну й обернено відбувалося тільки в джерелах і стоках<img width=«38» height=«34» src=«ref-1_863049860-252.coolpic» v:shapes="_x0000_i1160"> для повторного потоку і не припускалася передача повторного потоку від ресурсів одного типу до ресурсів іншого типу, тобто щоб розмір активної складового первинного потоку (потоку ресурсів), що підтримує повторний потік від джерела до стоку, оставалась постоянной

У цьому випадку умови зберігання повторного потоку еквівалентні умовам зберігання активної складового первинного потоку, що дає можливість не розглядати повторний потік у явному виді. Якщо в мережі існує лише один тип первинного потоку <img width=«51» height=«21» src=«ref-1_863050112-145.coolpic» v:shapes="_x0000_i1161">, задача(3)-(11) зводиться до звичайної задачі про двохпродуктовий потік <img width=«13» height=«21» src=«ref-1_863050257-93.coolpic» v:shapes="_x0000_i1162"> і <img width=«15» height=«17» src=«ref-1_863050350-94.coolpic» v:shapes="_x0000_i1163">:
<img width=«221» height=«185» src=«ref-1_863050444-1954.coolpic» v:shapes="_x0000_i1164">
У ідеальному випадку, коли пасивна складова <img width=«17» height=«19» src=«ref-1_863052398-95.coolpic» v:shapes="_x0000_i1165"> відсутніх (тобто первинний потік цілком використовується для підтримки повторного потоку) або може бути задана апріорно, аналізована задача ще більш спрощується і переходить у задачу про однопродуктовий потік <img width=«20» height=«21» src=«ref-1_863052493-93.coolpic» v:shapes="_x0000_i1166"> мінімальної вартості.

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

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

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

Задано спрямованого графа G (К, А), що подає єдину транспортну мережу і складається з декількох подграфов <img width=«283» height=«27» src=«ref-1_863052586-527.coolpic» v:shapes="_x0000_i1167">окремих видів, що подають транспортні мережі окремих видів транспорту транспорту (рис. 2.2). Дуги графа подають можливі шляхи переміщення транспортних засобів, а вершини — пункти i<img width=«39» height=«25» src=«ref-1_863053113-137.coolpic» v:shapes="_x0000_i1168"> відправлення і призначення вантажів, пункти i<img width=«39» height=«25» src=«ref-1_863053250-142.coolpic» v:shapes="_x0000_i1169"> перевалювання вантажів і транзитні пункти <img width=«119» height=«22» src=«ref-1_863053392-328.coolpic» v:shapes="_x0000_i1170">.


<img width=«300» height=«511» src=«ref-1_863053720-4971.coolpic» v:shapes="_x0000_s1134 _x0000_s1142 _x0000_s1125 _x0000_s1132 _x0000_s1144 _x0000_s1131 _x0000_s1133 _x0000_s1149 _x0000_s1139 _x0000_s1124 _x0000_s1128 _x0000_s1143 _x0000_s1137 _x0000_s1140 _x0000_s1130 _x0000_s1123 _x0000_s1126 _x0000_s1127 _x0000_s1129 _x0000_s1138 _x0000_s1136 _x0000_s1141 _x0000_s1147 _x0000_s1146 _x0000_s1148 _x0000_s1145 _x0000_s1135 _x0000_s1122">



Рис 2.2-Транспортні мережі окремих видів транспорту транспорту
Перевезення вантажів із пункту відправлення в пункт призначення можуть здійснюватися різноманітними видами транспорту з послідовним перевалюванням у пунктах i<img width=«39» height=«25» src=«ref-1_863053250-142.coolpic» v:shapes="_x0000_i1174"> з одного виду транспорту на інший. При цьому загальний обсяг вантажів, що перевалюються з одних видів транспорту на інші, не перевищує пропускної спроможності пункту перевалювання <img width=«21» height=«25» src=«ref-1_863058833-112.coolpic» v:shapes="_x0000_i1175"> в даний період
<img width=«336» height=«47» src=«ref-1_863058945-1399.coolpic» v:shapes="_x0000_i1176"> (12)
де<img width=«43» height=«37» src=«ref-1_863060344-235.coolpic» v:shapes="_x0000_i1177">= <img width=«38» height=«34» src=«ref-1_863060579-223.coolpic» v:shapes="_x0000_i1178">, (13)

<img width=«34» height=«29» src=«ref-1_863060802-142.coolpic» v:shapes="_x0000_i1179">  — обсяг вантажів n-го роду, що перевалюються в i-м пункті з L,-го виду транспорту на M-й у t-м періоді.

У перевезенні вантажів між пунктами i і j M-м видом транспорту можуть брати участь різноманітні типи транспортних засобів т <img width=«36» height=«23» src=«ref-1_863060944-127.coolpic» v:shapes="_x0000_i1180">моючих різну вантажопідіймальність bтп:
<img width=«381» height=«50» src=«ref-1_863061071-1276.coolpic» v:shapes="_x0000_i1181"> (14)
де <img width=«36» height=«31» src=«ref-1_863062347-146.coolpic» v:shapes="_x0000_i1182">  — кількість вантажів п-го роду, перевезених M-м видом транспорту в t-й період, <img width=«29» height=«27» src=«ref-1_863062493-136.coolpic» v:shapes="_x0000_i1183">  — кількість транспортних засобів m-го виду, що перевозять вантажі n-го роду в t-й період.
    продолжение
--PAGE_BREAK--Потік <img width=«28» height=«27» src=«ref-1_863062629-129.coolpic» v:shapes="_x0000_i1184"> транспортних засобів m-го типу по дузі ділиться па потік навантажених <img width=«29» height=«27» src=«ref-1_863062493-136.coolpic» v:shapes="_x0000_i1185"> і порожніх <img width=«27» height=«27» src=«ref-1_863062894-130.coolpic» v:shapes="_x0000_i1186"> транспортних засобів


<img width=«396» height=«41» src=«ref-1_863063024-870.coolpic» v:shapes="_x0000_i1187"> (15)
Кількість транспортних засобів m-го типу <img width=«116» height=«27» src=«ref-1_863063894-258.coolpic» v:shapes="_x0000_i1188">, що починають або закінчують роботу в різноманітних вузлах i<img width=«44» height=«25» src=«ref-1_863064152-149.coolpic» v:shapes="_x0000_i1189"> транспортної мережі <img width=«28» height=«24» src=«ref-1_863041740-125.coolpic» v:shapes="_x0000_i1190"> у період t, дорівнює плановому обсягу запровадження і висновка їх з експлуатації в аналізованому плановому періоді <img width=«25» height=«25» src=«ref-1_863064426-120.coolpic» v:shapes="_x0000_i1191">:
<img width=«291» height=«28» src=«ref-1_863064546-513.coolpic» v:shapes="_x0000_i1192"> (16)
Передбачається, що у випадку недостача транспортних засобів вони можуть бути орендовані в зовнішніх організацій, а вільні транспортні засоби можуть бути спрямовані в резерв.

Для кожного вузла i транспортної мережі <img width=«163» height=«27» src=«ref-1_863065059-359.coolpic» v:shapes="_x0000_i1193"> виконуються умови зберігання минущого через нього потоку вантажів у кожний період часу t (t = <img width=«23» height=«25» src=«ref-1_863065418-105.coolpic» v:shapes="_x0000_i1194">):
<img width=«535» height=«43» src=«ref-1_863065523-1360.coolpic» v:shapes="_x0000_i1195"> (17)
— для пунктів відправлення-призначення <img width=«131» height=«25» src=«ref-1_863066883-288.coolpic» v:shapes="_x0000_i1196">, загальних для транспортних мереж декількох видів транспорту (<img width=«32» height=«25» src=«ref-1_863067171-134.coolpic» v:shapes="_x0000_i1197"> — обсяг вивозу надпланових вантажів M-м видом транспорту в періоді t);
<img width=«342» height=«40» src=«ref-1_863067305-841.coolpic» v:shapes="_x0000_i1198"> (18)
— для інших пунктів <img width=«165» height=«25» src=«ref-1_863068146-345.coolpic» v:shapes="_x0000_i1199"> відправлення-призначення;
<img width=«378» height=«41» src=«ref-1_863068491-1116.coolpic» v:shapes="_x0000_i1200"> (19)
— для пунктів <img width=«179» height=«25» src=«ref-1_863069607-368.coolpic» v:shapes="_x0000_i1201">, що є загальними для транспортних мереж декількох видів транспорту, але не є пунктами відправлення-призначення вантажів;
<img width=«136» height=«46» src=«ref-1_863069975-596.coolpic» v:shapes="_x0000_i1202"> (20)
— для інших вузлів <img width=«125» height=«25» src=«ref-1_863070571-279.coolpic» v:shapes="_x0000_i1203"> транспортної мережі.

<img width=«12» height=«23» src=«ref-1_863032857-73.coolpic» v:shapes="_x0000_s1151 _x0000_s1150">
Аналоггічною уявою для кожного вузла i виконуються умови зберігання потоків навантажених і порожніх транспортних засобів кожного типу т <img width=«36» height=«23» src=«ref-1_863060944-127.coolpic» v:shapes="_x0000_i1204">, М =<img width=«32» height=«27» src=«ref-1_863042071-132.coolpic» v:shapes="_x0000_i1205"> у період t (t = <img width=«23» height=«25» src=«ref-1_863065418-105.coolpic» v:shapes="_x0000_i1206">):

а) навантажені транспортні засоби
<img width=«220» height=«37» src=«ref-1_863071287-609.coolpic» v:shapes="_x0000_i1207">, (21)
-          для пунктів <img width=«52» height=«25» src=«ref-1_863071896-163.coolpic» v:shapes="_x0000_i1208">, у яких відбувається навантаження-розаантаження (<img width=«63» height=«25» src=«ref-1_863072059-186.coolpic» v:shapes="_x0000_i1209"> кількість транспортних засобів із вантажем n-го роду, що завантажуються і що розвантажуються в період t у пункті i);
<img width=«136» height=«37» src=«ref-1_863072245-479.coolpic» v:shapes="_x0000_i1210"> (22)
для інших пунктів <img width=«89» height=«25» src=«ref-1_863072724-227.coolpic» v:shapes="_x0000_i1211">;

б) порожні транспортні засоби
<img width=«460» height=«38» src=«ref-1_863072951-1079.coolpic» v:shapes="_x0000_i1212">. (23)
— для пунктів<img width=«97» height=«25» src=«ref-1_863074030-241.coolpic» v:shapes="_x0000_i1213"> — відправлення-призначення вантажів, у яких транспортні засоби вводяться і виводяться з експлуатації ( <img width=«55» height=«25» src=«ref-1_863074271-173.coolpic» v:shapes="_x0000_i1214">  — кількості транспортних засобів m-го типу, що спрямовуються в резерв і надходять із резерву, <img width=«25» height=«25» src=«ref-1_863074444-119.coolpic» v:shapes="_x0000_i1215">- кількість арендованих транспортних засобів);
<img width=«409» height=«39» src=«ref-1_863074563-976.coolpic» v:shapes="_x0000_i1216"> (24)


-для інших пунктів <img width=«149» height=«25» src=«ref-1_863075539-326.coolpic» v:shapes="_x0000_i1217">, у яких відбувається навантаження-розаантаження;
<img width=«215» height=«38» src=«ref-1_863075865-605.coolpic» v:shapes="_x0000_i1218"> (25)
— для інших пунктів <img width=«149» height=«25» src=«ref-1_863076470-321.coolpic» v:shapes="_x0000_i1219"> і запровадження і виводу транспортних засобів з експлуатації;
<img width=«134» height=«38» src=«ref-1_863076791-465.coolpic» v:shapes="_x0000_i1220"> (26)
-для інших пунктів <img width=«135» height=«25» src=«ref-1_863077256-303.coolpic» v:shapes="_x0000_i1221">транспортної мережі.

Загальна кількість вантажів n-го роду (<img width=«51» height=«25» src=«ref-1_863077559-144.coolpic» v:shapes="_x0000_i1222"> ), що відправляються з різноманітних пунктів або що доставляються в них, не перевищує необхідних обсягів відправлення-доставки вантажів <img width=«25» height=«25» src=«ref-1_863077703-116.coolpic» v:shapes="_x0000_i1223"> у заданому періоді <img width=«62» height=«27» src=«ref-1_863077819-180.coolpic» v:shapes="_x0000_i1224">.
<img width=«203» height=«40» src=«ref-1_863077999-602.coolpic» v:shapes="_x0000_i1225"> (27)
де <img width=«55» height=«25» src=«ref-1_863078601-171.coolpic» v:shapes="_x0000_i1226">  — кількість вантажів, що відправляються і що доставляються M-м видом транспорту.

Передбачається, що при наявності вільних транспортних засобів можна здійснити перевезення додаткових, надпланових вантажів (наприклад, вантажів іноземних фрахтувальників на морському транспорті).

Кількість вантажів, що зберігаються на складах у пункті <img width=«48» height=«25» src=«ref-1_863078772-152.coolpic» v:shapes="_x0000_i1227">(без обмежень будемо припускати, що <img width=«108» height=«25» src=«ref-1_863078924-248.coolpic» v:shapes="_x0000_i1228">) у кожний період часу t, не перевищує загальної ємності складів у даний період

<img width=«472» height=«52» src=«ref-1_863079172-1371.coolpic» v:shapes="_x0000_i1229"> (28)
де <img width=«65» height=«25» src=«ref-1_863080543-187.coolpic» v:shapes="_x0000_i1230">  — кількість вантажів n-го роду ввезених на склади і вивезених із них M-м видом транспорту в період <img width=«13» height=«22» src=«ref-1_863080730-149.coolpic» v:shapes="_x0000_i1231">, <img width=«24» height=«25» src=«ref-1_863080879-117.coolpic» v:shapes="_x0000_i1232">  — ємність складів у пункті i у період t, <img width=«19» height=«25» src=«ref-1_863080996-106.coolpic» v:shapes="_x0000_i1233">  — можливе збільшення ємності складів (наприклад, шляхом оренди додаткових помешкань) у період t,<img width=«21» height=«25» src=«ref-1_863081102-109.coolpic» v:shapes="_x0000_i1234"> — початкова кількість вантажів n-го роду та складах.

У будь-який момент часу кількість вантажів кожного роду, що зберігаються на складах, невід’ємна:
<img width=«352» height=«53» src=«ref-1_863081211-1197.coolpic» v:shapes="_x0000_i1235"> (29)
Кількість транспортних засобів кожного типу, що знаходяться в резерві в пункті i, невід’ємна:
<img width=«345» height=«45» src=«ref-1_863082408-800.coolpic» v:shapes="_x0000_i1236"> (30)
Загальний обсяг навантаження-розвантаження в кожному пункті i не перевищує пропускної спроможності вантажно-розвантажувальних устроїв
<img width=«325» height=«39» src=«ref-1_863083208-813.coolpic» v:shapes="_x0000_i1237"> (31)
а загальна кількість транспортних засобів, що переміщаються по дузі (i,j) транспортної мережі, — пропускної спроможності цієї дуги


<img width=«403» height=«39» src=«ref-1_863084021-989.coolpic» v:shapes="_x0000_i1238"> (32)
Крім того, на потік транспортних засобів накладені обмеження бюджетного типу                                                                                                                            
<img width=«359» height=«41» src=«ref-1_863085010-990.coolpic» v:shapes="_x0000_i1239"> (33)
де <img width=«23» height=«20» src=«ref-1_863086000-104.coolpic» v:shapes="_x0000_i1240">  — загальна кількість ресурсів, виділених для транспортних засобів m-го типу (наприклад, розмір бюджету часу), <img width=«59» height=«27» src=«ref-1_863086104-187.coolpic» v:shapes="_x0000_i1241">  — кількість ресурсів, що затрачаються на переміщення одиниці потоку по дузі (i, j). Всі перемінні задачі невід’ємні:      
<img width=«408» height=«27» src=«ref-1_863086291-780.coolpic» v:shapes="_x0000_i1242"> (34)
Потрібно визначити оптимальні кількості навантажених і порожніх транспортних засобів кожного типу, що переміщаються по дугах транспортних мереж різноманітних видів транспорту, кількості транспортних засобів, що спрямовуються в резерв, арендованих, починаючих і різноманітних вузлах закінчують, що роботу в, мережі, а також оптимальні обсяги відправлення, доставки, збереження, перевалювання і перевезення вантажів, при яких забезпечується одержання максимального прибутку (без урахуванням постійних складових):


<img width=«537» height=«187» src=«ref-1_863087071-4193.coolpic» v:shapes="_x0000_i1243"> (35)
де <img width=«21» height=«25» src=«ref-1_863091264-112.coolpic» v:shapes="_x0000_i1244">  — питомі прибутки від перевезення одиниці вантажів; <img width=«128» height=«25» src=«ref-1_863091376-305.coolpic» v:shapes="_x0000_i1245">  — питомі витрати на перевалювання, навантаження-розвантаження і збереження вантажів; <img width=«21» height=«25» src=«ref-1_863091681-111.coolpic» v:shapes="_x0000_i1246">- питомі прибутки від перевезення надпланових вантажів; <img width=«17» height=«25» src=«ref-1_863091792-105.coolpic» v:shapes="_x0000_i1247">  — питомі витрати на збільшення ємності складів; <img width=«53» height=«27» src=«ref-1_863091897-173.coolpic» v:shapes="_x0000_i1248">  — питомі витрати на переміщення й оренду транспортних засобів, <img width=«27» height=«25» src=«ref-1_863092070-123.coolpic» v:shapes="_x0000_i1249">  — питомі утрати від простою транспортних засобів.


    продолжение
--PAGE_BREAK--2.4           Двохрівнева система моделей планування транспортних потоків


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

Роздивимося тепер більш докладно формулювання і методи рішення задач кожного рівня [18].

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

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

Задано графа <img width=«77» height=«23» src=«ref-1_863092193-193.coolpic» v:shapes="_x0000_i1250">, що подає агреговану єдину транспортну мережу країни, що складається з агрегованих транспортних мереж <img width=«163» height=«27» src=«ref-1_863092386-366.coolpic» v:shapes="_x0000_i1251"> окремих видів транспорту і містить вершини <img width=«88» height=«25» src=«ref-1_863092752-220.coolpic» v:shapes="_x0000_i1252"> пункти відправлення-призначення, що подають, вантажів і пункти їхній перевалювання. Для кожного пункту <img width=«48» height=«25» src=«ref-1_863092972-149.coolpic» v:shapes="_x0000_i1253"> задані обсяги вантажів n-го роду <img width=«52» height=«25» src=«ref-1_863093121-161.coolpic» v:shapes="_x0000_i1254"> котрі потрібно відправити з нього або доставити у відповідний період часу, прибутки <img width=«61» height=«25» src=«ref-1_863093282-197.coolpic» v:shapes="_x0000_i1255">, витрати <img width=«28» height=«25» src=«ref-1_863093479-130.coolpic» v:shapes="_x0000_i1256"> при використані M-м видом транспорту одиниці ємності складів у пункті i прибуток <img width=«27» height=«25» src=«ref-1_863093609-127.coolpic» v:shapes="_x0000_i1257"> від вивозу одиниці вантажів, що були на складах у пункті i до початку планового періоду. Відомі також пропускні спроможності <img width=«26» height=«29» src=«ref-1_863093736-136.coolpic» v:shapes="_x0000_i1258"> ланок транспортної мережі, пропускні спроможності <img width=«21» height=«25» src=«ref-1_863058833-112.coolpic» v:shapes="_x0000_i1259"> пунктів перевалювання і витрати <img width=«32» height=«25» src=«ref-1_863093984-143.coolpic» v:shapes="_x0000_i1260"> на перевалювання одиниці вантажу з одного виду транспорту на інший. З деяких пунктів можливий вивіз надпланових вантажів (наприклад, на морському транспорті такими вантажами є вантажі іноземних фрахтувальників).

Потрібно знайти розмір агрегованого потоку вантажів по дугах графа {<img width=«31» height=«27» src=«ref-1_863094127-140.coolpic» v:shapes="_x0000_i1261"> }, обсяги відправлення і доставки вантажів {<img width=«31» height=«25» src=«ref-1_863094267-135.coolpic» v:shapes="_x0000_i1262"> }, {<img width=«31» height=«25» src=«ref-1_863094402-135.coolpic» v:shapes="_x0000_i1263"> }, обсяги перевалювання вантажів із М-го виду транспорту на L-й і навпаки в кожному пункті перевалювання {<img width=«29» height=«25» src=«ref-1_863094537-136.coolpic» v:shapes="_x0000_i1264"> }, {<img width=«29» height=«25» src=«ref-1_863094673-138.coolpic» v:shapes="_x0000_i1265"> }, обсяги відправлення надпланових вантажів {<img width=«32» height=«25» src=«ref-1_863094811-137.coolpic» v:shapes="_x0000_i1266"> }, кількості вантажів, що спрямовуються кожним видом транспорту на склади або вивезених із складів {<img width=«29» height=«25» src=«ref-1_863094948-136.coolpic» v:shapes="_x0000_i1267"> }, {<img width=«29» height=«25» src=«ref-1_863095084-135.coolpic» v:shapes="_x0000_i1268"> }, і визначити частки {<img width=«27» height=«25» src=«ref-1_863095219-125.coolpic» v:shapes="_x0000_i1269"> } і {<img width=«28» height=«25» src=«ref-1_863095344-129.coolpic» v:shapes="_x0000_i1270"> } початкової кількості вантажів на складах у кожному пункті і загальній ємності складів, що виділяються в розпорядження кожного виду транспорту, при яких досягається максимум економічного ефекту

  <img width=«554» height=«69» src=«ref-1_863095473-2823.coolpic» v:shapes="_x0000_i1271">
При цьому повинні виконуватися умови зберігання агрегованого потоку вантажів n-го роду (<img width=«55» height=«25» src=«ref-1_863098296-154.coolpic» v:shapes="_x0000_i1272"> ) при проходженні через вершини графа в кожний період часу t(<img width=«44» height=«25» src=«ref-1_863098450-132.coolpic» v:shapes="_x0000_i1273"> )
<img width=«481» height=«48» src=«ref-1_863098582-1596.coolpic» v:shapes="_x0000_i1274"> (37)

<img width=«513» height=«48» src=«ref-1_863100178-1802.coolpic» v:shapes="_x0000_i1275">(38)

<img width=«528» height=«48» src=«ref-1_863101980-1979.coolpic» v:shapes="_x0000_i1276">(39)
де
<img width=«97» height=«25» src=«ref-1_863103959-237.coolpic» v:shapes="_x0000_i1277"> <img width=«109» height=«21» src=«ref-1_863104196-220.coolpic» v:shapes="_x0000_i1278"> (40)
Обмеження (37) відповідає пунктам відправлення і доставки вантажів, що одночасно є пунктами перевалювання, обмеження (38) — пунктам, що є тільки пунктами відправлення і доставки, а обмеження (39) — іншим пунктам. Крім того, виконуються обмеження на максимально можливі обсяги відправлення і доставки вантажів
<img width=«265» height=«55» src=«ref-1_863104416-1270.coolpic» v:shapes="_x0000_i1279"> (41)
обмеження на максимально можливі обсяги перевалювання вантажів з одного виду транспорту на інший у кожному пункті перевалювання

<img width=«280» height=«41» src=«ref-1_863105686-985.coolpic» v:shapes="_x0000_i1280"> (42)
обмеження на пропускну спроможність ланки агрегованої транспортної мережі:
<img width=«277» height=«39» src=«ref-1_863106671-694.coolpic» v:shapes="_x0000_i1281"> (43)
і обмеження на використання ємності складів у вузлах агрегованої транспортної мережі різноманітними видами транспорту
<img width=«375» height=«45» src=«ref-1_863107365-936.coolpic» v:shapes="_x0000_i1282"> (44)
де
<img width=«277» height=«37» src=«ref-1_863108301-715.coolpic» v:shapes="_x0000_i1283"> (45)
Кількість вантажів кожного роду, що зберігаються на складах у кожний момент часу, невід’ємна:
<img width=«404» height=«45» src=«ref-1_863109016-917.coolpic» v:shapes="_x0000_i1284"> (46)
де <img width=«27» height=«25» src=«ref-1_863095219-125.coolpic» v:shapes="_x0000_i1285"> початкової кількості вантажів п-го роду, що може бути вивезена M-м видом транспорту,
    продолжение
--PAGE_BREAK--<img width=«228» height=«37» src=«ref-1_863110058-587.coolpic» v:shapes="_x0000_i1286"> (47) Крім того, повинні виконуватися умови невід’ємності:


<img width=«397» height=«37» src=«ref-1_863110645-1345.coolpic» v:shapes="_x0000_i1287"> (48)
Сформульована задача є задачею лінійного програмування з мережною підструктурою. В.зв'язку з тим що матриця її обмежень має квазіблочний вид, для рішення задачі може бути використаний метод декомпозиції.

Шляхом розкладання обмежень (41), (42), (45), (47) на окремі обмеження для кожного підграфа вихідна задача (36) — (48) зводиться до двохрівневої системи більш простих задач. Ця система складається з розв'язуваних на другому рівні задач розподілу обсягів відправлення і доставки вантажів <img width=«52» height=«25» src=«ref-1_863093121-161.coolpic» v:shapes="_x0000_i1288">, пропускних спроможностей пунктів перевалювання <img width=«21» height=«25» src=«ref-1_863058833-112.coolpic» v:shapes="_x0000_i1289">, ємностей складів <img width=«24» height=«25» src=«ref-1_863080879-117.coolpic» v:shapes="_x0000_i1290"> і початкової кількості вантажів у них <img width=«21» height=«25» src=«ref-1_863081102-109.coolpic» v:shapes="_x0000_i1291"> між різноманітними видами транспорту:
<img width=«381» height=«331» src=«ref-1_863112489-5017.coolpic» v:shapes="_x0000_i1292">
і розв'язуваних на першому рівні задач визначення агрегованых потоків вантажів по окремим підграфами <img width=«96» height=«24» src=«ref-1_863117506-249.coolpic» v:shapes="_x0000_i1293">, що відповідають різноманітним видам транспорту М:
<img width=«525» height=«177» src=«ref-1_863117755-3597.coolpic» v:shapes="_x0000_i1294">
Крім того, повинні виконуватися обмеження (37)-(39), (43), (44), (46), (48).

Застосування методу декомпозиції дозволяє істотно | зменшити розрахункові труднощі. Задача другого рівня 1 мають просту структуру, і їхні рішення можуть бути виписані 3 у явному виді, а задача першого рівня вирішуються на окремих підграфах і можуть бути зведені до задач про однопродуктовий потік мінімальної вартості, для яких є ефективні спеціальні алгоритми [14-26] (як зазначено в [13], за допомогою даних алгоритмів задачі вирішуються приблизно в 50-100 разів швидше, чим за допомогою звичайних методів лінійного програмування. Так, наприклад, задача з 1200 вершинами і 4000 дуг була вирішена усього за 20 с).

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

2.6 Модель нижнього рівня — оптимізація транспортних потоків на транспортних мережах окремих видів транспорту


Як вже визначалося, задача нижнього рівня розпадається на <img width=«21» height=«20» src=«ref-1_863006072-107.coolpic» v:shapes="_x0000_i1295"> задач, що відповідають окремим видам транспорту. Для кожного виду транспорту М вирішується така задача. Потрібно максимізувати економічний ефект від перевезення вантажів М-м видом транспорту
<img width=«526» height=«109» src=«ref-1_863121459-3519.coolpic» v:shapes="_x0000_i1296">(49)

при виконанні обмежень
<img width=«522» height=«39» src=«ref-1_863124978-1460.coolpic» v:shapes="_x0000_i1297">(50)

<img width=«476» height=«39» src=«ref-1_863126438-1539.coolpic» v:shapes="_x0000_i1298"> (51)

<img width=«537» height=«39» src=«ref-1_863127977-1412.coolpic» v:shapes="_x0000_i1299"> (52)

<img width=«277» height=«39» src=«ref-1_863129389-904.coolpic» v:shapes="_x0000_i1300"> (53)
де <img width=«103» height=«25» src=«ref-1_863130293-212.coolpic» v:shapes="_x0000_i1301">відображаючих умови зберігання потоку вантажів кожного роду.

Крім того, повинні виконуватися обмеження на максимально можливі обсяги відправлення і доставки вантажів
<img width=«208» height=«25» src=«ref-1_863130505-416.coolpic» v:shapes="_x0000_i1302"> (54)
обмеження на кількість вантажів, що можуть бути спрямовані на склад:

<img width=«341» height=«45» src=«ref-1_863130921-965.coolpic» v:shapes="_x0000_i1303"> (55)
і узяті зі складів:
<img width=«336» height=«45» src=«ref-1_863131886-887.coolpic» v:shapes="_x0000_i1304"> (56)
Розглянемо математичну модель і метод рішення.

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

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

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

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

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

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

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

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

У [19] запропонований двохетапний метод рішення задачі розставляння транспортних засобів.

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

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

У [10] розглянута задача розподілу транспортних засобів по всіх можливих схемах прямування і динамічної задачі переміщення транспортних засобів з одних схем на інші при зміні умов експлуатації в різні періоди часу.

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

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

У зв`язку із цим у [15] запропонований декомпозиційний метод для рішення задач, що мають велику розмірність.

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

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

Перед тим, як переходити до формулювання моделі, уведемо деякі позначення:

<img width=«27» height=«25» src=«ref-1_863132773-118.coolpic» v:shapes="_x0000_i1305">  — обсяг перевезень вантажів n-го роду по l-му напрямку в період <img width=«13» height=«15» src=«ref-1_863132891-85.coolpic» v:shapes="_x0000_i1306"> транспортними засобами m-го типу, що належать підприємству (усі типи транспортних засобів т діляться на групи <img width=«80» height=«28» src=«ref-1_863132976-196.coolpic» v:shapes="_x0000_i1307">);

<img width=«57» height=«27» src=«ref-1_863133172-182.coolpic» v:shapes="_x0000_i1308">  — обсяги перевезень транспортними засобами m-го типу, орендованими в іншого підприємства р для виконання окремих перевезень і на весь період <img width=«13» height=«15» src=«ref-1_863132891-85.coolpic» v:shapes="_x0000_i1309"> відповідно;

<img width=«19» height=«25» src=«ref-1_863133439-107.coolpic» v:shapes="_x0000_i1310">  — обсяг вантажів n-го роду, що транспортне підприємство повинно перевезти по напрямку l у заданий період, часу [<img width=«41» height=«28» src=«ref-1_863133546-147.coolpic» v:shapes="_x0000_i1311">];

<img width=«21» height=«25» src=«ref-1_863133693-110.coolpic» v:shapes="_x0000_i1312">  — залишок вантажів n-го роду на l-й напрямку в період <img width=«63» height=«25» src=«ref-1_863133803-282.coolpic» v:shapes="_x0000_i1313">;

<img width=«29» height=«27» src=«ref-1_863134085-132.coolpic» v:shapes="_x0000_i1314">  — обсяг перевезень транспортними засобами m-го типу, зданими в оренду іншому підприємству р для виконання окремих перевезень;
    продолжение
--PAGE_BREAK--<img width=«24» height=«27» src=«ref-1_863134217-120.coolpic» v:shapes="_x0000_i1315">  — витрати бюджету часу транспортних засобів, наданих у ореду іншому підприємству р на період <img width=«13» height=«15» src=«ref-1_863132891-85.coolpic» v:shapes="_x0000_i1316">;
<img width=«24» height=«20» src=«ref-1_863134422-106.coolpic» v:shapes="_x0000_i1317">  — позаексплуатаційні витрати бюджету часу (наприклад, на плановий ремонт), розподіл яких по період дам часу {<img width=«20» height=«25» src=«ref-1_863134528-106.coolpic» v:shapes="_x0000_i1318">} можна регулювати;

<img width=«27» height=«25» src=«ref-1_863134634-121.coolpic» v:shapes="_x0000_i1319">  — трудомісткість перевезення вантажу n-го роду по l-му напрямку в період <img width=«13» height=«15» src=«ref-1_863132891-85.coolpic» v:shapes="_x0000_i1320"> транспортними засобами m-го типу;

<img width=«20» height=«25» src=«ref-1_863134840-107.coolpic» v:shapes="_x0000_i1321">  — прибутки від перевезення одиниці вантажу;

<img width=«27» height=«25» src=«ref-1_863134947-121.coolpic» v:shapes="_x0000_i1322">  — експлуатаційні витрати на перевезення единиці вантажу;

<img width=«55» height=«27» src=«ref-1_863135068-182.coolpic» v:shapes="_x0000_i1323">  — арендна платня за перевезення лдиниці вантажу та за одинцю бютжетного часу арендованого транспортного засобу;
<img width=«24» height=«28» src=«ref-1_863135250-128.coolpic» v:shapes="_x0000_i1324">  — експлуатаційні витрати на одиницю бюджету времени транспортних засобів, що здаються в оренду другому пред прийняттю на перпод <img width=«13» height=«15» src=«ref-1_863132891-85.coolpic» v:shapes="_x0000_i1325">;
<img width=«23» height=«25» src=«ref-1_863135463-112.coolpic» v:shapes="_x0000_i1326">  — втрати від невивозу вантажу n-го роду на l-ном напрямку в період <img width=«45» height=«25» src=«ref-1_863135575-135.coolpic» v:shapes="_x0000_i1327">(щодо обов’язкових перевезень <img width=«53» height=«25» src=«ref-1_863135710-151.coolpic» v:shapes="_x0000_i1328">).

Математична модель планування об’ємів перевезень має наступний вигляд.

Потрібно максимізувати отримуємий транспортним підприємством прибуток, який складається з прибутків від перевезення вантажів як власними, так й арендованими транспортними засобами та прибутків від надання транспортних засобів у аренду за різністю експлуатаційних витрат, витрат на аренду та витрат, пов’язаних з затримкою вивозу вантажів:
<img width=«519» height=«181» src=«ref-1_863135861-3399.coolpic» v:shapes="_x0000_i1329"> (57)
При цьому повинні бути виконані такі обмеження.
Сума обсягу вантажів, перевезених як власними, так і орендованими транспортними засобами, і обсягу вантажів, перевезення яких переноситься на інші періоди, повинна бути дорівнює загальній кількості вантажів:
<img width=«375» height=«56» src=«ref-1_863139260-1316.coolpic» v:shapes="_x0000_i1330"> (58)

<img width=«368» height=«51» src=«ref-1_863140576-1051.coolpic» v:shapes="_x0000_i1331"> (59)
Витрати бюджету часу транспортних з асобів, що укладаються з витрат на перевезення вантажів, витрат під час оренди і позаесплуатаційних витрат, не повинні перевищувати загального календарного бюджету часу транспортних засобів даного типу в даний період:
<img width=«329» height=«51» src=«ref-1_863141627-1011.coolpic» v:shapes="_x0000_i1332"> (60)
де
<img width=«191» height=«37» src=«ref-1_863142638-482.coolpic» v:shapes="_x0000_i1333"> (61)
Витрати на аренду не повині перевищувати виділену для цього суму
<img width=«247» height=«37» src=«ref-1_863143120-895.coolpic» v:shapes="_x0000_i1334"> (62)
Обсяги надання транспортних засобів в оренду не повинні перевищувати відповідних потреб:
<img width=«221» height=«36» src=«ref-1_863144015-506.coolpic» v:shapes="_x0000_i1335"> (63)

<img width=«127» height=«27» src=«ref-1_863144521-273.coolpic» v:shapes="_x0000_i1336"> (64)
Витрати бютжету часу арендованих транспортних засобів не можуть більше максимально м ожливих:

<img width=«257» height=«36» src=«ref-1_863144794-809.coolpic» v:shapes="_x0000_i1337"> (65)
Витрати бюджету часу, обсяги перевезень і обсяги вантажів невід’:
<img width=«235» height=«27» src=«ref-1_863145603-459.coolpic» v:shapes="_x0000_i1338"> (66)
Особливістю даної моделі в порівнянні з запропонованими: раніше є те, що в ній істотно враховується сезонність вантажопотоків і обмеження на використання транспортних засобів на окремих напрямках перевезень у різний час року, припускається перенос перевезення деяких вантажів на інший період часу,' враховуються утрати від невчасного вивозу вантажів, обов'язковість деяких із перевезень і можливість оренди транспортних засобів.

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

У результаті декомпозиції шляхом розкладання обмежень (58), (59), (62), (63) по групах типів транспортних засобів <img width=«80» height=«28» src=«ref-1_863132976-196.coolpic» v:shapes="_x0000_i1339">, задача (57)-(66) зводиться до двохрівневому комплексу задач меншої розмірності.

На другому (верхньому) рівні вирішуються задачі розподілу обсягів вантажів, обсягів решти транспортних засобів в оренду і коштів між групами транспортних засобів:
<img width=«532» height=«96» src=«ref-1_863146258-2237.coolpic» v:shapes="_x0000_i1340">
де коефіцієнти цільових функцій <img width=«80» height=«27» src=«ref-1_863148495-221.coolpic» v:shapes="_x0000_i1341"> характеризуютьдоцільність збільшення для j-й групи транспортних засобів що виділяється обсягу решти транспортних засобів в аренду, кількості коштів і обсягу вантажів відповідно.

На першому (нижньому) рівні для кожної групи j (j =1, J) визначаються обсяги перевезень власними й арендованими транспортними засобами, обсяги вантажів, перевезення котрих переноситься на інші планові періоди, а також обсяги аренди і решти в оренду транспортних засобів, що забезпечують отримання максимального економічного ефекту
<img width=«529» height=«139» src=«ref-1_863148716-3245.coolpic» v:shapes="_x0000_i1342">
при виконанні обмежень (59)-(61), (64), (65), специфічних для даної групи транспортних засобів, а також заданих другим рівнем обмежень на загальні обсяги перевезень вантажів власними, арендованими і що здаються в аренду транспортними засобами
<img width=«317» height=«96» src=«ref-1_863151961-1583.coolpic» v:shapes="_x0000_i1343">
і на загальні витрати, пов'язані з орендою транспортних засобів,
<img width=«267» height=«40» src=«ref-1_863153544-981.coolpic» v:shapes="_x0000_i1344">
та умовневід’ємності змінних


<img width=«239» height=«27» src=«ref-1_863154525-486.coolpic» v:shapes="_x0000_i1345">
Для узгодження рішень отриманих підзадач другого і першого рівня з метою досягнення оптимального рішення вихідної задачі застосовується ітеративний алгоритм.

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

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

Для рішення практичних задач розподілу потоків вантажів між різноманітними типами транспортних засобів розроблені програми: GRASS1, що дозволяє вирішити задачу (57)-(66) звичайним алгоритмом лінійного програмування, і GRASS2, що реалізує декомпозиционный алгоритм рішення цієї задачі. Програми побудовані по модульному принципі, мають оверлейную структуру і містять такі модулі:

GRAS1, GRAS2 — модулі, що управляють викликом підпрограм при рішенні задача (57)-(66) та відповідно задач другого і першого рівнів у дворівневоймоделі;

INPUT1, INPUT2 — підпрограми для запровадження вихідних даних і формування на їхній основі матриць умов задачі лінійного програмування;

LINK1, LINK2- підпрограми для перетворення розширеної матриці умов, задача лінійного програмування (яка містить строчку коефіцієнтів критерію і стовпчик правих частин обмежень) у компактну форму (без нульових елементів);

SIMPL1, SIMPL2 — підпрограми для рзшзния задач лінійного програмування з компактною формою матриці обмежень;

SOLVE1, SOLVE2- підпрограми, що реалізують звичайний Ц декомпозиционный алгоритми рішення задачі з використанням одноуровневой і двухуровневой моделей відповідно;


    продолжение
--PAGE_BREAK--2.7 Основні задачі оптимізації транспортних потоків


Всі задачі оптимізації транспортних потоків можна розділити на два класи: задача, у яких транспортні потоки рахуються незалежними, і задача, у яких враховується взаємозв'язок транспортних потоків різноманітних видів.

Перший клас задач вивчений достатньо докладно, і йому присвячене значне спало робіт, чого не можна сказати про другий клас, порівняно мало досліджуваному.

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

Найбільше добре вивченими і широко застосовуваними є задачі визначення максимального транспортного потоку однієї групи (потоку вантажів, транспортних засобів і т.п.), що протікає від джерела s у стік t мережі. При цьому кожній дузі (i, j) мережі G (K, А) приписана деяка пропускна спроможність, що визначає найбільше значення транспортного потоку, що може протікати по даній дузі.

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

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

Одним з окремих випадків задач оптимізації потоків, розв'язуваних при керуванні масовими перевозками, є визначення найкоротших шляхів на транспортній мережі. Ця задача необхідна для упорядкування матриць кореспонденції: таблиць міжпортових кореспонденції — на морському транспорті і шахів-маток кореспонденції — на залізничному транспорті.

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

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

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

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

У задачах маршрутизації при заданих множинах пунктів гроизводства, споживання, розміщення рухливого складу,

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

У випадку, що коли вирішує чинником у плануванні роботи транспортного підприємства є урахування динаміки транспортного процесу, виникають задачі упорядкування графіків прямування транспортних засобів. У графіках визначаються маршрути прямування транспортних засобів, що задовольняють заданим моментам їхній прибуття або відправлення в пункти транспортної мережі. Будь-яке транспортне підприємство, плануючи свою роботу на тривалий період T, як правило, намагається організувати роботу частини транспортних засобів із якоюсь періодичністю. Графіки з повторюваною структурою на інтервалах часу [(k — 1)T; kT], k = 1, 2,… будемо називати розкладом роботи транспортного засобу. Період Т може бути, наприклад, дорівнює 24 ч для роботи міського і приміського транспорту, тижню чи місяцю для роботи морських і річкових судів.

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

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

Показано, що задача оптимізації потоку транспортних засобів, що чинять дрібні перевезення, не мають ефективних точних алгоритмів рішення [3]. Застосування точних алгоритмів, заснованих на методах математичного програмування, для одержання чисельного рішення задач реальної розмірності надається практично неспроможним. Ці методи дозволяють вирішувати задача незначних розмірностей і мають головною уявою теоретичне значення. Тому для рішення задач маршрутизації й упорядкування графіків використовуються наближені й евристичні алгоритми.

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


    продолжение
--PAGE_BREAK--2.8 Математичні моделі, у яких враховується взаємозв'язок потоків


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

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

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

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

РОЗДІЛ 3 МАТЕМАТИЧНА МОДЕЛЬ ТРАНСПОРТНОЇ СИСТЕМИ ПІДПРИЄМСТВА 3.1 Структура моделі


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

На першому верхньому рівні знаходяться транспортні зв'язки підприємства із суміжниками і покупцями товару їм що випускається. На другому рівні міжцехові транспортні зв'язки. На третьому знаходяться внутрішньоцехові зв'язки. Крім того, рівні будуть пов'язані між собою окремими вертикальними зв'язками. Цю структурну схему можна уявити на рис.3.1.

При цьому на верхньому рівні, рівень А, рис.3.1, йде обмін по закупівлі і постачанню комплектуючих і постачанню продукції, що буде здійснюватися відповідно по трем потоках а1, а2.а3, далі другий рівень, рівень підприємства в целом- У, характеризується міжцеховими потоками: в1, в2, в3,...і в цьому випадку при наявності окремих підрозділів або цехів і нарешті на третьому рівні С, що веде роль грають внутрицеховые потоки деталей, заготівель, стружки і т.д., тобто, це потоки: c1, с2,… сm.


3.2 Математичний опис моделі


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

Для опису системи в цілому введемо залишкову функцію вантажопотоків — <img width=«21» height=«24» src=«ref-1_863155011-107.coolpic» v:shapes="_x0000_i1346">на обраному рівні як
<img width=«132» height=«49» src=«ref-1_863155118-391.coolpic» v:shapes="_x0000_i1347">, (67)
де

<img width=«24» height=«24» src=«ref-1_863155509-111.coolpic» v:shapes="_x0000_i1348">- вхідний вантажопотік;

<img width=«23» height=«25» src=«ref-1_863155620-107.coolpic» v:shapes="_x0000_i1349">- вихідний вантажопотік.

При цьому можна вважати, відповідно до робіт [1,2], що будуть справедливі такі співвідношення
<img width=«141» height=«41» src=«ref-1_863155727-377.coolpic» v:shapes="_x0000_i1350">, (68)
де

<img width=«16» height=«17» src=«ref-1_863156104-92.coolpic» v:shapes="_x0000_i1351">  — щільність вантажопотоку;

<img width=«13» height=«15» src=«ref-1_863156196-85.coolpic» v:shapes="_x0000_i1352">- швидкість переміщення вантажу у вантажопотоку.
Вираження (68) можна записати в іншому виді
<img width=«203» height=«44» src=«ref-1_863156281-560.coolpic» v:shapes="_x0000_i1353">.
Або для одномірного випадку
<img width=«132» height=«41» src=«ref-1_863156841-386.coolpic» v:shapes="_x0000_i1354">.
У одномірному випадку ми можемо одержати значення швидкості як

<img width=«89» height=«83» src=«ref-1_863157227-386.coolpic» v:shapes="_x0000_i1355">, (69)
де під <img width=«13» height=«15» src=«ref-1_863156196-85.coolpic» v:shapes="_x0000_i1356"> розуміється компонента швидкості в цьому ж напрямку.

Крім того, необхідно прийняти таке допущення, що буде справедливо співвідношення для цінового потенціалу <img width=«23» height=«19» src=«ref-1_863157698-101.coolpic» v:shapes="_x0000_i1357">:
<img width=«80» height=«21» src=«ref-1_863157799-172.coolpic» v:shapes="_x0000_i1358">, (70)
де

<img width=«13» height=«19» src=«ref-1_863157971-88.coolpic» v:shapes="_x0000_i1359">-коефіцієнт пропорційності;

Це співвідношення говорить про те, що вантажопотік потенційний.

Причому значення <img width=«23» height=«19» src=«ref-1_863157698-101.coolpic» v:shapes="_x0000_i1360"> може являти собою як ціновий потенціал, так потенціал організаційного типу.

У двумерном випадку можна записати, що справедливо вираження
<img width=«129» height=«48» src=«ref-1_863158160-375.coolpic» v:shapes="_x0000_i1361">.

При цьому, ограничившись одним виміром одержимо, що
<img width=«88» height=«44» src=«ref-1_863158535-260.coolpic» v:shapes="_x0000_i1362">

Одержимо, що справедливо вираження:
<img width=«109» height=«44» src=«ref-1_863158795-305.coolpic» v:shapes="_x0000_i1363">, (71)
де значення <img width=«31» height=«44» src=«ref-1_863159100-168.coolpic» v:shapes="_x0000_i1364"> може бути заздалегідь задане у виді функції або вираження.

<img width=«663» height=«257» src=«ref-1_863159268-5163.coolpic» v:shapes="_x0000_s1153">
<img width=«12» height=«23» src=«ref-1_863032857-73.coolpic» v:shapes="_x0000_i1365">

Рис3.2.- Залежність щільності <img width=«36» height=«21» src=«ref-1_863164504-128.coolpic» v:shapes="_x0000_i1366"> від координати за умови, що з=f(x4)
На Рис. 3.2. призводимо графік, що ілюструє цю залежність

У свою чергу графік зміна швидкості вантажопотоку, відповідно до вираження прийме вид, див. графік, рис.3.3.
<img width=«621» height=«255» src=«ref-1_863164632-5141.coolpic» v:shapes="_x0000_s1154">
Рис.3.3.- Графік, що фіксує зміну швидкості вантажопотоку <img width=«13» height=«15» src=«ref-1_863156196-85.coolpic» v:shapes="_x0000_i1367"> в залежності від координати <img width=«13» height=«15» src=«ref-1_863169858-84.coolpic» v:shapes="_x0000_i1368">або шляху при заданому законі зміни в залежності від часу
Функція швидкості асимптотична і швидко досягає свого граничного значення, рис.3.3.

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

Проте, рішення рівняння (70), називане звичайно диференціальним рівнянням фізики [2], викликає достатньо багато трудностей, можливість рішення рівнянь подібного типу пов'язано з можливістю поділу перемінних у спеціально обраних системах координат. У принципі рішення можна уявити у виді твори до, прикладу у виді:
<img width=«169» height=«28» src=«ref-1_863169942-581.coolpic» v:shapes="_x0000_i1369">.
У цьому випадку підстановка цього рішення в основне рівняння і проведення спеціальних процедур дозволяє одержати рішення, що влаштовує усіх.

Більш реально для пошуку рішення обмежитися одномірним випадком або застосувати, можливо, диференціювання по шляху.

Інший варіант рішення складається в тому, щоб задаватися простим вираженням, приміром, для <img width=«31» height=«44» src=«ref-1_863159100-168.coolpic» v:shapes="_x0000_i1370"> і потім знаходити рішення для <img width=«16» height=«17» src=«ref-1_863156104-92.coolpic» v:shapes="_x0000_i1371"> з рівняння (68).

Проте, підходом до рішення може бути таке, із рівняння (68) знаходиться значення <img width=«16» height=«17» src=«ref-1_863156104-92.coolpic» v:shapes="_x0000_i1372">, після чого це вираження подставляется в рівняння, що після ряду перетворень дозволяє одержати значення швидкості <img width=«13» height=«15» src=«ref-1_863156196-85.coolpic» v:shapes="_x0000_i1373"> реального вантажопотоку.

Крім того, відомо, що щільність вантажопотоку можна знайти по вираженню
<img width=«173» height=«52» src=«ref-1_863170960-457.coolpic» v:shapes="_x0000_i1374">,


де <img width=«69» height=«24» src=«ref-1_863171417-185.coolpic» v:shapes="_x0000_i1375">- фазова щільність;

<img width=«16» height=«17» src=«ref-1_863171602-90.coolpic» v:shapes="_x0000_i1376">- імпульс вантажу в потоку.

Імпульс вантажу у вантажопотоку являє собою не що інше як
<img width=«72» height=«24» src=«ref-1_863171692-168.coolpic» v:shapes="_x0000_i1377">,
де, у свою чергу <img width=«21» height=«24» src=«ref-1_863171860-103.coolpic» v:shapes="_x0000_i1378">- маса вантажу.

<img width=«13» height=«19» src=«ref-1_863171963-87.coolpic» v:shapes="_x0000_i1379">  — швидкість вантажу.

А масу вантажу, що проходить по вантажопотоку, можна визначити по такому вираженню
<img width=«189» height=«29» src=«ref-1_863172050-524.coolpic» v:shapes="_x0000_i1380">.
У цьому випадку, у загальному виді, ми маємо весь комплект рівнянь для визначення маси вантажопотоку і його швидкості.

Слід зазначити, що для вантажопотоків на рівні С будуть справедливі такі положення, описані на прикладі виробничої ділянки.

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


<img width=«407» height=«274» src=«ref-1_863172574-12640.coolpic» v:shapes="_x0000_s1155">
а- послідовна схема;

б- послідовна багаторівнева схема.

Рис.3.4.- Схеми розташування устаткування на ділянках ротаційного обкатування
Інший варіант розташування устаткування, аналогічний роторному або кільцевому принципу розташування, мал.3.5.
<img width=«255» height=«205» src=«ref-1_863185214-6502.coolpic» v:shapes="_x0000_s1156">
Рис 3.5.- Роторний або кільцевий принцип розміщення устаткування.
Кожній із схем розташування устаткування властиві ті або інші хиби, схема мал.3.6 а, у випадку недовантаження ділянки, дозволяє резервувати устаткування для планово-попереджувальних ремонтів. У свою чергу схема, рис3.2., кільцевого типу передбачає рівномірне завантаження устаткування з необхідністю вимикання однієї з одиниць перекиданням виробничого навантаження на що залишилися.
<img width=«367» height=«182» src=«ref-1_863191716-5523.coolpic» v:shapes="_x0000_i1381"> 

Рис 3.6- Графи, що відповідають схемам компонування ділянки ротаційного обкатування
Схема рис.3.6, б, передбачає регулювання навантаження на устаткування і вона використовується з відносної невеличкою «багатоповерховістю» при проектуванні устаткування різноманітними фірмами.

Можна зіставити приведеним схемам графи, показані на рис.3.6.

а, б, в- графи компонування, що відповідають поданим схемам компонування

У цьому випадку, як приведено в літературі, у матричній формі, рівняння поперечних і подовжніх перемінних будуть мати вид:
<img width=«64» height=«24» src=«ref-1_863197239-168.coolpic» v:shapes="_x0000_i1382">
щодо подовжніх перемінних
<img width=«68» height=«24» src=«ref-1_863197407-168.coolpic» v:shapes="_x0000_i1383">
де <img width=«17» height=«24» src=«ref-1_863197575-100.coolpic» v:shapes="_x0000_i1384"> і <img width=«21» height=«24» src=«ref-1_863197675-103.coolpic» v:shapes="_x0000_i1385"> квадратні матриці m-ого порядку.

У досліджуваній задачі, якості вхідної поперечної перемінної приймаємо інтенсивність потоку заготівель — <img width=«16» height=«24» src=«ref-1_863197778-94.coolpic» v:shapes="_x0000_i1386"> після опрацювання на давильном устаткуванні. У свою чергу, у якості подовжньої перемінної, приймаємо <img width=«19» height=«24» src=«ref-1_863197872-103.coolpic» v:shapes="_x0000_i1387">- інтенсивність потоку під опрацювання на ротаційно-обкатаному устаткуванні.

У окремому випадку, зв'язок між поперечної і подовжньої перемінною може бути отримана у виді вираження
<img width=«139» height=«25» src=«ref-1_863197975-271.coolpic» v:shapes="_x0000_i1388">, (72)
де

<img width=«21» height=«24» src=«ref-1_863198246-103.coolpic» v:shapes="_x0000_i1389">-інтенсивність потоку заготівель до <img width=«9» height=«17» src=«ref-1_863198349-80.coolpic» v:shapes="_x0000_i1390">-ой одиниці устаткування;

<img width=«17» height=«17» src=«ref-1_863198429-91.coolpic» v:shapes="_x0000_i1391">- комплексний показник технологічного процесу, реалізованого на встановленому устаткуванні;

<img width=«16» height=«17» src=«ref-1_863198520-91.coolpic» v:shapes="_x0000_i1392">- комплексний показник технічного рівня устаткування;

<img width=«16» height=«17» src=«ref-1_863171602-90.coolpic» v:shapes="_x0000_i1393"> і <img width=«12» height=«13» src=«ref-1_863198701-82.coolpic» v:shapes="_x0000_i1394">- технологічні параметри системи.

Проте вираження (72) являє собою загальний випадок.

Дослідження простих моделей ділянок, показало, що для достатньо ефективного наближенням може бути використання виражень типу:
<img width=«107» height=«37» src=«ref-1_863198783-255.coolpic» v:shapes="_x0000_i1395"> (73)
де

<img width=«12» height=«15» src=«ref-1_863199038-83.coolpic» v:shapes="_x0000_i1396">- параметр устаткування, причому <img width=«36» height=«19» src=«ref-1_863199121-114.coolpic» v:shapes="_x0000_i1397"> і <img width=«65» height=«19» src=«ref-1_863199235-146.coolpic» v:shapes="_x0000_i1398">.

Тоді, продуктивність ділянки може бути знайдена по вираженню
<img width=«67» height=«45» src=«ref-1_863199381-301.coolpic» v:shapes="_x0000_i1399">
Приведене вираження справедливо для всіх трьох випадків гаданого компонування ділянок, мал.4,5.

Причому для різноманітних схем воно одержить різноманітний вид.

У першому випадку його форма будет такой
<img width=«213» height=«64» src=«ref-1_863199682-750.coolpic» v:shapes="_x0000_i1400">
В другому випадку, вираження получит аналогічну форму
<img width=«216» height=«83» src=«ref-1_863200432-833.coolpic» v:shapes="_x0000_i1401">
де

<img width=«17» height=«15» src=«ref-1_863201265-88.coolpic» v:shapes="_x0000_i1402">- число верстатів.

Проте, у третьому випадку вираження для продуктивності буде иметь вид
<img width=«71» height=«24» src=«ref-1_863201353-172.coolpic» v:shapes="_x0000_i1403">
де

<img width=«16» height=«24» src=«ref-1_863201525-94.coolpic» v:shapes="_x0000_i1404">- інтенсивність вихідного потоку може бути знайдене з вираження (73 );

<img width=«17» height=«15» src=«ref-1_863201265-88.coolpic» v:shapes="_x0000_i1405">- число верстатів.

Або
<img width=«140» height=«36» src=«ref-1_863201707-311.coolpic» v:shapes="_x0000_i1406">.
Це вираження можна ілюструвати графіками, поданими на мал.3.7,8

<img width=«384» height=«192» src=«ref-1_863202018-5125.coolpic» v:shapes="_x0000_i1407">

Рис. 3.7- Графік залежності продуктивності П від інтенсивності вхідного потоку <img width=«16» height=«21» src=«ref-1_863207143-98.coolpic» v:shapes="_x0000_i1408"> і параметра технологічної системы- s, при числі верстатів <img width=«17» height=«15» src=«ref-1_863201265-88.coolpic» v:shapes="_x0000_i1409">= 4 значеннях комплексних показників <img width=«17» height=«17» src=«ref-1_863198429-91.coolpic» v:shapes="_x0000_i1410">= 5, <img width=«16» height=«17» src=«ref-1_863198520-91.coolpic» v:shapes="_x0000_i1411">= 10
<img width=«468» height=«167» src=«ref-1_863207511-4810.coolpic» v:shapes="_x0000_i1412">

Рис. 3.8- Графік залежності продуктивності П від інтенсивності вхідного потоку <img width=«16» height=«21» src=«ref-1_863207143-98.coolpic» v:shapes="_x0000_i1413"> і числі верстатів <img width=«17» height=«15» src=«ref-1_863201265-88.coolpic» v:shapes="_x0000_i1414">, при значеннях <img width=«12» height=«15» src=«ref-1_863199038-83.coolpic» v:shapes="_x0000_i1415">= 2 і комплексних показниках <img width=«17» height=«17» src=«ref-1_863198429-91.coolpic» v:shapes="_x0000_i1416">= 5,<img width=«16» height=«17» src=«ref-1_863198520-91.coolpic» v:shapes="_x0000_i1417"> = 10
Графік ілюструє ріст продуктивності з характерним максимумом при рості параметра, що характеризує технологічну систему.

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

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

Проте, оптимізація роботи ділянки може здійснюватися по декількох критеріях.

Таким чином, оптимізація рішення зводиться до оптимізацію вираження
<img width=«157» height=«45» src=«ref-1_863212772-482.coolpic» v:shapes="_x0000_i1418">
Оптимізація вираження може бути ефективно виконана за допомогою інструментів «Mathcad-8», «Optimization» або «Matlab », інструментарій «Optimization».


    продолжение
--PAGE_BREAK--3.3 Аналіз математичної моделі


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

Залежність розміру вантажопотоку від швидкості <img width=«13» height=«15» src=«ref-1_863156196-85.coolpic» v:shapes="_x0000_i1419"> буде відбита на графіку рис.3.10.

<img width=«595» height=«258» src=«ref-1_863213339-4312.coolpic» v:shapes="_x0000_s1157">
І на графіку, рис.3.11, приведена залежність розміру вантажопотоку від цінового потенціалу.
Для побудови імітаційної моделі необхідно скористатися такими рівняннями.

У випадку рівня А, мал.1, ми одержимо такий комплект рівнянь:
<img width=«132» height=«49» src=«ref-1_863155118-391.coolpic» v:shapes="_x0000_i1420">;

……………………

<img width=«160» height=«29» src=«ref-1_863218042-465.coolpic» v:shapes="_x0000_i1421">

……………………;

<img width=«157» height=«29» src=«ref-1_863218507-453.coolpic» v:shapes="_x0000_i1422">;

……………………;
Для рівня У система рівнянь висловиться в такий спосіб:
<img width=«132» height=«49» src=«ref-1_863155118-391.coolpic» v:shapes="_x0000_i1423">;

<img width=«160» height=«29» src=«ref-1_863219351-469.coolpic» v:shapes="_x0000_i1424">;

<img width=«161» height=«29» src=«ref-1_863219820-471.coolpic» v:shapes="_x0000_i1425">;

<img width=«157» height=«29» src=«ref-1_863220291-457.coolpic» v:shapes="_x0000_i1426">;

<img width=«157» height=«29» src=«ref-1_863220291-457.coolpic» v:shapes="_x0000_i1427">;

<img width=«189» height=«29» src=«ref-1_863172050-524.coolpic» v:shapes="_x0000_i1428">.
Для рівня С система основних рівнянь прийме вид:
<img width=«132» height=«49» src=«ref-1_863155118-391.coolpic» v:shapes="_x0000_i1429">

<img width=«189» height=«29» src=«ref-1_863172050-524.coolpic» v:shapes="_x0000_i1430">;

<img width=«160» height=«29» src=«ref-1_863219351-469.coolpic» v:shapes="_x0000_i1431">;

<img width=«161» height=«29» src=«ref-1_863219820-471.coolpic» v:shapes="_x0000_i1432">;

<img width=«157» height=«29» src=«ref-1_863220291-457.coolpic» v:shapes="_x0000_i1433">;

<img width=«157» height=«29» src=«ref-1_863220291-457.coolpic» v:shapes="_x0000_i1434">;

<img width=«189» height=«29» src=«ref-1_863172050-524.coolpic» v:shapes="_x0000_i1435">.
Крім того, на системи рівнянь повинні бути накладені групи обмежень, що характеризують технічні можливості транспортних систем різноманітного рівня. Крім того, аналогічні обмеження, що стосуються технічних можливостей транспорту, накладаються і на міжрівневий транспорт.

Призводимо ці обмеження.
<img width=«56» height=«24» src=«ref-1_863225022-145.coolpic» v:shapes="_x0000_i1436">- обмеження по швидкості прямування;

<img width=«57» height=«24» src=«ref-1_863225167-156.coolpic» v:shapes="_x0000_i1437">- обмеження на пропускну спроможність
Останнє, що дозволяє дати замкнуте рішення, ця наявність рівнянь зв'язку між різноманітними рівнями транспортної системи підприємства. Вони можуть бути виражені у виді рівнянь балансу типу:
<img width=«132» height=«49» src=«ref-1_863155118-391.coolpic» v:shapes="_x0000_i1438">
У поділі присвяченій розробці імітаційної моделі призводимо результати, що характеризують обрані транспортні потоки з заданими параметрами.

РОЗДІЛ 4 ПОБУДОВА ІМІТАЦІЙНОЇ МОДЕЛІ ТРАНСПОРТНОЇ СИСТЕМИ


Для побудови імітаційної моделі скористаємося системою імітаційного моделювання «Stratum- 2000», розробленої в однім із головних російських університетів.

У моделюючому середовищі Стратум застосовані багато передових технологій — D&D, гипер, видимості периферії, відкритості dll, мультимедиа, 3D, анімація, ієрархія, инструментальність, пряме відео, мережа, об'єктне проектування, стандартний обмін Windows.


4.1 Основні властивості середовища проектування


D&D-технологія.

Зображення об'єкта може знаходитися у визначених координатах у вікні. Їхнє значення зберігається в перемінних Org і Org. Якщо на поле схеми встановлений імідж Drag&Drop, те вказівка і захоплення мишкою графічного об'єкта, що має ім'я, призведе до керування відповідними координатами. Таким чином, якщо схема використовує значення перемінних Org і Org, те можна маніпулювати віртуальним світом об'єктів на екрані, впливаючи на їхні властивості, модель.

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

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

Ієрархія.

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

Інструментальність.

Середовище припускає, що вам даються інструменти. Задачу або проект необхідний вам ви виготовте їх за допомогою самостійно. Середовище не є автоматизованим робочим місцем, не алгоритмізує окрему задачу, але сприяє написанню таких продуктів. У порівнянні з відомими інструментальними засобами (FoxPro, Paint, 3DMax і іншими) середовище:

1. об'єднує усі види уявлення інформації в однім продукті (можливість використовувати інші редактори залишається, тому що підтримується Windows стандарт) — музика, зображення (растровое, об'єктне), бази даних, моделі, зображення, відео, і так далі;

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

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

4. середовище є відкритої, для користувачів із кваліфікацією програміста даються мовна нотація;

5. середовище реалізує об'єктний принцип проектування і сама є системою проектування.

Об'єктне проектування.

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

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


    продолжение
--PAGE_BREAK--