Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Методи та алгоритми розв'язування задач синтезу мереж зі складною структурою

Автореферат

дисертації на здобуття наукового ступеня доктора фізико - математичних наук

Загальна характеристика роботи

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

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

Підвищення ефективності розв'язання задач синтезу мереж тісно пов'язане із зменшенням трудомісткості розв'язання таких задач як знаходження мінімального розрізу в неорієнтованій і в параметричній мережі, задача знаходження потоку мінімальної вартості, для розв`язання яких відомі строго поліноміальні алгоритми. Багато задач комбінаторної оптимізації, як зазначив J. Edmonds, не мають подібних алгоритмів розв'язання. Дослідження за теорією складності дискретних оптимізаційних задач і методів їх розв'язання впроваджували С.А. Cook, А.А. Karp та ін. Ці дослідження привели до виділення -важких задач і задач, для вирішення яких існують поліноміальні алгоритми (клас ). Всі задачі, що є доповненнями задач з , утворюють клас . Доведення того, що деяка задача належить перетину і , називається доброю характеризацією цієї задачі. Задачі синтезу мереж і розміщення належать класу -важких задач. В.А. Трубін, Н.З. Шор розробили специфічні алгоритми для вирішення ряду задач розміщення та синтезу мереж і показали їх високу ефективність на ряді тестових і реальних задач. A.R. Mahjoub, H. Kerivin, J.B. Magnanti, P. Mirchandani, R. Vachani, F. Barahona, B. Forth, M. Labbe, M. Grеtschel, З.L. Monma, M.X. Stoer запропонували поліед-ральний підхід до розв'язання ряду задач синтезу мереж з використанням правильних (valid) нерів-ностей для многогранника їх допустимих розв'язків. M.X. Goemans і D.J. Bertsimas та інши показали, що розрізні нерівності (cut inequalities) за деяких додаткових умов визначають грані многогранника допустимих розв'язків задач синтезу мереж. С.С. Лебедев, А. Понюков, Б.Л. Береснев, M.E. Efroymson, T.L. Ray, J.L. Nemhauser, О. Blide, J. Krarup запропонували різні методи розв'язання задач розміщення. Багато потокових задач на мережах, задачі перетину двох поліматроїдів, задачі покриття орієнтованих розрізів є окремими випадками задачі про субмодулярний потік. J. Edmonds і R. Gilies показали цілком двоїсту цілочисельність матриці обмежень цієї задачі. Для вирішення задачі про субмодулярний потік F. Barahona, W. Cunningham застосовують симплекс-метод. При цьому передбачається, що існує деякий оракул для знаходження мінімуму субмодулярної функції (ЗМСФ). А. Schrijver, S. Iwata, L. Fleischer, S. Fujishige запропонували строгі поліноміальні алгоритми для розв`язання ЗМСФ. M. Fredman, R.G. Tarjan, A.V. Goldberg, використовуючи Фібоначчі-структури для подання вершини з тимчасовими помітками, поліпшують показники часової складності алгоритму Дейкстри. P. Kleinschmiidt, H. Schannath, R.К. Ahuja, J.В. Orlin, A.V. Goldberg, J.B. Magnanti, J. Vygen показали, що можна зменшити трудомісткість відомих поліноміальних алгоритмів при розв'язанні задачі знаходження потоку мінімальної вартості з використанням різних деревовидних структур для подання даних. L. Thomas, М.Л. Бронштейн і К.В. Ким зазначають, що серед відомих методів розв`язання задачі знаходження потоку мінімальної вартості ефективним є метод потенціалів з використанням деревовидної структури у вигляді однозв'язного списку (singly linked list) для представлення даних.

Зв'язок работи з науковими програмами, планами темами. Дана робота є складовою частиною наукових досліджень, що проводилися в Інституті кібернетики ім. В.М. Глушкова НАН України, зокрема, таких:

1. ИП 110.08 «Розробити і ввести в експлуатацію ППП (ДИСНЕЛ) для розв`язання на ЕОМ різних типів дискретних і нелінійних задач математичного програмування».

