Page 120 - 4204

ЛЕКЦІЯ 8. ЗАДАЧІ МЕРЕЖЕВОГО АНАЛІЗУ З ЕЛЕМЕНТАМИ ТЕОРІЇ ГРАФІВ

пункті, оскільки сумарна відстань пройдена усіма учнями у цьому випадку

буде найменшою.

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

Модель даної задачі використовується у ситуаціях, коли пот-

рібно здійснити оптимальний вибір серед найбільш невдалих ва-

ріантів згідно з деяким критерієм (зменшення збитків, мінімізація

затрат та ін.)

Формулювання. Задана дорожня мережа, яка складається з

n вершин (населених пунктів), з’єднаних ребрами. Необхідно:

1) обчислити матрицю найкоротших відстаней між усіма пунк-

тами мережі;

2) використовуючи побудовану матрицю, знайти оптималь-

ний варіант розташування пожежної частини у одному з на-

селених пунктів.

Дана задача зводиться до відшукання центра відповідного

графа. В основу розв’язування задачі покладено таке міркування:

відстань від пожежної частини до найбільш віддаленого пун-

кту мережі повинна бути мінімальною. Подібні міркування на-

зивають принципом мінімаксу, а саму задачу – мінімаксною (за-

дачу про розміщення школи – мінісумною). Аналогічно

розв’язуються задачі про розміщення пунктів інших служб термі-

нового реагування (станції швидкої допомоги, служби охорони)

119