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

Филиал федерального государственного бюджетного образовательного учреждения

высшего профессионального образования

«Кемеровский государственный университет»

в г. Анжеро-Судженске

«1» марта 2013 г.

РАБОЧАЯ ПРОГРАММА

по дисциплине «Исследование операций» (ФТД.2) для специальности 080801.65 «Прикладная информатика в экономике»

факультет информатики, экономики и математики курс: 3 семестр: 5 зачет: 5 семестр лекции: 36 часов самостоятельная работа: 30 часов всего часов: 66 Составитель: д-р. физ.-мат. наук, профессор кафедры математики Якупов Р. Т.

Анжеро-Судженск Рабочая программа составлена на основании:

«ГОСУДАРСТВЕННОГО ОБРАЗОВАТЕЛЬНОГО СТАНДАРТА

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ» (2000г.) Рабочая программа обсуждена На заседании кафедры информатики Протокол №6 «31» января 2013г.

Зав. кафедрой_ Якупов Р.Т.

(Ф.И.О., подпись) Одобрено методической комиссией Протокол №8 «26» февраля 2013г.

Председатель Якупов Р.Т.

(Ф.И.О., подпись) 1. Пояснительная записка Актуальность и значимость учебной дисциплины. Под исследованием операций (ИО) понимаются системные исследования, ориентированные на количественные описания. ИО – это математическая дисциплина, охватывающая исследование моделей для выбора величин, оптимизирующих заданную конструкцию.

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

Рабочая программа разработана в соответствии с Государственным образовательным стандартом высшего профессионального образования по специальности 080801 «Прикладная информатика (по областям)».

Цель учебной дисциплины – познакомить студентов с основными методами и моделями исследования операций.

Задачи учебной дисциплины – обучить студентов понятиям и методам теории игр и исследования операций; научить их строить и решать математические модели различных задач принятия решений, интерпретировать результаты; подготовить к самостоятельному изучению тех разделов исследования операций, которые могут потребоваться дополнительно в практической и исследовательской работе специалистовматематиков.

Место дисциплины в профессиональной подготовке специалиста.

Курс «ИО» требует наличие знаний по математическому анализу, линейной алгебре, дискретной математике теории вероятностей и математической статистике Структура учебной дисциплины. Курс «ИО» состоит из нескольких частей.

Первая часть носит вводный характер. В ней приводятся сведения из истории развития ИО, дано сжатое изложение основных разделов, основ и методов ИО, рассмотрены различные классификации моделей ИО, методика проведения операционных исследований и принятия решений.

Во второй части изучаются специальные модели ИО – модели сетевого планирования и управления. Задачи этого раздела состоят в нахождении минимальной продолжительности комплекса операций, оптимального соотношения величин стоимости и сроков их выполнения.

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

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

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

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

Формы организации учебного процесса по данной дисциплине. В учебном процессе используются аудиторные занятия (лекционные, лабораторные) и предусмотрена самостоятельная работа студентов (чтение специальной литературы, решение задач, освоение специализированных компьютерных программ).

Взаимосвязь аудиторной и самостоятельной работы студентов. На аудиторных занятиях даются основные понятия, постановки задач и формулы, решаются задачи. Некоторые вопросы, более широко раскрывающие материал, выносятся на самостоятельное изучение.

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

Студенты должны уметь: строить математическую модель задачи, подбирать метод ее решения, находить оптимальное решение и делать содержательную интерпретацию.

Студенты должны владеть: терминологией исследования операций и соответствующим математическим аппаратом.

Объем и сроки изучения дисциплины. Курс «Исследование операций»

читается как факультативная дисциплина для студентов 3 курса дневного отделения факультета информатики, экономики и математики специальности 080801 «Прикладная информатика (по областям)». Как лекции, так и лабораторные занятия проводятся в 5 семестре в объеме 18 часов. По каждой теме запланированы вопросы для самостоятельного изучения, общий объем самостоятельной работы 30 часов.

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

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

