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

и j=1,2,3,…,n

Приращения Нелинейное программирование и Нелинейное программирование, зависящие только от n и выбранного мас­штабного множителяНелинейное программирование, определяются по формулам

Нелинейное программирование (8)

Нелинейное программирование (9)

Заметим, что величина масштабного множителя Нелинейное программированиевыбирается ис­следователем, исходя из характеристик решаемой задачи. При Нелинейное программирование=1 ребра регулярного симплекса имеют единичную длину. Вычисления второго типа, связанные с отражением относи­тельно центра тяжести, также представляют несложную процедуру. Пусть Нелинейное программирование— точка, подлежащая отражению. Центр тяжести осталь­ных n точек расположен в точке

Нелинейное программирование (10)

Все точки прямой, проходящей через Нелинейное программирование и хс, задаются формулой

Нелинейное программирование (11)

При Нелинейное программирование=0 получаем исходную точку Нелинейное программирование, тогда как значение Нелинейное программирование=1 соответствует центру тяжести хс. Для того чтобы построенный симп­лекс обладал свойством регулярности, отражение должно быть сим­метричным. Следовательно, новая вершина получается при Нелинейное программирование=2. Таким образом,

Нелинейное программирование (12)

Проиллюстрируем вычислительную схему метода следующим при­мером.

Пример 5. Вычисления в соответствии с методом поиска по симплексу

Минимизировать f(x)=Нелинейное программирование

Решение.

Для построения исходного симплекса требуется задать начальную точку и масштабный множитель. Пусть xНелинейное программирование =Нелинейное программированиеи Нелинейное программирование=2. Тогда

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

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

Используя эти два параметра, вычислим координаты двух остальных вершин симплекса:

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

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

которым соответствуют значения целевой функции, равные Нелинейное программирование=0,2374 и Нелинейное программирование3,0658. Так как Нелинейное программирование5, необходимо отразить точку Нелинейное программированиеотносительно центра тяжести двух остальных вершин симплекса

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

Используя формулу (12), получаем

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

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

В полученной точке Нелинейное программирование2,3027, т. е. наблюдается уменьшение целевой функции. Новый симплекс образован точками Нелинейное программированиеиНелинейное программирование. В соответствии с алгоритмом следует отразить точку х(2), ко­торой соответствует наибольшее значение целевой функции, отно­сительно центра тяжести точек Нелинейное программированиеи х(3). Итерации продолжаются до тех пор, пока не потребуется применение правил 1, 2 и 3, которые были сформулированы выше.

Изложенный выше алгоритм Нелинейное программирование- метода имеет несколько очевид­ных преимуществ.

1. Расчеты и логическая структура метода отличаются сравни­тельной простотой, и, следовательно, соответствующая программа для ЭВМ оказывается относительно короткой.

2. Уровень требований к объему памяти ЭВМ невысокий, мас­сив имеет размерность (n+1, n+2).

3. Используется сравнительно небольшое число заранее уста­новленных параметров: масштабный множитель Нелинейное программирование, коэффициент уменьшения множителя Нелинейное программирование(если применяется правило 2) и параметры окончания поиска.

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

Перечисленные факторы характеризуют метод поиска по симплек­су как весьма полезный при проведении вычислений в реальном времени.

Алгоритм обладает также рядом существенных недостатков.

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

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

3. Не существует простого способа расширения симплекса, не требующего пересчета значений целевой функции во всех точках образца. Таким образом, если Нелинейное программированиепо какой-либо причине уменьшается (например, если встречается область с узким «оврагом» или «хреб­том»), то поиск должен продолжаться с уменьшенной величиной шага.


4.1.2. Метод поиска Хука-Дживса.

Метод, разработанный Хуком и Дживсом, является одним из первых алгоритмов, в которых при определении нового направления поиска учитывается информация, полученная на предыдущих итерациях. По существу процедура Хука—Дживса представляет собой комбинацию «исследующего» поиска с циклическим изменением переменных и ускоряющегося поиска по образцу с использованием определенных эвристических правил. Исследующий поиск ориентирован на выявление характера локального поведения целевой функции и определение направлений вдоль «оврагов». Полученная в результате исследующего поиска информация затем используется в процессе поиска по образцу при движении по «оврагам».

Исследующий поиск.

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

Поиск по образцу.

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

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

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

Нелинейное программирование- текущая базовая точка,

Нелинейное программирование- предыдущая базовая точка,

Нелинейное программирование- точка, построенная при движении по образцу,

Нелинейное программирование- следующая (новая) базовая точка.

Приведенная последовательность характеризует логическую струк­туру поиска по методу Хука — Дживса.

Структура метода поиска Хука — Дживса

Шаг 1 . Определить:

начальную точку Нелинейное программирование ,

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

коэффициент уменьшения шага Нелинейное программирование,

параметр окончания поиска Нелинейное программирование.

Ш а г 2. ровести исследующий поиск.

Ш а г 3. Был ли исследующий поиск удачным (найдена ли точ­ка с меньшим значением

целевой функции)?

Да: перейти к шагу 5.

Нет: продолжать.

Ш а г 4. Проверка на окончание поиска.

Выполняется ли неравенство Нелинейное программирование?

Да: прекратить поиск; текущая точка аппроксимирует точку оп­тимумаНелинейное программирование.

Нет: уменьшить приращения по формуле

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

Перейти к шагу 2.

Ш а г 5. Провести поиск по образцу:

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

Шаг 6. Провести исследующий поиск, используя Нелинейное программирование в ка­честве базовой точки;

пусть Нелинейное программирование полученная в результате точка.

Ш а г 7. Выполняется ли неравенство Нелинейное программирование?

Да: положить Нелинейное программирование Перейти к шагу 5.

Нет: перейти к шагу 4.


Пример 6 Поиск по методу Хука — Дживса

Найти точку минимума функции Нелинейное программирование используя начальную точку Нелинейное программирование.

Решение.

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

Нелинейное программирование векторная величина приращения = Нелинейное программирование,

Нелинейное программирование коэффициент уменьшения шага = 2,

Нелинейное программирование параметр окончания поиска = 10-4.

Итерации начинаются с исследующего поиска вокруг точки Нелинейное программирование, которой соответствует значение функции Нелинейное программированиеФиксируя Нелинейное программирование, дадим приращение переменной Нелинейное программирование:

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

Нелинейное программированиеУспех.

Следовательно, необходимо зафиксировать Нелинейное программирование и дать прираще­ние переменной Нелинейное программирование:

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

Нелинейное программирование Успех.

Таким образом, в результате исследующего поиска найдена точка

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

Поскольку исследующий поиск был удачным, переходим к поиску по образцу:

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

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

Далее проводится исследующий поиск вокруг точки Нелинейное программирование, который оказывается удачным при использовании положительных прираще­ний переменных х1 и х2. В результате получаем точку

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

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

Из примера следует, что метод Хука — Дживса характери­зуется несложной стратегией поиска, относительной простотой вычислений и невысоким уровнем требований к объему памяти ЭВМ, который оказывается даже ниже, чем в случае использования ме­тода поиска по симплексу.

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


Итерации поиска по методу Хука-Дживса на примере

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: