|
Дед и бабка
|
Заяц
|
Волк
|
Медведь
|
Лиса
|
Дед и бабка
|
0
|
6
|
4
|
5
|
2
|
Заяц
|
6
|
0
|
3
|
3,5
|
4,5
|
Волк
|
4
|
3
|
0
|
5,5
|
5
|
Медведь
|
5
|
3,5
|
5,5
|
0
|
2
|
Лиса
|
2
|
4,5
|
5
|
2
|
0
|
2.
Математическая модель задачи.
Для решения задачи присвоим каждому пункту маршрута
определенный номер: дед и бабка – 1, заяц – 2, волк – 3, медведь – 4 и лиса –
5. Соответственно общее количество пунктов . Далее введем альтернативных переменных , принимающих значение 0, если
переход из i-того пункта в j-тый не входит в маршрут и 1
в противном случае. Условия прибытия в каждый пункт и выхода из каждого пункта
только по одному разу выражаются равенствами (1) и (2).
(1)
(2)
Для обеспечения непрерывности маршрута
вводятся дополнительно n переменных
и дополнительных ограничений
(3).
(3)
Суммарная протяженность маршрута F,
которую необходимо минимизировать, запишется в следующем виде:
(4)
В нашем случае эти условия запишутся в
следующем виде:
(1); (2);
(3)
(4)
3.
Решение задачи методом ветвей и границ.
1) Анализ множества D.
Найдем оценку снизу Н. Для этого
определяем матрицу минимальных расстояний по строкам (1 где расстояние
минимально в строке).
=> ;
Аналогично определяем матрицу минимальных расстояний по столбцам.
=> ;
;
Выберем начальный план: . Тогда верхняя оценка:
.
Очевидно, что ,
где означает
переход из первого пункта в j-тый. Рассмотрим эти подмножества по порядку.
2) Анализ подмножества D12.
;
;
;
;
;
3) Анализ подмножества D13.
;
;
;
4) Анализ подмножества D14.
;
;
;
;
;
5) Анализ подмножества D15.
;
;
;
;
;
6) Отсев неперспективных подмножеств.
;
Подмножества D13 и D15
неперспективные. Т.к. ,
но , то далее
будем рассматривать подмножество D14.
.
7) Анализ подмножества D142.
;
;
;
;
;
8) Анализ
подмножества D143.
;
;
;
;
9) Анализ
подмножества D145.
;
;
;
;
;
10) Отсев неперспективных подмножеств.
;
Подмножество D143 неперспективное.
Т.к. , но , то далее будем
рассматривать подмножество D145.
.
9) Анализ подмножества D1452.
;
;
;
;
;
9) Анализ подмножества D1453.
;
;
;
;
;
;
Оптимальное решение: .
.
Таким образом,
маршрут колобка: дед и бабка – медведь – лиса – заяц – волк – дед и бабка.