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

АНОТАЦІЯ

104 стор., 27 рис., 4 табл., 20 літер. джерел.

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

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

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

Ключьові слова: ТРАНСПОРТНА СИСТЕМА, ЦІНОВИЙ ПОТЕНЦІАЛ, ЩІЛЬНІСТЬ ВАНТАЖОПОТОКУ, ТРАНСПОРТНІ МЕРЕЖІ.

ЗМІСТ

• ВСТУП
• РОЗДІЛ 1. АНАЛІЗ ТРАНСПОРТНИХ СИСТЕМ ТА ІХ МОДЕЛЮВАННЯ
• 1.1 Керування транспортною системою
• 1.1.1.Характеристика транспорту як об'єкту керуваня
• 1.1.2 Моделювання транспортної системи
• РОЗДІЛ 2. Транспортні потоки, планування та оптимізація
• 2.1 Задачі планування незалежних транспортних потоків
• 2.2 Узагальнені задачі про потоки
• 2.3 Багатопродуктові потоки
• 2.4 Задача планування перевезень як задача оптимізації взаємозалежних потоків на мережі
• 2.5 Двохрівнева система моделей планувания транспортних потоків
• 2.6 Модель нижнього рівня — оптимізація транспортних потоків на транспортних мережах окремих видів транспорту
• 2.7 Основні задачі оптимізації транспортних потоків
• 2.8 Математичні моделі, у яких враховується взаємозв'язок потоків
• РОЗДІЛ 3 МАТЕМАТИЧНА МОДЕЛЬ ТРАНСПОРТНОЇ СИСТЕМИ ПІДПРИЄМСТВА
• 3.1 Структура моделі
• 3.2 Математичний опис моделі
• 3.3 Аналіз математичної моделі
• РОЗДІЛ 4 ПОБУДОВА ІМІТАЦІЙНОЇ МОДЕЛІ ТРАНСПОРТНОЇ СИСТЕМИ
• 4.1 Основні властивості середовища проектування
• 4.2 Побудова імітаційної моделі
• 4.3 Аналіз результатів прогону імітаційної моделі
• ВИСНОВКИ
• СПИСОК ЛІТЕРАТУРИ

ВСТУП

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

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

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

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

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

РОЗДІЛ 1. АНАЛІЗ ТРАНСПОРТНИХ СИСТЕМ ТА ІХ МОДЕЛЮВАННЯ

1.1 Керування транспортною системою

1.1.1 Характеристика транспорту як об'єкту керування

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

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

1. У процесі свого функціонування транспортна система не створює нового матеріального продукту, її продукцією є самий процес переміщення вантажів і пасажирів.

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

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

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

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

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

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

До числа загальнотраснпортних задач, що повинні вирішуватися цією системою, ставляться:

забезпечення взаємообміну АСУ різноманітних видів транспорту координація діяльності і розвитки різноманітних видів транспорту;

оптимальний розподіл вантажопотоків між різними видами транспорту;

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

ув’язування планів перевезення і перевалювання вантажів різноманітними видами транспорту;

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

забеспечення взаємообміну АСУ різноманітних видів транспорту уніфікованою інформацією про роботу суміжних видів транспорту.

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

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

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

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

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

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

До числа основних із цих задач ставляться:

розподіл вантажопотоків між видами транспорту;

розподіл обсягів перевезень між виробничими підприємствами усередині кожного виду транспорту;

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

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

1.1.2 Моделювання транспортної системи

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

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

Для зображення вершин (або вузлів) орієнтованих і неорієнотованих дуг використовуються відповідно кружки, лінії зі стрілками і лінії без стрілк. У більшості випадків можна замінити одну неориєнтовану дугу двома орієнтованими і напроти спрямованими дугами. У зв’язку з розподілом єдиної транспортної системи України на підсистеми, що відповідають окремим видам транспорту, транспортна мережа G (К, А) розпадається на ряд окремих підмереж G^м (К^м, А^м), що обслуговуються різноманітними видами транспорту М = 1,…,. Ці підмережі мають загальні вершини, що подають транспортні вузли, у яких відбувається перевалювання вантажів з одного виду транспорту на інший. Для зручності побудови моделей планування перевезень вантажів кожний вузол реальної транспортної мережі, у якому відбувається взаємодія декількох видів транспорту, можна уявити в графі G (K, А) у виді декількох вершин, кожна з який відповідає виду транспорту. Ці вершини сполучені між собою парою напроти орієнтованих дуг, що означають перевалювання вантажів з одного виду транспорту на інший. Як приклад на рис. 1.1, а приведена схема загально транспортного вузла, у якому взаємодіють три види транспорту (залізничний, автомобільний і річковий), на рис. 1.1, б — його уявлення в мережі G (K, А), де можливе перевалювання вантажів позначений штриховими стрілками.

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

