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




Скачать 148.24 Kb.
НазваниеПрограмма дисциплины дискретные математические модели
Дата20.03.2013
Размер148.24 Kb.
ТипПрограмма дисциплины


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


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


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



Факультет Экономики


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


ДИСКРЕТНЫЕ МАТЕМАТИЧЕСКИЕ МОДЕЛИ


для направления 080100.62 «Экономика» подготовки бакалавра


Автор д.т.н., профессор Ф.Т. Алескеров

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

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


методы в экономике экономики


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

_________ __А.С.Шведов _____________ _Ф.Т.Алескеров «_____» __________________ 20__ г. «_ ___»_____________ _____ 20__ г.


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

___экономики____________


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

_________________________________

« ____» ___________________20__ г.

Москва


Требования к студентам: Изучение курса "Дискретные математические модели" не требует предварительных знаний, выходящих за пределы программ общеобразовательной средней школы и курса «Линейная алгебра» (1-й, 2-й модуль 1-го курса).

Аннотация курса:

В последние десятилетия стала очевидна необходимость использования для практического анализа и изучения вопросов, связанных с социально-экономической и общественно-политической жизнью современного общества, довольно широкого класса дискретных математических моделей. Прежде всего, это модели, относящиеся к теории коллективных решений, одним из классических результатов которой является теорема о невозможности К.Эрроу об агрегировании индивидуальных предпочтений в коллективное. Сюда же относятся результаты, впервые полученные Д.Гейлом и Л.Шепли, об обобщенных паросочетаниях. Еще одни типом моделей описывается распределение влияния между участниками в выборных органа. Другой тип дискретных моделей связан с анализом сбалансированности выборных органов. И, наконец, последний тип моделей, активно разрабатываемых и используемых в последнее время, относится к задаче справедливого дележа.

Курс «Дискретные математические модели» содержит основные современные математические подходы к описанию дискретных математических объектов, к построению и изучению прикладных дискретных математических моделей, адекватных реалиям и потребностям социально-экономической и общественно-политической жизни современного общества и рассматривается как необходимый компонент фундаментальной подготовки современных экономистов. Курс не имеет аналогов не только в российской практике обучения, но и в мировой. Изучаемые здесь на доступном для студентов 1-го года обучения (1-ый цикл обучения) уровне вопросы представлены в отдельных западных университетах в качестве тем спецкурсов для магистров и аспирантов.

Курс обильно иллюстрирован примерами из современной российской и зарубежной социально-экономической и общественно-политической жизни. Например, рассматриваются оценки влияния групп и фракций в российском парламенте и Совете Министров Евросоюза и др.

Учебные задачи курса.

В результате изучения курса «Дискретные математические модели» студенты должны

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

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

  • демонстрировать знание и понимание основных определений, теорем, алгоритмов и методов решения задач;

  • уметь строить логически выверенные рассуждения;

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

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



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






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



Всего


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

Самост. работа







часов

Лекции

Семинары

1.

Элементы теории множеств

10

2

2

6

2.

Бинарные отношения и функции полезности

20

4

4

12

3.

Обобщенные паросочетания

10

2

2

6

4.

Задача голосования. Коллективные решения на графе

20

4

4

12

5.

Коалиции и влияние групп в парламенте

15

3

3

9

6.

Справедливый дележ

15

3

3

9

7.

Игровые модели

18

4

4

10







































Итого


108

22

22

64



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

Тема 1. Элементы теории множеств.

Множества, подмножества. Множество всех подмножеств. Операции над множествами: объединение, пересечение, дополнение, разность множеств, симметрическая разность, разбиение. Диаграммы Эйлера-Венна. Число элементов конечного множества. Алгебраические законы операций над множествами. Принцип двойственности.

Литература:

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

Тема 2. Бинарные отношения и функции полезности.

Бинарные отношения и их свойства. Операции над бинарными отношениями. Графическая интерпретация бинарных отношений и их свойств. Специальные классы бинарных отношений: частичный порядок, слабый порядок, линейный порядок. Отношение несравнимости и его свойства для специальных классов бинарных отношений.

Модель ординальной полезности. [Выбор по отношению предпочтения].

Литература:

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

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


Тема 3. Обобщенные паросочетания, или паросочетания при линейных предпочтениях участников.

Предпочтения. Условия классической рациональности предпочтений. Обобщенные паросочетания. Устойчивость паросочетаний. Теорема о существовании устойчивого паросочетания при любых предпочтениях участников (теорема Гейла – Шепли). Манипулирование предпочтениями. Примеры обобщенных паросочетаний: распределение студентов по комнатам общежития, распределение работников по фирмам и др.

Литература:

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

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

Тема 4. Задача голосования. Коллективные решения на графе.

Правило простого большинства. Парадокс Кондорсе. Правило Борда. Внутренняя и внешняя устойчивость. Ядро. Некоторые правила принятия решений: позиционные правила, правила, использующие мажоритарное отношение, правила, использующие вспомогательную числовую шкалу, правила, использующие турнирную матрицу. [Правило порогового агрегирования. Правило выбора непокрытого множества. Правило выбора слабоустойчивого множества].

Литература:

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

  2. Дополнительная литература: [10] (гл. 5), [19] (гл.1-2), [21] (гл.7), [30] (гл.1).


Тема 5. Коалиции и влияние групп в парламенте.

Голосование с квотой. Индексы влияния. Индекс влияния Банцафа. Влияние стран в Совете Безопасности ООН. Анализ влияния групп и фракций в Государственной Думе Российской Федерации. Институциональный баланс власти в Совете министров расширенного Евросоюза. [Примеры других индексов влияния: индекс Шепли-Шубика, индекс Джонсона, индекс Дигена-Пакела, индекс Холера-Пакела]. Индексы влияния, учитывающие предпочтения участников.

Литература:

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

  2. Дополнительная литература: [6], [7], [21] (гл.6), [36].



Тема 6. Справедливый дележ.

Историческая постановка задачи. Процедура «дели и выбирай». Манипулирование при дележе. Критерии справедливости дележа. Процедура «подстраивающийся победитель» и ее свойства. Разрешение трудовых споров. Слияние фирм. Раздел имущества. Дележ при числе участников больше двух. Дележ при наличии неделимых пунктов. [Манипулирование при использовании процедуры «подстраивающийся победитель»].

Литература:

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

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


Тема7. Игровые модели.

Игры 2х2: стратегии, выигрыши, платежная матрица. Доминантные стратегии. Понятие равновесия игры по Нэшу. Примеры игр 2х2: дилемма заключенного и др. Примеры игр, имеющих равновесие по Нэшу, не имеющих его, а также имеющих бесконечно много равновесий.

Вероятность события и ожидаемый выигрыш. Смешанные стратегии. Теорема о существовании равновесия Нэша в смешанных стратегиях для любой игры 2х2. Ожидаемые полезности: правительство – профсоюзы. Фокальные равновесия.

Игры против природы. Как следует арендовать машины для уборки улиц?

Литература:

  1. Базовый учебник: [29] (c. 173-198).


Литература


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


  1. Алескеров Ф.Т., Хабина Э.Л., Шварц Д.А. Бинарные отношения, графы и

коллективные решения. – М.: Издательский дом ГУ ВШЭ, 2006.

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




  1. Айзерман М.А., Алескеров Ф.Т. «Выбор вариантов (основы теории)», М., Наука, 1990

  2. Алескеров Ф.Т. «Слияние фирм: анализ трех ключевых проблем», Финансовый бизнес, №6, 2002, 3-7

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

  4. Алескеров Ф.Т., Платонов В.В. «Системы пропорционального представительства и индексы представительности парламента», препринт ГУ-Высшая Школа Экономики, WP7/2003/05, Москва, 2003

  5. Алескеров Ф.Т., Благовещенский Н.Ю., Сатаров Г.А., Соколова А.В., Якуба В.И. "Оценка влияния групп и фракций в российском парламенте (1994 - 2003 гг.)", препринт ГУ Высшая Школа Экономики, WP7/2003/01, Москва, 2003

  6. Алескеров Ф.Т., Благовещенский Н.Ю., Константинов М.Л., Сатаров Г.А., Якуба В.И."О сбалансированности Государственной Думы Российской Федерации (1994-2003 гг.)", препринт ГУ Высшая Школа Экономики, WP7/2003/02, Москва, 2003

  7. Алескеров Ф.Т., Яновская Ю.М. «Применение теории справедливых решений к

