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

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«ТЮМЕНСКИЙ ИНДУСТРИАЛЬНЫЙ УНИВЕРСИТЕТ»

Кафедра бизнес-информатики и математики

КУРСОВАЯ РАБОТА ПО ДИСЦИПЛИНЕ

«МЕТОДЫ ОПТИМИЗАЦИИ»

              Выполнил:  

Проверил:          

Дата:  «_____»_____________ 20____г.

СОДЕРЖАНИЕ

Введение        3

1        Описание метода хука-дживса        5

1.1        прицнип работы и идея метода        5

1.2        математическое описание        6

1.3        преимущества и недостатки метода        9

2          реализация метода хука-дживса на delphi        11

2.1        описательная часть алгоритма и решение задачи        11

Заключение        15

Список используемых источников        16

Приложение A        17

Введение

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

     Один из методов решения задач нелинейного программирования –  метод Хука-Дживса, который был разработан в 1961 году В. Хуком и Д. Дживсом.

     Он относится к классу методов без производных и основан на поиске по образцу (паттерн-поиске). Он пытается улучшить текущее решение, пошагово перемещаясь вокруг него в поисках более оптимального решения. Если новое решение получается лучше, чем текущее, метод Хука-Дживса перемещается в сторону нового решения, иначе - метод возвращается к предыдущему шагу.                 Обычно метод Хука-Дживса используется для задач с небольшим количеством переменных или для начального приближения на сложных задачах оптимизации.

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

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

1. Принцип работы и идея метода

     Основная идея данного метода состоит в организации повторного процесса, во время которого происходят расчеты, а итерация представляет собой переход от предыдущего приближения x(k-1) к последующему x(k). Данный метод делится на две фазы: исследующий поиск и поиск по образцу, и проверить условия сходимости.

     Процедура поиска минимума с помощью метода Хука-Дживса состоит из следующих шагов:

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

            2. Определяется шаг поиска (экспериментальный параметр), который используется для нахождения новой точки, удаленной на расстояние h по направлению экспериментального вектора s, который может быть произвольным (например, s = (1,0,...,0) – поиск вдоль оси X1).