Раздел 1. МАТЕМАТИЧЕСКИЕ МОДЕЛИ Лекция 3. Типовые математические модели. - презентация

1 Раздел 1. МАТЕМАТИЧЕСКИЕ МОДЕЛИ Лекция 3. Типовые математические модели

2 Примеры моделей Оптимизационные модели Математическая оптимизационная модель должна содержать следующие основные компоненты: Переменные – значения, которых необходимо вычислить. Целевая функция – цель, записанная математически в виде функции от переменных. Обязательно указывается, что необходимо сделать с этой функцией для решения проблемы: найти ее максимум или минимум. Ограничения – записанные, математически ограничения, выявленные из анализа предметной ситуации.

3 Примеры моделей Оптимизационные модели Задача распределения ресурсов На предприятии, выпускающем неоднородную продукцию, руководители хотят определить уровни производства этой продукции на некоторый период времени. Исходные данные: количество материалов (X, Y, Z), требуемых на каждом этапе технологического процесса для выпуска единицы продукции; объем запасов этих материалов на складе; доход, получаемый в результате выпуска единицы продукции. Цель планирования – увеличение прибыли.

4 Примеры моделей Оптимизационные модели Задача распределения ресурсов Этапы технологического процесса ресурсы 1234 Требуемые ресурсы (кг, бочки, литры, ящики т.п.). количество материала X 111,5230 количество материала Y количество материала Z Доход с единицы продукции Объем выпуска продукции x1x1 x2x2 x3x3 x4x4 целевая функция (критерий): 4x 1 +5x 2 +9x 3 +11x 4 max. ограничения: x 1 + x 2 + 1,5x 3 + 2x 4 30, 2x 1 + 5x 2 + 3x 3 + 7x 4 120, 3x 1 + 5x x 3 +15x 4 100, x 1 0, x 2 0, x 3 0, x 4 0.

5 Описательные (дескриптивные) модели Основная задача: описание процесса с помощью математического аппарата в целях изучения поведения систем и прогнозирования их дальнейшего развития. Виды моделей: Регрессионные модели Модели кластеризации Модели ассоциации Области применения: в практике маркетинговых исследований интеллектуальный анализ данных отражение содержания и основных свойств экономических объектов

6 Основные подходы к моделированию Использование законов природы Пример 1. Всплытие подводной лодки (используются законы Архимеда и Ньютона) Пример 2. Полет ракеты (используется закон сохранения количества движения (импульса)).

7 Основные подходы к моделированию Принцип аналогии Применение аналогий основано на свойстве моделей: универсальности, т.е. применимости к объектам принципиально различной природы. Системы можно представить как совокупность простых элементов типа: резистора, оказывающего сопротивление переносу субстанции, конденсатора, обладающего свойством инерционности, что проявляется в стремлении сохранить поток субстанции неизменным.

8 Основные подходы к моделированию Использование типовых моделей В качестве детерминированных моделей: дифференциальные и интегральные уравнения конечные автоматы сетевые модели В качестве стохастических моделей: вероятностные автоматы системы массового обслуживания игровые модели

9 Иерархический подход к получению моделей Процесс построения моделей Словесное описание объекта или явления, т.е. сформировываются предметная модель и цели исследования модели Выбирается или формулируется закон, которому подчиняется объект. Модель записывается в математической форме. Завершается построение модели. Проводится селекция факторов, при которой отбрасываются несущественные и малозначимые факторы. Построенная модель исследуется и делается вывод о ее адекватности, т.е. соответствии объекту и целям исследования.

10 Конечные автоматы Автомат можно рассматривать как некоторое устройство (черный ящик), на которое подаются входные сигналы, снимаются выходные и которое может иметь некоторые внутренние состояния. Состояние – это то, на что влияет управление, и что вместе с управлением определяет результат (выход). Конечным автоматом называется автомат, у которого множество внутренних состояний, входных и выходных сигналов являются конечными множествами. Работа конечного автомата описывается двумя функциями: - функция переходов - функция выхода x – переменная состояния; u – переменная управления; y – переменная выхода; t – момент времени ( t = 0,1,2,3…).

