Реферат: Лабораторная работа №6 по "Основам теории систем" (Решение задачи о ранце методом ветвей и границ)

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

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

Решение задачи о ранце методомветвей и границ.1. Постановказадачи.

1929 год. В США великая депрессия, введен сухойзакон. Страна просто задыхается без спиртного. В этот сложный момент группаинициативных граждан под руководством Аль Капоне решает помочь родной стране.Ими планируется поставка алкогольной продукции из Ливерпуля в Штаты. Благодарные сограждане из 5крупных городов США готовы платить большие деньги за тонну спиртного: 2000долл. в Бостоне, 3000 в Детройте, 2500 в Вашингтоне, 3200 в Нью-Йорке и 1800долл в Чикаго. Все 5 городов находятся на разном расстоянии от порта, кудаприбывает груз: Бостон – 250 миль, Детройт – 300 миль, Вашингтон – 500 миль,Нью-Йорк –100 миль и Чикаго – 600 миль. Требуется выбрать города, в которыхможно получить максимальную прибыль от продажи спиртного. При этом суммарноерасстояние от этих портов до порта с грузом не должно превышать 1000 миль.

2. Решениезадачи.

Данная задача является задачей о ранце вида:

<img src="/cache/referats/9004/image002.gif" v:shapes="_x0000_i1025"> ,                                                        (1)

где критерием является функция

<img src="/cache/referats/9004/image004.gif" v:shapes="_x0000_i1026">                                                             (2)

которая может быть устремлена и к максимуму, и кминимуму.

Для начала составим следующую математическую модель:

Пусть <img src="/cache/referats/9004/image006.gif" v:shapes="_x0000_i1027"> – j-тый город, откуда соответственно <img src="/cache/referats/9004/image008.gif" v:shapes="_x0000_i1028">j-тый город будет разгружаться алкогольная продукция, то <img src="/cache/referats/9004/image010.gif" v:shapes="_x0000_i1029"><img src="/cache/referats/9004/image012.gif" v:shapes="_x0000_i1030">

<img src="/cache/referats/9004/image014.gif" v:shapes="_x0000_i1031"> ;

Целевой функцией иликритерием будет являться максимальная благодарность сограждан:

<img src="/cache/referats/9004/image016.gif" v:shapes="_x0000_i1032">

Далее отбираем порты поприоритетности, т.е. в порядке убывания отношения <img src="/cache/referats/9004/image018.gif" v:shapes="_x0000_i1033">

<img src="/cache/referats/9004/image020.gif" v:shapes="_x0000_i1034"> (3); <img src="/cache/referats/9004/image022.gif" v:shapes="_x0000_i1035"> (2); <img src="/cache/referats/9004/image024.gif" v:shapes="_x0000_i1036">; <img src="/cache/referats/9004/image026.gif" v:shapes="_x0000_i1037"> (1); <img src="/cache/referats/9004/image028.gif" v:shapes="_x0000_i1038"> (5).

После этого определяемначальный план следующим образом: пусть <img src="/cache/referats/9004/image030.gif" v:shapes="_x0000_i1039"><img src="/cache/referats/9004/image032.gif" v:shapes="_x0000_i1040"> наибольшее, иследовательно продажа спиртного в Нью-Йорке даст наибольшую прибыль принаименьших затратах, которые зависят от расстояния. Вычитая из суммарногорасстояния <img src="/cache/referats/9004/image034.gif" v:shapes="_x0000_i1041"> расстояние до порта мыполучим расстояние, которое разделяется между остальными городами, т.е.:

<img src="/cache/referats/9004/image030.gif" v:shapes="_x0000_i1042">, <img src="/cache/referats/9004/image036.gif" v:shapes="_x0000_i1043">

Аналогично рассуждая, далее получаем:

<img src="/cache/referats/9004/image038.gif" v:shapes="_x0000_i1044">, <img src="/cache/referats/9004/image040.gif" v:shapes="_x0000_i1045">

<img src="/cache/referats/9004/image042.gif" v:shapes="_x0000_i1046">, <img src="/cache/referats/9004/image044.gif" v:shapes="_x0000_i1047">

В последнем случае оставшееся после других городоврасстояние меньше 500 миль, поэтому <img src="/cache/referats/9004/image046.gif" v:shapes="_x0000_i1048"> будет дробным:<img src="/cache/referats/9004/image048.gif" v:shapes="_x0000_i1049"><img src="/cache/referats/9004/image050.gif" v:shapes="_x0000_i1050">

Таким образом, начальный опорный план: <img src="/cache/referats/9004/image052.gif" v:shapes="_x0000_i1051">

Значение целевой функции: <img src="/cache/referats/9004/image054.gif" v:shapes="_x0000_i1052">

Но <img src="/cache/referats/9004/image056.gif" v:shapes="_x0000_i1053"> обязательно целое.Поэтому чтобы определить, чему все же равен <img src="/cache/referats/9004/image046.gif" v:shapes="_x0000_i1054">

<img src="/cache/referats/9004/image058.gif" v:shapes="_x0000_i1055">;–целая часть критерия при существующем опорном плане.

<img src="/cache/referats/9004/image060.gif" v:shapes="_x0000_i1056">;– значениекритерия при целочисленном опорном плане, т.е. <img src="/cache/referats/9004/image062.gif" v:shapes="_x0000_i1057">

Множество D, которому принадлежит <img src="/cache/referats/9004/image064.gif" v:shapes="_x0000_i1058"> имеет <img src="/cache/referats/9004/image066.gif" v:shapes="_x0000_i1059"><img src="/cache/referats/9004/image068.gif" v:shapes="_x0000_i1060">Разделим его на 2 подмножества, такие что:

<img src="/cache/referats/9004/image070.gif" v:shapes="_x0000_i1061">;

<img src="/cache/referats/9004/image072.gif" v:shapes="_x0000_i1062">  — здесь <img src="/cache/referats/9004/image074.gif" v:shapes="_x0000_i1063">

<img src="/cache/referats/9004/image076.gif" v:shapes="_x0000_i1064">здесь <img src="/cache/referats/9004/image078.gif" v:shapes="_x0000_i1065">

