Page 112 - 4204

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

ріанти розпочати маршрут, далі для кожного з них буде по 3 варіанти

продовження шляху, потім лише 2 варіанти, і нарешті – в останнє місто

й назад до пункту M . Всього буде 4 3 2 1  24  ! 4 варіантів.

Запишемо біля кожного ребра відстань між пунктами а в кінці кож-

ного маршруту їх суму – тобто його довжину. Тепер видно, що з отрима-

них 24-х маршрутів два з них М-В-Б-А-Г-М та М-Г-А-Б-В-М будуть мати

найменшу довжину (по 28 км). По суті це один і той самий маршрут,

пройдений у протилежних напрямках. (6+6+7+5+4=28).

Недоліком методу перебору варіантів є те, що потрібно

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

із збільшенням числа міст n: 5! = 120, 6! = 720, 10! = 3 628 800, а

20! – число, що містить 19 позицій. Тому для великих n задача

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

комп’ютерних програм.

Подібні задачі часто виникають при проектуванні маршрутів

розвезення товарів по магазинам, матеріалів по будівництвам і

т. д. Причому критерієм оптимальності крім відстані між

об’єктами може бути, час або вартість подорожі.

8.3. Задача про найдешевшу транспортну мережу (побу-

дова графа найменшої довжини)

Велике практичне значення має наступна задача, яку можна

сформулювати на прикладі проведення доріг. Маємо декілька

міст M , M ... , , M , які потрібно з’єднати між собою мережею
2
n
1
доріг. Для кожної пари міст M M відома вартість будівництва
i j

111