Загальна характеристика задач оптимізації

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

Загальна кількість можливих варіантів з’єднання n об’єктів між собою визначається сумою можливих варіантів з’єднання зазначених об’єктів по 2, по 3,..., по n, тобто

,

де - кількість розміщень з n об’єктів по k,

при цьому кожна пара об’єктів може бути з’єднана способами.

У табл. 1.1 надані значення у залежності від значень n = 2, 3,..., 10.

Таблиця 1.1. Залежність значень від значень n

n

 

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

Кажуть, що над подібними задачами тяжіє прокляття розмірності.

Дійсно, враховуючи, що , де – кількість сполучень з n об’єктів по k, тобто >> , а , значення >>2 ⁿ.

Втім, будемо вважати ≈ 2 ⁿ.

Про фантастичну величину числа 2¹²⁰ можна судити з таких міркувань.

Припустимо, що для розв’язання задачі оптимізації структури мережі поштового зв’язку використовується суперкомп’ютер, швидкодія якого 3·10¹⁰ операцій за секунду (це теоретична межа швидкодії комп’ютера у виді сфери діаметром 1 см, яка визначається лише часом розповсюдження електромагнітної хвилі від одного краю сфери до протилежного).

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

Подамо число у виді ≈ 2¹²⁰ ≈ 10³⁶. Тоді для розрахунку всіх можливих варіантів повинно бути витрачено 10³⁶/(3·10¹⁰) = 0,33·10²⁶ секунд або 10¹⁸ (мільярд мільярдів) років!

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

При побудові структури мережі поштового зв’язку за адміністративно-територіальним принципом в центрах відповідних адміністративних утворень України створюються об’єкти поштового зв’язку універсального призначення, ієрархічна підпорядкованість яких відповідає ієрархічній підпорядкованості зазначених адміністративних утворень: Україна (Головний вузол або Зональний вузо) – Область (Обласний вузол) – Район (Районний вузол) – Сільрада (Відділення зв’язку).

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

При переході від структури мережі поштового зв’язку, побудованої за адміністративно-територіальним принципом, до структури мережі поштового зв’язку, побудованої за функціонально-територіальним принципом, на території України передбачено створення поштових регіонів з Регіональними (міжобласними) вузлами поштового зв’язку, а на територіях поштових регіонів – поштових округів з Окружними (міжрайонними) вузлами поштового зв’язку.

На рис. 1.2 наведено співвідношення рівнів ієрархії мереж поштового зв’язку (а – мережі, побудованої за адміністративно-територіальним принципом, б – мережі, побудованої за функціонально-територіальним принципом).

 

Рисунок 1.2. Співвідношення рівнів ієрархії мереж поштового зв’язку

 

На рис. 1.3 наведено узагальнені структури мереж поштового зв’язку (а – мережі, побудованої за адміністративно-територіальним принципом, б – мережі, побудованої за функціонально-територіальним принципом).

 

		Зональні вузли     Обласні вузли     Районні вузли   Відділення зв’язку

 

 

 

 

 

а

 

 

б

Рисунок 1.3. Узагальнені структури мереж поштового зв’язку

 

В мережі поштового зв’язку, побудованій за адміністративно-територіальним принципом, об’єкти рівня ієрархії 1 (зональні вузли) з’єднуються між собою магістральними поштовими маршрутами; кожний об’єкт рівня ієрархії 1 (зональний вузол) з’єднується з усіма підпорядкованими йому об’єктами рівня ієрархії 2 (обласні вузли) зональними поштовими маршрутами; кожний об’єкт рівня ієрархії 2 (обласний вузол) з’єднується з усіма підпорядкованими йому об’єктами рівня ієрархії 3 (районні (міські) вузли) обласними поштовими маршрутами; кожний об’єкт рівня ієрархії 3 (районний (міський) вузол) з’єднується з усіма підпорядкованими йому об’єктами рівня ієрархії 4 (відділення зв’язку) районними (міськими) поштовими маршрутами.

В мережі поштового зв’язку, побудованій за функціонально-територіальним принципом, об’єкти рівня ієрархії 1 (регіональні вузли) з’єднуються між собою магістральними поштовими маршрутами; кожний об’єкт рівня ієрархії 1 (регіональний вузол) з’єднується з усіма підпорядкованими йому об’єктами рівня ієрархії 2 (окружні вузли) регіональними поштовими маршрутами; кожний об’єкт рівня ієрархії 2 (окружний вузол) з’єднується з усіма підпорядкованими йому об’єктами рівня ієрархії 3 (відділення зв’язку) окружними поштовими маршрутами.

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

Як випливає з рис. 1.3, пересилання пошти в мережі поштового зв’язку, побудованій за адміністративно-територіальним принципом, у найбільш несприятливому випадку здійснюється за схемою Відділення зв’язку – Районний вузол – Обласний вузол – Зональний вузол – Зональний вузол – Обласний вузол – Районний вузол – Відділення зв’язку (8 об’єктів, 7 маршрутів), а в мережі поштового зв’язку, побудованій за функціонально-територіальним принципом, – за схемою Відділення зв’язку – Окружний вузол – Регіональний вузол – Регіональний вузол – Окружний вузол – Відділення зв’язку (6 об’єктів, 5 маршрутів).

Таким чином, при переході від побудови мережі поштового зв’язку за адміністративно-територіальним принципом до побудови мережі поштового зв’язку за функціонально-територіальним принципом, максимальна кількість об’єктів поштового зв’язку, задіяних у пересиланні поштівок, скорочується з 8 до 6 (в 1,33 рази), а максимальна кількість поштових маршрутів, задіяних у цьому пересиланні, – з 7 до 5 (в 1,4 рази). Завдяки цьому суттєво зменшуються витрати на оброблення пошти, скорочується кількість поштових маршрутів, скорочується час пересилання пошти, спрощується синхронізація оброблення і перевезення пошти.

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

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

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

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