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