ПРИКЛАД РІШЕННЯ ОПТИМІЗАЦІЙНОГО ЗАВДАННЯ

Задача.

Вирішити завдання оптимального розміщення обчислювальних центрів (ОЦ) і абонентських пунктів (АП) на території регіону з заданою площею. Вихідні дані для розрахунку:

- D,L - ширина й довжина регіону, обумовлена відповідно до площі регіону ( ). Приймаємо D=10, L=8 км;

- N=8000 - число абонентів мережі;

- =350 - капітальні витрати на установку одного ОЦ, тис. грн.;

- =15 - капітальні витрати на установку одного АП, тис. грн.;

- =20 - вартість 1 км каналу зв'язку між ОЦ, ;

- =10 - вартість 1 км каналу зв'язку між АП і ОЦ, ;

- =5 – питомі витрати на передачу обсягу інформації на одиницю довжини каналу зв'язку між ОЦ, ;

- W_S = 15000 - сумарні витрати на виробництво й обслуговування мережі, тис. грн.

Рішення.

1 Дамо рекомендації з вибору технічних засобів проектованої інформаційної мережі.

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

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

,

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

Для мережі з рівномірно розподіленим вартісним класом , з нього випливає ряд наступних співвідношень:

,

,

звідки вираження сумарних витрат:

.

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

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

2 Рішення завдання оптимального розміщення вузлів мережі.

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

Загальна схема розміщення ОЦ у мережі подана на рис. 2, де колами позначені зони дії кожного ОЦ.

Пошук R здійснюється у такий спосіб: на великому інтервалі із заданим кроком беруться точки (значення R). Виробляється підстановка R у вираження мінімізації витрат:

.

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

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

R={5,120 5,200 5,280 5,360 5,440 5,520 5,600 5,680 0,960 5,760 ...}.

Вибравши одне з найбільш відповідних значень R=5,12 км, знаходимо далі відповідному цьому значенню величини, що визначають оптимальний розподіл витрат для синтезованої мережі:

- - середня відстань між АП і ОЦ:

=1.81 км;

- n_yo - оптимальне число вузлів (ОЦ):

=7;

- n_АП - середнє число АП, приєднаних до кожного вузла:

=23,

де m - середнє число абонентів на 1 АП,

m=N/(n_yo n_АП)=50.

Після розрахунку основних параметрів необхідно приступитися до синтезу топології ІМ (рис Б.1.).

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

Рисунок Б.1 - Синтез топології ІМ

При рішенні поставленого завдання можна для пунктів розташування абонентів побудувати мінімальне покриваюче дерево, що забезпечує мінімальне значення сумарної довжини ліній передачі повідомлень між ОЦ, для цього застосовується, як правило, алгоритм Литтла [1]. У деяких випадках, коли задана вихідна матриця відстаней, вона може бути прийнята як вагові значення дуг.

Координати ОЦ відповідно до отриманої топологічної структури мережі зводимо до таблиці (табл. Б.1).

Таблиця Б.1 - Координати ОЦ

3 Проведемо найпростіший топологічний аналіз отриманої мережі.

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

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

Зазначимо функції вузлів у рамках прийнятої топології, як показано на рис. Б. 2 і визначимо обсяг оброблюваних запитів (вихідний розподіл потоків по дугах мережі) або обсяг інформаційно-обчислювальних робіт, виконуваних кожним ОЦ для групи абонентів, що належать до зони i-го ОЦ. Якщо визначити приналежність запитів до зони дії ОЦ у такий спосіб:

де - підмножина абонентів, що належать зоні i-го ОЦ, то обсяг запитів, що надходять в ОЦ із зони його дії, складе

Тоді, відповідно до прийнятої топології мережі й проведених раніше розрахунків, отримаємо:

Q₁=100; Q₂=50; Q₃=50; Q₄=50; Q₅=150; Q₆=150; Q₇=50.

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

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

У цьому випадку існує тільки один спрямований шлях, позначений жирною лінією. Тоді, мінімальна пропускна здатність M розрізу П-Ц дорівнює:

М_П-Ц = m_2-6 + m_6-1 = 100.

Це й відповідає максимальному потоку.

Ц - центр, П – периферія

Рисунок Б.2 - Функції вузлів проектованої мережі

4 Проведемо функціонально-вартісний аналіз мережі.

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

,

де , - витрати на виробництво і функціонування мережі відповідно.

Для цього будуються допоміжні матриці – матриця суміжності |Cм| і матриця відстаней |R|.

Матриця суміжності заповнюється з наступних міркувань:

- = 0, якщо немає зв'язку між вузлами i і j;

- = 1, якщо є зв'язок між вузлами i і j;

- = «-», якщо i = j.

Матриця суміжності |Cм|:

Матриця |R| показує відносну відстань між вузлами й заповнюється з наступних міркувань:

- = 0, якщо немає зв'язку між вузлами i і j;

- = , якщо є зв'язок між вузлами i і j,

де - відстань між вузлами i і j;

- = «-», якщо i = j.

Матриця відстаней |R|:

Результуючі витрати W ^/ виходять як сума капітальних витрат на установку АП і ОЦ, і капітальних витрат на прокладку каналів зв'язку

,

де:

- витрати на установку АП і ОЦ:

;

- витрати на проведення каналів зв'язку:

Отже,

W ^/ = 4865+3262,456=8127,456 тис. грн.

Визначимо витрати на функціонування мережі - .

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

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

.

Очевидно, що відстані між ОЦ будуть визначені з матриці відстаней |R|, питомі витрати W₅ задані, а середнє значення обсягу інформації, що циркулює між ОЦ, визначається обсягом запитів, що надходять до ОЦ із зони його дії - Q_i і було розраховано раніше, тоді:

Тобто, приведені витрати на створення й функціонування мережі будуть:

= 8127.456+4047.5=12174.956 тис.грн.

Висновок.

За умовою завдання, сумарні витрати не повинні перевищувати W_S = 15000 тис. грн. Очевидно, що сумарні витрати не перевищують розрахункові на виробництво й забезпечення функціонування мережі:

W_S > W,

15000>12174.956,

отже, вибір устаткування й розрахунки мережі зроблені коректно.