Программа дисциплины " Системный анализ и моделирование" Направление

Вид материалаПрограмма дисциплины

Содержание


Описание дисциплины 3
Условия и критерии выставления оценок 4
Темы лекций 7
Описание дисциплины
Темы лекций и семинарских занятий
Подобный материал:

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ


Государственное образовательное учреждение высшего профессионального образования

Российский Университет дружбы народов


(РУДН)


ПРОГРАММА

Дисциплины " Системный анализ и моделирование"

Направление " Автоматизация и управление"


Инженерный факультет

Кафедра "Кибернетики и мехатроники"


Составитель программы д.т.н., проф. Воронов Е.М.

"ОДОБРЕНО":

Зав. кафедрой д.т.н., проф. Пупков К.А.

«Кибернетики и мехатроники»


Москва 2010 г.


содержание
^

ОПИСАНИЕ ДИСЦИПЛИНЫ 3


Цель дисциплины 3

Содержание дисциплины 3

Организационно-методическое построение дисциплины 4

Обязательная литература 4

Дополнительная литература 4

^ УСЛОВИЯ И КРИТЕРИИ ВЫСТАВЛЕНИЯ ОЦЕНОК 4

Балльная структура оценки 5

Шкала оценок 5

Правила выполнения письменных работ 6

Академическая этика 6

^ ТЕМЫ ЛЕКЦИЙ 7

Неделя I 7

Неделя II 7

Неделя III 7

Неделя IV 7

Неделя V 8

Неделя VI 8

Неделя VII 8

Неделя VIII 9

Неделя IX 9

Неделя X 9

Неделя XI 9

Неделя XII 10

Неделя XIII 10

Неделя XIV 11

Неделя XV 11

Неделя XVI 11

Неделя XVII 12

Неделя XVIII 12

^

Описание дисциплины



Цель дисциплины. Целью дисциплины является ознакомление студентов с теорией, задачами и методами исследования операций (МИСО) и принятия решений (ПР). Знания в области МИСО и ПР дополняют ранее полученные при изучении основ теории управления и, особенно, методов регулирования, оптимизации управления объектом и многообъектной многокритериальной системой (ММС). При изучении МИСО и ПР имеют место два направления расширения знаний и навыков по теории управления. Во-первых, формализованные подходы и постановки в задачах управления и регулирования на основе вариационных методов нелинейного программирования дополняются слабоформализованными в целом методами ПР, причем МИСО формирует предварительное количественное обоснование решений на основе прямых методов нелинейного программирования и математического моделирования. Во-вторых, дисциплина МИСО и ПР расширяет структурное представление управляемых сложных систем и знакомит с типичной иерархической структурой с уровнями – ММС регулирования, управления и верхним уровнем – принятие решения. В этой связи, изучение дисциплины необходимо для понимания проблем исследования структурно-сложных систем и для введения в последующую дисциплину по методам системного анализа (11 семестр).

