Примеры контрольных работ.

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

 

Национальный исследовательский университет-

Высшая школа экономики

 

Факультет мировой экономики

 

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

 

 

Методы оптимальных решений

 

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

 

 

Авторы программы: Ф. Т. Алескеров, К. С. Сорокин, С.Г. Кисельгоф

 

 

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

_________________________ высшей математики

на факультете экономики

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

 

_____________ __________ _____________ Ф.Т. Алескеров ________________

" __" __________ 20__ г. " __ " ______________ 20__ г.

 

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

_____________

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

 

_______________ ______________

" __ " _________ 20__ г.

Москва

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

 

Требования к студентам

Учебная дисциплина “Методы оптимальных решений” (2, 3, 4-й модули учебного плана 2-го курса факультета экономики) опирается на предшествующие ей дисциплины «Математика» и «Линейная алгебра» (1-2 модули учебного плана 1-го курса).

 

Аннотация

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

 

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

 

Программа курса предусматривает лекции (42 часа), семинарские и практические занятия (42 часа).

 

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

 

Учебная задача дисциплины

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

- знать и основные математические методы анализа принятия решения;

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

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

 

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

 

№	Наименование темы	Всего часов	Аудиторные часы	Самост. работа
лекции	практ. зан.
Первый модуль
	Введение. Математические методы и модели в принятии решений
	Линейные оптимизационные модели и линейное программирование
Всего
Второй модуль
	Нелинейные оптимизационные модели и нелинейное программирование
	Целочисленная оптимизация. Оптимизация на графах
	Оценка эффективности организационных единиц
	Многокритериальное принятие решений
Всего
Третий модуль
	Паросочетания и обобщенные паросочетания
	Коллективное принятие решений, голосования
	Коалиции и влияние групп в парламенте
	Задача дележа
Всего
Итого

 

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

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

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

- промежуточный контроль: контрольные работы в конце 1-го и 2-го модулей;

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

 

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

оценок по 10-бальной шкале за первую контрольную работу , вторую контрольную работу и экзамен , с последующим округлением до целого числа баллов.

 

На основании результатов текущего контроля за каждый модуль для каждого студента формируется сумма бонусных баллов, которая добавляется к результатам контрольной работы за этот модуль (экзаменационной работы в случае третьего модуля), если оценка за контрольную работу составляет 4 балла или выше. Если оценка за контрольную (экзаменационную) работу составляет 3 балла и ниже, бонусные баллы не добавляются.

 

 

Таблица соответствия оценок по десятибалльной и пятибалльной системам.

Оценка по 10-балльной шкале	Оценка по 5-балльной шкале
	Неудовлетворительно
	Удовлетворительно
	Хорошо
	Отлично

 

 

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

 

Тема 1. Введение. Математические методы и модели в принятии решений.

 

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

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

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

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

Литература.

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

Дополнительная литература: [5], [7], [10], [13], [14], [18].

 

Тема 2. Линейные оптимизационные модели и линейное программирование.

 

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

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

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

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

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

Литература.

Базовый учебник: [1].

Дополнительная литература: [4], [5], [9], [14].

 

Тема 3. Нелинейные оптимизационные модели, нелинейное программирование.

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

Прямые методы решения нелинейных оптимизационных задач. Градиентный метод.

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

Литература.

Базовый учебник: [1].

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

 

Тема 4. Целочисленная оптимизация. Оптимизация на графах.

 

Целочисленное программирование. Методы решения задач целочисленного программирования.

 

Транспортные задачи линейного программирования. Задача о назначении. Задача о выборе кратчайшего пути. Метод потенциалов. Теорема о целочисленности решения.

 

Понятие о графе. Ориентированный граф. Граф транспортной сети. Задача о максимальном потоке в сети. Сведение к задаче линейного программирования. Связь с транспортной задачей в матричной постановке. Алгоритм Форда-Фалкерсона для отыскания максимального потока.

 

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

Литература.

Базовый учебник: [1].

Дополнительная литература: [5], [10], [11], [12], [13], [21].

 

Тема 5. Модели оценки эффективности организационных единиц.

 