трудовым спорам», Управление персоналом, №1, 2003, 59-61

  1. Басакер Р., Саати Т. Конечные графы и сети, М.: Наука,1974

  2. Берж К. Теория графов и ее приложения, М.:, ИЛ,1962

  3. Биркгоф Г. Теория решеток, М.: Наука, 1984

  4. Брамс С., Тейлор А. Делим по справедливости. М., СИНТЕГ, 2003

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

  6. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера, М.: Энергия, 1980

  7. Куратовский К., Мостовский А. Теория множеств, М.: Мир

  8. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов, М.: Наука, 1975

  9. Линдон Р. Заметки по логике, М.: Мир,1968

  10. Мендельсон Э. В. Ведение в математическую логику, М.: Наука, 1976

  11. Миркин Б.Г. Проблема группового выбора. М., Наука, 1974

  12. О.Оре Теория графов. М., Наука, 1968

  13. Робертс Ф. Дискретные математические модели. М., Наука, 1986

  14. Столл Р. Множество, логика, аксиоматические теории, М.: Просвещение, 1968

  15. Харари Ф.Теория графов, М.: Мир, 1973

  16. Хаусдорф Ф. Теория множеств, М.: ОНТИ, 1937

  17. Черч А. Введение в математическую логику, М.: Изд-во иностр.лит., 1961

  18. Шиханович Ю.А. Ведение в современную математику, М.: Наука, 1965

  19. Шрейдер Ю.А. Равенство, сходство, порядок, М.: Наука, 1971

  20. Яблонский С.В. Введение в дискретную математику, М.: Наука

  21. «Исследование операций в экономике» / под ред. Н.Ш. Кремера, М., Банки и биржи, 1997

  22. Aleskerov F. Arrovian Aggregation Models, Kluwer Academic Publishers, Dordercht, 1999

  23. Aleskerov F., Monjardet B. Utility Maximization, Choice and Preference, Springer-Verlag, Berlin, 2002

  24. Alkan, Ahmet. 1986. Nonexistence of stable threesome matchings Mathematical Social Sciences. 16, 207-9. (2)

  25. Biggs N.L. Discrete Mathematics, Oxford University Press, London, 2003

  26. Gale, David, and Lloyd Shapley. 1962. College admissions and the stability of marriage. American Mathematical Monthly, 69, 9-15. 12. 51

  27. Roth A., Sotomayor M.O. Two-sided matching, Cambridge University Press, 1990, Cambridge

  28. Алескеров Ф.Т., Благовещенский Н.Ю., Сатаров Г.А., Соколова А.В., Якуба В.И. Влияние и структурная устойчивость в Российском парламенте (1905—1917 и 1993—2005 гг.) М.: ФИЗМАТЛИТ, 2007.—312 с.



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


- текущий контроль: контроль правильности выполнения домашнего задания, учет активности на семинарах, а также возможность выполнения дополнительных нестандартных заданий;

- промежуточный контроль: контрольная работа по темам 1-4;

- итоговый контроль: письменный зачёт в конце 3-го модуля.


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



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

Перевод в 5-балльную шкалу осуществляется по правилу:


Оценка по 10-балльной шкале

Оценка по 5-балльной шкале

1


незачет

2

3

4



зачет

5

6

7

8

9

10



Типовой вариант контрольной работы

(темы 1 – 4 программы)

  1. Докажите, что .

  2. Пусть , и предпочтения участников имеют вид:

; ;

; ;

; ;

; .

Является ли устойчивым паросочетание

?

Ответ обоснуйте.

3. Пусть , и предпочтения участников имеют вид:

; ;

; ;

; ;

; .

;

Постройте паросочетания и .

4. Пусть А – непустое конечное множество, на котором задана функция полезности - множество неотрицательных действительных чисел. Бинарное отношение Р определим так, что , где - фиксированное положительное число. Какими свойствами обладает бинарное отношение Р?

5. Докажите, что бинарное отношение Р транзитивно, если и только если .

6. Приведите пример, показывающий, что отношение несравнимости для антирефлексивного связного полутранзитивного отношения не всегда удовлетворяет условию связности.

7. Постройте мажоритарный граф при следующих предпочтениях участников на множестве относительно кандидатов из множества :

;

;

;

.

Есть ли здесь победитель Кондорсе? Проанализируйте полученный результат.

8. Компания из трех человек выбирает вариант совместного проведения вечернего досуга. Ими рассматриваются четыре альтернативы: поход на дискотеку (D), поход в кино (С), поход в театр (Т), поход на модное фотобиеннале (F). Предпочтения участников имеют вид:







D

C

F

T

C

D

F

T

T

F

C

D


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


Типовой вариант зачетной работы

(темы 4 – 7 программы)


  1. Найдите максимальные внутренне устойчивые множества для слабого порядка. Как определить его число внутренней устойчивости?

  2. Найдите ядро изображенного графа или покажите, что оно не существует.



3. Найдите выигрывающие коалиции в голосовании с квотой (5; 2, 1, 1, 1, 1, 1, 1, 1) и подсчитайте для каждого из участников индекс Банцафа.

