Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение
высшего образования
«Российский государственный гуманитарный университет»
Филиал РГГУ в г. Домодедово
Кафедра математических и естественнонаучных дисциплин
УЧЕБНО-МЕТОДИЧЕСКОЕ ПОСОБИЕ
Для самостоятельного приобретения знаний и овладения умениями
По дисциплине
МЕТОДЫОПТИМАЛЬНЫХ РЕШЕНИЙ
(направление ЭКОНОМИКА)
(Бесконтактная форма обучения)
Самостоятельное занятие 1
Тема: Принятие оптимальных решений по совершенствованию структур систем управления на основе теории графов
Время: 4 часа
Разработал профессор СМИРНОВ В.Е.
Домодедово 2019
Самостоятельное занятие 1
Тема занятия: Принятие оптимальных решений по совершенствованию структур систем управления организациями на основе теории графов
Время: 4 часа
Теоретическая часть
Элементы теории управления
В общем случае – управление – целенаправленный процесс перевода объекта управления из одного состояния в другое путем воздействия на него управляющими воздействиями, вырабатываемыми органом управления из совокупности допустиых.
Независимо от типа объекта управления процесс управления всегда включает обобщенно четыре этапа:
- получение информации о задачах и целях управления;
- сбор информации о состоянии объекта управления и внешней среды;
- анализ полученной информации и выработка решения по переводу объекта управления в требуемое состояние;
- исполнение решения и контроль за его реализацией.
Формально процесс управления реализуется в рамках системы управления.
|
|
Система управления – совокупность взаимодействующих между собой органа управления и объекта управления, деятельность которых направлена на достижение заданной цели.
В зависимости от типа объекта управления различают:
- системы управления организационного типа (в объект управления входят коллективы людей). К таким объектам относятся фирмы, предприятия, отрасли и т.д.;
- системы управления технологического типа (объект управления – технологический процесс);
- системы технического управления (объект управления – техническое устройство, изделие).
Любая система управления характеризуется структурой и поведением (функционированием). Структура системы – это совокупность элементов системы и связей между ними.
Различают несколько типов структур: организационная, функциональная, техническая и т.д. Структура – это статическая модель системы. Для исследования структур используются, в основном, элементы теории графов. Поведение системы, как правило, реализуется во времени, поэтому ее исследование осуществляется чаще всего путем решения систем дифференциальных уравнений (при непрерывном времени) или уравнений в конечных разностях (если время дискретно).
Наиболее перспективными являются, так называемые, замкнутые системы, структура которых изображена на рис.1.
управления, стру
| Обратный канал связи |
| Цели управления |
| Прямой канал связи |
| Внешняя среда |
| Орган управления |
| Объект управления |
| Задачи управления |
Рисунок 1 – Обобщенная структура системы управления замкнутого типа
|
|
Таким образом, структура системы управления всегда включает: орган управления, объект управления и связи между ними: прямую связь, предназначенную для передачи от органа управления нам объект управления управляющих воздействий и обратную связь – связь, по которой передается осведомляющая информация (информация о текущем состоянии объекта управления).
Управляющее воздействие формируется на основе информации о состоянии объекта управления в текущий или предшествующий момент времени с учетом задач управления, целей управления, влияния внешней среды и возможностей самого объекта управления.
Основу процесса управления составляет формирование и принятие решения. В свою очередь, формирование и принятие решения тоже является не одномоментным, а представляет собой многоэтапный процесс. Схематично модель такого процесса изображена на рис. 2.
Исследование таких моделей осуществляется в основном на основе теории графов.
Основные понятия теории графов
Начало теории графов положено швейцарским математиком Леонардом Эйлером, долгое время жившим и работавшим в России. Его первая работа о графах появилась в 1736 г. в публикациях Петербургской Академии наук.
Предпосылкой работы о графах явилась «задача о кенигсбергских мостах». Кенигсберг (ныне Калининград) расположен на обоих берегах реки Преголя и двух островах Вислинского залива Балтийского моря. Различные части города в те времена были соединены семью мостами. Рассмотренная Эйлером задача формулировалась таким образом: «Можно ли совершая прогулку, обойти все мосты, пройдя в точности один раз по каждому мосту?» С помощью предложенной им теории Эйлер доказал, что в данном случае это невозможно.
|
|
Предметом первых задач в теории графов были конфигурации, состоящие из точек и соединяющих их линий (прямых или криволинейных непрерывных дуг любой длины). В дальнейшем теория графов нашла свое применение при исследованиях структур систем управления, электрических
сетей (в том числе компьютерных), моделей кристаллов, структур молекул и при решении многих других фундаментальных и прикладных задач.
К их числу относятся: транспортные задачи, возникающие в рамках единой логистической цепи при доставке товаров от производителя к потребителю в кратчайшие сроки, с наименьшими затратами и потерями; составление расписаний и графиков работы; управление запасами; задачи о потоках в сетях и многие другие социально-экономические задачи.
Особое место теория графов занимает при исследовании (анализе и синтезе) структур систем управления предприятиями (экономическими системами).
Основным понятием теории графов является граф, представляющий собой совокупность двух множеств: множества элементов и множества соотвeтcтвий между ними. В тоже время граф - это геометрическая схема различной конфигурации.
При исследовании систем управления организациями используются конечные графы - объекты, состоящие из двух множеств:
- вершин (множество V), которые обозначаются а1, а2, аз,... аn, где n -конечное число вершин графа. Вершины графа отображают элементы системы. Они обозначаются прямоугольниками, окружностями, точками и другими фигурами подобного типа;
- ребер (дуг) (множество Е), соединяющих соответствующие вершины и обозначающихся (аi, аj). Дуги (ребра) отображают связи между элементами системы. Если ребра ориентированы, то они называются дугами, а граф - ориентированным или орграфом. Таким образом, граф – это пара
G = (V,E).
Путь в графе - это последовательность обхода вершин вдоль дуг. Он обозначается как (а1, а2, а3,... ak), где k <= n.
Цикл - это путь, в котором начальные и конечные вершины совпадают, образуя замкнутый контур.
На рисунке 1.3 путь (а1, а2, а3, а1) является циклом, также как и путь (а1, а4, а3, a1).
Наибольшее применение при исследованиях систем управления организациями находят графы типа «дерево». Деревом называется граф, не содержащий циклов. Например, деревом является граф, изображенный на рисунке 1.4. В виде графов подобного типа отображается обычно организационная структура системы управления (например, предприятием).
Две вершины, определяющие дугу (ребро), называются смежными, как и две дуги, если они имеют общую вершину. Пример графа приведен на рис.3.
Заметим, что граф, который можно начертить таким образом, чтобы его дуги (ребра) пересекались только в вершинах, называется плоским графом. Если это условие не выполняется, то граф называется пространственным.
| Рисунок 2 - Структура процесса выработки и принятия решения |
| Окончание времени действия предыдущего решения |
| Указание вышестоящей организации |
| Изменение состояния объекта управления |
| Изменение состояния внешней среды |
| Осознание наличия реальной проблемной ситуации |
| Разработка (выбор) целей, критериев, показателей оценки альтернатив |
| Анализ влияния внешней среды |
| Анализ наличия и достаточности ресурсов (ограничений) |
| Генерирование альтернатив (вариантов) решений |
| Объективная оценка альтернатив |
| Выбор оптимальной альтернативы (принятие решения) |
| Оформление решения |
| Доведение решения (управляющего воздействия) до исполнителей (объекта управления) |
| Целенаправленное изменение состояния объекта управления |
| Аппарат ЛПР |
| Контроль выполнения решения Оценка эффективности реализации решения |
| Корректировка решения (при необходимости) |
  |
В нашей дисциплине мы рассматриваем только ориентированные или направленные графы, в которых дуги обозначаются стрелками. В дальнейшем, кроме приведенных выше определений из теории графов, нам понадобится и ряд других понятий, В том числе путь и цикл.
| а1 |
| а4 |
| а3 |
| а2 |
Рисунок 3- Ориентированный граф
При работе с «деревьями» принято разделять вершины дерева по уровням. На рис. 4 вершина верхнего уровня обозначена через А, это так называемая корневая вершина или корень дерева; В1, В2, ВЗ - вершины второго уровня; С1, С2,..., Cn - вершины третьего уровня и т.д.
Вес дуги - это вектор из «m» чисел, поставленный в соответствие дуге. Вес пути - вектор из «m» чисел, в котором координата с номером «i», где 1<= i <= m, определяется как сумма координат с номером «i» всех дуг, входящих в путь.
Графы типа «дерево» используются, в частности, при сравнительной оценке эффективности альтернативных вариантов решения поставленной задачи.
| А |
| В1 |
| В2 |
| В3 |
| С1 |
| С2 |
| С3 |
| Сn |
Рисунок 4- Граф типа «дерево»