Модель «max-min» у задачах захисту об’єктів комунікаційних мереж
Проблема захисту об’єктів стратегічного значення зведена до задачі про максимальний потік/мінімальний переріз у мережі, яка розв’язана в середовищі MS Excel за допомогою вбудованого модулю математичної оптимізації. Цей підхід є ілюстрацією сучасної методики формування та прийняття відповідальних ріш...
Збережено в:
| Опубліковано в: : | Реєстрація, зберігання і обробка даних |
|---|---|
| Дата: | 2009 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Інститут проблем реєстрації інформації НАН України
2009
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/50404 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Модель «max-min» у задачах захисту об’єктів комунікаційних мереж / О.Г. Додонов, А.І. Кузьмичов // Реєстрація, зберігання і обробка даних. — 2009. — Т. 11, № 4. — С. 78-88. — Бібліогр.: 10 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-50404 |
|---|---|
| record_format |
dspace |
| spelling |
Додонов, О.Г. Кузьмичов, А.І. 2013-10-16T23:06:20Z 2013-10-16T23:06:20Z 2009 Модель «max-min» у задачах захисту об’єктів комунікаційних мереж / О.Г. Додонов, А.І. Кузьмичов // Реєстрація, зберігання і обробка даних. — 2009. — Т. 11, № 4. — С. 78-88. — Бібліогр.: 10 назв. — укр. 1560-9189 https://nasplib.isofts.kiev.ua/handle/123456789/50404 004.942.519.87(045) Проблема захисту об’єктів стратегічного значення зведена до задачі про максимальний потік/мінімальний переріз у мережі, яка розв’язана в середовищі MS Excel за допомогою вбудованого модулю математичної оптимізації. Цей підхід є ілюстрацією сучасної методики формування та прийняття відповідальних рішень із використанням апарату математичного і електронно-табличного моделювання. Проблема защиты объектов стратегического назначения сведена к задаче о максимальном потоке/минимальном разрезе в сети, которая решена в среде MS Excel с помощью встроенного модуля математической оптимизации. Этот подход является иллюстрацией современной методики формирования и принятия ответственных решений с использованием аппарата математического и электронно-табличного моделирования. The defense of strategic objects problem as a maximal flow/minimal cut in a network problem which is solved in the MS Excel by built-in module of mathematical optimization is interpreted. This approach is an illustration of modern method of forming and making responsible decisions with the use of mathematical and spreadsheet modeling. uk Інститут проблем реєстрації інформації НАН України Реєстрація, зберігання і обробка даних Методи захисту інформації в комп’ютерних системах і мережах Модель «max-min» у задачах захисту об’єктів комунікаційних мереж Модель «max-min» в задачах защиты объектов коммуникационных сетей «Max-Min» Model for a Defense of Communication Networks Objects Problems Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Модель «max-min» у задачах захисту об’єктів комунікаційних мереж |
| spellingShingle |
Модель «max-min» у задачах захисту об’єктів комунікаційних мереж Додонов, О.Г. Кузьмичов, А.І. Методи захисту інформації в комп’ютерних системах і мережах |
| title_short |
Модель «max-min» у задачах захисту об’єктів комунікаційних мереж |
| title_full |
Модель «max-min» у задачах захисту об’єктів комунікаційних мереж |
| title_fullStr |
Модель «max-min» у задачах захисту об’єктів комунікаційних мереж |
| title_full_unstemmed |
Модель «max-min» у задачах захисту об’єктів комунікаційних мереж |
| title_sort |
модель «max-min» у задачах захисту об’єктів комунікаційних мереж |
| author |
Додонов, О.Г. Кузьмичов, А.І. |
| author_facet |
Додонов, О.Г. Кузьмичов, А.І. |
| topic |
Методи захисту інформації в комп’ютерних системах і мережах |
| topic_facet |
Методи захисту інформації в комп’ютерних системах і мережах |
| publishDate |
2009 |
| language |
Ukrainian |
| container_title |
Реєстрація, зберігання і обробка даних |
| publisher |
Інститут проблем реєстрації інформації НАН України |
| format |
Article |
| title_alt |
Модель «max-min» в задачах защиты объектов коммуникационных сетей «Max-Min» Model for a Defense of Communication Networks Objects Problems |
| description |
Проблема захисту об’єктів стратегічного значення зведена до задачі про максимальний потік/мінімальний переріз у мережі, яка розв’язана в середовищі MS Excel за допомогою вбудованого модулю математичної оптимізації. Цей підхід є ілюстрацією сучасної методики формування та прийняття відповідальних рішень із використанням апарату математичного і електронно-табличного моделювання.
Проблема защиты объектов стратегического назначения сведена к задаче о максимальном потоке/минимальном разрезе в сети, которая решена в среде MS Excel с помощью встроенного модуля математической оптимизации. Этот подход является иллюстрацией современной методики формирования и принятия ответственных решений с использованием аппарата математического и электронно-табличного моделирования.
The defense of strategic objects problem as a maximal flow/minimal cut in a network problem which is solved in the MS Excel by built-in module of mathematical optimization is interpreted. This approach is an illustration of modern method of forming and making responsible decisions with the use of mathematical and spreadsheet modeling.
|
| issn |
1560-9189 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/50404 |
| citation_txt |
Модель «max-min» у задачах захисту об’єктів комунікаційних мереж / О.Г. Додонов, А.І. Кузьмичов // Реєстрація, зберігання і обробка даних. — 2009. — Т. 11, № 4. — С. 78-88. — Бібліогр.: 10 назв. — укр. |
| work_keys_str_mv |
AT dodonovog modelʹmaxminuzadačahzahistuobêktívkomuníkacíinihmerež AT kuzʹmičovaí modelʹmaxminuzadačahzahistuobêktívkomuníkacíinihmerež AT dodonovog modelʹmaxminvzadačahzaŝityobʺektovkommunikacionnyhsetei AT kuzʹmičovaí modelʹmaxminvzadačahzaŝityobʺektovkommunikacionnyhsetei AT dodonovog maxminmodelforadefenseofcommunicationnetworksobjectsproblems AT kuzʹmičovaí maxminmodelforadefenseofcommunicationnetworksobjectsproblems |
| first_indexed |
2025-11-26T15:00:47Z |
| last_indexed |
2025-11-26T15:00:47Z |
| _version_ |
1850625534237605888 |
| fulltext |
Методи захисту інформації
в комп’ютерних системах і мережах
78
УДК 004.942.519.87(045)
О. Г. Додонов1, А. І. Кузьмичов2
1Інститут проблем реєстрації інформації НАН України
вул. М. Шпака, 2, 03113 Київ, Україна
e-mail: dssd@ipri.kiev.ua
2Академія муніципального управління МОН України
вул. І. Кудрі, 33, 01601 Київ, Україна
e-mail: akuzmychov@mail.ru
Модель «max-min» у задачах захисту
об’єктів комунікаційних мереж
Проблема захисту об’єктів стратегічного значення зведена до задачі
про максимальний потік/мінімальний переріз у мережі, яка розв’язана
в середовищі MS Excel за допомогою вбудованого модулю математич-
ної оптимізації. Цей підхід є ілюстрацією сучасної методики форму-
вання та прийняття відповідальних рішень із використанням апарату
математичного і електронно-табличного моделювання.
Ключові слова: комунікаційна мережа, максимальний потік, мінімаль-
ний переріз, електронно-табличне моделювання, математична опти-
мізація в MS Excel.
Вступ
У світовій безпековій практиці надзвичайно актуальним став клас потокових
задач про моніторинг, перевірку та контроль і, за необхідності, накладення забо-
рони (network interdiction, [1]) руху чи передачі даних ділянками комунікаційної
мережі з метою обмеження доступу будь-якими шляхами — каналами зв’язку, за-
лізницею, дорогами, повітрям, водою чи навіть бездоріжжям — до стратегічних
об’єктів (коротко — до критичної інфраструктури [2]).
Прикладами практичних ситуацій, де виникають мережні задачі про захист,
заборону чи обмеження доступу є:
— захист адміністративних і бізнес-центрів, стратегічних джерел постачання
харчовими продуктами чи енергоресурсами від терористичних атак [3];
— реєстрація та локалізація у звичайних чи труднодоступних місцевостях та,
особливо, на обширних територіях місць збирання, накопичення, виготовлення,
зберігання, доставки нелегальними маршрутами й розповсюдження контрабанди,
зброї чи наркотиків;
— заборона нелегального перетину будь-яких кордонів;
© О. Г. Додонов, А. І. Кузьмичов
Модель «max-min» у задачах захисту об’єктів комунікаційних мереж
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2009, Т. 11, № 4 79
— перекриття каналів руху небезпечних потоків води, транспортних засобів,
шкідливих речовин, груп людей, вогню, інформаційних матеріалів тощо.
Обмеженість спеціальних кадрових, часових і технічних ресурсів для якісно-
го і своєчасного моніторингу, здійснення контрольних чи заборонних функцій у
мережі відносить ці задачі до класу потокових моделей про оптимальне викорис-
тання обмежених ресурсів шляхом пошуку «болючих точок» і «вузьких місць»
для адресного направлення саме до них ефективних ресурсних комплектів (ко-
манд, засобів).
Серйозність, складність та актуальність цієї проблематики пояснюється тим,
що великі розміри реальних територій і комунікацій місцевого, регіонального чи
державного значення, які з часом лише збільшуються й ускладнюються, розмаїття
ресурсів спеціального призначення та їхніх властивостей формують безліч поста-
новок задач та їхніх модифікацій, тож виникає необхідність побудови спеціально-
го класу відповідних математичних моделей, пошуку раціональних способів опе-
ративної підготовки, редагування й уведення початкових даних, розробки ефекти-
вних обчислювальних алгоритмів і використання доступних комп’ютерних засо-
бів їхньої практичної реалізації й не в університетських наукових лабораторіях,
обладнаних унікальними суперкомп’ютерами і забезпечених кваліфікованим пер-
соналом, а безпосередньо на командних пунктах для оперативного прийняття та
супроводження процесу реалізації відповідальних організаційних і управлінських
рішень.
Предметна область дослідження — комунікаційна мережа — вже пропонує
для моделювання й розв’язання таких задач розвинений апарат потокового про-
грамування [4–6], який базується на математичній теорії графів. Адже будь-яка
географічна чи інша карта є наявною графічною, тобто, наочною і зрозумілою,
моделлю досліджуваного об’єкта, за якою будується відповідна аналітична і роз-
рахункова потокова математична модель, результат її комп’ютерної реалізації від-
творюється на тій же карті у вигляді конкретних місць, куди треба направити ре-
сурси у визначених кількостях оптимальними шляхами.
Існує два підходи до комп’ютерного моделювання практичних задач про по-
токи у мережах — спеціалізований та універсальний.
Спеціалізований підхід
У початковий період технології прийняття рішень за результатами комп’ю-
терного моделювання (60-ті роки ХХ ст.), коли комп’ютери (ЕОМ) мали вкрай
обмежені експлуатаційні можливості, класичні моделі лінійного програмування
матричного типу, до яких зводяться потокові моделі, вимагали для своєї реалізації
значно більше машинних ресурсів (пам’яті й швидкодії процесора), ніж було до-
ступно, тому в класичній роботі [4] вперше було запропоновано досить економ-
ний алгоритм переборного типу для фундаментальної потокової моделі під на-
звою «Задача про максимальний потік/мінімальний переріз», який, як і тоді, так і
зараз, звичайно реалізується у вигляді спеціалізованої програми, що створює і су-
проводжує штат професійних математиків-програмістів відповідними мовними
засобами на конкретне замовлення.
О. Г. Додонов, А. І. Кузьмичов
80
Універсальний підхід
Для сучасних потужних і доступних ПК тепер застосовується інша технологія
організації модельних розрахунків, розрахована на її масове застосування рядо-
вими користувачами — це проста, доступна й універсальна реалізація потокової
моделі симплекс-методом лінійного програмування за допомогою стандартної чи
промислової версії програми-надбудови Solver Excel (Поиск решения), що екс-
плуатується з 1991 р. [7], де не ставляться серйозні умови щодо математичної й
програмістської підготовки користувача.
Цей підхід до здійснення комп’ютерного моделювання визначених вище ти-
пів потокових задач набув найбільшого поширення в бізнес-освіті [8–10] й поки
що мало відомий в Україні серед практиків (ОПР — осіб, що приймають рішен-
ня), тож саме він пропонується нами на прикладі розв’язання типової потокової
задачі про максимальний потік/мінімальний розріз.
Задача про максимальний потік/мінімальний переріз («max-min»)
Об’єкт дослідження — комунікаційна мережа — задана певними «точкови-
ми» пунктами (це — окремі об’єкти, міста, станції, перехрестя доріг) та ділянками
шляхів між ними. Мовою теорії графів ділянки називають дугами, а пункти — ву-
злами. Цими дугами від вузла до вузла передаються потоки (людей, техніки, про-
дуктів, ресурсів, інформації), які вимірюються у відповідних одиницях (т, шт.,
чол., грн., м3, Мб). Реальна мережа зображується картою, а її спрощений проблем-
но-орієнтований варіант — картосхемою (рис. 1).
Рис. 1. Географічна карта та картосхема мережі
Модель «max-min» у задачах захисту об’єктів комунікаційних мереж
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2009, Т. 11, № 4 81
Залежно від кількості типів об’єктів, що одночасно передаються дугами, роз-
різняють одно- та багатопродуктові потоки, а мережа може бути одно- та багато-
полюсною, тобто, мати по одному загальному входу (вузол-джерело, єдиний по-
стачальник) та одному виходу (вузол-стік, єдиний споживач) чи входів і виходів
буде більше одного.
У класичній постановці задана однополюсна мережа з m вузлів та n дуг, де є
один вузол-джерело s, один вузол-стік t, усі інші вузли — проміжні (транзитні), d
— інтенсивність (потужність) джерела s, яка є невідомою, зрозуміло, що інтенсив-
ність стоку дорівнює –d (бо «скільки увійшло, стільки й вийшло»). Шукана вели-
чина d — максимальний потік, який може пропустити через себе мережа. Кожна
i-та дуга (i = 1,…, n) характеризується пропускною здатністю рі.
У розширеній постановці, що відповідає практичним задачам захисту, мережа
є багатополюсною, бо має кілька джерел і стоків, що з’єднуються між собою пев-
ними шляхами.
Переріз — множина дуг, видалення яких відокремлює s від t, величина пере-
різу — сума пропускних здатностей дуг, що йому належать. Переріз , що має
найменшу пропускну здатність, називається мінімальним. Доведено [4], що вели-
чина максимального потоку з джерела s до стоку t дорівнює пропускній здатності
мінімального перерізу: max d =
i
ip . Отже, якщо пропускна здатність дуги фун-
кціонально відповідає кількості ресурсу для її перекриття, значить, треба знайти
мінімальний переріз, який покаже, які дуги треба «перерізати» й скільки ресурсу
для цього знадобиться. Ця задача є двоїстою до задачі про пошук максимального
потоку. Тож, якщо NS — множина «ворожих» вузлів, з яких планується атака на
множину вузлів-цілей NT, тоді є зрозумілим алгоритм розв’язання задачі про по-
шук мінімальної кількості засобів для захисту NT.
Числові характеристики, що визначають шуканий результат (це — невідомі
дугові потоки, тобто, обґрунтована й зважена відповідь на запитання «звідки-
куди-скільки» передається), стосуються кожної з дуг, це, у першу чергу, її пропу-
скна здатність та, можливо, певний ваговий коефіцієнт, один чи декілька, що за-
лежить від пропускної здатності й враховується в розрахунках.
Для задачі, що розглядається, найважливішою характеристикою дуги є її
пропускна здатність, фактично, це ресурсні вимоги, необхідні для її повного пере-
криття (інакше, для автоматичної реєстрації чи явної перевірки усіх засобів, хто
рухаються ділянкою). Наприклад, для ділянки (4, 8) величина потрібного ресурсу
для повної заборони руху нею складає r48 = 7, тож, якщо визначено оптимальний
потік для неї х48 = 1 (не повне перекриття), значить, вона потребує й повністю ко-
нтролюється 7-ма одиницями ресурсу, ця величина (7) увійде в загальну суму ви-
трачених ресурсів, що мінімізується, якщо ж виходить, що х48 < 1, тоді ділянка (4,
8) вимушено контролюється лише частково меншим числом ресурсів.
У загальному випадку вузли у складі моделі «пасивні» чи «прості», бо лише
фіксують умову балансу потоків у них за принципом — який потік увійшов, такий
і вийшов, тобто, у них реалізуються функції, лише обмежуючі величину потоку.
Якщо ж необхідно явно задати потокові характеристики для певного «непросто-
го» вузла (наприклад, транзит крупним чи старовинним містом за тривалістю мо-
жна прирівняти до руху певною ділянкою, тож для такого «непростого» вузла
О. Г. Додонов, А. І. Кузьмичов
82
треба задати його пропускну здатність чи тривалість переїзду), такий вузол замі-
нюють парою «простих» вузлів і дугою між ними з відповідними характеристи-
ками — тепер ця дуга є моделлю відповідного «непростого» вузла.
У потокових задачах безпекового типу для зручності вузли-джерела з множи-
ни NS вважаються «зовнішніми» пунктами організації атак, направлених на «вну-
трішні»1 вузли-стоки з множини NT, що разом із відповідними дугами між ними
утворюють критичну інфраструктуру і яку треба захистити, бо атаки здійснюють-
ся рухом атакуючих сил ланцюгами «джерелапроміжні ділянкистоки» мере-
жі. Перекриття руху будь-яким ланцюгом здійснюється перекриттям конкретної
ланки цього ланцюга в певному чи будь-якому довільному її місці, на що витра-
чаються певні ресурси у заданій кількості при задоволенні обмеження на їхню за-
гальну кількість.
Отже, для задачі про максимальний потік/мінімальний переріз («max-min»)
задана мережа
М = {G, P},
де G = {N, A} — орієнтований граф у вигляді сукупності вузлів (N, nodes) та дуг
(A, arcs); P = {p(А)} — масив вагових коефіцієнтів дуг (пропускних здатностей
дуг), цей основний масив може бути доповненим іншими масивами, зокрема, кі-
лькостями ресурсу (ресурсів), необхідного для повного перекриття дуги.
Ресурсами можуть бути: технічні засоби, обслуговуючий чи оперативний пер-
сонал, час, необхідний для здійснення контрольних чи заборонних операцій.
Згідно теорії лінійного програмування (ЛП) задача про максимальний потік
називається прямою, її результат — усі дугові потоки xi, що рухаються з джерел
до стоків, сума цих потоків максимальна. Задача про мінімальний переріз є двоїс-
тою (спряженою до прямої), її результат — сукупність дуг, що утворюють міні-
мальний переріз, скорочена назва математичної задачі й відповідної моделі —
«max-min».
У цій моделі необхідно визначити:
1) пряму задачу:
— потоки кожною дугою;
— рівень насиченості дуг (наприклад, у %);
— потоки через кожен вузол;
— максимальну пропускну здатність комунікаційної мережі;
2) двоїсту задачу:
— мінімальний переріз («вузьке місце») у вигляді множини дуг, видалення
яких повністю перекриває рух з початкових вузлів (джерел) до кінцевих вузлів
(стоків);
— кількість необхідних ресурсів (це максимальна пропускна здатність мере-
жі).
1 Це досить умовна термінологія, адже джерело географічно може бути розташоване у середині
мережі, а об’єкти-цілі — ззовні його, наприклад, терористи базуються у горах всередині регіону й
атакують об’єкти, що розташовані на прикордонних ділянках.
Модель «max-min» у задачах захисту об’єктів комунікаційних мереж
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2009, Т. 11, № 4 83
Класичний підхід до розв’язання задачі max-min передбачає зведення реаль-
ної багатополюсної мережі до однополюсного варіанту (1, 1), де додатково уво-
дяться фіктивні зовнішні вузли-полюси: Вхід (узагальнене джерело) і Вихід (уза-
гальнений стік), а усі направлені зв’язки між цими полюсами та із заданими вхід-
ними (на рис. 2 їх три) й вихідними вузлами (два) мають нульові характеристики
(рис. 2).
Цей підхід змушено збільшує розмір задачі, ускладнює підготовку початко-
вих даних і певним чином робить таку модель дещо штучною. Нами пропонується
реалізація багатополюсного варіанта, у прикладі (3, 2)-полюсної мережі, де моде-
люється задана мережа (на рис. зафарбована) без будь-яких допоміжних перетво-
рень і додавань.
Рис. 2. Однополюсний варіант (3, 2)-полюсної мережі
Приклад. На території України комунікаційна мережа представлена змішаним
графом G = (A, N), що складається з 40 дуг та 25 вузлів (рис. 3).
Множина А усіх 40 заданих дуг А = {A1, A2, А3}, це:
А1 — підмножина орієнтованих дуг-стрілок, що зв’язують вхідні (джерела) і
вихідні (стоки) вузли з проміжними вузлами, їх всього 34;
А2 — 20 дуг у складі А1 зв’язують вхідні вузли з усіма іншими (сума потоків
ними визначає пропускну здатність мережі, тобто, цільову функцію, що максимі-
зується);
А3 — підмножина неорієнтованих дуг-ліній між певними проміжними вузла-
ми, їх 6: (ВінницяЖитомир), (ВінницяХмельницький), (Хмельниць-
кийЖитомир), (СумиХарків), (ДніпропетровськЗапоріжжя) та (Івано-
ФранківськТернопіль); рух ними можливий в обох напрямках, вибір кращого з
цих двох — додатковий шуканий результат.
Множина N з 25 вузлів N = {NS, NP, NT}, це:
NS — 8 «зовнішніх» (вхідних) вузлів-джерел, з яких організується атака (пря-
мокутники);
NP — 13 проміжних (транзитних) вузлів, через які проходять шляхи атакую-
чих сил (чорні кружечки);
NT — 4 «внутрішніх» (вихідних) вузла-стоків, на які направлена атака (по-
двійні кружечки).
Оскільки граф G з позиції орієнтації дуг змішаний, його треба представити у
вигляді мережі — орієнтованого зваженого графа, для цього 6 неорієнтованих дуг
О. Г. Додонов, А. І. Кузьмичов
84
(А3) замінюють парами направлених назустріч дуг з однаковими пропускними
здатностями. В результаті маємо багатополюсну (8 входів і 4 виходи) мережу
М(25, 46) з 25 вузлів і 46 орієнтованих дуг. Якщо б ми користувалися класичним
способом потокового програмування, треба б було ще додати 2 фіктивних вузли
(Вхід, Вихід) і з’єднати їх 12 дугами з 8 вхідними й 4 вихідними вузлами, тоді б
мали мережуМ(27, 58), що певним чином ускладнює процес розв’язання задачі.
Класичний спосіб ЛП представляє потокову задачу у вигляді прямокутних
матриць типу: «вузол-вузол» розміром 2525 (більше 600 невідомих) або «вузол-
дуга» розміром 2546 (більше 1000 невідомих), який є нереальним для практики,
то ж ми використовуємо для представлення мережі економну спискову структуру
даних з 46 невідомими.
NS NP NT
Рис. 3. (8, 4)-полюсна мережа
Модель «max-min» у задачах захисту об’єктів комунікаційних мереж
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2009, Т. 11, № 4 85
Отже, моделюється мережа М (25, 46). Для потоків від початкових вузлів че-
рез проміжні до кінцевих вузлів існують шляхи у вигляді направлених ланцюгів,
ланки яких утворюють суміжні дуги-стрілки. Відповідна математична модель
прямої потокової задачі ЛП (на максимум) складається з 46 невідомих величин
(дугові потоки) та 25 обмежень на їх значення (баланс у вузлах). Для двоїстої за-
дачі (на мінімум) навпаки — треба знайти 25 невідомих (потенціали вузлів) із вра-
хуванням 46 обмежень (для дугових потоків).
Зовнішні умови, що враховують специфічні властивості задачі, представля-
ються відповідними додатковими обмеженнями — це дещо ускладнює модель,
зате робить її ближчою до реального стану об’єкта, що досліджується.
Математична модель
Позначення:
m — кількість направлених дуг (невідомих);
i — поточний номер дуги (потоку), i = 1, …, m;
n — кількість вузлів (обмежень);
j – поточний номер вузла, j = 1, …, n;
(n, m) — розмір потокової задачі;
Fвх — загальний вхідний потік з усіх джерел;
Fвих — загальний вихідний потік в усі стоки;
xi — величина потоку і-ю дугою, X = {xі} — шуканий план прямої задачі;
pi — пропускна здатність і-ої дуги;
yj — двоїста оцінка вузла, Y = { yj} — шуканий план двоїстої задачі;
Fвх(j) — сума вхідних потоків у j-й вузол;
Fвих(j) — сума вихідних потоків з j-го вузла;
d — величина максимального потоку (мінімального перерізу) мережі.
Задача потокової оптимізації
Пряма задача (про максимальний потік).
І. Знайти вектор X = {xі}, такий, щоб
ІІ. d =
Ai
ix max (ЦФ), де А — множина дуг мережі.
ІІІ. за обмежень:
(3.1) хі pi (для кожної і-ї дуги, у прикладі усі pi = 1);
(3.2) Fвх(j) — Fвих(j) = 0 (умова збереження потоку для кожного j-го вузла);
(3.3) Fвих = Fвх (для мережі) та граничних умов: усі хі 0.
Двоїста задача (про мінімальний переріз).
І. Знайти вектор Y = {yj}, такий, щоб
ІІ.
Ai
ii py min (ЦФ)
ІІІ. за обмежень:
(3.1) yj {0, 1} (для кожного j-го вузла)
(3.2) Fвих(j) = Fвх(j) (умова збереження потоку для кожного j-го вузла)
(3.3) Fвих Fвх (для мережі) та граничних умов: усі yj 0.
О. Г. Додонов, А. І. Кузьмичов
86
Електронно-таблична (ЕТ) модель
На рис. 4 представлено табличний документ з початковими даними і резуль-
татами обчислень для прямої та двоїстої потокової задачі про максимальний по-
тік/мінімальний переріз симплекс-методом ЛП, до нього додана схематична ілюс-
трація (рис. 5).
Рис. 4. ЕТ-модель задачі «max-min»
Модель «max-min» у задачах захисту об’єктів комунікаційних мереж
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2009, Т. 11, № 4 87
Оскільки мережа складається з двох об’єктів: вузлів і дуг, відповідна ЕТ-
модель складається з двох таблиць: для вузлів і для дуг.
Алгоритм
1. Ввести початкові дані (назви 25 вузлів); рекомендується скомпонувати їх у
3 групи згідно моделі: NS (8 вузлів, NT (4 вузла) та NP (13 вузлів), для зручності
перенумерувати і виділити групи вузлів кольором чи шрифтом, так формується
таблиця для вузлів.
2. З цих назв зв’язуванням сформувати 46 пар дуг (Початок-Кінець) згідно
конфігурації мережі; рекомендується скомпонувати ці пари у 3 групи: A1 (20 вхід-
них дуг, потоки якими визначать пропускну здатність мережі); A2 (14 орієнтова-
них дуг); А3 (множина з 6 пар, всього 12 неорієнтованих дуг), перенумерувати і
виділити групи дуг кольором чи шрифтом.
3. У таблиці для вузлів у стовпці Вхід обчислюються суми вхідних потоків у
кожен вузол (Fвх(j)), у стовпці Вихід — суми вихідних потоків з кожного вузла
(Fвих(j)), а у стопці Вх-Вих — їхня алгебраїчна сума.
4. Обчислення лівих (ЛЧО) і правих (ПЧО) частин обмежень для вузлів, ЛЧО
— це сума потоків з 8 вхідних вузлів (Fвх), а ПЧО — сума потоків у 4 вихідні вуз-
ли (Fвих).
5. Обчислення значення цільової функції — суми потоків з 8 вхідних вузлів
6. Запуск програми «Поиск решения»; заповнення полів вікна програми.
7. Для зручності діапазонам клітинок рекомендується надати змістовні імена,
де: МаксПЗ — максимальна пропускна здатність (ЦФ); Потік — шуканий план;
Баланс — значення Вх–Вих для проміжних вузлів.
8. Після отримання результату побудувати звіт зі стійкості плану (Устойчи-
вость) для визначення мінімального перерізу (нормовані вартості для невідомих
та тіньові ціни для вузлів).
9. Модифікація моделі: додавання обмежень, зміна початкових даних, дослі-
дження впливу певного параметру на кінцевий результат.
а) б)
Рис. 5. Розв’язок задачі «max-min»:
а) максимальний потік (25 дуг); б) мінімальний переріз (13 дуг)
О. Г. Додонов, А. І. Кузьмичов
88
Висновок: запропонований підхід до потокового моделювання в доступному
й ефективному середовищі MS Excel дає змогу проводити аналіз складних ситуа-
цій і формувати на його основі зважені й обґрунтовані управлінські рішення.
1. Wood K. Deterministic Network Interdiction / K. Wood // Mathematical and Computer Model-
ing. — 1993. — Vol. 17.
2. Brown G. Defending Critical Infrastructure / G. Brown, M. Carlyle, J. Salmeron, K. Wood // In-
terfaces. — 2006. — Vol. 36.
3. Salmeron J. Analysis of Electric Grid Security Under Terrorist Threat / J. Salmeron, K. Wood,
R. Baldick // IEEE Transactions on Power Systems. — 2004. — Vol. 19.
4. Ford L.R. Flows in Networks / L.R. Ford, D.R. Fulkerson. — Princeton University. — NJ, 1962;
пер. рос. Форд Л., Фалкерсон Д. Потоки в сетях. — М.: Мир, 1966.
5. Brown G. Solving Generalized Networks / G. Brown, R. McBride // Management Science. —
1984. — Vol. 30.
6. Anderson L. Application of the Maximum Flow Problem to Sensor Placement on Urban Road
Networks for Homeland Security / Anderson L., Atwell R., Barnett D., Bovey R. — Homeland Security
Affairs. — 2007. — Vol. I.
7. Fylstra D. Design and Use of the Microsoft Excel Solver / D. Fylstra, L. Lasdon, J. Watson, A.
Waren // Interfaces, 1998.
8. Moore J.H. Decision modeling with Microsoft Excel / J H. Moore, L.R. Weatherford. — Pren-
tice Hall, 2001; пер. рос. Мур Дж., Уэдерфорд Л. Экономическое моделирование в Microsoft Excel.
— 6-е изд. — М.: «Вильямс», 2004.
9. Кузьмичов А.І. Лінійні задачі математичного програмування в MS Excel: навч. пос. / А.І.
Кузьмичов, М.Г. Медведєв. — К.: АМУ, 2006.
10. Kuzmychov A. Operations Research: Optimization models for Decision-making: навч. пос. / А.
Kuzmychov. — К.: АМУ, 2007.
Надійшла до редакції 06.10.2009
|