Задачи нелинейного программирования. Понятие итераций и рекуррентных соотношений.

Математическая формулировка задачи принятия оптимального решения эквивалентна задаче отыскания наибольшего или наименьшего значения функции одной или нескольких переменных. В большинстве практических задач критерий оптимальности Q (u), где u – вектор управляющих переменных, не может быть записан в явном виде, его значение обычно находится в результате решения системы уравнений математического описания оптимизируемого объекта. На независимые переменные u_i, i = могут быть наложены связи и ограничения как в виде равенств φ_t(u) = 0, t = , так и в виде неравенств ψ _i (u) ≤ 0, i = , которые, как правило, являются нелинейными и трудно вычислимыми соотношениями. Задачи такого типа являются предметом рассмотрения специального раздела математики, называемого нелинейным программированием. Обычно, решения задач нелинейного программирования могут быть найдены только численными методами.

Задача нелинейного программирования встречается в естественных науках, технике, экономике, математике, в сфере деловых отношений и в науке управления государством.

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

Метод "затраты – эффективность" также укладывается в схему нелинейного программирования. Данный метод был разработан для использования при принятии решений в управлении государством. Общей функцией эффективности является благосостояние. Здесь возникают две задачи нелинейного программирования: первая – максимизация эффекта при ограниченных затратах, вторая – минимизация затрат при условии, чтобы эффект был выше некоторого минимального уровня. Обычно эта задача хорошо моделируется с помощью нелинейного программирования.

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

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

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

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

В большинстве методов нелинейного программирования используется идея движения в n -мерном пространстве в направлении оптимума. При этом из некоторого исходного или промежуточного состояния uⁱ осуществляется переход в следующее состояние u^{i +1} изменением вектора uⁱ на величину Δ uⁱ, называемую шагом или итерацией.

Методы нелинейного программирования представляют со­бой последовательность однотипных шагов, или итераций.

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

При поиске минимума целевой функции Q (u) для удачно выбранного шага должно выполняться условие Q (u^{i +1}) < Q (uⁱ), в противном случае переход в состояние u^{i +1} нецелесообразен.

В значительной части методов шаг определяется как некоторая функция состояния uⁱ: Δ uⁱ = Δ uⁱ (uⁱ), и, следовательно, новое состояние можно рассматривать как функцию исходного состояния u^{i +1} = uⁱ + Δ uⁱ (uⁱ). В этом смысле шаговые методы поиска оптимума называются итеративными.

Методы нелинейного программирования в зависимости от способа задания шага Δ u _t подразделяются на три основных класса: 1) градиентные методы; 2) безградиентные методы; 3) методы случайного поиска. Некоторые методы организуются как комбинированные алгоритмы, использующие достоинства методов различных классов. Кроме того различают методы одномерной оптимизации (u -скаляр) и многомерной оптимизации (u -вектор).

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

Если целевая функция Q (u) непрерывна в области U, то вокруг точки u _опт всегда можно провести в данной плоскости замкнутую линию, вдоль которой значение Q (u) постоянно (рис. 3.1, а). Эти замкнутые линии называются линиями равного уровня функции Q (u) и отвечают различным значениям Q (u) = q _t. Вокруг точки u _опт можно провести сколько угодно линий уровня, причем каждая из них будет целиком охватывает любую линию, для которой значение целевой функции Q (u) меньше (или больше).

При наличии связи φ(u) = 0, что в n -мерном пространстве определяет (n – 1)-мерную поверхность, пересечение которой с рассматриваемой поверхностью определяет область (рис. 3.1, б), в которой и ищется оптимальное решение.

Ограничения типа неравенств независимо от их числа наглядно представлены на рис. 3.1, в. Здесь заходить в заштрихованную область нельзя.

Рис. 3.1 Геометрическое представление целевой функции: а – линии равного уровня; б – линии равного уровня и связи типа равенств; в – линии равного уровня и ограничения типа неравенств