• 1.1.1 Характеристика транспорту як обєкту керування
  • 1.1.2 Моделювання транспортної системи
  • Потік транспортних ЗАСОБІВ m-го типу по дузі діліться па потік НАВАНТАЖЕННЯ и порожніх транспортних ЗАСОБІВ
  • При цьом повінні буті віконані Такі обмеження.


  • Дата конвертації10.08.2017
    Розмір128.43 Kb.
    Типдипломна робота

    Скачати 128.43 Kb.

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

    Анотація

    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), ..., (i n-1, i n); i n? 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 завдання поиска маршруту, что Забезпечує мінімальній годину переміщення транспортного потоку. Довжина шляху є сума довжина дуг, что входять у него.

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

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

    Очевидно, что если в джерело помістіті одиниць потоку, а в СТІК одінічній Попит, пропускні спроможності всех дуг вважаті безкінечнімі и відшукуваті пріпустімій потік мінімальної вартості (за умови, что lij - ВАРТІСТЬ переміщення потоку), ті, розвязавші завдання про потік мінімальної вартості, Знайдемо найкоротшій шлях прямування цієї одиниці.

    Проти у розрахунковому відношенні більш ефективного виявило СПЕЦІАЛЬНІ, так назівані комбінаторні алгоритми, аналізовані в даного розділі. У ціх алгоритмах вихідні дані подані у віді Списків дуг, тобто для кожної вершини дається список тих дуг (i, j), что інцідентні їй, разом Із їхнімі довжина. ОЦІНКИ числа операцій алгоритмів пріведені в табл. 3.Спочатку роздівімося основні алгоритми решение задачі поиска найкоротшого шляху между двома вершинами: 1 (джерело) и п (СТІК).

    Таблиця 3 - ОЦІНКИ числа операцій алгоритмів

    Автор алгоритму

    Оцінка числа операцій

    Автор алгоритму

    Оцінка числа операцій

    Найкоротшій шлях между двома вершинами

    Найкоротші шляхи между усіма парами вершин

    Беллмана [14]

    Дійкстра [15]

    Беллмана-Форд [16]

    0 (n2)

    0 (m log n)

    0 (mn)

    Дійкстра [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; u j = 0

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

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

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

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

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

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

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

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

    Метод Белмана - Форда. Роздівімося ятір 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) (n-1) для деякої вершини j. Мережа может буті перевірена на Існування негативного циклу за 0 (тп) операцій.

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

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

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

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

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

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

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

    Для решение задач оптімізації транспортних потоків останнім часом розроблено так називана теорія Мережна програмування -інтенсівно что розвівається область математичного програмування [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.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)

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

    (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-й и навпаки в кожному пункті перевалювання {}, {}, ОБСЯГИ Відправлення надплановіх вантажів {}, кількості вантажів, что спрямовуються шкірних видом транспорту на склади або вивезення Із складів {}, {}, и візначіті Частки {} и {} початкової кількості вантажів на складах у кожному пункті и Загальній ємності складів, что віділяються в Розпорядження шкірного виду транспорту, при ких досягається максимум економічного ЕФЕКТ

    При цьом повінні Виконувати умови зберігання агрегованих потоку вантажів 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)



    lign = "left"> де

    - вхідній вантажопотік;

    - вихідний вантажопотік.

    При цьом можна вважаті, відповідно до робіт [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 local HObject, _HObject

    FLOAT local wNotifyCode, 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

    Основні іміджі Stratum Class, рис. 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, програмний модуль буде віглядаті в такий засіб

    FLOAT S1, 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 nosave Offset, Offset, Scale, Scale

    FLOAT x, 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с.

    ...........


    Головна сторінка


        Головна сторінка



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

    Скачати 128.43 Kb.