Министерство образования и науки Российской Федерации
Федеральное агентство по образованию
Государственное образовательное учреждение
высшего профессионального образования
«Комсомольский-на-Амуре государственный технический университет»
Кафедра «Прикладная математика и информатика»
УТВЕРЖДАЮ
Первый проректор ГОУВПО «КнАГТУ»
____________________
А.Р. Куделько
«____» __________________ 2008 года
РАБОЧАЯ ПРОГРАММА
дисциплины «Теория игр и исследование операций» основной образовательной
программы подготовки дипломированных бакалавров по направлению 010500.62
– «Прикладная математика и информатика»
Форма обучения
очная
Технология обучения
традиционная
Объем дисциплины
72 часа; 2 зачетные единицы
Комсомольск-на-Амуре 2008
2
Рабочая программа обсуждена и одобрена на заседании кафедры «Прикладная математика и информатика»
Заведующий кафедрой
д.т.н., профессор
_______________ В.И. Одиноков
«____» ______________ 2008 года
СОГЛАСОВАНО:
Начальник учебно-методического
управления к.т.н., профессор
_______________ А.А. Скрипилев
«____» ______________ 2008 года
Декан факультета компьютерных
технологий к.т.н., профессор
_______________ В.П. Котляров
«____» ______________ 2008 года
Рабочая программа рассмотрена, одобрена и рекомендована к использованию методической комиссией факультета компьютерных технологий
Председатель методической
комиссии к.т.н., профессор
_______________ В.П. Котляров
«____» ______________ 2008 года
Автор рабочей программы
к.ф.-м.н., ст. преподаватель
______________ А.Ю. Лошманов
«____» ______________ 2008 года
3
ВВЕДЕНИЕ
Рабочая программа разработана на основании требований Государственного
Образовательного Стандарта для специальности 010501 – «Прикладная математика и информатика».
Данная рабочая программа по дисциплине «Теория игр и исследование операций» является базовым и руководящим документом для студентов указанной
специальности и преподавателей, которые ведут занятия по данной дисциплине.
Рабочая программа предназначена для четкой ориентации и представления, чем
конкретно предстоит заниматься при изучении и освоении данной дисциплины.
Содержание программы охватывает основные положения дисциплины. Основными требованиями преподавания дисциплины является формирование у будущих
специалистов представления о методах теории игр, их использовании в учебной и
профессиональной деятельности, обучение работе со специальной литературой.
Теорию игр обычно определяют как раздел математики для изучения конфликтных ситуаций. В наше время теория игр все шире проникает в практику
экономических решений и исследований, так как именно там часто возникает
необходимость согласования действий фирм, объединений, министерств и других
участников проекта в случаях, когда их интересы не совпадают.
Таким образом, методы теории игр позволяют вырабатывать оптимальные
правила поведения каждой стороны, участвующей в нахождении решения в конфликтной ситуации.
1
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
1.1 Требования государственного образовательного стандарта
Принятие решений, элементы теории игр, линейные модели; сетевые модели; вероятностные модели, имитационное моделирование.
1.2 Предмет, цели, задачи и принципы построения дисциплины
Цель. Дисциплина «Теория игр и исследование операций» способствует
пониманию основ теории игр и принятия решений в условиях неопределенности и
риска, развитию интереса к дальнейшему изучению этой важной области математики.
Задачи. Основные задачи дисциплины:
- помочь студентам усвоить основы теории игр: основные виды игр и их
применение для решения задач, а также для объяснения различных ситуаций;
- развить умение использовать основные методы решения матричных, бескоалиционных, позиционных и других игр;
- развить умение постановки и составления игровых моделей и решения задач.
При изучении дисциплины необходимо усвоить:
4
- понятия чистой стратегии, сме- шанной стратегии, цены игры;
- принцип доминирования
- аффинные преобразования для уменьшения размерности матрицы игры;
- графический метод;
- связь матричных игр с линейным программированием;
- симплекс-метод;
- графический метод для игр порядка 2*2;
- итерационный метод Брауна для решения матричных игр;
- метод Шепли-Сноу для определения полного множества решений игры;
- теория статистических игр (игр с природой);
- критерии для поиска оптимальных решений: максминный критерий Вальда, максимаксный, пессимизма-оптимизма, Сэвиджа, Лапласа.
Принципы построения дисциплины.
Главным принципом является доступность изучаемого материала. Студенту
предлагается большое количество примеров. Сначала изучается относительно
легкие темы, а затем, опираясь на изученный материал и полученный опыт, осуществляется переход к сложным темам.
Второй принцип – тесная взаимосвязь лекционных занятий и РГЗ. Последовательность изложения и объем теоретического материала, излагаемый на лекциях, согласованы с темами РГЗ и графиком их выполнения.
Третий принцип – рейтинговая система для дневных студентов. Предлагаются дополнительные задания, повышающие в итоге итоговую оценку.
1.3 Роль и место дисциплины в структуре реализуемой
образовательной программы
Теорию игр обычно определяют как раздел математики для изучения конфликтных ситуаций. Методы теории игр позволяют вырабатывать оптимальные
правила поведения сторон, участвующих в нахождении решения в конфликтной
ситуации. Таким образом, для успешного изучения дисциплины «Теория игр и
исследование операций» необходимо иметь хорошие знания по дисциплине «Алгебра и геометрия» (матрицы и действия над ними, решение систем линейных
уравнений), «Теория вероятностей и математическая статистика», «Математическое моделирование».
Знания, умения и навыки, полученные студентом в ходе обучения по курсу
«Теория игр и исследование операций», необходимы для изучения дисциплин
«Экономико-математические методы», «Математическое обеспечение фондового
рынка».
5
1.4 Объемы учебной работы и предусмотренные рабочими учебными
планами реализуемых образовательных программ формы
аттестации ее результатов
Таблица 1 – Характеристика трудоемкости дисциплины
Виды учебной работы
Семестр
Объемы учебной работы (в семестре/в
неделю), ч.
Аудиторные
СамостояВсего
занятия
тельная работа
1
1. Предусмотренный
рабочим
учебным
планом объем изучения дисциплины в
учебных семестрах:
-всего:
-в т.ч. по семестрам
2. По видам аудиторных занятий:
-лекции
-практические занятия
3. Аттестация по
дисциплине:
-экзамен
4. Итого объем дисциплины по семестрам (записи в зачетную книжку):
-экзамен
5. Итого трудоемкость дисциплины
2
3
4
5
Объемы
учебной работы в кредитах (зачетных единицах)
6
9
34/2
34/2
38/2
38/2
72/4
72/4
2
2
9
17/1
-
17/1
0,5
9
17/1
-
17/1
0,5
9
-
-
36
1
9
-
-
72
2
-
-
-
108
3
6
2
СТРУКТУРА ДИСЦИПЛИНЫ
Таблица 2 – Модули курса
Наименование
Основные понятия. Принцип доминирования
Описание раздела
Понятие чистой стратегии, смешанной
стратегии. Цена игры. Принцип доминирования, аффинные преобразования для
уменьшения размерности матрицы игры.
Графический метод. Связь матричных игр с
линейным программированием, симплексметод
Связь матричных игр с линейным Графический метод для игр порядка 2*2.
программированием
Связь матричных игр с линейным программированием, симплекс-метод
Методы решения матричных игр Итерационный метод Брауна для решения
матричных игр. Метод Шепли-Сноу для
определения полного множества решений
игры
Критерии поиска оптимальных Теория статистических игр (игр с прирорешений
дой). Критерии для поиска оптимальных
решений: максминный критерий Вальда,
максимаксный,
пессимизма-оптимизма,
Сэвиджа, Лапласа
Игры с природой (статистические Основные особенности игр с природой.
игры или принятие решений в
Критерии выбора оптимальной стратегии в
условиях неопределенности и
играх с природой . Примеры решения игр с
риска)
природой
Принятие решений в условиях
Принцип максимальной эффективности.
полной определенности
Принцип минимальной потери. Примеры
решения многокритериальной задачи с помощью метода аддитивной оптимизации
Позиционные игры
Безусловный денежный эквивалент и ожидаемая денежная оценка в позиционных играх
Игры с ненулевой суммой. БиБиматричные игры. Точка равновесия
матричные игры
Кооперативные игры. ПаретоПрименение аппарата теории кооперативоптимальное множество. Решение ных игр для анализа проблем микроэконоНэша
мики. Ящик Эджворта. Множество Паретооптимальных распределений
Функция полезности Неймана- Основные понятия. Аксиомы . Измерение
Моргенштерна
отношения к риску. Страхование от риска
7
3
КАЛЕНДАРНЫЙ ГРАФИК ИЗУЧЕНИЯ ДИСЦИПЛИНЫ
3.1 Наименование тем, их содержание, объем в часах лекционных
занятий
Таблица 3 – Наименование тем и содержание
Номер, наименование темы и содержание
1. Основные положения математической теории игр. Фундаментальные понятия. Классификация игр. Примеры игровых ситуаций разного типа.
Принципы решения матричных игр. Чистые стратегии
игроков. Верхняя, нижняя цена игры.
Седловая точка. Принцип
доминирования. Понятие смешанной стратегии
2. Методы решения матричных игр.
Графический метод решения матричных игр. Графический метод для игр порядка 2 2 . Графический метод решения матричных игр порядка 2 n . Графический
метод решения матричных игр порядка m 2 . Решение матричных
игр методами линейного программирования. Итерационный метод
Брауна. Метод Шепли - Сноу для решения матричных игр
3. Игры с природой (статистические игры или принятие решений в
условиях неопределённости и риска). Основные особенности игр с
природой. Критерии выбора оптимальной стратегии в играх с природой. Примеры решения игр с природой
4. Принятие решений в условиях полной определенности. Принцип
максимальной эффективности. Принцип минимальной потери. Примеры решения многокритериальной задачи помощью метода аддитивной оптимизации
5. Позиционные игры. Безусловный денежный эквивалент и ожидаемая денежная оценка в позиционных играх
6. Игры с ненулевой суммой. Биматричные игры. Точка равновесия
7. Кооперативные игры. Парето-оптимальное множество. Решение
Нэша. Применение аппарата теории кооперативных игр для анализа
проблем микроэкономики. Ящик Эджворта. Множество Паретооптимальных распределений
8. Функция полезности Нэймана-Моргенштерна. Основные понятия.
Аксиомы. Измерение отношения к риску . Страхование от риска
9. Обобщающее занятие.
Итого по дисциплине в целом лекций
Объем,
ч
2
2
2
2
2
2
2
2
1
17
8
3.2 Наименование тем, содержание, объем в часах практических
занятий
Таблица 4 – Наименование тем и содержание практических занятий
Номер, наименование темы и содержание
Объем,
ч
1. Основные положения математической теории игр. Примеры игровых ситуаций разного типа. Принципы решения матричных игр. Чистые стратегии игроков. Верхняя, нижняя цена игры
2
2. Седловая точка. Принцип доминирования. Понятие смешанной
стратегии. Графический метод решения матричных игр. Графический
метод для игр порядка 2 2
2
3. Графический метод решения матричных игр порядка 2 n . Графический метод решения матричных игр порядка m 2 . Решение матричных игр методами линейного программирования
4. Итерационный метод Брауна. Метод Шепли - Сноу для решения
матричных игр
5. Критерии выбора оптимальной стратегии в играх с природой.
Примеры решения игр с природой. Принцип максимальной эффективности. Принцип минимальной потери
6. Позиционные игры. Игры с ненулевой суммой
7. Биматричные игры. Точка равновесия. Кооперативные игры. Парето-оптимальное множество
8. Решение Нэша. Применение аппарата теории кооперативных игр
для анализа проблем микроэкономики. Функция полезности Нэймана-Моргенштерна
9. Обобщающее занятие. Контрольная работа
Итого по дисциплине практических занятий
2
2
2
2
2
2
1
17
9
3.3 Объем, структура и содержание самостоятельной работы студентов,
график ее выполнения
3.3.1 Примерный перечень теоретических разделов курса для
самостоятельного изучения
1. Методы оптимизации управляющих решений. Рациональное ведение хозяйства. Теория личного потребления. Модели фирмы. Спрос и предложение.
Теория общего равновесия. Оптимальный экономический рост. Оптимизация в
условиях неопределенности.
3. Практическое использование методов теории игр. Декомпозиция и сокращение размерности больших моделей. Экономико-математический анализ оптимальных решений. Имитационное моделирование на ЭВМ.
3.3.2 Примерные требования к оформлению и сдаче отчетов по
расчетно-графическим заданиям
По каждому расчетно-графическому заданию должен быть составлен отчет
в виде документа MS Word, содержащий следующие разделы:
титульный лист;
задание;
теоретический материал, содержащий описание методики выполнения
расчетно-графического задания
решение задач;
список использованной литературы.
Отчет должен быть оформлен в соответствии с правилами оформления студенческих текстовых работ, изложенных в РД ГОУВПО «КнАГТУ» 013-2005
«Текстовые студенческие работы. Правила оформления».
3.3.3 Наименование тем и содержание расчетно-графических заданий
Таблица 5 – Наименование тем и содержание РГЗ
Номер, наименование темы и содержание
Графический метод решения матричных игр. Графический метод
для игр порядка 2 2 . Графический метод решения матричных игр
порядка 2 n . Графический метод решения матричных игр порядка
m 2 . Решение матричных игр методами линейного программирования. Итерационный метод Брауна. Метод Шепли - Сноу для решения матричных игр
Итого по дисциплине в семестре
График самостоятельной работы представлен в таблице:
Объем,
ч
10,8
10,8
Таблица 6 – График самостоятельной работы студентов в 17-недельном семестре
Вид самостоятельной работы
1
2
3
4
5
6
Число часов в неделю
7
8
9
10 11
Подготовка к лекциям
Подготовка к практическим занятиям
Подготовка к контрольным мероприятиям
Изучение теоретических разделов дисциплины
Выполнение РГЗ
-
0,2
0,2
0,2
0,2
0,2
0,2
0,2
0,2
0,2
0,2
0,2
0,2
0,2
0,2
0,2
0,2
Итого по
видам
работы
3,2
-
0,5
-
0,5
-
0,5
-
0,5
-
0,5
-
0,5
-
0,5
-
0,5
-
0,5
-
0,5
-
0,5
-
0,5
-
0,5
-
0,5
КР
0,5
1
0,5
1
8
2
-
1
РГЗ
1
0,8
1
0,8
1
0,8
1
0,8
1
0,8
1
0,8
1
0,8
1
0,8
1
0,8
1
0,8
1
0,8
1
0,8
1
0,8
-
-
14
10,8
Итого
-
1,7
2,5
2,5
2,5
2,5
2,5
2,5
2,5
2,5
2,5
2,5
2,5
2,5
2,5
1,7
1,7
38
12
13
14
15
16
17
4
ТЕХНОЛОГИИ И МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ
КОНТРОЛЯ РЕЗУЛЬТАТОВ УЧЕБНОЙ ДЕЯТЕЛЬНОСТИ
ОБУЧАЕМЫХ
Текущий контроль учебной деятельности студентов осуществляется на
практических занятиях, при сдаче расчетно-графических заданий, при контрольной работе. Студент обязан в срок выполнить выданное ему расчетнографическое задание (их темы приведены в таблице 5). Во время практических
занятий студент выполняет одну контрольную работу (сроки см. в таблице 6).
Студент, не выполнивший к концу изучения дисциплины расчетнографическое задание, не допускается до экзамена. Экзамен проводится в письменной форме, время проведения экзамена – 2 академических часа. На экзамен
каждому студенту предлагается два задания (1 билет). Все задачи в экзаменационном билете аналогичны задачам, разбираемым в учебном процессе (во время
лекций и практических занятий).
Список вопросов на экзамен
1. Классификация игр.
2. Чистые стратегии игроков. Верхняя, нижняя цена игры. Седловая точка.
3. Принцип доминирования.
4. Смешанные стратегии игроков.
5. Графический метод решения матричных игр порядка 2 2 .
6. Графический метод решения матричных игр порядка 2 n .
7. Графический метод решения матричных игр порядка m 2 .
8. Решение матричных игр методами линейного программирования.
9. Итерационный метод Брауна.
10. Метод Шепли-Сноу для получения полного решения матричной игры.
11. Игры с природой, основные отличия.
12. Критерии для выбора оптимальной стратегии в играх с природой.
13. Принятие решений в условиях полной определенности в случае однородности и неоднородности критериев.
14. Принципы максимальной эффективности и минимальной потери при
принятии решений в условиях полной определенности.
15. Позиционные игры. Безусловный денежный эквивалент и ожидаемая денежная оценка.
16. Биматричные игры. Ситуация равновесия.
17. Кооперативные игры. Парето-оптимальное множество. Решение Нэша.
18. Ящик Эджворта. Множество Парето-оптимальных распределений.
19. Функция полезности Неймана-Моргенштерна. Основные понятия и аксиомы.
20. Измерение отношения к риску.
21. Страхование от риска.
12
5
РЕСУРСНОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ
5.1 Список основной учебной дисциплины
1. Каверзина С.А. Теория игр: Учеб. пособие – Комсомольск-на-Амуре: Государственное образовательное учреждение высшего профессионального образования
«Комсомольский-на-Амуре государственный технический университет», 2002. –
94 с.
2. Бережная Е.В. Математические методы моделирования экономических систем /
Е.В. Бережная, В.И. Бережной. – М.: Финансы и статистика, 2001. – 368 с.
3. Воробьев Н.Н. Теория игр для экономистов-кибернетиков. М.: Наука, 1985. –
271 с.
4. Конюховский П.В. Математические методы исследования операций в экономике. СПб.: Питер, 2000. – 364 с.
5. Шикин Е.В. Математические методы и модели в управлении / Е.В. Шикин, А.Г.
Чхарташвили. - М.: Дело, 2000. – 439 с.
5.2 Список дополнительной учебной литературы
1. Карманов В.Г. Математическое программирование. – М.: Наука, 1975.
2. Вентцель Е.С. Исследование операций. – М.: Сов. радио, 1972.
3. Зайченко Ю.П. Исследование операций. – Киев: Вища школа, 1979.
4. Исследование операций / Под ред. Дж. Моудера, С. Элмаграби. – М.: Мир,
1981.
5. Саати Т. Целочисленные методы оптимизации и связанные с ними экстремальные проблем. – М.: Мир, 1973.
6. Филькенштейн Ю.Ю. Приближенные методы и прикладные задачи дискретного
программирования. – М.: Наука, 1976.
7. Юдин Ю.Д., Гольштейн Е.Г. Задачи и методы линейного программирования. –
М.: Сов. радио, 1964.
8. International Society of Dynamic Games – www.isdgrus.ru.
9. Данилов В.И. Лекции по теории игр (http://www.nes.ru/russian/research/abstracts)
