Рабочая программа дисциплины Исследование операций

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

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

Факультет компьютерных наук и информационных технологий

УТВЕРЖДАЮ

проректор по учебно-методической

работе, проф. 

______________________________

"____" _______________20___ г.

Рабочая программа дисциплины

Исследование операций

Направление подготовки

27.03.03 (220100) Системный анализ и управление

Профиль подготовки

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

Квалификация (степень) выпускника

Бакалавр

Форма обучения

очная

Саратов,

2014

1. Цели освоения дисциплины

Целями освоения дисциплины «Исследование операций» являются развитие у студентов личностных качеств, а также формирование общекультурных и профессиональных компетенций в соответствии с требованиями ФГОС ВПО и основной образовательной программы по направлению подготовки 27.03.03 – Системный анализ и управление.

2. Место дисциплины в структуре ООП бакалавриата

Дисциплина «Исследование операций» относится к вариативной части профессионального цикла ООП бакалавриата 27.03.03 – Системный анализ и управление.

Для освоения дисциплины требуются знания по дисциплинам «Высшая математика», «Дискретная математика». Знания, умения и навыки, полученные студентами при изучении курса «Исследование операций», позволят эффективно решать задачи по исследованию операций, задачи моделирования и управления стохастическими системами при выполнении выпускной квалификационной работы и в будущей профессиональной деятельности.

3. Компетенции обучающегося, формируемые в результате освоения дисциплины

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

– способность находить организационно-управленческие решения в нестандартных ситуациях и нести за них ответственность (ОК-4);

– способность применять основные положения и методы социальных, гуманитарных и экономических наук при решении социальных, профессиональных и организационных задач и анализе социально-значимых проблем и процессов (ОК-9);

– способность применять основные законы естественнонаучных дисциплин в профессиональной деятельности, применять методы математического анализа и моделирования, теоретического и экспериментального исследования (ОК-10);

– способность применять аналитические, вычислительные и системно-аналитические методы для решения прикладных задач в области управления объектами техники, технологии, организационными системами, работать с традиционными носителями информации, распределенными базами знаний (ПК-1);

– способность принимать научно-обоснованные решения на основе математики, физики, химии, информатики, экологии, методов системного анализа и теории управления, осуществлять постановку и выполнять эксперименты по проверке их корректности и эффективности (ПК-8);

– способность разрабатывать методы моделирования, анализа и технологии синтеза процессов и систем в области техники, технологии и организационных систем (ПК-12).

В результате освоения дисциплины обучающийся должен:

Знать:

– цели и основные этапы исследования операций;

– типичные распределительные задачи;

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

– методы решений вырожденных и открытых транспортных задач;

– алгоритм решения задачи о назначении;

– основные понятия и определения теории управления запасами;

– основные факторы и эффекты, влияющих на стратегию управления запасами;

– структуру затрат в задачах управления запасами;

– общую структуру системы управления запасами;

– классификацию моделей управления запасами;

– классические модели управления запасами;

– принципы построения моделей управления запасами;

– методы решения задач управления запасами;

– методы решения задач износа, ремонта и замены оборудования;

– аналитические методы решения задач упорядочения;

– формальную структуру состязательных ситуаций;

– основные аспекты теории игр;

– методы решения состязательных задач;

– типы ситуаций поиска и источников ошибок наблюдения;

– математическую постановку задач поиска;

– модели получения решения задач поиска.

– основные понятия теории расписаний;

– критерии оценки расписаний для одной машины и для конечного числа работ;

– условия оптимальности упорядочения;

– алгоритмы составления расписаний для конвейерных систем;

– алгоритм Джонсона:

– математические методы получения оптимальных расписаний;

– влияние структуры системы на временные характеристики протекающих в ней процессов;

– алгоритмы решения сетевых задач упорядочения;

– графические методы теории расписаний;

– области применения моделей динамического программирования;

– принципы построения моделей динамического программирования;

– метод поиска оптимальной стратегии при конечном плановом периоде;

– критерии оптимизации, используемые при бесконечном плановом периоде;

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

– принципы построения стохастических моделей динамического программирования;

– методы поиска оптимальных стратегий для стохастических моделей динамического программирования;

