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