Выдержка из текста работы
В некотором царстве, некотором государстве жил-былкот Василий, который очень любил мышей… на обед. А обедал он исключительно вамбаре своего хозяина, да так хорошо, что бедные мыши и носу не могли высунутьиз своих нор. Но всю жизнь в норе не просидишь, есть то хочется, и стали мышидумать и гадать, как им провести кота Василия и до заветных пищевых ресурсовамбара добраться.
В амбаре было 4 мышиныхноры: в первой проживало 15 мышей, во второй – 20, в третьей – 10 мышей, а вчетвертой – 25 мышей, а также 5 источников пищи, от которых и кормилась вся этаорава мышей: у окорока – 5 мышей, у мешка крупы – 18 мышей, у мешка муки – 17мышей, у мешка картошки – 22 мыши и у стопки старых газет и журналовэротического содержания – 8 мышей.
И тут мыши вспомнили, что когда-то в стопке журналовлежала книжка по математическому программированию. Конечно мыши давным-давноуспели ее сгрызть, но кое-что из нее они, пока грызли, прочитать успели, вчастности, как решать транспортные задачи.
Считая что <img src="/cache/referats/9000/image002.gif" v:shapes="_x0000_i1025"><img src="/cache/referats/9000/image004.gif" v:shapes="_x0000_i1026"><img src="/cache/referats/9000/image006.gif" v:shapes="_x0000_i1027"><img src="/cache/referats/9000/image008.gif" v:shapes="_x0000_i1028">количество мышей, проживающих в <img src="/cache/referats/9000/image004.gif" v:shapes="_x0000_i1029"><img src="/cache/referats/9000/image011.gif" v:shapes="_x0000_i1030"><img src="/cache/referats/9000/image006.gif" v:shapes="_x0000_i1031">
1)<img src="/cache/referats/9000/image013.gif" v:shapes="_x0000_i1032">;
2)<img src="/cache/referats/9000/image015.gif" v:shapes="_x0000_i1033">
ну и конечно <img src="/cache/referats/9000/image017.gif" v:shapes="_x0000_i1034">
Исходя из этих условий онисоставили математическую модель процесса своего питания:
<img src="/cache/referats/9000/image019.gif" v:shapes="_x0000_i1035">; <img src="/cache/referats/9000/image021.gif" v:shapes="_x0000_i1036">; <img src="/cache/referats/9000/image023.gif" v:shapes="_x0000_i1037">
Ну, и для наглядностинарисовали ее в виде таблицы:
окорок
мешок крупы
мешок муки
мешок картошки
журналы
нора 1
<img src="/cache/referats/9000/image026.gif" v:shapes="_x0000_i1038">
<img src="/cache/referats/9000/image028.gif" v:shapes="_x0000_i1039">
<img src="/cache/referats/9000/image030.gif" v:shapes="_x0000_i1040">
<img src="/cache/referats/9000/image032.gif" v:shapes="_x0000_i1041">
<img src="/cache/referats/9000/image034.gif" v:shapes="_x0000_i1042">
нора 2
<img src="/cache/referats/9000/image036.gif" v:shapes="_x0000_i1043">
<img src="/cache/referats/9000/image038.gif" v:shapes="_x0000_i1044">
<img src="/cache/referats/9000/image040.gif" v:shapes="_x0000_i1045">
<img src="/cache/referats/9000/image042.gif" v:shapes="_x0000_i1046">
<img src="/cache/referats/9000/image044.gif" v:shapes="_x0000_i1047">
нора 3
<img src="/cache/referats/9000/image046.gif" v:shapes="_x0000_i1048">
<img src="/cache/referats/9000/image048.gif" v:shapes="_x0000_i1049">
<img src="/cache/referats/9000/image050.gif" v:shapes="_x0000_i1050">
<img src="/cache/referats/9000/image052.gif" v:shapes="_x0000_i1051">
<img src="/cache/referats/9000/image054.gif" v:shapes="_x0000_i1052">
нора 4
<img src="/cache/referats/9000/image056.gif" v:shapes="_x0000_i1053">
<img src="/cache/referats/9000/image058.gif" v:shapes="_x0000_i1054">
<img src="/cache/referats/9000/image060.gif" v:shapes="_x0000_i1055">
<img src="/cache/referats/9000/image062.gif" v:shapes="_x0000_i1056">
<img src="/cache/referats/9000/image064.gif" v:shapes="_x0000_i1057">
В левом верхнем углу каждойячейки таблицы мыши указали число попавших в лапы кота (в процентах) поотношению к общему числу мышей из <img src="/cache/referats/9000/image004.gif" v:shapes="_x0000_i1058"><img src="/cache/referats/9000/image006.gif" v:shapes="_x0000_i1059">
<img src="/cache/referats/9000/image067.gif" v:shapes="_x0000_i1060">
Безусловно, цель мышей –добраться до еды с минимальными потерями по дороге, то есть:
<img src="/cache/referats/9000/image069.gif" v:shapes="_x0000_i1061">
Таким образом:
<img src="/cache/referats/9000/image071.gif" v:shapes="_x0000_i1062">
Необходимо, конечно, оценитьи выгодность передвижения из каждой норы к каждому пищевому ресурсу. Для этогомыши оценили так называемые потенциалы нор (<img src="/cache/referats/9000/image073.gif" v:shapes="_x0000_i1063"><img src="/cache/referats/9000/image075.gif" v:shapes="_x0000_i1064">
<img src="/cache/referats/9000/image077.gif" v:shapes="_x0000_i1065"> (1).
Система (1) и будет служитьв дальнейшем критерием оптимальности плана.
Запишем подробнодвойственную задачу на основе этого ограничения:
<img src="/cache/referats/9000/image079.gif" v:shapes="_x0000_i1066">; <img src="/cache/referats/9000/image081.gif" v:shapes="_x0000_i1067">; <img src="/cache/referats/9000/image083.gif" v:shapes="_x0000_i1068">; <img src="/cache/referats/9000/image085.gif" v:shapes="_x0000_i1069">; <img src="/cache/referats/9000/image087.gif" v:shapes="_x0000_i1070">
Критерием двойственнойзадачи будет максимизация выгодности:
<img src="/cache/referats/9000/image089.gif" v:shapes="_x0000_i1071">
Первое, что пришло на уммышам – использовать те источники пищи, доступ к которым легче, и они решилипостроить начальный опорный план по методу максимальной загрузки, исходя изформулы:
<img src="/cache/referats/9000/image091.gif" v:shapes="_x0000_i1072"> (2).
т.е. выбираются те варианты, которые могутобеспечить едой максимальное количество мышей, и эти варианты будутиспользоваться в соответствии с (2).
Поскольку хотят есть все мыши во всех норах, томодель закрытая, т.е.
<img src="/cache/referats/9000/image093.gif" v:shapes="_x0000_i1073">
Общая схема построенияначального опорного плана по методу максимальной загрузки такова:
1) Выбираем коммуникацию,которую можно больше всего загрузить.
2) Максимально ее загружаемв соответствии с (2).
3) Корректируем объемы производства и потребленияна величину выбранной перевозки, вычисляя остатки производства и потребления:
<img src="/cache/referats/9000/image095.gif" v:shapes="_x0000_i1074">; <img src="/cache/referats/9000/image097.gif" v:shapes="_x0000_i1075">
4) Вычеркиваем в транспортной таблице строку или столбец с нулевым объемомпроизводства или потребления:
если <img src="/cache/referats/9000/image099.gif" v:shapes="_x0000_i1076"> – вычеркиваем <img src="/cache/referats/9000/image004.gif" v:shapes="_x0000_i1077">
если <img src="/cache/referats/9000/image101.gif" v:shapes="_x0000_i1078"> – вычеркиваем <img src="/cache/referats/9000/image006.gif" v:shapes="_x0000_i1079">;
5) Повторяем этот процесс с пункта 1 по 4, пока не будут перечеркнуты всестроки или столбцы
В нашем случае это выглядит следующим образом:
окорок
мешок крупы
мешок муки
мешок картошки
журналы
5 2 0
18 0
17 2 0
22 0
8 0
нора 1
15 0
<img src="/cache/referats/9000/image104.gif" v:shapes="_x0000_i1080">
<img src="/cache/referats/9000/image106.gif" v:shapes="_x0000_i1081">
<img src="/cache/referats/9000/image108.gif" v:shapes="_x0000_i1082">
<img src="/cache/referats/9000/image110.gif" v:shapes="_x0000_i1083">
<img src="/cache/referats/9000/image112.gif" v:shapes="_x0000_i1084">
нора 2
20 2 0
<img src="/cache/referats/9000/image114.gif" v:shapes="_x0000_i1085">
<img src="/cache/referats/9000/image116.gif" v:shapes="_x0000_i1086">
<img src="/cache/referats/9000/image118.gif" v:shapes="_x0000_i1087">2
<img src="/cache/referats/9000/image120.gif" v:shapes="_x0000_i1088">
<img src="/cache/referats/9000/image122.gif" v:shapes="_x0000_i1089">
нора 3
10 2 0
<img src="/cache/referats/9000/image110.gif" v:shapes="_x0000_i1090">2
<img src="/cache/referats/9000/image104.gif" v:shapes="_x0000_i1091">
<img src="/cache/referats/9000/image126.gif" v:shapes="_x0000_i1092">
<img src="/cache/referats/9000/image128.gif" v:shapes="_x0000_i1093">
<img src="/cache/referats/9000/image130.gif" v:shapes="_x0000_i1094">
нора 4
25 3 0
<img src="/cache/referats/9000/image112.gif" v:shapes="_x0000_i1095">3
<img src="/cache/referats/9000/image133.gif" v:shapes="_x0000_i1096">
<img src="/cache/referats/9000/image135.gif" v:shapes="_x0000_i1097">
<img src="/cache/referats/9000/image137.gif" v:shapes="_x0000_i1098">
<img src="/cache/referats/9000/image139.gif" v:shapes="_x0000_i1099">
Римскими цифрами пронумерован порядок итераций.
I. <img src="/cache/referats/9000/image141.gif" v:shapes="_x0000_i1100"><img src="/cache/referats/9000/image143.gif" v:shapes="_x0000_i1101"><img src="/cache/referats/9000/image145.gif" v:shapes="_x0000_i1102"><img src="/cache/referats/9000/image147.gif" v:shapes="_x0000_i1103"> – 4 столбец исключен.
II. <img src="/cache/referats/9000/image149.gif" v:shapes="_x0000_i1104"><img src="/cache/referats/9000/image151.gif" v:shapes="_x0000_i1105"><img src="/cache/referats/9000/image153.gif" v:shapes="_x0000_i1106"><img src="/cache/referats/9000/image155.gif" v:shapes="_x0000_i1107"> – 2 столбец исключен.
III. <img src="/cache/referats/9000/image157.gif" v:shapes="_x0000_i1108"><img src="/cache/referats/9000/image159.gif" v:shapes="_x0000_i1109"><img src="/cache/referats/9000/image161.gif" v:shapes="_x0000_i1110"><img src="/cache/referats/9000/image163.gif" v:shapes="_x0000_i1111"> – 1 строка исключена.
IV. <img src="/cache/referats/9000/image165.gif" v:shapes="_x0000_i1112"><img src="/cache/referats/9000/image167.gif" v:shapes="_x0000_i1113"><img src="/cache/referats/9000/image169.gif" v:shapes="_x0000_i1114"><img src="/cache/referats/9000/image171.gif" v:shapes="_x0000_i1115"> – 5 столбец исключен.
V. <img src="/cache/referats/9000/image173.gif" v:shapes="_x0000_i1116"><img src="/cache/referats/9000/image175.gif" v:shapes="_x0000_i1117"><img src="/cache/referats/9000/image177.gif" v:shapes="_x0000_i1118"><img src="/cache/referats/9000/image179.gif" v:shapes="_x0000_i1119"> – 4 строка исключена.
VI. <img src="/cache/referats/9000/image181.gif" v:shapes="_x0000_i1120"><img src="/cache/referats/9000/image183.gif" v:shapes="_x0000_i1121"><img src="/cache/referats/9000/image185.gif" v:shapes="_x0000_i1122"><img src="/cache/referats/9000/image187.gif" v:shapes="_x0000_i1123"> – 3 строка и 1 столбец исключены.
VII. <img src="/cache/referats/9000/image189.gif" v:shapes="_x0000_i1124"><img src="/cache/referats/9000/image191.gif" v:shapes="_x0000_i1125"><img src="/cache/referats/9000/image193.gif" v:shapes="_x0000_i1126"><img src="/cache/referats/9000/image195.gif" v:shapes="_x0000_i1127"> – 2 строка и 3столбец исключены.
Порассуждав таким образом, мыши получилиследующий начальный опорный план:
<img src="/cache/referats/9000/image197.gif" v:shapes="_x0000_i1128">;
<img src="/cache/referats/9000/image199.gif" v:shapes="_x0000_i1129">.
По этому опорному плану коту достанется аж 13 мышей(0,18 часть мыши отдельно вряд ли выживет). “Жирно ему будет”-, подумалимыши и стали составлять другой опорный планметодом северо-западногоугла.
Данный метод очень прост, пункты 1 и 2 в методемаксимальной загрузки заменяются на следующий: очередная загружаемаякоммуникация <img src="/cache/referats/9000/image201.gif" v:shapes="_x0000_i1130"> выбирается в левойверхней клетке сохраненной части таблицы, т.е. в северо-западном углу таблицы.Математически это выражается следующим образом:
<img src="/cache/referats/9000/image203.gif" v:shapes="_x0000_i1131">I – множествономеров пунктов производства;
<img src="/cache/referats/9000/image205.gif" v:shapes="_x0000_i1132">, J – множествономеров пунктов потребления;
Последовательно по итерациям метода получаем:
I. <img src="/cache/referats/9000/image207.gif" v:shapes="_x0000_i1133"><img src="/cache/referats/9000/image209.gif" v:shapes="_x0000_i1134"><img src="/cache/referats/9000/image211.gif" v:shapes="_x0000_i1135"><img src="/cache/referats/9000/image213.gif" v:shapes="_x0000_i1136"> – 1 столбец исключен.
II. <img src="/cache/referats/9000/image215.gif" v:shapes="_x0000_i1137"><img src="/cache/referats/9000/image217.gif" v:shapes="_x0000_i1138"><img src="/cache/referats/9000/image219.gif" v:shapes="_x0000_i1139"><img src="/cache/referats/9000/image221.gif" v:shapes="_x0000_i1140"> – 1 строка исключена.
III. <img src="/cache/referats/9000/image149.gif" v:shapes="_x0000_i1141"><img src="/cache/referats/9000/image224.gif" v:shapes="_x0000_i1142"><img src="/cache/referats/9000/image226.gif" v:shapes="_x0000_i1143"><img src="/cache/referats/9000/image228.gif" v:shapes="_x0000_i1144"> – 2 столбец исключен.
IV. <img src="/cache/referats/9000/image230.gif" v:shapes="_x0000_i1145"><img src="/cache/referats/9000/image232.gif" v:shapes="_x0000_i1146"><img src="/cache/referats/9000/image234.gif" v:shapes="_x0000_i1147"><img src="/cache/referats/9000/image236.gif" v:shapes="_x0000_i1148"> – 2 строка исключена.
V. <img src="/cache/referats/9000/image238.gif" v:shapes="_x0000_i1149"><img src="/cache/referats/9000/image240.gif" v:shapes="_x0000_i1150"><img src="/cache/referats/9000/image242.gif" v:shapes="_x0000_i1151"><img src="/cache/referats/9000/image244.gif" v:shapes="_x0000_i1152"> – 3 столбец исключен.
VI. <img src="/cache/referats/9000/image246.gif" v:shapes="_x0000_i1153"><img src="/cache/referats/9000/image248.gif" v:shapes="_x0000_i1154"><img src="/cache/referats/9000/image250.gif" v:shapes="_x0000_i1155"><img src="/cache/referats/9000/image252.gif" v:shapes="_x0000_i1156"> – 3 строка исключена.
VII. <img src="/cache/referats/9000/image254.gif" v:shapes="_x0000_i1157"><img src="/cache/referats/9000/image256.gif" v:shapes="_x0000_i1158"><img src="/cache/referats/9000/image258.gif" v:shapes="_x0000_i1159"><img src="/cache/referats/9000/image260.gif" v:shapes="_x0000_i1160"> – 4 столбец исключен.
VIII. <img src="/cache/referats/9000/image262.gif" v:shapes="_x0000_i1161"><img src="/cache/referats/9000/image264.gif" v:shapes="_x0000_i1162"><img src="/cache/referats/9000/image266.gif" v:shapes="_x0000_i1163"><img src="/cache/referats/9000/image268.gif" v:shapes="_x0000_i1164"> – 4 строка и 5столбец исключены.
окорок
мешок крупы
мешок муки
мешок картошки
журналы
5 0
18 8 0
17 5 0
22 17 0
8 0
нора 1
15 10 0
<img src="/cache/referats/9000/image104.gif" v:shapes="_x0000_i1165">
<img src="/cache/referats/9000/image106.gif" v:shapes="_x0000_i1166">
<img src="/cache/referats/9000/image108.gif" v:shapes="_x0000_i1167">
<img src="/cache/referats/9000/image110.gif" v:shapes="_x0000_i1168">
<img src="/cache/referats/9000/image112.gif" v:shapes="_x0000_i1169">
нора 2
20 12 0
<img src="/cache/referats/9000/image114.gif" v:shapes="_x0000_i1170">
<img src="/cache/referats/9000/image116.gif" v:shapes="_x0000_i1171">
<img src="/cache/referats/9000/image118.gif" v:shapes="_x0000_i1172">
<img src="/cache/referats/9000/image120.gif" v:shapes="_x0000_i1173">
<img src="/cache/referats/9000/image122.gif" v:shapes="_x0000_i1174">
нора 3
10 5 0
<img src="/cache/referats/9000/image110.gif" v:shapes="_x0000_i1175">
<img src="/cache/referats/9000/image104.gif" v:shapes="_x0000_i1176">
<img src="/cache/referats/9000/image126.gif" v:shapes="_x0000_i1177">
<img src="/cache/referats/9000/image128.gif" v:shapes="_x0000_i1178">
<img src="/cache/referats/9000/image130.gif" v:shapes="_x0000_i1179">
нора 4
25 8 0
<img src="/cache/referats/9000/image112.gif" v:shapes="_x0000_i1180">
<img src="/cache/referats/9000/image133.gif" v:shapes="_x0000_i1181">
<img src="/cache/referats/9000/image135.gif" v:shapes="_x0000_i1182">
<img src="/cache/referats/9000/image137.gif" v:shapes="_x0000_i1183">
<img src="/cache/referats/9000/image139.gif" v:shapes="_x0000_i1184">
Получили следующий опорный план:
<img src="/cache/referats/9000/image270.gif" v:shapes="_x0000_i1185">
<img src="/cache/referats/9000/image272.gif" v:shapes="_x0000_i1186">
Те же самые 13 мышей, и даже хуже предыдущегоопорного плана (если учитывать сотые). Пришлось мышам использовать методминимальных затрат.
В этом методе в первую очередь загружаются текоммуникации, в которых затраты на перевозку минимальные. В нашем случае, этоте пути, мышиные потери на которых минимальны.
VIII
окорок
мешок крупы
мешок муки
мешок картошки
журналы
5 0
18 0
17 0
22 20 18 15 0
8 0
нора 1
15 0
<img src="/cache/referats/9000/image104.gif" v:shapes="_x0000_i1187">
<img src="/cache/referats/9000/image106.gif" v:shapes="_x0000_i1188">
<img src="/cache/referats/9000/image108.gif" v:shapes="_x0000_i1189">
<img src="/cache/referats/9000/image110.gif" v:shapes="_x0000_i1190">
<img src="/cache/referats/9000/image112.gif" v:shapes="_x0000_i1191">
нора 2
20 3 0
<img src="/cache/referats/9000/image114.gif" v:shapes="_x0000_i1192">
<img src="/cache/referats/9000/image116.gif" v:shapes="_x0000_i1193">
<img src="/cache/referats/9000/image118.gif" v:shapes="_x0000_i1194">
<img src="/cache/referats/9000/image120.gif" v:shapes="_x0000_i1195">
<img src="/cache/referats/9000/image122.gif" v:shapes="_x0000_i1196">
нора 3
10 2 0
<img src="/cache/referats/9000/image110.gif" v:shapes="_x0000_i1197">
<img src="/cache/referats/9000/image104.gif" v:shapes="_x0000_i1198">
<img src="/cache/referats/9000/image126.gif" v:shapes="_x0000_i1199">
<img src="/cache/referats/9000/image128.gif" v:shapes="_x0000_i1200">
<img src="/cache/referats/9000/image130.gif" v:shapes="_x0000_i1201">
нора 4
25 7 2 0
<img src="/cache/referats/9000/image112.gif" v:shapes="_x0000_i1202">
<img src="/cache/referats/9000/image133.gif" v:shapes="_x0000_i1203">
<img src="/cache/referats/9000/image135.gif" v:shapes="_x0000_i1204">
<img src="/cache/referats/9000/image137.gif" v:shapes="_x0000_i1205">
<img src="/cache/referats/9000/image139.gif" v:shapes="_x0000_i1206">
I. <img src="/cache/referats/9000/image275.gif" v:shapes="_x0000_i1207"><img src="/cache/referats/9000/image277.gif" v:shapes="_x0000_i1208"><img src="/cache/referats/9000/image279.gif" v:shapes="_x0000_i1209"><img src="/cache/referats/9000/image281.gif" v:shapes="_x0000_i1210"> – 2 столбец исключен.
II. <img src="/cache/referats/9000/image173.gif" v:shapes="_x0000_i1211"><img src="/cache/referats/9000/image284.gif" v:shapes="_x0000_i1212"><img src="/cache/referats/9000/image286.gif" v:shapes="_x0000_i1213"><img src="/cache/referats/9000/image288.gif" v:shapes="_x0000_i1214"> – 1 столбец исключен.
III. <img src="/cache/referats/9000/image254.gif" v:shapes="_x0000_i1215"><img src="/cache/referats/9000/image291.gif" v:shapes="_x0000_i1216"><img src="/cache/referats/9000/image293.gif" v:shapes="_x0000_i1217"><img src="/cache/referats/9000/image295.gif" v:shapes="_x0000_i1218"> – 4 строка исключена.
IV. <img src="/cache/referats/9000/image165.gif" v:shapes="_x0000_i1219"><img src="/cache/referats/9000/image297.gif" v:shapes="_x0000_i1220"><img src="/cache/referats/9000/image299.gif" v:shapes="_x0000_i1221"><img src="/cache/referats/9000/image301.gif" v:shapes="_x0000_i1222"> – 5 столбец исключен.
V. <img src="/cache/referats/9000/image246.gif" v:shapes="_x0000_i1223"><img src="/cache/referats/9000/image304.gif" v:shapes="_x0000_i1224"><img src="/cache/referats/9000/image306.gif" v:shapes="_x0000_i1225"><img src="/cache/referats/9000/image308.gif" v:shapes="_x0000_i1226"> – 3 строка исключена.
VI. <img src="/cache/referats/9000/image230.gif" v:shapes="_x0000_i1227"><img src="/cache/referats/9000/image310.gif" v:shapes="_x0000_i1228"><img src="/cache/referats/9000/image312.gif" v:shapes="_x0000_i1229"><img src="/cache/referats/9000/image314.gif" v:shapes="_x0000_i1230"> – 3 столбец исключен.
VII. <img src="/cache/referats/9000/image316.gif" v:shapes="_x0000_i1231"><img src="/cache/referats/9000/image318.gif" v:shapes="_x0000_i1232"><img src="/cache/referats/9000/image320.gif" v:shapes="_x0000_i1233"><img src="/cache/referats/9000/image322.gif" v:shapes="_x0000_i1234"> – 2 строка исключена.
VIII. <img src="/cache/referats/9000/image324.gif" v:shapes="_x0000_i1235"><img src="/cache/referats/9000/image326.gif" v:shapes="_x0000_i1236"><img src="/cache/referats/9000/image328.gif" v:shapes="_x0000_i1237"><img src="/cache/referats/9000/image330.gif" v:shapes="_x0000_i1238"> – 1 строка и 4столбец исключены.
Опорный план:
<img src="/cache/referats/9000/image332.gif" v:shapes="_x0000_i1239">
Целевая функция:
<img src="/cache/referats/9000/image334.gif" v:shapes="_x0000_i1240">
Этот опорный план понравился мышам значительнобольше, но все равно потери достаточно велики (7 мышей). Теперь требовалосьрешить эту задачу и найти оптимальный план. И сделать они это собрались самымточным методом – методом потенциалов.
Если план действительно оптимален, то система (1)будет выполняться, т.е.:
1) длякаждой занятой клетки транспортной таблицы сумма потенциалов должна быть равна <img src="/cache/referats/9000/image336.gif" v:shapes="_x0000_i1241"> для этой клетки;
2) длякаждой незанятой клетки сумма потенциалов не больше (меньше или равно) <img src="/cache/referats/9000/image336.gif" v:shapes="_x0000_i1242">
Построим для каждой свободной переменной плана числа<img src="/cache/referats/9000/image338.gif" v:shapes="_x0000_i1243"> и они должны быть положительны.Так как число потенциалов равно 9, а система состоит из 8 уравнений, то длянахождения какого-либо решения этой системы необходимо первому из потенциаловпридать произвольное значение (например: <img src="/cache/referats/9000/image340.gif" v:shapes="_x0000_i1244">
<img src="/cache/referats/9000/image342.gif" v:shapes="_x0000_i1245"> <img src="/cache/referats/9000/image344.gif" v:shapes="_x0000_i1246">
<img src="/cache/referats/9000/image346.gif" v:shapes="_x0000_i1247"> <img src="/cache/referats/9000/image348.gif" v:shapes="_x0000_i1248">
<img src="/cache/referats/9000/image350.gif" v:shapes="_x0000_i1249"> <img src="/cache/referats/9000/image352.gif" v:shapes="_x0000_i1250">
<img src="/cache/referats/9000/image354.gif" v:shapes="_x0000_i1251"> <img src="/cache/referats/9000/image356.gif" v:shapes="_x0000_i1252">
окорок
мешок крупы
мешок муки
мешок картошки
журналы
нора 1
<img src="/cache/referats/9000/image104.gif" v:shapes="_x0000_i1253">
<img src="/cache/referats/9000/image106.gif" v:shapes="_x0000_i1254">
<img src="/cache/referats/9000/image108.gif" v:shapes="_x0000_i1255">
<img src="/cache/referats/9000/image110.gif" v:shapes="_x0000_i1256">
<img src="/cache/referats/9000/image112.gif" v:shapes="_x0000_i1257">
<img src="/cache/referats/9000/image340.gif" v:shapes="_x0000_i1258">
нора 2
<img src="/cache/referats/9000/image114.gif" v:shapes="_x0000_i1259">
<img src="/cache/referats/9000/image116.gif" v:shapes="_x0000_i1260">
<img src="/cache/referats/9000/image118.gif" v:shapes="_x0000_i1261">
<img src="/cache/referats/9000/image120.gif" v:shapes="_x0000_i1262">
<img src="/cache/referats/9000/image122.gif" v:shapes="_x0000_i1263">
<img src="/cache/referats/9000/image360.gif" v:shapes="_x0000_i1264">
нора 3
<img src="/cache/referats/9000/image110.gif" v:shapes="_x0000_i1265">
<img src="/cache/referats/9000/image104.gif" v:shapes="_x0000_i1266">
<img src="/cache/referats/9000/image126.gif" v:shapes="_x0000_i1267">
<img src="/cache/referats/9000/image128.gif" v:shapes="_x0000_i1268">
<img src="/cache/referats/9000/image130.gif" v:shapes="_x0000_i1269">
<img src="/cache/referats/9000/image362.gif" v:shapes="_x0000_i1270">
нора 4
<img src="/cache/referats/9000/image112.gif" v:shapes="_x0000_i1271">
<img src="/cache/referats/9000/image133.gif" v:shapes="_x0000_i1272">
<img src="/cache/referats/9000/image135.gif" v:shapes="_x0000_i1273">
<img src="/cache/referats/9000/image137.gif" v:shapes="_x0000_i1274">
<img src="/cache/referats/9000/image139.gif" v:shapes="_x0000_i1275">
<img src="/cache/referats/9000/image364.gif" v:shapes="_x0000_i1276">
<img src="/cache/referats/9000/image366.gif" v:shapes="_x0000_i1277">
<img src="/cache/referats/9000/image368.gif" v:shapes="_x0000_i1278">
<img src="/cache/referats/9000/image370.gif" v:shapes="_x0000_i1279">
<img src="/cache/referats/9000/image372.gif" v:shapes="_x0000_i1280">
<img src="/cache/referats/9000/image374.gif" v:shapes="_x0000_i1281">
Таким образом, после того, как все потенциалынайдены, можно искать <img src="/cache/referats/9000/image376.gif" v:shapes="_x0000_i1282">
<img src="/cache/referats/9000/image378.gif" v:shapes="_x0000_i1283"> <img src="/cache/referats/9000/image380.gif" v:shapes="_x0000_i1284">
<img src="/cache/referats/9000/image382.gif" v:shapes="_x0000_i1285"> <img src="/cache/referats/9000/image384.gif" v:shapes="_x0000_i1286">
<img src="/cache/referats/9000/image386.gif" v:shapes="_x0000_i1287"> <img src="/cache/referats/9000/image388.gif" v:shapes="_x0000_i1288">
<img src="/cache/referats/9000/image390.gif" v:shapes="_x0000_i1289"> <img src="/cache/referats/9000/image392.gif" v:shapes="_x0000_i1290">
<img src="/cache/referats/9000/image394.gif" v:shapes="_x0000_i1291"> <img src="/cache/referats/9000/image396.gif" v:shapes="_x0000_i1292">
<img src="/cache/referats/9000/image398.gif" v:shapes="_x0000_i1293"> <img src="/cache/referats/9000/image400.gif" v:shapes="_x0000_i1294">
Видно, что <img src="/cache/referats/9000/image402.gif" v:shapes="_x0000_i1295"> и <img src="/cache/referats/9000/image404.gif" v:shapes="_x0000_i1296"><img src="/cache/referats/9000/image406.gif" v:shapes="_x0000_i1297">
Строим цикл:
(2;1) – начальная точка цикла;
Что характерно, для этой точки (впрочем как и длядругих) мы можем построить только один цикл. Каждой клетке цикла приписываемопределенный знак:
(2;1) – “+”, (4; 1) – “-”, (4; 4) – “+” (2; 4) – “-”.
окорок
мешок крупы
мешок муки
мешок картошки
журналы
нора 1
<img src="/cache/referats/9000/image104.gif" v:shapes="_x0000_i1298">
<img src="/cache/referats/9000/image106.gif" v:shapes="_x0000_i1299">
<img src="/cache/referats/9000/image108.gif" v:shapes="_x0000_i1300">
<img src="/cache/referats/9000/image110.gif" v:shapes="_x0000_i1301">
<img src="/cache/referats/9000/image112.gif" v:shapes="_x0000_i1302">
нора 2
<img src="/cache/referats/9000/image114.gif" v:shapes="_x0000_i1303">
<img src="/cache/referats/9000/image116.gif" v:shapes="_x0000_i1304">
<img src="/cache/referats/9000/image118.gif" v:shapes="_x0000_i1305">
<img src="/cache/referats/9000/image120.gif" v:shapes="_x0000_i1306">
<img src="/cache/referats/9000/image122.gif" v:shapes="_x0000_i1307">
нора 3
<img src="/cache/referats/9000/image110.gif" v:shapes="_x0000_i1308">
<img src="/cache/referats/9000/image104.gif" v:shapes="_x0000_i1309">
<img src="/cache/referats/9000/image126.gif" v:shapes="_x0000_i1310">
<img src="/cache/referats/9000/image128.gif" v:shapes="_x0000_i1311">
<img src="/cache/referats/9000/image130.gif" v:shapes="_x0000_i1312">
нора 4
<img src="/cache/referats/9000/image112.gif" v:shapes="_x0000_i1313">
<img src="/cache/referats/9000/image133.gif" v:shapes="_x0000_i1314">
<img src="/cache/referats/9000/image135.gif" v:shapes="_x0000_i1315">
<img src="/cache/referats/9000/image137.gif" v:shapes="_x0000_i1316">
<img src="/cache/referats/9000/image139.gif" v:shapes="_x0000_i1317">
В клетках с “+” – увеличиваем загрузку, а в клетках с “-” – уменьшаем. Величина, на которуюувеличиваем или уменьшаем всегда одна и она определяется из условия:
<img src="/cache/referats/9000/image409.gif" v:shapes="_x0000_i1318"><img src="/cache/referats/9000/image002.gif" v:shapes="_x0000_i1319">“-”.
Таким образом получаем:
<img src="/cache/referats/9000/image412.gif" v:shapes="_x0000_i1320">; 4), где в процессе реализации цикла загрузкауменьшится до 0.
Перейдем к новому опорному плану
окорок
мешок крупы
мешок муки
мешок картошки
журналы
нора 1
<img src="/cache/referats/9000/image104.gif" v:shapes="_x0000_i1321">
<img src="/cache/referats/9000/image106.gif" v:shapes="_x0000_i1322">
<img src="/cache/referats/9000/image108.gif" v:shapes="_x0000_i1323">
<img src="/cache/referats/9000/image110.gif" v:shapes="_x0000_i1324">
<img src="/cache/referats/9000/image112.gif" v:shapes="_x0000_i1325">
<img src="/cache/referats/9000/image340.gif" v:shapes="_x0000_i1326">
нора 2
<img src="/cache/referats/9000/image114.gif" v:shapes="_x0000_i1327">
<img src="/cache/referats/9000/image116.gif" v:shapes="_x0000_i1328">
<img src="/cache/referats/9000/image118.gif" v:shapes="_x0000_i1329">
<img src="/cache/referats/9000/image120.gif" v:shapes="_x0000_i1330">
<img src="/cache/referats/9000/image122.gif" v:shapes="_x0000_i1331">
<img src="/cache/referats/9000/image416.gif" v:shapes="_x0000_i1332">
нора 3
<img src="/cache/referats/9000/image110.gif" v:shapes="_x0000_i1333">
<img src="/cache/referats/9000/image104.gif" v:shapes="_x0000_i1334">
<img src="/cache/referats/9000/image126.gif" v:shapes="_x0000_i1335">
<img src="/cache/referats/9000/image128.gif" v:shapes="_x0000_i1336">
<img src="/cache/referats/9000/image130.gif" v:shapes="_x0000_i1337">
<img src="/cache/referats/9000/image362.gif" v:shapes="_x0000_i1338">
