Математические методы принятия решений. Бодров В.И - 24 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

ния 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, в. Здесь захо-
дить в заштрихованную область нельзя.
•
u
опт
•
ϕ
(u) = 0
а)
б)
в)
ϕ
1
(u) = 0
ϕ
2
(u) = 0
•
Рис. 3.1 Геометрическое представление целевой функции:
а – линии равного уровня; б – линии равного уровня и связи типа равенств;
в – линии равного уровня и ограничения типа неравенств
Особенностями целевой функции являются седловые точки, так называемые "овраги" и многоэкс-
тремность. В седловых точках функция Q (
u) по одному или нескольким направлениям имеет минимум,
в то время как по остальным – максимум. При наличии оврагов вдоль определенных направлений вели-
чина функции Q (
u) изменяется очень слабо. Целевая функция может иметь не один, а несколько опти-
мумов. Оптимум называется глобальным, если для него справедливо условие
Q (
u
опт
) ≤ Q (u), u ∈ U, которое выполняется для любых допустимых значений u. Если существуют дру-
гие оптимумы, то они называются локальными, и соотношения типа
)()(
опт
uu QQ ≤ выполняется только в
окрестностях точек
.
опт
u
Для отыскания глобального оптимума необходимо найти и проверить, вообще
говоря, все без исключения локальные оптимумы, имеющейся целевой функции.
Среди методов, применяемых для решения задач нелинейного программирования значительное ме-
сто занимают методы поиска решения, основанные на анализе производных оптимизируемой функции.

Страницы