Рабочая программа дисциплины «Системный анализ и исследование операций» по направлению подготовки дипломированного специалиста 654600 «Информатика и вычислительная техника»

Вид материала

Рабочая программа

Содержание 1. Цели и задачи дисциплины Основными задачами изучения дисциплины 2. Требования к уровню освоения содержания дисциплины 3. Объем дисциплины и виды учебной работы 4. Содержание дисциплины 4.2. Содержание разделов дисциплины Раздел 1. Основы системного анализа (3 часа). Раздел 2. Методология исследования операций (4 часа). Раздел 3. Линейное программирование (4 часа). Раздел 4. Транспортная задача ЛП (2 часа). Раздел 5. Целочисленное программирование (4 часа) Раздел 6. Динамическое программирование (4 часа). Раздел 7. Стохастическое программирование (2 часа). Раздел 8. Геометрическое программирование (3 часа). Раздел 9. Теория игр (4 часа). Раздел 10. Типовые задачи и модели исследования операций (1 час). Раздел 11. Программное обеспечение исследования операций (2 часа). 5.1. Лабораторный практикум 5.2. Практические занятия 6. Учебно-методическое обеспечение ... Полное содержание

Подобный материал:

• Рабочая программа дисциплины «Компьютерная графика» по направлению подготовки дипломированного, 108.6kb.
• Рабочая программа дисциплины «Методы оптимизации» по направлению подготовки дипломированного, 132.79kb.
• Рабочая программа дисциплины «Теория систем» по направлению подготовки дипломированного, 142.63kb.
• Рабочая программа дисциплины «Инструментальные средства 3D графики» по направлению, 112.55kb.
• Рабочая программа дисциплины «Параллельные вычислительные процессы» по направлению, 108.72kb.
• Рабочая программа дисциплины «Теория принятия решений» по направлению подготовки дипломированного, 176.95kb.
• Рабочая программа дисциплины «Проектирование интеллектуальных автоматизированных систем», 126.15kb.
• Рабочая программа дисциплины «Современные технологии разработки интеллектуальных автоматизированных, 121.51kb.
• Рабочая программа дисциплины «Системы искусственного интеллекта» по направлению подготовки, 132.28kb.
• Рабочая программа дисциплины «Теоретические основы автоматизированного управления», 141.49kb.

Министерство образования Российской Федерации

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

УТВЕРЖДАЮ

Председатель УМК по направлению

«Информатика и вычислительная техника»

проф., д.т.н. Федунец Н.И.

«_____» ____________2002 г.

Рабочая программа

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

по направлению подготовки дипломированного специалиста

654600 - «Информатика и вычислительная техника»

специальности 220200 – «Автоматизированные системы обработки информации и управления»

Москва 2002

^ 1. ЦЕЛИ И ЗАДАЧИ ДИСЦИПЛИНЫ

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

^ Основными задачами изучения дисциплины являются:

• рассмотрение основных положений системного анализа и обучение студентов практическому применения к задачам исследования операций;
  
• обучение практическим навыкам подхода к построению качественной и математической постановке практических типовых задач исследования операций;
  
• детальное изучение каждого метода и реализующих их алгоритмов исследования операций;
  
• обучение практическим навыкам решения задач исследования операций ручным методом;
  
• обучение практическим навыкам решения различных задач исследования операций на персональном компьютере с использованием библиотек и пакетов программ (в том числе в интерактивном режиме в глобальной сети INTERNET).
  

^ 2. ТРЕБОВАНИЯ К УРОВНЮ ОСВОЕНИЯ СОДЕРЖАНИЯ ДИСЦИПЛИНЫ

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

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

Студент должен уметь:

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

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


^ 3. ОБЪЕМ ДИСЦИПЛИНЫ И ВИДЫ УЧЕБНОЙ РАБОТЫ

Вид учебной работы	Всего часов	Семестр
Общая трудоемкость дисциплины Аудиторные занятия	136 85	5
Лекции Практические занятия (ПЗ) Лабораторные занятия (ЛЗ)	51 17 17	51 17 17
Самостоятельная работа (СР)	51	51
Курсовая работа (КР)
Расчетно-графические работы (РГР)
Вид итогового контроля		зачет, экзамен