Содержание дисциплины. Дисциплина содержит вводную и две основные части –методы математического моделирования операций и методы оптимизации операций и принятия решений. Во вводной части курса дается понятие операции, исследования операций и принятия решений, классифицируются цели ИСО и ПР и даются общие характеристики моделей операций как структурно-сложных систем. В первой основной части рассматриваются следующие методы математического моделирования операций: моделирование операций по схеме марковских цепей, моделирование операций на основе метода динамики средних, моделирование операций методом статистических испытаний, кратко обсуждаются методы имитационного и полунатурного моделирования и операционные (деловые) игры. Рассматривается применение методов в задачах массового обслуживания, анализа надежности и живучести систем, моделирования динамики конфликта, получения статистических характеристик операции на основе статистических испытаний и др. Во второй основной части курса рассматриваются методы оптимизации операций и принятия решений со скалярными и векторными критериями в формализованных и слабоформализованных системах и в условиях неопределенности, а также их применение в задачах распределения ресурсов и ранжирования, управления запасами, в сетевых задачах упорядочения и координации, выбора маршрута, в многоканальных системах управления (регулирования), целераспределения с прогнозом, в динамических и матричных четких и нечетких играх, в задачах получения статистических решений и др. При этом формируются задачи получения допустимого и оптимального решения на множестве альтернатив и его расширения на основе свойства сложности. Исследуются точные и приближенные методы решения задачи распределения ресурсов, размещения и назначения как задачи линейного, нелинейного и эвристического программирования. Рассматриваются методы многокритериального выбора решений и управлений в формализованных задачах на основе прямого подхода (метод конусов доминирования, генетические алгоритмы и др.), подхода со скаляризацией (метод обобщенного скалярного показателя, метод пороговой оптимизации, метод лексикографической оптимизации и др.), подхода на основе компромисса (метод «утопической» точки, метод характеристической функции, арбитражных схем и др.), а также в слабоформализованных задачах на основе функций полезности, анализа иерархий, метода ELECTRE, метода проспектов и др. Рассматривается структура условий неопределенности и методы получения решений в условиях неопределенности.

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

Организационно-методическое построение дисциплины. Дисциплина МИСО и ПР состоит из лекций, практических занятий (семинаров), курсовой работы и самостоятельной работы по изучению дополнительных тем, раздаточного материала и литературы, а также написания реферата по заданию преподавателя.

Обязательная литература:
  1. Вентцель Е.С. Исследование операций. – М.: Сов.радио, 1972
  2. Вентцель Е.С. Исследование операций. Задачи, принципы, методология. – М.: Наука, 1988
  3. Воронов Е.М. Методы исследования операций и принятия решений. Конспект на дискете. 1997 г.
  4. Воронов Е.М. Методы исследования операций. Методические указания на выполнение курсовой работы с задачами и примерами. – М.: МГТУ им. Баумана, 1983
  5. Ермольев Ю.М., Ляшко Н.Н. и др. Математические методы исследования операций. – Киев: Высшая школа, 1979
  6. Морозов В.В., Сухарев А.Г., Федоров В.В. Исследование операций в задачах и примерах. – М.: Высшая школа, 1986
  7. Плотников В.Н., Зверев В.Ю. Принятие решений в системах управления. //Методы робастного, нейронечеткого и адаптивного управления. Часть IV// Под ред. Пупкова К.А. и Егупова Н.Д. – М.: МГТУ, 2001
  8. Ларичев О.А. Теория и методы принятия решений. – М.: Логос, 2001

Дополнительная литература:
  1. Воронов Е.М. Методы оптимизации управления многообъектными многокритериальными системами на основе стабильно-эффективных компромиссов. – Под редакцией Пупкова К.А., Егупова Н.Д., М.: МГТУ, 2001
  2. Акоф Р., Сасиени М. Основы исследования операций. – М.: Мир, 1971
  3. Вагнер Г. Основы исследования операций. Т.1,2,3 – М.: Мир, 1973
  4. Майзер Х. и др. Исследование операций. Т.1,2 – М.: Мир, 1981
  5. Гермейер Ю.Б. Введение в теорию исследования операций. – М.: Наука, 1971
  6. Дегтярев Ю.Н. Исследование операций. – М.: Высшая школа, 1986
  7. Абчук В.А. и др.. Справочник по исследованию операций. – М.: Воениздат, 1979
  8. Протасов И.Д. Теория игр и исследование операций. – М.: Гелиос АРВ, 2003



^

Темы лекций и семинарских занятий



Неделя I. (каждая неделя: лекция – 4 ч, семинар – 2 ч.)

Лекция. ИСО как одна из дисциплин системного анализа. Об истории возникновения ИСО. Многокритериальность и структурная сложность задач ИСО. Военно-технические, технологические, экономические и социальные примеры задач ИСО. Понятия операции, исследования операций и принятия решений. Соотношение задач оптимизации управления (ЗОУ), исследования операций (ЗИСО) и принятия решений (ЗПР) в нелинейном программировании. ИСО как количественное обоснование решения. Понятие о классах ЗИСО и их краткая характеристика.