– основные понятия теории марковских процессов принятия решений с дискретным и непрерывным временем;

– методы анализа марковских процессов с дискретным и непрерывным временем;

– методы нахождения оптимальных стратегий для процессов последовательных решений с дискретным временем без переоценки и с переоценкой;

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

Уметь:

– строить математические модели для простейших задач исследования операций;

– использовать методы математического программирования для решения задач исследования операций;

– ставить задачу составления оптимального расписания реальной системы, определять соответствующую математическую модель, устанавливать соответствие между параметрами исходной системы и модели;

– составлять оптимальные расписания для сиcтемы n |1;

– составлять оптимальное расписание при заданном отношении предшествования;

– составлять оптимальные расписания для системы конвейерного типа;

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

– минимизировать суммарную длительность всех настроек;

– решать задачи идеального упорядочения;

– решать сетевые задачи упорядочения;

– проверять корректность составленного расписания;

– проводить исследование реальных систем с помощью моделей динамического программирования;

– находить оптимальные стратегии при конечном плановом периоде;

– находить оптимальные стратегии при бесконечном плановом периоде с использованием различных критериев оптимизации;

– строить стохастические модели динамического программирования для конкретных задач;

– находить оптимальные стратегии при бесконечном плановом периоде для стохастических моделей динамического программирования;

– проводить теоретическое исследование реальных систем, описываемых марковскими процессами с дискретным и непрерывным временем;

– использовать производящие функции и преобразования Лапласа для анализа марковских процессов с дискретным и непрерывным временем;

– моделировать реальные системы марковскими процессами последовательных решений;

– использовать рекуррентный и итерационный методы нахождения оптимальных стратегий для процессов последовательных решений с дискретным временем;

– использовать итерационный метод нахождения оптимальных стратегий для процессов последовательных решений с несколькими эргодическими классами состояний;

– использовать методы нахождения оптимальных стратегий для процессов последовательных решений с дискретным временем и переоценкой;

– использовать методы нахождения оптимальных стратегий для процессов последовательных решений с непрерывным временем.

Владеть:

– навыками построения математических моделей для типовых задач исследования операций;

– навыками использования математических методов исследования операций для нахождения оптимальных решений при управлении эволюцией детерминированных и стохастических систем;

– навыками составления оптимальных расписаний для систем различных типов;

– методами теории расписаний, исследования операций, теории графов при построении оптимальных расписаний;

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

– навыками работы в коллективе при составлении оптимальных расписаний для реальных систем;

– навыками использования методов динамического программирования при анализе и управлении реальными детерминированными и стохастическими системами;

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

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

4. Структура и содержание дисциплины

Общая трудоемкость дисциплины составляет 8 зачетных единиц, 288 часов.

№ п/п	Раздел дисциплины	Семестр	Неделя семестра	Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах)	Формы текущего контроля успеваемости (по неделям семестра) Формы промежуточной аттестации (по семестрам)
Лекции	Лабораторные занятия	Практические занятия	Самостоятельная работа
1	Введение в исследование операций	5	1	2
2	Распределительные задачи	5	2-4	6		8	6
3	Задачи управления запасами	5	5-8	8		8	4
4	Задачи сетевого планирования и управления	5	9-10	4		6	4
5	Задачи замены и ремонта оборудования	5	11-13	6		4	6
6	Состязательные задачи	5	14-15	4		6	6
7	Задачи поиска	5	16-18	6		4	4	Контрольная работа 1
	Итого:			36		36	30	зачет
8	Основные понятия теории расписаний	6	1	2		4	2
9	Задачи теории расписаний	6	2	2		28	18	Контрольная работа 2
10	Прикладные задачи динамического программирования	6	3	2	6		8
11	Модели с бесконечным плановым периодом	6	4, 5	4	4		8
12	Вероятностные модели динамического программирования	6	6-8	6	4		4
13	Марковские процессы с дискретным временем и доходами	6	9, 10	4	4
14	Процессы последовательных решений	6	11, 12	4	6		6
15	Процессы последовательных решений с переоценкой	6	13, 14	4	4		6
16	Процессы последовательных решений с непрерывным временем	6	15, 16	4	4		2
	Итого:			32	32	32	54	зачет, экзамен (36 часов)

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