1) Анализ множества D1.

Поскольку <img src="/cache/referats/9004/image074.gif" v:shapes="_x0000_i1066"> целевая функция иограничения будут иметь вид:

<img src="/cache/referats/9004/image080.gif" v:shapes="_x0000_i1067">

<img src="/cache/referats/9004/image082.gif" v:shapes="_x0000_i1068">

Строим новый опорный план:

<img src="/cache/referats/9004/image030.gif" v:shapes="_x0000_i1069">, <img src="/cache/referats/9004/image036.gif" v:shapes="_x0000_i1070">

<img src="/cache/referats/9004/image038.gif" v:shapes="_x0000_i1071">, <img src="/cache/referats/9004/image040.gif" v:shapes="_x0000_i1072">

<img src="/cache/referats/9004/image042.gif" v:shapes="_x0000_i1073">, <img src="/cache/referats/9004/image044.gif" v:shapes="_x0000_i1074">

Т.к. <img src="/cache/referats/9004/image084.gif" v:shapes="_x0000_i1075"><img src="/cache/referats/9004/image086.gif" v:shapes="_x0000_i1076"> будет дробным:<img src="/cache/referats/9004/image088.gif" v:shapes="_x0000_i1077"><img src="/cache/referats/9004/image090.gif" v:shapes="_x0000_i1078">

Таким образом, новый опорный план: <img src="/cache/referats/9004/image092.gif" v:shapes="_x0000_i1079">

<img src="/cache/referats/9004/image094.gif" v:shapes="_x0000_i1080">;

<img src="/cache/referats/9004/image096.gif" v:shapes="_x0000_i1081">, при<img src="/cache/referats/9004/image062.gif" v:shapes="_x0000_i1082">

2) Анализ множества D2.

Поскольку <img src="/cache/referats/9004/image078.gif" v:shapes="_x0000_i1083"> целевая функция иограничения будут иметь вид:

<img src="/cache/referats/9004/image099.gif" v:shapes="_x0000_i1084">

<img src="/cache/referats/9004/image101.gif" v:shapes="_x0000_i1085"> => <img src="/cache/referats/9004/image103.gif" v:shapes="_x0000_i1086">.

Строим новый опорный план:

<img src="/cache/referats/9004/image030.gif" v:shapes="_x0000_i1087">, <img src="/cache/referats/9004/image105.gif" v:shapes="_x0000_i1088">

<img src="/cache/referats/9004/image038.gif" v:shapes="_x0000_i1089">, <img src="/cache/referats/9004/image107.gif" v:shapes="_x0000_i1090">

Т.к. <img src="/cache/referats/9004/image109.gif" v:shapes="_x0000_i1091"><img src="/cache/referats/9004/image111.gif" v:shapes="_x0000_i1092"> будет дробным:<img src="/cache/referats/9004/image113.gif" v:shapes="_x0000_i1093"><img src="/cache/referats/9004/image115.gif" v:shapes="_x0000_i1094">

Таким образом, новый опорный план: <img src="/cache/referats/9004/image117.gif" v:shapes="_x0000_i1095">

<img src="/cache/referats/9004/image119.gif" v:shapes="_x0000_i1096">;

<img src="/cache/referats/9004/image121.gif" v:shapes="_x0000_i1097">, при<img src="/cache/referats/9004/image123.gif" v:shapes="_x0000_i1098">

3) Отсев неперспективного подмножества.

<img src="/cache/referats/9004/image125.gif" v:shapes="_x0000_i1099">

Так как <img src="/cache/referats/9004/image127.gif" v:shapes="_x0000_i1100"> и <img src="/cache/referats/9004/image129.gif" v:shapes="_x0000_i1101"> больше Rec, то оба подмножестваможно считать перспективными, но поскольку <img src="/cache/referats/9004/image131.gif" v:shapes="_x0000_i1102">D2. Разделим егона 2 подмножества, такие что:

<img src="/cache/referats/9004/image133.gif" v:shapes="_x0000_i1103">;

<img src="/cache/referats/9004/image135.gif" v:shapes="_x0000_i1104">  — здесь <img src="/cache/referats/9004/image137.gif" v:shapes="_x0000_i1105">

<img src="/cache/referats/9004/image139.gif" v:shapes="_x0000_i1106">здесь <img src="/cache/referats/9004/image141.gif" v:shapes="_x0000_i1107">

4) Анализ множества D3.

Поскольку <img src="/cache/referats/9004/image078.gif" v:shapes="_x0000_i1108"><img src="/cache/referats/9004/image143.gif" v:shapes="_x0000_i1109"> целевая функция иограничения будут иметь вид:

<img src="/cache/referats/9004/image145.gif" v:shapes="_x0000_i1110">

<img src="/cache/referats/9004/image147.gif" v:shapes="_x0000_i1111">.

Строим новый опорный план:

<img src="/cache/referats/9004/image030.gif" v:shapes="_x0000_i1112">, <img src="/cache/referats/9004/image105.gif" v:shapes="_x0000_i1113">

<img src="/cache/referats/9004/image038.gif" v:shapes="_x0000_i1114">, <img src="/cache/referats/9004/image107.gif" v:shapes="_x0000_i1115">

Т.к. <img src="/cache/referats/9004/image149.gif" v:shapes="_x0000_i1116"><img src="/cache/referats/9004/image086.gif" v:shapes="_x0000_i1117"> будет дробным:<img src="/cache/referats/9004/image152.gif" v:shapes="_x0000_i1118"><img src="/cache/referats/9004/image154.gif" v:shapes="_x0000_i1119">

Таким образом, новый опорный план: <img src="/cache/referats/9004/image156.gif" v:shapes="_x0000_i1120">

<img src="/cache/referats/9004/image158.gif" v:shapes="_x0000_i1121">;

<img src="/cache/referats/9004/image160.gif" v:shapes="_x0000_i1122">, при<img src="/cache/referats/9004/image123.gif" v:shapes="_x0000_i1123">

5) Анализ множества D4.

