Нелинейное программирование. 
Исследование операций в экономике

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

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

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

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

Основные понятия НЛП:

• * целевую функция;
• * ограничения;
• * допустимый план;
• * множество допустимых планов;
• * модель нелинейного программирования;
• * оптимальный план.

Необходимо уметь:

• * определять, является ли функция выпуклой;
• * строить функцию Лагранжа задачи НЛП;
• * проверять оптимальность полученных решений.

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

исследование операция моделирование математический где х = (x1, х2, …, хn) — вектор переменных задачи.

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

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

Вектор х = (x1, х2, …, хn), компоненты хj которого удовлетворяют ограничениям (2) и (3), называется допустимым решением или допустимым планом задачи НЛП.

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

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

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

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

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

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

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

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

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

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

Рисунок. Классификация задач и методов нелинейного программирования Большинство существующих методов в нелинейном программировании можно разделить на два больших класса:

• 1. Прямые методы — методы непосредственного решения исходной задачи. Прямые методы порождают последовательность точек — решений, удовлетворяющих ограничениям, обеспечивающим монотонное убывание целевой функции.
• 2. Недостаток: трудно получить свойство глобальной сходимости.
• 3. Задачи с ограничениями в виде равенств.
• 4. Метод замены переменных (МЗП)
• 5. Двойственные методы — методы, использующие понятие двойственности. В этом случае легко получить глобальную сходимость.
• 6. Недостаток: не дают решения исходной задачи в ходе решения — оно реализуемо лишь в конце итерационного процесса.
• o Метод множителей Лагранжа (ММЛ)
• o Методы штрафов
• o Метод множителей
• o Методы линеаризации для задач условной оптимизации
• o Алгоритм Франка-Вульфа
• o Метод допустимых направлений Зойтендейка
• o Метод условного градиента
• o Метод проекции градиента
• o Сепарабельное программирование.
• o Квадратичное программирование
• 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) не выпуклы. Надежных методов решения задач такого типа пока не существует (3, стр. 74−77).

Как пример, рассмотрим нелинейную модель оптимального распределения ресурсов:

Описание задачи распределения ресурсов Задача распределения ресурсов рассматривается для n предприятий. Центр осуществляет управление этими промышленными предприятиями, выпускающими однотипную продукцию. Обозначим через Рi объем продукции, выпускаемой предприятием i, i=1,. ., n. Результат функционирования центра определяется результатами функционирования отдельных производителей, т.к. центр сам не производит продукции.

Считаем, что величина продукции, произведенной i-м предприятием, определяется объемом фондов Fi и количеством рабочей силы Li, согласие производственной функции КоббаДугласа:

где i=1,., n (4).

В выражении (4) di и ki характеристики предприятия i (i=1,. ., n), удовлетворяющие условиям: di > 0, i=1,…, n.

Пусть wi — ставка заработной платы на предприятии i. Тогда доля дохода предприятия i в общей сумме прибыли объединения определится так:

Gi =ci*Pi-wi*Li, i=1,.. ., n.

Если величина фондов предприятия фиксирована, то объем продукции Pi однозначно определяется количеством рабочей силы .

Центр влияет на работу предприятий распределением дополнительного ресурса, который полностью находиться в его распоряжении. Если предприятие i получит дополнительный ресурс в количестве Vi, то оно сможет произвести продукцию в объеме.

i=1,…, n (5).

Задача центра состоит в распределении имеющегося в его распоряжении ресурса В, т. е. в определении оптимальных значений величин Vi, i =1,…, n, обеспечивающих максимум суммарной прибыли объединения в целом.

Математическая форма модели В данной задаче считаем, что используется схема централизованного планирования, в рамках которой центр рассчитывает оптимальное распределение ресурсов, оптимальные величины рабочей силы при заданных параметрах модели. Конкретно центр изменяет Vi и Li, i = 1,…, n, из условий:

z = max (G1 + G2 + ,…, + Gn) (6).

Vi, Vimin, Li 0, i=1,…, n (7).

Анализ чувствительности модели как способ восстановления финансового равновесия.

Основой сохранения и восстановления финансового равновесия предприятия и снижения уровня риска является анализ чувствительности предложенной модели. Анализ чувствительности состоит из следующих этапов:

• 1. Выбор ключевого показателя, т. е. такого параметра, относительно которого и рассчитывается чувствительность проекта (чаще всего это чистый приведенный доход и внутренняя норма доходности).
• 2. Выбор факторов, которые влияют на эти показатели.
• 3. Расчет значений ключевых показателей на разных этапах реализации проекта (поиск, проектирование, строительство, эксплуатация).

Чем выше чувствительность показателей к факторам внешней среды, тем более рискованным является проект. Для каждого показателя определяется чувствительность каждого момента времени или отрезка времени. Определяется эффективность проекта.

Часто во время анализа чувствительности определяется точка безубыточности проекта, т. е. определяется тот объем выпуска продукции, при котором предприятие выходит из зоны убытка.

Анализ чувствительности проекта разрешает специалистам учитывать риск и неопределенность. Например, если цена продукции оказалась критической, то возможно усилить программу маркетинга или снизить стоимость проекта. Если критическим окажется объем выпущенной продукции, то необходимо повысить квалификацию рабочих, уделить внимание обучению персонала, менеджерам и другим факторам повышения производительности.

Недостатки метода анализа чувствительности:

• 1. Метод не рассчитан на все случайное и возможное обстоятельства.
• 2. Метод не уточняет вероятность реализации альтернативных проектов.

Анализ чувствительности оптимального решения Анализ чувствительности выполняется уже после получения оптимального решения задачи линейного программирования (ЛП). Его цель — определить, приведет ли изменение коэффициентов исходной задачи к изменению текущего оптимального решения, и если да, то, как эффективно найти новое оптимальное решение (если оно существует).

В общем случае изменение коэффициентов исходной задачи может привести к одной из следующих четырех ситуаций.

• 1. Текущее базисное решение остается неизменным.
• 2. Текущее решение становится недопустимым.
• 3. Текущее решение становится неоптимальным.
• 4. Текущее решение становится неоптимальным и недопустимым.

Во второй ситуации можно использовать двойственный симплекс-метод для восстановления допустимости решения. В третьей ситуации мы используем прямой симплекс-метод для получения нового оптимального решения. В четвертой для получения нового оптимального и допустимого решения следует воспользоваться как прямым, так и двойственным симплекс-методом.