1. ВВЕДЕНИЕ В ИССЛЕДОВАНИЕ ОПЕРАЦИЙ. 1.1. Постановка задачи исследования операций. 1.2. Цель исследования операций. 1.3. Основные этапы исследования операций. 1.4. Значение методов и моделей исследования операций в процессе подготовки и принятия управленческих решений. 1.5. Математические модели и методы в исследовании операций.

2. РАСПРЕДЕЛИТЕЛЬНЫЕ ЗАДАЧИ. 2.1. Типичная распределительная задача. Статические и динамические, сбалансированные и несбалансированные распределительные задачи. 2.2. Транспортная задача: отыскание допустимого начального и оптимального решений. 2.3. Вырожденная транспортная задача. 2.4. Несбалансированные (открытые) транспортные задачи. 2.5. Задача о назначении. 2.6. Примеры распределительных задач.

3. ЗАДАЧИ УПРАВЛЕНИЯ ЗАПАСАМИ. 3.1. Природа задач управления запасами. Управляемые и неуправляемые переменные в задачах о запасах. 3.2. Содержание задач управления запасами. 3.3. Структура систем управления запасами. 3.4. Примеры задач управления запасами. 3.5. Общая детерминированная задача для однородной продукции при одном уровне управления. 3.6. Детерминированная задача при разных видах продукции и одноуровневом управлении запасами. 3.7. Примеры реальных задач управления запасами.

4. ЗАДАЧИ СЕТЕВОГО ПЛАНИРОВАНИЯ И УПРАВЛЕНИЯ. 4.1. Задачи упорядочения (задачи составления расписания). Условия, осложняющие постановку и решение задач упорядочения. 4.2. Критерии оптимальности, применяемые в задачах упорядочения. 4.3. Аналитические методы решения задач упорядочения. 4.4. Задачи согласования. Условия для постановки задачи согласования.

5. ЗАДАЧИ ЗАМЕНЫ И РЕМОНТА ОБОРУДОВАНИЯ. 5.1. Типы задач замены и ремонта оборудования. 5.2. Обновление оборудования при неслучайном износе. 5.3. Оборудование длительного пользования. 5.4. Приведение (дисконтирование) затрат. 5.5. Замена с целью предупреждения отказа. 5.6. Групповая замена. 5.7. Задача контроля исправности. 5.8. Общий процесс обновления оборудования. 5.9. Случайный износ. Кривая продолжительности службы оборудования. Надежность.

6. СОСТЯЗАТЕЛЬНЫЕ ЗАДАЧИ. 6.1. Структура состязательных ситуаций. Теория игр. 6.2. Примеры состязательных задач. 6.3. Парная игра с нулевой ничьей. 6.4. Игры с ненулевой суммой. 6.5. Задачи о торгах: закрытые торги за контракт на услуги, открытые торги (аукцион). 6.6. Задача сбыта.

7. ЗАДАЧИ ПОИСКА. 7.1. Типы ситуаций поиска. 7.2. Источники ошибок наблюдений. План выборки. Оптимальное распределение усилий на поиск. Многоэтапный поиск. 7.3. Математическая постановка задач поиска. 7.4. Задача индивидуального типа. 7.5. Массовый случай. 7.6. Подход статистической теории принятия решений к проверке гипотез. 7.7. «Обратный» поиск.

8. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ РАСПИСАНИЙ. 8.1. Операция. Классификация задач теории расписаний. Методы представления расписаний. 8.2. Критерии оценки расписаний. Критерии оценки систем. 8.3. Соотношение между длительностью прохождения и средним числом работ в системе. Расписания и стоимость.

