Лабораторные работы по Основам теории систем
Вычисляем нижнюю границу:
;
Т.к.
,
то
;
.
10) Анализ множества D4.
Поскольку
,
то:
.
=>
;
a)
Определяем
начальный план
для
:
,
;
В последнем
случае оставшееся
после других
городов расстояние
меньше 500 миль,
поэтому
будет дробным:
,
=>
.
Таким образом,
новый опорный
план:
.
;
б)
Определяем
начальный план
для
:
,
;
,
;
Таким образом,
новый опорный
план:
.
;
в)
Определяем
начальный план
для
:
В этом случае
оставшееся
после других
городов расстояние
меньше 150 миль,
поэтому
будет дробным:
,
=>
.
Таким образом,
новый опорный
план:
.
;
г) Вычисление верхней и нижней границ.
Вычисляем верхнюю границу:
;
– третье
ограничение
более жесткое.
Определяем опорные планы для третьего ограничения:
Очевидно,
что поскольку
,
то
.
Вычисляем нижнюю границу:
Т.к.
,
то
;
.
Т
ак
как
и
больше Rec,
то оба подмножества
перспективные,
но поскольку
,
то подмножество
более перспективное,
следовательно
оптимальным
планом будет
.
То есть города,
удовлетворяющие
всем 3 условиям
и при этом дающие
максимальную
прибыль – Детройт
и Нью-Йорк.
Лабораторная работа № 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. Математическая модель задачи.
Для решения
задачи присвоим
каждому пункту
маршрута определенный
номер: дед и
бабка – 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

;
;
;
;
;
3

;
;
;
;

4

;
;
;
;
;
5

;
;
;
;
;
6) Отсев неперспективных подмножеств.
;
Подмножества
D13 и D15
неперспективные.
Т.к.
,
но
,
то далее будем
рассматривать
подмножество
D14.
.
7

;
;
;
;

8) Анализ подмножества D143.
;
;
;


9) Анализ подмножества D145.
;
;
;
;
;
10) Отсев неперспективных подмножеств.
;
Подмножество
D143
неперспективное.
Т.к.
,
но
,
то далее будем
рассматривать
подмножество
D145.
.
9

;
;
;
;
;
9

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