11 Конечные автоматы Задание автомата в виде таблицы и графа При изображении функций в виде графа: состояния приписывают вершинам, управления – дугам. Пример 1. Пусть множество управлений u состоит из управлений α, β, γ, множество состояний x – состояний 1,2,3,4, т.е. u α, β,, x 1,2,3,4, y 0,1. Функции φ (переходов) и (выхода) заданы таблицей переходов:и в виде направленного графа: x(t) u(t) αβ 12/ 0 3/ 1 4/ 0 22/ 1 -3/ 0 3 4/ / 1 1/ 0 2/ 1

12 Конечные автоматы Задание автомата в виде таблицы и графа Пример 2. Рассмотрим автомат, который выдает билет при опускании в него монет в сумме 3 руб., причем он принимает монеты 50 коп., 1 рубль и 2 рубля. Автомат может давать сдачу. Требуется составить функцию перехода и выхода. u α=0,5, β=1, =2, x 1,2,3,4,5,6, y 1 0,1., y 2 0, 0.5, 1, 1.5 Функция переходов Функция выхода

13 Конечные автоматы Матричное задание автомата Матрица переходов – квадратная матрица, размерность которой совпадает с числом состояний, а элементами являются дуги, соединяющие состояния

14 Минимизация конечных автоматов Минимизация автоматов – сокращение числа состояний путем объединения эквивалентных состояний. Состояния называются эквивалентными, если поведение автомата одинаково независимо от того, какое из них является исходным. Состояние называется k эквивалентным, если автомат, находясь в любом из них, имеет одинаковое поведение в течение k тактов. k эквивалентные состояния образуют k- эквивалентные классы.

15 Определение эквивалентных состояний автомата Автомат представлен в виде графа. Требуется определить, есть ли у автомата эквивалентные состояния. x U β 11/02/1 2 1/0 3 2/1 U Классыx β I II22 1 x u αβ 1,31/ 0 2/ 1 2 1/ 0

16 Аналитическое задание конечных автоматов Достоинства аналитического представления конечных автоматов: компактность записи по сравнению с табличным, графовым или матричным заданиями; простота моделирования работы конечных автоматов на ЭВМ; аналитическое представление необходимо при синтезе структуры автомата, так как при таком задании функции функциональных преобразователей выражаются через элементарные функции, реализуемыми простыми элементами. Для формального описания цифровых управляющих устройств применяется аппарат алгебры логики.

17 Основная функционально полная система Включает операции &, и инверсию Хаггарти Р. Дискретная математика для программистов. М.: Техностфера, 2012 – 400 с. xyx & y x y инв xинв y

18 Нормальные формы Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция конечного числа различных членов, каждый из которых представляет собой конъюнкцию отдельных переменных или их отрицаний, входящих в данный набор не более одного раза Конъюнктивной нормальной формой (КНФ) называется конъюнкция конечного числа различных членов, каждый из которых представляет собой дизъюнкцию отдельных переменных или их отрицаний, входящих в данный набор не более одного раза СДНФ – СКНФ –

19 Разложение функций на конституенты Конституентой единицы называют конъюнкцию, содержащую все переменные или их инверсии, которая обращается в единицу только при одном выборочном наборе переменных. Конституентой нуля называют дизъюнкцию, содержащую все переменные или их инверсии, которая обращается в нуль только при одном выборочном наборе переменных.

20 Переход от табличного задания функции к аналитическому Табличное представление функции Функция в виде СДНФ: Функция в виде СКНФ: abcf

21 Вероятностные автоматы Вероятностные (стохастические) автоматы представляют собой конечные автоматы со случайными управлениями, у которых, как правило, учитываются только состояния. Пример: модель системы, которая случайным образом может оказаться в одном из технических состояний: исправное, неисправное, поиск неисправности, ремонт и т.д.

22 Марковские цепи с дискретным временем Марковским называется случайный процесс, состояние которого в очередной момент времени t + t зависит только от текущего состояния в момент времени t. Исходные данные для определения дискретной марковской цепи: множество состояний матрица вероятностей переходов вектор начальных вероятностей

23 Марковские цепи с дискретным временем Марковская цепь изображается в виде графа, вершины которого соответствуют состояниям цепи и дуги – переходам между состояниями Пример. Дана матрица вероятностей переходов Граф: вектор начальных вероятностей

