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

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

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

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

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

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

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

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

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

(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) - активної складового первинного потоку другого типу);

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

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