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