планирование программ сетевыми методами Глава 1. Общие вопросы ИО 1.1*. Становление ИО как научной дисциплины. (История возникновения ИО. Место и время зарождения. Первые публикации по ИО. Этапы развития ИО до наших дней).

1.2. Определение ИО. Предмет ИО. (Определение исследования операций. Область применения).

1.3*. ИО как наука и искусство. (Обосновывается научность ИО, подчеркивается творческий характер работы специалиста по ИО).

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

1.5. Структурные характеристики задач ИО. (Управляемые, неуправляемые переменные. Ограничения, целевая функция.

Параметры).

1.6. Классификация моделей ИО. (Математические, имитационные, эвристические. Детерминированные, стохастические. Статические, динамические).

1.7. Методика проведения операционных исследований и принятия решений. (Определение целей; составление плана разработки проекта; формулировка проблемы (определение размерности задачи, определение управляемых переменных, определение неуправляемых переменных, определение технологических параметров системы, определение показателей эффективности); построение модели (соотношения вытекающие из определений, эмпирические соотношения, нормативные соотношения); разработка вычислительного метода; разработка технического задания на программирование; программирование и отладка программы; сбор данных; проверка модели (непротиворечивость, чувствительность, реалистичность, работоспособность); реализация результата).

1.8*. Основные области применения ИО. (Перечень областей, где применимы модели ИО: военная область, техника, экономика и т.д.).

Глава 2. Календарное планирование программ сетевыми методами 2.1. Характеристики и этапы метода сетевого планирования и управления программами (СПУ). (Определение программы, операции. Метод критического пути, метод оценки и пересмотра Звездочкой помечены вопросы, выносимые на самостоятельную работу.

программ. Этапы сетевого планирования и управления).