Приклад фрагмента мережі G (K, А) для трьох видів транспорту приведений на рис. 1.2. Вершини, у яких зароджуються транспортні потоки, називаються «джерелами», а вершини, у яких вони поглинаються, — «стоками». Окремі об'єкти, що переміщаються, або «протікають», із пунктів зародження транспортних потоків у пункти їхній поглинання, називаються «одиницями потоку». Будемо використовувати символ для позначення вершини i = 1,…, n «графа G (K, А) і символ (i, j) А для позначення орієнтованої дуги, що веде з, до -. Упорядкована послідовність вершин і спрямованих дуг мережі (1, 2),, (2, 3),…,, (n-1, n), така, що кінець попередньої дуги є початком наступної, називається шляхом (або маршрутом), що веде з вершини у вершину. При послідовність називається орієнтованим циклом або кільцевим маршрутом. Якщо будь-які дві вершини мережі можна з'єднати шляхом, те мережа називається зв`язаною. Якщо мережа не є зв`язаною, те її можна розбити на зв’язкові підмережі або компоненти зв`язані. Прикладом незв’язної транспортної мережі може служити підсікти шляхів повідомлень річкового транспорту, що складає з декількох не з`єднаних річкових басейнів.

Рис 1.2 Фрагмент мережі

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

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

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

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

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

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

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

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

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

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

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

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

вантажів;

пасажирів;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

j? s, t

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

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

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

Таблиця.2-Тривалість обчислень

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

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

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

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

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

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

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

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

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

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

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

j=2,3,…, n;u_j=0

У результаті розрахунків знаходиться (якщо воно існує) дерево найкоротших відстаней із коренем у вершині 1, у якому довжина єдиного шляху з 1 у j дорівнює uj, j=2, 3,…, п.

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

Крок 0. Покласти

S={1,2,3…, n}

Крок 1. Знайти, для котрого =, якщо uk =+ - стіп; не існує шляху у вершини, що залишилася в S. Положимо S = S — {k}. Якщо S = - стіп; обчислення закінчені.

Крок 2. Покласти = min{} для всіх (k, j) Е. Перейти до кроку 1.

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

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

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

Нехай uj^(k) — довжина найкоротшого шляху від вихідної вершини до вершини j за умови, що шлях містить не більш ніж k дуг. Спочатку положимо Тоді та. Для дуг k = 2, 3,…, n- 1 необхідно 0 (n) ітерацій. Кожна ітерація потребує 0 (m) операцій. Отже, метод потребує 0 (т п) операцій. Зауважимо, що для плоских графів потрібно 0 () операцій.

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

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

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

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

Нехай мережа G (V, Е) складається з неорієнтованих дуг і ми хочемо знайти найкоротший шлях між двома визначеними вершинами. Якщо всі довжини дуг невід'ємних, те можна замінити кожну неорієнтованих дугу парою симетричних орієнтованих дуг (i, j) і (j, i) із і застосувати будь-який із зазначених вище алгоритмів.

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

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

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

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

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

Будемо вважати, що якщо в будь-яку дугу (i, j) Е з вершини i виходить одиниць потоку, то з цієї дуги у вершину j увійде одиниць потоку. Розмір має назву коефіцієнта підсилення або просто посиленням дуги (i, j).

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

Узагальнена задача про транспортний потік мінімальної вартості на мережі G (V, Е) може бути сформульована як задача лінійного програмування такого виду:

де vs — чистий вхідної потік у s, а vt — чистий вихідний потік із t.

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

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

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

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

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

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

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

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

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

2.3 Багатопродуктові потоки

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

Розмір потоку k-го продукту по дузі (i, j) Е визначимо через, а вартість переміщення одиниці k-го продукту по дузі (i, j) — через (k = 1,2,…, K).

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

Задача про багатопродуктовий потік мінімальної вартості складається в тому, щоб знайти такі значення (i, j) Е, k = 1, 2,…К щоб

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

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

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

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

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

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

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

Задано спрямованого графа без петель G (K, А), де K — множина вершин, А — множина дуг, що складається з підграфів пов’язаних загальними вершинами .

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

Повторний потік Первинний потік

1-й тип

2-й тип

3-й тип

1-й тип

2-й тип

3-й тип Рис. 2.1-Первинний і вторинний потоки Потоки не є однорідними: на графі може існувати видів повторного потоку і типів первинного потоку. При цьому повторний потік може протікати від джерел до стоків будь-якими припустимими шляхами, тоді як кожний тип первинного потоку може існувати лише на визначеному підграфі (відповідно до цого всі типи первинного потоку 1,…, розділені на групи, М = невзаємозамінює типів).

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

Первинний потік m-го типу по дузі (i, j), М =, складається з потоків «активної» і «пасивної» складових:

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

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

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

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

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

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

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

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

На відміну від задачі (5) — (11) припускається лише часткове перетворення потоків різноманітних типів продуктів і без їхнього посилення або ослаблення: відмінні від нуля і рівні одиниці лише ті з коефіцієнтів перетворення, що зв’язують активну і пасивну складові того самого типу первинного потоку. Ці складові можуть переходити друг у друга у вершинах, наприклад на початку і по закінченні робіт (зокрема, при навантаженні і розвантаженні потік порожніх транспортних засобів перетворюється в потік навантажених і навпаки) або при зміні одних ресурсів на інші (зокрема, при перевалюванні вантажів із транспортних засобів одного типу на транспортні засоби іншого типу).

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

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

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

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

Максимізувати

(3)

(де — корисний ефект від переміщення одиниці повторного потоку і витрати на переміщення одиниці первинного потоку m-ого типу по дугах (i, j) A графа) при виконанні звичайних умов зберігання кожного з потоків, що проходять через вершину i графа:

(6)

де , — попит і пропозиції для первинного і повторного потоків Ks₊^I, Ks-I, Ks₊^II і Ks-II — джерела і стоки для первинного і повторного потоків відповідно, а також обмежень на пропускну спроможність дуг

(8)

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

(9)

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

(10)

Крім того, повинні виконуватися умови невід'ємності

. (11)

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

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

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

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

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

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

Задано спрямованого графа G (К, А), що подає єдину транспортну мережу і складається з декількох подграфов окремих видів, що подають транспортні мережі окремих видів транспорту транспорту (рис. 2.2). Дуги графа подають можливі шляхи переміщення транспортних засобів, а вершини — пункти i відправлення і призначення вантажів, пункти i перевалювання вантажів і транзитні пункти .

Рис 2.2-Транспортні мережі окремих видів транспорту транспорту

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

(12)

де =, (13)

— обсяг вантажів n-го роду, що перевалюються в i-м пункті з L,-го виду транспорту на M-й у t-м періоді.

У перевезенні вантажів між пунктами i і j M-м видом транспорту можуть брати участь різноманітні типи транспортних засобів т моючих різну вантажопідіймальність bтп:

(14)

де — кількість вантажів п-го роду, перевезених M-м видом транспорту в t-й період, — кількість транспортних засобів m-го виду, що перевозять вантажі n-го роду в t-й період.

Потік транспортних засобів m-го типу по дузі ділиться па потік навантажених і порожніх транспортних засобів

(15)

Кількість транспортних засобів m-го типу, що починають або закінчують роботу в різноманітних вузлах i транспортної мережі у період t, дорівнює плановому обсягу запровадження і висновка їх з експлуатації в аналізованому плановому періоді :

(16)

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

Для кожного вузла i транспортної мережі виконуються умови зберігання минущого через нього потоку вантажів у кожний період часу t (t =):

(17)

— для пунктів відправлення-призначення, загальних для транспортних мереж декількох видів транспорту (- обсяг вивозу надпланових вантажів M-м видом транспорту в періоді t);

(18)

— для інших пунктів відправлення-призначення;

(19)

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

(20)

— для інших вузлів транспортної мережі.

Аналоггічною уявою для кожного вузла i виконуються умови зберігання потоків навантажених і порожніх транспортних засобів кожного типу т, М = у період t (t =):

а) навантажені транспортні засоби

(21)

для пунктів, у яких відбувається навантаження-розаантаження (кількість транспортних засобів із вантажем n-го роду, що завантажуються і що розвантажуються в період t у пункті i);

(22)

для інших пунктів ;

б) порожні транспортні засоби

. (23)

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