17.3. Відповідь. Найвигідніше розмістити школу у четвертому населеному пункті. Сума відстаней, пройдених всіма учнями при цьому буде мінімальною і становитиме 9650 кілометрів.

Тема 18 Задача про розміщення пожежної частини

18.1. Завдання. Задана дорожна мережа, яка складається з дев’яти вершин, з’єднаних ребрами (завдання до теми 17). Необхідно:

1. розрахувати матрицю найкоротших відстаней між пунктами мережі, використовуючи алгоритм Флойда, або ж метод перебору варіантів;

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

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

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

18.2. Приклад розв’язування

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

1. розміщення пожежної частини у населеному пункті;

2. розміщення пожежної частини поза населеним пунктом.

Тому необхідно проаналізувати обидва варіанти, а потім вибрати кращий з них.

18.2.1. Задача про розміщення пожежної частини у населеному пункті.

Ця задача зводиться до задачі про побудову матриці найкоротших відстаней між вершинами графа. Розглянемо дорожну мережу, яку ми вже розглядали у темах 15 – 17. Матриця найкоротших відстаней має вигляд:

	1	2	3	4	5	6	7	8	9	max
1	0	31	55	38	62	58	52	49	60	62
2	31	0	24	55	38	27	48	60	49	60
3	55	24	0	31	22	33	32	42	53	55
4	38	55	31	0	24	35	14	11	22	55
5	62	38	22	24	0	11	10	35	33	62
6	58	27	33	35	11	0	21	33	22	58
7	52	48	32	14	10	21	0	25	36	52
8	49	60	42	11	35	33	25	0	11	60
9	60	49	53	22	33	22	36	11	0	60

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

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

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

Нижня оцінка віддаленості ребер від найдальшої вершини.

Р

Рис.9. Розміщення пожежної частини на ребрі мережі

озглянемо ребро (ij), що з’єднує вершини i та j, а також деяку іншу вершину k. Нехай x – координата ( відстань від вершини i ) пожежної частини u на ребрі (ij). Відстань від вершини j до пожежної частини дорівнює d_ij – x ( d_ij – довжина ребра (ij) ). Оптимальний маршрут від u до k визначається з умови d_uk = min ( x+d_ik, d_ij-x+d_jk ). Найменше значення (нижня оцінка) цієї відстані визначається з умови

.

Отже, ми повинні переглянути всі вершини k  i,j. Для кожної з них необхідно визначити величину і потім вибрати найбільшу з них. Це і буде нижня оцінка найбільш віддаленого пункта у випадку розташування пожежної частини на ребрі (i,j). Розглянуту операцію необхідно повторити для всіх ребер і вибрати з усіх нижніх оцінок найменшу. Це і буде ребро, на якому найдоцільніше розташувати пожежну частину.

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

Таблиця 9. Таблиця нижніх оцінок віддаленості ребер від найдальшої вершини

ребро	(1,2)	(1,4)	(2,3)	(2,6)	(3,4)	(3,5)	(4,7)	(4,8)	(5,6)	(5,7)	(6,9)	(7,8)	(8,9)
	49	35	49	35	38	55	48	55	58	52	58	49	49

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

= max(min(55,24), min(38,55), min(62,38), min(58,27), min(52,48), min(49,60), min(49,60) ) = max( 24,38,38,27,48,49,49) = 49.

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