Метод розенброка для решения задач нп при наличии ограничений

Пускай имеем задачу НП: минимизировать

,

(1)

при ограничениях

.

(2)

Розенброком было предложено преобразование задачи НП (1)¸(2) к присоединённой функции без ограничений вида:

Метод розенброка для решения задач нп при наличии ограничений

,

(3)

где

при

и

при

.

Следовательно, (3) вне допустимой области обращается в нуль. Предполагается, что в каждой точке допустимой области целевая функция принимает отрицательное значение, т.е.

. В случае если в некоторых либо кроме того во всех точках допустимой области

была хорошей, то вычитанием из

солидного постоянного числа

, будем иметь:

. Ясно, что

в этом случае не изменится.

Численный оптимизационный поиск задачи (3) может начинаться не только с внутренней точки

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

Чтобы продемонстрировать на связь между функцией (3) и присоединённой функцией ((4) в прошлом заголовке), прологарифмируем левую и правую части (3), предварительно поменяв их символы и перейдя от минимизации к максимизации, возьмём:

Метод розенброка для решения задач нп при наличии ограничений

,

(3′)

(Умножить

и

нужно для того, чтобы получить положительные значения). Т.к.

Метод розенброка для решения задач нп при наличии ограничений

на любой стадии вычислительного процесса есть константой, то возможно положить

и вычислять, что

, следовательно соответствие между (3) и (4 в прошлом заголовке) установлена.

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

Пускай

– единичные векторы,

– индекс, обозначающий этапы поиска. Ортонормированные векторы

строятся на основании информации, взятой на

-м этапе (будет продемонстрировано ниже).

На начальной стадии

, направления

в большинстве случаев берутся параллельными осям

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

Метод розенброка для решения задач нп при наличии ограничений

,

(4)

где

– единичный вектор в направлении

;

– единичный вектор в направлении

.

Совокупность (4) в матричной форме:

.

(5)

Разглядим

-й этап:

Поиск начинается из начальной точки

, для чего вводится возмущение, равное

, в первом координатном направлении (

– протяженность шага, которая связана с направлением

). В случае если значение

, то ход считается успешным и полученная пробная точка заменяет

.

умножается на множитель

и вводится возмущение по направлению

. В случае если

, то ход считается неудачным и

не заменяется,

умножается на

и опять задаётся возмущение по направлению

. Розенброком предложено в общем случае брать значения параметров

.

По окончании того как пройдены все направления

,

, опять возвращаются к первому направлению

и вводится возмущение с длиной шага, равной

либо

, в зависимости от результата прошлого возмущения по направлению

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

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

уменьшают последовательно длины шагов. Причём, последняя полученная точка делается начальной точкой следующего этапа

.

Нормированное направление

берётся параллельым

, а остальные направления выбираются ортонормированными друг к другу и к

посредством одного из способов:

К примеру: Пускай

– имеется алгебраическая сумма всех успешных шагов (суммарное перемещение) в направлении

на

м этапе. Определим

векторов по формулам:

Метод розенброка для решения задач нп при наличии ограничений

.

(6)

Так

– имеется вектор перехода из

в

,

– имеется вектор перехода из

в

и т.д.

Следовательно

представляет собой полное перемещение с

-го этапа на

-й этап,

– полное перемещение, но без учёта продвижения, сделанного на протяжении поиска в направлении

и т.д.

В случае если в (6) каждые

из

обращаются в нуль, то новые направления отыскивают лишь для тех

направлений, для которых

; остальные

направлений остаются неизменными:

,

(7)

Так, векторам с нулевыми

приписываются первые

номеров.

Так как первые

векторов взаимно ортогональны и для

;

, то они не будут иметь составляющих в направлениях

,

. А так как последние направления взаимно ортогональны, то из этого направляться, что все направления являются взаимно ортогональными.

Итак, направления на

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

выбирается так, дабы он совпадал с направлением результирующего перемещения на прошлом этапе

. Остальные направления поиска строятся как взаимно ортогональные к

единичные векторы (ортонормированные). [Описание для того чтобы построения дано в работах по теории матриц и линейной алгебре].

Коротко, без доказательств, комплект ортонормированных векторов

на

-м этапе вычисляется по следующим соотношениям:

Метод розенброка для решения задач нп при наличии ограничений

,

(8)

где

– норма

;

– норма

.

Та же процедура поиска, которая проводилась на

-м этапе повторяется после этого на

-м этапе с точки

.

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

. Поиск или проводится на определённое число этапов, или заканчивается, когда величина

делается меньше определённого значения на нескольких последовательных этапах. Также, возможно по окончании каждого этапа расстояние

сравнивать с размером шага

.

В случае если

, то

дробят на 10, и предстоящий поиск осуществляется в

прошлых направлениях с новым

.

В случае если

, то поиск длится на

-м этапе, как было поведано выше.

Разглядим числовой пример для иллюстрации способа Розенбока:

Минимизировать

,

(1п)

Выбираем начальную точку, к примеру

, вычислим

.

Этап 1: Выбираем направления начального поиска, совпадающими с координатными осями

и

, т.е.

,

Задаёмся длиной шага

и

. Вводим возмущение в направлении

, вычислим:

Метод розенброка для решения задач нп при наличии ограничений

,

т.е. имеем

, т.е. имеет место неудача. Следовательно, умножаем

на

. Вводим возмущение в направлении

, вычислим:

Метод розенброка для решения задач нп при наличии ограничений

,

т.е.

, т.е. опять имеет место неудача. Следовательно, на следующем цикле кроме этого

.

Вводим возмущение

в направлении

из последнего успешного значения

, т.е.

.

Метод розенброка для решения задач нп при наличии ограничений

,

т.е.

, т.е. имеет место успех. Следовательно:

, где

, т.е.

Вводим возмущение

в направлении

из точки

:

Метод розенброка для решения задач нп при наличии ограничений

,

Следовательно, на следующем цикле

.

Потом производятся подобные расчёты на 1-м этапе поиска. Числовые эти по предстоящим циклам 1-го этапа продемонстрируем в следующей таблице (таб.39):

функция и Условный экстремум Лагранжа

Похожие статьи:

Понравилась статья? Поделиться с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!:

Adblock
detector