Семинар. Анализ примеров постановок задач ИСО.

Вопросы:
  1. Определения операции, исследования операции и принятия решения.
  2. Классы задач ИСО.
  3. Взаимосвязь ЗОУ, ЗИСО, ЗПР.

Неделя II.

Лекция. Информационные условия и постановка детерминированных, стохастических задач ИСО и в условиях неопределенности. Классификация систем по структурным свойствам. Аналитические, статистические, непрерывные и динамические модели ИСО.

Семинар. Анализ примеров моделей. Дискретная статистическая модель надежности и непрерывная статистическая экономическая модель статической дуополии. Непрерывная детерминированная динамическая модель летного комплекса.

Вопросы:
  1. Дайте классификацию систем по структурным свойствам.
  2. Охарактеризуйте три вида информационных условий в задачах ИСО.
  3. Дайте классификацию систем по структурным свойствам и моделей ИСО.

Неделя III.

Лекция. Методы математического моделирования операций и методы оптимизации операций и принятия решений – две основные части курса. Моделирование операций по схеме марковских процессов. Марковская цепь. Размеченный граф состояния. Определение вероятности состояний марковской цепи для любого шага. Марковский процесс с непрерывным временем и дискретными состояниями. Уравнение Чепмена-Колмогорова для вероятностей состояний. Понятие о полумарковских процессах. Потоки событий. Простейший поток, нестационарный пуассоновский поток. Свойства потоков.

Семинар. Решение задач по составлению моделей, анализу операций на основе марковских процессов.

Вопросы:
  1. Понятие марковской цепи, определение вероятностей состояния.
  2. Получение уравнения Чепмена-Колмогорова.
  3. Свойства простейшего потока.

Неделя IV.

Лекция. Потоки Пальма, Эрланга и их свойства. Метод псевдосостояний. Применения потока Эрланга. Предельные вероятности состояния, стационарные режимы. Две типичные схемы стационарных режимов.

Семинар. Решение задач с применением потоков Пальма, Эрланга. Анализ примеров стационарных режимов: «гибели и размножения», с обратной связью.

Вопросы:
  1. Метод псевдосостояний. Применение потока Эрланга. Свойства потоков Пальма, Эрланга.
  2. Анализ стационарных режимов. Две типичные схемы стационарных марковских процессов.

Неделя V.

Лекция. Элементы теории массового обслуживания. Классификация СМО и их показателей эффективности. Основные параметры СМО. Марковские одноканальные и многоканальные СМО с отказом. Марковская СМО с ожиданием (с ограниченной и неограниченной очередью). Формула Литтла. Марковская СМО с ограниченным ожиданием. Замкнутые СМО. СМО со связью между каналами, с учетом ошибок обслуживания.

Семинар. Решение задач по модели систем массового обслуживания на основе марковских процессов.

Вопросы:
  1. Классификация СМО. Основные параметры и показатели СМО.
  2. Марковские СМО с отказом.
  3. Марковские СМО с ожиданием. Формула Литтла.
  4. Марковские СМО с ограниченным ожиданием. Замкнутые СМО. СМО со связью между каналами и учетом ошибок обслуживания.

Неделя VI.

Лекция. Применение марковских моделей к исследованию надежности и живучести системы. Плотность распределения времени безотказной работы. Среднее время безотказной работы. Экспоненциальный закон надежности. Интенсивность отказов. Надежность нерезервированной и резервированной системы. Три вида резервирования. Надежность систем с восстановлением. Замена с целью предупреждения отказов.

Понятие живучести. Об интегро-дифференциальных моделях живучести на основе функциональной избыточности и полумарковских процессов.

Семинар. Решение задач анализа надежности систем на основе моделей марковских процессов.

