Geum.ru

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

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

Содержание


Автор программы
Учебные задачи курса.
Тематический план учебной дисциплины
Содержание программы
4. Михайлова Елена
6. Перепечаева Арина
Подобный материал:

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


Государственный университет - Высшая школа экономики


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



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


Основы математического моделирования

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

(специализация «электронный бизнес»)


Автор А.А. Рубчинский


Рекомендована секцией УМС Одобрена на заседании кафедры


Математические и статистические высшей математики методы в экономике на факультете экономики

Председатель Зав. кафедрой


__________________А.С. Шведов __________________Ф.Т. Алескеров ________________________________ ___________________________

«_____» __________________ 20 г. «____»___________________20 г


Утверждена УС факультета

Бизнес-информатики

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


_________________________________

« ____» ___________________20 г.

Москва 2010

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


Автор программы А.А. Рубчинский.


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


Аннотация. Формальные методы математического исследования в большой степени опираются на построение моделей, естественно предшествующее таким исследованиям. Построение моделей является в первую очередь искусством. И, как всякому искусству, ему можно учиться на примерах и подражании. Одного подражания, конечно же, мало. Как написано в авторском предисловии к книге Фреда Актона «Численные методы, которые работают» (F. Acton, Numerical methods that work), «Научиться численным методам, глядя на то, как другие решают задачи, так же невозможно, как научиться портретной живописи, стоя за спиной художника. Это просто не работает.»

Таким образом, имеет место обычное противоречие – противоречие между формальным характером математики и неформальным характером её приложений. Решать реальные задачи действительно очень трудно, просто читать, как это делается, почти бесполезно, а решать вместо реальных задач те, которые даются в учебных пособиях (и часто называются прикладными) полезно только на начальном уровне.

Частичным выходом из этого противоречия является предлагаемый в данном курсе подход. Суть дела состоит в следующем. Рассматриваются реальные задачи (часть из которых относится к электронному бизнесу), в которых можно естественно выделить достаточно простые подзадачи, требующие, однако, владения соответствующим формальным аппаратом. Поэтому у данного курса есть две цели: и овладение (на каком-то уровне) формальным языком математического моделирования (аппаратом оптимизации, теории графов и др.), и анализ достаточно типичных реальных ситуаций, в которых эти методы действительно приложимы.

Более подробно рассматриваемые реальные задачи и используемые при их решении фор-мальные методы рассмотрены в разделах курса.


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

– иметь представление о современных методах математического моделирования;

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

Формы контроля. Основными формами изучения дисциплины являются
    • лекции, семинара и самостоятельная работа студентов;
    • текущий контроль;
    • итоговый контроль: письменный экзамен в конце 5-го модуля.


Итоговая оценка K по 10-балльной шкале формируется как взвешенная сумма:

K = 0,4 Сам. Раб. + 0,6 Экз.

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


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

№
Название темы
Всего
часов
Аудиторные часы
Сам.
работа

Лекции
Практ. занятия

1
Примеры удачных и неудачных моделей
11
2
2
7

2
Торговля по каталогам. Профиль клиен-та.

11
2
2
7

3
Анализ данных и автоматическая класси-фикация в торговле по каталогам
12
2
2
8

4
Виртуальная реклама – перспективы и за-дачи
12
2
2
8

5
Распознавание образов и обработка изоб-ражений
12
2
2
8

6
Телекоммуникационные системы

11
2
2
7

7
Аппарат описания: графы и потоки
12
2
2
8

8
Кольца в телекоммуникационных сетях
11
2
2
7

9
Оптимизация колец
12
2
2
8

10
Тракты в телекоммуникационных сетях
12
2
2
8

11
Распределение операционного времени

11
2
2
7

12
Игровые постановки распределительных задач
11
2
2
7

13
Эффективная реклама – игровой подход
12
2
2
8

14
Имитационное моделирование
12
2
2
8



Итого
162
28
28
106

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

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

Тема 1. Примеры удачных и неудачных моделей.

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

Лит-ра: основная: [1], введение и раздел 1; дополнительная: [6], гл. 4.


Тема 2. Торговля по каталогам. Профиль клиента.

Системы массового обслуживания. Разнообразие клиентов. Понятие профиля клиента, трудности обработки и анализа информации.

Лит-ра: основная: [1], раздел 2; дополнительная: [8], гл. 14.


Тема 3. Анализ данных и автоматическая классификация в торговле по каталогам. Сжатое представление информации. Факторный анализ и классификация. Data mining. Основные подходы и методы.

