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

 

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

Общая задача нелинейного программирования (ОЗНП) оп­ределяется как задача нахождения максимума (или минимума) целевой функции f (x ₁, х _2,..., x_n) на множестве D, определяемом системой ограничений

 

 

где хотя бы одна из функций f или g_i является нелинейной.

По аналогии с линейным программированием ЗНП однознач­но определяется парой (D, f) и кратко может быть записана в следующем виде

 

 

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

Как и в ЗЛП, вектор х * = (x ₁^*, x ₂^*,..., x_n^*) Î D называется допус­тимым планом, а если для любого x Î D выполняется неравен­ство f (x *) ≥ f (x), то х* называют оптимальным планом. В этом случае х* является точкой глобального максимума.

С точки зрения экономической интерпретации f(x) может рассматриваться как доход, который получает фирма (предпри­ятие) при плане выпуска х, а g_i (х) ≤ 0 как технологические ог­раничения на возможности выпуска продукции. В данном слу­чае они являются обобщением ресурсных ограничений в ЗЛП (а_iх – b_i ≤ 0).

Задача (2.2) является весьма общей, т. к. допускает запись логических условий, например:

 

 

или запись условий дискретности множеств:

 

 

Набор ограничений, определяющих множество D, при необ­ходимости всегда можно свести либо к системе, состоящей из одних неравенств:

 

 

либо, добавив фиктивные переменные у, к системе уравнений:

 

 

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

1. Множество допустимых планов D может иметь очень сложную структуру (например, быть невыпуклым или несвяз­ным).

2. Глобальный максимум (минимум) может достигаться как внутри множества D, так и на его границах (где он, вообще гово­ря, будет не совпадать ни с одним из локальных экстремумов).

3. Целевая функция f может быть недифференцируемой, что затрудняет применение классических методов математическо­го анализа.

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

2.1.2. Решение задач условной оптимизации методом Лагранжа. Одним из наиболее общих подходов к решению за­дачи поиска экстремума (локального максимума или миниму­ма) функции при наличии связующих ограничений на ее пере­менные (или, как еще говорят, задачи условной оптимизации) является метод Лагранжа. Многим читателям он должен быть известен из курса дифференциального исчисления. Идея данного метода состоит в сведении задачи поиска условного экcтремума целевой функции

 

 

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

 

 

к задаче безусловной оптимизации функции

 

 

где u Î R^m — вектор дополнительных переменных, называе­мых множителями Лагранжа. Функцию Ф(х,и), где x Î Rⁿ, u Î Rⁿ, называют функцией Лагранжа. В случае дифференцируемости функций f и g_i справедлива теорема, опре­деляющая необходимое условие существования точки услов­ного экстремума в задаче (2.3)-(2.4). Поскольку она непосредственно относится к предмету математического ана­лиза, приведем ее без доказательства.

 

Теорема 2.1. Если х* является точкой условного эк­стремума функции (2.3) при ограничениях

(2.4) и ранг матрицы первых частных производных функций

равен т, то существуют такие и ₁^*, и ₂^*, ...,и_m^*, не равные одновременно нулю, при которых

 

Из теоремы (2.1) вытекает метод поиска условного экстре­мума, получивший название метода множителей Лагранжа, или просто метода Лагранжа. Он состоит из следующих этапов.

1. Составление функции Лагранжа Ф(х,и).

2. Нахождение частных производных

 

 

3. Решение системы уравнений

 

 

относительно переменных x и u.

4. Исследование точек, удовлетворяющих системе (2.7), на максимум (минимум) с помощью достаточного признака экст­ремума.

Присутствие последнего (четвертого) этапа объясняется тем, что теорема (2.1) дает необходимое, но не достаточное ус­ловие экстремума. Положение дел с достаточными признаками условного экстремума обстоит гораздо сложнее. Вообще гово­ря, они существуют, но справедливы для гораздо более частных ситуаций (при весьма жестких предпосылках относительно функций f и g_i) и, как правило, трудноприменимы на практике.

Еще раз подчеркнем, что основное практическое значение метода Лагранжа заключается в том, что он позволяет перей­ти от условной оптимизации к безусловной и, соответствен­но, расширить арсенал доступных средств решения проблемы. Однако нетрудно заметить, что задача решения системы урав­нений (2.7), к которой сводится данный метод, в общем случае не проще исходной проблемы поиска экстремума (2.3)-(2.4). Методы, подразумевающие такое решение, называются непря­мыми. Они могут быть применены для весьма узкого класса за­дач, для которых удается получить линейную или сводящуюся к линейной систему уравнений (2.7). Их применение объясняет­ся необходимостью получить решение экстремальной задачи в аналитической форме (допустим, для тех или иных теоретиче­ских выкладок). При решении конкретных практических задач обычно используются прямые методы, основанные на итера­тивных процессах вычисления и сравнения значений оптимизи­руемых функций.

2.1.3. Градиентные методы решения задач безуслов­ной оптимизации. Ведущее место среди прямых методов ре­шения экстремальных задач занимает градиентный метод (точнее, семейство градиентных методов) поиска стационар­ных точек дифференцируемой функции. Напомним, что стаци­онарной называется точка, в которой f (x)=0 и которая в со­ответствии с необходимым условием оптимальности является «подозрительной» на наличие локального экстремума. Таким образом, применяя градиентный метод, находят множество то­чек локальных максимумов (или минимумов), среди которых определяется максимум (или минимум) глобальный.

Идея данного метода основана на том, что градиент функции указывает направление ее наиболее быстрого возрастания в окрестности той точки, в которой он вычислен. Поэтому, если из некоторой текущей точки х ⁽¹⁾ перемещаться в направлении вектора f (x ⁽¹⁾), то функция f будет возрастать, по крайней мере, в некоторой окрестности х ⁽¹⁾. Следовательно, для точки х ⁽²⁾ = х ⁽¹⁾ +λ f (x ⁽¹⁾), (λ>0), лежащей в такой окрестности, справедливо неравенство f (x ⁽¹⁾)≤ f (x ⁽²⁾). Продолжая этот про­цесс, мы постепенно будем приближаться к точке некоторого локального максимума (см. рис. 2.1).

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

 

 

задающей последовательность точек, стремящихся к точке мак­симума.

В зависимости от способа ее решения различают различные варианты градиентного метода. Остановимся на наиболее изве­стных из них.