Практика / Z9411_КафкаРС_ПМО_пр

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

федеральное государственное автономное образовательное учреждение высшего образования

«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ»

ИНСТИТУТ НЕПРЕРЫВНОГО И ДИСТАНЦИОННОГО ОБРАЗОВАНИЯ

КАФЕДРА 41

ОЦЕНКА

ПРЕПОДАВАТЕЛЬ

старший преподаватель				Б. К. Акопян
должность, уч. степень, звание		подпись, дата		инициалы, фамилия

ОТЧЁТ О ПРАКТИЧЕСКОЙ РАБОТЕ №1

Применение метода ветвей и границ для применения задачи коммивояжера

по дисциплине: Прикладные методы оптимизации

РАБОТУ ВЫПОЛНИЛ

СТУДЕНТ ГР. №	Z9411				Р. С. Кафка
	номер группы		подпись, дата		инициалы, фамилия
Студенческий билет №	2019/3603

Шифр ИНДО

Санкт-Петербург 2023

Цель работы: изучение метода ветвей и границ применительно к решению задачи коммивояжера.

Задание: решить задачу коммивояжера, используя метод ветвей и границ.

1. Определить значения α и β, дополнить ими исходную матрицу расстояний.

2. Вычислить нижнюю границу на всем множестве допустимых решений D.

3. Вычислить верхнюю оценку на рассматриваемом множестве допустимых решений жадным алгоритмом. При необходимости обновить рекорд х⁰.

4. Осуществить ветвление имеющегося множества на подмножества.

5. Для каждого из получаемых подмножеств повторять пп. 1–4, при необходимости отсекая множества согласно правому правилу отсечений, до тех пор, пока не будет найдено оптимальное решение.

6. Сделать выводы о полученных результатах.

7. Оформить отчет.

Условие задания согласно 8 варианту:

Таблица 1: Матрица расстояний задачи коммивояжера

№ города	1	2	3	4
1	-	11	8	4
2	9	-	3	6
3	8	7	-	4
4	2	1	5	-

Решение:

Пусть х⁰ равно пустому множеству, следовательно, f(x⁰) = +∞. В соответствии с матрицей расстояний требуется вычислить нижнюю границу на всем множестве D. Изначально коммивояжер находится в первом городе, значит, p = 1, а также:

Для всех I, k = 1, …, 4. В таком случае:

Результаты вычислений сведены в таблице 2, где к исходной матрице расстояний добавлены столбец α и β.

Таблица 2 – Дополненная матрица расстояний

№ города	1	2	3	4	α
1	-	11	8	4	4
2	9	-	3	6	3
3	8	7	-	4	4
4	2	1	5	-	1
β	1	0	0	0

Нижняя граница равна:

Для расчета верхней оценки на рассматриваемом множестве допустимых решений воспользуемся жадным алгоритмом построения допустимого решения («иди в ближайший доступный город, где еще не был»). Получим контур y = (1, 4, 2, 3, 1).

Значение целевой функции f(y) = 4+1+3+8 = 16.

Так как f(y)<f(x⁰), то обнаружен новый рекорд x⁰ = y = (1, 4, 2, 3, 1), соответствующий верхней границе f(x⁰)=16.

Поскольку , то множество D разбивается на 2 подмножества.

Затем из каждого значения в таблице вычитаем α и β.

Таблица 3 - Приведённая таблица

№ города	1	2	3	4
1	-	7	4	0
2	5	-	0	3
3	3	3	-	0
4	0	0	4	-

Определяем сумму минимальных элементов

Q41 = 3+0

Q42 = 3+0

Q23 = 4+3=7

Q14=0+4

Q34=0+3

Множество делим на 2 подмножества с исключением точки (2;3) и включением точки (2;3).

Чтобы оценить верхнюю границу для исключения нужно к нижней границе прибавить сумму минимальных элементов.

H0=H0иск+Q23=13+7=20

№ города	1	2	3	4
1	-	7	4	0
2	5	-	0	3
3	3	3	-	0
4	0	0	4	-

№ города	1	2	4	α
1	-	7	0	0
3	3	3	0	0
4	0	0	-	0
β	0	0	0

Нижняя граница равна:

H0=13+0=13

№ города	1	2	4
1	-	7	0
3	3	3	0
4	0	0	-

Q14=7

Q34=3

Q41=3

Q42=3

H0 = H0иск + Q14 = 13 + 7 = 20

№ города	1	2	4
1	-	7	0
3	3	3	0
4	0	0	-

№ города	1	2	α
3	3	3	3
4	0	0	0
β	0	0

Нижняя граница равна:

H0=13+3=16

№ города	1	2
3	0	0
4	0	0

Оставшийся маршрут (города):

{3, 1}

{4, 2}

Оптимальное решение: путем отсекания множеств в ходе работы было найдено решение для нахождения оптимального пути:

{1,4},{4,2},{2,3},{3,1}.

Рекорд x⁰=(1, 4, 2, 3, 1) – оптимальное решение задачи, а соответствующая ему длина гамильтонова контура равна f(x⁰)=16.

Рисунок 1 – Полное дерево ветвлений

ВЫВОД

В ходе выполнения данной работы я познакомился с методами решения задач дискретной оптимизации, имеющих конечное число допустимых решений. Были рассмотрены методы неявного перебора, в том числе метод ветвей и границ. Я узнал, что при решении подобных задач часто используются методы неявного перебора, так как последовательный перебор всех возможных решений может быть трудно осуществим даже для задач небольшой размерности. Метод ветвей и границ заключается в последовательном разбиении допустимого множества решений и проверке подмножеств на предмет содержания оптимального решения. При этом используется понятие рекорда – допустимого решения, дающего наименьшую верхнюю оценку. Рассматриваемое подмножество может быть отброшено в том случае, если оценка снизу целевой функции на данном подмножестве не меньше оценки сверху и, следовательно, не содержит решения лучше рекорда. Если значение целевой функции на рассматриваемом решении не превосходит рекордного, то рекорд изменяется. Принято считать, что подмножество решений просмотрено, если выявлено, что в нем нет решения лучше рекорда. По окончании просмотра всех элементов разбиения текущий рекорд принимается за оптимальное решение и алгоритм завершает работу. Если оптимальное решение не найдено, то из числа не просмотренных элементов разбиения выбирается наиболее перспективное подмножество, которое подвергается разбиению для последующего анализа по описанному алгоритму. Процесс продолжается до тех пор, пока не будут просмотрены все подмножества.