Лит-ра: основная: [1], раздел 3; дополнительная: [1], гл. 4, 5; [2], гл. 3.


Тема 4. Виртуальная реклама – перспективы и задачи.

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

Лит-ра: основная: [1], раздел 4.

Тема 5. Распознавание образов и обработка изображений.

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

Лит-ра: основная: [1], раздел 4; дополнительная: [14].


Тема 6. Телекоммуникационные системы.

Основные понятия. Параметры телекоммуникационных систем. Оптико-волоконные кабе-ли и сетевое оборудование. Надёжность телекоммуникационных систем и способы её по-вышения.

Лит-ра: основная: [1], раздел 5; дополнительная: [11].


Тема 7. Аппарат описания: графы и потоки

Графы. Основные понятия. Представление технических и организационных систем. Пути на графах. Гамильтоновы, эйлеровы, кратчайшие и критические пути. Моделирование телекоммуникационных систем графами. Потоковые сети и системы. Неориентированные сети. Минимаксная модификация алгоритма Дейкстры в потоковой задаче на равномер-ную загрузку сети.

Лит-ра: основная: [1], раздел 5; дополнительная: [7].


Тема 8. Кольца в телекоммуникационных сетях.

Основные типы колец. Передача информации по кольцам. ADM (add-drop moduls) и их параметры. Повреждения и перестройка сетей.

Лит-ра: основная: [1], раздел 5; дополнительная: [9], [10], [11].


Тема 9. Оптимизация колец.

Основные критерии оптимизации. Многокритериальная оптимизация: альтернативы, кри-терии, ограничения и правила. Дискретная оптимизация. Алгоритм оптимизации колец.

Лит-ра: основная: [1], раздел 5; дополнительная: [6], гл. 5, 6; [7], гл. 3–5; [11].


Тема 10. Тракты в телекоммуникационных сетях.

Восстановление информации о трактах по частичной информации об их включениях. Тракты и эйлеровы пути. Алгоритм Флёри нахождения эйлеровых путей и циклов.

Лит-ра: основная: [1], раздел 5; дополнительная: [13].


Тема 11. Распределение операционного времени.

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

Лит-ра: основная: [1], раздел 6; дополнительная: [12].


Тема 12. Игровые постановки распределительных задач.

Реальные мотивы действий участвующих сторон. Базовые понятия теории игр и игровые модели распределения ресурсов. Повторяющиеся игры и гипотеза индикаторного поведе-ния.

Лит-ра: основная: [1], раздел 6; дополнительная: [12]; [4], гл. 2, 10; [3], гл. 4.


Тема 13. Эффективная реклама – игровой подход.

Игровая постановка задачи о конкуренции и эффективной рекламе. Явные решения мат-ричных игр.

Лит-ра: основная: [1], раздел 6; дополнительная: [4], гл. 3.


Тема 14. Имитационное моделирование.

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

Лит-ра: основная: [1], раздел 7; дополнительная: [8], гл. 14.


Литература


Основная


1. Учебный материал «Основы математического моделирования» (подготовлен А.А. Рубчинским).


Дополнительная


1. Айвазян, С.А. и др. (1989). Прикладная статистика. Классификация и снижение размер-ности. М.: Финансы и статистика.

2. Барсегян А.А., Куприянов М.С., Степаненко В.В., Холод И.И. Технологии анализа дан-ных. СПб.: БХВ-Петербург, 2007, 376с.

3. Бурков В.Н., Опойцев В.И. Теория активных систем. М.: Наука, 1975, 238 с.

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

5. Кофман А. Введение в прикладную комбинаторику, М., Наука, 1975.

6. Ларичев О.И. Теория и методы принятия решений. М.: Логос, 2006, 391с.

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

8. Черчмен У., Акоф Р., Арноф Л. Введение в исследование операций. М.: Наука, 1968, 488с.

9. Model B., A.Rubchinsky. Optimization of Ring Structure in Telephone Networks. – ECMI 96, Book of Abstracts, pp. 169-171. – Copenhagen, 1996.

10. Bregman L., A.Pridor, A.Rubchinsky. Flow Optimization in Telephone Network with Rings. – ECMI 96, Book of Abstracts, pp. 176-178. – Copenhagen, 1996.

11. Method for cost effective ring allocation in telecommunication networks. – Patent Number 125683 in Israel. Inventors: Lev Bregman, Yuri Kazarinov, Boris Model, Alexander Rubchins-ky, and Alexander Virtzer. 1998.