2. ВФ 120.01 «Розробка нових методів розв'язування спеціальних класів багатоекстремальних задач та задач булевого программування» (№ держреєстрації 0197U005232, 1997-1998 рр.).

3. МФ 110.04 «Задача проектування та аналізу комунікаційних мереж: моделі, методи, алгоритми та програмне забезпечення» (№ держреєстрації 0197Г024584, 1997-2000 рр.).

4. ВФ 120.03 «Розробка методів рішення складних дискретних і багатоекстремальних задач оптимізації і їхнього застосування» (№ держреєстрації 0201Г001860, 1999-2000 рр.).

5. ВФ 120.05 «Розробка нових методів рішень дискретних задач» (№ держреєстрації 0204Г003086, 2000-2004 рр.).

6. ВФ 120.08 «Розробка ефективних методів для рішення спеціальних задач дискретного програмування великої розмірності» (№ держреєстрації 0104Г000276,

2004-2005 рр.).

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

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

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

Дисертаційна робота містить такі основні результати:

- розглянуто нові класи задачі синтезу мереж, досліджені їхні властивості і на базі цих властивостей сформульовані математичні моделі задач у термінах потоків на мережі;

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

- запропоновано поліедральный метод для рішення задачі синтезу двозв'язної мережі

- запропоновані алгоритми знаходження точного й наближеного рішень задачі синтезу двозв'язної мережі, задачі синтезу мережі з незалежними шляхами;

- зформульовано загальну задачу розміщення, запропоновано нові ефективні алгоритми для розв'язання оцінних задач, отриманих шляхом лінійної релаксації розглянутої задачі, ці алгоритми використані в загальній схемі методу гілок і границь;

- показана ефективність запропонованих алгоритмів на реальних і тестових задачах;.

- зформульована загальна задача атаки на гіперграфах і доведено, що багатогранник опуклої оболонки допустимих рішень задачі є цілком двоїстий цілочисельній задачі;

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

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

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

Результати роботи використовувалися також у ряді госпдоговорів, які виконувалися Інститутом кібернетики. Зокрема, спільно з ДіпроНДІсільгоспом Держагропрому СРСР вирішена задача оптимізації розміщення і вибору типорозмірів устаткування зернообробних підприємств для Алтайського краю. Спільно з Українським науково-дослідним інститутом зв'язку розв`язана задача розрахунків варіантів побудови міжміської телефонної мережі України, а також задача проектування магістральної телекомунікаційної мережі зв'язку в рамках теми «Розвиток математичного і програмного забезпечення для розрахунку первинної магістральної телефонної мережі України». Впровадження отриманих результатів дозволило значно скоротити час підготовки проектних рішень і поліпшити якість цих рішень. У роботі також показано, що відома генетична задача з молекулярної біології зводиться до спеціальної задачі синтезу мережі.

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

Особистий внесок здобувача. Всі наукові результати дисертаційної роботи отримані автором самостійно. У працях, виконаних у співавторстві, дисертантом отримано наступні результати. В роботі [1] дисертант є автором розділу задачі проектування мереж для випадку, коли ребра, ізоморфні заданному графу, можуть вийти з ладу. У роботі [2] - основні результати отримані дисертантом, а співавтор брав участь в обговореннях. У роботах [4, 5, 7] дисертантом запропоновані алгоритми розглянутих задач, а також реалізації цих алгоритмів. У роботі [19] співавтору належить лише постановка задачі.

Апробація. Основні результати роботи доповідалися на наукових семінарах Інституту кібернетики ім. В.М. Глушкова НАН України, конференції «Системні питання розвитку єдиної національної системи зв'язку України» (Київ, 1997); II International symposium «Problems mathematical modeling, control and information technologies in oil-gas industry» (Baku, 1998); «Teleworking in research, medicine and business» (Kiev, 2001); «Recent advances in non-differentiable optimization», U.S. - Ukrainian Workshop (Kyiv, 2000); «International conference on Applied Mathematics, Dedicated to 65-th anniversary B.N. Pshenichnyi» (Kyiv, 2002); «International network optimization conference» (Evry /Paris, France, 2003); ІІ Міжнародній школі-семінарі» Теорія прийняття рішень» (Ужгород, 2004).

