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

Оглавление

1. Теоретическая основа метода оптимизации

.1 Постановка задачи

.2 Математические основы метода

.3 Пример расчета экстремума функции методом прямого поиска с дискретным шагом

.4 Анализ результатов расчетов

. Программная реализация задачи на ЭВМ

.1 Описание структуры программы

.2 Результаты отладки программы на контрольных примерах

.3 Составление инструкции по использованию программы

. Исследование эффективности работы метода оптимизации на тестовых задачах

.1 Выбор и описание тестовых задач

.2 Исследование влияния начального приближения

.3 Исследование работоспособности метода путем решения задач различной размерности и сложности

.4 Обработка результатов исследований визуальными и формальными средствами Excel

1. Теоретическая основа метода оптимизации

1.1 Постановка задачи

Целью данной работы является разработка компьютерной системы для решения задач многомерной оптимизации методом прямого поиска с дискретным шагом.

Для реализации поставленной цели необходимо решить следующие задачи:

Проанализировать теоретические основы метода оптимизации;

Программно реализовать данный метод оптимизации;

Исследовать эффективность работы метода оптимизации на контрольных примерах;

1.2 Математические основы метода

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

Рисунок 1 - Траектория метода прямого поиска с дискретным шагом

Рассматриваемый метод состоит из следующих операций. Исследующий поиск. Задается начальное приближение X(1) и приращения по координатам D X. Рассчитывается значение f(X(1)) в базисной точке. Затем в циклическом порядке совершаются пробные шаги. Если приращение улучшает целевую функцию, то шаг считается удачным . По этой переменной значение изменяется на величину шага и дается приращение по другой переменной (см. рисунок 1). Иначе - неудачным и делается шаг в противоположном направлении. И если он тоже оказался неудачным , то значение этой переменной оставляют без изменения и дается приращение по другой переменой и т.д. пока не будут изменены все независимые переменные. На этом завершается первый исследующий поиск, найдена точка X(2).