Лабораторнаяработа № 5
ТелешовойЕлизаветы, гр. 726,Транспортные задачи линейногопрограммирования.1. Постановказадачи.
В некотором царстве, некотором государстве жил-былкот Василий, который очень любил мышей… на обед. А обедал он исключительно вамбаре своего хозяина, да так хорошо, что бедные мыши и носу не могли высунутьиз своих нор. Но всю жизнь в норе не просидишь, есть то хочется, и стали мышидумать и гадать, как им провести кота Василия и до заветных пищевых ресурсовамбара добраться.
В амбаре было 4 мышиныхноры: в первой проживало 15 мышей, во второй – 20, в третьей – 10 мышей, а вчетвертой – 25 мышей, а также 5 источников пищи, от которых и кормилась вся этаорава мышей: у окорока – 5 мышей, у мешка крупы – 18 мышей, у мешка муки – 17мышей, у мешка картошки – 22 мыши и у стопки старых газет и журналовэротического содержания – 8 мышей.
И тут мыши вспомнили, что когда-то в стопке журналовлежала книжка по математическому программированию. Конечно мыши давным-давноуспели ее сгрызть, но кое-что из нее они, пока грызли, прочитать успели, вчастности, как решать транспортные задачи.
Считая что количество мышей, проживающих в
1);
2)
ну и конечно
Исходя из этих условий онисоставили математическую модель процесса своего питания:
; ;
Ну, и для наглядностинарисовали ее в виде таблицы: Пища Норы
окорок
мешок крупы
мешок муки
мешок картошки
журналы
5
18
17
22
8
нора 1
15
нора 2
20
нора 3
10
нора 4
25
В левом верхнем углу каждойячейки таблицы мыши указали число попавших в лапы кота (в процентах) поотношению к общему числу мышей из
Безусловно, цель мышей –добраться до еды с минимальными потерями по дороге, то есть:
Таким образом:
2. Двойственаязадача.
Необходимо, конечно, оценитьи выгодность передвижения из каждой норы к каждому пищевому ресурсу. Для этогомыши оценили так называемые потенциалы нор (
(1).
Система (1) и будет служитьв дальнейшем критерием оптимальности плана.
Запишем подробнодвойственную задачу на основе этого ограничения:
; ; ; ;
Критерием двойственнойзадачи будет максимизация выгодности:
3. Методпоследовательной максимальной загрузкивыбранных коммуникаций.
Первое, что пришло на уммышам – использовать те источники пищи, доступ к которым легче, и они решилипостроить начальный опорный план по методу максимальной загрузки, исходя изформулы:
(2).
т.е. выбираются те варианты, которые могутобеспечить едой максимальное количество мышей, и эти варианты будутиспользоваться в соответствии с (2).
Поскольку хотят есть все мыши во всех норах, томодель закрытая, т.е.
Общая схема построенияначального опорного плана по методу максимальной загрузки такова:
1) Выбираем коммуникацию,которую можно больше всего загрузить.
2) Максимально ее загружаемв соответствии с (2).
3) Корректируем объемы производства и потребленияна величину выбранной перевозки, вычисляя остатки производства и потребления:
;
4) Вычеркиваем в транспортной таблице строку или столбец с нулевым объемомпроизводства или потребления:
если – вычеркиваем
если – вычеркиваем ;
5) Повторяем этот процесс с пункта 1 по 4, пока не будут перечеркнуты всестроки или столбцы
В нашем случае это выглядит следующим образом:
I
II
III
IV
V
VI
VII Пища Норы
окорок
мешок крупы
мешок муки
мешок картошки
журналы
5 2 0
18 0
17 2 0
22 0
8 0
нора 1
15 0
нора 2
20 2 0
2
нора 3
10 2 0
2
нора 4
25 3 0
3
Римскими цифрами пронумерован порядок итераций.
I. – 4 столбец исключен.
II. – 2 столбец исключен.
III. – 1 строка исключена.
IV. – 5 столбец исключен.
V. – 4 строка исключена.
VI. – 3 строка и 1 столбец исключены.
VII. – 2 строка и 3столбец исключены.
Порассуждав таким образом, мыши получилиследующий начальный опорный план:
;
.
По этому опорному плану коту достанется аж 13 мышей(0,18 часть мыши отдельно вряд ли выживет). “Жирно ему будет”-, подумалимыши и стали составлять другой опорный планметодом северо-западногоугла.4. Методсеверо-западного угла.
Данный метод очень прост, пункты 1 и 2 в методемаксимальной загрузки заменяются на следующий: очередная загружаемаякоммуникация выбирается в левойверхней клетке сохраненной части таблицы, т.е. в северо-западном углу таблицы.Математически это выражается следующим образом:
I – множествономеров пунктов производства;
, J – множествономеров пунктов потребления;
Последовательно по итерациям метода получаем:
I. – 1 столбец исключен.
II. – 1 строка исключена.
III. – 2 столбец исключен.
IV. – 2 строка исключена.
V. – 3 столбец исключен.
VI. – 3 строка исключена.
VII. – 4 столбец исключен.
VIII. – 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. Метод минимальных затрат.
В этом методе в первую очередь загружаются текоммуникации, в которых затраты на перевозку минимальные. В нашем случае, этоте пути, мышиные потери на которых минимальны.
I
II
III
IV
V
VI
VII
VIII Пища Норы
окорок
мешок крупы
мешок муки
мешок картошки
журналы
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. – 2 столбец исключен.
II. – 1 столбец исключен.
III. – 4 строка исключена.
IV. – 5 столбец исключен.
V. – 3 строка исключена.
VI. – 3 столбец исключен.
VII. – 2 строка исключена.
VIII. – 1 строка и 4столбец исключены.
Опорный план:
Целевая функция:
Этот опорный план понравился мышам значительнобольше, но все равно потери достаточно велики (7 мышей). Теперь требовалосьрешить эту задачу и найти оптимальный план. И сделать они это собрались самымточным методом – методом потенциалов.6. Решениезадачи методом потенциалов.
Если план действительно оптимален, то система (1)будет выполняться, т.е.:
1) длякаждой занятой клетки транспортной таблицы сумма потенциалов должна быть равна для этой клетки;
2) длякаждой незанятой клетки сумма потенциалов не больше (меньше или равно)
Построим для каждой свободной переменной плана числа и они должны быть положительны.Так как число потенциалов равно 9, а система состоит из 8 уравнений, то длянахождения какого-либо решения этой системы необходимо первому из потенциаловпридать произвольное значение (например:
Пища Норы
окорок
мешок крупы
мешок муки
мешок картошки
журналы
5
18
17
22
8
нора 1
15
нора 2
20
нора 3
10
нора 4
25
Таким образом, после того, как все потенциалынайдены, можно искать
Видно, что и
Строим цикл:
(2;1) – начальная точка цикла;
Что характерно, для этой точки (впрочем как и длядругих) мы можем построить только один цикл. Каждой клетке цикла приписываемопределенный знак:
(2;1) – “+”, (4; 1) – “-”, (4; 4) – “+” (2; 4) – “-”.
+
+
-
- Пища Норы
окорок
мешок крупы
мешок муки
мешок картошки
журналы
5
18
17
22
8
нора 1
15
нора 2
20
нора 3
10
нора 4
25
В клетках с “+” – увеличиваем загрузку, а в клетках с “-” – уменьшаем. Величина, на которуюувеличиваем или уменьшаем всегда одна и она определяется из условия:
“-”.
Таким образом получаем:
; 4), где в процессе реализации цикла загрузкауменьшится до 0.
Перейдем к новому опорному плану Пища Норы
окорок
мешок крупы
мешок муки
мешок картошки
журналы
5
18
17
22
8
нора 1
15
нора 2
20
нора 3
10