4. Совет директоров банка состоит из пяти человек P, A, B, C, D. Президент банка Р имеет три голоса, остальные члены совета директоров – по одному. Правило принятия решения – минимум пять голосов «за». Известно, что Р и вице-президенты А и В в силу определенных причин никогда не голосуют все вместе за одно решение. Найдите индексы влияния Банцафа для каждого члена совета директоров.

5. Для осуществления своей деятельности коммерческой фирме требуется арендовать офисные помещения в Москве. В процессе переговоров представитель фирмы и арендодатель обсуждают предложения по следующим вопросам: стоимость аренды 1 кв.м. площадей, величина арендуемых площадей, продолжительность аренды, финансовые вложения в текущий ремонт помещений, количество машиномест на парковке, предлагаемых фирме-арендатору. Оценки важности данных вопросов для каждой стороны представлены в таблице.

Пункты переговоров

Фирма

А

В

Стоимость аренды 1 кв.м.

10

20

Величина арендуемых площадей

30

30

Продолжительность аренды

10

20

Вложения в текущий ремонт

20

10

Количество машиномест на парковке

30

20

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

6. Пусть две фирмы «Лакомка» и «Сладкоежка» производят шоколад. Количество покупателей этого шоколада делится примерно поровну. Если компании не рекламируют свой товар, то прибыли фирм равны и составляют по 100 тыс. руб. На рекламу может быть потрачено 20 тыс. руб., причем, если обе фирмы тратятся на рекламу, их доходы увеличиваются на10 тыс. руб., соответственно, прибыль составляет 90 тыс. руб.Если одна фирма тратится на рекламу, а другая – нет, то прибыль первой фирмы составит 140 тыс. руб., а второй – только 60 тыс. руб.

Составьте платежную матрицу данной игры. Найдите все равновесия Нэша в чистых стратегиях. Будут ли они Парето-оптимальными?

7. Найдите равновесия Нэша как в чистых, так и в смешанных стратегиях, в игре заданной следующей матрицей выигрышей:

(3, 1)

(0, 1)

(1, 1)

(2, 2)


Базовый учебник [1] содержит более 100 задач, которые могут быть использованы для проверки качества усвоения курса студентами.


Автор программы: Ф.Т. Алескеров


Ф.Т.Алескеров


Похожие:

Программа дисциплины дискретные математические модели iconПрограмма дисциплины дискретные математические модели для направления 080100. 62 «Экономика»
Требования к студентам: Изучение курса "Дискретные математические модели" не требует предварительных знаний, выходящих за пределы...
Программа дисциплины дискретные математические модели iconПрограмма наименование дисциплины: Дискретные математические модели
Магистерская специализация «Математическое моделирование оптических наноструктур»
Программа дисциплины дискретные математические модели iconПримерная программа наименование дисциплины
Эконометрика, Математический анализ, Микроэкономика, Макроэкономика, Дифференциальные и разностные уравнения, Дискретные математические...
Программа дисциплины дискретные математические модели iconПрограмма курса «дискретные задачи принятия решений»
Математические модели. Дискретные экстремальные задачи. Системы поддержки принятия решений
Программа дисциплины дискретные математические модели iconПрограмма: Магистратура
Модели линейной алгебры и их применения. Математические модели в аналитической геометрии. Модели использования теории математического...
Программа дисциплины дискретные математические модели iconМетодические указания по изучению теоретической части Чебоксары 2009 г
Общие сведения о сигналах и помехах, их математические модели; непрерывные и дискретные каналы связи, их математические модели; преобразование...
Программа дисциплины дискретные математические модели iconПрограмма наименование дисциплины: Дискретные и вероятностные модели
Задачей дисциплины является формирование у студентов понимания проблематики математического моделирования объектов информационно-телекоммуникационных...
Программа дисциплины дискретные математические модели iconРабочая программа дисциплины «Дискретные динамические системы»
ОД. А. 09; цикл од. А. 00 «Дисциплины по выбору аспиранта» основной образовательной программы подготовки аспиранта по отрасли 010000...
Программа дисциплины дискретные математические модели iconПрограмма дисциплины «Экономико-математические методы и модели в логистике» По направлению 080500. 62 080200. 62 "Менеджмент", профиль специальных дисциплин "Логистика и управление цепями поставок"
...
Программа дисциплины дискретные математические модели iconПрограмма дисциплины Модели финансовых рынков для направления 080100. 62- экономика подготовки бакалавров Автор программы
Программа «Модели финансовых рынков» предназначена для студентов 4 курса бакалавриата специализации «математические методы анализа...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница