Нелинейное программирование. Метод Хука-Дживса

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

    Обозначим через – координатные направления:

    

      Отметим, что при поиске по  направлению меняется только переменная , а остальные переменные остаются зафиксированными. 

    

2. АЛГОРИТМ  МЕТОДА ХУКА-ДЖИВСА.

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

      Шаг 2.  Провести исследующий поиск по выбранному координатному направлению:

     

      Шаг 3.  Проверить условия:

    а) если i < n, то положить i= i+1 и перейти  к шагу 2. (продолжить исследующий поиск по оставшимся направлениям);

    б) если i = n, проверить успешность исследующего поиска:

    - если , перейти к шагу 4.

    - если , перейти к шагу 5.

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

    

    В точке провести исследующий поиск, в результате которого получается точка

    Если , то точка становится точкой нового базиса, а - точкой старого базиса. Перейти к шагу 5. .

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

    Шаг 5.  Проверить условие окончания счета:

    а) если все  , то поиск закончить ;

    б) для тех i, для которых  , уменьшить величину шага и перейти к шагу 2.  

      Пример.

    Найти минимум функции 

      Решение. 

      Зададим начальную точку ; число . Положим i=1, k=0.

     , то шаг неудачен. , то шаг удачен.

     Поскольку i=1 <2=n, то положим i=2 и перейдем к шагу 2.

    

     , то шаг неудачен.

     ,то шаг удачен 

      Поскольку i=2=n и  , то перейдем к шагу 4.

      Проведем поиск по образцу  из точки Положим i=1, k= k+1=1. и перейдем к шагу 2.

      Выполняем исследующий поиск из точки . , то шаг неудачен. Т.к. , то шаг удачен.

      Поскольку i=1 <2=n, то положим i= i+1=2 и перейдем к шагу 2.

     , то шаг неудачен. , то шаг неудачен.

       , то поиск по образцу на шаге 40 прошел успешно.

    Точка становится новым базисом, а точка становится старым базисом. Выполним поиск по образцу из нового базиса. Перейдем к шагу 4.

      Положим i=1, k=k+1=2. 

    и перейдем к шагу 2.

     , то шаг удачен.

      Поскольку i=1 <2=n, то положим i= i +1=2 и перейдем к шагу 2.

     , то шаг удачен.

      Т.к. i=2=n и f(4,5)=5 > f(5,5)=1, то поиск по образцу на прошел неудачно. Переходим к шагу 5.

     , то следует уменьшить шаг.  Положим , за базис возьмем точку (5,5) и повторим цикл вычислений с новым базисом и новыми значениями шагов. Минимум достигается в точке  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

    Заключение 

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

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

Список  используемой литературы: 

1. «Электронный  учебник "Экономико-математические методы" » под разработкой Коляденкова И. С., Ванькина Н. Г., по курсу лекций Ширяева В. Д.
2. «Учебное пособие "Методы Оптимизации Систем Автоматизированного Проектирования" http://www.optimizaciya-sapr.narod.ru)