12. Нелинейное программирование

Цели

В данной главе описываются Оптимизационные задачи нелиней­ного программирования (НЛП), математические модели которых содержат нелинейные зависимости от переменных. Источники не­линейности относятся в основном к одной из двух категорий:

1) реально существующие и эмпирически наблюдаемые нели­нейные соотношения, например: непропорциональные зависимо­сти между объемом производства и затратами; между количеством используемого в производстве компонента и некоторыми показа­телями качества готовой продукции; между затратами сырья и физическими параметрами (давление, температура и т. п.) соответ­ствующего производственного процесса; между выручкой и объ­емом реализации и др.;

2) установленные (постулируемые) руководством правила поведения или задаваемые зависимости, например: формулы или правила расчета с потребителями энергии или других видов услуг; эвристические правила определения страховых уровней за­паса продукции; гипотезы о характере вероятностного распреде­ления рассматриваемых в модели случайных величин; различного рода договорные условия взаимодействия между партнерами по бизнесу и др.

Решать линейные задачи значительно проще, чем нелинейные, и если линейная модель обеспечивает адекватность реальным си­туациям, то ее и следует использовать. В практике экономичес­кого управления модели линейного программирования успешно применялись даже в условиях нелинейности. В одних случаях нелинейность была несущественной и ею можно было пренебречь, в других — производилась линеаризация нелинейных соотноше­ний или применялись специальные приемы, например строились так называемые линейные аппроксимационные модели, благода­ря чему достигалась требуемая адекватность. Тем не менее име­ется большое число ситуаций, где нелинейность является сущест­венной и ее нужно учитывать в явном виде.

Далее приводятся общая модель задачи нелинейного програм­мирования и классы задач НЛП, а также описываются условия оптимальности решения.

После того как вы выполните задания, предлагаемые в этой главе, вы будете уметь определять и использовать для экономи­ческого анализа:

• целевую функцию;

• ограничения;

• допустимый план;

• множество допустимых планов;

• модель нелинейного программирования;

• оптимальный план.

Вы сможете также:

• определять, является ли функция выпуклой;

• строить функцию Лагранжа задачи НЛП;

• проверять оптимальность полученных решений.

Модели

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

Где Х = (X1, Х2, ..., хN) — вектор переменных задачи.

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

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

Вектор Х = (X1, Х2, ..., хN), компоненты ХJ которого удовлетво­ряют ограничениям (2) и (3), называется Допустимым решением Или Допустимым планом задачи НЛП.

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

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

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

— внутренняя точка множества допус­тимых планов, в которой все первые частные производные

— точка границы множества допус­тимых планов};

— точка множества допустимых планов, в которой функция F(X) недифференцируема}.

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

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

В экономических приложениях рассматриваются следующие классы задач НЛП.

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

F(Х) ® mах,

X ³ 0,

Где Х = (Х1, Х2,..., хN) — вектор переменных задачи.

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

Необходимые условия того, что в точке Х0 достигается макси­мум функции F(X):

Это означает, что:

И

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

Функция F(X) с числовыми значениями, определенная на вы­пуклом множестве точек К, называется Вогнутой, если для любой пары точек Х1, Х2 и для всех чисел l, 0 £ l £ 1, выполняется нера­венство

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

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

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

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

Здесь — частная производная второго порядка, вычис­ленная в точке Х0.

Матрица размера П ´ П, составленная из элементов , на­зывается матрицей Хессе (Hesse). По значениям ее главных миноров можно судить о выпуклости или вогнутости функции. Функ­ция F(X) Строго выпукла в малой окрестности точки Х0, если все главные миноры ее матрицы Хессе строго положительны. Если имеют место нестрогие неравенства (³), то функция в окрестно­сти точки Х0 Выпукла. Если при этом главные миноры матрицы Хессе от Х не зависят, то функция всюду (строго) выпукла.

Весьма распространены относящиеся к данному типу Модели квадратичного программирования, в которых целевая функция F(X) является квадратичной функцией переменных Х1, х2, ..., ХN. Су­ществует большое число алгоритмов решения такого типа задач, в которых функция F(X) вогнутая (для задач минимизации — выпуклая).

2. Модели выпуклого программирования. К такого рода моделям относятся задачи НЛП (1)—(3), в которых F(X) — вогнутая (выпук­лая) функция, a Gi(X) — выпуклые функции. При данных услови­ях локальный максимум (минимум) является и глобальным.

Пусть F(X) и Gi(X), I= 1,..., Т, — дифференцируемые функции.

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

Рассмотрим задачу НЛП (1)—(3) и функцию Лагранжа L (Х, L) =

Условия Куна — Таккера оптимальности решения Х0 для зада­чи максимизации F(X) имеют вид

Где — частная производная функции Лагранжа по пе­ременной ХJ при Х = Х0 и L = L0. Пусть максимальное значение F(X) равно F(X0) = F0. Числа связаны с F0 следующими соотношениями:

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

3. Сепарабельное программирование. Специальный случай вы­пуклого программирования при условии, что F(X) и все Gi(Х) — сепарабельные функции, т. е.

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

4. Дробно-нелинейное программирование. Максимизировать (ми­нимизировать) функцию F(X) = F1(X)/F2(X).

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

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

< Предыдущая		Следующая >