Программная модель поиска глобального минимума нелинейных "овражных" функций двух переменных - Курсовая работа

Проблема выбора оптимального варианта решения относится к числу наиболее актуальных технико-экономических проблем. В математической постановке она представляет собой задачу минимизации (максимизации) некоторого функционала, описывающего те или иные характеристики системы. Численное решение оптимизационных задач на ЭВМ сводится к поиску экстремума функции многих переменных. Среди различных типов оптимизационных задач особое место занимают задачи оптимизирования невыпуклых детерменированных функций с единственной точкой экстремума. Эти задачи представляют интерес с различных точек зрения.А именно: функция f называется унимодальной на отрезке [a,b], если она имеет на этом отрезке единственную точку глобального минимума Xmin и слева от этой точки является строго убывающей, а справа строго возрастающей (см. рис. Другими словами, функция f унимодальная, если точка Xmin существует и единственна, причем для любых двух точек х1, х2 I [a,b] таких, что х1Xmin всегда следует f(x1)f(x2). Функция f(x) называется строго выпуклой, если для любых точек х1 и х2 из области ее определения имеет место неравенство: F(lx1 (1-l)x2)< lf(x1) (1-l)f(x2), LI(0,1). Функции, унимодальные по любому направлению, если это направление происходит через точку минимум, образуя класс строго унимодальных функций [3]. Функция, допускающая такое разбиение переменных в некоторой области, называется хорошо организованной (овражной) функцией в этой области, а число существенных переменных определяет размерность оврага [4].Сущность всех методов приближенного решения этой задачи состоит в построении последовательности точек х1, х2, х3, …, хк, …, монотонно уменьшающих значение целевой функции: f(x0) >= f(x1) >= f(x3) >= … >= f(xk) >= … (1.3) Такие методы (алгоритмы) называют методами спуска. Если же метод предполагает использование и вторых производных, то его называют методом второго порядка и т.д. Сходимость здесь понимается в том смысле, что последовательность {xk} должна сходиться к точке глобального (локального) минимума. Однако точки минимума могут составлять целое множество и многие алгоритмы позволяют построить последовательность {xk}, которая сама не является сходящейся, но любая ее сходящаяся последовательность имеет в качестве предельной некоторую точку минимум (см. рис.Ненулевой антиградиент - Nf(x0) указывает направление, небольшое перемещение вдоль которого из х0 приводит к значению функции f меньшему, чем f(x0). Эти методы отличаются друг от друга способом выбора величины шага ak. Достаточно малый шаг ak обеспечивает убывание целевой функции f(xk 1) = f(xk - ak Nf(xk)) <f(xk), (1.4) но может привести к слишком большому количеству итераций для достижения требуемой точности. Часто величину ak рекомендуют выбирать так, чтобы имело место более жесткое условие убывания, чем 1.4: f(xk) - f(xk - AKNF(xk)) >= eak || Nf(xk) ||, (1.5) где 0 0 (например, ak = 1), одинаковое для всех итераций, а затем при необходимости уменьшают его до тех пор, пока не будет выполнено неравенство 1.5. Пусть функция f ограничена снизу, непрерывно дифференцируема на R и ее градиент Nf(x) удовлетворяет условию Липшица: || Nf(x)-Nf(x’) || <= L || x - x’ || для всех x,x’ I R, где L >= 0 - некоторая фиксированная константа.Поиск минимума функции R(x) выполняют по шагам начиная с начальной точки. На первом шаге вычисляют значение функции, градиент поля функции, путем вычисления частной производной по каждой переменной, модуль градиента, значения переменных в шаге и величину шага по каждой переменной.Перед началом работы над курсовым проектом передо мной встал вопрос: в какой системе программирования или с помощью какого приложения я буду писать программу по данной мне теме. Кроме того, в данный программный продукт встроен редактор Visual Basic, с помощью которого можно писать макросы. Visual Basic предоставляет единую законченную среду редактирования, схожую со средой автономной версии Visual Basic 5.0. Среда редактирования Visual Basic включает улучшенный редактор кода, иерархическое средство просмотра объектов, многооконный отладчик, окно отображения свойств и средство просмотра проектов для управления кодом и объектами проекта. Для облегчения создания синтаксически правильного кода среда редактирования Visual Basic имеет группу команд в меню Правка, включающую команды Список свойств/методов, Список констант и Параметры.Ввод данных осуществляется с помощью диалогового окно «Ввод данных» (см. рис. Вывод промежуточных и выходных данных осуществляется в таблицу (см. табл.Минимальные требования предъявляемы к аппаратной части: Процессор - 486 DX/2 80Mz В качестве операционной среды на персональном компьютере должна быть установлена одна из версий Windows (9x, 2000, NT 4.0, XP, Me), а также программный пакет Microsoft Office (97, 2000) или, хотя бы, Microsoft Excel.Найти минимум функции В начальных точках х1=-0,5, х2=-1 вычислим по методу градиента значение функции, градиент поля функции, значение переменных в шаге и величину шага. Полученные данн

Содержание

Введение

1. Пояснительная записка

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

1.2 Численные методы в задачах без ограничений

1.2.1 Общая схема методов спуска

1.2.2 Градиентные методы

1.2.3 Метод наискорейшего спуска

2. Инструментальные программные средства

3. Блок-схема алгоритма моделирования

4. Операционная среда

5. Контрольная задача

Заключение

Литература

Приложение

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

Численное решение оптимизационных задач на ЭВМ сводится к поиску экстремума функции многих переменных. Таковы задачи оптимального управления и идентификации, задачи супервизорного управления, оптимизационного проектирования и планирования.

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

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

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

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

При этом, число работ, посвященных унимодальным задачам, сравнительно не велико. Аналитические методы исследования невыпуклых задач не разработаны изза принципиальной сложности, численные методы, как правило, ориентированы на более простые классы задач.