В данной теме описываются оптимизационные задачи нелинейного программирования (НЛП), математические модели которых содержат нелинейные зависимости от переменных. Источники нелинейностей относятся в основном к одной из двух категорий:
• реально существующие и эмпирически наблюдаемые нелинейные соотношения, такие, например, как непропорциональные зависимости между объемом производства и затратами; между количеством используемого в производстве компонента и некоторыми показателями качества готовой продукции; между затратами сырья и физическими параметрами (давление, температура и т.п.) соответствующего производственного процесса; между выручкой и объемом реализации и др.;
• установленные (постулируемые) руководством правила поведения или задаваемые зависимости, такие, например, как формулы или правила расчета с потребителями энергии или других видов услуг; эвристические правила определения страховых уровней запаса продукции; гипотезы о характере вероятностного распределения рассматриваемых в модели случайных величин; различного рода договорные условия взаимодействия между партнерами по бизнесу и др.
|
|
Решать линейные задачи значительно проще и, если линейная модель обеспечивает адекватность реальным ситуациям, то ее и следует использовать. В практике экономического управления имеется большой опыт успешного применения моделей линейного программирования даже в условиях нелинейности. В некоторых случаях нелинейности были несущественными и можно было пренебречь, в других — производилась линеаризация нелинейных соотношений или применялись специальные приемы, например, строились так называемые линейные аппроксимационные модели, благодаря чему достигалась указанная выше адекватность. Тем не менее имеется большое число ситуаций, где нелинейность является существенной и ее нужно учитывать в явном виде.
В общем виде задача нелинейного программирования описывается с помощью следующей модели нелинейного программирования:
F(x)→ max; (1)
g(x)≤ bi i = 1, …, m; (2)
x ≥ 0, (3)
где x = (x1, …, xn)— вектор переменных задачи.
Задача (1)—(3) называется задачей нелинейного программирования в стандартной форме на максимум.
Аналогично может быть сформулирована задача НЛП на минимум.
Вектор х = (x1, …,xn), компоненты хj которого удовлетворяют ограничениям (2)—(3), называется допустимым решением или допустимым планом задачи нелинейного программирования.
Совокупность всех допустимых планов называется множеством допустимых планов.
Допустимое решение задачи нелинейного программирования, на котором целевая функция (1) достигает максимального значения, называется оптимальным решением задачи НЛП.
|
|
Возможные местонахождения максимального значения функции F(x) при наличии ограничений (2) и (3) определяются следующим общим принципом. Максимальное значение F(x), если оно существует, может достигаться в одной или более точках, которые могут принадлежать:
S1 —множеству внутренних точек области допустимых решений, в которых все первые частные производные функции F равны нулю;
S2 —множеству точек границы допустимой области;
S3 — множеству точек допустимой области, в которой функция не дифференцируема.
В отличие от задач линейного программирования, любая из которых может быть решена с помощью симплекс-метода, не существует одного или нескольких алгоритмов, эффективных для решения любых нелинейных задач. Некоторый алгоритм может оказаться эффективным для решения задач одного типа и неудачным для задач другого типа. Эффективность алгоритма может даже существенно зависеть от постановки задачи, например, от изменения масштабов измерения тех или иных переменных. Поэтому алгоритмы разрабатываются для каждого класса (типа) задач. При этом программы, ориентированные на решение определенного класса задач, как правило, не гарантируют правильность решения любых задач данного класса, и оптимальность решения рекомендуется проверять в каждом конкретном случае.
.