ИССЛЕДОВАНИЕ ОПЕРАЦИЙ

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

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

Достижение цели обучения обеспечивается решением следу ющих основных задач:

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

ü знание основных принципов оптимальности (экстремальность, паретооптимальность, доминирование, гарантированный результат, равновесие, устойчивость);

ü овладения умениями и навыками применения математического аппарата к задачам теории исследования операций.

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

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

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

ü уметь моделировать практические задачи исследования операций,

ü уметь применять математический аппарат, используемый в теории исследования операций

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

Вид учебной работы	Всего часов	Семестры
Общая трудоемкость	144	9
Аудиторные занятия	72
Лекции	36
Практические занятия (семинары)	28
Лабораторные работы	8
Самостоятельная работа	72
Курсовые работы/рефераты	X
Вид итогового контроля		экзамен

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

4.1. РАЗДЕЛЫ ДИСЦИПЛИНЫ И ВИДЫ ЗАНЯТИЙ¹

Мо			Практи-	Лабора-
п/п	Разделы дисциплины	Лекции	ческие занятия,	торные работы
			семинары
I	Основные понятия и мате-
	матическая модель операции	Х(4)	Х(4)
2	Классические оптимизаци-
	онные задачи	Х(4)	Х(4)
3	Линейное программирование	Х(4)	Х(2)	Х(2)
4	Нелинейное программирование	Х(4)	Х(2)	Х(2)

¹ В скобках указано распределение часов по видам занятий, рекомендо ванное Учебно-методической комиссией по информатике УМО по специальностям педагогического образования

5	Динамическое программи рование	Х(4)	Х(2)	Х(2)
6	М ногокритериальная оптимизация	Х(4)	Х(4)
7	Игры в нормальной форме	Х(4)	Х(4)
8	Позиционные игры	Х(4)	Х(4)
9	Теория массового обслуживания	Х(4)	Х(2)	Х(2)

4.2. СОДЕРЖАНИЕ РАЗДЕЛОВ ДИСЦИПЛИНЫ

I. ОСНОВНЫЕ ПОНЯТИЯ И МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ОПЕРАЦИИ

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

II. КЛАССИЧЕСКИЕ ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ

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

III. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Постановка задачи, геометрический смысл, примеры. Симплекс-метод. Двойственные задачи и теоремы двойственности. Транс портная задача, метод потенциалов. Целочисленное линейное программирование. Методы отсечений и ветвей и границ.

IV. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

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

V. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

Многошаговые задачи принятия решений. Формулировка задачи динамического программирования, примеры (задачи распределения ресурсов, управления запасами, сетевые). Метод динамического программирования. Принцип оптимальности и функция Беллмана.

VI. МНОГОКРИТЕРИАЛЬНАЯ ОПТИМИЗАЦИЯ

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

VII. ИГРЫ В НОРМАЛЬНОЙ ФОРМЕ

Определение игры. Информированность и принципы поведения. Гарантированный результат. Биматричные игры. Доминирующие и доминируемые стратегии. Разрешимость по доминированию. Равновесие по Нэшу. Равновесие и паретооптимальность. Антагонистические игры. Матричная игра. Определение понятия цены антагонистической игры. Смешанные стратегии. Существование цены игры и равновесия в смешанных стратегиях. Методы решения матричных игр и нахождения равновесных ситуаций. Примеры.

VIII. ПОЗИЦИОННЫЕ ИГРЫ

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

IX. ТЕОРИЯ МАССОВОГО ОБСЛУЖИВАНИЯ

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

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

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

2. Решение двойственной задачи линейного программирования; нахождение по решению двойственной задачи, решение прямой задачи.

3. Метод Монте-Карло решения целочисленной задачи линейного программирования.

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

5. Решение задачи квадратичного программирования.

6. Метод условного градиента для решения задач квадратичного программирования.

7. Задачи о распределении ресурса; задачи о благосостоянии; задачи о капиталовложениях.

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

5. УЧЕБНО-МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ

5.1. РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА

ОСНОВНАЯ

1. Акулич И.Л. Математическое программирование в задачах и упражнениях М Высшая школа,.

2. Давыдов Э.Г. Исследование операций. М Высшая школа,1990

