Программа дисциплины «Теория игр и исследование операций»



жүктеу 234.38 Kb.
Дата07.05.2019
өлшемі234.38 Kb.
түріПрограмма дисциплины



Национальный исследовательский университет «Высшая школа экономики»
Программа дисциплины «Теория игр и исследование операций»

для направления 080500.62 «Бизнес-информатика» подготовки бакалавра







Правительство Российской Федерации
Федеральное государственное автономное образовательное учреждение
высшего профессионального образования


Национальный исследовательский университет
"Высшая школа экономики"


Факультет Бизнес-информатики

4

Программа дисциплины


ТЕОРИЯ ИГР

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




для направления 080500.62 «Бизнес-информатика»

подготовки бакалавра

Автор программы: к.ф.-м.н. Молоствов В.С.

Одобрена на заседании кафедры высшей математики на факультете экономики

Зав. кафедрой Алескеров Ф.Т.


Рекомендована секцией УМС «___»____________ 20 г

Председатель


Утверждена Ученым Советом факультета экономики «___»_____________20 г.

Ученый секретарь


Москва, 2012

Настоящая программа не может быть использована другими подразделениями университета и другими вузами без разрешения кафедры-разработчика программы.

1Область применения и нормативные ссылки


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

Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 080500.62 «Бизнес-информатика» подготовки бакалавра, изучающих дисциплину «Теория игр и исследование операций».



Программа разработана в соответствии с:

  • Образовательным стандартом государственного образовательного бюджетного учреждения высшего профессионального образования «Государственный университет – Высшая школа экономики», в отношении которого установлена категория «Национальный исследовательский университет»;

  • Образовательной программой 080500.62, направление «Бизнес-информатика» подготовки бакалавра;

  • Рабочим учебным планом университета по направлению 080500.62 «Бизнес-информатика» подготовки бакалавра, утвержденным в 2012г.


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


Целями освоения дисциплины «Теория игр и исследование операций» являются:

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

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

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

  • овладение техникой нахождения решений, обладающих свойствами эффективности и устойчивости.



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


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

  • Знать основные математические методы анализа решений.

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

  • Владеть навыками применения современного инструментария дисциплины.



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


Компетенция

Код по ФГОС/ НИУ

Дескрипторы – основные признаки освоения (показатели достижения результата)

Формы и методы обучения, способствующие формированию и развитию компетенции

Общенаучная

ОНК-1

Способность к анализу и синтезу на основе системного подхода

Стандартные (лекционно-семинарские)

Общенаучная

ОНК-2

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

Стандартные (лекционно-семинарские)

Общенаучная

ОНК-3

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

Стандартные (лекционно-семинарские)

Общенаучная

ОНК-4

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

Стандартные (лекционно-семинарские)

Общенаучная

ОНК-5

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

Стандартные (лекционно-семинарские)

Общенаучная

ОНК-6

Способность приобретать новые знания с использованием научной методологии и современных образовательных и информационных технологий

Стандартные (лекционно-семинарские)

Общенаучная

ОНК-7

Способность порождать новые идеи (креативность)

Стандартные (лекционно-семинарские)

Инструментальные

ИК-2

Умение работать на компьютере, навыки использования основных классов прикладного программного обеспечения, работы в компьютерных сетях, составления баз данных

Стандартные (лекционно-семинарские)

Профессиональные

ПК-1

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

Стандартные (лекционно-семинарские)

Профессиональные

ПК-2

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

Стандартные (лекционно-семинарские)

Профессиональные

ПК-4

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

Стандартные (лекционно-семинарские)

ПрофессиональныеСтандартные (лекционно-семинарские)

ПК-8

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

Стандартные (лекционно-семинарские)

4Место дисциплины в структуре образовательной программы


