Номера задач из "упражнений" указаны в таблице ниже



страница1/26
Дата04.05.2016
Размер1.06 Mb.
  1   2   3   4   5   6   7   8   9   ...   26
Номера задач из “упражнений” указаны в таблице ниже.

Тексты “упражнений” приведены в конце каждой лекции. Ссылки на них указаны в содержании.








Лекция




1.1.

1.2.

1.3.

1.4.

1.5.

2.1.

2.2.

2.3.

2.4.

Вариант 1

1

5

1

4

1

1(1)

2(1)

3(1)

1(1)

1(4)

1(1)

2

1

6

1

6

1

КУРС

Оптимизация и основы теории принятия решений

СОДЕРЖАНИЕ



Раздел 1. Основы теории оптимизации 3

Лекция 1.1. Введение в теорию оптимизации. 3

Введение. 3

Примеры моделей, приводящих к задачам линейного программирования 5

1. Задача о диете 5

2. Классическая транспортная задача 8

3. Задача линейного раскроя 9

Общая схема моделирования 14

Канонические формы задач линейного программирования 16

Контрольные вопросы 19

Упражнения 19

Лекция 1.2. Двойственная задача. Признак оптимальности. 20

Двойственная задача. 20

Признак оптимальности. 22

Геометрическая интерпретация двойственности 24

Контрольные вопросы 26

Упражнения 26



Лекция 1.3. Метод последовательного улучшения 27

Общая идея метода последовательного улучшения 27

Процедура одного шага метода последовательного улучшения 29

Построение начального базисного множества 32

Контрольные вопросы 36

Упражнения 37



Лекция 1.4. Общая схема метода последовательного улучшения 37

Крайние точки выпуклых множеств 38

Схема метода последовательного улучшения для задач с общей системой ограничений 39

Теорема двойственности 42

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

Контрольные вопросы 46

Упражнения 47

Лекция 1.5. Нелинейное программирование. Теоремы Куна — Таккера. 49

Выпуклые функции. Субградиент выпуклой функции 49

Применение в анализе решений задач линейного программирования 52

Задачи выпуклой оптимизации 53

Задачи выпуклого программирования 54

Критерии оптимальности в задачах выпуклого программирования 56

Контрольные вопросы 58

Упражнения 59



Список литературы 59

Раздел 2. Основы теории принятия решений 60

Лекция 2.1. Введение.Теория игр и теория принятия решений 60

Теория игр и проблема выбора 60

Рациональность 62

Предпочтения и выбор в простой ситуации 63

Контрольные вопросы 66

Упражнения 67



Лекция 2.2. Принятие решений в детерминированных условиях 67

Одномерная оптимизация 67

Принятие решений в динамике, дерево решений 68

Межвременные предпочтения и дисконтирование 71

Контрольные вопросы 72

Упражнения 72



Лекция 2.3. Принятие решений при риске 74

Лотереи 75

Ожидаемая полезность (функция полезности фон Неймана—Моргенштерна) 76

Отношение к риску 78

Сложные и простые лотереи 80

Санкт-петербургский парадокс 80

Свертывание дерева решений с лотереями 81

Принятие решений при риске (непрерывный случай) 85

Рандомизация, смешанные стратегии 86

Контрольные вопросы 87

Упражнения 88

Лекция 2.4. Байесовское принятие решений 89

Решение о зонте 89

Разведка нефти 90

Контрольные вопросы 94

Упражнения 94

Список литературы 95



Раздел 1. Основы теории оптимизации

Лекция 1.1. Введение в теорию оптимизации.

Введение.


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

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



,

т.е. требуется минимизировать значение некоторой функции f на множестве W, являющемся частью евклидова пространства Rn. Наиболее простой частный случай этой задачи, когда f — дифференцируемая функция, a W — открытое множество (например, W = Rn), изучается в курсе математического анализа и для R1 известен уже школьникам. В этом случае речь идет об использовании теоремы Ферма, дающей необходимое условие оптимума в виде равенства нулю значения производной функции f.

В математическом анализе изучается и другой частный случай указанной проблемы, когда W задается как множество решений некоторой системы уравнений вида

,

где fi — также дифференцируемые функции. Это классические задачи на условный экстремум, и в этом случае применяется известное правило множителей Лагранжа, формально сводящее вопрос к прежнему случаю переходом к функции , гдеyi — новые переменные,которые и называются множителями Лагранжа.

Собственно задачи математического программирования, которые условно можно было бы назвать «неклассическими» задачами на условный экстремум, отличаются от «классических» тем, что уравнения заменяются неравенствами.

Следует отметить, что математическая база для исследования этого нового класса задач на условный экстремум получена еще в начале XX столетия. Так, лемма Фаркаша, лежащая в основе теории линейных задач математического программирования (линейного программирования), получена уже в 1902 г. Появление нового раздела в теории оптимизации «запаздывало» ввиду отсутствия социального заказа. Именно потребности экономических исследований и явились заказом такого рода. Можно сказать, что своим рождением математическое программирование обязано экономике.

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

В 30-х годах В. В. Леонтьев начал изучать линейные балансовые модели применительно к экономике Америки.

Датой рождения линейного программирования, по-видимому, следует считать 1939 г., когда вышла монография Л. В. Канторовича «Математические методы организации и планирования производства». В этой работе Л. В. Канторович уже отчетливо обозначил основные направления развития нового раздела прикладной математики, получившего в дальнейшем название «линейное программирование». На примерах конкретных моделей Л. В. Канторович показал эффективность разработанного им метода для решения различных задач практического планирования (задача о распределении программы, задача рационального раскроя, распределение грузов по нескольким видам транспорта и т. п.). Сам метод, названный автором методом разрешающих множителей, фактически использовал основные элементы возникшей позже теории двойственности. В том же году А. И. Толстой опубликовал статью «Методы устранения нерациональных перевозок при планировании», в которой намечает пути исследования широко известной теперь транспортной задачи.

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

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

Работы Л. В. Канторовича получили высокую оценку мировой научной общественности — в 1975 г. ему была присуждена Нобелевская премия по экономике.


  1   2   3   4   5   6   7   8   9   ...   26


База данных защищена авторским правом ©bezogr.ru 2016
обратиться к администрации

    Главная страница