3. Курицкий Б'К. Поиск оптимальных решений средствами Ехсеl 7.0. - СПб.: ВНУ, 1997.

4. Мину М. Математическое программирование. Теория и алгоритмы. М.: Наука, 1990.

5. Шикин Е.В., Чхартишвили А.Г. Математические методы и модели в управлении- Учебник для вузов. М.: Дело, 2000.

ДОПОЛНИТЕЛЬНАЯ:

1. Горелик.В.А., Ушаков И.А. Исследование операций. М.: Машиностроение, 1986.

2. Вентцель Е.С. Исследование операций. М.: Советское радио, 1972.

3. Беллман Р., Дрейфус С. Прикладные задачи динамического про граммирования. М.: Наука, 1965.

4. Вагнер Г. Основы исследования операций. Т. 1 3. М.: Мир, 1972,1973.

5. Васильев Ф.П. Численные методы решения экстремальных задач. М.: Наука, 1980.

6. Вилкас Э.И. Оптимальность в играх и решениях. М.: Наука, 1990.

7. Гермейер Ю.Б. Введение в теорию исследования операций. М.: Наука, 1976.

8. Евтушенко Ю.Г. Методы решения экспериментальных задач и их применение в системах оптимизации. М.: Наука, 1982.

9. Интрилигатор М. Математические методы оптимизации и экокомическая теория. М.: Прогресс, 1975.

10. Морозов В.В., Сухарев А.Г., Федоров В.В. Исследование операций в задачах и упражнениях. М.: Высшая школа, 1986.

11. Мулен Э. Теория игр с примерами из математической экономики. М.: Мир, 1985.

12. Павловский Ю.Н. Имитационные модели и системы. М.: Фазиз, 2000.

13. Петросян Л.А., Зенкевич Н.А., Семина Е.А. Теория игр: Учебное пособие для университетов. М.: Высшая школа: Книжный дом Университет , 1998.

14. Таха X. Введение в исследование операций. Т. 1,2. М.: Мир,1985.

5.2. СРЕДСТВА ОБЕСПЕЧЕНИЯ ОСВОЕНИЯ ДИСЦИПЛИНЫ

1. Электронные таблицы Ехсе1.

2. Системы программирования: Turbo Pascal, Borland С++, Лисп.

3. Системы оптимизации и имитации.

4. Учебные и методические пособия (учебники, учебно-методические пособия, пособия для самостоятельной работы, сборники упражнений и др.).

6. МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ

Для обеспечения дисциплины необходимы: специально оборудованные аудитории; персональные компьютеры (модели: 386, 486, Pentium); различные технические и аудиовизуальные средства обучения.

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

7.1. ПЕРЕЧЕНЬ ПРИМЕРНЫХ КОНТРОЛЬНЫХ ВОПРОСОВ И ЗАДАНИЙ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

1. Построение математической модели задачи планирования производства.

2. Решение методом Лагранжа задачи о потреблении.

3. Графическое решение двухмерной задачи линейного программирования.

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

5. Графическое и аналитическое решение матричных и биматричных игр.

6. Нахождение совершенного равновесия методом обратной индукции.

7.2. ПРИМЕРНАЯ ТЕМАТИКА РЕФЕРАТОВ,КУРСОВЫХ РАБОТ

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

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

3. Обработка Данных по методу наименьших квадратов и его реализация с использованием электронных таблиц Ехсе1.

4. Метод Брана решения матричной игры и его численная реализация.

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

7.3. ПРИМЕРНЫЙ ПЕРЕЧЕНЬ ВОПРОСОВ К ЭКЗАМЕНУ

1. Необходимые и достаточные условия безусловного экстремума.

2. Метод множителей Лагранжа.

3. Симплекс-метод.

4. Теоремы двойственности в линейном программировании.

5. Метод потенциалов для решения транспортной задачи.

6. Методы отсечении в целочисленном линейном программировании.

7. Теорема Куна Таккера для задачи выпуклого программирования.

8. Метод штрафных функций решения задачи математического программирования.

9. Метод динамического программирования.

10. Теорема фон Неймана: существование цены матричной игры в смешанных стратегиях.

11. Метод Шепли Сноу решения матричных игр.

12. Равновесие по Нэшу.

13. Оценка пропускной способности СМО.

14. Оценка среднего времени ожидания заявки.