Page 209 - 4685

Приклад. Нехай є п'ять пунктів, сполучених між собою дорогами так, що з
будь-якого пункту можна проїхати в будь-який інший пункт. Відомий час
перевезення з пункту i в пункт j:

З В пункт j
пункту і
1 2 3 4 5
1 0 10 25 25 10
2 1 0 10 15 2
3 8 9 0 20 10
4 14 10 24 0 15
5 10 8 25 27 0

Потрібно знайти такий маршрут, що починається в даному пункті,
проходить через всі пункти і закінчується в пункті виїзду, щоб його тривалість
була найменшою.
Рішення. Введемо позначення: i, j – номери пунктів виїзду і в'їзду; t – час
ij
переїзду з пункту i в пункт j (t в загальному випадку може не дорівнювати часу
ij
переїзду у зворотному напрямі, ' ≈ ' наприклад, коли один пункт на вершині
=
=
гори, а інший – біля її підніжжя). Введемо булеві змінні:
_ = 1, якщо з пункту i торговець переїде в пункт j; 0, якщо не поїде.
=
Складемо модель:

З п. 1 можна виїхати в будь-який з пунктів (2 або 5, або 3, або 4), або
залишитися в п. 1. Але при цьому можна виїхати лише в одному єдиному
напрямі. Цю умову можна записати так:
b
_ !! + _ ![ + _ !` + _ !a + _ !b = 1 або ; _ != = 1
=!
або для довільного (будь-якого) i-го пункту:
b
; _ = 1 A = 1, … 5
!=
=!
Ці залежності забезпечують виконання умови, що з кожного пункту виїзд
здійснюється лише один раз і лише в одному напрямі.
Умова в'їзду в п. 1 аналогічна умові виїзду з п. 1. Вимога мінімальної
тривалості маршруту запишеться у вигляді цільової функції:
min : = ' _ + ' _ + ' _ + ' _ + ' _ + ' _ + ' _ + ⋯ + ' _ ,
[! [!
[[ [[
bb bb
!` !`
![ ![
!! !!
!b !b
!a !a
205