Вопросы:
  1. Надежность и живучесть систем. Характеристики безотказной работы. Стохастический закон надежности. Интенсивность отказов.
  2. Три вида резервирования. Надежность с восстановлением. Замена для предупреждения отказов.
  3. Интегро-дифференциальные модели живучести на основе избыточности и полумарковских свойств процессов.

Неделя VII.

Лекция. Моделирование операций по методу динамики средних. Определение вероятности состояния элемента, средних численностей, дисперсий. Зависимость интенсивности перехода от численности состояний. Принцип квазирегулярности. Применение метода динамики средних к моделированию динамики конфликта. Уравнения Ланчестера. Понятие об операционных играх как методе моделирования операции.

Семинар. Решение задач конфликтного взаимодействия на обобщенных моделях динамики средних.

Вопросы:
  1. Модель операции по методу динамики средних.
  2. Принцип квазирегулярности. Уравнение Ланчестера динамики конфликта.
  3. Обобщенная модель конфликта (учет запаздывания информации, конечного времени взаимосвязи, упреждений и т.д.).


Неделя VIII.

Лекция. Моделирование операций методом статистических испытаний. Стохастическая терминальная задача попадания ансамбля траекторий в заданную область. Три этапа метода: формирование показателей, оценок, сведение статистических испытаний к СМР (стандартному механизму розыгрыша). Розыгрыш величин, распределенных по нормальному закону.

Семинар. Решение стохастической терминальной задачи попадания ансамбля траекторий в заданную область на основе метода статистических испытаний.

Вопросы:
  1. Структура метода статистических испытаний.
  2. Контроль точности статистических оценок.
  3. Как статистические испытания сводятся к СМР?

Неделя IX.

Лекция. Однокритериальная оптимизация операций и решений. Задача принятия допустимого и оптимального решения на декартовом произведении множества альтернатив (P×H×Y×U×G×D). Понятие расширенного множества альтернатив.

Основные этапы решения линейных задач принятия решений (ЛЗПР) в форме распределения ресурсов, размещения и назначения (выбора) на основе симплекс-метода. Решение ЛЗПР геометрическим методом (n-m ≤ 3), конструктивные свойства решений. Применение табличного алгоритма замены базисных переменных, опорное и оптимальное решение ЛЗПР. Решение задачи размещения по критерию стоимости методом «северо-западного угла», методом потенциалов.

Семинар. Решение задач распределения. Решение задач размещения.

Вопросы:
  1. Задача принятия допустимого и оптимального решения на множестве альтернатив (P×H×Y×U×G×D).
  2. Решение ЛЗПР симплекс-методом.
  3. Метод потенциалов в решении задачи размещения.
  4. Метод «северо-западного угла» в задачах размещения.

Неделя X.

Лекция. Принятие решения на основе задачи назначения (выбора). Понятие о точных методах: линейное и динамическое программирование, венгерский метод (метод Мака), метод с матрицами особого вида и др. Приближенные методы решения задачи назначения: «кратчайшего увеличивающегося пути», поэтапного выбора, метод Фогеля, «жадные» алгоритмы, метод минимального (максимального) элемента, метод приращений и др. Комбинирование методов Мака и минимального элемента. Задача выбора с аддитивным, вероятностным или минимаксным критерием.

Семинар. Решение задач назначения точными и приближенными методами.

Вопросы:
  1. Точные методы решения задачи назначения.
  2. Приближенные методы решения задачи назначений.
  3. Задачи выбора с аддитивным, вероятностным или минимаксным критерием.

Неделя XI.

Лекция. Динамическое программирование в нелинейной задаче распределения ресурсов. Основное функциональное уравнение Беллмана в дискретной форме. Этапы решения ЗРР методом динамического программирования. Обобщения: n-отраслей, резервирование и т.д. ЗРР по порядковому номеру объекта, с мультипликативным критерием и др.

Семинар. Решение нелинейных ЗРР методом динамического программирования.

