s:=e_k, l_k=argmin j(x*+ls)

         x’:=x*+l_ks

         x*:=x’

       Конец.

    Шаг 3.

       Если  ||l|| > e, то иди на Шаг 2,

       иначе Конец. 

 

    

    3. Программная реализация

    3.1 Программная реализация метода экстремального поиска

    Алгоритм  метода экстремального покоординатного поиска был реализован в программной среде Delphi. Входными данными программы стали: точность вычислений, начальная точка, размерность и коэффициенты минимизируемой функции. Выходными: точка минимума, значение функции в точке минимума и количество итераций.

    Программа позволяет производить расчеты  с использование некоторых методов одномерной оптимизации: метода дихотомии, метода деления отрезка пополам и метода касательных. При включении программы на форме находятся лишь входные данные; для произведения расчёта необходимо воспользоваться главным или контекстным меню, позволяющим выбрать один из методов одномерной оптимизации.

    Программа имеет автоматическое расширение или  сужение, а также центрирует все  компоненты, расположенные на форме, в зависимости от их параметров.

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

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

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

    Форма программы имеет следующий вид: 

    

Рисунок 1- Окно программы «Метод экстремального покоординатного поиска» 

    Программа протестирована на примерах, просчитанных в Excel. Результаты тестирования совпали.

 

 
    

 
    3.2 Анализ быстродействия  работы различных  методов

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

    Таблица 1 – Зависимость количества итераций от заданной точности 0,01

    Таблица 2 – Зависимость количества итераций от заданной точности 0,001

    Таблица 3 - Зависимость количества итераций от заданной точности 0,0001

 
 

    Таким образом, на основе полученных данных зависимости, можно сделать вывод, что размерность и выбранный одномерный метод оптимизации не влияют на количество итераций. При точности 0,01 количество итераций составляет 9-12, при точности 0,001 – 12-15, при точности 0,0001 – 16-19.

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

      

    Заключение

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

    В данной курсовой работе рассмотрен метод  экстремального покоординатного поиска. В работе дана постановка задачи многомерной  оптимизации, приведены методы одномерной оптимизации, использующиеся при нахождении минимального значения многомерной функции методом экстремального покоординатного поиска, приведён алгоритм данного метода. Алгоритм реализован в программной среде Delphi. Программа позволяет производить расчёты с использованием следующих методов одномерной оптимизации: метода дихотомии, метода деления отрезка пополам и метода касательных. Программа протестирована на примере, рассчитанном в Excel. Результаты тестирования совпали.

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

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

 

    

    Список  литературы

    1.Банди Б. Методы оптимизации (вводный курс). М.: Радио и связь, 1988. 69 с.

    2.Васильев Ф.П. Численные методы решения экстремальных задач. М.: Наука, 1980. 184 с.

    3.Карманов В.Г. Математическое программирование. Учебное пособие. М.: Наука, 2000. 52 с.

    4.Подиновский В.В., Ногин В.Д. Парето - оптимальные решения    многокритериальных задач. М.: Наука, 1982. 59 с.

    5.Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983. 72 с.

    6.Юдин Д.Б., Гольштейн Е.Г. Линейное программирование: Теория и конечные методы. М.: Наука, 1964. 91 с.

    7.Янг Л. Лекции по вариационному исчислению и теории оптимального управления. М.: Мир, 1974. 54 с.