Государственное образовательное учреждение высшего профессионального образования
«Дальневосточный государственный университет путей сообщения»
Естественно-научный институт
УТВЕРЖДАЮ:
Заведующий кафедрой
профессор
______________
«___»_________2011 г.
РАБОЧАЯ ПРОГРАММА
дисциплины
«Теория игр и исследование операций»
для специальности / направления подготовки:
Математик, системный программист / 010500 Прикладная математика и информатика
Составитель: профессор
Обсуждена на заседании кафедры «Прикладная математика»
«__» ____________ 20____ г., протокол № ___
Одобрена на заседании методической комиссии «Естественно-научного института»
«___» ____________ 20____ г., протокол № ___
Одобрена на заседании методической комиссии «Институт экономики»
«___» ____________ 20____ г., протокол № ____
2011 г.
Рабочая программа
по дисциплине
«Теория игр и исследование операций»
направление 010500 Прикладная математика и информатика
квалификация Математик, системный программист
1. Цель и задачи дисциплины, ее связь с другими дисциплинами
Цель и задачи дисциплины «Теория игр и ислледование операций» (ТИиИО) состоят в том, чтобы научить студентов математическему моделированию конфликтных ситуаций, а также освоению ими математических методов и алгоритмов поиска оптимальных стратегий. Дисциплина связана практически со всеми разделами математики, а также с экономикой и социологическими науками. Для понимания задач и методов ТИиИО необходимо владение основными понятиями и результатами математического анализа, алгебры и теории вероятностей. С другой стороны,
например, экономика уже давно использует игровые модели с привлечением результатов ТИиИО. В последнее время ТИиИО применяется в транспортных проблемах для поиска оптимальных решений.
2. Требования ГОСТА к обязательному минимуму содержания основной образовательной программы
Выписка из требований ГОСТА: по окончании курса ТииИО студент должен иметь навыки по составлению математических моделей операций, знание теоретических положений по основным типам задач исследования операций и основным типам игр, навыки по разработке алгоритмов решения задач исследования операций и теории игр в различных условиях информированности о неконтролируемых факторах.
3. Объем дисциплины и его распределение по видам работ
Семестр 7 (18 недель)
Лекции | 18 | Формы отчетности | |
Лабораторные занятия | 0 | Экзамен | 1 |
Практические занятия | 18 | Зачет | 0 |
Всего аудиторных часов | 36 | Курсовой проект | 0 |
Индивидуальные занятия | Курсовая работа | 0 | |
Самостоятельная работа студента | 20 | Расчетно-графическая работа | 0 |
Всего часов | 56 | Форма рубежного контроля: опрос | 0 |
4. Модульное построение содержания учебного материала дисциплины
Не требуется, т. к. дисциплина изучается один семестр.
5. Тематическое содержание курса
Содержание лекционного курса
Номер занятия (лекции, практического, семинарского, лабораторного занятия) | Содержание занятия | Кол-во часов |
1 | Определение конечной антагонистической игры. Нижнее и верхнее значения игры. Ситуация равновесия. Максиминная и минимаксная чистые стратегии. | 2 |
2 | Введение в линейное программирование. Формулировка теоремы о существовании оптимального решения. | 2 |
3 | Смешанное расширение матричной игры. Лемма о существовании максиминной стратегии. Теорема о минимаксе (I). | 2 |
4 | Теорема о минимаксе (II). Следствия. | 2 |
5 | Теорема о значении матричной игры как экстремальном значении некоторого множества вещественных чисел. Теорема о свойстве спектра оптимальной стратегии. | 2 |
6 | Теоремы о подыгре. Одна модель антагонистической конкуренции. Вариант конечной игры. | 2 |
7 | Сведение задачи матричной игры к задачам линейного программирования. | 4 |
8 | Бесконечные антагонистические игры. Проблемы, возникающие в связи с бесконечными множествами чистых стратегий. Формулировка теоремы о существовании значения игры. Спектр. Теорема о свойстве спектра оптимальной стратегии. | 2 |
9 | Бескоалиционные игры. Определение среднего выигрыша каждого игрока. | 2 |
Итого | 18 |
Содержание практического курса
Номер занятия (лекции, практического, семинарского, лабораторного занятия) | Содержание занятия | Кол-во часов |
1 | Вычисление верхнего и нижнего значений конечных антагонистических игр в чистых стратегиях. Примеры решения конечных антагонистических игр в чистых стратегиях. | 2 |
2 | Выпуклые множества. Выпуклая линейная оболочка. Гиперплоскость, полупространство, угловые точки. Задачи о выпуклых множествах. | 2 |
3 | Симплекс-метод для решения задач линейного программирования | 2 |
4 | Смешанное расширение конечной антагонистической игры. Решение игры с матрицей 2x2. Решение игры с матрицей 3x3. | 2 |
5 | Решение игры 2xn. Пример антагонистической конкуренции. Вариант конечной игры. | 2 |
6 | Нахождение решения игры nxn с помощью компьютера. | 2 |
7 | Вычисление интегралов Римана – Стилтьеса. | 4 |
8 | Пример антагонистической конкуренции. Вариант бесконечной игры. | 2 |
9 | Биматричная игра как частный случай бескоалиционной игры. Примеры биматричных игр. Решение биматричных игр 2x2. | 2 |
Итого | 18 |
6. Виды самостоятельной работы студентов и их состав
Самостоятельная работа студентов направлена на закрепление теоретических навыков, правильное оформление результатов практических работ, на работу с учебно-методической литературой.
Формы самостоятельной работы:
1. Проработка лекционного материала.
2. Выполнение самостоятельных домашних заданий.
3. Подготовка к экзамену.
7. Формы текущего контроля знаний
Текущий контроль осуществляется в форме проверки самостоятельных домашних заданий и собеседования преподавателя со студентом по соответствующей теме.
Основные формы контроля:
- сдача самостоятельных домашних заданий,
- опрос на занятиях по предыдущим темам.
8. Вопросы к экзамену
1. Лемма о связи между sup inf и inf sup.
2. Лемма о том, что <<чистая>> ситуация равновесия образуется максиминной и минимаксной стратегиями.
3. Лемма о существовании максиминной стратегии.
4. Лемма о разделяющей гиперплоскости.
5. Лемма о двух альтернативах.
6. Теорема о минимаксе.
7. Теорема о том, что множество оптимальных стратегий игрока I совпадает с множеством максиминных стратегий.
8. Теорема об экстремальном смысле значения матричной игры (теорема 1.4).
9. Теорема о свойстве спектра оптимальной стратегии (теорема 1.6).
10. Теорема о форме решения игры, у которой матрица выигрышей игрока~I является линейной функцией другой матрицы (теорема 1.11).
11. Сведение решения матричной игры к решению задачи линейного программирования.
12. Пример бесконечной игры, когда значение игры не существует (пример 2.2).
13. Пример бесконечной игры, в котором <<нижнее значение больше верхнего>> (пример 2.3).
14. Теорема о свойстве спектра оптимальной стратегии в бесконечной игре (теорема 2.7).
15. Биматричные игры. Определение ситуации равновесия. Определение приемлемых ситуаций.
16. Теорема об условии, при котором чистая стратегия не входит в спектр смешанной стратегии (теорема 3.3).
17. Найти ситуацию равновесия биматричной игры с матрицей 2x2.
9. Примерный календарный план дисциплины
№недели | Кол. час | Тема и содержание лекций | ТСО | Кол. час | Тема и содержание практических, лабораторных и индивидуальных занятий | Файл | ТСО | Контроль качества усвоения материала |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 | |
1. | 1 | Определение конечной антагонистической игры. Нижнее и верхнее значения игры. | 1 | Примеры решения конечных антагонистических игр в чистых стратегиях (I). | ||||
2. | 1 | Ситуация равновесия. Максиминная и минимаксная чистые стратегии. | 1 | Примеры решения конечных антагонистических игр в чистых стратегиях (II). | 1 | |||
3. | 1 | Введение в линейное программирование. Формулировка теоремы о существовании оптимального решения. | 1 | Выпуклые множества. Выпуклая линейная оболочка. Гиперплоскость, полупространство, угловые точки. Задачи о выпуклых множествах. | ||||
4. | 2 | Смешанное расширение матричной игры. Лемма о существовании максиминной стратегии. | ||||||
5. | 2 | Симплекс-метод для решения задач линейного программирования | ||||||
6. | 2 | Теорема о минимаксе (I). | ||||||
7. | 2 | Решение игры с матрицей 2x2. Решение игры с матрицей 3x3. | 1 | |||||
8. | 2 | Теорема о минимаксе (II). Следствия. | 2 | |||||
9. | 2 | Решение игры 2xn. | ||||||
10. | 2 | Теорема о значении матричной игры как экстремальном значении некоторого множества вещественных чисел. Теорема о свойстве спектра оптимальной стратегии. | ||||||
11. | 1 | Теоремы о подыгре. | 1 | Пример антагонистической конкуренции. Вариант конечной игры. | ||||
12. | 1 | Одна модель антагонистической конкуренции. Вариант конечной игры. | 1 | Нахождение решения игры nxn с помощью компьютера | ||||
13. | 1 | Сведение задачи матричной игры к задачам линейного программирования. | 1 | . Вычисление интегралов Римана – Стилтьеса. | ||||
14. | 2 | Бесконечные антагонистические игры. Проблемы, возникающие в связи с бесконечными множествами чистых стратегий. Формулировка теоремы о существовании значения игры. Спектр. Теорема о свойстве спектра оптимальной стратегии. | ||||||
15. | 2 | Бескоалиционные игры. Определение среднего выигрыша каждого игрока. | ||||||
| ||||||||
16. | 2 | Пример антагонистической конкуренции. Вариант бесконечной игры. | ||||||
17. | 2 | Биматричная игра как частный случай бескоалиционной игры. Примеры биматричных игр | 2. | |||||
18. | 2 | Решение биматричных игр 2x2. |
Выполнение графика самостоятельной работы. | ||||||||||||||||||||||
Наименование вида работы (подготовка к аудиторным занятиям, РГР, КП, КР и т. д.) | Часы самост. работы | Срок выдачи | Срок сдачи | Рейтинговые баллы по неделям и видам работ | Рейтинг по виду работ | |||||||||||||||||
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | |||||
Подготовка к ДЗ.1 | 6 | 2 | 7 | 6 | 6 | 2 | 6 | 20 | ||||||||||||||
Подготовка к ДЗ.2 | 6 | 8 | 17 | 6 | 6 | 18 | 40 | |||||||||||||||
Экзамен | 8 | 40 | ||||||||||||||||||||
Рейтинг за неделю | 6 | 6 | 2 | 12 | 6 | 18 | 5 | 5 | 10 | 100 | ||||||||||||
Рейтинг с нарастанием | 6 | 12 | 14 | 26 | 32 | 50 | 55 | 60 | 70 | 100 |
10. Перечень обязательной литературы
* Чеботарев теории игр. Учебное пособие / ,
– Хабаровск, ДВГУПС, 2005.
11. Перечень дополнительной литературы
Боровков, вероятностей / . - М.: Наука, 1986. Березанский, анализ / , Г. Ф. Ус,. - Киев.: Выща школа, 1990.
3. Воробьев, игр: лекции для экономистов-кибернетиков /
. - Л.: ЛГУ, 1974.
4. Джафаров, теории игр / , . - Новосибирск, 1998.
5. Дюбин, в прикладную теорию игр / , . - М.:
Наука, 1981.
6. Колмогоров, теории функций и функционального анализа /
, . - М.: Наука, 1968.
7. Косоруков, операций / , . - М.:
Экзамен, 2003.
8. Курош, высшей алгебры / . - М.: Наука, 1960.
9. Математическая энциклопедия: В 5 т. Т. 3 / Гл. ред. . - М.:
Советская энциклопедия, 1982.
10. Мулен, Э. Теория игр с примерами из математической экономики / Э. Мулен. –
М.: Мир, 1985.
11. Нейман, Дж. фон. Теория игр и экономическое поведение / Дж. фон Нейман,
О. Моргенштерн. - М.: Наука, 1970.
12. Оуэн, Г. Теория игр / Г. Оуэн. - М.: Мир, 1971.
13. Партхасаратхи, Т. Некоторые вопросы теории игр двух лиц / Т. Партхасаратхи,
Т. Рагхаван. - М.: Мир, 1974.
14. Рудин, У. Функциональный анализ / У. Рудин. - М.: Мир, 1975.
15. Солодовников, в экономике: В 2 ч. Ч. I / ,
, . - М.: Финансы и статистика, 2001.
16. Фихтенгольц, дифференциального и интегрального исчисления:
В 3 т. Т. I / .- М.: Физматлит, СПб.: Невский диалект, 2001.
17. Фихтенгольц, дифференциального и интегрального исчисления:
В 3 т. Т. III / .- М.: Физматлит, СПб.: Невский диалект, 2001.
18. Шварц, Л. Анализ: В 2 т. Т. 1 / Л. Шварц. - М.: Мир, 1972.
12. Перечень наглядных и других пособий
Электронная версия учебного пособия:
Чеботарев теории игр. Учебное пособие / ,
13. Технологическая карта изучения дисциплины
Направление 010500 – Прикладная математика и информатика Специальность – Прикладная математика и информатика Семестр 4 | Трудоемкость дисциплины _6_ зач. ед. Число часов в семестре _36_ Число часов в неделе _2_ лекций _9_ практических (семинарских) занятий _9_ самостоятельной работы _20ч_ Форма отчетности _ДЗ, опрос, экзамен |
