Реферат: Факультет Бизнес Информатики программа дисциплины

Правительство Российской Федерации


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


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


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


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


Методы принятия решений

для специальности 010400.62 «Прикладная математика и информатика» подготовки бакалавров

Автор к.т.н. И.А. Зутлер


Рекомендована секцией УМС Одобрена на заседании кафедры _____________________________ ________________________________ Председатель Зав. кафедрой _____________________________ ________________________________ «_____» __________________ 20__ г. «____»__________________ 20__ г Утверждена УС факультета _________________________________ Ученый секретарь _________________________________ « ____» ___________________20__ г.
Москва

^ Пояснительная записка


Требования к студентам Изучение курса «Методы принятия решений» требует предварительных знаний теории вероятностей и математического анализа в объёме, доступном бакалаврам математических специальностей университетов.


Аннотация

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

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

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

Будут изучены: методы Revenue&Yield management – управления продуктом с конечным сроком полезности и низким marginal cost (например, авиабилеты); модели вероятностного динамического программирования; управляемые марковские процессы; основы теории массового обслуживания (ТМО) и их применение к решению задач управления производством и номерным фондом гостиниц. ТМО, появившаяся сто лет назад для анализа телетрафика, сейчас стала необходимой дисциплиной для понимания основ параллельных вычислений.

Во второй части курса будут моделироваться процессы распространения SIS и SIR эпидемий и хищник-жертва методом динамики средних. Далее те же процессы будут изучены с точки зрения теории сетей. Описаны некоторые специфические особенности Scale-Free Networks. Студентам будут предложены задачи моделирования процессов распространения моды, информации, вирусов на различных классах социальных сетей.

В конце курса изложены классические сетевые модели: поиска кратчайшего и критические пути на графе, задача о наибольшем потоке. Разобран парадокс Брасса (Braess) – увеличение пробок от строительства новых дорог.

^ Задачи курса

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

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

уметь пользоваться типовыми методами теории принятия решения,

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


Основными формами изучения дисциплины являются:

лекции

семинары

самостоятельная работа слушателей.



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

текущий контроль: работа и доклады на семинарах,

итоговый контроль: исследовательская работа или письменный экзамен.


^ Итоговая оценка K формируется как взвешенная сумма:

K = 0,4 Текущий контроль + 0,6 Итоговый контроль.

10-балльная итоговая оценка округляются до целого числа баллов.


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

№

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

Всего
часов

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

Сам.
работа

Лекции

Практ. занятия

1

Проблема выбора. Жесткие и мягкие модели, удачные и неудачные модели.













2

Yield management. Задачи торговли продуктом с конечным сроком полезности. Эвристические стационарные методы.













3

Вероятностное динамическое программирование. Динамические методы управления продажами.













4

Дискретные марковские процессы. Управляемые марковские процессы.













5

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













6

Метод динамики средних. Модель эпидемии.

Основы теории сетей.













7

Теория графов. Сетевые модели. Теория расписаний. Парадокс Брасса.















Итого












Лекции и семинары распределены в соответствии с РУПом.

^ Содержание программы

Тема 1. Проблемы выбора. Жесткие и мягкие математические модели реального мира

Психология выбора. Примеры выявления проблем, этапы анализа проблемной ситуации. Анализ и Синтез. Виды моделей. Критерии оценки моделей. Примеры удачных и неудачных моделей.

Лит-ра: [1], [2], [3].


^ Тема 2. Yield management

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

Стационарные модели управления продажами. Структура корзин (nested fare class structure). Метод ожидаемой предельной полезности (EMR – expected marginal revenue). Доказательство формулы Литтлвуда (Littelwood). Пример использования эвристических методов - теневой цены (shadow price) и заявочной цены (bid price) для построения структуры корзин при продаже билетов на стыковых авиарейсах по нескольким тарифам.

Лит-ра: [4].


^ Тема 3. Динамические методы управления продажами

Задачи динамического управления продажами по разным тарифам – открытие/закрытие продаж по низким тарифам. Вероятностное динамическое программирование.

Лит-ра: [5], [6].


^ Тема 4. Дискретные марковские процессы

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

Лит-ра: [6].


^ Тема 5. Основы теории массового обслуживания

Использование ТМО при моделировании экономических процессов. Виды систем массового обслуживания, дисциплины обслуживания. Исследуемые характеристики СМО.

Пуассоновский входящий поток. Свойства, парадоксы. Обобщение на нестационарный неординарный поток. Поток Пальма. Экспоненциальное время обслуживания. Решение прикладных задач управления запасами.

Марковские системы массового обслуживания. Модель Энгсета. Формула Литтла. Уравнения Эрланга. Многомерные уравнения Эрланга, пример их использования при стационарном управлении номерным фондом гостиниц.

Решение систем типа M/G/n/.

Использование методов ТМО для динамического управления продажами в непрерывном времени.

Лит-ра: [5], [6], [7], [8], [9], [10].


^ Тема 6. Метод динамики средних. Теория сетей

Основания метода динамики средних. Модель хищник-жертва. Модель эпидемии SIS и SIR. Моделирование социальных процессов. Основы теории сетей. Scale-Free Networks, Small-World Graphs.

[19], [20], [21], [22], [11], [23].


^ Тема 8. Теория графов. Сетевые модели. Теория расписаний. Анализ алгоритмов

Оценка времени выполнения алгоритма.

Графы. Основные понятия. Пути и потоки на графах. Нетрадиционные транспортные модели. Задача о назначениях.

Сетевые модели. Кратчайшие и критические пути. Алгоритм Флойда. Задача о наибольшем потоке. Сетевое планирование.

Парадокс Брасса. Использование общественных благ.

