.

Лабораторные работы по Основам теории систем

Язык: русский
Формат: реферат
Тип документа: Word Doc
0 207
Скачать документ

Лабораторная работа № 7

Телешовой Елизаветы, гр. 726,

Решение задачи коммивояжера методом ветвей и границ.

1. Постановка задачи.

Испекла бабка колобок и поставила его остывать на окошко. И решил
колобок, что пока он остывает, он вполне может обежать лес, посмотреть
на лесных жителей и снова вернуться к деду и бабке. Сказано – сделано.
Спрыгнул колобок из окошка и покатился в лес. Помогите колобку найти
кратчайший маршрут его движения по лесу, если расстояния между норами
лесных жителей, а также домом деда и бабки даны в таблице.

Дед и бабка Заяц Волк Медведь Лиса

Дед и бабка 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. Математическая модель задачи.

, принимающих значение 0, если переход из i-того пункта в j-тый не
входит в маршрут и 1 в противном случае. Условия прибытия в каждый пункт
и выхода из каждого пункта только по одному разу выражаются равенствами
(1) и (2).

(1)

(2)

дополнительных ограничений (3).

(3)

Суммарная протяженность маршрута F, которую необходимо минимизировать,
запишется в следующем виде:

(4)

В нашем случае эти условия запишутся в следующем виде:

(2);

(3)

(4)

3. Решение задачи методом ветвей и границ.

1) Анализ множества D.

Найдем оценку снизу Н. Для этого определяем матрицу минимальных
расстояний по строкам (1 где расстояние минимально в строке).

;

Аналогично определяем матрицу минимальных расстояний по столбцам.

;

;

. Тогда верхняя оценка:

.

означает переход из первого пункта в j-тый. Рассмотрим эти
подмножества по порядку.

2) Анализ подмножества D12.

;

;

;

;

;

3) Анализ подмножества D13.

;

;

;

;

4) Анализ подмножества D14.

;

;

;

;

;

5) Анализ подмножества D15.

;

;

;

;

;

6) Отсев неперспективных подмножеств.

;

, то далее будем рассматривать подмножество D14.

.

4) Анализ подмножества D142.

;

;

;

;

;

Дед и бабка Заяц Волк Медведь Лиса

Дед и бабка 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

PAGE

PAGE 3

Нашли опечатку? Выделите и нажмите CTRL+Enter

Похожие документы
Обсуждение

Оставить комментарий

avatar
  Подписаться  
Уведомление о
Заказать реферат!
UkrReferat.com. Всі права захищені. 2000-2020