Настоящая дисциплина относится к циклу математических и естественнонаучных дисциплин, является базовой для студентов 3-го курса (2-й и 3-й модули учебного плана подготовки бакалавра по направлению 080500.62 «Бизнес-информатика».

Изучение данной дисциплины базируется на следующих дисциплинах:


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



  • знание элементарной математики

  • умение решать системы линейных и нелинейных уравнений

  • знание дифференциального исчисления

  • владение базовым аппаратом теории вероятностей

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



  • Макроэкономика,

  • Микроэкономика,

  • Теория отраслевых рынков,

  • Экономика общественного сектора,

  • Институционная экономика,

  • Эконометрика,

  • Макроэкономическое планирование и прогнозирование.

  • Фондовый рынок и финансовый менеджмент.

5Тематический план учебной дисциплины






Наименование темы


Всего часов

Аудиторные часы

Самостоятельная работа

Лекции

Семинары

Практические занятия




Третий модуль

1

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

12

2

2




8

2

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

32

6

6




20

3

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

12

2

2




8

4

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

32

6

6




20

Всего

88

16

16




56




Четвертый модуль

5

Введение в теорию игр, классификация, примеры

10

2

2




6

6

Антагонистические игры.

32

6

6




20

7

Неантагонистические бескоалиционные игры

32

6

6




20

8

Методы решения игр с конечным числом стратегий

18

4

4




10

Всего

92

18

18




56

Итого

180

34

34




112


6Формы контроля знаний студентов


Тип контроля

Форма контроля

2 год

Параметры

3

4

Текущий


(неделя)

Контрольная работа

*




Письменная работа 70 минут



Контрольная работа




*

Письменная работа 70 минут

Итоговый

Зачет







Письменная работа 90 мин.



6.1Критерии оценки знаний, навыков


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

Оценки по всем формам текущего контроля выставляются по 10-ти балльной шкале.




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


Тема 1. Введение. Примеры задач и математическая модель исследования операций. Игровые модели как инструмент исследования операций в конфликтных ситуациях.

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

Классификация моделей по объекту исследования, уровню агрегирования, применяемому математическому аппарату. Система задач математического программирования.

Вопросы применения средств вычислительной техники.



Литература:

Базовый учебник: [1] (тема 1), [3] (введение, гл.1).

Основная литература: [9] (гл.1-2).

Дополнительная литература:, [12], [20] (гл.1), [13] (гл.1-3).



Тема 2. Линейные оптимизационные модели в исследовании операций
Задачи линейного программирования (ЛП), их особенности, место и роль в системе оптимизационных математических моделей. Примеры: задачи об оптимальном использовании ресурсов, о диете, о смесях, транспортные и другие задачи. Графический метод решения задачи ЛП.

Общая постановка и различные формы задачи ЛП. Геометрия задач ЛП. Выпуклые множества. Выпуклые оболочки. Вершины многогранного множества. Экстремумы линейной функции на многограннике и многогранном множестве. Алгебра задач ЛП. Базисные и допустимые базисные решения. Связь вершин многогранника допустимых решений и базисных решений. Понятие о симплекс-методе решения задач ЛП.

Теория двойственности в ЛП. Взаимно двойственные задачи. Теоремы двойственности. Содержательная интерпретация двойственных переменных. Анализ чувствительности оптимального решения к изменениям параметров задачи.

Литература:

Базовый учебник: [3] (гл. 1-7).

Основная литература: [5] (гл. 1), [8]

Дополнительная литература: [15].


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

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

Компьютерные системы линейного программирования.

Литература:

Базовый учебник:[3] (гл. 8).

Основная литература: [11] (гл. 3, 4).

Дополнительная литература: [17]


Тема 4. Нелинейные оптимизационные модели в исследовании операций
Принятие решений в условиях определенности; детерминированная статическая задача оптимизации. Математическое программирование – аппарат решения оптимизационных задач. Классификации задач математического программирования. Содержательные примеры.

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

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

Общая задача нелинейного программирования. Функция Лагранжа. Условия локального экстремума в задаче оптимизации на неотрицательном ортанте. Теорема Куна-Таккера в «седловой» и дифференциальной форме. Условие Слейтера и его существенность. Условия дополняющей нежесткости.

Понятие о численных методах решения задач нелинейного программирования. Классификация методов. Безусловная оптимизация: градиентные методы и методы второго порядка. Условная оптимизация, метод штрафных функций.

Компьютерные системы для решения задач нелинейного программирования.



Литература:

Базовый учебник: [1] (темы 3,4), [3] (гл. 10-11,13) .

Основная литература: [7], [11] (гл. 5 ).

Дополнительная литература: [17] (гл. 3 ).


Тема 5. Введение в теорию игр: классификация, примеры
Игра как модель конфликтной ситуации. Содержательные примеры игр. Формализация игры: участники игры, стратегии, ситуации, исходы, функции выигрыша. Предположения об информированности игроков. Классификация игр по различным признакам: по множествам стратегий (конечные или бесконечные), по структуре целей (антагонистические или неантагонистические игры), по информации и поведению (кооперативные и некооперативные игры, и др.), по наличию динамики (статические, многошаговые, дифференциальные). Игры в нормальной и развернутой форме.

Литература:

Базовый учебник: [4] (введение).

Дополнительная литература: [22] (гл.1).



Тема 6. Антагонистические игры

Игры двух участников с противоположными интересами. Доминирующие, доминируемые и недоминируемые стратегии. Принцип наилучшего гарантированного результата. Гарантирующие минимаксная и максиминная стратегии игроков. Нижнее и верхнее значения игры. Ситуация равновесия (седловая точка), оптимальные стратегии. Значение (цена) игры. Необходимое и достаточное условие существования ситуации равновесия. Принятие управленческих решений в условиях неопределенности как антагонистическая «игра с природой». Пример – задача планирования производства при неопределенности спроса на рынке.

Литература:

Базовый учебник: [4] (гл.1).

Дополнительная литература: [22] (гл. 1, 2).

Тема 7. Неантагонистические бескоалиционные игры
Неантагонистические игры нескольких лиц. Ситуация равновесия по Нэшу. Сопоставление свойств седловых точек и точек Нэша (эквивалентность, взаимозаменяемость). Недостатки точек Нэша. Примеры «дилемма заключенного», «семейный спор». Парето-оптимальность ситуаций. Векторные седловые точки. Приложения в менеджменте и экономике.

Литература:

Базовый учебник: [4] (гл.3).

Дополнительная литература: [22] (гл.2).


Тема 8. Методы решения игр с конечным числом стратегий

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

Литература:

Базовый учебник: [4] (гл. 1, 3).

Дополнительная литература: [22] (гл. 1-3).

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


  • контрольная работа № 1: построение моделей по вербальному описанию задачи, линейное программирование, двойственность в ЛП, выпуклое программирование;

  • контрольная работа № 2: построение игровых моделей, методы вычисления равновесных стратегий

  • зачетная работа: по темам 5 – 8.


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

Одно из практических занятий по теме 2 «Линейные оптимизационные модели в исследовании операций» целесообразно провести в компьютерном классе.



Методические указания студентам

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


Рекомендации по использованию информационных технологий

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




8Оценочные средства для текущего контроля и аттестации студента

8.1Вопросы для оценки качества освоения дисциплины





  • Почему симплекс-метод находит точное решение задачи ЛП за КОНЕЧНОЕ число шагов?

  • Какова верхняя оценка максимального числа шагов до достижения решения?

  • Почему реальное число шагов гораздо меньше этой оценки?

  • Каковы две возможные причины отсутствия решений в задачах линейного программирования?

  • Может ли достигаться максимум или минимум линейной целевой функции во внутренней точке множества допустимых решений?

  • Может ли задача ЛП иметь ровно три оптимальных решения?

  • Может ли задача ЛП иметь ровно три оптимальных базисных решения?

  • Может ли оптимальное решение замкнутой транспортной задачи с целочисленными условиями (запасами и запросами) быть нецелочисленным?

  • Дайте определение выпуклого множества. Докажите, что пересечение двух выпуклых множеств выпукло.

  • Докажите «в лоб», исходя из определения выпуклости, что множество решений системы линейных неравенств Ax≤ выпукло.

  • То же для множества решений СЛУ Ax=b

  • Докажите, что локальный экстремум выпуклой функции на выпуклом множестве является и глобальным экстремумом.

  • Докажите, что строго выпуклая функция имеет на выпуклом множестве не более одной точки экстремума.

  • Может ли выпуклая функция иметь на выпуклом множестве ровно три точки максимума?

  • Может ли выпуклая функция иметь на выпуклом множестве ровно три точки минимума?

  • Справедливо ли утверждение: «выпуклая функция на выпуклом множестве имеет экстремум»?

  • Справедливо ли утверждение: «выпуклая функция на выпуклом множестве имеет не более одного экстремума»?

  • Сформулируйте двойственную задачу ЛП (для стандартной формы - с неравенствами). В каком случае двойственная задача совпадает с прямой задачей?

  • Докажите, что задача ЛП, двойственная к двойственной, совпадает с исходной (для канонической формы).

  • Сформулируйте 2-ю теорему двойственности в задаче ЛП (условия дополняющей нежесткости).

  • Как найти оптимальное решение прямой задачи линейного программирования, если найдено оптимальное решение ее двойственной задачи?

  • Сформулируйте необходимые и достаточные условия выпуклости и строгой выпуклости дважды дифференцируемой функции нескольких переменных (в терминах Гессиана).

  • Сформулируйте теорему Куна-Таккера для задачи выпуклого программирования в дифференциальной форме.

  • Сформулируйте достаточное условие существования глобального экстремума (теорема Вейерштрасса). Назовите возможные причины отсутствия оптимального решения, приведите примеры.

  • Чем вызвана необходимость разработки и применения численных методов?

  1. По каким признакам можно классифицировать игры?

  2. Приведите примеры игры в нормальной и развернутой форме.

  3. Что такое доминирующие, доминируемые и недоминируемые стратегии, строгое доминирование?

  4. Изложите на примере матричной игры принцип наилучшего гарантированного результата.

  5. Ситуация равновесия (седловая точка) в антагонистической игре, оптимальные стратегии. Значение (цена) игры.

  6. Связь седловых точек и гарантирующих стратегий. Свойства седловых точек в случае их неединственности.

  7. Необходимое и достаточное условие существования ситуации равновесия (равенство минимаксов).

  8. Принятие управленческих решений в условиях неопределенности как антагонистическая «игра с природой». Приведите пример.

  9. Критерии Вальда, Гурвица, Сэвиджа и Лапласа для принятия решений в условиях неопределенности.

  10. Дайте определение ситуации равновесия по Нэшу, поясните его содержательный смысл.

  11. Сопоставьте свойств седловых точек и точек Нэша (эквивалентность, взаимозаменяемость).

  12. Как соотносятся свойства эффективности (Парето-оптимальность), устойчивости и справедливости решений в неантагонистических играх (на примере игр («дилемма заключенного», «семейный спор»).

  13. Смешанное расширение матричной игры – что это и зачем понадобилось вводить?

  14. Что значит использовать смешанную стратегию (0.1, 0.1, 0.8)?

  15. Какие Вы знаете способы вычисления седловых точек в чистых стратегиях?

  16. Что гласит основная теорема матричных игр?

  17. Вычисление седловой точки в смешанных стратегиях специальным представлением функции выигрыша (аналитический метод).

  18. Вычисление седловой точки в смешанных стратегиях для игр 2хn и mх2 (графо-аналитический метод).

  19. Связь матричной игры с задачей линейного программирования.

  20. Биматричные игры. Примеры. Смешанное расширение биматричной игры.

  21. Поиск ситуаций равновесия (точек Нэша) в чистых стратегиях. Основная теорема матричных игр (существование решения в смешанных стратегиях).

  22. На чем основан метод наилучшего отклика для вычисления ситуаций равновесия в смешанных стратегиях для игр 2х2 (метод зигзагов).

  23. Что такое игры с иерархической структурой? Как найти оптимальные по Штакельбергу стратегии (на примере непрерывной игры – дуополия Штакельберга)?

  24. Приведите пример динамической игры с полной информацией, найдите ее решение методом обратной индукции.







9Порядок формирования оценок по дисциплине


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

- письменная аудиторная контрольная работа № 1 (второй модуль, 70 мин),

- письменная аудиторная контрольная работа № 2 (третий модуль, 70 мин),

- зачет (третий модуль, 90 мин).

Оценки за контрольные работы, домашнее задание, зачет ставятся в десятибалльной шкале с одним знаком после запятой.

Накопленная оценка учитывает результаты студента следующим образом: Онакопленная = 0,2•Оаудиторная + 0,4•Оконтр1+0,4•О контр2


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

Итоговая десятибалльная оценка успеваемости студента по дисциплине в целом определяется по формуле

Оитоговая = 0,5•Онакопленная + 0,5•Озачет.
Способ округления оценки за зачет и итоговой оценки текущего контроля производится по правилам арифметики округления.
Перевод итоговой десятибалльной оценки в пятибалльную осуществляется по общепринятому в НИУ ВШЭ правилу:

не больше 3 – неудовлетворительно, 4,5 – удовлетворительно, 6, 7 – хорошо, 8,9,10 – отлично.


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

10.1Базовые учебники


  1. А.В. Соколов, В.В. Токарев. Методы оптимальных решений. Т.1. Общие положения. Математическое программирование. Москва: ФИЗМАТЛИТ, 2010, 2011.

  2. В.В. Токарев. Методы оптимальных решений. Т.2. Многокритериальность. Динамика. Неопределенность. Москва: ФИЗМАТЛИТ, 2010, 2011

  3. Исследование операций в экономике. Под ред. Кремера Н.Ш. М.: Маркет ДС, 2007.

  4. Воробьев Н.Н. Теория игр для экономистов-кибернетиков. М.: Наука, 1985 (гл. 1,3).



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


  1. Ф.П. Васильев, А.Ю. Иваницкий. Линейное программирование. М. Факториал Пресс, 2008.

  2. Ф.П. Васильев. Методы оптимизации. М. Факториал Пресс, 2005.

  3. Ногин В.Д. Методы оптимальных решений. СПб, СПб филиал ГУ – ВШЭ, 2006.

  4. Гольштейн Е.Г., Юдин Д.Б. Задачи линейного программирования транспортного типа. М.: Наука, 1969.

  5. Вентцель Е.С. Исследование операций. Задачи, принципы, методология. М.: ВШ, 2001.

  6. Подиновский В.И., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М.: Физматлит, 2007.

  7. Курицкий Б.Я. Поиск оптимальных решений средствами Excel 7.0. СПб., BHV, 1997.

10.3Дополнительная литература


  1. Ларичев О.И. Теория и методы принятия решений. / Учебник. М.: Логос, 2002.

  2. Петров А.А., Поспелов И.Г., Шананин А.А. Опыт математического моделирования экономики. М., Энергоатомиздат, 1996.

  3. Л.В. Канторович, А.Б. Горстко. Математическое оптимальное программирование в экономике. М.: Знание, 1968.

  4. Дж. Данциг. Линейное программирование, его обобщения и применение. М.: Прогресс, 1966.

  5. Подиновский В.В. Введение в теорию важности критериев в многокритериальных задачах принятия решений. М.: Физматлит, 2007.

  6. Математические методы принятия решений в экономике. /Учебник. Под ред. Колемаева В.А. М.: Финстатинформ, 1999.

  7. Лотов А.В. Введение в экономико-математическое моделирование / Учебное пособие. М.: Наука, Физматлит, 1984.

  8. Хрестоматия по учебной дисциплине «Теория и методы принятия многокритериальных решений». Составитель В.В. Подиновский. М.: ГУ – ВШЭ, 2005.

  9. Хазанова Л.Э. Математические методы в экономике: Учебное пособие. – М.:,БЕК, 2002.

  10. Жуковский В.И., Молоствов В.С. Многокритериальное принятие решений в условиях неопределенности. М.: Международный НИИ проблем управления, 1988.

  11. Шагин В.Л. Теория игр. Учебное пособие. М.: ГУ ВШЭ, 2003 (гл. 1-3).

Автор программы В.С.Молоствов


© В.С.Молоствов



Достарыңызбен бөлісу:


©kzref.org 2019
әкімшілігінің қараңыз

    Басты бет