Модели и методы решения.

 

В общем виде задача нелинейного программирования описывается с помощью следующей модели нелинейного программирования :

F(x) ® max                  (1)

gi(x) Јbi, i = 1,2,...,m,   (2)

xj і0, j = 1,2,...,n,          (3)

где x =( x1, x2, ..., xn ) – вектор переменных задачи.

Задача (1)-(3) называется задачей нелинейного программирования в стандартной форме на максимум.

Может быть сформулирована также задача НЛП на минимум.

Вектор x =( x1, x2, ..., xn ) , компоненты x j   которого удовлетворяют ограничениям (2) и (3) , называется допустимым решением или допустимым планом задачи нелинейного программирования.

Совокупность всех допустимых планов называется множеством допустимых планов.

Допустимое решение задачи нелинейного программирования, на котором целевая функция (1) достигает максимального значения, называется оптимальным решением задачи НЛП.

Возможные местонахождения максимального значения функции F(x) при наличии ограничений (2) и (3) определяются следующим общим принципом. Максимальное значение F(x), если оно существует, может достигаться в одной или более точках, которые могут принадлежать следующим множествам:

S1={(x 1 ,…,x n): (x 1 ,…,x n) – внутренняя точка в области допустимых решений, в которой (точке) все первые частные производные Fxj =0 , j = 1,2,...,n },

S2 ={(x 1 ,…,x n): (x 1 ,…,x n) – точка границы допустимой области},

S3 ={(x 1 ,…,x n): (x 1 ,…,x n) – точка допустимой области, в которой функция F(x) не дифференцируема}.

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

В экономических приложениях рассматриваются следующие классы задач нелинейного программирования:

 

Оптимизация нелинейной функции с ограничениями на неотрицательность значений переменных.

F(x) ® max

xj і 0, j = 1, 2, ..., n,  где  x =( x1, x2, ..., xn ) – вектор переменных задачи.

Пусть F(x) дифференцируемая функция.

Необходимые условия того, что в точке x0 достигается максимум функции F(x) :     ,   j=1,2,.,n

Это означает, что , в случае xoj = 0 и  , в случае xoj > 0.

Если F(x) вогнутая функция (в случае задачи минимизации – если выпуклая), то эти условия являются также достаточными.

Функция F с числовыми значениями, определенная на выпуклом множестве точек К , называется вогнутой, если для любой пары точек x1, x2 и для всех чисел

l , 0 Ј l Ј 1 выполняется неравенство

F(lx1 + (1- l) x2 ) іlF (x1) + (1- l) F (x2)

Если F(lx1 + (1- l) x2 ) Ј lF (x1) + (1- l) F (x2) ,

то функция F называется выпуклой. Если имеют место строгие неравенства, то говорят, что функция строго вогнута или строго выпукла.

Данное определение вогнутости (выпуклости) функции годится для любого типа функции. Практически, однако, применять его трудно. Для дважды дифференцируемой функции F имеет место следующий критерий:

Дифференцируемая функция F(x) строго вогнута в некоторой окрестности точки

x0 =( x01, x02, ..., x0n ) , если выполняются следующие условия:

F11(x0) < 0 ,

F22(x0) < 0 ,

Определитель матрицы

F11(x0) F12(x0)
F21(x0) F22(x0)

положителен.

Определитель матрицы.

F11(x0) F12(x0) F13(x0)
F21(x0) F22(x0) F23(x0)
F31(x0) F32(x0) F33(x0)

отрицателен и т.д. ,т. е. если знаки этих определителей чередуются указанным образом.

Здесь Fij(x0) – частная производная второго порядка, вычисленная в точке x0.

Матрица размерности nxn , составленная из элементов Fij(x0) , называется матрицей Хессе ( Hesse). По значениям ее главных миноров можно судить о выпуклости или вогнутости функции. Функция F(x) строго выпукла в малой окрестности точки x0 , если все главные миноры ее матрицы Hesse строго положительны. Если имеют место нестрогие неравенства ( і ) , то функция в окрестности точки x0 выпукла. Если при этом главные миноры матрицы Hesse от x не зависят, то функция всюду (строго) выпуклая.

 

Оптимизация нелинейной функции с линейными ограничениями.

Весьма распространены относящиеся к данному типу модели квадратичного программирования, в которых целевая функция F(x) является квадратичной функцией переменных x1, x2, ..., xn.   Существует большое число алгоритмов решения такого типа задач, в которых функция F(x) вогнутая (для задач минимизации - выпуклая).

Модели выпуклого программирования.

К такого рода моделям относятся НЛП, в которых

1. F(x) – вогнутая (выпуклая) функция;

2. Каждая gi(x) – выпуклая функция.

При данных условиях локальный максимум (минимум) является и глобальным.

Пусть F(x) и gi(x) , i = 1,2,...,m, дифференцируемые функции.

Необходимые и достаточные условия оптимальности решения- выполнение условий Куна-Таккера.

Рассмотрим задачу нелинейного программирования (1) – (3) и

пусть функция  L(x, l) называется функцией Лагранжа.

Условия Куна-Таккера оптимальности решения x0 для задачи максимизации F(x) имеют вид:

L` xj (x0, l0) і 0 , xij * L` xj (x0, l0) = 0 для j = 1, 2, ..., n (5)

gi(x0) - bi Ј 0 , loi = (gi(x0) - bi ) =0 для i = 1, 2, ..., m (6)

xij і 0 для j = 1, 2, ..., n (7)

loi і 0 для i = 1, 2, ..., m , (8)

где L` xj (x0, l0) – частная производная функции Лагранжа по переменной xj, при

x = x0 и l=l0.

Пусть максимальное значение F(x) равно F(x0) = F0.

Числа loi связаны с F0 следующими соотношениями:

, для i = 1, 2, ..., m.

Из этих соотношений видно, что числа loi характеризуют реакцию значения F0 на изменение значения соответствующего bi. Например, если loi <0 , то при уменьшении bi (в пределах устойчивости loi ) значение F0 увеличится, а loi =0 указывает на несущественность соответствующего ограничения gi(x) Ј bi , которое может быть без ущерба для оптимального решения из системы ограничений исключено.

 

Сепарабельное программирование.

Специальный случай выпуклого программирования при дополнительном условии

3. F(x) и все gi(x)  – сепарабельные функции. Это означает, что указанные функции имеют вид:

, i = 1,2,...,m.

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

Дробно- нелинейное программирование.

Максимизировать (минимизировать) функцию

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

 

Невыпуклое программирование.

F(x) и (или) какие-либо gi(x) не выпуклы. Надежных методов решения задач данного типа пока не существует.