9. ЗАДАЧИ ТЕОРИИ РАСПИСАНИЙ. 9.1. Перестановочные расписания. Упорядочение по минимуму длительностей работ. Упорядочение в соответствии с плановым сроком. Случайное упорядочение. 9.2. Антитетичные правила составления расписаний. Упорядочение при неполной информации. Упорядочение в случае критерия с учетом весов. Задачи упорядочения.
9.3. Длительность настройки, зависящая от упорядочения. Неодновременное поступление работ. 9.4. Составление расписаний при частичном упорядочении. Составление расписаний при заданном отношении предшествования. 9.5. Параллельные машины. Параллельно-последовательное обслуживание. 9.6. Перестановочные расписания. Минимизация максимальной длительности прохождения в системе n | 2 | F | Fmax. Минимизация средней длительности прохождения в системе n | 2 | F | F. 9.7. Упорядочение в больших системах конвейерного типа. Задачи составления расписаний. 9.8. Поиск критического пути. Отыскание кратчайшего пути. Системы типа сборочной линии.

10. ПРИКЛАДНЫЕ ЗАДАЧИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ. 10.1. Анализ динамических процессов. Область применения моделей динамического программирования. Структура многошагового анализа. Принцип оптимальности. Рекуррентное соотношение для нахождения стратегии оптимальных затрат для n шагов. 10.2. Задача управления запасами. Построение модели. Формулировка задачи динамического программирования. Поиск оптимальной производственной программы. Анализ чувствительности решения по отношению к длительности планового периода. Зависимость оптимальной программы от исходного уровня запасов. Долгосрочный анализ при усеченном плановом периоде. Поиски возможностей улучшения плана. 10.3. Модель распределения усилий. Модель общего вида. Модель с двумя ограничениями. Погруженная задача для модели распределения усилий. 10.4. Модель замены оборудования. Использование ациклической сети для описания задачи определения стратегии замены оборудования. Сравнение двух моделей замены оборудования.

11. МОДЕЛИ С БЕСКОНЕЧНЫМ ПЛАНОВЫМ ПЕРИОДОМ.
11.1. Критерии оптимальности. Оптимальное поведение при стационарности. Методы оценки бесконечных последовательностей значений эффекта. Полезность денег. Критерий среднего эффекта за отрезок. Критерий интегрального дисконтированного эффекта. Критерий эквивалентного среднего эффекта. 11.2. Модель эксплуатации лесного хозяйства. Однократное принятие решения. Оптимальная стратегия при бесконечном плановом периоде. Модель восстановления при конечном плановом периоде. Модель восстановления при бесконечном плановом периоде. 11.3. Методы последовательных приближений. Бесконечный период как предел конечного периода. Метод последовательных приближений в пространстве функций. Метод последовательных приближений в пространстве стратегий. 11.4. Методы оптимизации при бесконечном плановом периоде. Экстремальное уравнение для бесконечного планового периода. Теорема о стационарной стратегии. Дискретная задача динамического программирования. Метод итераций по критерию. Метод итераций по стратегиям. Минимизация среднего эффекта за отрезок: теорема о стационарной стратегии, метод итераций по стратегиям.

12. ВЕРОЯТНОСТНЫЕ МОДЕЛИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ. 12.1. Стохастические модели прикладных задач динамического программирования. Задача распределения усилий. Оптимальные правила принятия управляющих решений. Дерево решений. Модель управления запасами. Задача определения оптимального размера партии заказа. Задача составления коммерческого прогноза. Стохастическая модель восстановления (задача замены оборудования). Применимость методов вероятностного динамического программирования. 12.2. Стохастическая модель задачи о кратчайшем маршруте. Рекуррентное соотношение для оптимизационной задачи. Практическая применимость стохастической задачи о кратчайшем маршруте. Постановка и решение задачи в терминах линейного программирования. 12.3. Обобщенная стохастическая модель при бесконечном плановом периоде. Экстремальное уравнение для случая бесконечного планового периода с дисконтированием. Теорема о стационарной стратегии. Метод итераций по критерию. Метод итераций по стратегиям.

13. МАРКОВСКИЕ ПРОЦЕССЫ С ДИСКРЕТНЫМ ВРЕМЕНЕМ И ДОХОДАМИ. 13.1. Марковские процессы с дискретным временем. Производящие функции. Анализ марковских процессов с помощью производящих функций. Анализ марковских процессов с поглощающими и периодическими состояниями. 13.2. Марковские процессы с доходами. Рекуррентное соотношение для доходов. Анализ марковских процессов с доходами при помощи производящих функций. Исследование полного ожидаемого дохода при больших n.

