На контрольной работе студент должен продемонстрировать умение решать задач нелинейного программирования с использованием условий Куна-Таккера.
При выполнении первого домашнего задания студент должен проявить умение формулировать проблемы экономического и социального содержания, строить математические модели этих проблем и отыскивать их решение.
На зачете студент должен продемонстрировать знания и умения в области решения задач математического программирования, в том числе уметь доказывать несложные утверждения из первых двух разделов курса.
При выполнении второго домашнего задания студент должен продемонстрировать навыки решения задач линейного программирования с помощью вычислительной техники, а также проводить анализ чувствительности решения к изменению ограничений в условиях задачи.
На экзамене студент должен проявить умение решать задачи оптимизации в условиях неопределенности, многокритериальные задачи и задачи динамического программирования с использованием метода Беллмана.
Содержание дисциплины
Тема I. Введение. Математические модели и оптимизация в экономике. Общее представление о статической задаче оптимизации
Математические модели в экономике. Примеры: модели поведения потребителя и планирования производства в фирме. Пример использования оптимизации для идентификации параметров математической модели.
Использование математических моделей для описания поведения экономических агентов. Рациональное поведение. Использование оптимизации как способа описания рационального поведения. Принятие экономических решений. Теория оптимизации и методы выбора экономических решений. Применение оптимизации в системах поддержки принятия решений.
Основные представления о статической задаче оптимизации. Инструментальные переменные и параметры математической модели. Допустимое множество. Критерий выбора решения и целевая функция. Линии уровня целевой функции. Формулировка детерминированной статической задачи оптимизации. Неопределенность в параметрах и ее влияние на решение.
Глобальный максимум и локальные максимумы. Достаточное условие существования глобального максимума (теорема Вейерштрасса). Причины отсутствия оптимального решения. Максимумы во внутренних и граничных точках допустимого множества.
Основная литература.
1. Соколов А.В., Токарев В.В. Методы оптимальных решений. М.: Физматлит, 2010.(тема 3)
2. Интрилигатор М. Математические методы оптимизации и экономическая теория. М.: Изд. Айрис-Пресс, 2002. (гл. 1-2)
Дополнительная литература.
2. Иванилов Ю.П., Лотов А.В. Математические модели в экономике. М.: Наука, 1979.
3. Лотов А.В. Введение в экономико-математическое моделирование. М.: Издательство «Наука», 1984.
4. Хазанова Л.Э. Математические методы в экономике. Учебное пособие. М.: Изд. БЕК, 2002.
Тема II. Задача нелинейного программирования
Общая задача нелинейного программирования (НЛП). Задача НЛП и классическая задача условной оптимизации. Условия Куна-Таккера в геометрической форме как необходимые условия локальной оптимальности. Условие дополняющей нежесткости. Условия Куна-Таккера в алгебраической форме. Функция Лагранжа для задачи НЛП. Седловая точка функции Лагранжа. Достаточное условие оптимальности в общей задаче НЛП.
Выпуклые задачи оптимизации. Основные понятия геометрии многомерного линейного пространства. Выпуклые множества. Примеры выпуклых множеств. Опорная гиперплоскость. Разделяющая гиперплоскость. Теорема об отделимости выпуклых множеств. Выпуклые и вогнутые функции. Строгая выпуклость. Надграфик выпуклой функции. Условия выпуклости и вогнутости функций. Свойства выпуклых функций. Теоремы о локальном максимуме в выпуклом случае.
Формулировка выпуклой задачи НЛП. Теорема Куна-Таккера. Условия Куна-Таккера как необходимые и достаточные условия оптимальности. Экономическая интерпретация множителей Лагранжа. Зависимость решения от параметров.
Основная литература.
1. Соколов А.В., Токарев В.В. Методы оптимальных решений. М.: Физматлит, 2010.(тема 4)
2. Интрилигатор М. Математические методы оптимизации и экономическая теория. М.: Изд. Айрис-Пресс, 2002. (гл. 4)
Дополнительная литература.
1. Васильев Ф.П. Методы оптимизации. М.: Издательство «Факториал», 2001.
2. Васильев Ф.П. Численные методы решения экстремальных задач. М.: Наука, 1988.
3. Габасов Р., Кириллова Ф.М. Методы оптимизации. Минск: Изд. БГУ, 1975.
4. Моисеев Н.Н., Иванилов Ю.П., Столярова Е.Н. Методы оптимизации. М.: Наука, 1978.
Тема III. Задача линейного программирования
Формулировка задачи линейного программирования (ЛП). Примеры задач ЛП. Стандартная (нормальная) и каноническая формы представления задачи ЛП и сведение к ним.
Свойства допустимого множества и оптимального решения в задаче ЛП. Основные представления о методах решения задач ЛП, основанных на направленном переборе вершин (симплекс-метод и др.).
Функция Лагранжа и условия Куна-Таккера в задаче ЛП. Двойственные задачи линейного программирования. Теоремы двойственности. Интерпретация двойственных переменных. Анализ чувствительности оптимального решения к параметрам задачи линейного программирования.
Некоторые специальные задачи линейного программирования (транспортная, производственно-транспортная и т.д.).
Основная литература.
1. Соколов А.В., Токарев В.В. Методы оптимальных решений. М.: Физматлит, 2010.(тема 5)
2. Интрилигатор М. Математические методы оптимизации и экономическая теория. М.: Изд. Айрис-Пресс, 2002. (гл. 5)
3. Вентцель Е.С. Исследование операций. Задачи, принципы, методология. М.: Высшая школа, 2001. (гл. 3)
Дополнительная литература.
1. Габасов Р., Кириллова Ф.М. Методы оптимизации. Минск: Изд. БГУ, 1975.
2. Хазанова Л.Э. Математические методы в экономике. Учебное пособие. М.: Изд. БЕК, 2002.
3. Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом образовании. М.: Изд. ДЕЛО, 2003.
Компьютерные методы оптимизации
Градиентные методы в задаче безусловной оптимизации. Метод Ньютона. Методы штрафных функций в задачах линейного и нелинейного программирования. Линейное программирование в среде MS Excel.
Основные представления о методах оптимизации в невыпуклом случае. Целочисленные задачи линейного программирования.
Основная литература.
1. Соколов А.В., Токарев В.В. Методы оптимальных решений. М.: Физматлит, 2010.(тема 4, п.8, тема 5, п.9, тема 6)
2. Интрилигатор М. Математические методы оптимизации и экономическая теория. М.: Изд. Айрис-Пресс, 2002. (гл. 4, 5)
3. Вентцель Е.С. Исследование операций. Задачи, принципы, методология. М.: Высшая школа, 2001. (гл. 3).
Дополнительная литература.
1. Васильев Ф.П. Методы оптимизации. М.: Издательство «Факториал», 2001.
2. Моисеев Н.Н., Иванилов Ю.П., Столярова Е.Н. Методы оптимизации. М.: Наука, 1978.
3. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983.
4. Fletcher R. (2000) Practical methods of Optimization. Wiley.
5. Rardin R.L. (1997) Optimization in Operations Research. Prentice Hall.
6. Walsey L.A. (1998) Integer Programming. Wiley.
Тема IV. Оптимизация в условиях неопределенности
Задача выбора решений в условиях неопределенности. Критерии выбора решений в условиях неопределенности (принцип гарантированного результата, критерий Гурвица, критерий Байеса-Лапласа, критерий Сэвиджа). Применение принципа гарантированного результата в задачах экономического планирования. Множество допустимых гарантирующих программ. Наилучшая гарантирующая программа.
Принятие решение при случайных параметрах. Вероятностная информация о параметрах. Принятие решений на основе математического ожидания. Случайность и риск. Учет склонности к риску.
Основная литература.
1. Токарев В.В. Методы оптимальных решений, т.2. М.: Физматлит, 2010. (тема, 10 п.1, п. 4, тема 11, п.1)
2. Глухов В.В., Медников М.Д., Коробко С.Б. Математические методы и модели для менеджмента. СПб.: Лань, 2000. (гл. 8, 9)
Дополнительная литература.
1. Райфа Г. Анализ решений. М.: Наука, 1977.
2. Clemen, R.T. (1996) Making Hard Decisions. Belmont: Duxbury Press.
Тема V. Основные понятия многокритериальной оптимизации
Происхождение и постановка задачи многокритериальной оптимизации. Пример: задача поиска разумных экономических решений с учетом экологических факторов. Множество достижимых критериальных векторов. Доминирование и оптимальность по Парето. Эффективные решения и паретова граница. Теорема Куна-Таккера в выпуклых задачах многокритериальной оптимизации.
Понятие лица, принимающего решение. Основные типы методов решения задач многокритериальной оптимизации. Методы аппроксимации паретовой границы.
Основная литература.
1. Токарев В.В. Методы оптимальных решений, т.2. М.: Физматлит, 2010. (тема 7)
2. Вентцель Е.С. Исследование операций. Задачи, принципы, методология. М.: Высшая школа, 2001. (гл. 2, § 6)
Дополнительная литература.
1. Ларичев О.И. Теория и методы принятия решений. М.: Логос, 2000.
2. Лотов А.В. Введение в экономико-математическое моделирование. М.: Издательство «Наука», 1984.
3. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М.: Наука, 1982.
4. Штойер Р. Многокритериальная оптимизация: теория, вычисления и приложения. М.: Радио и связь, 1992.
5. Lotov A.V., Bushenkov V.A., and Kamenev G.K. (2004) Interactive Decision Maps. Approximation and Visualization of Pareto Frontier. Kluwer Academic Publishers.
6. Miettinen K. (1999) Nonlinear multi-objective optimization. Kluwer Academic Publishers.
Тема VI. Оптимизация динамических систем
Динамические задачи оптимизации. Примеры: простейшая динамическая модель производства и задача поиска оптимальной производственной программы. Многошаговые и непрерывные модели. Управление и переменная состояния в динамических моделях. Задание критерия в динамических задачах оптимизации. Принципы построения динамического управления: построение программной траектории и использование обратной связи. Задача построения программной траектории как задача математического программирования (в конечномерном или бесконечномерном пространстве).
Динамическое программирование в многошаговых задачах оптимизации. Принцип оптимальности. Функция Беллмана. Уравнение Беллмана в многошаговых задачах оптимизации. Решение задач динамического программирования.
Основная литература.
1. Токарев В.В. Методы оптимальных решений, т.2. М.: Физматлит, 2010. (тема 9)
2. Интрилигатор М. Математические методы оптимизации и экономическая теория. М.: Изд. Айрис-Пресс, 2002. (гл. 11-13)
3. Вентцель Е.С. Исследование операций. Задачи, принципы, методология. М.: Высшая школа, 2001. (гл. 4)
Дополнительная литература.
1. Беллман Р., Калаба Р. Динамическое программирование и современная теория управления. М.: Наука, 1969.
2. Благодатских В.И. Введение в оптимальное управление. М.: Высшая школа, 2001.
3. Габасов Р., Кириллова Ф.М. Методы оптимизации. Минск: Изд. БГУ, 1975.
4. Пропой А.И. Элементы теории оптимальных дискретных процессов. М.: Наука, 1973.
5. Хазанова Л.Э. Математические методы в экономике. Учебное пособие. М.: Изд. БЕК, 2002.
6. Kamien, M.I., Schwarz, N.L. (1981) Dynamic optimization. The calculus of variations and optimal control in economics and management. New York: Elsevier.
7. Bryson A.E. (2002) Applied linear optimal control: examples and algorithms. Cambridge Univ. Press.
8. Denardo E.V. (2003) Dynamic Programming: Models and Applications. Dover Publ.