Застосування елементів теорії графів для рішення задачі розміщення пунктів обслуговування

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

Для того, щоб формулювати і розв'язувати задачі про розміщення, необхідно ввести нові поняття теорії графів:

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

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

Розглянемо типові практичні задачі, розв'язувані в межах теорії розміщень:

  1. Адміністрація регіону планує будівництво нового торгового центру, що має обслуговувати кілька районів. Центр вирішено розташувати біля якої-небудь магістралі таким чином, щоб мінімізувати відстань до найбільш віддаленої від нього точки.

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

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

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

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

Як видно, по суті розглянуті однакові задачі. Проте для рішення кожної з них необхідно вміти визначати різні числові характеристики побудованого для задачі графа.

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

Знаходження центру графа — приклад:

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

Центр графа - приклад

Зображення графа для розглядуваної задачі

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

Пісоя цього, для кожного рядка матриці , визначаємо елемент що містить максимальне значення:

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

Блок-схема алгоритму знаходження центру графа

Центр графа блок-схема

Матеріал був корисним, поділись в соціальних мережах:
Якщо тобі сподобалась дана тема, залиш свій коментар