Поскольку <img src="/cache/referats/9004/image078.gif" v:shapes="_x0000_i1124"><img src="/cache/referats/9004/image162.gif" v:shapes="_x0000_i1125"> целевая функция иограничения будут иметь вид:

<img src="/cache/referats/9004/image164.gif" v:shapes="_x0000_i1126">

<img src="/cache/referats/9004/image166.gif" v:shapes="_x0000_i1127"> => <img src="/cache/referats/9004/image168.gif" v:shapes="_x0000_i1128">.

Строим новый опорный план:

<img src="/cache/referats/9004/image030.gif" v:shapes="_x0000_i1129">, <img src="/cache/referats/9004/image170.gif" v:shapes="_x0000_i1130">

Т.к. <img src="/cache/referats/9004/image172.gif" v:shapes="_x0000_i1131"><img src="/cache/referats/9004/image174.gif" v:shapes="_x0000_i1132"> будет дробным:<img src="/cache/referats/9004/image176.gif" v:shapes="_x0000_i1133"><img src="/cache/referats/9004/image178.gif" v:shapes="_x0000_i1134">

Таким образом, новый опорный план: <img src="/cache/referats/9004/image180.gif" v:shapes="_x0000_i1135">

<img src="/cache/referats/9004/image182.gif" v:shapes="_x0000_i1136">;

<img src="/cache/referats/9004/image184.gif" v:shapes="_x0000_i1137">, при<img src="/cache/referats/9004/image186.gif" v:shapes="_x0000_i1138">

6) Отсев неперспективного подмножества.

<img src="/cache/referats/9004/image188.gif" v:shapes="_x0000_i1139">

Так как <img src="/cache/referats/9004/image190.gif" v:shapes="_x0000_i1140"> и <img src="/cache/referats/9004/image192.gif" v:shapes="_x0000_i1141"> больше Rec, то оба подмножестваможно считать перспективными, но поскольку <img src="/cache/referats/9004/image194.gif" v:shapes="_x0000_i1142">D3. Разделим егона 2 подмножества, такие что:

<img src="/cache/referats/9004/image196.gif" v:shapes="_x0000_i1143">;

<img src="/cache/referats/9004/image198.gif" v:shapes="_x0000_i1144">  — здесь <img src="/cache/referats/9004/image200.gif" v:shapes="_x0000_i1145">

<img src="/cache/referats/9004/image202.gif" v:shapes="_x0000_i1146">здесь <img src="/cache/referats/9004/image204.gif" v:shapes="_x0000_i1147">

7) Анализ множества D5.

Поскольку <img src="/cache/referats/9004/image078.gif" v:shapes="_x0000_i1148"><img src="/cache/referats/9004/image143.gif" v:shapes="_x0000_i1149"><img src="/cache/referats/9004/image200.gif" v:shapes="_x0000_i1150"> целевая функция иограничения будут иметь вид:

<img src="/cache/referats/9004/image207.gif" v:shapes="_x0000_i1151">

<img src="/cache/referats/9004/image209.gif" v:shapes="_x0000_i1152">.

Строим новый опорный план, очевидно: <img src="/cache/referats/9004/image211.gif" v:shapes="_x0000_i1153"><img src="/cache/referats/9004/image137.gif" v:shapes="_x0000_i1154"><img src="/cache/referats/9004/image200.gif" v:shapes="_x0000_i1155"> ограничение выполняетсявсегда.

<img src="/cache/referats/9004/image214.gif" v:shapes="_x0000_i1156">;

<img src="/cache/referats/9004/image216.gif" v:shapes="_x0000_i1157">, при<img src="/cache/referats/9004/image123.gif" v:shapes="_x0000_i1158">

8) Анализ множества D6.

Поскольку <img src="/cache/referats/9004/image078.gif" v:shapes="_x0000_i1159"><img src="/cache/referats/9004/image143.gif" v:shapes="_x0000_i1160"><img src="/cache/referats/9004/image218.gif" v:shapes="_x0000_i1161"> целевая функция иограничения будут иметь вид:

<img src="/cache/referats/9004/image220.gif" v:shapes="_x0000_i1162">

D

D1

D2

D3

D4

D5

D6

<img src="/cache/referats/9004/image233.gif" align=«left» v:shapes="_x0000_s1100 _x0000_s1092 _x0000_s1093 _x0000_s1094 _x0000_s1095 _x0000_s1097 _x0000_s1055 _x0000_s1053 _x0000_s1054 _x0000_s1056 _x0000_s1058 _x0000_s1059 _x0000_s1060 _x0000_s1061 _x0000_s1062 _x0000_s1063 _x0000_s1064 _x0000_s1065 _x0000_s1066 _x0000_s1067 _x0000_s1068 _x0000_s1069 _x0000_s1070 _x0000_s1071 _x0000_s1072 _x0000_s1073 _x0000_s1074 _x0000_s1075 _x0000_s1076 _x0000_s1077 _x0000_s1078 _x0000_s1079 _x0000_s1080 _x0000_s1081 _x0000_s1082 _x0000_s1087 _x0000_s1088 _x0000_s1089 _x0000_s1096 _x0000_s1098 _x0000_s1099"><img src="/cache/referats/9004/image235.gif" v:shapes="_x0000_i1163">.

Ограничение несовместное, поскольку даже при <img src="/cache/referats/9004/image237.gif" v:shapes="_x0000_i1164"> оно не выполняется. Следовательномножество D6 несуществует.

Таким образом, оптимальным планом данной задачибудет: <img src="/cache/referats/9004/image239.gif" v:shapes="_x0000_i1165">

3. Постановка задачи омногомерном ранце.

В связи с тем, что спиртное стало хорошо раскупаться, Аль Капоне решилувеличить поставки. Но чтобы мирно спящее ФБР не дай бог не проснулось, былорешено осуществлять поставки через три разных порта на восточном побережье.Цены на спиртное в пяти вышеуказанных городах не изменились, расстояние же отних (в милях) до портов указано в следующей таблице:

Бостон

Детройт

Вашингтон

Нью-Йорк

Чикаго

Порт 1

250

300