2.2. Сетевое представление программы. Правила построения сетевой модели. (Понятие события. Сетевая модель. 3 правила построения 2.3. Определение критического пути. (Определение критической и некритической операции. 2 этапа для расчета критического пути (прямой и обратный). Определение раннего срока и позднего срока наступления события. 3 условия, которым должна удовлетворять критическая операция).

2.4. Определение резервов времени. (Срок позднего начала и раннего окончания операции. Полный и свободный резервы операции).

2.5*. Роль полных и свободных резервов времени при выборе календарных сроков некритических операций. (Соотношение между полным и свободным резервами времени некритического пути. Сдвиг некритической операции в зависимости от резервов времени).

2.6. Построение календарного графика распределения ресурсов.

(Правило построения календарных планов. Левый календарный план.

Правый календарный план. Оптимальный план).

2.8*. Управление процессом реализации программы. (Корректировка программы и ее частота в зависимости от времени реализации Глава 3. Теория игр 3.1. Определение и классификация игр. (Определение ТИ, конфликта, игрока, стратегии, функции выигрыша, игры. Процесс разыгрывания игры. Классификация игр по времени, множеству игроков, интересам, стратегиям, функциям выигрыша. Основные вопросы ТИ: выбор принципа оптимальности, его реализуемость, нахождение оптимальной стратегии).

3.2. Описание матричных игр (МИ). (Определение матричной игры.

Процесс разыгрывания. Модели матричной игры).

3.3. Принцип минимакса. (Определение нижней и верхней цен игры, максимальной и минимальной стратегии игроков. Определение седловой точки, оптимальных стратегий. Принцип минимакса).

3.4. Смешанное расширение игры. (Определение смешанной стратегии, ожидаемого выигрыша, верхней и нижней цен игры в смешанных стратегиях, смешанного расширения игры, седловой точки, оптимальной смешанной стратегии. Принцип минимакса в смешанных стратегиях. Основная теорема матричных игр).

3.5*. Свойства решений МИ. (Понятие спектра смешанной стратегии, подигры игры. Принцип доминирования в смешанных стратегиях. теорем, постулирующих свойства решения матричной игры).

3.6. Вычисление оптимальных стратегий в МИ (прямое). (Нахождение решения в чистых стратегиях, использование доминирования для уменьшения размерности игры).

3.7. Решение игры «22». (Вывод формул для нахождения оптимальных стратегий и цены игры).

3.8. Решение игр «2n» и «m2». (Вывод формул для нахождения оптимальных стратегий и цены игры).

3.9. Решение игр «mn» (m,n > 2). (Сведение игры к паре двойственных задач линейного программирования, определение оптимальных стратегий и цены игры).

3.10*. Моделирование реального конфликта МИ. (Перечень условий, которым должен удовлетворять реальный конфликт, чтобы его можно было моделировать матричной игрой).

3.11. Природа и структура бескоалиционных игр (БИ). (Определение бескоалиционной игры. Модель БИ. Разыгрывание БИ.

Классификация).

3.12. Смешанное расширение БИ. (Определение смешанных стратегий, ожидаемого выигрыша, смешанного расширения игры).

3.13. Ситуации равновесия в БИ. (Определение ситуации равновесия по Нэшу в чистых и смешанных стратегиях. Теорема о существовании решений в смешанных стратегиях. Способ нахождения точек равновесия).

3.14*. Биматричные игры. (Определение. Математическая модель.

Метод нахождения оптимальных стратегий и цены игры).

3.15*. Моделирование реального конфликта БИ. (Условия, которым должен удовлетворять реальный конфликт, чтобы его можно было моделировать БИ).

3.16. Природа и структура кооперативных игр (КИ). (Определение КИ.

Модель КИ в нормальной форме. Определение коалиции. Список вопросов, включаемых в переговоры об объединении в коалицию.

Образование максимальной коалиции. Виды выигрышей:

трансфербельные, нетрансферабельные. Определение характеристической функции (х.ф.). Свойства х.ф. Математическая модель КИ в форме х.ф.).

3.17. Дележи. Доминирование дележей. (Определение дележа, существенной и несущественной игры. Доминирование дележей.

Доминирование дележей по коалиции).

3.18. Понятие решения КИ. (Перечисление принципов оптимальности в 3.19. С-ядро. (Определение с-ядра. Теоремы и леммы о существовании сядра).

3.20*. Н-М-решение. (Определение Н-М-решения. Связь между Н-Мрешением и с-ядром. Теоремы о существовании Н-М-решения.

Недостатки Н-М-решения).

3.21*. n-ядро. (Определение эксцесса, отношения предпочтения по эксцессу, n-ядра. Теорема о существовании и единственности n-ядра.

Определение n-ядра в результате последовательного решения задач линейного программирования. Связь с с-ядром).

3.22. Вектор Шепли. (Определение вектора Шепли. Аксиомы справедливости. Теорема существования и единственности вектора Шепли. Вычислительная формула. Связь с с-ядром).

3.23*. Арбитражная схема. (Понятие точки status quo, арбитражной схемы. Аксиомы справедливости. Теорема о существовании и единственности решения арбитражной схемы. Вычислительная 3.24*. Моделирование реального конфликта КИ. (Условия, при которых реальный конфликт моделируется КИ. Выбор конкретного принципа оптимальности решения для реального конфликта, моделируемого Глава 4. Теория массового обслуживания 4.1. Основные компоненты моделей массового обслуживания. (Понятие заявки на обслуживание, механизма обслуживания. Факторы, влияющие на функциональные возможности модели МО).

4.2. Пуассоновское и экспоненциальное распределения вероятностей.

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

4.3. Входной и выходной потоки. (Процесс чистого рождения. Вывод 4.4. Общая характеристика систем массового обслуживания при наличии входного и выходного потоков. (Предположения. Унифицированные обозначения a | b | c : d | e | f. Пример. Критерий эффективности функционирования систем МО. Операционные характеристики систем МО и их взаимосвязь).

Глава 5. Имитационное моделирование 5.1. Имитационное моделирование систем как статистический эксперимент. (Предмет ИМ. Определение имитационной модели.

Классификация имитационных моделей. Механика дискретной имитации на примере СМО. Модель дискретных событий. Модель 5.2. Генерирование выборочных значений с заданным распределением.

(Метод обратных функций. Метод сверток. Метод отбора).

5.3*. Методы сбора информации в процессе имитационного моделирования. (Характеристика методов сбора статистических данных по результатам имитационного эксперимента. Метод подынтервалов, метод повторений. Метод циклов).

4. Учебно-методическое обеспечение по дисциплине 1. Горлач Б. А. Исследование операций: Учебное пособие. - СПб.:

Издательство «Лань», 2013. - 448 с.: ил. - (Учебники для вузов. Специальная http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id= 2. Есипов Б. А. Методы исследования операций: Учебное пособие. - СПб.:

Издательство «Лань», 2010. - 256 с.: ил. - (Учебники для вузов. Специальная http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id= 1. Струченков В.И. Методы оптимизации: Основы теории, задачи, обучающие компьтерные программы : учеб. пособие. - М.: Экзамен, 2005. с.

2. Вентцель Е.С. Исследование операций: задачи, принципы, методология : учеб. пособие. - 3-е изд., стереотип. - М.: Дрофа, 2004. - 208 с.

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

Кузбассвузиздат, 2005. - 107 с.

4. Данилов Н.Н. Теоретико - игровое моделирование конфликтных ситуаций : учеб. пособие. - Томск: Изд-во Томского ун-та, 2005. - 120 с.

5. Афанасьев М.Ю. Прикладные задачи исследования операций : учеб.

пособие / М.Ю. Афанасьев, К.А. Багриновский, В.М. Матюшок. - М.:

ИНФРА - М, 2006. - 352 с.

5. Формы текущего, промежуточного и рубежного контроля Семестровые задания Каждое семестровое задание сводится к решению практической задачи из раздела «Теория игр» и включает в себя:

Изучение алгоритма решения Решение прикладной задачи Темы семестровых заданий:

I. Бесконечные антагонистические игры Примеры приложений в экономике 1. Антагонистическая конференция двух фирм (непрерывный случай) 2. Захват рынков сбыта 3. Планирование посева в условиях конкурентной экономики 4. Распределение средств Примеры приложений в военном деле 5. Теоретико-игровая модель постановки и траления мин (непрерывный вариант) 6. Теоретико-игровая модель поиска на рубеже и его прорыва (случай одного наблюдения) 7. Теоретико-игровая модель поиска на рубеже и его прорыва (при k 8. Теоретико-игровая модель наступательного боя 9. Теоретико-игровая модель восстановления контакта с уклоняющейся подводной лодкой Примеры приложений в технике 10.Расчет оптимальных сечений балки в условиях отсутствия информации о свойствах материала 11.Расчет оптимальных сечений балки при наличии информации о свойствах материала Примеры приложений в социологии 12.Оценка параметров мультиномиального распределения II. Конечные позиционные игры Пример приложения в экономике 13.Планирование цикла посева Пример приложений в военном деле 14.Теоретико-игровая модель боевых действий с различной информацией о функции выигрыша у игроков 15.Теоретико-игровая модель динамики морского боя Пример приложения в спорте 16.Теоретико-игровая модель доигровки в волейболе III. Детерминированные, стохастические и рекурсивные игры Примеры приложений в военном деле 17.Теоретико-игровое обоснование оптимального расхода ресурсов 18.Теоретико-игровое обоснование оптимальной организации поисковых действий на рубеже и оптимального времени его 19.Радиоэлектронное противодействие поиску 20.Теоретико-игровая модель динамики морского боя Примеры приложений в спорте 21.Теоретико-игровая модель динамики волейбола IV. Неатомические бескоалиционные игры Пример приложений в экономике 22.Теоретико-игровая модель прогноза пассажиропотоков в городской Примерные задания для контрольных работ 1. По теме «Календарное планирование программ сетевыми методами».

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

2. По теме «Теория игр».

Решить матричную игру.

3. По темам «Теория массового обслуживания» и «Имитационное моделирование».

Очередь в закусочную вмещает не более 10 человек, остальные клиенты вынуждены ждать неподалеку. Поступление клиентов пуассоновское со средней частотой 18 чел./ч. Среднее время обслуживания одного клиента мин. Какова вероятность того, что прибывший клиент встанет в очередь в специально отведенном для ожидания месте?

Описать логику функционирования имитационной модели.

1. Становление ИО как научной дисциплины.

2. Определение ИО. Предмет ИО.

3. Основные разделы ИО.

4. Структурные характеристики задач ИО.

5. Классификация моделей ИО.

6. Методика проведения операционных исследований и принятия решения.

7. Характеристики и этапы метода сетевого планирования и управления программами (СПУ).

8. Сетевое представление программы. Правила построения сетевой 9. Определение критического пути.

10.Определение резервов времени.

11.Роль полных и свободных резервов времени при выборе календарных сроков некритических операций.

12.Построение календарного графика распределения ресурсов.

13.Управление процессом реализации программы.

14.Определение и классификация игр.

15.Описание матричных игр (МИ).

16.Принцип минимакса.

17.Смешанное расширение игры.

18.Свойства решений МИ.

19.Вычисление оптимальных стратегий в МИ (прямое).

20.Решение игры «22».

21.Решение игр «2n» и «m2».

22.Решение игр «mn» (m,n > 2).

23.Моделирование реального конфликта МИ.

24.Природа и структура бескоалиционных игр (БИ).

25.Смешанное расширение БИ.

26.Ситуации равновесия в БИ.

27.Биматричные игры.

28.Моделирование реального конфликта БИ.

29.Природа и структура кооперативных игр (КИ).

30.Дележи. Доминирование дележей.

31.Понятие решения КИ.

32.0-1-редуцированная форма КИ.

33.С-ядро.

34.НМ-решение.

35.n-ядро.

36.Вектор Шепли.

37.Арбитражная схема.

38.Моделирование реального конфликта КИ.

39.Основные компоненты моделей массового обслуживания.

40.Пуассоновское и экспоненциальное распределения вероятностей.

41.Входной и выходной потоки.

42.Общая характеристика систем массового обслуживания при наличии входного и выходного потоков.

43.Система массового обслуживания M | M | 1 : GD | |.

44.Система массового обслуживания M | M | 1 : GD | N |.

45.Система массового обслуживания M | G | 1 : M | G | 1. Формула Поллачека-Хинчина.

46.Система массового обслуживания M | M | c : GD | |.

47.Система массового обслуживания M | M | c : GD | |, с < N.

48.Система массового обслуживания M | M | : GD | |. Модель самообслуживания.

49.Система массового обслуживания M | M | R : GD | K | K, R < K. Модель обслуживания машинного парка.

50.Имитационное моделирование систем как статистический эксперимент.

51.Типы имитационных моделей.

52.Моделирование дискретной случайной величины.

53.Метод обратных функций.

54.Метод сверток.

55.Метод отказов.

56.Моделирование дискретной двумерной случайной величины.

57.Моделирование непрерывной двумерной случайной величины.

58.Метод подынтервалов.

59.Метод повторения.

60.Метод циклов.

Изменения и дополнения, вносимые в рабочую программу по итогам ее ежегодного рассмотрения на кафедре и переутверждения в установленном порядке, указываются в специальном Приложении 2, составленном согласно форме:

Дополнения и изменения к рабочей программе учебной дисциплины Сведения о переутверждении РП на текущий учебный год и № Учебный Содержание Преподаватель- Рабочая программа Внесенные