Вопросы:
  1. Этапы решения нелинейной ЗРР методом динамического программирования.
  2. Обобщения нелинейной ЗРР.
  3. ЗРР по порядковому номеру объекта, с мультипликативным критерием и ее решение методом динамического программирования.

Неделя XII.

Лекция. Многокритериальная оптимизация в формализованных задачах ИСО и ПР. Формирование избыточного вектора показателей в задаче управления и операции на основе эффективности, стабильности, сложности, стоимости, робастности, интеллектуальности, других базовых требований. Принцип Заде единства целей и ограничений в многокритериальной оптимизации. Три подхода многокритериальной оптимизации: прямые методы, методы скаляризации, методы компромиссов. Определение оптимальных по Парето решений на основе конуса доминирования. Двухэтапных алгорим Парето-оптимизации на основе конуса доминирования (глобальный анализ и локальная оптимизация). Методы глобального анализа на основе случайного поиска. Понятие о генетических алгоритмах глобального анализа и генетическом программировании.

Семинар. Решение многокритериальных задач на основе конусов доминирования. Структурный анализ генетического алгоритма.

Вопросы:
  1. Определение Парето-оптимальных решений на основе конусов доминирования.
  2. Двухэтапный алгоритм Парето-оптимизации на основе конуса доминирования.
  3. Структурные свойства генетического алгоритма.

Неделя XIII.

Лекция. Некоторые способы сведения задачи к выбору кооперативных компромиссов и скалярной оптимизации. Формирование обобщенной скалярной функции. Последовательная лексикографическая оптимизация (метод уступок). Метод оптимизации с использованием желаемых уровней показателей (пороговая оптимизация, процедуры целевого программирования). Постановки двухкритериальной задачи назначения с аддитивным и минимаксным критерием на основе пороговой оптимизации. Многокритериальная задача назначения с аддитивными критериями. Метод компромиссной оптимизации на основе приближения к идеальной (утопической или биутопической) точке по Салуквадзе. Постановка двухкритериальной задачи назначения с аддитивными показателями на основе метода Салуквадзе. Многокритериальная оптимизация на основе коллективной и индивидуальной рациональности. Понятие о кооперативной игре в форме характеристической функции. Дележи по Шепли. Задача получения кооперативного компромисса с выбором Парето-решения в окрестности точки Шепли. Компромисс на основе арбитражных схем Нэша и Райфы.

Семинар. Решение двухкритериальной задачи назначения с аддитивным и минимаксным критерием методом пороговой оптимизации. Решение двухкритериальной задачи назначения с аддитивными критериями на основе утопической точки.

Вопросы:
  1. Метод последовательных уступок в многокритериальной оптимизации.
  2. Метод пороговой оптимизации в многокритериальной оптимизации.
  3. Метод скаляризации показателей в многокритериальной оптимизации.
  4. Метод утопической точки в многокритериальной оптимизации.
  5. Понятие о компромиссе на основе функции дележа по Шепли в многокритериальной оптимизации.
  6. Компромиссы на основе арбитражных схем.

Неделя XIV.

Лекция. Принятие многокритериальных решений (выбор многокритериальных альтернатив) в слабоформализованных задачах. Методы выбора и сравнения альтернатив на основе функций полезности. Основные этапы метода анализа иерархий (МАИ) Саати. Методы ELECTRE ранжирования многокритериальных альтернатив. Понятие о методе Подиновского, методе проспектов.

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

Семинар. Решение слабоформализованных задач МИСО и ПР на основе функций полезности, МАИ и методов ELECTRE.

Вопросы:
  1. Выбор многокритериальных альтернатив на основе функции полезности.
  2. Выбор многокритериальных альтернатив на основе метода анализа иерархий.
  3. Выбор многокритериальных альтернатив на основе методов ELECTRE.

Неделя XV.