Публікації. Основний зміст дисертаційної роботи опубліковано в 34 наукових роботах, з них одна - монографія та 21 стаття, які опубліковані в наукових фахових виданнях, затверджених ВАК України.

Структура та обсяг роботи. Робота складається із вступу, п'яти розділів, висновків, списку використаних джерел 152 найменувань, та документа, який відображає впровадження результатів роботи. Загальний обсяг роботи - 283 сторінки, основний текст роботи викладено на 266 сторінках.

Зміст роботи

синтез мережа математичний алгоритм

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

Перший розділ присвячено загальній задачі синтезу надійних мереж (ЗЗСМ), яка формулюється в § 1.1. В наступних §§ 2-13 досліджуються властивості ЗЗСМ і розглядаються її окремі випадки.

Нехай задані множини вершин і ребер неорієнтованого графа , множина вузлів (термінальних вершин) , невід`ємна вага для всіх ребер . Також заданий інший неорієнтований граф за допомогою одного з наступних способів:

1) задані множини і , або зазначені числа ребер і вершин графа з виділеною структурою (множина в явному вигляді не задана);

2) граф може бути довільним графом з виділеною структурою (множини і не задані, числа ребер і вершин графа не зазначені).

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

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

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

Твердження 1. Задача про допустимість має розв'язок тоді і тільки тоді, коли множина ребер довільного підграфа , ізоморфного , не утворює розріз, відділяючий хоча б один вузол з від решти вузлів , в графі .

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

У § 1.2 формулюється наступна математична модель ЗЗСМ з потоковими змінними і досліджуються її властивості.

Знайти

(1)

при обмеженнях

(2)

(3)

. (4)

Тут - множина ізоморфних підграфів графа , - множина ребер, що з'єднують вершини з вершинами з на графі, який отримується після видалення з всіх ребер підграфа .

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

Твердження 2. Задача визначення -повна.

Твердження 3. Якщо в не існує підграфа, який не містить жодного ребра оптимального дерева Штейнера , то є оптимальним розв'язком ЗЗСМ .

Показано, що генетична задача з молекулярної біології зводиться до перевірки, чи є дерево Штейнера розв'язком ЗЗСМ. Із твердження 3 випливає, що в множині існує хоча б один підграф , множина ребер якого містить ребра оптимального дерева Штейнера. За твердженням 2 задача лінійного програмування (1) - (3), що є - релаксацією ЗЗСМ (оціночна задача), в загальному випадку належить до класу -повних задач. Нехай - двоїсті змінні, які відповідають обмеженням (2), а - ізоморфний графа підграф, який містить ребро .

Розглянемо двоїсту до (1) - (3) задачу, що може бути представлена таким: чином: знайти

при обмеженнях

, , ,

, ,

, .

, - множина, яка містить усі підграфи .

Твердження 4. Існує оптимальний розв'язок двоїстої задачі до (1) - (3), такий, що тільки для одного підграфа .

За твердженням 4, для кожного ребра досить залишити одну змінну в обмеженнях двоїстої задачі. Тому у випадках, коли підграф визначається за поліноміальний час, число змінних двоїстої задачі скорочується до величини, яка оцінюється як . Для деяких спеціальних графів підграф можна визначити за поліноміальний час, і тим самим доводиться поліноміальна розв'язність задачі (1) - (3) у цих випадках. Розв'язком задачі (1) - (3) визначається нижня оцінка для ЗЗСМ.

Теорема 1. У випадках, коли граф заданий першим способом, , , або - паросполучення потужністю , розв'язок задачі (1) - (3) можна знайти за поліноміальний час.

Для другого способу задання показано, якщо - граф типу дерева або паросполучення, то задача (1) - (3) також розв'язується за поліноміальний час.

У § 1.3 розглядаються окремі випадки ЗЗСМ з першим способом задання графа , і доводиться поліноміальна вирішуваність задачі: чи існує розв'язок ЗЗСМ.

Теорема 6. Якщо множина ребер графа містить по одному ребру з кожного простого циклу в , які не перетинаються ребрами, а реберна зв'язність графа рівна 4, то існує розв'язок ЗЗСМ.

Твердження 5. В оптимальному розв'язку задачі (9) - (12) знайдеться хоча б два шляхи з в , які не перетинаються ребрами, з додатними пропускними спроможностями () ребер цих шляхів.

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

Визначення 1. Щодо знайдених шляхів , () шлях називається поліпшуючим, якщо , де - сума вагів ребер шляху , для довільного .

Теорема 7. Допустимий розв'язок задачі (9) - (12) є оптимальним розв'язком задачі тоді і тільки тоді, коли в мережі не існує поліпшуючий шлях.

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

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

На базі вищезазначених властивостей задачі (9) - (12) для її розв`язання запропонований строго поліноміальний алгоритм із трудомісткістю .

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

