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


Правительство Российской Федерации
Федеральное государственное автономное образовательное учреждениевысшего профессионального образования
Национальный исследовательский университет"Высшая школа экономики"
Факультет Бизнес-информатики
Программа дисциплины
ТЕОРИЯ ИГР
И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
AUTOTEXT " Простая надпись"
для направления 080500.62 «Бизнес-информатика»
подготовки бакалавра
Автор программы: к.ф.-м.н. Молоствов В.С.
Одобрена на заседании кафедры высшей математики на факультете экономики 28.08.2014
Зав. кафедрой Алескеров Ф.Т.
Рекомендована секцией УМС «___»____________ 20 г
Председатель
Утверждена Ученым Советом факультета экономики «___»_____________20 г.
Ученый секретарь
Москва, 2014

Настоящая программа не может быть использована другими подразделениями университета и другими вузами без разрешения кафедры-разработчика программы.
Область применения и нормативные ссылки
Настоящая программа учебной дисциплины устанавливает минимальные требования к знаниям и умениям студента и определяет содержание и виды учебных занятий и отчетности.
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 080500.62 «Бизнес-информатика» подготовки бакалавра, изучающих дисциплину «Теория игр и исследование операций».
Программа разработана в соответствии с:
Образовательным стандартом государственного образовательного бюджетного учреждения высшего профессионального образования «Государственный университет – Высшая школа экономики», в отношении которого установлена категория «Национальный исследовательский университет»;
Образовательной программой 080500.62, направление «Бизнес-информатика» подготовки бакалавра;
Рабочим учебным планом университета по направлению 080500.62 «Бизнес-информатика» подготовки бакалавра.
Цели освоения дисциплины
Целями освоения дисциплины «Теория игр и исследование операций» являются:
знакомство с основными классами оптимизационных задач и моделей исследования операций,
введение в математическую проблематику принятия рациональных решений в конфликтных ситуациях
выработка навыков построения математических моделей для практических задач принятия решений в экономике и других областях
овладение техникой нахождения решений, обладающих свойствами эффективности и устойчивости.
Компетенции обучающегося, формируемые в результате освоения дисциплины
В результате освоения дисциплины студент должен:
Знать основные математические методы анализа решений.
Уметь выбирать рациональные варианты действий в практических задачах принятия решений в конфликтных ситуациях с использованием экономико-математических моделей, самостоятельно находить и использовать дополнительную информацию в данной предметной области,
Владеть навыками применения современного инструментария дисциплины.
В результате освоения дисциплины студент осваивает следующие компетенции:
Компетенция Код по ФГОС/ НИУ Дескрипторы – основные признаки освоения (показатели достижения результата) Формы и методы обучения, способствующие формированию и развитию компетенции
Общенаучная ОНК-1 Способность к анализу и синтезу на основе системного подхода Стандартные (лекционно-семинарские)
Общенаучная ОНК-2 Способность перейти от проблемной ситуации к проблемам, задачам и лежащим в их основе противоречиям Стандартные (лекционно-семинарские)
Общенаучная ОНК-3 Способность использовать методы критического анализа, развития научных теорий, опровержения и фальсификации, оценить качество исследований в некоторой предметной области Стандартные (лекционно-семинарские)
Общенаучная ОНК-4 Готовность использовать основные законы естественнонаучных дисциплин в профессиональной деятельности, применять методы математического анализа и моделирования, теоретического и экспериментального исследования при работе в какой-либо предметной области Стандартные (лекционно-семинарские)
Общенаучная ОНК-5 Готовность выявить естественнонаучную сущность проблем, возникающих в ходе профессиональной деятельности, привлечь их для решения соответствующий аппарат дисциплины Стандартные (лекционно-семинарские)
Общенаучная ОНК-6 Способность приобретать новые знания с использованием научной методологии и современных образовательных и информационных технологий Стандартные (лекционно-семинарские)
Общенаучная ОНК-7 Способность порождать новые идеи (креативность) Стандартные (лекционно-семинарские)
Инструментальные ИК-2 Умение работать на компьютере, навыки использования основных классов прикладного программного обеспечения, работы в компьютерных сетях, составления баз данных Стандартные (лекционно-семинарские)
Профессиональные ПК-1 Способность демонстрации общенаучных базовых знаний естественных наук, математики и информатики, понимание основных фактов, концепций, принципов теорий, связанных с прикладной математикой и информатикой Стандартные (лекционно-семинарские)
Профессиональные ПК-2 Способность понимать и применять в исследовательской и прикладной деятельности современный математический аппарат Стандартные (лекционно-семинарские)
Профессиональные ПК-4 Способность критически оценивать собственную квалификацию и её востребованность, переосмысливать накопленный практический опыт, изменять при необходимости вид и характер своей профессиональной деятельности Стандартные (лекционно-семинарские)
ПрофессиональныеСтандартные (лекционно-семинарские) ПК-8 Способность решать задачи производственной и технологической деятельности на профессиональном уровне, включая разработку математических моделей, алгоритмических и программных решений Стандартные (лекционно-семинарские)
Место дисциплины в структуре образовательной программы
Настоящая дисциплина относится к циклу математических и естественнонаучных дисциплин, является базовой для студентов 3-го курса (2-й и 3-й модули учебного плана подготовки бакалавра по направлению 080500.62 «Бизнес-информатика».
Изучение данной дисциплины базируется на следующих дисциплинах:
Математический анализ
Линейная алгебра
Теория вероятностей
Институциальная экономика
Для освоения учебной дисциплины студенты должны владеть следующими знаниями и компетенциями:
знание элементарной математики
умение решать системы линейных и нелинейных уравнений
знание дифференциального исчисления
владение базовым аппаратом теории вероятностей
Основные положения дисциплины должны быть использованы в дальнейшем при изучении следующих дисциплин:
Теория отраслевых рынков,
Экономика общественного сектора,
Макроэкономическое планирование и прогнозирование.
Фондовый рынок и финансовый менеджмент.
Тематический план учебной дисциплины
№ Наименование темы Всего часов Аудиторные часы Самостоятельная работа
Лекции Семинары Практические занятия Третий модуль
1 Игровая модель как способ описания конфликтной ситуации. Классификация теоретико-игровых моделей. 10 2 2 6
2 Игры в нормальной форме. Равновесие по Нэшу в чистых и смешанных стратегиях. 22 6 6 10
3 Игры с несовершенной и с неполной информацией. 32 6 6 20
4 Кооперативные игры.
28 4 4 20
Всего 92 18 18 56
Четвертый модуль
5 Введение. Примеры задач и математическая модель исследования операций. 12 2 2 8
6 Линейные оптимизационные модели в исследовании операций 32 6 6 20
7 Нелинейные оптимизационные модели и методы нелинейного программирования 12 2 2 8
8 Многокритериальные модели и методы решения многокритериальных задач 32 6 6 20
Всего 92 16 16 56
Итого 180 34 34 112
Формы контроля знаний студентов
Тип контроля Форма контроля 3 курс Параметры
3 4 Текущий
Контрольная работа * Письменная работа 80 минут
Контрольная работа * Письменная работа 80 минут
Итоговый Зачет FILLIN \* MERGEFORMAT * Письменная работа 80 минут
Критерии оценки знаний, навыков
Для успешного прохождения контроля студент должен показать знание основных понятий, определений и формулировок теорем; умение решать типовые задачи исследования операций, строить математические модели по вербальной постановке оптимизационных и игровых задач, знание методов и алгоритмов для вычисления рациональных решений.
Оценки по всем формам текущего контроля выставляются по 10-ти балльной шкале.
Содержание дисциплины
Тема 1. Игровая модель как способ описания кон-фликтной ситуации. Классификация тео-ретико-игровых моделей.
Игра как модель конфликтной ситуации. Содержательные примеры игр. Формализация игры: участники игры, стратегии, ситуации, исходы, функции выигрыша. Предположения об информированности игроков. Классификация игр по различным признакам: по множествам стратегий (конечные или бесконечные), по структуре целей (антагонистические или неантагонистические игры), по информации и поведению (кооперативные и некооперативные игры, и др.), по наличию динамики (статические, многошаговые, дифференциальные). Игры в нормальной и развернутой форме.
Литература:
Базовый учебник: [4] (введение).
Дополнительная литература: [22] (гл.1).
Тема 2. Игры в нормальной форме. Равновесие по Нешу в чистых и смешанных стратегиях. Основы эволюционной теории игр.
Статические игры в нормальной форме. Доминирующие и доминируемые стратегии. Равновесие по Нешу в чистых стратегиях. Равновесие по Нешу в смешанных стратегиях. Теорема о существовании равновесия (для игр с конечным числом стратегий). Интерпретация равновесий по Нешу в чистых и смешанных стратегиях, в т.ч. при множественности равновесий. Эволюционно-устойчивые стратегии. Анализ эволюционных процессов в биологических и социально-экономических системах с помощью теоретико-игровых моделей.
Тема 3. Динамические игры с совершенной и несовершенной информацией. Повторяющиеся игры. Игры с неполной информацией.
Игры с последовательными ходами; понятие стратегии. Метод обратной индукции. Равновесие по Нешу, совершенное в подыграх. Байесовские игры в нормальной форме. Равновесие Байеса-Неша.
Тема 4. Кооперативные игры.
Переход от некооперативной игры к кооперативной. Коперативные игры с трансферабельной полезностью. Концепция трансферабельной полезности и ограничения ее применимости. Модель кооперативной игры: множество игроков, коалиции, характеристическая функция. Свойства игр: монотонность, супераддитивность, выпуклость.
Дележ как решения кооперативной игры. С-ядро игры и его свойства. Вектор Шепли и его свойства. Нахождение вектора Шепли. Нуклеолус.
Дополнительно: простые игры для моделирования коллективного принятия решений. Интепретация вектора Шепли в простых играх.
Тема 5. Введение. Примеры задач и математическая модель исследования операций. Игровые модели как инструмент исследования операций в конфликтных ситуациях.
Предмет и методы исследования операций. Взаимосвязь исследования операций, принятия решений, системного анализа. Необходимость разработки и использования моделей. Моделирование, его виды. Преимущества математического моделирования по сравнению с натурными экспериментами. Основные этапы моделирования. Круг Самарского.
Классификация моделей по объекту исследования, уровню агрегирования, применяемому математическому аппарату. Система задач математического программирования.
Вопросы применения средств вычислительной техники.
Литература:
Базовый учебник: [1] (тема 1), [3] (введение, гл.1).
Основная литература: [9] (гл.1-2).
Дополнительная литература:, [12], [20] (гл.1), [13] (гл.1-3).
Тема 6. Линейные оптимизационные модели в исследовании операций
Задачи линейного программирования (ЛП), их особенности, место и роль в системе оптимизационных математических моделей. Примеры: задачи об оптимальном использовании ресурсов, о диете, о смесях, транспортные и другие задачи. Графический метод решения задачи ЛП.
Общая постановка и различные формы задачи ЛП. Геометрия задач ЛП. Выпуклые множества. Выпуклые оболочки. Вершины многогранного множества. Экстремумы линейной функции на многограннике и многогранном множестве. Алгебра задач ЛП. Базисные и допустимые базисные решения. Связь вершин многогранника допустимых решений и базисных решений. Понятие о симплекс-методе решения задач ЛП.
Теория двойственности в ЛП. Взаимно двойственные задачи. Теоремы двойственности. Содержательная интерпретация двойственных переменных. Анализ чувствительности оптимального решения к изменениям параметров задачи.
Задачи целочисленного линейного программирования. Метод ветвей и границ.
Литература:
Базовый учебник: [3] (гл. 1-8).
Основная литература: [5] (гл. 1), [8]
Дополнительная литература: [15, 17].
Тема 7. Нелинейные оптимизационные модели и нелинейное программирование
Общая оптимизационная задача. Математическое программирование – аппарат решения оптимизационных задач. Классификации задач математического программирования. Понятие о численных методах решения задач нелинейного программирования. Классификация методов. Безусловная оптимизация: градиентные методы и методы второго порядка. Условная оптимизация, метод штрафных функций.
Литература:
Базовый учебник: [1] (темы 3,4), [3] (гл. 10-11,13) .
Основная литература: [7], [11] (гл. 5).
Дополнительная литература: [17] (гл. 3).
Тема 8. Многокритериальные модели и методы решения многокритериальных задач
Многокритериальные модели исследования операций и многокритериальные задачи оптимизации. Содержательные примеры.
Описание многокритериальных предпочтений. Функции ценности и отношения предпочтения. Оптимальные и недоминируемые решения.
Отношение и оптимумы Парето. Свойства парето-оптимальных решений.
Метод обобщенного критерия. Методы SMART и SMARTS.
Целевое программирование.
Метод анализа иерархий. Приоритеты критериев и вариантов. Оценивание приоритетов.
Литература:
Базовый учебник: [3] (Тема 7).
Основная литература: [11] (§ 1.1 – 1.5, § 2.1 – 2.2).
Дополнительная литература: [13] (Лекции 1, 5 ), [20] (с. 96 – 118, 174 – 182).
Тематика заданий по различным формам текущего контроля
Контрольные работы содержат задачи по следующим темам дисциплины:
контрольная работа № 1: построение игровых моделей, поиск равновесия по Нешу
контрольная работа № 2: построение моделей по вербальному описанию задачи, линейное программирование, двойственность в ЛП;
зачетная работа: по темам 5 – 8.
Методические рекомендации преподавателю
Одно из практических занятий по теме 2 «Линейные оптимизационные модели в исследовании операций» целесообразно провести в компьютерном классе.
Методические указания студентам
Для успешного изучения дисциплины рекомендуется перед каждым практическим занятием повторить теоретический материал по конспекту лекций, а после активной работы на занятии – выполнять полученные задания (решать предложенные задачи) и изучать указанную в программе литературу.
Рекомендации по использованию информационных технологий
Для решения линейных и нелинейных задач исследования операций и вычисления оптимальных стратегий в конечных играх программирования целесообразно использовать программу MS Exсel.
Оценочные средства для текущего контроля и аттестации студента
Вопросы для оценки качества освоения дисциплины
По каким признакам можно классифицировать игры?
Приведите примеры игры в нормальной и развернутой форме.
Что такое доминирующие, доминируемые и недоминируемые стратегии, строгое доминирование?
Изложите на примере матричной игры принцип наилучшего гарантированного результата.
Ситуация равновесия (седловая точка) в антагонистической игре, оптимальные стратегии. Значение (цена) игры.
Связь седловых точек и гарантирующих стратегий. Свойства седловых точек в случае их неединственности.
Необходимое и достаточное условие существования ситуации равновесия (равенство минимаксов).
Принятие управленческих решений в условиях неопределенности как антагонистическая «игра с природой». Приведите пример.
Критерии Вальда, Гурвица, Сэвиджа и Лапласа для принятия решений в условиях неопределенности.
Дайте определение ситуации равновесия по Нэшу, поясните его содержательный смысл.
Сопоставьте свойств седловых точек и точек Нэша (эквивалентность, взаимозаменяемость).
Как соотносятся свойства эффективности (Парето-оптимальность), устойчивости и справедливости решений в неантагонистических играх (на примере игр («дилемма заключенного», «семейный спор»).
Смешанное расширение матричной игры – что это и зачем понадобилось вводить?
Что значит использовать смешанную стратегию (0.1, 0.1, 0.8)?
Какие Вы знаете способы вычисления седловых точек в чистых стратегиях?
Что гласит основная теорема матричных игр?
Вычисление седловой точки в смешанных стратегиях специальным представлением функции выигрыша (аналитический метод).
Вычисление седловой точки в смешанных стратегиях для игр 2хn и mх2 (графо-аналитический метод).
Связь матричной игры с задачей линейного программирования.
Биматричные игры. Примеры. Смешанное расширение биматричной игры.
Поиск ситуаций равновесия (точек Нэша) в чистых стратегиях. Основная теорема матричных игр (существование решения в смешанных стратегиях).
На чем основан метод наилучшего отклика для вычисления ситуаций равновесия в смешанных стратегиях для игр 2х2 (метод зигзагов).
Что такое игры с иерархической структурой? Как найти оптимальные по Штакельбергу стратегии (на примере непрерывной игры – дуополия Штакельберга)?
Приведите пример динамической игры с полной информацией, найдите ее решение методом обратной индукции.
Может ли достигаться максимум или минимум линейной целевой функции во внутренней точке множества допустимых решений?
Каковы две возможные причины отсутствия решений в задачах линейного программирования (ЛП)?
Может ли задача ЛП иметь ровно три оптимальных решения?
Докажите, что множество решений системы линейных неравенств Ax≤ b выпукло.
Сформулируйте двойственную задачу ЛП (для стандартной формы - с неравенствами). В каком случае двойственная задача совпадает с прямой задачей?
Докажите, что задача ЛП, двойственная к двойственной, совпадает с исходной (для стандартной формы).
Сформулируйте и докажите основное неравенство ЛП.
Сформулируйте и докажите основную теорему ЛП.
Сформулируйте 2-ю теорему двойственности ЛП (условия дополняющей нежесткости).
Как найти оптимальное решение прямой задачи линейного программирования, если найдено оптимальное решение ее двойственной задачи?
Может ли выпуклая функция иметь на выпуклом множестве ровно три точки минимума?
Справедливо ли утверждение: «выпуклая функция на выпуклом множестве имеет экстремум»?
Сформулируйте достаточное условие существования глобального экстремума (теорема Вейерштрасса). Назовите возможные причины отсутствия оптимального решения, приведите примеры.
Чем вызвана необходимость разработки и применения численных методов нелинейного программирования?
Какова принципиальная особенность многокритериальных задач по сравнению с однокритериальными задачами оптимизации?
Как описываются предпочтения на языке функции ценности и отношения предпочтения?
Что такое оптимальное и недоминируемое решения, как они соотносятся?
В чем смысл отношения Парето? Как определяется множество Парето?
Как характеризуется оптимальное по Парето решение при помощи линейной свертки и функции Гермейера?
Каков порядок решения задачи методом SMART? В чем состоит «интеллектуальная ошибка» этого метода.
В чем суть метода SMARTS?
Опишите метод целевого программирования.
Дайте общее описание метода анализа иерархий.
Как оцениваются приоритеты критериев и вариантов в методе анализа иерархий?
Как вычисляются глобальные приоритеты вариантов в методе анализа иерархий?
Порядок формирования оценок по дисциплине
Итоговая оценка по учебной дисциплине определяется на основе оценок за следующие виды контрольных работ:
- письменная аудиторная контрольная работа № 1 (второй модуль, 120 мин),
- письменная аудиторная контрольная работа № 2 (третий модуль, 80 мин),
- зачет (третий модуль, 80 мин).
Текущий контроль в 3 и 4 модулях осуществляется в виде одной письменной контрольной работы в конце каждого из модулей по изученному материалу и домашних заданий по материалам прочитанных лекций и проведенных семинаров. Итоговый контроль осуществляется в виде письменной экзаменационной работы по изученному материалу в течение 4 модуля и проводится него.
Оценки за контрольные работы и зачет, промежуточные и итоговая оценки выставляются в десятибалльной шкале. Способ округления всех оценок арифметический. Промежуточные оценки за 3 и 4 модули Онак.3 и Онак.4выставляются с учетом оценки за контрольную работу, работы студента на аудиторных занятиях и самостоятельной работы.
Итоговая десятибалльная оценка Оитог. успеваемости студента по дисциплине в целом определяется по формуле
Оитог. = 0,4Онак.3 + 0,4Онак.4+ 0,2Озачет.
Перевод итоговой десятибалльной оценки в пятибалльную осуществляется по общепринятому в НИУ ВШЭ правилу:
0, 1, 2, 3 неудовлетворительно
4, 5 удовлетворительно
6, 7 хорошо
8, 9, 10 отлично
На пересдаче студенту не предоставляется возможность получить дополнительный балл для компенсации оценки за текущий контроль.
Учебно-методическое и информационное обеспечение дисциплины
Базовые учебники
Захаров А.В. Теория игр в общественных науках. Москва: Издательский дом ВШЭ, 2015.
Соколов А.В., Токарев В.В. Методы оптимальных решений. Т.1. Общие положения. Математическое программирование. Москва: ФИЗМАТЛИТ, 2010, 2011.
Токарев В.В. Методы оптимальных решений. Т.2. Многокритериальность. Динамика. Неопределенность. Москва: ФИЗМАТЛИТ, 2010, 2011.
Исследование операций в экономике. Под ред. Кремера Н.Ш. М.: Маркет ДС, 2007.
Воробьев Н.Н. Теория игр для экономистов-кибернетиков. М.: Наука, 1985 (гл. 1,3).
Основная литература
Ф.П. Васильев, А.Ю. Иваницкий. Линейное программирование. М. Факториал Пресс, 2008.
Ф.П. Васильев. Методы оптимизации. М. Факториал Пресс, 2005.
Ногин В.Д. Методы оптимальных решений. СПб, СПб филиал ГУ – ВШЭ, 2006.
Гольштейн Е.Г., Юдин Д.Б. Задачи линейного программирования транспортного типа. М.: Наука, 1969.
Вентцель Е.С. Исследование операций. Задачи, принципы, методология. М.: ВШ, 2001.
Подиновский В.И., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М.: Физматлит, 2007.
Курицкий Б.Я. Поиск оптимальных решений средствами Excel 7.0. СПб., BHV, 1997.
Дополнительная литература
Ларичев О.И. Теория и методы принятия решений. / Учебник. М.: Логос, 2002.
Петров А.А., Поспелов И.Г., Шананин А.А. Опыт математического моделирования экономики. М., Энергоатомиздат, 1996.
Л.В. Канторович, А.Б. Горстко. Математическое оптимальное программирование в экономике. М.: Знание, 1968.
Дж. Данциг. Линейное программирование, его обобщения и применение. М.: Прогресс, 1966.
Подиновский В.В. Введение в теорию важности критериев в многокритериальных задачах принятия решений. М.: Физматлит, 2007.
Математические методы принятия решений в экономике. /Учебник. Под ред. Колемаева В.А. М.: Финстатинформ, 1999.
Лотов А.В. Введение в экономико-математическое моделирование / Учебное пособие. М.: Наука, Физматлит, 1984.
Хрестоматия по учебной дисциплине «Теория и методы принятия многокритериальных решений». Составитель В.В. Подиновский. М.: ГУ – ВШЭ, 2005.
Хазанова Л.Э. Математические методы в экономике: Учебное пособие. – М.:,БЕК, 2002.
Жуковский В.И., Молоствов В.С. Многокритериальное принятие решений в условиях неопределенности. М.: Международный НИИ проблем управления, 1988.
Шагин В.Л. Теория игр. Учебное пособие. М.: ГУ ВШЭ, 2003 (гл. 1-3).
http://plato.stanford.edu/entries/game-evolutionary/
A. Dixit and B. Nalebuff. Thinking Strategically, Norton 1991
Автор программыВ.С.Молоствов
© В.С. Молоствов, С.Г. Кисельгоф, В.В. Подиновский

Приложенные файлы

  • docx 2469569
    Размер файла: 58 kB Загрузок: 0

Добавить комментарий