12. Rubchinsky A. Time Allocation in Surgery Coordination Center. – International Conference on Control Sciences, Book of Abstracts, vol. 2, pp. 41-42. – Institute of Control Science, Moscow, 1999.

13. Rubchinsky A. Trails in Bezeq Network. – Proc. of International Conference on Distributed Computer Communication Networks, pp. 147-151. – Tel-Aviv, 1999.

14. Rubchinsky A. A New Approach to Image Processing. – Четвёртая Международная конфе-ренция по проблемам управления. Сборник трудов, стр.398–410. М., 2009.


Примеры заданий на экзамене


Задание 1. В заданном неориентированном графе найти эйлеров цикл, пользуясь алгорит-мом Флёри (должны быть показаны все шаги, вплоть до ситуации, когда дальнейший путь определяется совершенно однозначно, но не более того).

Задание 2. Отметки 7 школьников по 4 предметам даны в таблице:

Школьник
Алгебра
Геометрия
Литература
Английский

1. Aрсенкова Александра

5
4
4
5

2. Баранникова Елена
3
4
4
3

3. Кулакова Екатерина
3
3
4
3

4. Михайлова Елена
3
3
4
4

5. Морозова Мария
5
4
3
5

6. Перепечаева Арина
4
3
5
4

7. Полищук Наталья
3
5
3
3

Найти и нарисовать паретовские уровни (со всеми дугами, соединяющими соседние уровни) по данным этой таблицы.

Задание 3. Найти все оптимальные чистые стратегии в игре и чистую цену игры с платёж-ной матрицей

1
2
1

0
100
0

1
3
1

Задание 4. Найти оптимальные смешанные стратегии обоих игроков в игре с матрицей



Задание 7. Найти все оптимальные стратегии обоих игроков и цену игры в игре с платёж-ными матрицами




Задание 5. Рассматривается игра двух лиц с платёжной матрицей



где 1-ое (2-ое) число в скобках – выигрыш игрока А (B). Требуется найти равновесия Нэша в чистых стратегиях (если они есть).

Задание 6. Пусть Qi = [102, ), fi() =  (i = 1, ..., N). Проверить, что в игре с ука-занными функциями выигрыша точка (, ..., ) является точкой Нэша.

Задание 7. Найти выигрыш каждого игрока в указанной точке Нэша и в точке = (102, ..., 102).

Задание 8. В орграфах на рисунке найти следующие множества.




а) Все максимальные внутренне устойчивые множества, т.е. не содержащиеся ни в одном другом бóльшем внутренне устойчивом множестве.

b) Все минимальные внешне устойчивые множества.

c) Все устойчивые множества.

Задание 9. Требуется распределить квоты методом Адамса в следующей ситуации.

Наксон (Naxxon), Ароко (Aroco) и Евробайл (Eurobile) образовали консорциум для строи-тельства морской нефтедобывающей платформы у побережья Африки. Компании решили сформировать совет из 9 членов для руководства проектом; число представителей каждой компании в совете должно быть пропорционально числу держателей акций. Наксон имеет 4700 держателей, Ароко  3700 дер- жателей и Евробайл  1600 держателей.

Задание 10. Из официального сайта Госдумы взять данные по голосованию на последних выборах в думу (2-ого декабря 2007г). Используя эту информацию:

а) разделить места методами Гамильтона, Джефферсона, Адамса и Вебстера, сравнить с нынешним составом и дать краткий комментарий.

Задание 11. За последние 4 года на ежемесячные встречи выпускников приходило следу-ющее число человек:

28
51
31
33
27
35
33
40
37
28
33
27

33
31
41
46
42
36
53
23
33
27
40
30

33
22
37
38
36
48
22
36
45
34
26
28

40
42
43
41
35
38
31
48
38
36
39
35

Разбив числа на классы 20–24, 25–29, 30–34, 35–39, 40–44, 45–49, 50–54, построить эмпирическую функцию распределения «меньше чем».

Задание 12. Отчёты больницы показывают, что среднее время операции равно 111,6 минуты при среднеквадратичном отклонении 2,8 минуты. Каков минимальный процент операций, выполненных за время между 106,0 и 117,2 минуты?

Задание 13. Исследование, проведённое офицером бронетанкового батальона, показало, что в течение 64 дней среднее число исправных машин равно 1266 при среднеквадратич-ном отклонении = 105. Найти 95-процентный доверительный интервал.

Задание 14. Пусть для некоторой популяции = 15. Найти размер n выборки, гарантиру-ющей, что ошибка среднего не превосходит 2 с вероятностью 0,98.


Автор программы: А.А. Рубчинский