500

100

600

Порт 2

100

200

700

400

300

Порт 3

500

400

300

550

150

Вовсех трех случаях суммарное расстояние от порта до городов не должно превышать1000 миль. Требуется решить тот же самый вопрос: в какие города выгоднеепоставлять продукцию?

4. Решениезадачи о многомерном ранце (вручную).

Задача о многомерном ранцеимеет следующую математическую модель:

<img src="/cache/referats/9004/image241.gif" v:shapes="_x0000_i1166"> ,                                                    (3)

где критерием является функция

<img src="/cache/referats/9004/image243.gif" v:shapes="_x0000_i1167">                                                             (4)

От задачи об одномерномранце она отличается наличием нескольких ограничений. Таким образом,математическая модель:

Пусть <img src="/cache/referats/9004/image245.gif" v:shapes="_x0000_i1168"> – j-тый город, откуда соответственно <img src="/cache/referats/9004/image008.gif" v:shapes="_x0000_i1169">j-тый город будет разгружаться алкогольная продукция, то <img src="/cache/referats/9004/image010.gif" v:shapes="_x0000_i1170"><img src="/cache/referats/9004/image012.gif" v:shapes="_x0000_i1171">

<img src="/cache/referats/9004/image247.gif" v:shapes="_x0000_i1172"> ;

Целевой функцией иликритерием будет являться максимальная благодарность сограждан:

<img src="/cache/referats/9004/image016.gif" v:shapes="_x0000_i1173">

Решим задачу оценки критерия для каждого ограниченияв отдельности. Пусть множество <img src="/cache/referats/9004/image250.gif" v:shapes="_x0000_i1174"> относится к первомуограничению, <img src="/cache/referats/9004/image252.gif" v:shapes="_x0000_i1175"><img src="/cache/referats/9004/image254.gif" v:shapes="_x0000_i1176">

1) Анализ множества <img src="/cache/referats/9004/image250.gif" v:shapes="_x0000_i1177">.

<img src="/cache/referats/9004/image256.gif" v:shapes="_x0000_i1178"> (3); <img src="/cache/referats/9004/image258.gif" v:shapes="_x0000_i1179"> (2); <img src="/cache/referats/9004/image260.gif" v:shapes="_x0000_i1180">; <img src="/cache/referats/9004/image262.gif" v:shapes="_x0000_i1181"> (1); <img src="/cache/referats/9004/image264.gif" v:shapes="_x0000_i1182"> (5).

Определяем начальный план:

<img src="/cache/referats/9004/image030.gif" v:shapes="_x0000_i1183">, <img src="/cache/referats/9004/image266.gif" v:shapes="_x0000_i1184">

<img src="/cache/referats/9004/image038.gif" v:shapes="_x0000_i1185">, <img src="/cache/referats/9004/image268.gif" v:shapes="_x0000_i1186">

<img src="/cache/referats/9004/image042.gif" v:shapes="_x0000_i1187">, <img src="/cache/referats/9004/image270.gif" v:shapes="_x0000_i1188">

В последнем случае оставшееся после других городоврасстояние меньше 500 миль, поэтому <img src="/cache/referats/9004/image046.gif" v:shapes="_x0000_i1189"> будет дробным:<img src="/cache/referats/9004/image048.gif" v:shapes="_x0000_i1190"><img src="/cache/referats/9004/image050.gif" v:shapes="_x0000_i1191">

Таким образом, начальный опорный план: <img src="/cache/referats/9004/image272.gif" v:shapes="_x0000_i1192">

<img src="/cache/referats/9004/image274.gif" v:shapes="_x0000_i1193">;

2) Анализ множества <img src="/cache/referats/9004/image276.gif" v:shapes="_x0000_i1194">.

<img src="/cache/referats/9004/image278.gif" v:shapes="_x0000_i1195">; <img src="/cache/referats/9004/image280.gif" v:shapes="_x0000_i1196">; <img src="/cache/referats/9004/image282.gif" v:shapes="_x0000_i1197">; <img src="/cache/referats/9004/image284.gif" v:shapes="_x0000_i1198">; <img src="/cache/referats/9004/image286.gif" v:shapes="_x0000_i1199">(4).

Определяем начальный план:

<img src="/cache/referats/9004/image288.gif" v:shapes="_x0000_i1200">, <img src="/cache/referats/9004/image290.gif" v:shapes="_x0000_i1201">

<img src="/cache/referats/9004/image038.gif" v:shapes="_x0000_i1202">, <img src="/cache/referats/9004/image292.gif" v:shapes="_x0000_i1203">

<img src="/cache/referats/9004/image294.gif" v:shapes="_x0000_i1216">, <img src="/cache/referats/9004/image296.gif" v:shapes="_x0000_i1217">

В последнем случае оставшееся после других городоврасстояние также равно 300 миль, поэтому <img src="/cache/referats/9004/image298.gif" v:shapes="_x0000_i1218"> будет целым:<img src="/cache/referats/9004/image300.gif" v:shapes="_x0000_i1219"><img src="/cache/referats/9004/image204.gif" v:shapes="_x0000_i1220">

Таким образом, опорный план: <img src="/cache/referats/9004/image303.gif" v:shapes="_x0000_i1221">

<img src="/cache/referats/9004/image305.gif" v:shapes="_x0000_i1222">;

3) Анализ множества <img src="/cache/referats/9004/image254.gif" v:shapes="_x0000_i1223">.

<img src="/cache/referats/9004/image308.gif" v:shapes="_x0000_i1224">; <img src="/cache/referats/9004/image310.gif" v:shapes="_x0000_i1225">2); <img src="/cache/referats/9004/image312.gif" v:shapes="_x0000_i1226">3); <img src="/cache/referats/9004/image314.gif" v:shapes="_x0000_i1227">; <img src="/cache/referats/9004/image316.gif" v:shapes="_x0000_i1228">(1).

Определяем начальный план:

<img src="/cache/referats/9004/image318.gif" v:shapes="_x0000_i1229">, <img src="/cache/referats/9004/image320.gif" v:shapes="_x0000_i1230">

