Математические методы в принятии решений

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

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

3.2 Общая характеристика  методов решения задач нелинейного  программирования

 

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

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

u_i+1 = u_i + Δu_i.     (3.1)

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

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

В этом смысле шаговые методы поиска оптимума называются итеративными.

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

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

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

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

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

Особенностями целевой функции  являются седловые точки, так называемые "овраги" и многоэкстремность. В седловых точках функция Q (u) по одному или нескольким направлениям имеет минимум, в то время как по остальным – максимум. При наличии оврагов вдоль определенных направлений величина функции Q (u) изменяется очень слабо. Целевая функция может иметь не один, а несколько оптимумов. Оптимум называется глобальным, если для него справедливо условие Q (u_опт) ≤ Q (u), u ∈ U, которое выполняется для любых допустимых значений u. Если существуют другие оптимумы, то они называются локальными, и соотношения типа Q(u_опт ) ≤Q(u) выполняется только в окрестностях точек u_опт. Для отыскания глобального оптимума необходимо найти и проверить, вообще говоря, все без исключения локальные оптимумы, имеющейся целевой функции.

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

Эта функция должна быть непрерывно дифференцируемой. Для этого  вводится понятие производной по направлению l

где u, u* – точки, расположенные на прямой l. Эта производная (3.2) характеризует скорость изменения функции Q (u) в точке и в направлении l, она может быть выражена через производные по координатам, число которых конечно и равно размерности n. Согласно правилу дифференцирования сложных функций, можно записать

Рассмотрим расчет ∂uι / ∂l в пространстве двух переменных (рис. 3.2).

Из прямоугольного треугольника АВС можно записать Таким образом, величины ∂uι / dl есть не что иное, как направляющие косинусы выбранного направления l по отношению к осям координат. Следовательно, (3.3) можно переписать следующим образом

Если теперь рассмотреть  поверхность равного уровня, которая  имеет (n – 1) независимых переменных, то в каждой точке этой поверхности, называемой гиперповерхностью, можно провести (n – 1) взаимно перпендикулярных касательных в соответствии с числом измерений этой поверхности. Кроме того, в этой же точке можно провести ось, перпендикулярную всем касательным и, следовательно, направленную по нормали к поверхности. Подобное построение для случая (n = 3) изображено на рис. 3.3.

Рис. 3.3 Система  координат, связанная с произвольной точкой поверхности постоянного  уровня

Касательные и нормаль  могут рассматриваться как система  координат с началом в выбранной  точке поверхности. Данная система  координат обладает тем важным свойством, что частные производные от функции Q (u) по направлениям осей равны нулю, так как вдоль этих направлений функция Q (u) сохраняет постоянное значение. В соответствии со сказанным производная по произвольному направлению l запишется как

что следует из (3.4), где  производные по всем осям, за исключением  нормали, оказываются равными нулю.

Максимальное значение cos α по абсолютной величине не превышает  единицы, аргумент при этом равен  нулю, следовательно, направление, по которому производная ∂Q / ∂l имеет максимальное значение, совпадает с направлением нормали к поверхности постоянного уровня функции Q (u). Если теперь по направлению нормали отложить вектор длиной равной |δQ/δu|,  то полученный вектор называется градиентом скалярной функции Q (u) в точке u и обозначается ∇Q (u) (читается "набла ку") или ( gradQ(u) ).

Формулу (3.5) можно записать как 

где ∇l Q (u) – проекция градиента функции Q (u) по направлению l. Отсюда следует, что проекции вектора градиента на оси координат равны производным функции Q (u) по соответствующим переменным, т.е.

Основным свойствам градиента  целевой функции является то, что  вектор градиента по направлению  совпадает с направлением наискорейшего  возрастания этой функции. Именно это  свойство обусловило применение градиентных  методов при решении задач  нелинейного программирования.

3.3 Методы одномерной оптимизации

 

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

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

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

 

1. Метод прямого сканирования

 