Лекция. МИСО и ПР в условиях неопределенности. Классификация неопределенности по Моисееву (три вида). Подходы к исследованию систем в условиях неопределенности (теория статистических решений, «нечеткого» анализа, робастные методы, методы управления ансамблем траекторий, методы теории игр, генетический алгоритм многокритериальной оптимизации (ГАМО) Жуковского-Серова в условиях неопределенности среды на основе векторного минимакса и др.). Пять информационных ситуаций в МИСО и ПР в теории статистических решений. Планирование эксперимента в первой ситуации. Метод районирования Динера в третьей информационной ситуации. Критерии Вальда, Севиджа, Гурвица в пятой информационной ситуации. Понятие матричной игры с «природой», а также в условиях антагонистического конфликта в чистых и смешанных стратегиях.

Семинар. Решение задач планирования эксперимента, районирования Динера, матричной игры с «природой».

Вопросы:
  1. Классификация типов неопределенности по Моисееву.
  2. Методы парирования неопределенностей.
  3. Пять информационных ситуаций в теории статистических решений (ТСР).
  4. Планирование эксперимента в первой информационной ситуации ТСР.
  5. Метод районирования Динера в третьей информационной ситуации ТСР.
  6. Критерии Вальда, Севиджа, Гурвица в пятой информационной ситуации ТСР. Понятие матричной игры с «природой» в чистых стратегиях.

Неделя XVI.

Лекция. Решение матричных игр в смешанных стратегиях. Теорема фон Неймана. Следствия. Решение игры 2×n (m×2). Сведение матричной игры m× n к задаче линейного программирования. Нечеткие матричные игры по Мочалову. Постановка дифференциальной антагонистической игры. Общий анализ методов решения на основе подходов Айзекса, линейно-квадратичной и интегро-дифференциальной модели игры. Принцип максимума и метод экстремального прицеливания Красовского Н.Н. в динамической задаче ИСО – преследовании. Алгоритмический анализ динамической задачи многокритериальной оптимизации в условиях неопределенности Жуковского-Серова на основе векторного минимакса с ГАМО на этапе глобального анализа и модифицированным алгоритмом Топкиса-Вейнотта на этапе локальной оптимизации.

Семинар. Решение четких и нечетких матричных игр 2×n (m×2) в смешанных стратегиях. Анализ антагонистической динамической задачи преследования на основе принципа максимума. Пример решения задачи сближения – уклонения на основе экстремального прицеливания Красовского Н.Н.

Вопросы:
  1. Метод решения игры 2×n (m×2) в смешанных стратегиях.
  2. Этапы решения нечеткой матричной игры по Мочалову.
  3. Методы решения дифференциальных антагонистических игр.
  4. Двухэтапный метод многокритериальной оптимизации Жуковского – Серова в условиях неопределенности.

Неделя XVII.

Лекция. Сетевые задачи. Сетевая задача упорядочения и координации. Структурная таблица. Структурно-временной сетевой график. Улучшение плана операции за счет некритических путей. Общий алгоритм сетевого планирования управления (СПУ).

Сетевые задачи выбора маршрута на графах. Задача коммивояжера и ее решение методом ветвей и границ. Задача выбора кратчайшего пути в сетях. О методах решения комбинаторных задач ИСО и ПР.

Семинар. Решение задач СПУ, решение задачи коммивояжера методом ветвей и границ.

Вопросы:
  1. Понятие и этапы решения сетевой задачи упорядочения и координации. Общий алгоритм СПУ.
  2. Сетевые задачи выбора маршрута на графах. Постановка задачи коммивояжера. Этапы решения методом ветвей и границ.

Неделя XVIII.

Лекция. Задача управления запасами и сохранения ресурсов. Целевые функции и управляемые параметры задачи. Динамика запасов. Общая детерминированная задача управления запасами для однородной продукции. Задача управления запасами для неоднородной продукции с учетом ограничений.

Семинар. Анализ решения примеров задач управления запасами для однородной и неоднородной продукции.

Вопросы:
  1. Динамика запасов.
  2. Структура задачи управления запасами для однородной продукции.
  3. Структура задачи управления запасами для неоднородной продукции.