183501 (596674), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

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

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

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

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

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

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

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

(3)

(

(4)

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

(5)

(7)

(6)

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

(8)

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

(9)

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

(10)

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

. (11)

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

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

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

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

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

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

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

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

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

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

(12)

де = , (13)

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

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

(14)

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

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

(15)

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

(16)

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

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

(17)

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

(18)

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

(19)

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

(20)

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

Характеристики

Список файлов ВКР