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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где х = (x₁, х₂, ..., х_n) — вектор переменных задачи.

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

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

Вектор х = (x₁, х₂, ..., х_n), компоненты х_j которого удовлетво­ряют ограничениям (2) и (3), называется допустимым решением или допустимым планом задачиНЛП.

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

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

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

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

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

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

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

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

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

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

F(х) ® mах,

x ³ 0,

где х = (х₁, х₂,..., х_n) — вектор переменных задачи.

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

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

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

и

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где — частная производная функции Лагранжа по пе­ременной х_j при х = х⁰ и l = l⁰. Пусть максимальное значение F(x) равно F(x⁰) = F⁰. Числа связаны с F⁰ следующими соотношениями:

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

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

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

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

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

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

Примеры. Пример 1. Сколько производить?

Предприятие располагает ресурсами двух видов сырья и рабо­чей силы, необходимыми для производства двух видов продукции. Затраты ресурсов на изготовление одной тонны каждого продук­та, прибыль, получаемая предприятием от реализации тонны про­дукта, а также запасы ресурсов указаны в следующей таблице:

Стоимость одной тонны каждого вида сырья определяется сле­дующими зависимостями: (9 + 0,0088r₁) тыс. руб. для сырья 1 и (5 - 0,0086r₂) тыс. руб. для сырья 2, где r₁ и r₂ — затраты сырья на производство продукции. Стоимость одного часа трудозатрат определяется зависимостью (1 - 0,0002r, где r — затраты времени на производство продукции.

Вопросы:

1. Сколько продукта 1 следует производить для того, чтобы обес­печить максимальную прибыль?

2. Сколько продукта 2 следует производить для того, чтобы обес­печить максимальную прибыль?

3. Какова максимальная прибыль?

Решение. Пусть x₁ — объем выпуска продукта 1 (в тоннах), х₂ — объем выпуска продукта 2 (в тоннах). Тогда задача может быть описана в виде следующей модели нелинейного программиро­вания:

При использовании программы GINO исходную информацию для решения этой задачи представляем в следующем виде:

Получаем следующий результат:

Ответы: 1. 16,67т. 2.13,89т. 3. 507,407 тыс. руб.

Пример 2. Формирование портфеля ценных бумаг.

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

где х_j — объем средств, затраченных на покупку акций типа j (тыс. руб.);

m_j — математическое ожидание процента прибыли от вложения 1 тыс. руб. в акции типа j;

s_jj — дисперсия указанного выше процента прибыли;

s_ij — ковариация между процентами прибыли от вложения 1 тыс. руб. в акции типа i и j (i ¹ j).

Первая сумма в критерии — ожидаемое значение прибыли, обеспечиваемой пакетом акций, вторая — дисперсия прибыли пакета акций, взятая с «весом» 3. Дисперсия прибыли пакета ак­ций служит мерой риска.

Пусть средние значения процентов годовой прибыли от ак­ций компаний составляют соответственно 8, 10 и 13%. Дисперсии s₁₁ = 0,1, s₂₂ = 0,15, s₃₃ = 0.19. Ковариации s₁₂ = 0,01, s₁₃ = 0,02, s₂₃ = 0,03.

Вопросы:

1. Является ли целевая функция строго вогнутой?

2. Какую сумму следует вложить в покупку акций типа 1?

3. Какую сумму следует вложить в покупку акций типа 3?

Решение. Модель нелинейного (в данном случае — квадратич­ного) программирования имеет вид

Рассчитав значения соответствующих определителей (главных миноров матрицы Хессе), можно убедиться, что выполняются условия (4), откуда следует, что целевая функция строго выпукла для любых значений х₁, х₂, х₃ (значения определителей не зави­сят от значений переменных).

Используя программу GINO, исходную информацию для ре­шения этой задачи представляем в следующем виде:

Получаем следующий результат:

Непосредственной подстановкой полученного решения в усло­вия (5)—(8) можно убедиться, что условия Куна — Таккера выпол­няются, причем решение обеспечивает глобальный максимум це­левой функции, поскольку F строго вогнута.

Ответы: 1. Да, является (при любых значениях переменных).

2. 496,8 тыс. руб. 3. 197,93 тыс. руб.

Пример 3. Производство молочных продуктов.

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

Затраты, связанные с приобретением сырья (молока), являют­ся кусочно-линейной функцией закупаемого количества:

а) для фермы 1

б) для фермы 2

Вопросы:

1. Какова максимальная ежедневная прибыль молокозавода?

2. Сколько молока следует закупать на ферме 1?

3. Сколько молока следует закупать на ферме 2?

4. Как изменится максимальная прибыль, если максимальное суточное производство сметаны увеличить на 1 кг?

5. Как изменится максимальная прибыль, если максимальное суточное производство творога уменьшить на 2 кг?

Решение. Задача может быть описана с помощью модели ли­нейного программирования.

Пусть x₁ — количество молока, закупаемого на ферме 1, х₂ — количество молока, закупаемого па ферме 2. Представим х₁ и х₂ в следующем виде:

Тогда стоимость молока, закупаемого на ферме 1, описывает­ся функцией

а стоимость молока, закупаемого на ферме 2, — функцией

Окончательно модель линейного программирования имеет вид

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

Используя для решения этой задачи программу POMWIN, по­лучаем следующий результат:

Далее представлена таблица, содержащая границы устойчиво­сти по коэффициентам целевой функции:

Границы устойчивости по правым частям ограничений:

Ответы: 1. 8275 руб. 2. 312,5 кг. 3. 218,75 кг. 4. Увеличится на 45 руб. 5. Уменьшится на 80 руб.