- •Введение
- •Тема 1 Математическое программирование и оптимизация
- •1.1 Эволюция развития математических методов и моделей в экономике
- •1.2 Классификация экономико-математических моделей
- •1.3 Математическое программирование
- •1.4 Оптимизация в математике и ее методы
- •1.5 Метод Монте-Карло
- •1.5.1 Алгоритм Бюффона для определения числа Пи
- •1.5.2 Связь стохастических процессов и дифференциальных уравнений
- •1.5.3 Рождение метода Монте-Карло в Лос-Аламосе
- •1.5.4 Дальнейшее развитие и современность
- •1.5.5 Интегрирование методом Монте-Карло
- •1.5.6 Обычный алгоритм Монте-Карло интегрирования
- •1.5.7 Геометрический алгоритм Монте-Карло интегрирования
- •Тема 2 Линейное программирование
- •2.1 Общая задача линейного программирования
- •2.2 Основная задача лп (озлп)
- •2.3 Симплекс-метод линейного программирования
- •2.4 Двойственные задачи линейного программирования
- •2.5 Целочисленное линейное программирование
- •2.6 Параметрическое линейное программирование
- •2.7 Дробно-линейное программирование
- •2.8 Блочное программирование
- •2.9 Теория графов
- •2.10 Транспортная задача
- •2.10.1 Общая характеристика транспортной задачи
- •2.10.2 Математическая модель транспортной задачи
- •Тема 3 Нелинейное программирование
- •3.1 Методы нелинейного программирования
- •3.2 Метод множителей Лагранжа
- •3.3 Сепарабельное программирование
- •3.4 Выпуклое программирование
- •3.5 Квадратичное программирование
- •3.6 Геометрическое программирование
- •3.7 Динамическое программирование
- •3.8 Стохастическое программирование
- •Тема 4 Межотраслевой баланс и сетевое моделирование
- •4.1 Задача межотраслевого баланса
- •4.2 Балансовая модель Леонтьева
- •4.3 Модели межотраслевого баланса в планировании инновационных программ
- •4.3.1 Однопродуктовая динамическая макроэкономическая модель
- •1) Открытая однопродуктовая динамическая модель Леонтьева
- •2) Замкнутая однопродуктовая модель Леонтьева
- •4.4 Сетевая модель данных
- •4.4.1 Историческая справка
- •4.4.2 Основные элементы сетевой модели данных
- •4.4.3 Особенности построения сетевой модели данных
- •4.4.4 Операции над данными сетевой модели
- •4.4.5 Использование сетевой модели
- •4.5 Сетевой график
- •4.6 Методика составления сетевого графика
- •5. Задачи оптимального проектирования
- •5.1. Постановка задачи оптимального проектирования
- •5.1.1. Основные понятия и определения
- •5.2. Пример задачи оптимального проектирования
- •5.3. Классификация задач оптимального проектирования
- •Первая постановка
- •5.4 Определение уравнений линейной регрессии
- •5.7. Методика получения исходных данных
- •5.3. Решение задач оптимального проектирования
- •5.3.1. Оптимизация параметров изделия
3.3 Сепарабельное программирование
В качестве приближения к нелинейной функции на большом отрезке используется её кусочно-линейная аппроксимация, если разбить отрезок на подинтервалы и построить линейные приближения функции на каждом из подинтервалов. Этот метод применим только к сепарабельным функциям.
Определение.
Функция , где - N-мерный вектор, называется сепарабельной, если она представляется в виде суммы функций, каждая из которых зависит только от одной из N переменных, т.е.
Кусочно-линейная аппроксимация для сепарабельной непрерывной функции f(x) строится следующим образом. Интервал значений каждой переменной xi разбивается при помощи сетки с Ki узлами. Таким образом, на интервале xi(L) Ј xi Ј xi(R) рассматривается следующая последовательность точек:
xi(L) = xi(1) < xi(1) <...< xi(Ki) = xi(R)
Введём обозначение fi(k) = fi(xi(k)). Тогда аппроксимирующая функция примет вид:
причём при всех i=1,...,N выполняется:
Последнее условие выражает тот факт, что не более двух переменных l(i) должны быть положительными.
Таким образом, нелинейная функция f(x) заменяется кусочно-линейной . Для построения хорошего приближения число узлов сетки должно быть большим, то есть линейность достигается за счёт роста размерности задачи, то есть решение задачи НЛП сводится к решению задачи ЛП большой размерности с переменными li(k). Полученная задача ЛП может быть решена с помощью симплекс-метода, дополненного правилом ограниченного ввода в базис, учитывающего условие (*).
Решение, полученное с помощью сепарабельного программирования, представляет собой локальный минимум. Сходимость к глобальному минимуму гарантирована только тогда, когда целевая функция и допустимая область выпуклы. Метод сепарабельного программирования подходит для решения задач, которые в основном линейный, а отклонения от линейности представляются сепарабельными функциями. Если не требуется высокой точности, то приближенное решение задачи можно получить в процессе однократного решения задачи ЛП.
Мы рассмотрели два подхода к решению нелинейных задач. Первый (метод непосредственной линеаризации) эффективен в окрестности базовой точки и ненадёжен при удалении от неё. Второй (сепарабельное программирование) даёт хорошие приближения во всей области определения каждого ограничения, однако он применим только к сепарабельным задачам и его точность сильно зависит от густоты узлов сетки. Поэтому, необходимо построить алгоритм, использующий довольно грубые аппроксимации внешних частей ограничений для достижения окрестности оптимальной точки и строящий более тонкие аппроксимации в этой окрестности.
3.4 Выпуклое программирование
Определение 1 Задачей выпуклого программирования называется задача нелинейного программирования, у которой все функции являются выпуклыми функциями. Таким образом, задача выпуклого программирования является задачей минимизации выпуклой функции на выпуклом множестве, образованном системой выпуклых неравенств.
Основные свойства выпуклых и вогнутых функций:
1. Множество точек минимума выпуклой функции, заданной на выпуклом множестве ‑ выпукло.
2. Пусть f(x) ‑ выпуклая функция, заданная на замкнутом выпуклом множестве . Тогда локальный минимум f(x) на Х является и глобальным.
3. Если глобальный минимум достигается в двух различных точках, то он достигается и в любой точке отрезка, соединяющего данные точки.
4. Если f(x)‑ строго выпуклая функция, то ее глобальный минимум на выпуклом множестве Х достигается в единственной точке.
5. Пусть функция f(x) ‑ выпуклая функция, заданная на выпуклом множестве Х, и, кроме того, она непрерывна вместе со своими частными производными первого порядка во всех внутренних точках Х. Пусть – точка, в которой . Тогда в точке достигается локальный минимум, совпадающий с глобальным минимумом.
6. Множество точек глобальных (следовательно, и локальных) минимумов выпуклой функции f(x), заданной на ограниченном замкнутом выпуклом множестве Х, включает хотя бы одну крайнюю точку; если множество локальных минимумов включает в себя хотя бы одну внутреннюю точку множества Х, то f(x) является функцией-константой.
Рассмотрим задачу нелинейного программирования
(1)
(2)
(3)
Для решения сформулированной задачи в такой общей постановке не существует универсальных методов. Однако для отдельных классов задач, в которых сделаны дополнительные ограничения относительно свойств функций , разработаны эффективные методы их решения.
Множество допустимых решений задачи (1) – (3) удовлетворяет условию регулярности, или условию Слейтера, если существует по крайней мере одна точка , принадлежащая области допустимых решений такая, что
Задача (1) – (3) называется задачей выпуклого программирования, если функция является выпуклой, а функции – выпуклыми. Функцией Лагранжа задачи выпуклого программирования (1) – (3) называется функция
где – множители Лагранжа.
Точка называется седловой точкой функции Лагранжа, если
для всех и .
Теорема (Куна – Таккера). Для задачи выпуклого программирования (1) – (3), множество допустимых решений которой обладает свойством регулярности, является оптимальным решением тогда и только тогда, когда существует такой вектор , что – седловая точка функции Лагранжа.
Если предположить, что функции и непрерывно дифференцируемы, то теорема Куна – Таккера может быть дополнена аналитическими выражениями, определяющими необходимые и достаточные условия того, чтобы точка была седловой точкой функции Лагранжа, т. е. являлась решением задачи выпуклого программирования:
где и – значения соответствующих частных производных функции Лагранжа, вычисленных в седловой точке.