<img src="/cache/referats/9004/image038.gif" v:shapes="_x0000_i1231">, <img src="/cache/referats/9004/image323.gif" v:shapes="_x0000_i1232">

<img src="/cache/referats/9004/image325.gif" v:shapes="_x0000_i1233">, <img src="/cache/referats/9004/image327.gif" v:shapes="_x0000_i1234">

В последнем случае оставшееся после других городоврасстояние меньше 550 миль, поэтому <img src="/cache/referats/9004/image329.gif" v:shapes="_x0000_i1235"> будет дробным:<img src="/cache/referats/9004/image331.gif" v:shapes="_x0000_i1236"><img src="/cache/referats/9004/image333.gif" v:shapes="_x0000_i1237">

Таким образом, опорный план: <img src="/cache/referats/9004/image335.gif" v:shapes="_x0000_i1238">

<img src="/cache/referats/9004/image337.gif" v:shapes="_x0000_i1239">;

4) Вычисление верхней и нижней границ.

Вычисляем верхнюю границу:

<img src="/cache/referats/9004/image339.gif" v:shapes="_x0000_i1240">; – третье ограничение более жесткое, далее будем исследоватьопорный план <img src="/cache/referats/9004/image335.gif" v:shapes="_x0000_i1241">.

Определяем опорные планы для третьего ограничения:

a) <img src="/cache/referats/9004/image030.gif" v:shapes="_x0000_i1242">, <img src="/cache/referats/9004/image342.gif" v:shapes="_x0000_i1243">

<img src="/cache/referats/9004/image038.gif" v:shapes="_x0000_i1244">, <img src="/cache/referats/9004/image344.gif" v:shapes="_x0000_i1245">

Впоследнем случае оставшееся после других городов расстояние равно 50 миль,поэтому <img src="/cache/referats/9004/image346.gif" v:shapes="_x0000_i1246">. Такимобразом: <img src="/cache/referats/9004/image348.gif" v:shapes="_x0000_i1247">

б) <img src="/cache/referats/9004/image288.gif" v:shapes="_x0000_i1248">, <img src="/cache/referats/9004/image350.gif" v:shapes="_x0000_i1249">

<img src="/cache/referats/9004/image038.gif" v:shapes="_x0000_i1250">, <img src="/cache/referats/9004/image352.gif" v:shapes="_x0000_i1251">

Впоследнем случае оставшееся после других городов расстояние равно 100 миль,поэтому <img src="/cache/referats/9004/image354.gif" v:shapes="_x0000_i1252">. Такимобразом: <img src="/cache/referats/9004/image356.gif" v:shapes="_x0000_i1253">

в) В этом случае <img src="/cache/referats/9004/image358.gif" v:shapes="_x0000_i1254">

Вычисляем нижнюю границу:

<img src="/cache/referats/9004/image360.gif" v:shapes="_x0000_i1255">;

<img src="/cache/referats/9004/image362.gif" v:shapes="_x0000_i1256">;

<img src="/cache/referats/9004/image364.gif" v:shapes="_x0000_i1257">;

<img src="/cache/referats/9004/image366.gif" v:shapes="_x0000_i1258">

5) Ветвление множества D.

<img src="/cache/referats/9004/image070.gif" v:shapes="_x0000_i1259">;

<img src="/cache/referats/9004/image368.gif" v:shapes="_x0000_i1260">  — здесь <img src="/cache/referats/9004/image370.gif" v:shapes="_x0000_i1261">

<img src="/cache/referats/9004/image372.gif" v:shapes="_x0000_i1262">здесь <img src="/cache/referats/9004/image374.gif" v:shapes="_x0000_i1263">

6) Анализ множества D1.

a) Определяем начальный пландля <img src="/cache/referats/9004/image376.gif" v:shapes="_x0000_i1264">

<img src="/cache/referats/9004/image038.gif" v:shapes="_x0000_i1265">, <img src="/cache/referats/9004/image378.gif" v:shapes="_x0000_i1266">

<img src="/cache/referats/9004/image042.gif" v:shapes="_x0000_i1267">, <img src="/cache/referats/9004/image380.gif" v:shapes="_x0000_i1268">

Впоследнем случае оставшееся после других городов расстояние меньше 500 миль,поэтому <img src="/cache/referats/9004/image382.gif" v:shapes="_x0000_i1269"> будет дробным:<img src="/cache/referats/9004/image384.gif" v:shapes="_x0000_i1270"><img src="/cache/referats/9004/image386.gif" v:shapes="_x0000_i1271">

Таким образом, новыйопорный план: <img src="/cache/referats/9004/image388.gif" v:shapes="_x0000_i1272">

<img src="/cache/referats/9004/image390.gif" v:shapes="_x0000_i1273">;

б)Определяем начальный план для <img src="/cache/referats/9004/image392.gif" v:shapes="_x0000_i1274">

<img src="/cache/referats/9004/image042.gif" v:shapes="_x0000_i1275">, <img src="/cache/referats/9004/image395.gif" v:shapes="_x0000_i1276">

<img src="/cache/referats/9004/image038.gif" v:shapes="_x0000_i1277">, <img src="/cache/referats/9004/image292.gif" v:shapes="_x0000_i1278">

<img src="/cache/referats/9004/image399.gif" v:shapes="_x0000_i1279">, <img src="/cache/referats/9004/image401.gif" v:shapes="_x0000_i1280">

Впоследнем случае оставшееся после других городов расстояние меньше 700 миль,поэтому <img src="/cache/referats/9004/image382.gif" v:shapes="_x0000_i1281"> будет дробным:<img src="/cache/referats/9004/image403.gif" v:shapes="_x0000_i1282"><img src="/cache/referats/9004/image405.gif" v:shapes="_x0000_i1283">

Таким образом, новыйопорный план: <img src="/cache/referats/9004/image407.gif" v:shapes="_x0000_i1284">

<img src="/cache/referats/9004/image409.gif" v:shapes="_x0000_i1285">;

в)Определяем начальный план для <img src="/cache/referats/9004/image411.gif" v:shapes="_x0000_i1286">

<img src="/cache/referats/9004/image413.gif" v:shapes="_x0000_i1287">, <img src="/cache/referats/9004/image415.gif" v:shapes="_x0000_i1288">

<img src="/cache/referats/9004/image038.gif" v:shapes="_x0000_i1289">, <img src="/cache/referats/9004/image323.gif" v:shapes="_x0000_i1290">

<img src="/cache/referats/9004/image325.gif" v:shapes="_x0000_i1291">, <img src="/cache/referats/9004/image327.gif" v:shapes="_x0000_i1292">

Впоследнем случае оставшееся после других городов расстояние меньше 100 миль, поэтому <img src="/cache/referats/9004/image111.gif" v:shapes="_x0000_i1293"> будет дробным:<img src="/cache/referats/9004/image422.gif" v:shapes="_x0000_i1294"><img src="/cache/referats/9004/image424.gif" v:shapes="_x0000_i1295">

Таким образом, новыйопорный план: <img src="/cache/referats/9004/image426.gif" v:shapes="_x0000_i1296">

<img src="/cache/referats/9004/image428.gif" v:shapes="_x0000_i1297">;

г) Вычисление верхней инижней границ.

Вычисляем верхнюю границу:

<img src="/cache/referats/9004/image430.gif" v:shapes="_x0000_i1298">; – первое ограничение более жесткое.

Определяем опорные планы дляпервого ограничения:

– В этом случае <img src="/cache/referats/9004/image432.gif" v:shapes="_x0000_i1299">

– <img src="/cache/referats/9004/image288.gif" v:shapes="_x0000_i1300">, <img src="/cache/referats/9004/image434.gif" v:shapes="_x0000_i1301">

<img src="/cache/referats/9004/image038.gif" v:shapes="_x0000_i1302">, <img src="/cache/referats/9004/image436.gif" v:shapes="_x0000_i1303">

Впоследнем случае оставшееся после других городов расстояние равно 450 миль, поэтому<img src="/cache/referats/9004/image438.gif" v:shapes="_x0000_i1304">. Такимобразом: <img src="/cache/referats/9004/image356.gif" v:shapes="_x0000_i1305">

– <img src="/cache/referats/9004/image441.gif" v:shapes="_x0000_i1306">, <img src="/cache/referats/9004/image443.gif" v:shapes="_x0000_i1307">

<img src="/cache/referats/9004/image444.gif" v:shapes="_x0000_i1308">, <img src="/cache/referats/9004/image446.gif" v:shapes="_x0000_i1309">

Впоследнем случае оставшееся после других городов расстояние равно 100 миль, поэтому <img src="/cache/referats/9004/image448.gif" v:shapes="_x0000_i1310">. Такимобразом: <img src="/cache/referats/9004/image450.gif" v:shapes="_x0000_i1311">

Вычисляемнижнюю границу:

Т.к. <img src="/cache/referats/9004/image452.gif" v:shapes="_x0000_i1312"><img src="/cache/referats/9004/image454.gif" v:shapes="_x0000_i1313">;

<img src="/cache/referats/9004/image456.gif" v:shapes="_x0000_i1314">;

<img src="/cache/referats/9004/image458.gif" v:shapes="_x0000_i1315">

7) Анализ множества D2.

Поскольку <img src="/cache/referats/9004/image374.gif" v:shapes="_x0000_i1316">

<img src="/cache/referats/9004/image460.gif" v:shapes="_x0000_i1317">

<img src="/cache/referats/9004/image462.gif" v:shapes="_x0000_i1318"> =><img src="/cache/referats/9004/image464.gif" v:shapes="_x0000_i1319">;

a) Определяем начальный пландля <img src="/cache/referats/9004/image466.gif" v:shapes="_x0000_i1320">

<img src="/cache/referats/9004/image038.gif" v:shapes="_x0000_i1321">, <img src="/cache/referats/9004/image268.gif" v:shapes="_x0000_i1322">

<img src="/cache/referats/9004/image042.gif" v:shapes="_x0000_i1323">, <img src="/cache/referats/9004/image270.gif" v:shapes="_x0000_i1324">

В последнемслучае оставшееся после других городов расстояние меньше 500 миль, поэтому <img src="/cache/referats/9004/image382.gif" v:shapes="_x0000_i1325"> будет дробным:<img src="/cache/referats/9004/image048.gif" v:shapes="_x0000_i1326"><img src="/cache/referats/9004/image471.gif" v:shapes="_x0000_i1327">

Таким образом, новыйопорный план: <img src="/cache/referats/9004/image272.gif" v:shapes="_x0000_i1328">

<img src="/cache/referats/9004/image474.gif" v:shapes="_x0000_i1329">;

б)Определяем начальный план для <img src="/cache/referats/9004/image476.gif" v:shapes="_x0000_i1330">

<img src="/cache/referats/9004/image042.gif" v:shapes="_x0000_i1331">, <img src="/cache/referats/9004/image478.gif" v:shapes="_x0000_i1332">

<img src="/cache/referats/9004/image038.gif" v:shapes="_x0000_i1333">, <img src="/cache/referats/9004/image480.gif" v:shapes="_x0000_i1334">

<img src="/cache/referats/9004/image399.gif" v:shapes="_x0000_i1335">, <img src="/cache/referats/9004/image482.gif" v:shapes="_x0000_i1336">

Таким образом, новыйопорный план: <img src="/cache/referats/9004/image303.gif" v:shapes="_x0000_i1337">

<img src="/cache/referats/9004/image485.gif" v:shapes="_x0000_i1338">;

в)Определяем начальный план для <img src="/cache/referats/9004/image487.gif" v:shapes="_x0000_i1339">

<img src="/cache/referats/9004/image413.gif" v:shapes="_x0000_i1340">, <img src="/cache/referats/9004/image489.gif" v:shapes="_x0000_i1341">

