Економіка/Математичні
методи в економіці
К.ф.м.н. Корольов
М.Є., студ. Нестеренко Ю.Ю.
Автомобільно-дорожній інститут ДНВЗ
«Донецький національний технічний університет»
Застосування
алгоритму побудови мінімального остового дерева відносно проекту розвитку
західного регіону Криму
Рада міністрів Криму
постановила задачу про розробку проекту розвитку західного регіону півострова.
Одним із підрозділів цього проекту є побудова мережі доріг з твердим покриттям,
що з’єднують населені пункти Знаменське, Окунівка, Мар’їно, Красносельське,
Оленівка з містом Чорноморське (рис.1). Необхідно спланувати найбільш
економічну дорожню мережу.
Не є виключенням
використання в даній задачі алгоритму побудови мінімального остового дерева.
Тож використаємо цю модель відносно проекту розвитку західного регіону Криму. Для
рішення даної задачі необхідно в першу чергу розглянути алгоритм побудови
мінімального остового дерева, що припускає з’єднання усіх вузлів мережі за допомогою шляхів найменшої
довжини. Опишемо процедуру виконання цього алгоритму.
Позначимо через N={1,2,…,n}множина вузлів мережі і введемо нові позначення [2]:
Ck — множина вузлів мережі, з'єднаних алгоритмом після
виконання k-ї ітерації цього
алгоритму,
— множина вузлів мережі, з'єднаних з вузлами безлічі Ck після виконання k-ї
ітерації цього алгоритму.
Крок
0. Думаємо C0 = 
і 
= N [3].
Крок1. Вибираємо будь-який вузол і з множини 
визначаємо
C1 = {i}, тоді 
= N-{i}. Думаємо k = 2.
Рисунок 1 – Існуюча дорожня мережа на західному регіоні
Криму
Умовні позначення: 1 –
Чорноморське; 2 – Знаменське; 3 – Окунівка;
4 – Мар’їно; 5 –
Красносельське; 6 – Оленівка.
Основний крок k. У множини 
вибираємо вузол j*, що
з'єднаний найкоротшою дугою з яким-небудь вузлом з множини Ck-1. Вузол j*
приєднується до множини Ck-1
і видаляється з множини 
. Таким чином,
Ck = Ck-1 + {j*}, 
= 
- {j*} [1].
Якщо множина 
порожня, то виконання алгоритму
закінчується. У противному випадку думаємо k
= k + 1 і повторюємо останній крок.
Почнемо
виконання алгоритму побудови мінімального остового дерева з вибором вузла 1.
Тоді C1 = {1} і = {2,3,4,5,6}.
Послідовні
ітерації виконання алгоритму представлені на рис.2. Тут тонкими лініями
показані ребра , що з'єднують вузли , які належать множинам Ck і 
, серед яких шукається ребро з мінімальною довжиною. Знайдене
ребро показане пунктирною лінією. Товстими суцільними лініями позначені ребра
з'єднуючі вузли множини Ck (і
які раніше позначалися пунктирними лініями) та вузли, що входять до множини Ck. Вузли, що входять до 
нанесені тонкими суцільними лініями.
Рисунок 2 – Послідовні ітерації виконання алгоритму
Наприклад
на першій ітерації ребро (1,2) має найменшу відстань між пунктами мережі серед
всіх інших ребер , що з'єднують вузол 1 з вузлами. Тому j=2 і C2={1,2}
,
={3,4,5,6,}. Інші ітерації виконуються аналогічно.
Рішення у виді
мінімального остового дерева отримано на 5-й ітерації (рис.2 ). Сума ребер на отриманому
мінімальному остовому дереві дорівнює:
9 +
11 + 8 + 5 + 16 = 49км.
Тож сумарна
мінімальна відстань, що з’єднує населені пункти Знаменське, Окунівка, Мар’їно,
Красносельське, Оленівка з містом Чорноморське складає 49км.
В цілому алгоритм
побудови мінімального остового дерева не характеризується значною трудомісткістю,
а тому знайшов широке використання серед проектування доріг, трубопроводів,
кабельної мережі та ін. Цей алгоритм дозволяє
створити таку мережу, де б мінімізувалася довжина шляхів, а сам проект в
цілому був би і економічним і ефективним.
Література:
1.
Шикин Е.В., Шикина Г.Є. Исследование операций. – М: ТК Велби,
Изд-во Проспект,
2006 – с. 21-28.
2.
Катренко А.В. Дослідження операцій:
Підручник. Видання третє, виправлене і доповнене. – Львів: «Магнолія» , 2009
– с118-122.
3.
Зайченко Ю.П. Исследование операций. Учебник. - 6
изд., перераб. и доп. К: Издательский Дом "Слово", 2003. – с.312-319.