Реферат: Лабораторная работа №5 по "Основам теории систем" (Транспортные задачи линейного программирования)

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

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

Транспортные задачи линейногопрограммирования.1. Постановказадачи.

В некотором царстве, некотором государстве жил-былкот Василий, который очень любил мышей… на обед. А обедал он исключительно вамбаре своего хозяина, да так хорошо, что бедные мыши и носу не могли высунутьиз своих нор. Но всю жизнь в норе не просидишь, есть то хочется, и стали мышидумать и гадать, как им провести кота Василия и до заветных пищевых ресурсовамбара добраться.

В амбаре было 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/image024.gif" v:shapes="_x0000_s1033"> Пища Норы

окорок

мешок крупы

мешок муки

мешок картошки

журналы

нора 1

нора 2

нора 3

нора 4

В левом верхнем углу каждойячейки таблицы мыши указали число попавших в лапы кота (в процентах) поотношению к общему числу мышей из <img src="/cache/referats/9000/image004.gif" v:shapes="_x0000_i1058"><img src="/cache/referats/9000/image006.gif" v:shapes="_x0000_i1059">

Безусловно, цель мышей –добраться до еды с минимальными потерями по дороге, то есть:

Таким образом:

2. Двойственаязадача.

Необходимо, конечно, оценитьи выгодность передвижения из каждой норы к каждому пищевому ресурсу. Для этогомыши оценили так называемые потенциалы нор (<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) и будет служитьв дальнейшем критерием оптимальности плана.

Запишем подробнодвойственную задачу на основе этого ограничения:

Критерием двойственнойзадачи будет максимизация выгодности:

3. Методпоследовательной максимальной загрузкивыбранных коммуникаций.

Первое, что пришло на уммышам – использовать те источники пищи, доступ к которым легче, и они решилипостроить начальный опорный план по методу максимальной загрузки, исходя изформулы:

<img src="/cache/referats/9000/image091.gif" v:shapes="_x0000_i1072"> (2).

т.е. выбираются те варианты, которые могутобеспечить едой максимальное количество мышей, и эти варианты будутиспользоваться в соответствии с (2).

Поскольку хотят есть все мыши во всех норах, томодель закрытая, т.е.

Общая схема построенияначального опорного плана по методу максимальной загрузки такова:

1) Выбираем коммуникацию,которую можно больше всего загрузить.

2) Максимально ее загружаемв соответствии с (2).

3) Корректируем объемы производства и потребленияна величину выбранной перевозки, вычисляя остатки производства и потребления:

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, пока не будут перечеркнуты всестроки или столбцы

В нашем случае это выглядит следующим образом:

III

VII

<img src="/cache/referats/9000/image102.gif" v:shapes="_x0000_s1056 _x0000_s1034 _x0000_s1035 _x0000_s1036 _x0000_s1037 _x0000_s1038 _x0000_s1039 _x0000_s1040 _x0000_s1041 _x0000_s1042 _x0000_s1043 _x0000_s1044 _x0000_s1045 _x0000_s1046 _x0000_s1047 _x0000_s1048 _x0000_s1049 _x0000_s1050 _x0000_s1051 _x0000_s1052 _x0000_s1053 _x0000_s1054 _x0000_s1055"> Пища Норы

окорок

мешок крупы

мешок муки

мешок картошки

журналы

5 2 0

18 0

17 2 0

22 0

8 0

нора 1

15 0

нора 2

20 2 0

<img src="/cache/referats/9000/image118.gif" v:shapes="_x0000_i1087">2

нора 3

10 2 0

<img src="/cache/referats/9000/image110.gif" v:shapes="_x0000_i1090">2

нора 4

25 3 0

<img src="/cache/referats/9000/image112.gif" v:shapes="_x0000_i1095">3

Римскими цифрами пронумерован порядок итераций.

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 часть мыши отдельно вряд ли выживет). “Жирно ему будет”-, подумалимыши и стали составлять другой опорный планметодом северо-западногоугла.

4. Методсеверо-западного угла.

Данный метод очень прост, пункты 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

нора 2

20 12 0

нора 3

10 5 0

нора 4

25 8 0

Получили следующий опорный план:

Те же самые 13 мышей, и даже хуже предыдущегоопорного плана (если учитывать сотые). Пришлось мышам использовать методминимальных затрат.

5. Метод минимальных затрат.

В этом методе в первую очередь загружаются текоммуникации, в которых затраты на перевозку минимальные. В нашем случае, этоте пути, мышиные потери на которых минимальны.

III

VII

VIII

<img src="/cache/referats/9000/image273.gif" v:shapes="_x0000_s1267 _x0000_s1226 _x0000_s1227 _x0000_s1228 _x0000_s1229 _x0000_s1230 _x0000_s1231 _x0000_s1232 _x0000_s1233 _x0000_s1241 _x0000_s1250 _x0000_s1252 _x0000_s1253 _x0000_s1254 _x0000_s1255 _x0000_s1256 _x0000_s1257 _x0000_s1258 _x0000_s1259 _x0000_s1260 _x0000_s1261 _x0000_s1262 _x0000_s1263 _x0000_s1264 _x0000_s1265 _x0000_s1266"> Пища Норы

окорок

мешок крупы

мешок муки

мешок картошки

журналы

5 0

18 0

17 0

22 20 18 15 0

8 0

нора 1

15 0

нора 2

20 3 0

нора 3

10 2 0

нора 4

25 7 2 0

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столбец исключены.

Опорный план:

Целевая функция:

Этот опорный план понравился мышам значительнобольше, но все равно потери достаточно велики (7 мышей). Теперь требовалосьрешить эту задачу и найти оптимальный план. И сделать они это собрались самымточным методом – методом потенциалов.

6. Решениезадачи методом потенциалов.

Если план действительно оптимален, то система (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/image357.gif" v:shapes="_x0000_s1321"> Пища Норы

окорок

мешок крупы

мешок муки

мешок картошки

журналы

нора 1

нора 2

нора 3

нора 4

Таким образом, после того, как все потенциалынайдены, можно искать <img src="/cache/referats/9000/image376.gif" v:shapes="_x0000_i1282">

Видно, что <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) – “-”.

<img src="/cache/referats/9000/image407.gif" v:shapes="_x0000_s1360 _x0000_s1355 _x0000_s1324 _x0000_s1350 _x0000_s1351 _x0000_s1352 _x0000_s1353 _x0000_s1354 _x0000_s1356 _x0000_s1357 _x0000_s1358 _x0000_s1359"> Пища Норы

окорок

мешок крупы

мешок муки

мешок картошки

журналы

нора 1

нора 2

нора 3

нора 4

В клетках с “+” – увеличиваем загрузку, а в клетках с “-” – уменьшаем. Величина, на которуюувеличиваем или уменьшаем всегда одна и она определяется из условия:

<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.

Перейдем к новому опорному плану

<img src="/cache/referats/9000/image413.gif" v:shapes="_x0000_s1361"> Пища Норы

окорок

мешок крупы

мешок муки

мешок картошки

журналы

нора 1

нора 2