Впоследнем случае оставшееся после других городов расстояние меньше 400 миль, поэтому <img src="/cache/referats/9004/image491.gif" v:shapes="_x0000_i1342"> будет дробным:<img src="/cache/referats/9004/image493.gif" v:shapes="_x0000_i1343"><img src="/cache/referats/9004/image495.gif" v:shapes="_x0000_i1344">Таким образом, новый опорный план: <img src="/cache/referats/9004/image497.gif" v:shapes="_x0000_i1345">

<img src="/cache/referats/9004/image499.gif" v:shapes="_x0000_i1346">;

г) Вычисление верхней инижней границ.

Вычисляем верхнюю границу:

<img src="/cache/referats/9004/image501.gif" v:shapes="_x0000_i1347">; – третье ограничение более жесткое.

Определяем опорные планы длятретьего ограничения:

– <img src="/cache/referats/9004/image503.gif" v:shapes="_x0000_i1348">, <img src="/cache/referats/9004/image505.gif" v:shapes="_x0000_i1349">

В последнем случаеоставшееся после других городов расстояние равно 50 миль, поэтому <img src="/cache/referats/9004/image507.gif" v:shapes="_x0000_i1350">Такимобразом: <img src="/cache/referats/9004/image348.gif" v:shapes="_x0000_i1351">

– <img src="/cache/referats/9004/image510.gif" v:shapes="_x0000_i1352">, <img src="/cache/referats/9004/image512.gif" v:shapes="_x0000_i1353">

<img src="/cache/referats/9004/image503.gif" v:shapes="_x0000_i1354">, <img src="/cache/referats/9004/image505.gif" v:shapes="_x0000_i1355">

Впоследнем случае оставшееся после других городов расстояние равно 50 миль,поэтому <img src="/cache/referats/9004/image507.gif" v:shapes="_x0000_i1356">. Такимобразом: <img src="/cache/referats/9004/image514.gif" v:shapes="_x0000_i1357">

– В этомслучае <img src="/cache/referats/9004/image516.gif" v:shapes="_x0000_i1358">

Вычисляемнижнюю границу:

Т.к. <img src="/cache/referats/9004/image452.gif" v:shapes="_x0000_i1359"><img src="/cache/referats/9004/image518.gif" v:shapes="_x0000_i1360">;

<img src="/cache/referats/9004/image520.gif" v:shapes="_x0000_i1361">;

<img src="/cache/referats/9004/image522.gif" v:shapes="_x0000_i1362">

8) Отсев неперспективного подмножества.

<img src="/cache/referats/9004/image524.gif" v:shapes="_x0000_i1363">

Так как <img src="/cache/referats/9004/image526.gif" v:shapes="_x0000_i1364"> и <img src="/cache/referats/9004/image528.gif" v:shapes="_x0000_i1365"> больше Rec, то оба подмножестваперспективные, но поскольку <img src="/cache/referats/9004/image131.gif" v:shapes="_x0000_i1366"><img src="/cache/referats/9004/image531.gif" v:shapes="_x0000_i1367">

<img src="/cache/referats/9004/image133.gif" v:shapes="_x0000_i1368">;

<img src="/cache/referats/9004/image534.gif" v:shapes="_x0000_i1369">  — здесь <img src="/cache/referats/9004/image536.gif" v:shapes="_x0000_i1370">

<img src="/cache/referats/9004/image538.gif" v:shapes="_x0000_i1371">здесь <img src="/cache/referats/9004/image540.gif" v:shapes="_x0000_i1372">

9) Анализ множества D3.

Поскольку <img src="/cache/referats/9004/image536.gif" v:shapes="_x0000_i1373">

<img src="/cache/referats/9004/image542.gif" v:shapes="_x0000_i1374">

<img src="/cache/referats/9004/image544.gif" v:shapes="_x0000_i1375">

a) Определяем начальный пландля <img src="/cache/referats/9004/image546.gif" v:shapes="_x0000_i1376">

<img src="/cache/referats/9004/image042.gif" v:shapes="_x0000_i1377">, <img src="/cache/referats/9004/image548.gif" v:shapes="_x0000_i1378">

<img src="/cache/referats/9004/image550.gif" v:shapes="_x0000_i1379">, <img src="/cache/referats/9004/image552.gif" v:shapes="_x0000_i1380">

Впоследнем случае оставшееся после других городов расстояние меньше 600 миль,поэтому <img src="/cache/referats/9004/image086.gif" v:shapes="_x0000_i1381"> будет дробным:<img src="/cache/referats/9004/image555.gif" v:shapes="_x0000_i1382"><img src="/cache/referats/9004/image557.gif" v:shapes="_x0000_i1383">

Таким образом, новыйопорный план: <img src="/cache/referats/9004/image559.gif" v:shapes="_x0000_i1384">

<img src="/cache/referats/9004/image561.gif" v:shapes="_x0000_i1385">;

б)Определяем начальный план для <img src="/cache/referats/9004/image563.gif" v:shapes="_x0000_i1386">

<img src="/cache/referats/9004/image042.gif" v:shapes="_x0000_i1387">, <img src="/cache/referats/9004/image478.gif" v:shapes="_x0000_i1388">

<img src="/cache/referats/9004/image399.gif" v:shapes="_x0000_i1389">, <img src="/cache/referats/9004/image566.gif" v:shapes="_x0000_i1390">

Впоследнем случае оставшееся после других городов расстояние меньше 700 миль,поэтому <img src="/cache/referats/9004/image046.gif" v:shapes="_x0000_i1391"> будет дробным:<img src="/cache/referats/9004/image569.gif" v:shapes="_x0000_i1392"><img src="/cache/referats/9004/image571.gif" v:shapes="_x0000_i1393">

Таким образом, новыйопорный план: <img src="/cache/referats/9004/image573.gif" v:shapes="_x0000_i1394">

<img src="/cache/referats/9004/image575.gif" v:shapes="_x0000_i1395">;

в)Определяем начальный план для <img src="/cache/referats/9004/image577.gif" v:shapes="_x0000_i1396">

<img src="/cache/referats/9004/image413.gif" v:shapes="_x0000_i1397">, <img src="/cache/referats/9004/image489.gif" v:shapes="_x0000_i1398">

