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

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

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

Відмінність даної задачі від попередньої полягає в тому, що для кожної дуги (i,j) Е задана вартість переміщення одиниці транспортного потоку і необхідно знайти потік заданого розміру v із джерела s у стік t, що мінімізує зважену суму потоків

Для рішення цієї задачі запропонована множина різноманітних алгоритмів і їхніх узагальнень. Серед. них алгоритми, засновані на застосуванні прямих і двоїстих симплекс-алгоритмів лінійного програмування й алгоритмів пошуку найкоротших шляхів. Одним із поширених алгоритмів є так називаний алгоритм дефекту [4], що дозволяє вирішувати задач про потік мінімальної вартості достатньо загального виду. Число операцій алгоритму дефекту оцінюється як 0( ), де число К₀, обумовлене на перших ітераціях алгоритму, не перевищує , п - число вершин мережі, т - число її дуг, а

Очевидно, можна замість 0( ) використовувати оцінку 0( ). У [5] запропонована модифікація алгоритму дефекту з оцінкою числа операцій 0 ( ).

Алгоритми пошуку потоку мінімальної вартості застосовуються для рішення задач у дуже великих мережах. У роботах [11, 12] повідомляється про рішення прямими алгоритмами задач із 20000 вершин 450 000 дуг, а в [13] - про рішення однієї задачі з 3000 вершин і 35 000 дуг за 97 с на IВМ-360/67 і іншої задачі з 5000 вершин та 15 000 дуг за 113 с.

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

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

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

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

Проте у розрахунковому відношенні більш ефективними виявилися спеціальні, так називані комбінаторні алгоритми, аналізовані в даному розділі. У цих алгоритмах вихідні дані подані у виді списків дуг, тобто для кожної вершини дається список тих дуг (i, j), що інцидентні їй, разом із їхніми довжинами . Оцінки числа операцій алгоритмів приведені в табл. 3.Спочатку роздивимося основні алгоритми рішення задачі пошуку найкоротшого шляху між двома вершинами: 1 (джерело) і п (стік).

Таблиця 3 - Оцінки числа операцій алгоритмів

Метод Белмана. Скористаємося рівнянням Белмана для визначення найкоротшого шляху між вершинами 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. Покласти

якщо (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 (т) операцій. Тоді для приклада рівняння Белмана можуть бути вирішені простим обчисленням: и₁ = 0, и₂ залежить тільки від и₁, и₃ залежить від и₁, и₂, иj залежить від и₁, и₂,..., и_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⁽ⁿ⁾ < uj^(n-1) для деякої вершини j. Мережа може бути перевірена на існування негативного циклу за 0 (тп) операцій.

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

У розглянутих вище задачах передбачалося, що однорідний транспортний потік, що виходить із дуги (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.

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

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