Задача оценки эффективности однотипных самостоятельных организационных (управленческих) единиц (ОЕ). Примеры из экономики и менеджмента. Анализ оболочек данных. Составные ОЕ. Множество производственных возможностей и его эффективная граница. Эффективность ОЕ по входам и выходам. Эффективные и неэффективные ОЕ. Оценка эффективности ОЕ при постоянной отдаче от масштаба производства. Обобщение удельных критериев эффективности на многомерный случай. Мультипликативная модель оценки эффективности ОЕ: дробно-линейная задача и связанная с ней пара двойственных задач линейного программирования. Использование результатов анализа оболочек данных для выработки рекомендаций по улучшению работы неэффективных ОЕ.

Литература.

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

Тема 6. Многокритериальное принятие решений.

 

Понятие о многокритериальной оптимизации. Причины многокритериальности, примеры многокритериальных задач. Пространство решений и пространство оценок. Доминирование и оптимальность по Парето и Слейтеру. Роль понятия Парето-оптимальности в принятии решений.

Достаточные условия оптимальности по Парето и Слейтеру в форме свертки критериев в один обобщенный критерий. Коэффициенты важности в линейных свертках.

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

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

Литература.

Базовый учебник: [2].

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

 

Тема 7. Паросочетания и обобщенные паросочетания.

 

Понятие о двудольном графе. Задача о распределении работ. Задача о свадьбах. Паросочетания. Совершенные и максимальные паросочетания. Условие Холла. Чередующиеся цепи. Трансверсали семейства множеств.

 

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

 

Литература.

Базовый учебник: [3].

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

 

Тема 8. Коллективное принятие решений, задача голосования.

 

Процедуры выработки коллективных решений. Правило простого большинства. Парадокс Кондорсе. Правило Борда. Внутренняя и внешняя устойчивость. Ядро. Некоторые нелокальные правила принятия решений.

 

Парадокс Эрроу. Манипулирование и стратегическое поведение участников при голосовании.

Литература.

Базовый учебник: [3].

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

 

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

Голосование с квотой. Индексы влияния. Индекс влияния Банцафа. Влияние стран в Совете Безопасности ООН. Институциональный баланс власти в Совете министров расширенного Евросоюза. Примеры других индексов влияния.

 

Литература.

Базовый учебник: [3].

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

Тема 10. Задача дележа.

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

 

Литература.

Базовый учебник: [3].

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

Литература

 

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

 

1. А.В. Соколов, В.В. Токарев. Методы оптимальных решений. Т.1. Общие положения. Математическое программирование. Москва: ФИЗМАТЛИТ, 2010.
2. А.В. Соколов, В.В. Токарев. Методы оптимальных решений. Т.2. Многокритериальность. Динамика. Неопределенность. Москва: ФИЗМАТЛИТ, 2010.
3. Ф.Т. Алескеров, Э.Л. Хабина, Д.А. Шварц. Бинарные отношения, графы и коллективные решения. М: Издательский дом ГУ-ВШЭ, 2006

 

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

 

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

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

1. М. Интрилигатор. Математические методы оптимизации и экономическая теория. М.: Изд. Айрис-Пресс, 2002.
2. Х. А. Таха. Введение в исследование операций. М.: Издательский дом «Вильямс», 2005.

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

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

10. Г. Вагнер. Основы исследования операций. М.:Мир, 1972 Т.1

11. Г. Вагнер. Основы исследования операций. М.:Мир, 1973 Т.2

12. Л. Р. Форд, Д. Р. Фалкерсон. Потоки в сетях. М.: Мир, 1966.

13. Исследование операций в экономике. Под ред. Кремера Н.Ш. М.: ЮНИТИ, 2005.

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

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

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

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

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

1. В.Е. Кривоножко и др. Анализ эффективности функционирования сложных систем. // Автоматизация проектирования. 1999. № 1. С. 2 – 7.
2. R. Banker, A. Charnes, W.W. Cooper, J. Swaris, D.A. Thomas. An introduction to data envelopment analysis with some of its models and there uses. // Research in governmental and nonprofit accounting, 1989 / V. 5. P. 125 – 163.
3. О. Оре. Теория графов. М.: Наука. 1968.
4. К. Берж. Теория графов и ее приложения. М.: ИЛ.1962.
5. Б.Г. Миркин. Проблема группового выбора. М.: Наука. 1974.
6. Ф.Т. Алескеров, П. Ортешук. Выборы. Голосование. Партии. М.: Академия, 1995.
7. С. Брамс, А. Тейлор. Делим по справедливости. М.: СИНТЕГ. 2003.

 

