Главная | Обратная связь

Задачі мережевого аналізу

 

Мережевий аналіз спрямований на опрацювання даних лінійних об’єктів, які мають розгалужену (деревоподібну) структуру.

Класичні задачі мережного аналізу: оптимізація маршрутів (Знаходження найкоротшого чи найбільш вигідного маршруту) та обчислення “зон досяжності” в мережі.

 

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

 

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

 

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

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

Ребро(англ. Edge) – це лінія, що зв'язує точки (об'єкти графа). Ребра представляють відношення між об'єктами.

Вузол(англ. Node) – це вершина, загальна для двох і більшого числа дуг. У вузлах сходяться дуги.

Дуга(англ. Arc) – це ребро з певною орієнтацією (напрямком) відносно її кінцевих вершин.

Кількість вершин графа називають його порядком.

 

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

Маршрутом (або шляхом) у графі називається послідовність вершин v_i і ребер e_i така, що кожні два сусідні ребра в цій послідовності мають спільну вершину, отже, e_i=(v_i,v_{i +1}), i=1,2,…,k.

Вершина v₁ називається початком шляху, а вершина v_{k +1} - кінцем шляху. Всі інші вершини цього шляху називаються проміжними, або внутрішніми, вершинами.

 

Кількість k ребер у маршруті називається довжиною маршруту. Кажуть, що цей маршрут з’єднує вершини v₁ і v_{k +1} або веде з вершини v₁ у вершину v_{k +1}.

 

Маршрут, в якому всі ребра попарно різні, називається ланцюгом. Маршрут, в якому всі проміжні вершини попарно різні, називається простим ланцюгом.

 

Маршрут називається замкненим (або циклічним), якщо v₁=v_{k +1}. Замкнений ланцюг називається циклом, а замкнений простий ланцюг - простим циклом.

Граф, довільні дві вершини якого можуть бути з’єднані деяким маршрутом називається зв’язним. Інакше граф називається незв’язним.

Зв’язний граф що немає циклів називається деревом.

 

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

 

Цю задачу можна сформулювати ще так:

Нехай у місті М знаходиться кур’єрська служба і кур’єр повинен розвести листи в інші міста. Ясно, що є багато маршрутів об’їхати всі міста. Який з них буде найкоротший?

 

(тут розв’язок очевидний спочатку треба поїхати на пиво, а потім будь-який маршрут буде найкоротшим :)

 

Розглянемо граф що відповідає 5-ти населеним пунктам і кожні два пункти сполучені дорогою. Такий граф називають повним. Числа на лініях вказують відстані між пунктами по цих дорогах.

Для знаходження відповіді найпростіше проаналізувати всі варіанти за допомогою нового графу. Вверху вершина М – початок маршруту, з неї є 4 варіанти почати маршрут, далі для кожного з них буде по 3 варіанти продовження шляху, потім 2 потім в останнє місто і назад до М. Всього варіантів.

Запишемо біля кожного ребра відстань між пунктами а в кінці кожного маршруту їх суму – тобто його довжину. Тепер видно, що з отриманих 24-х варіантів два М-В-Б-А-Г-М та М-Г-А-Б-В-М будуть найменшими по 28 км. По суті це один і той же маршрут, пройдений у протилежних напрямках. (6+6+7+5+4=28).

 

(недоліком такого методу є швидке зростання кількості варіантів із збільшенням кількості міст) 5! = 120, 6! = 720, 10! = 3 628 800, а 20! – число що містить 19 позицій.

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

 

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