24 Анализ марковских цепей Результат анализа марковской цепи: как при известном начальном состоянии от шага к шагу меняются вероятности состояний, в которых может находиться система, каковы установившиеся значения этих вероятностей. Для расчета вероятностей используется уравнение Колмогорова-Чепмена вероятности состояний вычисляются рекуррентно: При n определяют установившиеся (финальные) вероятности

25 Анализ марковских цепей. Пример. Вероятностный автомат представлен в виде графа

26 Марковские процессы Главное свойство непрерывного марковского процесса – экспоненциальность распределения времени пребывания процесса в каждом из состояний. Марковский процесс с непрерывным временем переходов можно задать в виде графа или описать системой дифференциальных уравнений.

27 Расчет характеристик марковских процессов Для установившегося режима система дифференциальных уравнений преобразуется к системе линейных алгебраических уравнений, решением которой являются финальные вероятности состояний системы.

28 Модель "гибели и размножения"

29 Модели массового обслуживания Объекты заняты обслуживанием поступающих в общем случае случайных потоков заявок или требований. Поток событий – последовательность однородных событий, следующих одно за другим в какой-то случайный момент времени

30 Характеристика потока событий Характеристика потока событий – интенсивность среднее число событий, приходящееся на единицу времени. может быть постоянной ( = const), переменной, зависящей от времени t. поток автомашин, движущихся по улице, днем интенсивнее, чем ночью, в часы пик интенсивнее, чем в другие часы

31 Потоки событий Поток событий называется регулярным, если события следуют одно за другим через определенные, равные промежутки времени Поток событий называется стационарным, если его вероятностные характеристики не зависят от времени Поток событий называется потоком без последействия, если для любых двух непересекающихся интервалов времени 1 и 2 число событий, попадающих на один из них, не зависит от того, сколько событий попало на другой. Поток событий называется ординарным, если события в нем появляются поодиночке, а не группами

32 Простейший поток Поток событий называется простейшим (или стационарным пуассоновским), если он обладает сразу тремя свойствами: стационарен, ординарен, не имеет последействия. Процессы, связанные с простейшими потоками, имеют наиболее простое математическое описание. Для простейшего потока с интенсивностью интервал между соседними событиями имеет показательное (экспоненциальное) распределение

33 Системы массового обслуживания Процесс работы СМО представляет собой случайный процесс с дискретными состояниями и непрерывным временем; Состояние СМО меняется скачком в моменты появления каких-то событий

34 Теория массового обслуживания Предмет теории массового обслуживания построение математических моделей, связывающих заданные условия работы СМО число каналов, их производительность, правила работы, характер потока заявок с интересующими нас характеристиками показателями эффективности СМО, описывающими, с той или другой точки зрения, ее способность справляться с потоком заявок.

35 Классификация СМО с очередью очередь не ограничена очередь ограничена ограничение по длине очереди ограничение по времени обслуживания с отказами

36 Дисциплина обслуживания Заявки могут обслуживаться: в порядке поступления (раньше пришла, раньше обслуживается), в случайном порядке, обслуживание с приоритетом некоторые заявки обслуживаются вне очереди: приоритет может быть абсолютным когда заявка с более высоким приоритетом «вытесняет» из-под обслуживания заявку с низшим, относительным когда начатое обслуживание доводится до конца, а заявка с более высоким приоритетом имеет лишь право на лучшее место в очереди.

37 Модели временных рядов Временной ряд представляет собой последовательность чисел, которые являются значениями протекающего во времени процесса При построении модели ряд разделяют на части: детерминированную (неслучайную) случайную придает хаотичность и непредсказуемость. Для описания и анализа данного компонента используют понятия и методы теории вероятностей и математической статистики

38 Детерминированная часть Тренд изменяющийся, нециклический компонент, описывающий влияние долговременных факторов, эффект которых сказывается постепенно Сезонная составляющая описывает поведение, изменяющееся регулярно в течении заданного периода (года, месяца, недели, дня и т.п.). Состоит из почти повторяющихся циклов Циклическая составляющая описывает длительные периоды относительного подъема и спада и состоит из циклов, меняющихся по амплитуде и протяженности

39 Выделение тренда Метод скользящего среднего переход от начальных значений ряда к их средним значениям на заранее известном интервале времени, который скользит вдоль ряда Метод экспоненциального сглаживания наблюдениям приписывают различные веса Метод аналитического выравнивания