Лабораторная работа №7 по "Основам теории систем" (Решение задачи коммивояжера методом ветвей и гран...

Для решения задачи присвоим каждому пункту маршрута определенный номер: дед и бабка 1, заяц 2, волк 3,

Лабораторная работа №7 по Основам теории систем (Решение задачи коммивояжера методом ветвей и гран...

Реферат

Компьютеры, программирование

Другие рефераты по предмету

Компьютеры, программирование

Сдать работу со 100% гаранией

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

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

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

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

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

Дед и бабкаЗаяцВолкМедведьЛисаДед и бабка06452Заяц6033,54,5Волк4305,55Медведь53,55,502Лиса24,55202. Математическая модель задачи.

Для решения задачи присвоим каждому пункту маршрута определенный номер: дед и бабка 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.

;

;

;

;

;

;

Оптимальное решение: .

.

Таким образом, маршрут колобка: дед и бабка медведь лиса заяц волк дед и бабка.

 

 

Похожие работы