Лит-ра: [6], [13], [14].


Литература


Арнольд В.И. «Жесткие» и «мягкие» математические модели. МЦМНО, 2000.

Арнольд В.И. Теория катастроф. М.: Наука, 1990.

Перегудов Ф.И., Тарасенко Ф.П. Введение в системный анализ, -М.: Высшая школа, 1989.

Williamson Elizabeth L. Airline network seat inventory control: methodologies and revenue impacts, Doctoral Thesis, MIT Flight Transportation Laboratory, Cambridge, Ma. 1992.

Зутлер И. А. Управление ограниченным ресурсом на конечном промежутке времени в автоматизированных системах массового обслуживания. Автоматика и телемеханика. 2002 №2, стр. 179-184.

Таха Х.А. Введение в исследование операций. Вильямс 2005.

Taha H. A. Operations research: an introduction. University of Arkansas, Fayetteville.

Галеев Э. М. Классическое вариационное исчисление, оптимальное управление. М.: Изд- во МГГА, 1995.

Вентцель Е.С. Теория вероятностей. -М.: Высшая школа, 1999.

Ивченко Г. И., Каштанов В. А., Коваленко И. Н. Теория массового обслуживания.-М.: Высшая школа, 1982.

Клейнрок Л. Теория массового обслуживания.-М.: Машиностроение, 1979.

Kleinrock L. Queueing systems, 1974.

Гладуэлл М. Переломный момент. Как незначительные изменения приводят к глобальным переменам. Вильямс, 2006 г.

Gladwell M. The Tipping Point: How Little Things Can Make a Big Difference

Бююль А, Цёфель П., SPSS: искусство обработки информации, СПб, ООО ДиаСофтЮП, 2002

Кормен Т., Лейзерсон Ч., Ривест Р., Штаин К. Алгоритмы. Построение и анализ. 2005.

Cormen T., Leiserson C. Rivest R. Stein C., Introduction to algorithms. The MIT Press, Cambridge, Massachusetts

Робертс Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам, М. Наука, 1986.

Roberts F.S. Discrete mathematical models with application to social, biological and environmental problems.

Алескеров Ф.Т., Хабина Э.Л., Шварц Д.А., Бинарные отношения, графы и коллективные решения. Москва, Изд-во ГУ ВШЭ, 2005.

Печерский С.Л., Беляева А.А., Теория игр для экономистов, 2002.

Мулен Э. Кооперативное принятие решений: аксиомы и модели. М. Мир, 1991.

Алескеров Ф.Т., Ортешук П. Выборы. Голосование. Партии. М., 1995.

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

Newman M. E. J. The structure and function of complex networks. arXiv:cond-mat/0303516v1 [cond-mat.stat-mech] 25 Mar 2003

Easley D., Kleinberg J. Networks, Crowds, and Markets: Reasoning about a Highly Connected World, Cambridge University Press, 2010.

Dorogovtsev S.N., Goltsev A.V.,. Mendes J.F.F, Critical phenomena in complex networks arXiv:0705.0010v6 [cond-mat.stat-mech] 16 Nov 2007

Dorogovtsev S.N., Mendes J.F.F, Evolution of networks From biological nets to the Internet and WWW. Clarendon press. Oxford 2002



Примеры экзаменационных задач


Каждое утро кондитерский цех запрашивают 100±30 тортов (случайное количество). Стоимость торта 150 руб., предельная себестоимость производства 40 руб.

Определить оптимальный объем ночного производства, если непроданные торты пропадают (воспользуйтесь EMR).

Как рассчитывать объем производства, если непроданные торты можно реализовать на следующий день с дисконтом 50 руб.?

Игрок вращает рулетку 4 раза. На барабане нанесены выигрыши: 0$, 1$, 1$, 2$, 2$, 3$, 4$. На любом ходу игрок может забрать выпавший выигрыш либо продолжит. Описать оптимальную стратегию.

В магазине работает 2 кассира и сколько-то стажеров. Кассир обслуживает клиента в среднем за 3 минуты, стажер за 5 минут. В магазин заходит в среднем 40 клиентов в час. На обслуживание клиент становится в единую очередь. Если в очереди стоит более 2-х клиентов на кассу, клиент уходит без покупки. Сформулировать задачу для расчета оптимального числа стажеров. Написать определяющие уравнения.

Можно ли построить ломаную, пересекающую каждый из 16 отрезков только один раз? (ломаная не должна проходить через концы отрезков)




Отрезок [0;1] разделили на пять кусочков и выкинули интервалы [0.2; 0.4] и [0.6; 0.8]. Далее повторяли это процедуру с оставшимися кусками. Найти размерность получившегося множества.

В популяции есть как особи, приобретающие иммунитет, так и не приобретающие. Написать уравнения для смешанной SIS-SIR эпидемии.

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

Владелец земли обрабатывает ее, что приносит ему 10 000$ в год. 1-й арендодатель смог бы обрабатывать землю так, что доходность составила бы 20 000$, а 2-й с доходностью 30 000$. Найти ядро и цену Шепли.



Примеры заданий для докладов на семинарах


Задание 1. Ознакомиться с работой Williamson E. L. [4]. Провести анализ предложенных формул для расчета nested fare class structure в случае нескольких тарифов.


Задание 2. Доказать формулу Литтлвуда методом плотностей.


Задание 3. Построить модель работы маршрутного такси с конечной (начальной) остановкой около станции метро. Используя методы ТМО (или иные?) решить выявленные задачи оптимизации.


Задание 4. Прочитать книгу Переломный момент [11], провести критический анализ. Указать условия, которые нужно учесть при моделировании социальных процессов.


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


1 Если только речь идет не о выборе пирожного во французской кондитерской.