Далее на этапе безусловной оптимизации для всех последующих шагов вычисляется величина и оптимальным управлением на kм шаге является то значение, которое обеспечивает максимум дохода при соответствующем состоянии системы. 3. Теорияграфов и оптимизацияв форме той или иной задачи оптимизации на графах могут быть сформулированы многие прикладные задачи оптимизации. В теории графов наряду с этим многие занимательные задачи связаны с решением задач оптимизации. Из достаточно значительногоколичества типовых задач оптимизации на графах можно выделить основные и в некотором смысле ставшие классическими для данного класса: задача нахождения критического пути в сетевом графе; задача нахождения оптимальных покрывающих деревьев; задача нахождения кратчайшего пути в графе; задача нахождения максимального потока в графе. Для каждой из перечисленных задач поставлена в соответствие математическая постановка задачи в форме модели булева или целочисленного программирования.
В то же время существуют специальные алгоритмы их решения, которые учитывают специфические особенности постановки этих задач. Задача коммивояжёра является важной задачей транспортной логистики, отрасли, которая занимается планированием транспортных перевозок. Коммивояжёру, чтобы распродать необходимые и не очень необходимые в хозяйстве товары, следует объехать пунктов и в конце концов вернуться в исходный пункт. Требуетсяопределить наиболее выгодный маршрут объезда. В качестве меры выгодности маршрута (точнее говоря, невыгодности) может служить суммарная стоимость дороги, суммарное время в пути, или, в простейшем случае, длина маршрута. Задача обэкстремальном пути
Задачи поиска длиннейших и кратчайших путей на графах возникают в разных областях управления. Задача о кратчайшем пути. Пусть из вершины задана сеть, то есть ориентированный граф, в котором 2 вершины выделены- вход (нулевая вершина) и выход (вершина с номером).Для каждой дуги заданы числа, которые называются длинами дуг. Сумма длин входящих в него дугназывается длиной пути (контура)(если не заданы длины дуг, то длина пути (контура) обусловливаетсякак количество входящих в него дуг).В поискекратчайшего пути (пути минимальной длины) от входа до выхода сети заключается задача 1. Для существования кратчайшего пути необходимо и достаточно отсутствия в сети контуров отрицательной длины. Предположим, что в сети контуров нет. В этом случаевершины всегда можно пронумеровать таким образом, что для любой дуги Такая нумерация именуетсяправильной. Легко показать, что всегда в сети без контуров имеется правильная нумерация. Длину дуги (i; j) обозначим lij. В сети кратчайший путь, который имеет правильную нумерацию, определяется следующим алгоритмом. Алгоритм 1. Шаг 0: Помечаем нулевую вершину индексом — 0= 0;Шаг k: вершину kпомечаем индексом k=min (i+ lik), ik.Задача о максимальном потоке. Рассмотрим сеть, которая состоит из (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с.