.

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

Теорема 8. В оптимальному розв'язку внутрішньої задачі для допус-тимих значень вектора , якщо для , то і - оптимальне рішення двоїстої задачі.

Твердження 6. Обмежена система має допустимий розв'язок тоді і тільки тоді, коли пропускна спроможність мінімального розрізу на графі рівна .

Так само, як в прямодвоїстому симплекс-методі, визначаються нові значення і процес знову повторюється щодо отриманих значень двоїстих змінних. Коректність запропонованого алгоритму виходить з факту, що для змінних , відповідних множині дуг мінімального розрізу, виконуються умови теореми 8.

Значення змінних збільшуються від ітерації до ітерації. Тому пропускні спроможності дуг, інцидентних джерелу, зменшуються. В § 2.3 запропонований алгоритм розв'язання задачі знаходження мінімальних розрізів на параметричній мережі в разі, коли пропускні спроможності ребер, інцидентні джерелу і стоку, зменшуються або збільшуються (зокрема від 0 до 1). В цьому випадку властивість гнізда (див. «А fast parametric maximum flow algorithm» G. Gallo, M. Grigoriads, R. Tarjan. SІAM J. Computing. 1989. 18 №1. P. 30-55) не вірна для мінімальних розрізів в параметричній мережі.

Теорема 9. Число різних мінімальних розрізів на мережі, коли пропускні спроможності ребер, інцидентні джерелу і стоку, збільшуються (зменшуються), не більше ніж (число вершин мережі).

Запропонований алгоритм із трудомісткістю для розв`язання розглянутої задачі знаходження мінімальних розрізів у параметричній мережі, де - трудомісткість алгоритму визначення мінімального розрізу. В цьому алгоритмі оптимальний потік, знайдений на попередній ітерації, є допустимим потоком на поточній ітерації для задачі знаходження максимального потоку в мережі . Тому, при використовуванні цього алгоритму зменшується трудомісткість рішення двоїстої задачі (14) - (18), (20), (23) - (25).

У § 2.4 запропонований алгоритм обчислення нижньої оцінки, яка виз-начається шляхом знаходження наближеного розв'язку двоїстої задачі. На кожній ітерації алгоритму після зміни коефіцієнтів цільової функції розв'язується вищезгадана транспортна задача. На поточній ітерації алгоритму збільшуються значення змінних таким чином, що всі оптимальні розв'язки транспортних задач, які розв`язувалися на попередніх ітераціях, є оптимальним розв'язком цієї задачі. Окрім цього, значення змінних задовольняють обмеженням (24) і (25). Після знаходження розв'язку двоїстої задачі для побудови допустимого розв'язку задачі (13) - (22) покладемо , якщо обмеження в (24) виконується як рівність, або в протилежному випадку. Знову виходить транспортна задача, розв'язок якої є наближеним допустимим розв'язком задачі (13) - (22), і тим самим визначається верхня оцінка для (13). Показано, що алгоритм монотонний за зміною цільової функції і зходиться за скінченне число кроків.

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

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

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

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

,

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

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

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