14. ПРОЦЕССЫ ПОСЛЕДОВАТЕЛЬНЫХ РЕШЕНИЙ. 14.1. Определение стратегий. Рекуррентный метод. 14.2. Итерационный метод для процессов последовательных решений. Определение весов. Улучшение решения. 14.3. Итерационный метод для процессов с несколькими эргодическими классами. Определение весов. Улучшение решения.

15. ПРОЦЕССЫ ПОСЛЕДОВАТЕЛЬНЫХ РЕШЕНИЙ С ПЕРЕОЦЕНКОЙ. 15.1. Определение процесса последовательных решений с переоценкой. Рекуррентный метод. 15.2. Итерационный метод. Определение предельных доходов. Улучшение решения. Зависимость оптимального решения от коэффициента переоценки.

16. ПРОЦЕССЫ ПОСЛЕДОВАТЕЛЬНЫХ РЕШЕНИЙ С НЕПРЕРЫВНЫМ ВРЕМЕНЕМ. 16.1. Марковские процессы с непрерывным временем. Изучение марковских процессов с непрерывным временем с помощью преобразований Лапласа. 16.2. Марковские процессы с непрерывным временем и доходами. 16.3. Задача последовательных решений в случае непрерывного времени. Итерационный метод. Определение весов. Улучшение решения. 16.4. Процесс последовательных решений с непрерывным временем и переоценкой. Итерационный метод.

5. Образовательные технологии

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

6. Учебно-методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины

7. Учебно-методическое и информационное обеспечение дисциплины

а) основная литература:

1. Вентцель операций. Задачи, принципы, методология. – М.: Кнорус, 2010. – 192 с.

2. Исследование операций [Электронный ресурс] / Б. А. Горлач. – Москва : Лань, 2013.

б) дополнительная литература:

1. Л. Математическое программирование в примерах и задачах. – М.: Высш. шк., 1993. – 336 с.

2.  С. Исследование операций: задачи, принципы, методология. – М.: Кнорус, 2010. – 191 с.

3. Долгов теории исследования операций: учеб. пособие. – Саратов: Научная книга, 2008. – 151 с.

4. В. Динамическое программирование в экономических задачах. – М.: БИНОМ, Лаб. знаний, 2006. – 176 с.

5. Мирецкий И. Ю. Матричные модели и методы в теории расписаний. – Пенза: Изд-во Пенз. гос. ун-та, 2003. – 256 с.

6.  С. Управляемые марковские процессы и их приложения в системном анализе. – Саратов: Науч. кн., 2008. – 107 с.

7.  А.,  А. Теория вероятностей. Управляемые цепи Маркова в экономике. – М.: ФИЗМАТЛИТ, 2005. – 248 с.

8. Станкевич составления расписаний: Учеб.-метод. пособие Саратов: . центр «Наука», 2010.– 47 с.

9. Станкевич теории расписаний: Учеб. пособие Саратов: Изд-во «Научная книга», 2010.– 94 с.

10. Таха в исследование операций: в 2-х книгах / пер. с англ. – М.: Мир, 1985, Кн.1. – 480 с.

11. Таха в исследование операций: в 2-х книгах / пер. с англ. – М.: Мир, 1985, Кн.2. – 496 с.

в) Программное обеспечение: операционная система Microsoft Windows, офисный пакет приложений Microsoft Office, языки программирования C++, Object Pascal (Delphi). Интернет-ресурсы не используются.

8. Материально-техническое обеспечение дисциплины

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

Программа составлена в соответствии с требованиями ФГОС ВПО
с учетом рекомендаций и Примерной ООП ВПО по направлению подготовки 27.03.03 Системный анализ и управление.

Автор:

Доцент кафедры системного анализа

и автоматического управления, к. ф.-м. н.

Программа одобрена на заседании кафедры системного анализа и автоматического управления

от _________________2014 года, протокол № _____.

Подписи:

Зав. кафедрой системного анализа

и автоматического управления,

д. т.н., профессор

Декан факультета компьютерных наук

и информационных технологий,

к. ф.-м. н., доцент