^ 4. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ

4.1. Разделы дисциплины и виды занятий

№ п/п	Раздел дисциплины	Лекции	ПЗ	ЛР
1	2	3	4	5
	Введение	*
1	Основы системного анализа	*
2	Методология исследования операций	*
3	Линейное программирование	*	*	*
4	Транспортная задача линейного программирования	*	*	*
5	Целочисленное программирование	*	*	*
6	Динамическое программирование	*	*	*
7	Стохастическое программирование	*	*
8	Геометрическое программирование	*	*
9	Теория игр	*	*	*
10	Типовые задачи и модели исследования операций	*		*
11	Программное обеспечение исследования операций	*

^ 4.2. Содержание разделов дисциплины


Введение (1 час)

Предмет дисциплины, её цели и задачи. Связь данной дисциплины с другими математическими дисциплинами. История развития и использования методов исследования операций в мировой и отечественной практике.

^ Раздел 1. Основы системного анализа (3 часа).

Определение понятия системы. Сложные системы. Классификация систем. Свойства систем. Уровни описания систем. Анализ поведения систем. Основные определения системного анализа. Декомпозиция и композиция систем. Основные принципы системного анализа. Основные положения и особенности системного анализа.


^ Раздел 2. Методология исследования операций (4 часа).

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


^ Раздел 3. Линейное программирование (4 часа).

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


^ Раздел 4. Транспортная задача ЛП (2 часа).

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


^ Раздел 5. Целочисленное программирование (4 часа).

Причины возникновения целочисленных задач оптимизации. Общая математическая постановка задач целочисленного и смешанного целочисленного линейного программирования. Классификация и краткая характеристика методов решения задач целочисленного программирования. Методы и алгоритмы отсечения, ветвей и границ. Примеры. Краткая характеристика пакетов программ целочисленного программирования.


^ Раздел 6. Динамическое программирование (4 часа).

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


^ Раздел 7. Стохастическое программирование (2 часа).

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


^ Раздел 8. Геометрическое программирование (3 часа).

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


^ Раздел 9. Теория игр (4 часа).

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

Стратегические матричные игры. Игры двух лиц с нулевой суммой. Принцип минимакса. Графическое решение игр. Бесконечные, многошаговые, дифференциальные игры. Решение игр методами линейного программирования.

Статистические игры. Особенности. Принципы выбора стратегии. Применение критериев, основанных на известных вероятностных условий. Классические критерии Лапласа, Вальда, Сэвиджа, Гурвица. Статистические игры с проведением единичного эксперимента.

Кооперативные игры. Основные понятия и определения. Проблемы и формы кооперации. Характеристическая функция. Доминирование. Устойчивые множества дележей. Принципы и необходимые условия оптимальности стратегий. Значение игры по Шепли. Применение кооперативных игр на практике.


^ Раздел 10. Типовые задачи и модели исследования операций (1 час).

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

Математические модели в экономике, финансах, бизнесе, социальной сфере.


^ Раздел 11. Программное обеспечение исследования операций (2 часа).

Характеристика, структура, состав и особенности раздела «Оптимизация» зарубежных коммерческих библиотек программ по вычислительной математики NAG C, IMSL C, Java, Fortran и отечественных и зарубежных специализированных пакетов программ ПАОЭМ, БЧА НИВЦ МГУ и др., OSL, Optima Library, HSL 2000, CPLEX и др. для решения задач исследования операций под управлением различных операционных систем WINDOWS 2000/NT, UNIX, LINUX.

Организация данных, форматы ввода-вывода современных пакетов программ.


^ 5.1. ЛАБОРАТОРНЫЙ ПРАКТИКУМ

№ п/п	№ раздела дисциплины	Наименование лабораторных работ
1 2 3 4 5 6 7 8 9	3 3 4 3 5 6 10 9 10	Решение двухмерных задач линейного программирования с использованием Java Applets в сети Internet Решение задач линейного программирования небольшой размерности различными методами c использованием ППП LINDO Решение транспортных задач линейного программирования ПАОЭМ ПК Исследование задач ЛП на чувствительность с использованием пакета ПАОЭМ ПК и LINDO Решение задач целочисленного программирования (смешанных задач, задач с булевыми переменными) (ПАОЭМ ПК, LINDO) Решение дискретных задач методом динамического программирования Решение задач о максимальном потоке Решение матричных игр Решение задач нелинейного программирования (LINDO)

