курсовые,контрольные,дипломы,рефераты
Телешовой Елизаветы, гр. 726,
В некотором царстве, некотором государстве жил-был кот Василий, который очень любил мышей… на обед. А обедал он исключительно в амбаре своего хозяина, да так хорошо, что бедные мыши и носу не могли высунуть из своих нор. Но всю жизнь в норе не просидишь, есть то хочется, и стали мыши думать и гадать, как им провести кота Василия и до заветных пищевых ресурсов амбара добраться.
В амбаре было 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 |
В левом верхнем углу каждой ячейки таблицы мыши указали число попавших в лапы кота (в процентах) по отношению к общему числу мышей из
Безусловно, цель мышей – добраться до еды с минимальными потерями по дороге, то есть:
Таким образом:
Необходимо, конечно, оценить и выгодность передвижения из каждой норы к каждому пищевому ресурсу. Для этого мыши оценили так называемые потенциалы нор (
(1).
Система (1) и будет служить в дальнейшем критерием оптимальности плана.
Запишем подробно двойственную задачу на основе этого ограничения:
; ; ; ;
Критерием двойственной задачи будет максимизация выгодности:
Первое, что пришло на ум мышам – использовать те источники пищи, доступ к которым легче, и они решили построить начальный опорный план по методу максимальной загрузки, исходя из формулы:
(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 |
||||||||||||
нора 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 часть мыши отдельно вряд ли выживет). “Жирно ему будет”-, подумали мыши и стали составлять другой опорный план методом северо-западного угла.
Данный метод очень прост, пункты 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 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 мышей). Теперь требовалось решить эту задачу и найти оптимальный план. И сделать они это собрались самым точным методом – методом потенциалов.
Если план действительно оптимален, то система (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 |
||||||
нора 4 |
25 |
||||||
Определяем
Все больше 0, следовательно план оптимальный.
Целевая функция при этом плане:
М-да, незначительное улучшение для мышей. Целых 6 мышей и еще один мышиный хвостик – такова ежедневная дань коту Василию. Но делать нечего, и стали мыши действовать по этому плану.
И все было бы хорошо, но в 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, поэтому существующий опорный план можно улучшить. Поскольку и переходим к новому опорному плану.
Норы |
окорок |
мешок крупы |
мешок муки |
мешок картошки |
журналы |
R |
||||||
5 |
18 |
17 |
22 |
8 |
10 |
|||||||
нора 1 |
15 |
|||||||||||
нора 2 |
20 |
3 |
17 |
|||||||||
нора 3 |
20 |
12 |
8 |
|||||||||
нора 4 |
25 |
5 |
15 |
|||||||||
Определяем
меньше 0, поэтому существующий опорный план можно также улучшить. Теперь мы будем вводить в базис вектор, соответствующий клетке (2; 1). Строим цикл и переходим к новому опорному плану.
ПищаНоры |
окорок |
мешок крупы |
мешок муки |
мешок картошки |
журналы |
R |
||
5 |
18 |
17 |
22 |
8 |
10 |
|||
нора 1 |
15 |
|||||||
нора 2 |
20 |
17 |
||||||
нора 3 |
20 |
12 |
8 |
|||||
нора 4 |
25 |
18 |
||||||
Определяем
Все больше 0, следовательно план оптимальный.
Целевая функция при этом плане:
Этот план чуть хуже предыдущего, к тому же 10 мышей из первой норы остаются голодными. Во всяком случае питаются раз в три дня.
Но кот Василий тоже не дремал, и, произведя те же операции, что и мыши в свое время, определил оптимальный план их передвижений (см. пункт 6). Посмотрев на него, он сразу решил взять под особый контроль путь от второй норы к мешку муки и от четвертой норы к мешку крупы.
Вскоре мыши это на себе почувствовали, а почувствовав, кинулись составлять новый оптимальный план, пометив эти два маршрута как чрезвычайно опасные буквой М
ПищаНоры |
окорок |
мешок крупы |
мешок муки |
мешок картошки |
журналы |
||
5 |
18 |
17 |
22 |
8 |
|||
Нора 1 |
15 |
||||||
Нора 2 |
20 |
||||||
Нора 3 |
10 |
||||||
Нора 4 |
25 |
||||||
Видно, что этот план уже является оптимальным.
Целевая функция:
Как зыбко мышиное счастье. Стоило коту взяться за дело всерьез, и потери возросли чуть ли не в два раза.
Лабораторная работа № 5 Телешовой Елизаветы, гр. 726, Транспортные задачи линейного программирования. 1. Постановка задачи. В некотором царстве, некотором государстве жил-был кот Василий, который очень любил мышей… на обед. А обедал он исклю
Лабораторная работа №4 по "Основам теории систем" (Послеоптимизационный анализ задач линейного программирования)
Лабораторная работа №3 по "Основам теории систем" (Теория двойственности в задачах линейного программирования)
Лабораторная работа №2 по "Основам теории систем" (Решение задач линейного программирования симплекс-методом. Варианты разрешимости задач линейного программирования)
Лабораторная работа №6 по "Основам теории систем" (Решение задачи о ранце методом ветвей и границ)
Copyright (c) 2024 Stud-Baza.ru Рефераты, контрольные, курсовые, дипломные работы.