Реферат: Лабораторная работа №7 по "Основам теории систем" (Решение задачи коммивояжера методом ветвей и границ)
Лабораторнаяработа № 7ТелешовойЕлизаветы, гр. 726,
Решение задачи коммивояжера методомветвей и границ.1. Постановка задачи.Испекла бабка колобок и поставила его остывать наокошко. И решил колобок, что пока он остывает, он вполне может обежать лес,посмотреть на лесных жителей и снова вернуться к деду и бабке. Сказано –сделано. Спрыгнул колобок из окошка и покатился в лес. Помогите колобку найтикратчайший маршрут его движения по лесу, если расстояния между норами лесныхжителей, а также домом деда и бабки даны в таблице.
Дед и бабка
Заяц
Волк
Медведь
Лиса
Дед и бабка
6
4
5
2
Заяц
6
3
3,5
4,5
Волк
4
3
5,5
5
Медведь
5
3,5
5,5
2
Лиса
2
4,5
5
2
2.Математическая модель задачи.Для решения задачи присвоимкаждому пункту маршрута определенный номер: дед и бабка – 1, заяц – 2, волк –3, медведь – 4 и лиса – 5. Соответственно общее количество пунктов <img src="/cache/referats/8999/image002.gif" v:shapes="_x0000_i1025"><img src="/cache/referats/8999/image004.gif" v:shapes="_x0000_i1026"> альтернативныхпеременных <img src="/cache/referats/8999/image006.gif" v:shapes="_x0000_i1027">i-тогопункта в j-тыйне входит в маршрут и 1 в противном случае. Условияприбытия в каждый пункт и выхода из каждого пункта только по одному разувыражаются равенствами (1) и (2).
<img src="/cache/referats/8999/image008.gif" v:shapes="_x0000_i1028"> (1)
<img src="/cache/referats/8999/image010.gif" v:shapes="_x0000_i1029"> (2)
Для обеспечениянепрерывности маршрута вводятся дополнительно nпеременных <img src="/cache/referats/8999/image012.gif" v:shapes="_x0000_i1030"> и <img src="/cache/referats/8999/image004.gif" v:shapes="_x0000_i1031"> дополнительныхограничений (3).
<img src="/cache/referats/8999/image014.gif" v:shapes="_x0000_i1032"> (3)
Суммарная протяженностьмаршрута F, которую необходимоминимизировать, запишется в следующем виде:
<img src="/cache/referats/8999/image016.gif" v:shapes="_x0000_i1033"> (4)
В нашем случае эти условиязапишутся в следующем виде:
<img src="/cache/referats/8999/image018.gif" v:shapes="_x0000_i1034"> (1); <img src="/cache/referats/8999/image020.gif" v:shapes="_x0000_i1035"> (2);
<img src="/cache/referats/8999/image022.gif" v:shapes="_x0000_i1036"> (3)
<img src="/cache/referats/8999/image024.gif" v:shapes="_x0000_i1037"> (4)
3. Решениезадачи методом ветвей и границ.1) Анализ множества D.
Найдем оценку снизу Н. Для этого определяем матрицуминимальных расстояний по строкам (1 где расстояние минимально в строке).
<img src="/cache/referats/8999/image026.gif" v:shapes="_x0000_i1038"> => <img src="/cache/referats/8999/image028.gif" v:shapes="_x0000_i1039">
Аналогично определяем матрицу минимальных расстоянийпо столбцам.
<img src="/cache/referats/8999/image030.gif" v:shapes="_x0000_i1040"> => <img src="/cache/referats/8999/image032.gif" v:shapes="_x0000_i1041">
<img src="/cache/referats/8999/image034.gif" v:shapes="_x0000_i1042">;
Выберем начальный план: <img src="/cache/referats/8999/image036.gif" v:shapes="_x0000_i1043">
<img src="/cache/referats/8999/image038.gif" v:shapes="_x0000_i1044">
Очевидно, что <img src="/cache/referats/8999/image040.gif" v:shapes="_x0000_i1045"><img src="/cache/referats/8999/image042.gif" v:shapes="_x0000_i1046"> означает переход изпервого пункта в j-тый. Рассмотрим эти подмножества по порядку.
<div v:shape="_x0000_s1026">
<img src="/cache/referats/8999/image044.gif" v:shapes="_x0000_i1067">
2) Анализподмножества D12.<img src="/cache/referats/8999/image046.gif" v:shapes="_x0000_i1047">;
<img src="/cache/referats/8999/image048.gif" v:shapes="_x0000_i1048">
<img src="/cache/referats/8999/image050.gif" v:shapes="_x0000_i1049">
<img src="/cache/referats/8999/image052.gif" v:shapes="_x0000_i1050">
<img src="/cache/referats/8999/image054.gif" v:shapes="_x0000_i1051">
<div v:shape="_x0000_s1027">
<img src="/cache/referats/8999/image056.gif" v:shapes="_x0000_i1068">
3) Анализ подмножества D13.<img src="/cache/referats/8999/image058.gif" v:shapes="_x0000_i1052">;
<img src="/cache/referats/8999/image060.gif" v:shapes="_x0000_i1053">
<img src="/cache/referats/8999/image062.gif" v:shapes="_x0000_i1054">
<img src="/cache/referats/8999/image064.gif" v:shapes="_x0000_i1055">
<img src="/cache/referats/8999/image066.gif" v:shapes="_x0000_i1056">
<div v:shape="_x0000_s1028">
<img src="/cache/referats/8999/image068.gif" v:shapes="_x0000_i1069">
4) Анализ подмножества D14.<img src="/cache/referats/8999/image070.gif" v:shapes="_x0000_i1057">;
<img src="/cache/referats/8999/image072.gif" v:shapes="_x0000_i1058">
<img src="/cache/referats/8999/image074.gif" v:shapes="_x0000_i1059">
<img src="/cache/referats/8999/image076.gif" v:shapes="_x0000_i1060">
<img src="/cache/referats/8999/image078.gif" v:shapes="_x0000_i1061">
<div v:shape="_x0000_s1029">
<img src="/cache/referats/8999/image080.gif" v:shapes="_x0000_i1070">
5) Анализ подмножества D15.<img src="/cache/referats/8999/image082.gif" v:shapes="_x0000_i1062">;
<img src="/cache/referats/8999/image084.gif" v:shapes="_x0000_i1063">
<img src="/cache/referats/8999/image086.gif" v:shapes="_x0000_i1064">
<img src="/cache/referats/8999/image088.gif" v:shapes="_x0000_i1065">
<img src="/cache/referats/8999/image090.gif" v:shapes="_x0000_i1066">
<span Times New Roman",«serif»;mso-fareast-font-family:«Times New Roman»;mso-ansi-language: EN-US;mso-fareast-language:RU;mso-bidi-language:AR-SA">6) Отсев неперспективных подмножеств.
<img src="/cache/referats/8999/image092.gif" v:shapes="_x0000_i1071">
Подмножества D13и D15 неперспективные. Т.к. <img src="/cache/referats/8999/image094.gif" v:shapes="_x0000_i1072"><img src="/cache/referats/8999/image096.gif" v:shapes="_x0000_i1073">D14.
<img src="/cache/referats/8999/image098.gif" v:shapes="_x0000_i1074">.
<div v:shape="_x0000_s1030">
<img src="/cache/referats/8999/image100.gif" v:shapes="_x0000_i1105">
7) Анализ подмножества D142.<img src="/cache/referats/8999/image102.gif" v:shapes="_x0000_i1075">;
<img src="/cache/referats/8999/image104.gif" v:shapes="_x0000_i1076">
<img src="/cache/referats/8999/image106.gif" v:shapes="_x0000_i1077">
<img src="/cache/referats/8999/image108.gif" v:shapes="_x0000_i1078">
<div v:shape="_x0000_s1031">
<img src="/cache/referats/8999/image110.gif" v:shapes="_x0000_i1106">
<img src="/cache/referats/8999/image112.gif" v:shapes="_x0000_i1079">8) Анализ подмножества D143.
<img src="/cache/referats/8999/image114.gif" v:shapes="_x0000_i1080">;
<img src="/cache/referats/8999/image116.gif" v:shapes="_x0000_i1081">
<img src="/cache/referats/8999/image118.gif" v:shapes="_x0000_i1082">
<img src="/cache/referats/8999/image120.gif" v:shapes="_x0000_i1083">
<div v:shape="_x0000_s1033">
<img src="/cache/referats/8999/image122.gif" v:shapes="_x0000_i1107">
<img src="/cache/referats/8999/image124.gif" v:shapes="_x0000_i1084">9) Анализ подмножества D145.
<img src="/cache/referats/8999/image126.gif" v:shapes="_x0000_i1085">;
<img src="/cache/referats/8999/image128.gif" v:shapes="_x0000_i1086">
<img src="/cache/referats/8999/image130.gif" v:shapes="_x0000_i1087">
<img src="/cache/referats/8999/image132.gif" v:shapes="_x0000_i1088">
<img src="/cache/referats/8999/image134.gif" v:shapes="_x0000_i1089">
10) Отсев неперспективных подмножеств.
<img src="/cache/referats/8999/image136.gif" v:shapes="_x0000_i1090">
Подмножество D143неперспективное. Т.к. <img src="/cache/referats/8999/image138.gif" v:shapes="_x0000_i1091"><img src="/cache/referats/8999/image140.gif" v:shapes="_x0000_i1092">D145.
<img src="/cache/referats/8999/image142.gif" v:shapes="_x0000_i1093">.
<div v:shape="_x0000_s1035">
<img src="/cache/referats/8999/image144.gif" v:shapes="_x0000_i1108">
9) Анализ подмножества D1452.<img src="/cache/referats/8999/image146.gif" v:shapes="_x0000_i1094">;
<img src="/cache/referats/8999/image148.gif" v:shapes="_x0000_i1095">
<img src="/cache/referats/8999/image150.gif" v:shapes="_x0000_i1096">
<img src="/cache/referats/8999/image152.gif" v:shapes="_x0000_i1097">
<img src="/cache/referats/8999/image154.gif" v:shapes="_x0000_i1098">
<div v:shape="_x0000_s1036">
<img src="/cache/referats/8999/image156.gif" v:shapes="_x0000_i1109">
9) Анализ подмножества D1453.<img src="/cache/referats/8999/image158.gif" v:shapes="_x0000_i1099">;
<img src="/cache/referats/8999/image160.gif" v:shapes="_x0000_i1100">
<img src="/cache/referats/8999/image162.gif" v:shapes="_x0000_i1101">
<img src="/cache/referats/8999/image164.gif" v:shapes="_x0000_i1102">
<img src="/cache/referats/8999/image166.gif" v:shapes="_x0000_i1103">
<img src="/cache/referats/8999/image168.gif" v:shapes="_x0000_i1104">
<span Times New Roman",«serif»;mso-fareast-font-family:«Times New Roman»;mso-ansi-language: EN-US;mso-fareast-language:RU;mso-bidi-language:AR-SA">Оптимальное решение: <img src="/cache/referats/8999/image170.gif" v:shapes="_x0000_i1110">
<img src="/cache/referats/8999/image172.gif" v:shapes="_x0000_i1111">
Такимобразом, маршрут колобка: дед и бабка – медведь – лиса – заяц – волк – дед ибабка.
D
D12
D13
D14
D15
D142
D143
D145
D1452
D1453
<img src="/cache/referats/8999/image183.gif" v:shapes="_x0000_s1112 _x0000_s1040 _x0000_s1041 _x0000_s1042 _x0000_s1068 _x0000_s1044 _x0000_s1045 _x0000_s1049 _x0000_s1050 _x0000_s1064 _x0000_s1065 _x0000_s1069 _x0000_s1070 _x0000_s1071 _x0000_s1072 _x0000_s1073 _x0000_s1074 _x0000_s1075 _x0000_s1076 _x0000_s1077 _x0000_s1078 _x0000_s1079 _x0000_s1083 _x0000_s1081 _x0000_s1082 _x0000_s1084 _x0000_s1085 _x0000_s1086 _x0000_s1087 _x0000_s1088 _x0000_s1089 _x0000_s1090 _x0000_s1091 _x0000_s1092 _x0000_s1096 _x0000_s1094 _x0000_s1095 _x0000_s1097 _x0000_s1098 _x0000_s1099 _x0000_s1100 _x0000_s1101 _x0000_s1102 _x0000_s1103 _x0000_s1104 _x0000_s1106 _x0000_s1107 _x0000_s1108 _x0000_s1109 _x0000_s1110">