Впоследнем случае оставшееся после других городов расстояние меньше 350миль, поэтому <img src="/cache/referats/9004/image046.gif" v:shapes="_x0000_i1399"> будет дробным:<img src="/cache/referats/9004/image580.gif" v:shapes="_x0000_i1400"><img src="/cache/referats/9004/image582.gif" v:shapes="_x0000_i1401">

Таким образом, новыйопорный план: <img src="/cache/referats/9004/image584.gif" v:shapes="_x0000_i1402">

<img src="/cache/referats/9004/image586.gif" v:shapes="_x0000_i1403">;

г) Вычисление верхней инижней границ.

Вычисляем верхнюю границу:

<img src="/cache/referats/9004/image588.gif" v:shapes="_x0000_i1404">; – третье ограничение более жесткое.

Определяем опорные планы длятретьего ограничения:

– <img src="/cache/referats/9004/image288.gif" v:shapes="_x0000_i1405">, <img src="/cache/referats/9004/image590.gif" v:shapes="_x0000_i1406">

<img src="/cache/referats/9004/image325.gif" v:shapes="_x0000_i1407">, <img src="/cache/referats/9004/image327.gif" v:shapes="_x0000_i1408">

Впоследнем случае оставшееся после других городов расстояние равно 100 миль,поэтому <img src="/cache/referats/9004/image594.gif" v:shapes="_x0000_i1409">. Такимобразом: <img src="/cache/referats/9004/image596.gif" v:shapes="_x0000_i1410">

– <img src="/cache/referats/9004/image288.gif" v:shapes="_x0000_i1411">, <img src="/cache/referats/9004/image590.gif" v:shapes="_x0000_i1412">

<img src="/cache/referats/9004/image599.gif" v:shapes="_x0000_i1413">, <img src="/cache/referats/9004/image601.gif" v:shapes="_x0000_i1414">

Впоследнем случае оставшееся после других городов расстояние равно 300 миль, поэтому <img src="/cache/referats/9004/image603.gif" v:shapes="_x0000_i1415">. Такимобразом: <img src="/cache/referats/9004/image605.gif" v:shapes="_x0000_i1416">

– В этом случае <img src="/cache/referats/9004/image516.gif" v:shapes="_x0000_i1417">

Вычисляемнижнюю границу:

<img src="/cache/referats/9004/image608.gif" v:shapes="_x0000_i1418">;

Т.к. <img src="/cache/referats/9004/image610.gif" v:shapes="_x0000_i1419"><img src="/cache/referats/9004/image612.gif" v:shapes="_x0000_i1420">;

<img src="/cache/referats/9004/image614.gif" v:shapes="_x0000_i1421">

10) Анализ множества D4.

Поскольку <img src="/cache/referats/9004/image540.gif" v:shapes="_x0000_i1422">

<img src="/cache/referats/9004/image616.gif" v:shapes="_x0000_i1423">

<img src="/cache/referats/9004/image618.gif" v:shapes="_x0000_i1424"> => <img src="/cache/referats/9004/image620.gif" v:shapes="_x0000_i1425">;

a) Определяем начальный пландля <img src="/cache/referats/9004/image622.gif" v:shapes="_x0000_i1426">

<img src="/cache/referats/9004/image042.gif" v:shapes="_x0000_i1427">, <img src="/cache/referats/9004/image270.gif" v:shapes="_x0000_i1428">

Впоследнем случае оставшееся после других городов расстояние меньше 500 миль,поэтому <img src="/cache/referats/9004/image382.gif" v:shapes="_x0000_i1429"> будет дробным:<img src="/cache/referats/9004/image048.gif" v:shapes="_x0000_i1430"><img src="/cache/referats/9004/image471.gif" v:shapes="_x0000_i1431">

Таким образом, новыйопорный план: <img src="/cache/referats/9004/image272.gif" v:shapes="_x0000_i1432">

<img src="/cache/referats/9004/image624.gif" v:shapes="_x0000_i1433">;

б)Определяем начальный план для <img src="/cache/referats/9004/image626.gif" v:shapes="_x0000_i1434">

<img src="/cache/referats/9004/image042.gif" v:shapes="_x0000_i1435">, <img src="/cache/referats/9004/image628.gif" v:shapes="_x0000_i1436">

<img src="/cache/referats/9004/image399.gif" v:shapes="_x0000_i1437">, <img src="/cache/referats/9004/image482.gif" v:shapes="_x0000_i1438">

Таким образом, новыйопорный план: <img src="/cache/referats/9004/image303.gif" v:shapes="_x0000_i1439">

<img src="/cache/referats/9004/image630.gif" v:shapes="_x0000_i1440">;

в)Определяем начальный план для <img src="/cache/referats/9004/image632.gif" v:shapes="_x0000_i1441">

В этомслучае оставшееся после других городов расстояние меньше 150 миль, поэтому <img src="/cache/referats/9004/image086.gif" v:shapes="_x0000_i1442"> будет дробным:<img src="/cache/referats/9004/image635.gif" v:shapes="_x0000_i1443"><img src="/cache/referats/9004/image637.gif" v:shapes="_x0000_i1444">

Такимобразом, новый опорный план: <img src="/cache/referats/9004/image639.gif" v:shapes="_x0000_i1445">

<img src="/cache/referats/9004/image641.gif" v:shapes="_x0000_i1446">;

г) Вычисление верхней инижней границ.

Вычисляем верхнюю границу:

<img src="/cache/referats/9004/image643.gif" v:shapes="_x0000_i1447">; – третье ограничение более жесткое.

Определяем опорные планы длятретьего ограничения:

Очевидно, что поскольку <img src="/cache/referats/9004/image645.gif" v:shapes="_x0000_i1448"><img src="/cache/referats/9004/image647.gif" v:shapes="_x0000_i1449">

Вычисляемнижнюю границу:

Т.к. <img src="/cache/referats/9004/image649.gif" v:shapes="_x0000_i1450"><img src="/cache/referats/9004/image651.gif" v:shapes="_x0000_i1451">;

<img src="/cache/referats/9004/image653.gif" v:shapes="_x0000_i1452">

<table cellpadding=«0» cell

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