Министерство Образования Российской Федерации

Московский государственный университет экономики,

статистики и информатики

И.Н. Мастяева

О.Н. Семенихина

Методы оптимизации

Линейные и нелинейные методы и модели в экономике.

М осква 2010

II часть. Нелинейные методы и модели в экономике.

Введение…………………………………………………………………………..2

Глава 6. Постановки задачи нелинейного программирования (знп) и основные определения…………………………...3

6.1. Задача математического программирования (ЗМП) и ее постановки………………………………………………………..3

6.2. Основные определения……………………………………………………...4

6.3. Классификация ЗНП……..………………………………………………….7

6.4. Классическая оптимизация…………………………………………………8

Глава 7. Задача одномерной оптимизации…………………………………….13

7.1. Постановки задачи. Основные понятия...…………………..…………….13

7.2.Поиск отрезка, содержащего точку максимума. Алгоритм Свенна……..16

7.3. Методы нулевого порядка…………………………………………………18

7.4. Методы первого порядка…………………………………………………..26

7.5. Методы второго порядка…………………………………………………..31

Глава 8. Графический метод решения знп…………………………………...33

8.1. Алгоритм графического метода решения ЗНП…………………………..33

8.2. Примеры (эллипс, парабола, гипербола)…………………………………34

Глав 9. Выпуклый анализ………………………………………………………46

9.1. Определения………………………………………………………………..46

9.2. Свойства вогнутых (выпуклых) функций………………………………..46

9.3. Критерии вогнутости (выпуклости) гладких функций………………….49

9.4. Экстремальные свойства вогнутых (выпуклых) функций……………...52

9.5. Сильно вогнутые (выпуклые) функции………………………………….54

Глава 10. Выпуклое программирование……………………………………....62

10.1. Постановка задачи………………………………………………………..62

10.2. Функция Лагранжа. Седловая точка функции Лагранжа, условия ее существования……………………………………………………..63

10.3. Достаточные условия оптимальности………………………………….67

10.4. Условия регулярности выпуклого множества………………………….68

10.5. Теорема Куна-Таккера. Общий случай…………………………………68

10.6. Теорема Куна-Таккера. Случай линейных ограничений……………...70

Глава 11. Квадратичное программирование…………………………………74

11.1 Постановка задачи квадратичного программирования (ЗКП)…………………………………………………………..74

11.2. Применение теории Куна-Таккера к решению ЗКП…………………..75

11.3. Примеры………………………………………………………………….77

Глава 12. Задача безусловной оптимизации (збо)…………………………………………………………………..81

12.1. Постановка задачи……………………………………………………….81

12.2. Методы нулевого порядка (прямого поиска)…………………………..83

12.3. Методы первого и второго порядков………………………………….103

12.4. Методы, использующие сопряженные направления…………………110

Глава 13. Задача условной оптимизации (зуо)……………………….……127

13.1. Постановка задачи. Классификация методов………………………...127

13.2. Методы возможных направлений……………………………………..133

Введение.

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

В данном разделе рассматриваются методы решения задачи нелинейного программирования в одномерном случае (методы одномерной оптимизации), методы решения нелинейной задачи безусловной (в отсутствии ограничений) и условной оптимизации.

Глава 6.

Постановки задачи нелинейного программирования (ЗНП) и основные определения.

6.1. Задача нелинейного программирования (знп) и ее постановки.

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

В зависимости от свойств функции и множества X в ЗМП рассматривают различные классы задач: задачу линейного программирования, задачу нелинейного программирования (ЗНП), задачу выпуклого программирования (см. главу 10), задачу квадратичного программирования (см.главу 11), задачу целочисленного программирования, задачу стохастического программирования, задачу динамического программирования и т.д.

Определение 6.1. Общей задачей нелинейного программирования назовем следующую задачу:

(6.1)

(6.2)

(6.3)

(6.4)

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

В постановке ЗНП не принято выделять ограничения неотрицательности (если они есть), в отличие от ЗЛП.

Пример 6.1.

Найти минимальное значение функции:

при условиях:

Пример 6.2.

Найти максимальное значение функции:

при условиях: