Задачи оптимизации в теории управления

Оглавление
Введение 2
1. Линейное программирование 3
2. Динамическое программирование 6
3. Теория графов и оптимизация 11
Заключение 13
Литература 14

Далее на этапе безусловной оптимизации для всех последующих шагов вычисляется величина и оптимальным управлением на k -м шаге является то значение , которое обеспечивает максимум дохода при соответствующем состоянии системы . 3. Теорияграфов и оптимизацияв форме той или иной задачи оптимизации на графах могут быть сформулированы многие прикладные задачи оптимизации. В теории графов наряду с этим многие занимательные задачи связаны с решением задач оптимизации. Из достаточно значительногоколичества типовых задач оптимизации на графах можно выделить основные и в некотором смысле ставшие классическими для данного класса: задача нахождения критического пути в сетевом графе;  задача нахождения оптимальных покрывающих деревьев;  задача нахождения кратчайшего пути в графе;  задача нахождения максимального потока в графе. Для каждой из перечисленных задач поставлена в соответствие математическая постановка задачи в форме модели булева или целочисленного программирования. В то же время существуют специальные алгоритмы их решения, которые учитывают специфические особенности постановки этих задач.Задача коммивояжёра является важной задачей транспортной логистики, отрасли, которая занимается планированием транспортных перевозок. Коммивояжёру, чтобы распродать необходимые и не очень необходимые в хозяйстве товары, следует объехать  пунктов и в конце концов вернуться в исходный пункт. Требуетсяопределить наиболее выгодный маршрут объезда. В качестве меры выгодности маршрута (точнее говоря, невыгодности) может служить суммарная стоимость дороги, суммарное время в пути, или, в простейшем случае, длина маршрута. Задача обэкстремальном путиЗадачи поиска длиннейших и кратчайших путей на графах возникают в разных областях управления.Задача о кратчайшем пути. Пусть из вершины задана сеть, то есть ориентированный граф, в котором 2 вершины выделены– вход (нулевая вершина ) и выход (вершина с номером ).Для каждой дуги заданы числа,которые называются длинами дуг.Сумма длин входящих в него дугназывается длиной пути (контура)(если не заданы длины дуг, то длина пути (контура) обусловливаетсякак количество входящих в него дуг).В поискекратчайшего пути (пути минимальной длины) от входа до выхода сети заключается задача 1.Для существования кратчайшего пути необходимо и достаточно отсутствия в сети контуров отрицательной длины.Предположим, что в сети контуров нет.В этом случаевершины всегда можно пронумеровать таким образом, что для любой дуги Такая нумерация именуетсяправильной. Легко показать, что всегда в сети без контуров имеется правильная нумерация.Длину дуги (i; j) обозначим lij.В сети кратчайший путь,который имеет правильную нумерацию, определяется следующим алгоритмом.Алгоритм 1.Шаг 0: Помечаем нулевую вершину индексом - 0= 0;Шаг k:вершину kпомечаем индексом k=min(i+ lik),ik.Задача о максимальном потоке. Рассмотрим сеть, которая состоит из (n + 1) вершины. Пусть каждой дуге по-ставлено в соответствие число cij,который называетсяпропускной способностью дуги(i; j).В сети совокупность чисел {xij}называетсяпотоком x. При этом xijявляется потоком по дуге (i; j),который удовлетворяет условиям 0≤xij≤ciВ определениипотока максимальной величинызаключаетсязадача о максимальном потоке.В сети разрезом Wназывается каждое множество вершин,который обязательно содержит выход и не содержит вход. Пропускной способностью С(W) разреза W называется сумма пропускных способностей дуг, заходящих в разрез.Следовательно, если поток удастся найти, величина которого равна пропускной способности некоторого разреза, то этот поток является максимальным, а разрез - минимальным.Заключение В разных проблемах принятия решений появляются самые различные задачи оптимизации. Для их решения применяются те или иные методы, приближенные или точные. В теоретико-экономических исследованиях часто используются задачи оптимизации. Формированиеи развитие современного общества характеризуется увеличением технического уровня, управления войсками, углублением общественного разделения труда, усложнением организационной структуры производства, предъявлением значительных требований к методам планирования хозяйственного и военного руководства. Научный подход к руководству хозяйственной жизнью общества в этих условиях только позволит обеспечить высокие темпы развития народного хозяйства. Научного подхода требует и решение стратегических и тактических задач.ЛитератураГасс С.П., Путешествие в страну линейного программирования / Пер. с англ. - М.: Мир, 1973, 176с.Белов В.Б., Теория графов. - М.: Высшая школа, 1976, 392с.Бурков В.Н., Теория графов в управлении организационными системами. – М.: «Синтег», 2010, 124с.Орлов А.И., Задачи оптимизации и нечеткие переменные. – М.:«Знание», 1990.,64с.Орлов А.И., Эконометрика. – М.: «Экзамен», 2002,576с.Карнадская, Н.Л. Принятие управленческого решения - М.: ЮНИТИ, 1999,265с.Кофман А., Фор Р. Займемся исследованием операций / Пер. с франц.. - М,: Мир, 1976, 280 с.Планкетт Л.Т., Выработка и принятие управленческих решений - М.: ПРИОР, 1998, 300с.Шелобаев С.И., Математические методы и модели в экономике, финансах, бизнесе «ЮНИТИ-ДАНА» 2001, 367Фатхутдинов Р.А., Управленческие решения - М.: ИНФРА-М, 2001, 324с.Эддоус М.П, Методы принятия решений - М.: ИНФРА-М, 1999.Якокка Л.Р., Карьера менеджера - Мн.: Парадокс, 2000, 548с.