Реферат: Лабораторная работа №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">

еще рефераты
Еще работы по теории систем управления