^ 5.2. ПРАКТИЧЕСКИЕ ЗАНЯТИЯ

№ п/п	№ раздела дисциплины	Наименование практического занятия
1 2 3 4 5 6 7 8 9 10	3,11 3,11 3,11 4,11 4 3,5,11 6,11 7,11 8 9,11	Качественная постановка типовой задачи линейного программирования. Решение задач линейного программирования графическим методом. Решение задач линейного программирования небольшой размерности различными методами в интерактивном режиме в сети InterNet. Решение двойственной задачи линейного программирования. Решение транспортной задачи линейного программирования с различными критериями оптимальности Решение задач целочисленного программирования методами Гомори и ветвей и границ. Решение дискретных и непрерывных задач методом динамического программирования. Решение одно и двухэтапных задач методами стохастического программирования на персональном компьютере. Решение простейших задач методами геометрического моделирования. Решение матричных, стратегических и кооперативных игр.

^ 6. УЧЕБНО-МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ

6.1. Рекомендуемая литература

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

1. Исследование операций. В 2-х томах. Под ред. Моудера Дж., С. ЭлмаГраби. Пер. с англ. Том 1. Методологические основы и математические методы, с. 712. М., «Мир», 1981.
   
2. Таха Х. Введение в исследование операций. В 2-х кн. Кн.1, с. 479, кн.2, с.496. Пер. с англ. М., «Мир», 1985.
   
3. Дегтярев Ю.И. Системный анализ и исследование операций. Учебник для студентов вузов, обучающихся по спец. 22.02.00. М., «Высшая школа», 1996, с. 335, библ. 23 назв.
   
4. Браверман Э.М. Математические модели планирования и управления в экономических системах. М., «Наука», 1976, с. 366.
   
5. Цурков В.И. Декомпозиция в задачах большой размерности. Под ред. Г.С. Поспелова. М., «Наука», 1981, с. 351, библ. 146 назв.
   
6. Даффин Р., Питерсон Э., Зенер К. Геометрическое программирование. Пер. с англ. М., «Мир», 1972, с. 311, библ. к каждой главе.
   
7. Банди Б. Основы линейного программирования. Пер. с англ. М., «Радио и связь», 1989, с. 176, библ. 18 назв.
   
8. Юдин Д.Б., Юдин А.Д. Экстремальные модели в экономике. М., «Экономика», 1979, с. 287, библ. 66 назв.
   
9. Перегудов Ф.И., Тарасенко Ф.П. Основы системного анализа. М., «Высшая школа», 1957, с. 384, библ. в конце каждой главы.
   
10. Зарубежные библиотеки и пакеты программ по вычислительной математике. Пер.с англ. М., «Наука», 1993, с. 344, библ. к каждой главе.
    

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

1. Ермольев Ю.М., Ястремный А.И. Стохастические модели и методы в экономическом планировании. М., «Наука», 1979, с. 253, библ. стр. 248-251.
   
2. Венцель Е.С. Исследование операций. М., «Советское радио», 1972, с. 551, библ. 29 назв.
   
3. Кузнецов Ю.А., Кузубов В.И., Волощенко А.Б. Математическое программирование. Изд-е 2-е, пер. и доп., М., «Высшая школа», 1980, с. 300, библ. 17 назв.
   
4. Акулич И.Л. Математическое программирование в примерах и задачах. М., «Высшая школа», 1986, с. 319, библ. 35 назв.
   
5. Бекишев Г.А., Кратко М.И. Элементарное введение в геометрическое программирование. М., «Наука», 1980, с. 143, библ. 5 назв.
   
6. Зенер К. Геометрическое программирование и техническое проектирование. Пер. с англ. М., «Мир», 1973, с. 111, библ. с. 108-109.
   
7. Мину М. Математическое программирование. Теория и алгоритмы. Пер. с фр. М., 1990, с. 486, библ. к каждой главе.
   