Задача заключается в  локализации экстремума функции  одной переменной, заданной на интервале [a, b] с точностью до Δ. При решении этой задачи весь интервал разбивается на участки величиной Δ. В узлах разбиения вычисляются значения функции Q и из них выбирается экстремальное. Этот метод требует больших затрат времени (зависящего от значения Δ), но главное его преимущество – это определение глобального экстремума. Блок-схема алгоритма поиска Q (x) представлена на рис. 3.4, б.

Естественным и наиболее распространенным на практике методом  поиска экстремума функции одной  переменной является метод последовательного  деления отрезка пополам. Этот метод  был известен еще в древней  Греции как метод дихотомии.

Пусть требуется определить экстремум унимодальной функции Q (u) на отрезке [a, b] с точностью Δ. Отрезок [a, b] делится пополам и вычисляются значения функции Q (x1) = F1 и Q (x2) = F2 в точках

На основе анализа значений F1 и F2 вдвое уменьшается интервал неопределенности и процесс повторяется пока b – a > Δ. Блок-схема этого метода приведена на рис. 3.5, б.

 

3.3.2 Метод "золотого сечения"

Гораздо эффективнее, с точки  зрения уменьшения затрат на вычисления, метод "золотого сечения": интервал неопределенности делится не пополам, как в методе дихотомии, а в  определенном иррациональном соотношении  τ=ac/cb=cb/ab.

Это соотношение выполняется  при 

Метод заключается в том, что по заданным a и b как можно точнее определяется значение внутренней точки x₁ (см. рис. 3.6, б) по формуле

x₁ = b – (b – a) / 1,618033989…     (3.6)

Точка x2 определяется как точка, симметричная точке x₁ на отрезке (a – b).

На основе анализа значений F₁ = Q (x₁) и F₂ = Q (x₂) интервал неопределенности сокращается путем отбрасывания из рассмотрения отрезка в котором экстремум исключен, исходя из условий унимодальности Q (u). Далее мы определим симметричную точку внутри новых границ, вычисляем значение Q в этой точке, проводим анализ и т.д. до тех пор, пока разность между симметричными точками внутри интервала неопределенности больше Δ. Блок-схема алгоритма метода "золотого сечения" представлена на рис. 3.7.

Рис. 3.7 Блок-схема  метода "золотого сечения"

 

3.3.3 Метод Фибоначчи

Метод, использующий числа  Фибоначчи, позволяет наиболее эффективно достичь заданной точности в поиске экстремума функции Q (u). Числа Фибоначчи определяются соотношением F₀ = F₁ = 1; F_k = F_k–1 + F_k–2; k = 2, 3, …

При большом "k" отношение соседних чисел Фибоначчи близко к отношению "золотого сечения".

Этот метод делит интервал неопределенности не в постоянном соотношении, а в переменном и предполагает некоторое, вполне определенное, зависящее  от Δ, число вычислений значений функции Q (u).

По заданному Δ определяется количество вычислений n и соответствующее ему число Фибоначчи F_n, исходя из соотношения

В остальном схема метода близка к методу "золотого сечения" в котором значение x₁ и x₂ (см. рис.3.8) определяются отношением соответствующих чисел Фибоначчи.

3.4 Методы многомерной оптимизации

 

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

Смысл всех методов нахождения безусловного экстремума функции нескольких переменных заключается в том, что  по определенному правилу выбирается последовательность значений {uι} вектора u такая, что Q (ul+1) ≤ (≥) Q (ul). Так как целевая функция предполагается ограниченной, то такая последовательность ее значений стремится к пределу.

В зависимости от принятого  алгоритма и выбора начальной  точки этим пределом может быть локальный  или глобальный экстремум функции Q (u).

 

3.4.1 Метод Гаусса-Зайделя

Метод заключается в последовательном определении экстремума функции  одной переменной с точностью  до ε вдоль каждой координаты, т.е. фиксируются все координаты, кроме  одной, по которой и осуществляется поиск экстремума Q. Потом та же процедура осуществляется при фиксации следующей координаты.

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

 

3.4.2 Метод градиента