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

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

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

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

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

якщо (i,j) у ншому випадку,

 

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

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

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

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

Якщо припустити, що мережа G (V, Е) є ациклічний тобто не містить циклів, то в ній можна пронумерувати вершини так, що для кожної дуги з i у j виконується умова i < j. Очевидно, таке упорядкування може бути виконане за 0 (т) операцій. Тоді для приклада рівняння Белмана можуть бути вирішені простим обчисленням: и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) < uj(n-1) для деякої вершини j. Мережа може бути перевірена на існування негативного циклу за 0 (тп) операцій.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Тип задачі	Кіл-ть рівнянь	Кіл-ть змінних	Линійне програмування		Мережев методы
			Час рішення, с	Вартість, $	Час рішення, с	Вартість, $
Задача про призначення	400 400	1500 2250	231,85 336,37	41,73 60,55	1,16 1,34	0,21 0,24
Транспортна задача	200 200 200	1350 1500 2000	105,68 124,53 164,94	19,02 22,42 29,69	0,94 1,07 1,21	0,17 0,19 0,22
Задача про поток мінімальной вартості	400 1000	1306 2900	174,83 833,63	31,47 150,05	1,51 5,28	0,27 0,95
Узагальнена задача	100 100 100 250 250 500 1000	1000 1000 1000 4000 4000 5000 6000	62,65 62,65 94,72 453,02 742,61 1044,34* 1633,64**	11,28 14,57 17,05 81,54 133,67 186,98* 294,06**	7,51 7,29 9,70 16,65 14,74 22,55 50,22	1,35 1,31 1,75 3,00 2,65 4,06 9,04

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

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

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

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

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

(2)

(1)

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

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

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

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9