^ 6.2. Средства обеспечения освоения дисциплины

Для решения задач исследования операций на практических занятиях на персональных компьютерах используются библиотеки программ по вычислительной математике IMSL, NAG, MATLAB, MATHCAD и специализированные пакеты прикладных программ OSL, HARWEL, IBM, LINDO, ПАОЭМ.

7. ^ МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ
   

Для решения задач исследования операций на практических занятиях на персональных компьютерах используются библиотеки программ по вычислительной математике IMSL, NAG, MATLAB, MATHCAD и специализированные пакеты прикладных программ OSP, HARWEL, IBM.

7. ^ МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО ОРГАНИЗАЦИИ ИЗУЧЕНИЯ ДИСЦИПЛИНЫ
   

8.1. Методические рекомендации преподавателю

Лекции должны читаться в полном соответствии с нормами и правилами высшей школы Российской Федерации и данной рабочей программой. Преподавателю рекомендуется учесть как опыт чтения данной дисциплины в МГГУ и других ведущих университетах и вузах РФ, так и зарубежный опыт чтения лекций в ведущих университетах передовых стран мира: США, Канада, Германия, Англия и др. Для этого преподавателю рекомендуется просматривать, причем регулярно, Web-страницы и сайты ведущих университетов и институтов в сети InterNet, посвященные программам и отдельным разделам дисциплины «Исследование операций (Operations Research), а также программному обеспечению исследования операций.

^ Практические занятия рекомендуется проводить в полном соответствии с темами практических занятий, утвержденными данной программой. Для глубокого освоения методов и алгоритмов задачи исследования операций решаются преподавателем совместно со студентами вручную в аудитории, а также в учебной лаборатории на современных персональных компьютерах на базе Pentium II и Pentium III под управлением операционных систем Windows 2000/NT, UNIX, LINUX с использованием библиотек IMSL, NAG, IBM, HARWELL, OPTIMA и пакетов программ CPLEX, LINDO, ПАОЭМ, написанных на алгоритмических языках высокого уровня. Алгоритмические языки, программы и форматы ввода-вывода данных выбираются преподавателем по собственному усмотрению. По каждой выполненной лабораторной работе студентом выполняется отчет на компьютере. Преподавателю рекомендуется или периодически, или в конце семестра проводить зачетные занятия по лабораторным и практическим работам.

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


^ 8.2. Примерные темы рефератов

1. Сравнительный анализ методов решения задач линейного программирования.
   
2. Методы решения ЗЛП большой размерности.
   
3. Обзор пакетов прикладных программ для решения задач линейного программирования в РФ и за рубежом.
   
4. Организация данных пакетов прикладных программ. Форматы входных и выходных данных оптимизационных пакетов.
   
5. Обзор методов решения специальных задач линейного программирования. Транспортные задачи ЛП.
   
6. Задачи дробно-линейного программирования. Сведение их к задаче ЛП.
   
7. Задачи параметрического программирования. Экономическая и геометрическая их интерпретация.
   
8. Экономическая и геометрическая интерпретация задач нелинейного программирования. Примеры.
   
9. Градиентные методы решения задач нелинейного программирования.
   
10. Методы штрафных функций.
    
11. Сравнительный анализ методов решения задач целочисленного программирования.
    
12. Стохастические задачи динамического программирования.
    
13. Методы внутренних точек решения задач ЛП.
    
14. Аналитический и графический методы решения игр.
    
15. Многокритериальные задачи оптимизации.
    
16. Основные положения системного анализа.
    
17. Основные положения методологии исследования операций.
    
18. Краткая характеристика задач исследования операций.
    

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


^ 8.3. Методические рекомендации студентам

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

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

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

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


Программа составлена в соответствии с Государственным образовательным стандартом высшего профессионального образования по направлению 654600 – «Информатика и вычислительная техника» и специальности 220200 – «Автоматизированные системы обработки информации и управления».

Программу составил:

доц., к.т.н. Черников Ю.Г.


Рецензент

проф., д.т.н. Бахвалов Л.А.

Программа одобрена на заседании кафедры АСУ

«___» ___________2002 г. протокол №


Зав. кафедрой АСУ

проф., д.т.н. Федунец Н.И.