Примеры контрольных работ.

 

Контрольная работа 1. (Темы 1 и 2.)

 

1. На производство поступила достаточно большая партия стержней длиной 250 и 190 см. Нужно получить 470 заготовок длиной 120 см. и 450 заготовок длиной 80. Отходы должны быть минимизированы. Построить математическую модель данной задачи.

 

2. Найти максимум функции F = x₁+x₂ при условиях: 2x₁+4x₂ ≤ 16, -4x₁+2x₂ ≤ 8, x₁+3x₂ ≥ 9, x₁,x₂ ≥0. Обосновать.

 

3. Найти максимум функции F = 2x₁+x₂-x₃+x₄ -x₅ при условиях x₁+x₂+x₅=5, 2x₁+x₂+x₄= 9, x₁+2x₂+x₅=7, x₁,x₂,x₃,x₄ ,x₅≥0. Указание: использовать симплекс метод.

 

4.Для производства продукции трёх видов A, B, C используются три различных вида сырья. Каждый из видов сырья может быть использован в объёме не большем, чем 180, 210 и 236 кг. соответственно. Нормы затрат каждого из видов сырья на 1 кг. продукции данного вида и цена единицы продукции каждого вида приведены в таблице:

Вид сырья	Нормы затрат сырья на единицу продукции
Изделие A	Изделие B	Изделие C
I
II
III
Цена 1 кг. продукции (т.р.)

 

Потратив 50 т.р. фирма может открыть производство 4-го вида продукции, нормы затрат сырья на единицу которого составляют 2, 4 и 3 кг. соответственно, а цена 1 кг. равна 18 т.р. При этом функциональность старых линий производства не нарушается. Определить, окупится ли открытие новой линии производства при таких предположениях.

 

5. Дана задача линейного программирования f(x) = ‹c,x› →max, c = (c₁,...,c_n), Ax=b, b=(b₁,...,b_m). Доказать, что если эта задача имеет решение (f* < +∞), то f(x)=const для любых допустимых x.

Контрольная работа 2. (Темы 3,4,5,6)

1. Характеристики ОЕ с одним входом и одним выходом заданы таблицей:

 

ОЕ
x
y

 

· представить МПВ графически;

· выделить эффективные и неэффективные ОЕ;

· рассчитать графическим методом эффективность по входу и выходу для одной неэффективной ОЕ

 

2. Найти максимум функции f(x,y)=xy при ограничениях (x-2)²+(y-3)²≤ 1.

 

3. Дана функция f(x,y) = x²-xy+y²+x-y и начальная точка x₀=0, y₀ = 0. Сделать два шага по методу градиентного спуска при том, что α₀=½.

 

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

 

5. Пусть X – некоторое выпуклое множество в конечномерном пространстве Rⁿ, а f(x) – выпуклая непрерывно-дифференцируемая функция, определённая на всём Rⁿ. Доказать, что выполнение для некоторого x₀ из X и любых x из X неравенства ‹f'(x₀), x-x₀›≥0 является необходимым и достаточным условием того, что в x₀ достигается глобальный минимум функции f(x) на множестве X.

Экзаменационная работа (Темы 7, 8, 9, 10).

1. Рассмотрим ситуацию, возникающую при слиянии двух фирм А и В. Их оценки относительно обсуждающихся в ходе переговоров вопросов показаны в таблице.

 

Пункты переговоров	Фирма
А	В
Название фирмы
Местонахождение штаб-квартиры
Назначение президента
Назначение исполнительного директора
Увольнение персонала

 

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

 

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

;

;

;

.

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

 

3. Пусть , где , и . Найдите максимальное паросочетание в G, пользуясь алгоритмом его построения.

 

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

 

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