У § 3.5 розглядається задача синтезу інтегрованих цифрових мереж зв'язку, яка виникає на практиці. Нехай на карті країни задана множина географічних місць деяких об'єктів (наприклад, населених пунктів). Необхідно передати заданий обсяг інформаційного потоку в ерлангах між деякими невпорядкованими парами і із множини термінальних вузлів (далі вузли) мережі . В телекомунікаційних мережах зв'язку вузли відповідають великим містам (наприклад, обласним центрам на карті країни). Якщо для деякої вершини з не заданий обсяг інформації, що виходить із неї, то ця вершина називається транзитною, тобто для неї повинна виконатися умова балансу між інформацією, що виходить і входить. При передачі інформаційного потоку з деякого вузла до іншого вона може проходити через будь-яку транзитну вершину і при цьому витрати для відправлення потоку через транзитну вершину виражаються як вищезгадана функція від кількості переданого інформаційного потоку. Задані відстані між довільними парами вершин з і витрати як функція на будівництво кожного ребра, які залежать від величини сумарного інформаційного потоку на цьому ребрі. Для кожного ребра також задана ймовірність , щодо якої визначається кількість втрат від сумарного потоку на цьому ребрі. На практиці, згідно теорії інтегрованих цифрових мереж, при створенні лінії зв'язку, що сполучає два вузли, число каналів повинне бути кратним деякому наперед заданому числу, наприклад 30, . Щодо заданих і число каналів обчислюється за відомою формулою Ерланга. Якщо , то треба збільшити число каналів на ребрі , або знайти додатковий шлях між поточними вузлами мережі. Тому, проектована мережа може містити декілька шляхів, які не перетинаються ребрами. Виникає наступна задача синтезу інтегрованих цифрових мереж, в якій вимагається визначити число каналів на ребрах для передачі заданого навантаження між парою вузлів з за умови, що рівень втрат на його ребрах не перевищує заданого порогового значення втрат, так, щоб мінімізувати сумарні витрати на будівництво її ребер і витрати на проходження потоку через її транзитні вершини.

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

Алгоритми розв'язання задач синтезу мережі з незалежними шляхами і заданими втратами запрограмовані на мові . Створене програмне забезпечення було використано для розв`язування задач проектування інтегрованих цифрових мереж зв'язку України, а також при проектуванні вторинної мережі як для всієї країни, так і для окремих областей.

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

Потокова модель задачі аналогічна моделі ЗСНМ, алгоритми знаходження нижніх і верхніх оцінок ЗСНМ після незначної зміни визначають ці оцінки для цієї задачі.

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

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

, (26)

і зворотне зведення теж вірно. Тут функція для всіх , і вона є супермодулярною функцією.

Теорема 11. Існує поліноміальний алгоритм розв'язання задачі атаки мережі зі зваженими вершинами.

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

1) знайти ,

2) визначити, в яких випадках загальна задача мінімізації субмодулярної функції:

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

Шляхом заміни ця задача перетворюється до вигляду знайти

, (29)

де - поліматроїдна функція.

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

За теоремою 12 для визначення

спочатку будується базова мережа з використанням значень розрізної функції і для отриманої мережі розв'язується задача знаходження мінімального розрізу. З урахуванням того, що , для синтезу базової мережі ваги її вершин і ребер визначаються з функціональної рівності (28). Якщо покласти , і , в (28), то відповідно обчислюється вага вершин і вага ребер . При цьому з субмодулярності функції витікає, що вага ребер невід`ємна. Відзначимо, що в інших відомих алгоритмах розв'язання подібних задач синтезу мереж виникають труднощі, пов'язані з від`ємністю отриманих ваг ребер. Таким чином, визначається вага ребер і вершин базової мережі і алгоритмом розв'язання задачі знаходження мінімального розрізу з § 4.1 визначається необхідний мінімальний розріз за час . Показано, що з використанням розрізної функції можна побудувати неорієнтовану мережу, на якій можна знайти розв'язок задачі Гоморі і Ху, а також розв'язок задачі атаки зі зваженими вершинами і ряд інших задач.

Лема 7. Якщо в базовій мережі , то оптимальний розв'язок задачі (27) не містить вершину .

Припустимо, що в базовій мережі вага вершини залежить від деякого параметра . За лемою 7 можна вибрати , таким чином, що вершина не належить множині , яка визначається шляхом розв'язання задачі (27). Отже, вибираючи вагу вершин базової мережі шляхом розв'язання задачі (27), можна знайти мінімальний розріз на базовій мережі такій, що , тобто можна розв`язати задачу Гоморі і Ху. За теоремою 12 це еквівалентно знаходженню мінімуму параметричної заданої розрізної функції. Таким чином, якщо двоїста функція для заданої параметричної субмодулярної функції задовольняє умові теореми 12, то трудомісткість алгоритму знаходження мінімуму цієї функції оцінюється як .

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

(30)

при обмеженнях

, (31)

, , , , (32)

, , , , (33)

, , . (34)

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

Теорема 13. Серед оптимальних розв'язків задачі (30) - (33) (-релаксація (30) - (34)) є цілочисельний.

Ця властивість виходить із звідності задачі (30) - (34) на дереві до найпростішої задачі розміщення на дереві з вершинами.

Наслідок 1. Існує алгоритм розв'язання задачі (30) - (34) із трудомісткістю, що росте як .

Наслідок 2. Для фіксованого задача (30) - (34) розв`язна строго полі-номіальним алгоритмом.

Зауваження. Задача (30) - (34) на довільному графі також зводиться до найпростішої задачі розміщення.

У § 5.2 запропонований алгоритм розв'язання задачі (30) - (34). Для побудови алгоритму двоїстого типу розв'язання задачі (30) - (33) доводиться наступна властивість задачі, двоїстої до (30) - (33). Нехай двоїсті змінні і відповідають обмеженням (31) і (32).

Висновки

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

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

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

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

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

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

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

Розроблено алгоритми рішення задачі синтезу мережі з заданими числами шляхів і втратами. Ці алгоритми реалізовані мовою C і використані при рішенні задачі проектування інтегрованих цифрових мереж зв'язку (вторинної мережі).

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

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

Запропоновано алгоритм синтезу мережі з використанням значень розрізної функції.

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

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

Основні положення дисертації опубліковані в таких працях

Шор Н.З., Сергієнко І.В., Шаріфов Ф.А. та ін. Задачі оптимального проектування надійних мереж. - К.: Наук. думка, 2005. - 229 с.

Шор Н.З., Шарифов Ф.А. Общая задача синтеза надежных сетей // Проблемы управления и информатики. - 2006. - №1-2. - C. 184-202.

Шарифов Ф.А. Полиномиальность нахождения оценок в общей задаче синтеза сетей // Теория оптимальных решений. - Киев: Ин-т кибернетики им. В.М. Глушкова НАН Украины, 2005. - №4. - С. 80-87.

Трубин В.А., Шарифов Ф.А. Простейшая многоэтапная задача размещения на древовидной сети // Кибернетика и системный анализ. - 1992. - №6. - С. 128-135.

Трубин В.А., Шарифов Ф.А. Общая задача размещения // Теория и вычислительные проблемы оптимизации. - Киев: Ин-т кибернетики им. В.М. Глушкова АН Украины, 1993. - С. 16 - 20.

Шарифов Ф.А. Задача синтеза связных сетей относительно изоморфных подграфов // Кибернетика и системный анализ. -2004. - №5. - С. 126-131.

Михалевич В.С., Трубин В.А., Шор Н.З., Шарифов Ф.А., и др. Пакет прикладных программ для решения ЕС ЭВМ дискретной и нелинейной задачи оптимизации (ППП ДИСНЕЛ). 1991. - Рукопись деп. ВНТИЦ, Инв. №029.10 019092.

Шарифов Ф.А. Алгоритмы нахождения нижней оценки для задачи синтеза сетей с заданной вершинной связностью // Теория оптимальных решений. - Киев: Ин-т кибернетики им. В.М. Глушкова НАН Украины, 2004. - №3. - С. 89-96.

