Вопрос 29

Понятие о нелинейном программировании. В большинстве задач построение математической модели не удается свести к линейной задаче. Математические модели в задачах проектирования реальных объектов должны отражать реально протекающие процессы (химические, физические), которые, как правило, не линейны. Переменные этих объектов связаны между собой физическими нелинейными законами. Они могут быть ограничены предельными диапазонами и в результате оказывается, что большинство задач математического моделирования относятся к нелинейному программированию. Общая задача нелинейного программирования: Пусть в математической модели целевая функция F (x₁,x₂,…,x_n)=F(x) – произвольная функция. Система ограничений состоит из уравнений h₁ (x)=0 и неравенств g_m+1(x)>0

h₂ (x)=0 g_m+2(x)>0 (*)

h_m (x)=0 g_l(x)>0

Все функции h_i и g_j – произвольные. Задача. Найти набор значений X=(x₁,x₂,…,x_n), при котором целевая функция F(x) достигает своего max (min) значения, удовлетворяющего системе ограничений (*). В последнее время из нелинейного программирования выделим следующие самостоятельные разделы: 1. Выпуклое программирование; 2. Квадратичное программирование; 3. Целочисленное программирование; 4. Стахостическое программирование; 5. Динамическое программирование и другие. Задачи выпуклого программирования – задачи, в которых определяется либо min выпуклой функции, либо max вогнутой, которая задана на замкнутом выпуклом множестве. Задачи наиболее изучены. В задачах квадратичного программирования целевая функция – квадратичная, а система ограничений – линейная. В задачах целочисленного программирования ищется решение x₁,x₂,…,x_n – только если переменные имеют целые значения. В стахостическом программировании в целевой функции или в системе ограничений некоторые переменные являются случайными величинами; при решении этих задач используются законы теории вероятностей. В динамическом программировании одна из переменных является временем t. Решение таких задач описывается дифференциальными уравнениями. Методы нелинейного программирования. Нет универсальных методов решения задач нелинейного программирования. В зависимости от критерия выделяют следующие методы: 1. По количеству локальных критериев (количество условий системы ограничений): однокритериальные и многокритериальные. 2. По количеству переменных X=(x₁,x₂,…,x_n ): одномерные (n=1) и многомерные (n>1). 3. По наличию ограничений: без ограничений (безусловная оптимизация) и с ограничениями (условная оптимизация). 4. По типу информации: прямой поиск экстремума целевой функции (используются значения функции F), градиентные методы первого порядка (производные первого порядка) и градиентные методы второго порядка (производные второго порядка). Классический метод нахождения экстремума. Задача: найти max F=(x₁,x₂,…,x_n ) при ограничениях g₁(x₁,x₂,…,x_n )≥0

g₂(x₁,x₂,…,x_n )≥0

g_m(x₁,x₂,…,x_n )≥0

Один из способов решения такой задачи нелинейного программирования – воспользоваться методом дифференциального исчисления функций нескольких переменных. В этом случае функция F должна иметь все частные производные второго порядка. Мы ищем условный экстремум, для этого надо сделать следующее: 1. Найти множество стационарных точек функции F, исследовать эти точки на max. Среди них выбрать ту точку, которая дает наибольший max функции F. Эта точка должна удовлетворять системе ограничений. 2. Исследовать точки границы области, которая задается системой ограничений. Среди них выбрать точку, дающее наибольшее значение функции F на границе. 3. Сравнив значения функции F в точках из 1 и 2 пункта, в ответ идет наибольшее из них. Такой метод требует значительных вычислительных затрат и применяется в простейших случаях: при небольших значениях n и m, причем все функции g должны быть большое число раз дифференцируемы. Метод множителей Лагранжа. Это метод позволяет находить max(min) функции при системе ограничений, состоящей только из уравнений. Основная идея метода состоит в переходе от задачи на условный экстремум к задаче нахождения безусловного экстремума некоторой функции. Задача: найти min F=(x₁,x₂,…,x_n ) при ограничениях

h₁(x₁,x₂,…,x_n )=0

h₂(x₁,x₂,…,x_n )=0

h_m(x₁,x₂,…,x_n )=0

Вводим множители Лангранжа: λ₁,λ,₂…,λ_m их столько, сколько уравнений. Функция Лангранжа: L (x₁,x₂,…,x_n, λ₁,λ,₂…,λ_m )=F (x₁,x₂,…,x_n )+∑ λ_i h_i (x₁,x₂,…,x_n ). X=( x₁,x₂,…,x_n ) является решением исходной задачи, если все частные производного порядка приравнены к нулю:

δL/δλ=0, i=1,…,n

δh/δλ=0, j=1,…,m.