/>АНОТАЦІЯ
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.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),…,(in-1,in);in≡t...
Однорідним транспортнимпотоком у мережі G (V, Е) називається множина чисел xij, таких, що
/> j ≠ s,t
/>
Кількість потоку, щовиходять із джерела або входять у стік,
/>
Під задачею промаксимальний потік розуміється задача пошуку в G (V, Е) потоку максимальногорозміру v, що протікає з s у t.
Існує багаторізноманітних алгоритмів пошуку максимального потоку. Найбільше поширені з нихперераховані в табл. 1 із указівкою джерела й оцінки числа операцій. Уявленняпро тривалість обчислень можна одержати з табл..2 [10]
Таблиця.1-Алгоритмипошуку максимального потокуАвтор алгоритму Помилка в загальному випадку m=n m=n2 k=m+n
Форд-Фалкенсон
Эдмонс-Карп
Диниц
Карзанов
Черкаський
Галил
[4]
[5]
[6]
[7]
[8]
[9]
0(vm)
0(/>)
0(/>)
0(/>)
0(/>)
0(/>)
0(/>)
0(/>)
0(/>)
0(/>)
0(/>)
0(/>)
0(/>)
0(/>)
0(/>)
0(/>)
0(/>)
0(/>)
0(/>)
0(/>)
0(/>)
Таблиця.2-ТривалістьобчисленьЧисло вершин
Число
дуг Алгоритм Форда-Фалкенсона, модифікація Эдмонса-Карпа, c Алгоритм Диница, c Алгоритм Карзанова, c Алгоритм Черкаського, c
100
200
300
400
500
600
700
800
900
1000
500
1000
1500
2000
2500
3000
3500
4000
4500
5000
17,0
68,3
154,7
285,1
-
-
-
-
-
-
4,2
9,6
14,3
20,0
24,9
41,0
41,7
46,7
57,3
54,5
5,3
11,8
17,7
24,8
30,0
48,0
50,9
59,6
69,7
66,9
2,7
7,4
9,4
14,7
22,7
14,1
24,5
34,5
38,4
43,5 /> /> /> /> /> /> />
Більш загальною задачеюоптимізації однорідного транспортного потоку є задача пошуку такого потоку натранспортній мережі, витрати на переміщення якого є мінімальними. До задачіподібного роду зводяться, наприклад, задача визначення обсягів і шляхівдоставки вантажів із пунктів відправлення в пункти призначення, що забезпечуютьмінімум транспортних витрат, а також задача визначення маршрутів прямування ікількості, використовуваних транспортних засобів, при яких загальніексплуатаційні витрати на одну перевізку вантажів мінімальні.
Відмінність даної задачівід попередньої полягає в тому, що для кожної дуги (i,j) /> Е задана вартість /> переміщенняодиниці транспортного потоку і необхідно знайти потік заданого розміру v ізджерела s у стік t, що мінімізує зважену суму потоків
Для рішення цієї задачізапропонована множина різноманітних алгоритмів і їхніх узагальнень. Серед. нихалгоритми, засновані на застосуванні прямих і двоїстих симплекс-алгоритмівлінійного програмування й алгоритмів пошуку найкоротших шляхів. Одним ізпоширених алгоритмів є так називаний алгоритм дефекту [4], що дозволяєвирішувати задач про потік мінімальної вартості достатньо загального виду.Число операцій алгоритму дефекту оцінюється як 0(/>), де число К0,обумовлене на перших ітераціях алгоритму, не перевищує />, п — число вершин мережі, т — число її дуг, а
/>
Очевидно, можна замість0(/>)використовувати оцінку 0(/>). У [5] запропонована модифікаціяалгоритму дефекту з оцінкою числа операцій 0 (/>).
Алгоритми пошуку потокумінімальної вартості застосовуються для рішення задач у дуже великих мережах. Уроботах [11, 12] повідомляється про рішення прямими алгоритмами задач із 20000вершин 450 000 дуг, а в [13] — про рішення однієї задачі з 3000 вершин і 35 000дуг за 97 с на IВМ-360/67 і іншої задачі з 5000 вершин та 15 000 дуг за 113 с.
Пошук найкоротших шляхів.Окремими випадками задачі про транспортний потік мінімальної вартості, щоподають і самостійний інтерес, є задача перебування найкоротшого шляху міждвома пунктами транспортної сети G (V, Е) і задача пошуку маршруту, щозабезпечує мінімальний час переміщення транспортного потоку. Довжиною шляху єсума довжин дуг, що входять у нього.
Кожній дузі (i, j) мережіпоставлена у відповідність її довжина />, або тривалість проходженняодиниці транспортного потоку, що у загальному випадку може бути позитивним інегативним числом.
У ряді відомих алгоритмівробиться додаткове припущення про те, що G (V, Е) не містить циклів негативноїдовжини.
Очевидно, що якщо вджерело помістити одиницю потоку, а в стік одиничний попит, пропускніспроможності всіх дуг вважати безкінечними і відшукувати припустимий потікмінімальної вартості (за умови, що lij — вартість переміщення потоку), те,розв'язавши задачу про потік мінімальної вартості, знайдемо найкоротший шляхпрямування цієї одиниці.
Проте у розрахунковомувідношенні більш ефективними виявилися спеціальні, так називані комбінаторніалгоритми, аналізовані в даному розділі. У цих алгоритмах вихідні дані подані увиді списків дуг, тобто для кожної вершини дається список тих дуг (i, j), щоінцидентні їй, разом із їхніми довжинами />. Оцінки числа операцій алгоритмівприведені в табл. 3.Спочатку роздивимося основні алгоритми рішення задачіпошуку найкоротшого шляху між двома вершинами: 1 (джерело) і п (стік).
Таблиця 3 — Оцінки числа операційалгоритмівАвтор алгоритму Оцінка числа операцій Автор алгоритму Оцінка числа операцій Найкоротший шлях між двома вершинами Найкоротші шляхи між усіма парами вершин
Беллман [14]
Дийкстра [15]
Беллман-Форд [16]
0(n2)
0(m log n)
0(m n)
Дийкстра [17]
Спира [18]
Флойд-Варшал [19,20]
Фридман [21]
0(mn log n)
0(n2(log n)2)
0(n2)
0(n)2,5 /> /> /> /> />
Метод Белмана.Скористаємося рівнянням Белмана для визначення найкоротшого шляху між вершинами1 і n. Визначимо /> - довжину найкоротшого шляху звихідної вершини 1 у вершину j за умови, що вершини пронумеровані числами 1, 2,3,..., п. Шлях найкоротшої довжини знаходиться з такого рівняння:
/>j=2,3,…,n;uj=0
У результаті розрахунківзнаходиться (якщо воно існує) дерево найкоротших відстаней із коренем у вершині1, у якому довжина єдиного шляху з 1 у j дорівнює uj, j=2, 3,..., п.
Алгоритми Дийкстра.Роздивимося мережу G (V, Е), у котрої довжини lijусіх дугпозитивні. Тоді відомий алгоритм Дийкстра може бути записаний у такий спосіб.
Крок0. Покласти
/>
якщо (i,j)
у іншому випадку, />
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
Метод Белмана — Форда.Роздивимося мережу G (V, Е), у котрої або відсутні цикли, або довжини дугненегативні. Метод послідовних наближень, запропонований Белманом і Фордом,складається в такому.
Нехай uj(k) — довжина найкоротшого шляху від вихідної вершини до вершини j за умови, що шляхмістить не більш ніж k дуг. Спочатку положимо
/>
Тоді /> та />. Для дуг k = 2,3,...,n- 1 необхідно 0 (n) ітерацій. Кожна ітерація потребує 0 (m) операцій.Отже, метод потребує 0 (т п) операцій. Зауважимо, що для плоских графівпотрібно 0 (/>)операцій.
Він [17] запропонувавмодифікацію цього методу, що скорочує загальне число додавань і порівняньприблизно в чотирьох разу у випадку повної мережі й у два рази в довільномувипадку.
Задача визначеннянайкоротших шляхів між усіма парами вершин. Більш загальною задачею про пошукнайкоротших шляхів є задача визначення найкоротших маршрутів або шляхівякнайшвидшої доставки вантажів між усіма парами вузлів транспортної мережі.
Не розглядаючи кожний залгоритмів пошуку найкоротших шляхів, приведених у табл. 3, опишемо ідеї їхньоїпобудови.
Будемо шукати найкоротшішляхи між вершинами в мережі з позитивними і негативними довжинами дуг,починаючи з вершини 1. Очевидно, буде потрібно 0 (тп) обчислень для того, щобзнайти найкоротші шляхи з вершини 1 у всі інші вершини. Замінимо довжину кожноїдуги /> на />. Довжинашляху з i у j, визначена за значеннями />, відрізняється від щирої довжинина константу />. Отже, рішення задачі визначеннявсіх найкоротших пар шляхів із довжинами /> є рішенням вихідної задачі. Оскількитепер усі довжини дуг невід’ємних, можна застосувати метод Дийкстра для кожнійз останніх п — 1 задач. У результаті вся задача буде вирішена за 0 (/>) операцій, адля плоского графа за 0 (/>) операцій. У [18] запропонованийалгоритм для невід’ємних дуг мережі G (V, Е), у якому очікуване число обчисленьдорівнює 0 (/>).
Нехай мережа G (V, Е)складається з неорієнтованих дуг і ми хочемо знайти найкоротший шлях між двомавизначеними вершинами. Якщо всі довжини дуг невід’ємних, те можна замінитикожну неорієнтованих дугу парою симетричних орієнтованих дуг (i,j) і (j, i) із />і застосуватибудь-який із зазначених вище алгоритмів.
Проте якщо довжина дуги(i,j) негативний, те цей підхід нездатний, тому що в мережі з'явитьсянегативний цикл (i,j), (j, i)
У загальному випадкуможна скористатися, наприклад, методом Белмана- Форда для визначення існуванняциклу негативної довжини в G (V, Е). Якщо мережа є сильнозв`язною, то циклнегативної довжини існує тоді і тільки тоді, коли uj(n) />2.2 Узагальнені задачі про потоки
У розглянутих вищезадачах передбачалося, що однорідний транспортний потік, що виходить із дуги(i, j) /> Е,дорівнює потокові, що входить у цю дугу. Проте в ряді практичних ситуацій цеприпущення не виконується. Наприклад, при транспортуванні вантажів можевідбуватися їхнє псування або втрата (наприклад, вивітрювання), що призводитьдо зменшення потоку під час його переміщення по дузі (i, j) транспортної мережіG (V, Е).
Тому для рішення подібнихзадач необхідно відмовитися від припущення, відповідно до якого при проходженніпо дугах мережі G (V, Е) потік залишається незмінним, і припустити, щокількість однорідного потоку, що проходить по дузі, може збільшуватися абозменшуватися.
Будемо вважати, що якщо вбудь-яку дугу (i, j) /> Е з вершини i виходить /> одиницьпотоку, то з цієї дуги у вершину j увійде />одиниць потоку. Розмір /> має назвукоефіцієнта підсилення або просто посиленням дуги (i, j).
Якщо /> > 1, то потік подузі (i, j) посилюється. Якщо/>= 1, то потік по дузі (i, j)залишається незмінним. Якщо 0 = 0, то потік по дузі (i, j)губиться (поглинається цілком) і дана дуга звичайно розглядається як стік. Якщо/> одиниць потокуу вершину j, тобто в даному випадку дуга (i, j) може розглядатися якавлаштувала попит на потік.
Узагальнена задача протранспортний потік мінімальної вартості на мережі G (V, Е) може бутисформульована як задача лінійного програмування такого виду:
/>
де 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 />/>2.3 Багатопродуктові потоки
Розглядалися до цих пірзадачах транспортні потоки різноманітних видів (наприклад, що відповідаютьрізноманітним типам транспортних засобів або різних вантажів) оптимізуватинезалежно друг від друга або були зведені до деякого однорідного транспортногопотоку. Більш загальною задачею є оптимізація сукупності транспортних потоківдекількох видів з урахуванням наявності обмежень на загальну пропускнуспроможність ланок транспортної мережі. Ця задача може бути сформульована увиді так називаної «задачі про багатопродуктовий потік» на мережі G (V, Е), щоє задачею лінійного програмування спеціального виду.
Розмір потоку k-гопродукту по дузі (i,j) />/>Е визначимо через, /> а вартість переміщенняодиниці k-го продукту по дузі (i, j) — через /> (k = 1,2,...,K).
Кожний із продуктів k маєодне джерело /> />V і один стік /> />V, причому попит k-гопродукту /> урядку /> дорівнюєпропозиції цього ж продукту в джерелі />.
Задача пробагатопродуктовий потік мінімальної вартості складається в тому, щоб знайтитакі значення />(i,j)/>Е, k = 1, 2,…К щоб
(2)
(1) />
/>/>2.4 Задача плануванняперевезень як задача оптимізації взаємозалежних потоків на мережі
Якуже відзначалося вище, одним із найбільше характерних прикладів області додатказадач про взаємозалежні потоки є планування перевезень, при котрому необхіднооптимізувати декілька взаємозалежних потоків на транспортній мережі: потіквантажів, що доставляються від постачальників до споживачів, потік контейнерів(або тари), у яких знаходяться вантажі, потік транспортних засобів, щоперевозять вантажі або контейнери, і потік локомотивів або буксирів, щопереміщають транспортні засоби, якщо вони не є самохідними.
Узагальному випадку ці потоки не збігаються один з одним: як правило вонизароджуються і поглинаються в різноманітних вузлах транспортної мережі, прицьому деякі з них можуть існувати лише на визначених ділянках, що наприкладвідповідають різноманітним видам транспорту.
Незважаючина те що існування взаємозалежних потоків на транспортній мережі є об'єктивноюреальністю, цей факт не найшов явного відображення у відомих математичнихмоделях перевезень. У роботах, присвячених цій проблемі, або оптимізується одиніз потоків, або різноманітні потоки прямо або побічно відображається один зодним. У більшості робіт (наприклад, [12 — 17]) розглядається окремий випадок,коли потоки вантажів зафіксована і задача планування перевезень зводитися дозадачі оптимального розподілення транспортних засобів по напрямках перевезень.У роботі [24], навпаки, розглядається задача оптимального розподілу потоківвантажів по транспортних мережах різноманітних видів транспорту без урахуванняпереміщень транспортних засобів.
Уряді робіт (наприклад, [14 — 17]) розглядаються більш загальні задачі, у якихнаявність потоку вантажів враховується непрямою уявою шляхом виділення потоківнавантажених і порожніх транспортних засобів.
Постановказадачі оптимізації потоків на транспортній мережі, що у явному виді враховуєнаявність взаємозв'язку між потоками, запропонована в [18]. Проблемаоптимізації взаємозалежних транспортних потоків розглянута на прикладі задачаоптимізації двох основних потоків на транспортній мережі: потоку вантажів іпотоку транспортних засобів, що є окремим випадком задачі (5) — (11).
Сформульованав [18] задача оптимізації двох взаємозалежних потоків на мережі полягає втакому.
Заданоспрямованого графа без петель 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) припускається лише часткове перетворення потоків різноманітних типівпродуктів і без їхнього посилення або ослаблення: відмінні від нуля і рівніодиниці лише ті з коефіцієнтів перетворення, що зв'язують активну і пасивнускладові того самого типу первинного потоку. Ці складові можуть переходити другу друга у вершинах />, наприклад на початку і позакінченні робіт (зокрема, при навантаженні і розвантаженні потік порожніхтранспортних засобів перетворюється в потік навантажених і навпаки) або призміні одних ресурсів на інші (зокрема, при перевалюванні вантажів ізтранспортних засобів одного типу на транспортні засоби іншого типу).
Задача полягає вперебуванні такої комбінації первинного і повторного потоків по дугах графа, щозабезпечує одержання максимальної «прибули».
У [19] розглядалася більшзагальна задача про взаємозалежні потоки на мережі, у якій поряд із невзамозамінює і цілком взаємозамінними типами первинного потоку, що існують напідграфі, що не перетинаються, розглядалися і частково взаємозамінні типипотоку, що існують на підграфах, що мають загальні дуги.
Незважаючина свою специфічність, задача такого роду мають цілий ряд різноманітних іважливих практичних додатків. Вони виникають у сітковому плануванні і керуванні(коли поряд із послідовністю виконуваних робіт враховуються і переміщенняресурсів), керуванні виробництвом (коли оптимізується потік деталей абонапівпродуктів, що проходять послідовне опрацювання, так і потік ресурсів,необхідних для цього опрацювання), керуванні потоками інформації (колирозглядається як потік інформації, так і потік носіїв) і, як уже відзначалося,у плануванні роботи транспорту (коли поряд із розподілом потоку вантажів потранспортній мережі оптимізуються переміщення транспортних засобів, щоперевозять ці вантажі).
Длятого щоб більш наочно уявити особливості структури даної задачі, роздивимося їїокремий випадок, коли є лише один вид повторного потоку, а всі типи первинногопотоку цілком взаємозамінні. При цих умовах задача про двох взаємозалежніпотоки формулюється в такий спосіб.
Максимізувати
/> (3)
(4) (де /> — кориснийефект від переміщення одиниці повторного потоку і витрати на переміщенняодиниці первинного потоку m-ого типу /> по дугах (i, j)/>A графа) при виконаннізвичайних умов зберігання кожного з потоків, що проходять через вершину iграфа:
(5)
(7) />/> (6)
де />,/> — попит і пропозиціїдля первинного і повторного потоків Ks+I, Ks-I, Ks+IIі Ks-II- джерела і стоки для первинного і повторного потоківвідповідно, а також обмежень на пропускну спроможність дуг
/> (8)
і особливих обмежень, щовідбивають розподіл первинного потоку на активну і пасивну складові
/> (9)
і залежність повторногопотоку від активних складових різноманітних типів первинного потоку
/> (10)
Крім того, повиннівиконуватися умови невід’ємності
/>. (11)
Як неважко бачити,основною особливістю, що відрізняє дану задачу від звичайних задач пробагатопродуктові потоки мінімальної вартості [24], є наявність специфічнихобмежень (9), (10).
Розглянута задача можебути зведена до традиційних задач про потоки в мережах лише в деяких окремихвипадках. Одним із найбільше істотних умов для цього є виконання вимоги, щобперетворення активної складової в пасивну й обернено відбувалося тільки вджерелах і стоках/>для повторного потоку і неприпускалася передача повторного потоку від ресурсів одного типу до ресурсівіншого типу, тобто щоб розмір активної складового первинного потоку (потокуресурсів), що підтримує повторний потік від джерела до стоку, оставаласьпостоянной
У цьому випадку умовизберігання повторного потоку еквівалентні умовам зберігання активної складовогопервинного потоку, що дає можливість не розглядати повторний потік у явномувиді. Якщо в мережі існує лише один тип первинного потоку />, задача(3)-(11)зводиться до звичайної задачі про двохпродуктовий потік /> і />:
/>
У ідеальному випадку,коли пасивна складова /> відсутніх (тобто первинний потікцілком використовується для підтримки повторного потоку) або може бути заданаапріорно, аналізована задача ще більш спрощується і переходить у задачу прооднопродуктовий потік /> мінімальної вартості.
Задача плануванняперевезень декількома видами транспорту. Основним напрямком підвищенняефективності роботи транспорту є поліпшення взаємодії різноманітних його видівіз метою оптимального використання наявних ресурсів.
Узв'язку з цим однієї з найважливіших практичних задач є комплексне плануванняперевезень вантажів різноманітними видами транспорту (морським, залізничним іт.д.). Оскільки ця задача полягає, з одного боку, у виборі шляхів доставкизадача полягає, з одного боку, у виборі шляхів доставки вантажів і розподілівантажопотоків по транспортних мережах окремих видів транспорту, а з іншогобоку, у виборі типів використовуваних транспортних засобів (судів, вагонів іт.п.) і їхніх переміщень при виконанні перевезень, для її рішення можуть бутивикористані, моделі оптимізації двох взаємозалежних потоків: потоку вантажів(повторного потоку) і потоку транспортних засобів (первинного потоку), щоскладається з двох складових: потоку навантажених транспортних засобів (активнаскладова) і потоку порожніх транспортних засобів (пасивна складова).Взаємозв'язок потоків вантажів і транспортних засобів виражається в залежностірозміри потоку вантажів від розміру потоку навантажених транспортних засобів ів тому, що в пунктах навантаження-розаантаження потоки навантажених і порожніхтранспортних засобів переходять друг у друга, а в пунктах перевалювання потіктранспортних засобів одного виду транспорту переходить у потік транспортнихзасобів іншого виду транспорту.
Аналізованазадача формулюється в такий спосіб [18].
Задано спрямованого графа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-го типу, що спрямовуються в резерв і надходять ізрезерву, />-кількість арендованих транспортних засобів);
/> (24)
-для інших пунктів />, у якихвідбувається навантаження-розаантаження;
/> (25)
— для інших пунктів /> ізапровадження і виводу транспортних засобів з експлуатації;
/> (26)
-для інших пунктів />транспортноїмережі.
Загальнакількість вантажів n-го роду (/>), що відправляються з різноманітнихпунктів або що доставляються в них, не перевищує необхідних обсягіввідправлення-доставки вантажів /> у заданому періоді />.
/> (27)
де/> -кількість вантажів, що відправляються і що доставляються M-м видом транспорту.
Передбачається, що принаявності вільних транспортних засобів можна здійснити перевезення додаткових,надпланових вантажів (наприклад, вантажів іноземних фрахтувальників наморському транспорті).
Кількість вантажів, щозберігаються на складах у пункті />(без обмежень будемо припускати,що />) укожний період часу t, не перевищує загальної ємності складів у даний період
/> (28)
де /> - кількість вантажівn-го роду ввезених на склади і вивезених із них M-м видом транспорту в період />, /> - ємністьскладів у пункті i у період t, /> - можливе збільшення ємностіскладів (наприклад, шляхом оренди додаткових помешкань) у період t,/> — початковакількість вантажів n-го роду та складах.
У будь-який момент часукількість вантажів кожного роду, що зберігаються на складах, невід’ємна:
/> (29)
Кількість транспортнихзасобів кожного типу, що знаходяться в резерві в пункті i, невід’ємна:
/> (30)
Загальний обсягнавантаження-розвантаження в кожному пункті i не перевищує пропускноїспроможності вантажно-розвантажувальних устроїв
/> (31)
азагальна кількість транспортних засобів, що переміщаються по дузі (i,j)транспортної мережі, — пропускної спроможності цієї дуги
/> (32)
Крімтого, на потік транспортних засобів накладені обмеження бюджетного типу
/> (33)
де /> — загальнакількість ресурсів, виділених для транспортних засобів m-го типу (наприклад,розмір бюджету часу), /> - кількість ресурсів, щозатрачаються на переміщення одиниці потоку по дузі (i, j). Всі перемінні задачіневід’ємні:
/> (34)
Потрібно визначитиоптимальні кількості навантажених і порожніх транспортних засобів кожного типу,що переміщаються по дугах транспортних мереж різноманітних видів транспорту,кількості транспортних засобів, що спрямовуються в резерв, арендованих,починаючих і різноманітних вузлах закінчують, що роботу в, мережі, а такожоптимальні обсяги відправлення, доставки, збереження, перевалювання іперевезення вантажів, при яких забезпечується одержання максимального прибутку(без урахуванням постійних складових):
/> (35)
де /> - питомі прибутки відперевезення одиниці вантажів; /> - питомі витрати наперевалювання, навантаження-розвантаження і збереження вантажів; /> — питомі прибутки відперевезення надпланових вантажів; /> - питомі витрати на збільшенняємності складів; /> - питомі витрати на переміщення йоренду транспортних засобів, /> - питомі утрати від простоютранспортних засобів./>/>2.4 Двохрівнева система моделей планування транспортних потоків
Двохрівневасистема моделей будувалася таким чином, щоб не тільки забезпечити можливістьрішення вихідної задачі методом декомпозиції, але і щоб модель кожного рівня неносила штучний характер, а мала чітку змістовну інтерпретацію і принеобхідності могла використовуватися незалежно.
Роздивимосятепер більш докладно формулювання і методи рішення задач кожного рівня [18].
Задачею,що вирішується на верхньому рівні системи, є визначення оптимальних агрегованихвантажопотоків у єдиній транспортній мережі з урахуванням її характеристик іпотреб народного господарства в перевезеннях вантажів, розподіл вантажопотоківміж видами транспорту, планування змішаних перевезень за участю декількох видівтранспорту і вибір оптимальних пунктів перевалювання вантажів з одного видутранспорту на інший.
Дана задача формулюєтьсяв такий спосіб.
Задано графа />, що подаєагреговану єдину транспортну мережу країни, що складається з агрегованихтранспортних мереж /> окремих видів транспорту імістить вершини /> пункти відправлення-призначення,що подають, вантажів і пункти їхній перевалювання. Для кожного пункту /> задані обсягивантажів n-го роду /> котрі потрібно відправити з ньогоабо доставити у відповідний період часу, прибутки />, витрати /> при використані M-м видомтранспорту одиниці ємності складів у пункті i прибуток /> від вивозу одиниці вантажів, щобули на складах у пункті i до початку планового періоду. Відомі також пропускніспроможності /> ланок транспортної мережі,пропускні спроможності /> пунктів перевалювання і витрати /> наперевалювання одиниці вантажу з одного виду транспорту на інший. З деякихпунктів можливий вивіз надпланових вантажів (наприклад, на морському транспортітакими вантажами є вантажі іноземних фрахтувальників).
Потрібно знайти розмірагрегованого потоку вантажів по дугах графа {/>}, обсяги відправлення і доставкивантажів {/>}, {/>},обсяги перевалювання вантажів із М-го виду транспорту на L-й і навпаки вкожному пункті перевалювання {/>}, {/>}, обсяги відправлення надплановихвантажів {/>}, кількості вантажів, що спрямовуються кожним видом транспорту на склади абовивезених із складів {/>}, {/>}, і визначитичастки {/>}і {/>}початкової кількості вантажів на складах у кожному пункті і загальній ємностіскладів, що виділяються в розпорядження кожного виду транспорту, при якихдосягається максимум економічного ефекту
(36) />
При цьому повиннівиконуватися умови зберігання агрегованого потоку вантажів n-го роду (/>) припроходженні через вершини графа в кожний період часу t(/>)
/> (37)
/>(38)
/>(39)
де
/> /> (40)
Обмеження (37) відповідаєпунктам відправлення і доставки вантажів, що одночасно є пунктамиперевалювання, обмеження (38) — пунктам, що є тільки пунктами відправлення ідоставки, а обмеження (39) — іншим пунктам. Крім того, виконуються обмеження намаксимально можливі обсяги відправлення і доставки вантажів
/> (41)
обмеженняна максимально можливі обсяги перевалювання вантажів з одного виду транспортуна інший у кожному пункті перевалювання
/> (42)
обмеженняна пропускну спроможність ланки агрегованої транспортної мережі:
/> (43)
іобмеження на використання ємності складів у вузлах агрегованої транспортноїмережі різноманітними видами транспорту
/> (44)
де
/> (45)
Кількість вантажів кожного роду, що зберігаються наскладах у кожний момент часу, невід’ємна:
/> (46)
де /> початкової кількостівантажів п-го роду, що може бути вивезена M-м видом транспорту,/> (47)Крім того, повинні виконуватися умовиневід’ємності:
/> (48)
Сформульована задача єзадачею лінійного програмування з мережною підструктурою. В.зв'язку з тим щоматриця її обмежень має квазіблочний вид, для рішення задачі може бутивикористаний метод декомпозиції.
Шляхом розкладанняобмежень (41), (42), (45), (47) на окремі обмеження для кожного підграфавихідна задача (36) — (48) зводиться до двохрівневої системи більш простихзадач. Ця система складається з розв'язуваних на другому рівні задач розподілуобсягів відправлення і доставки вантажів />, пропускних спроможностей пунктівперевалювання />, ємностей складів /> і початкової кількостівантажів у них /> між різноманітними видамитранспорту:
/>
і розв'язуваних напершому рівні задач визначення агрегованых потоків вантажів по окремимпідграфами />,що відповідають різноманітним видам транспорту М:
/>
Крім того, повинні виконуватися обмеження (37)-(39),(43), (44), (46), (48).
Застосування методу декомпозиції дозволяє істотно |зменшити розрахункові труднощі. Задача другого рівня 1 мають просту структуру,і їхні рішення можуть бути виписані 3 у явному виді, а задача першого рівнявирішуються на окремих підграфах і можуть бути зведені до задач про однопродуктовийпотік мінімальної вартості, для яких є ефективні спеціальні алгоритми [14-26](як зазначено в [13], за допомогою даних алгоритмів задачі вирішуються приблизнов 50-100 разів швидше, чим за допомогою звичайних методів лінійного програмування.Так, наприклад, задача з 1200 вершинами і 4000 дуг була вирішена усього за 20с).
Узгодження рішень задач другого і першого рівнівздійснюється відповідно до ітеративного алгоритму: на кожній ітерації в моделяхпершого рівня коректуються праві частини обмежень на обсяги відправлення,доставки і перевалювання вантажів, що виділяються частка початкової кількостівантажів на складах і пропускних засіб ностей ланки транспортної мережі, а вмоделях другого рівня — значення коефіцієнтів цільової функції. Ітеративнийпроцес узгодження рішень задач різних рівнів продовжується доти, поки не будеотримане оптимальне рішення вихідної задачі.
2.6 Модельнижнього рівня — оптимізація транспортних потоків на транспортних мережахокремих видів транспорту
Як вже визначалося,задача нижнього рівня розпадається на /> задач, що відповідають окремимвидам транспорту. Для кожного виду транспорту М вирішується така задача.Потрібно максимізувати економічний ефект від перевезення вантажів М-м видомтранспорту
/>(49)
при виконанні обмежень
/>(50)
/> (51)
/> (52)
/> (53)
де />відображаючих умовизберігання потоку вантажів кожного роду.
Крім того, повиннівиконуватися обмеження на максимально можливі обсяги відправлення і доставкивантажів
/> (54)
обмеження на кількістьвантажів, що можуть бути спрямовані на склад:
/> (55)
і узяті зі складів:
/> (56)
Розглянемоматематичну модель і метод рішення.
У тому випадку, колипланування транспортних потоків різних видів відбувається незалежно, наприклад,на різних етапах \упорядкування планів, при перебуванні оптимальныхпотоковтранстранспортных засобів, необхідних для освоєння заданих потоків.; вантажів,у багатьох випадках (особливо при рішенні задач те що кут або перспективногопланування), можна вважати, що маршрути потоків транспортних засобів і потоківвантажів цілком збігаються, таким чином, для визначення потоків транспортнихзасобів достатньо знайти лише кількість транспортних засобів кожного типу, щозакріплюються за кожним вантажопотоком.
Математичні моделі, запропоновані для рішення такихзадач, називаних також задачами розставляння транспортних засобів, можнарозділити на два типи: моделі, що дозволяють.одночасно знаходити як оптимальнезакріплення транспортних засобів різного типу за різноманітними напрямкамивантажопотоків, так і схеми (маршрути) їхній переміщення, і моделі оптимальногорозподілу типів транспортних засобів по напрямках перевезень.
Одна з перших формулювань задачі розставляннятранспортних засобів з одночасною побудовою схем їхній переміщеннязапропонована в [44]. У даній роботі транспортна мережа містить тільки пунктивідправлення і пункти призначення вантажів одного роду і потрібно визначитиоптимальну кількість порожніх у навантажених транспортних засобів кожного типу,що переміщаються по ланках транспортної мережі, при якому забезпечуютьсямінімальні сумарні витрати бюджету часу транспортних засобів. Задано обмеженняна розмір бюджету часу кожного типу транспортних засобів на необхідні обсягиперевезень із кожного пункту відправлення в кожний пункт призначення, а такожобмеження, що відбивають умови зберігання потоку транспортних засобів припроходженні через вузли транспортної мережі.
У [15] розглянута подібна задача, у якійвраховується можливість оренди транспортних засобів і потрібно забезпечитимінімум суми витрат на оренду й експлуатаційні витрати, пропорційних витратамбюджету часу. Для зменшення обчислювальних труднощів, обумовлених великоюрозмірністю даної задачі, розроблений метод, заснований на методі генераціїстовпчиків. На кожній ітерації відшукують замкнутий маршрут кожного окремоготранспортного засобу, що забезпечує мінімальні витрати. Ця задача є задачею проциркуляцію мінімальної вартості і вирішується за допомогою алгоритму дефекту[4]. Потім на основі отриманих рішень підзадач для окремих транспортних засобіввирішується задача побудови нового базису вихідної задачі, для чого використовуютьтільки ті зі знайдених маршрутів, що є більш вигідними в порівнянні з існуючими.
У [17] сформульована задача планування перевезеньдекількох родів вантажів у різноманітні періоди часу. Частина вантажів повиннабути перевезена обов'язково, перевезення інших вантажів є факультативної. Порядз обмеженнями, розглянутими в [14, 15], задані обмеження на припустимескупчення транспортних засобів в однім регіоні і на мінімально припустимийобсяг перевезення вантажів між пунктами відправлення та пунктами призначення.Враховується також кількість транспортних засобів, що повинні вводитися вексплуатацію і виводитися з її в окремих вузлах транспортної мережі.
Оскільки задача даного типу є задачамицілочисельного лінійного програмування, їхнє рішення пов'язане із визначенимиобчислювальнимитруднощами, обумовленими високою розмірністю практичних задач інеобхідністю використовувати додаткові прийоми для усунення можливоїнезв`язнотсти одержуваних маршрутів прямування транспортнихзасобів.
Найбільше доцільною областю застосування моделейданого типу є задачі оперативного і середньострокового планування, у якихвимога недрібності потоків транспортнихзасобів є істотним.
Моделі другого типу більшпридатні для задач поточного і перспективного планування, у яких інформація пропочаткові позиції транспортних засобів, бюджетах їхнього часу а необхіднихобсягів перевезення вантажів є наближеної, і тому нема рації відшукуватиоптимальне рішення з точностью-до послідовності виконання окремих рейсівокремими транспортними засобами. У більшості випадків достатньо визначити лишеоптимальні витрати бюджету часу кожного ' типу транспортних засобів на освоєннякожного вантажопотоку або, що те ж саме, обсяги перевезень вантажівтранспортними засобами різноманітних типів.
У [19] запропонованийдвохетапний метод рішення задачі розставляння транспортних засобів.
На першому етапі потокивантажів різного роду агрегуються в потік деякого умовного, вантажу і для кожногопункту навантаження-розвантаження визначають потребу в тоннажі і кількістьтоннажу, не забезпеченого вантажем. Потім вирішується задача призначеннявільного тоннажу на перевезення вантажів до критерію мінімуму баластовихпереходів. На основі отриманих маршрутів переміщення порожніх транспортнихзасобів і заданих шляхів переміщення потоків вантажів будуються схемипрямування транспортних засобів.
На другому етапівирішується задача пошуку оптимального розподілу транспортних засобів кожноготипу по отриманих схемах прямування, що забезпечує максимум прибули привиконанні обмежень на бюджет часу транспортних засобів кожного типу й обсягперевезень вантажу по кожній схемі.
У [10] розглянута задачарозподілу транспортних засобів по всіх можливих схемах прямування і динамічноїзадачі переміщення транспортних засобів з одних схем на інші при зміні умовексплуатації в різні періоди часу.
У [8] вирішена задачарозподілу транспортних засобів різного типу по різних напрямках вантажопотоківз урахуванням можливості побіжних перевезень вантажів, обмежень на кількістьтранспортних засобів і бюджет їхнього експлуатаційного часу.
Основну трудність прирішенні практичних задач розподілу вантажопотоків між різноманітними типамитранспортних засобів складає їхня висока розмірність, що вимагає відмовлятисявід урахування цілого ряду важливих чинників,, вирішувати задачу для частинивантажопотоків і транспортних засобів, не враховувати тимчасові чинники.
У зв`язку із цим у [15]запропонований декомпозиційний метод для рішення задач, що мають великурозмірність.
Розроблена математичнамодель дозволяє визначити оптимальний розподіл обсягів перевезень вантажів укожний період часу між різноманітними типами власних і орендованих транспортнихзасобів, обсяги перевезень вантажів транспортними засобами, що здаються воренду, кількість вантажів, перевезення яких переноситься на інші періоди часу,та розподіл зовнішніх витрат бюджету часу (наприклад, на ремонт) міжрізноманітними періодами часу.
Дана модель є окремимвипадком розглянутої вище моделі оптимізації транспортних потоків натранспортній мережі одного виду транспорту, істотно спрощеної і модифікованоїна основі аналізу ряду реальних задач поточного і перспективного плануванняперевезень. Передбачається, що на початку планового періоду транспортні засобизнаходяться в пунктах відправлення вантажів, перевезення вантажів від пунктувідправлення в пункт призначення здійснюються без перевалювання в проміжнихпунктах, а пропускна спроможність ланки транспортної мережі, транспортних вузліві складів не обмежений. Завдяки цьому виявилося можливим, по-перше, висловитирозмір потоку вантажів по дугах графа через розмір потоку навантажених транспортнихзасобів, а по-друге, визначати розмір потоку транспортних засобів не дляокремих дуг графа, а в цілому для шляху від джерела до стоку (називаного«напрямком перевезень»).
Перед тим, як переходитидо формулювання моделі, уведемо деякі позначення:
/> - обсяг перевезень вантажів n-городу по l-му напрямку в період /> транспортними засобами m-го типу,що належать підприємству (усі типи транспортних засобів т діляться на групи />);
/> - обсяги перевезень транспортнимизасобами m-го типу, орендованими в іншого підприємства р для виконання окремихперевезень і на весь період /> відповідно;
/> - обсяг вантажів n-го роду, щотранспортне підприємство повинно перевезти по напрямку l у заданий період, часу[/>];
/> - залишок вантажів n-го роду наl-й напрямку в період />;
/> - обсяг перевезень транспортнимизасобами m-го типу, зданими в оренду іншому підприємству р для виконанняокремих перевезень;/> - витрати бюджету часутранспортних засобів, наданих у ореду іншому підприємству р на період />;
/> - позаексплуатаційні витратибюджету часу (наприклад, на плановий ремонт), розподіл яких по період дам часу{/>} можнарегулювати;
/> - трудомісткість перевезеннявантажу n-го роду по l-му напрямку в період /> транспортними засобами m-го типу;
/> - прибутки від перевезенняодиниці вантажу;
/> -експлуатаційні витрати на перевезення единиці вантажу;
/> - аренднаплатня за перевезення лдиниці вантажу та за одинцю бютжетного часу арендованоготранспортного засобу;/> -експлуатаційні витрати на одиницю бюджету времени транспортних засобів, щоздаються в оренду другому пред прийняттю на перпод />;
/> - втрати відневивозу вантажу n-го роду на l-ном напрямку в період />(щодо обов’язкових перевезень />).
Математичнамодель планування об’ємів перевезень має наступний вигляд.
Потрібномаксимізувати отримуємий транспортним підприємством прибуток, який складаєтьсяз прибутків від перевезення вантажів як власними, так й арендованимитранспортними засобами та прибутків від надання транспортних засобів у арендуза різністю експлуатаційних витрат, витрат на аренду та витрат, пов’язаних ззатримкою вивозу вантажів:
/> (57)При цьомуповинні бути виконані такі обмеження.
Сума обсягу вантажів,перевезених як власними, так і орендованими транспортними засобами, і обсягувантажів, перевезення яких переноситься на інші періоди, повинна бути дорівнюєзагальній кількості вантажів:
/> (58)
/> (59)
Витрати бюджету часутранспортних з асобів, що укладаються з витрат на перевезення вантажів, витратпід час оренди і позаесплуатаційних витрат, не повинні перевищувати загальногокалендарного бюджету часу транспортних засобів даного типу в даний період:
/> (60)
де
/> (61)
Витрати на аренду не повині перевищувати виділенудля цього суму
/> (62)
Обсягинадання транспортних засобів в оренду не повинні перевищувати відповіднихпотреб:
/> (63)
/> (64)
Витрати бютжету часуарендованих транспортних засобів не можуть більше максимально м ожливих:
/> (65)
Витрати бюджету часу,обсяги перевезень і обсяги вантажів невід’:
/> (66)
Особливістю даної моделів порівнянні з запропонованими: раніше є те, що в ній істотно враховуєтьсясезонність вантажопотоків і обмеження на використання транспортних засобів наокремих напрямках перевезень у різний час року, припускається переносперевезення деяких вантажів на інший період часу,' враховуються утрати від невчасноговивозу вантажів, обов'язковість деяких із перевезень і можливість орендитранспортних засобів.
У зв'язку з тим що длязначних транспортних організацій сформульована задача має надзвичайно великурозмірність, було запропоновано використовувати для її рішення декомпозиційнийметод.
У результаті декомпозиціїшляхом розкладання обмежень (58), (59), (62), (63) по групах типів транспортнихзасобів />,задача (57)-(66) зводиться до двохрівневому комплексу задач меншої розмірності.
На другому (верхньому)рівні вирішуються задачі розподілу обсягів вантажів, обсягів решти транспортнихзасобів в оренду і коштів між групами транспортних засобів:
/>
де коефіцієнти цільових функцій /> характеризуютьдоцільністьзбільшення для j-й групи транспортних засобів що виділяється обсягу рештитранспортних засобів в аренду, кількості коштів і обсягу вантажів відповідно.
На першому (нижньому) рівні для кожної групи j (j=1, J) визначаються обсяги перевезень власними й арендованими транспортнимизасобами, обсяги вантажів, перевезення котрих переноситься на інші плановіперіоди, а також обсяги аренди і решти в оренду транспортних засобів, щозабезпечують отримання максимального економічного ефекту
/>
при виконанні обмежень (59)-(61), (64), (65),специфічних для даної групи транспортних засобів, а також заданих другим рівнемобмежень на загальні обсяги перевезень вантажів власними, арендованими і щоздаються в аренду транспортними засобами
/>
і на загальні витрати,пов'язані з орендою транспортних засобів,
/>
та умовневід’ємностізмінних
/>
Для узгодження рішень отриманих підзадач другого іпершого рівня з метою досягнення оптимального рішення вихідної задачі застосовуєтьсяітеративний алгоритм.
Розроблені однорівнева і дворівнева моделідозволяють оптимізувати розподіл транспортних засобів по напрямках перевезень зурахуванням сезонної нерівномірності вантажопотоків. Ефективне використанняресурсів транспорту досягається завдяки раціональному розподілу перевезень міжтранспортними засобами різного типу, висновку транспортних засобів зексплуатації в період Мінімального навантаження, оренді транспортних засобів вінших підприємств у період максимального навантаження і решті в оренду власнихтранспортних засобів у період мінімальної.
Запропоновані моделіможуть бути використані для рішення цілого ряду практичних задач поточного і перспективногопланування, у тому числі для планування роботи транспортного підприємства,розподіли планових завдань на перевезення вантажів між різноманітнимитранспортними підприємствами, оптимізації структури парку транспортних засобів,визначення оптимальної кількості що закуповуються (мурованих, арендованих) і щосписуються в зв'язку з моральним зносом транспортних засобів кожного типу іт.п.
Для рішення практичнихзадач розподілу потоків вантажів між різноманітними типами транспортних засобіврозроблені програми: GRASS1, що дозволяє вирішити задачу (57)-(66) звичайнималгоритмом лінійного програмування, і GRASS2, що реалізує декомпозиционныйалгоритм рішення цієї задачі. Програми побудовані по модульному принципі, маютьоверлейную структуру і містять такі модулі:
GRAS1, GRAS2 — модулі, щоуправляють викликом підпрограм при рішенні задача (57)-(66) та відповідно задачдругого і першого рівнів у дворівневоймоделі;
INPUT1, INPUT2 — підпрограми для запровадження вихідних даних і формування на їхній основі матрицьумов задачі лінійного програмування;
LINK1, LINK2- підпрограмидля перетворення розширеної матриці умов, задача лінійного програмування (якамістить строчку коефіцієнтів критерію і стовпчик правих частин обмежень) укомпактну форму (без нульових елементів);
SIMPL1, SIMPL2 — підпрограми для рзшзния задач лінійного програмування з компактною формоюматриці обмежень;
SOLVE1, SOLVE2-підпрограми, що реалізують звичайний Ц декомпозиционный алгоритми рішеннязадачі з використанням одноуровневой і двухуровневой моделей відповідно;2.7 Основнізадачі оптимізації транспортних потоків
Всі задачі оптимізаціїтранспортних потоків можна розділити на два класи: задача, у яких транспортніпотоки рахуються незалежними, і задача, у яких враховується взаємозв'язоктранспортних потоків різноманітних видів.
Перший клас задачвивчений достатньо докладно, і йому присвячене значне спало робіт, чого неможна сказати про другий клас, порівняно мало досліджуваному.
Відповідно до яскравовираженого розходження в технології перевезень і задачах керування ними всізадачі оптимізації незалежних потоків можна розділити на задачі оптимізаціїтранспортних потоків, що відповідають масовим і мілкоштучними перевезеннямвантажів.
Найбільше добре вивченимиі широко застосовуваними є задачі визначення максимального транспортного потокуоднієї групи (потоку вантажів, транспортних засобів і т.п.), що протікає відджерела s у стік t мережі. При цьому кожній дузі (i, j) мережі G (K, А)приписана деяка пропускна спроможність, що визначає найбільше значеннятранспортного потоку, що може протікати по даній дузі.
Якщо є декілька пунктівзародження п поглинання транспортних потоків (джерела п стоків), причому міжрізноманітними джерелами і стоками протікають різнорідні транспортні потоки ісума усіх видів потоків через відповідну дугу обмежена її пропускноюспроможністю, така задача максимизації сумарного потоку між джерелами і стокаминазивається задачею про багатопродуктовий потік.
У випадку, коли надодаток до пропускних спроможностей задані також вартості переміщення одиницітранспортного потоку по кожній дузі мережі, виникає задача перебуваннятранспортного потоку, вартість переміщення якого мінімальна.
Одним з окремих випадківзадач оптимізації потоків, розв'язуваних при керуванні масовими перевозками, євизначення найкоротших шляхів на транспортній мережі. Ця задача необхідна дляупорядкування матриць кореспонденції: таблиць міжпортових кореспонденції — наморському транспорті і шахів-маток кореспонденції — на залізничному транспорті.
Якщовідмовитися від припущення, що в процесі переміщення по дузі розміртранспортного потоку залишається незмінної, тобто якщо на виході з дуги розмірпотоку дорівнює розміру потоку на; її вході, помноженої на деяке ненегатовниечисло, те задача про потік між я и г стає задачею про потоки з посиленнями абовтратами.
В усіх розглянутих вищевипадках неявно припускалися, що транспортні потоки, що існують у мережі, єстатистичними, тобто не враховується такий важливий показник, як часпереміщення потоку по дузі. Припустимо, що кожна дуга характеризуется додатковоі часом проходження по ній одиниці потоку. При цьому можливими потокамирахуються тільки, такі, у котрих кожна одиниця потоку проходить із джерела встік за час, що не перевищує задане. Задача про динамічний потік складається втому, щоб визначити оптимальний транспортний потік із джерела в стік узазначений час за умови, по в кожній вершині мережі G (K, А) потік можевідправлятися негайно або затримуватися. У такий важливої в практичному відношеніпостановці задачі можуть бути облічені також витрати на перевалювання,обмеження на ємність складів, пропускні здатності пунктів перевалювання,витрати на збереження і т.д. Задача динамічному потоку грає істотну роль упостановці та рішенні великого класу задач упорядкування графіків і роскладуроботи транспортних засобів.
У розглянутих вище задачахпередбачається, що потік вантажів від відправника до одержувача значно вищевантаже під’ємності транспортного засобу (масові перевезення) і його можна вимірятикількістю транспортних засобів, необхідних для його освоєння. При цьомунепарністю потоку вантажомісткості: транспортних засобів припустимо зневажати,тобто можна невраховувати цілочисльність потоку.
Протилежний випадок має місце приплануванні дрібних перевезень, коли вантажомісткість використовуванихтранспортних засобів значно вище ваги партії. Основними задачами оптимізаціїдрібних перевезень є- задача маршрутизації й упорядкування графіків прямуваннятранспортних засобів.
У задачах маршрутизаціїпри заданих множинах пунктів гроизводства, споживання, розміщення рухливогоскладу,
У якості таких критеріїввикористовуються найменше число транспортних засобів, найкоротший час виконанняперевезень, мінімальна сумарна відстань або вартість виконання перевезень іт.д.
У випадку, що коливирішує чинником у плануванні роботи транспортного підприємства є урахуваннядинаміки транспортного процесу, виникають задачі упорядкування графіківпрямування транспортних засобів. У графіках визначаються маршрути прямуваннятранспортних засобів, що задовольняють заданим моментам їхній прибуття абовідправлення в пункти транспортної мережі. Будь-яке транспортне підприємство,плануючи свою роботу на тривалий період T, як правило, намагається організуватироботу частини транспортних засобів із якоюсь періодичністю. Графіки зповторюваною структурою на інтервалах часу [(k — 1)T; kT], k = 1, 2,… будемоназивати розкладом роботи транспортного засобу. Період Т може бути, наприклад,дорівнює 24 ч для роботи міського і приміського транспорту, тижню чи місяцю дляроботи морських і річкових судів.
Таким чином, задачаупорядкування графіків прямування транспортних засобів є подальшим ускладненнямзадач маршрутизації.
Задача маршрутизації йупорядкування графіків і розкладів прямування транспортних засобів єнадзвичайно складними з обчислювальної точки зору. Відповідно до теоріїобчислювальної складності рішення задач дискретної оптимізації [2] ефективнорозв'язуваної називається задача, для рішення якої існує алгоритм із числомоперацій, статечним уявою залежних від розмірності вихідних даних. Задачаназивається важковирішальною, або NP-складною, якщо для будь-якого відомогоалгоритму її точного рішення можна побудувати приклад, для якого число операційалгоритму буде виражатися експоненціальною функцією від розмірності вихіднихданих задачі.
Показано, що задачаоптимізації потоку транспортних засобів, що чинять дрібні перевезення, не маютьефективних точних алгоритмів рішення [3]. Застосування точних алгоритмів,заснованих на методах математичного програмування, для одержання чисельногорішення задач реальної розмірності надається практично неспроможним. Ці методидозволяють вирішувати задача незначних розмірностей і мають головною уявоютеоретичне значення. Тому для рішення задач маршрутизації й упорядкуванняграфіків використовуються наближені й евристичні алгоритми.
Другим класом задачоптимізації транспортних потоків є задачі про взаємозалежні транспортні потоки,у котрих додані умови, що відбивають залежність розміру транспортного потокуодного виду, що протікає по якийсь дузі мережі, від розміру транспортнихпотоків інших видів, що протікають по цей же дузі. (Наприклад, залежністьпотоку вантажів від потоку транспортних засобів, що перевозять ці вантажі. )Крім того, у цих задачах може враховуватися можливість перетвореннятранспортних потоків одного виду в інші. Така ситуація має місце, зокрема, утранспортних вузлах, де відбувається перевалювання вантажів з одного видутранспорту на другий./>/>2.8 Математичні моделі, у якихвраховується взаємозв'язок потоків
Ці моделі більш точноописують реальний транспортний процес. Проте алгоритми рішення задач провзаємозалежні потоки значно складніше алгоритмів для задач про незалежні потокиі в даний час їхнє дослідження тільки починається.
На практику частіше іншихзустрічаються задачі, у яких потрібно оптимізувати два види взаємозалежнихтранспортних потоків: потік вантажів різного роду і потік різноманітних видівтранспортних засобів.
Задача оптимізаціївантажопотоків і потоків транспортних засобів можуть мати досить високурозмірність, особливо якщо мова йде про оптимальний розподіл вантажопотоків міжусіма видами транспорту. У цьому випадку доцільно використовувати не однуматематичну модель, а ієрархічну систему взаємодіючих моделей, у якій модельверхнього рівня описує весь транспортний процес із використанням агрегованихпоказників, а моделі нижнього рівня дають детальний опис окремих складовогоцього процесу. Рішення, отримане за допомогою агрегированої моделі,використовують для узгодження рішень детальних задач, а рішення детальних задач- для уточнення агрегованої моделі.
У ряді окремих випадківзадачі про взаємозалежні потоки вдасться зводити до задач про незалежні потоки,у які додані додаткові умови, що відбивають у непрямій формі обмеження,накладені на потік іншого виду. Прикладом такої задачі може служити задачарозподілу вантажопотоків між різноманітними типами транспортних засобів зурахуванням обмеження на обсяг робот, що можуть виконати транспортні засоби.
/>РОЗДІЛ 3 МАТЕМАТИЧНА МОДЕЛЬ ТРАНСПОРТНОЇ СИСТЕМИ ПІДПРИЄМСТВА/>/> 3.1 Структура моделі
Уякості структурної моделі транспортної системи підприємства можна запропонуватисхему, що складається з трьох рівнів. Необхідно відзначити, що з метою деякогоспрощення задачі розглядається транспортна система транспортування матеріальнихзасобів. Питання транспортування енергії, енергоносіїв, і ін. аналогічнихносіїв у даній роботі ми не розглядаємо.
Напершому верхньому рівні знаходяться транспортні зв'язки підприємства ізсуміжниками і покупцями товару їм що випускається. На другому рівні міжцехові транспортнізв'язки. На третьому знаходяться внутрішньоцехові зв'язки. Крім того, рівнібудуть пов'язані між собою окремими вертикальними зв'язками. Цю структурнусхему можна уявити на рис.3.1.
Прицьому на верхньому рівні, рівень А, рис.3.1, йде обмін по закупівлі іпостачанню комплектуючих і постачанню продукції, що буде здійснюватисявідповідно по трем потоках а1, а2.а3, далі другий рівень, рівень підприємства вцелом- У, характеризується міжцеховими потоками: в1, в2, в3,...і в цьому випадкупри наявності окремих підрозділів або цехів і нарешті на третьому рівні С, щоведе роль грають внутрицеховые потоки деталей, заготівель, стружки іт.д., тобто, це потоки: c1, с2,… сm./>/>3.2 Математичний опис моделі
Прицьому система може описуватися такими локальними параметрами: масою щопереміщаються або що транспортуються об'єктів, довжиною шляху транспортування,вартістю транспортування, часом транспортування.
Дляопису системи в цілому введемо залишкову функцію вантажопотоків — />на обраномурівні як
/>, (67)
де
/> — вхіднийвантажопотік;
/> — вихіднийвантажопотік.
Прицьому можна вважати, відповідно до робіт [1,2], що будуть справедливі такіспіввідношення
/>, (68)
де
/> - щільністьвантажопотоку;
/> — швидкістьпереміщення вантажу у вантажопотоку.
Вираження(68) можна записати в іншому виді
/>.
Абодля одномірного випадку
/>.
Уодномірному випадку ми можемо одержати значення швидкості як
/>, (69)
депід /> розумієтьсякомпонента швидкості в цьому ж напрямку.
Крімтого, необхідно прийняти таке допущення, що буде справедливо співвідношення дляцінового потенціалу />:
/>, (70)
де
/>-коефіцієнтпропорційності;
Цеспіввідношення говорить про те, що вантажопотік потенційний.
Причомузначення /> можеявляти собою як ціновий потенціал, так потенціал організаційного типу.
Удвумерном випадку можна записати, що справедливо вираження
/>.
Прицьому, ограничившись одним виміром одержимо, що
/>
Одержимо,що справедливо вираження:
/>, (71)
дезначення /> можебути заздалегідь задане у виді функції або вираження.
/>
/>
Рис3.2.-Залежність щільності /> від координати за умови, щоз=f(x4)
НаРис. 3.2. призводимо графік, що ілюструє цю залежність
Усвою чергу графік зміна швидкості вантажопотоку, відповідно до вираження приймевид, див. графік, рис.3.3.
/>
Рис.3.3.- Графік,що фіксує зміну швидкості вантажопотоку /> в залежності від координати />або шляху призаданому законі зміни в залежності від часу
Функціяшвидкості асимптотична і швидко досягає свого граничного значення, рис.3.3.
Необхідновідзначити, що в реальних умовах швидкість переміщення будь-якого вантажу будеобмежена.
Проте,рішення рівняння (70), називане звичайно диференціальним рівнянням фізики [2],викликає достатньо багато трудностей, можливість рішення рівнянь подібного типупов'язано з можливістю поділу перемінних у спеціально обраних системахкоординат. У принципі рішення можна уявити у виді твори до, прикладу у виді:
/>.
Уцьому випадку підстановка цього рішення в основне рівняння і проведенняспеціальних процедур дозволяє одержати рішення, що влаштовує усіх.
Більшреально для пошуку рішення обмежитися одномірним випадком або застосувати,можливо, диференціювання по шляху.
Іншийваріант рішення складається в тому, щоб задаватися простим вираженням,приміром, для /> і потім знаходити рішення для /> з рівняння(68).
Проте,підходом до рішення може бути таке, із рівняння (68) знаходиться значення />, після чого цевираження подставляется в рівняння, що після ряду перетворень дозволяє одержатизначення швидкості /> реального вантажопотоку.
Крімтого, відомо, що щільність вантажопотоку можна знайти по вираженню
/>,
де/> — фазоващільність;
/> — імпульсвантажу в потоку.
Імпульсвантажу у вантажопотоку являє собою не що інше як
/>,
де,у свою чергу /> — маса вантажу.
/> - швидкістьвантажу.
Амасу вантажу, що проходить по вантажопотоку, можна визначити по такомувираженню
/>.
Уцьому випадку, у загальному виді, ми маємо весь комплект рівнянь для визначеннямаси вантажопотоку і його швидкості.
Слідзазначити, що для вантажопотоків на рівні С будуть справедливі такі положення,описані на прикладі виробничої ділянки.
Виробництвопорожнистих напівфабрикатів здійснюється на вузько спеціалізованомуустаткуванні. Особливість виробництва- спеціалізація, близькість процесів подеяким свої характеристикам не до заготівельних, а до що механобробляють. Протенайбільший інтерес виникає у випадку проектування ділянок ротаційногообкатування і найбільше близьким піт істоті технологічним процесам. У цьомувипадку, у випадку серійного виробництва, можна запропонувати декількаваріантів розташування устаткування: ділянка з послідовним розташуваннямверстатів і спірального розташування на двох рівнях, а також кільцевим.Схематически варіанти розташування устаткування подані на рис.3.4.
/> />
а- послідовнасхема;
б-послідовна багаторівнева схема.
Рис.3.4.-Схеми розташування устаткування на ділянках ротаційного обкатування
Іншийваріант розташування устаткування, аналогічний роторному або кільцевомупринципу розташування, мал.3.5./> />
Рис 3.5.- Роторнийабо кільцевий принцип розміщення устаткування.
Кожнійіз схем розташування устаткування властиві ті або інші хиби, схема мал.3.6 а, увипадку недовантаження ділянки, дозволяє резервувати устаткування дляпланово-попереджувальних ремонтів. У свою чергу схема, рис3.2., кільцевого типупередбачає рівномірне завантаження устаткування з необхідністю вимикання однієїз одиниць перекиданням виробничого навантаження на що залишилися.
/>
Рис3.6- Графи, що відповідають схемам компонування ділянки ротаційного обкатування
Схемарис.3.6, б, передбачає регулювання навантаження на устаткування і вонавикористовується з відносної невеличкою «багатоповерховістю» припроектуванні устаткування різноманітними фірмами.
Можназіставити приведеним схемам графи, показані на рис.3.6.
а,б, в- графи компонування, що відповідають поданим схемам компонування
Уцьому випадку, як приведено в літературі, у матричній формі, рівнянняпоперечних і подовжніх перемінних будуть мати вид:
/>
щодоподовжніх перемінних
/>
де/> і /> квадратніматриці m-ого порядку.
Удосліджуваній задачі, якості вхідної поперечної перемінної приймаємоінтенсивність потоку заготівель — /> після опрацювання на давильномустаткуванні. У свою чергу, у якості подовжньої перемінної, приймаємо /> — інтенсивністьпотоку під опрацювання на ротаційно-обкатаному устаткуванні.
Уокремому випадку, зв'язок між поперечної і подовжньої перемінною може бутиотримана у виді вираження
/>, (72)
де
/>-інтенсивністьпотоку заготівель до />-ой одиниці устаткування;
/> — комплекснийпоказник технологічного процесу, реалізованого на встановленому устаткуванні;
/> — комплекснийпоказник технічного рівня устаткування;
/> і /> — технологічніпараметри системи.
Протевираження (72) являє собою загальний випадок.
Дослідженняпростих моделей ділянок, показало, що для достатньо ефективного наближеннямможе бути використання виражень типу:
/> (73)
де
/> — параметрустаткування, причому /> і />.
Тоді,продуктивність ділянки може бути знайдена по вираженню
/>
Приведеневираження справедливо для всіх трьох випадків гаданого компонування ділянок,мал.4,5.
Причомудля різноманітних схем воно одержить різноманітний вид.
Упершому випадку його форма будет такой
/>
Вдругому випадку, вираження получит аналогічну форму
/>
де
/> — числоверстатів.
Проте,у третьому випадку вираження для продуктивності буде иметь вид
/>
де
/> — інтенсивністьвихідного потоку може бути знайдене з вираження (73 );
/> — числоверстатів.
Або
/>.
Цевираження можна ілюструвати графіками, поданими на мал.3.7,8
/>
Рис.3.7- Графік залежності продуктивності П від інтенсивності вхідного потоку /> і параметратехнологічної системы- s, при числі верстатів />= 4 значеннях комплекснихпоказників />=5, />= 10
/>
Рис.3.8- Графік залежності продуктивності П від інтенсивності вхідного потоку /> і числіверстатів />,при значеннях />= 2 і комплексних показниках />= 5,/>= 10
Графікілюструє ріст продуктивності з характерним максимумом при рості параметра, щохарактеризує технологічну систему.
Графікпоказує інтенсивний ріст продуктивності при обмеженому числі верстатів іпрактично постійний її рівень у випадку збільшення числа верстатів, але присталості інтенсивності вхідного потоку заготівель. Це говорить пронедоцільність збільшення числа верстатів на ділянці у випадку, якщо не будутьвикористані інші критерії оцінки його роботи.
Спочаткуможна зажадати максимальної продуктивності ділянки ротаційного обкатування.Хоча це і є недостатньою умовою ефективності роботи ділянки.
Проте,оптимізація роботи ділянки може здійснюватися по декількох критеріях.
Такимчином, оптимізація рішення зводиться до оптимізацію вираження
/>
Оптимізаціявираження може бути ефективно виконана за допомогою інструментів«Mathcad-8», «Optimization» або «Matlab »,інструментарій «Optimization»./>/>3.3 Аналіз математичної моделі
Приймаючисталість фазової щільності, що цілком припустимо в наших умовах функціонуваннявантажопотоків одержимо, що залежність значення вантажопотоку від щільностіприйме вид, рис.3.9.
Залежністьрозміру вантажопотоку від швидкості /> буде відбита на графіку рис.3.10./> />
І на графіку,рис.3.11, приведена залежність розміру вантажопотоку від цінового потенціалу.
Дляпобудови імітаційної моделі необхідно скористатися такими рівняннями.
Увипадку рівня А, мал.1, ми одержимо такий комплект рівнянь:
/>;
……………………
/>
……………………;
/>;
……………………;
Длярівня У система рівнянь висловиться в такий спосіб:
/>;
/>;
/>;
/>;
/>;
/>.
Длярівня С система основних рівнянь прийме вид:
/>
/>;
/>;
/>;
/>;
/>;
/>.
Крімтого, на системи рівнянь повинні бути накладені групи обмежень, щохарактеризують технічні можливості транспортних систем різноманітного рівня.Крім того, аналогічні обмеження, що стосуються технічних можливостейтранспорту, накладаються і на міжрівневий транспорт.
Призводимоці обмеження.
/> — обмеження пошвидкості прямування;
/> — обмеження напропускну спроможність
Останнє,що дозволяє дати замкнуте рішення, ця наявність рівнянь зв'язку міжрізноманітними рівнями транспортної системи підприємства. Вони можуть бутивиражені у виді рівнянь балансу типу:
/>
Уподілі присвяченій розробці імітаційної моделі призводимо результати, щохарактеризують обрані транспортні потоки з заданими параметрами.
/>/>РОЗДІЛ 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. середовище реалізуєоб'єктний принцип проектування і сама є системою проектування.
Об'єктне проектування.
Середовище підтримуєпроцес проектування, дозволяючи проінтерпретувати проект, оживити його,зберегти процес створення проекту, коректувати будь-які складового проекту беззміни інших. Середовище реалізує об'єктний принцип опису сутностей. Середовищедозволяє як функціональний засіб опису, так і об'єктний, підтримуєтьсяінформаційно-логічний засіб. Використовується математична і мовна нотація,вирішується їхня комбінація.
У цьому випадкукористувач у праві самий вирішити, — на якій стадії йому зупинитися: вербальнийопис, графічне зображення проекту, функціональний опис, конструктор — інструментарій середовища користувача./>/>4.2 Побудова імітаційної моделі
Проектування моделіпочинаємо в такій послідовності. Попередньо виберемо основний імідж,щовідображає рівень транспортної системи А. Це буде імідж типуStratumClass_726raf_ 611, зробимо запис програмного блока в меню текст із'єднаємо його з іміджем графічної візуалізації OSCS2D (двумірный осцилограф).З'єднання виконай з поміччю спеціальної лини зв'язку, де установимо властивостізв'язку і його параметри (прошарки), а також зазначимо що переміщаються по цихлинах перемінні, див. рис.4.1.
/>
Рис. 4.1- Встановлюваніхарактеристики зв'язку
Для запровадження чисел,що характеризують пропускну спроможність каналу транспортної системискористаємося іміджами Numberln (поле запровадження числа) і для візуалізаціївисновка чисельних даних іміджем Numberln ( поле висновка числа). Такий рівеньбуде відбитий іміджем StratumClass_72е2860_ 611 до якого залучені аналогічнііміджі графічної візуалізації, а також иміджа і висновка цифрової інформації.
І нарешті останній рівеньвключає імідж StratumClass_72f1f110_611с супутніми іміджами Status_Out іOSCSpace2D.
При цьому, програмниймодуль іміджу Numberln, поле запровадження числа має форму
STRING WindowName
HANDLE HSpace
HANDLE localHObject,_HObject
FLOAT localwNotifyCode,msg,rez,_Value
STRING local str
FLOAT Value,Step
FLOAT Org,Org
if (~_Value!= ~Value)
logmessage(String(~Value))
rez:=SetControlText2d(~HSpace,~HObject,String(~Value))
_Value:= ~Value
exit()
endif
if(msg==WM_CONTROLNOTIFY)
if (wNotifyCode==768)
str:=GetControlText2d(HSpace,HObject)
Value:= Float(~str)
if (String(~Value)!=~str)
//rez:=SetControlText2d(HSpace,HObject,str)
Value:= Float(str)
endif
_Value:= ~Value
endif
exit()
endif
if (HObject == #0)
if (WindowName!="" && (~HSpace==#0)); HSpace:= GetWindowSpace(~WindowName);endif
if (~HSpace == #0);exit(); endif
if(GetWindowProp(GetWindowName(~HSpace),«CLASSNAME»)!=GetClassName(".."))
_HObject:=CreateObjectFromFile2D(~HSpace,AddSlash(GetClassDirectory(GetClassName("")))+GetClassName("")+".vdr",Org,Org,PFC_MOVEOBJECT)
endif
HObject:=GetObject2dByName(~HSpace,~_HObject,«edit»)
rez:=DelGroupItem2d(~HSpace,GetObjectParent2d(~HSpace,~HObject),~HObject)
if (~HObject)
registerobject(~HSpace,~HObject,"",WM_CONTROLNOTIFY,0)
rez:=SetControlText2d(~HSpace,~HObject,String(~Value))
_Value:= ~Value
endif
endif
У свою чергу програмниймодуль того ж іміджу для висновка значень Numberlend View також приобрететтакий вид
SetStatusText(pos,string(value))
Загальна структураімітаційної моделі, виконана відповідно до пропозицій поділу, подана нарис.4.2.
/>
Рис. 4.2- Загальнаструктура імітаційної моделі в пакеті Stratum- 2000
Основні іміджі StratumClass, рис. 4.2., подані по вертикалі ВІДПОВІДНО до рівнів А, У, С.
З використанням запису задопомогою ідентифікаторів рівняння балансу виглядають у такий спосіб:
На рівні А,X1-X2-Y1-Y2-Y3=A1, програмний модуль у цьому випадку имеет вид
FLOAT S1,S2,P1,P2,V1,V2,A1,t
t:=1
t:=t+1
x:=1
x:=x+1
b1:=3
a:=1
P1:= -1/b1*(a*f^2)
g1:=5
V1:=g1/P1
b2:=2
f:=3
P2:= -1/b2*(a*f^2)
g2:=2
V2:=g2/P2
S1:=12
X1:=S1*P1*V1*t
S2:=30
Y1:= S2*P2*V2*t
A1:= X1+X2-Y1-Y3
У свою чергу на рівні У,за умови рівняння балансу Y3-X2+Y4-X3 програмний модуль буде мати вираз
b1:=1.5
a:=2
P1:= -1/b1*(a*x^2)
g1:=4
V1:=g1*x^3
P3:= -1/b3*(a*x^2)
b3:=2
g2:=3
V3:=g2*x^3
S1:=40
X1:=S1*P1*V1*t
S3:=23
X3:= S3*P3*V3*t
B1:=Y3-X2-X3+Y4
На останньому з рівнів -Сутворюваної моделі, за умови рівнянні балансу типу X3-Y4, програмний модульбуде виглядати в такий засіб
FLOATS1,S2,P1,P2,V1,V2,C1
b4:= 3
P4:= -1/b4*(a*x^2)
g4:=3
V4:=g4*x^3
C1:= X3-Y4
Y4:= S4*P4*V4*t
На моделі рис.4.2,позначені контактні площадки, вона служать для побудови такого рівняімітаційної моделі і здійснюють передачу перемінних на цей рівень принеобхідності декількох перемінних. Отже, модель, подана на мал.1, може бутирозвиті і доповнена до необхідного обсягу і рівня складності. Спроможність дорозвитку і є особливістю імітаційних моделей, утворюваних у середовищі Stratum.
/>
Рис. 4.3 Частинанезалежної імітаційної моделі, рівень А
Ілюстрація роботифрагмента імітаційної моделі, зображеного на рис.4.2, приведена на рис.4.3. а нарис.4.3, подана графічна візуалізація уявлення функцій (1,4,5), розділів., іілюстрація залежності залишків продукції на рівні А в залежності від часу.Розглядався випадок відсутності вантажопотоків на інші рівні.
/>
Рис. 4.4 Візуалізаціярезультатів при роботі одночасно всієї моделі.
На рис.4.4 поданавізуалізація отриманих рішень загальної моделі транспортної системипідприємства. Хибою пакета в цілому, служить відсутність ефективногоавтомасштабування. Тому для великих багаторівневих моделей припадає подаватирезультати прогону фрагментами.
/>
Рис. 4.5 Візуалізаціяфрагмента результатів прогону загальної моделі
Звертає на себе увагалінійний характер зміни залишків на рівні обслуговування А, У, С и явнонелінійний характер обсягів вантажоперевезень. Це попередньо дає можливістьоцінити можливість зміни залишків перевезеної продукції на складах.
/>
Рис. 4.6 Графіки, щоілюструють роботу імітаційної моделі на однім прогоні
Модуль програмидвомірного «осцилографа», службовець для візуалізації отриманихрезультатів призводь нижче. Модуль написаний на специфічній мові Stratum і єрозробкою автора роботи.
STRING WindowName
FLOAT Height,Width
FLOAT local ret
FLOAT nosaveOffset,Offset,Scale,Scale
FLOATx,y,Control,PrintValue,PrintValue,Reset,buffer
COLORREF Color
FLOAT _enable
Установка значень зміннихвиконувалася у вікні, по таблиці, рис.4.7, що варіюються перемінні виділяютьсяавтоматично червоним кольором. Автоматично вказується тип змінних.
/>
Рис. 4.7- Установка значеньзмінних
Після установкиперемінних він ініціалізується на зазначеному модулі, для такого модуляпроцедура установки перемінних повторюється.
Ієрархію встановленихмодулів Stratum покажемо на мал. 6. Вона характеризує місце модуля вструктурній схемі верб відомій мірі послідовність обчислень приведеної моделі.У верхній частині знаходяться три іміджі Stratum Class_72, а потім OSCSpace 2D,що реалізують візуалізацію обчислень і останніми іміджі типу Numberlend.
/>
Рис.4.8 Ієрархіяспроектованої моделі
Ієрархію цілкомвідповідає структурі проекту./>/>4.3 Аналіз результатів прогонуімітаційної моделі
Аналіз результатів прогонуімітаційної моделі достатньо обсяжний і потребує дуже великих витрат часу ізасобів. Тому зупинимося на найбільше цікавих із них, що мають можливий впливна виробничий процес на аналізованому машинобудівному підприємстві.
У першу чергу роздивимосяможливу залежність вантажопотоків на наявні або виникаючі виробничі запаси.
На рис. 4.9 подано графікзалишків вантажу при наявності двох вантажопотоків, це відповідає нижньомурівню С прийнятої моделі.
/>
Рис.4.9- Залишок вантажівна рівні С прийнятої моделі
Графік свідчить пролінійно залежність розміри залишку від х.
Т.ч. це характеризує тойфакт, що функція вартісного потенціалу при невеликих змінах мало впливає нанакопичення запасів у прийняте моделі і не є керуючим чинником. Це говорить проте, що модель або повинна бути доповнена на іншому рівні або є нечуйним дозазначеного чинника.
/>
Рис.4.10- Зміна залишкувантажу при статечній функції вартісного потенціалу, n=7
У цьому випадку, мизштовхуємося із ситуацією, коли залишок різко зростає тільки при наявностідостатньо великого шляху доставки вантажів. При менших шляхах його простопрактично немає. Т.ч., використання імітації дозволило зазначити шляхузменшення залишків на проміжних складах.
/>
Рис.4.11 Зміна функціївартісного потенціалу, при n=3
Графік, рис.11, характеризуєзменшення складських запасів при визначеному виді вартісного потенціалу, щодозволяє зробити висновку про засіб скорочення запасів на проміжних складах.
Більш цікавим іактуальним є питання, як ростуть запаси згодом.
На рис.4.12 приведенийграфік залежності графік залежності залишку вантажу на рівні С від часу />.
/>
Рис. 4.12 Графікзалежності залишків вантажу від часу на рівні С
Залежність носить сугуболінійний характер. Це свідчить про накопичення залишків протягом часуфункціонування системи. Цей результат є показовим і свідчить про необхідністькерування процесом доставки і відправлення вантажів. Такий висновок єзакономірним, тому що «прогон» імітаційних моделей служить восновному для основи прийняття правильних управлінських рішень як виробничоготак і невиробничого характеру.
/>ВИСНОВКИ
Вроботі проаналізовано стан досліджень в галузі транспортних систем та потоків.Приведені моделі транспортних систем різного призначення.
Проаналізованомоделі систем транспорту різного використання. Розлянуто транспортні потоки, якоднопродуктові так і багатопродуктові. Проаналізовані моделі потоків. Приведенізасоби оптимізації, а також звісні моделі.
Розробленоматематичну модель транспортної системи підприємства з використанням теоріїпотенціалу. При цьому було встановлено, що:
· Маємісто факт залежності розміру вантажопотоку від цінового потенціалу;
· Розмірувантажопотоку />залежить від його щільності;
· Встановленовид залежності розміру вантажопотоку /> від швидкості його />;
· Встановленівирази для обчислювання залишку вантажу на кожному з рівнів.
Спроектованоімітаційну модель транспортної системі підприємства на базі програмного пакетуStratum. На основі прогону моделі получена візуалізація, яка може бутивикористана при оперативному керуванні підприємством.
Встановленохарактер зміни і накопичення залишків на кожному з транспортно-виробничомурівнів.
Зрівнянняза фактичними значеннями залишків на рівні С показали адекватність імітаційноїмоделі. Відхилення не перевищували 15-20% від розрахункового значення.
Проведенезрівняння розрахункових значень залишків з фактичним показало адекватністьрозробленої моделі.
/>/>СПИСОК ЛІТЕРАТУРИ
1 ЗельдовичЯ.Б., Мышкис А.Д. Элементы математической физики. Наука. М.: 2000. 351 с.
2 ДжефферсонГ., Свирлс Б. Методы математической физики. М.: Мир. 2001. 311 с.
3 Шеннон Р.Ю. Имитационноемоделирование систем- искусство и наука. М.: Мир, 1998. — 237с.
4 Соломатин Н.А и др.Имитационное моделирование в оперативном управлении производством. М.:Машиностроение 1994.- 459 с.
5 Вавилов А.А. Имитационноемоделирование производственных систем. Берлин. 1998. – 560с.
6 Вентцель Е.С. Исследованиеопераций. М.: Советское радио.1992. – 550 с.
7 Х. Таха. Введение висследование операций. М.: Мир. 1995. Т1. 479 с., Т2. 496 с.
8 Програмний пакет«Stratum» 2000-2001.Modeling Laboratory.РЦИ ПГТУ.
9 Резер С.М., Шкультин И.В.,Ловецкий С.Е., Бузюк М.А. АСУ взаимодействием видов транспорта. М.: Транспорт,2003.
10 Ловецкий С.Е., Меламед И.И.,Плотинский Ю.М. Модели и методы решения задач маршрутизации на транспортнойсети.- В кн.: Итоги науки и техники. Организация управления транспортом. М.:ВИНИТИ, 1999, т3, с.55-112.
11 Черкасский Б.В. Быстрыйалгоритм построения максимального потока в сети.- М.: ВИНИТИ? 1999.
12 Моисеенко Г.Е.Декомпазиционный метод решения задачи планирования объёмов перевозок.- М.:Наука,1987.
13 Диниц Е.А. Алгоритм решениязадачи о максимальном потоке в сети. М.: Машиностроение 1988.
14 Бурков В.Н., Кондратьев В.В.,Молчанова В.А., Щепкин А.В. Модели и механизмы функционирования иерархическихсистем.- АиТ,1997.
15 Нагаев Б.В. Модель составленияразвозок грузов.-Ижевск: Удмуртия 1994.-320 с.
16 Мухачева Э.А. Транспортнаязадача на сети с дополнительными ограничениями.-Экономика и мат.методы,1995.-280с.
17 Позамантир Э.И. Учётнеравномерности перевозок грузов при планировании транспорта. М.: Транспорт,1994.-250с.
18 Савин В.И. Оптимизация работыавтотранспорта. М.: Транспорт,1994.-280с.
19 Артынов А.П., Скалецкий В.В.Автоматизация процессов планирования и управления транспортными системами.-М.:Наука.1995.
20 Васильева Е.М., Левит Б.Ю., ЛившицВ.Н., Нелинейные транспортные задачи на сетях-. М.: Финансы и статистика, 2006.-104с.