Реферат по предмету "Теория систем управления"


Лабораторная работа №5 по "Основам теории систем" (Транспортные задачи линейного программирования)

Лабораторнаяработа № 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


Не сдавайте скачаную работу преподавателю!
Данный реферат Вы можете использовать для подготовки курсовых проектов.

Поделись с друзьями, за репост + 100 мильонов к студенческой карме :

Пишем реферат самостоятельно:
! Как писать рефераты
Практические рекомендации по написанию студенческих рефератов.
! План реферата Краткий список разделов, отражающий структура и порядок работы над будующим рефератом.
! Введение реферата Вводная часть работы, в которой отражается цель и обозначается список задач.
! Заключение реферата В заключении подводятся итоги, описывается была ли достигнута поставленная цель, каковы результаты.
! Оформление рефератов Методические рекомендации по грамотному оформлению работы по ГОСТ.

Читайте также:
Виды рефератов Какими бывают рефераты по своему назначению и структуре.

Сейчас смотрят :

Реферат Особливості оподаткування прибутку юридичних осіб від операцій з цінними паперами
Реферат Просвещенный абсолютизм в России
Реферат Основные этапы в истории Древнего Египта. Общественный и государственный строй
Реферат Разработка и обоснование бизнес-плана малого предприятия по производству деловой одежды для женщ
Реферат Особенности составления и оформления организационно распорядительных документов.Систематизация д
Реферат Особенности преступности несовершеннолетних на материалах Красноа
Реферат Психологічні особливості формування пізнавальних здібностей та пізнавальної активності молодших Ознайомлення із
Реферат Ocean Pollution Essay Research Paper Ocean Pollution
Реферат Типичные проблемы неуспеваемости в учебной деятельности младших школьников
Реферат Eduational Research Foundation Essay Research Paper Educational
Реферат Органы налоговой службы
Реферат Освобождение от уголовной ответственности 11
Реферат Особенности судебного следствия
Реферат Краткая историческая справка развития картографии в России и зарубежом
Реферат Феномен социального недоверия