Шарифов Ф.А. Многогранник допустимых решений задачи проектиро-вания недревовидных сетей // Доп. НАН України. - 2004. - №3. - С. 69-75.

Шарифов Ф.А. Об эффективности алгоритмов решения сетевых задач на древовидных структурах // Кибернетика и системный анализ. - 2003 - №3. - С. 179-185.

Шарифов Ф.А. Задача нахождения непересекающихся и несовпадающих циклов на сети // Теория оптимальных решений. - Киев: Ин-т кибернетики им. В.М. Глушкова НАН Украины, - 2003.- №2. - С. 155-161.

Шарифов Ф.А. О некоторых подходах к решению задачи проектирования надежных сетей // Теория оптимальных решений. - Киев: Ин-т кибернетики им. В.М. Глушкова НАН Украины, 2002. - №1. - С. 13-20.

Шарифов Ф.А. О задаче атаки для семейства подмножеств // Доп. НАН України. - 2001. - №2. - С. 80-85.

Шарифов Ф.А. Субмодулярные функции в задачах синтеза сетей // Кибернетика и системный анализ. -2001. - №4. - С. 166-175.

Шарифов Ф.А. Задача синтеза надежных сетей с многими источниками и стоками // Теория оптимальных решений. - Киев: Ин-т кибернетики им. В.М. Глушкова НАН Украины, - 2001. - С. 16-22.

Шарифов Ф.А. Задача синтеза надежных сетей // Кибернетика и системный анализ. -2000. - №4. - С. 145-157.

Шарифов Ф.А. Задача проектирования сетей с одним источником // Тр. II Междунар. симп. «Проблемы математического моделирования, управления и информационных технологий в нефтегазовой промышленности.» Известия Ан Аз., Серия физико-технических и математических наук. -1998. - Т.1. - С. 212-214.

Шарифов Ф.А. Задача синтеза сети с независимыми путями // Оптимизация и ее приложения. - Киев: Ин-т кибернетики им. В.М. Глушкова НАН Украины. -1997. - С. 26 - 31.

Шарифов Ф.А., Прудкой Ю.И., Фигурская И.Л., Трубина Е.В. Задача синтеза интегрированных цифровых сетей // Методы решения экстремаль-ных задач. - Киев: Ин-т кибернетики им. В.М. Глушкова НАН Украины, 1996. - С. 10-14.

Шарифов Ф.А. Нахождение минимального разреза с использованием баз расширенного полиматроида // Кибернетика и системный анализ. - 1996. - №6. - С. 138-152.

Шарифов Ф.А. Минимальные разрезы в параметрической сети // Кибернетика и системный анализ -1994. - №6. - С. 114-121.

Трубин В.А., Шарифов Ф.А. Задача выбора специализации и состава оборудования поточных линий // Методы исследования экстремальных задач. - Киев: Ин-т кибернетики им. В.М. Глушкова АН Украины, 1994. - С. 8-12.

Sharifov F.A. Submodular function and design network problems // Abstracts. The International Conference on Applied Mathematics Dedicated to the 65-th Anniversary of B.N. Pshenichnyi. - Kyiv. - 2002, June 25-28. - P. 52.

Sharifov F.A. Minisum General Location Problem // U.S.-Ukrainian Workshop, Recent Advances in non-differentiale optimization, Program, Abstracts. - Kyiv. - 2000, May 15-18. - P. 32.

Sharifov F.A. Optimal disjoint perfect matchings on a pair of weghted bipartite graphs // Міжнародна школа-семинар Теорія прийняття рішень (праці школи-семінару), Ужгород - 2004. - С. 94.

Sergienko I.V., Sharifov F.A. Problem of design reliability telecommunication networks // Abstracts. Teleworking in research, medicine and business. - Kiev. - 2001, April. 29-21. - P. 6.

Sharifov F.A. Network Design Problem when Edges of Isomorphic Subgraph are Deleted // Proceedings. - Evry, Paris, France. - 2003, October 27-29.- P. 521-525.

Размещено на Allbest.ru