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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


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

Информация:

Тип работы: Контрольная. Предмет: Математика. Добавлен: 16.08.2010. Сдан: 2010. Уникальность по antiplagiat.ru: --.

Описание (план):


Численные методы решения задач условной многомерной оптимизации
Пояснительная записка к курсовой работе по курсу "Методы оптимизации"
Аннотация
Используемые термины: Пусть X и Y -- два множества. Закон F, согласно которому каждому элементу поставлен в соответствие единственный элемент, называется отображением множества X в множество Y или функцией, заданной на X со значениями в Y. Экстремум -- максимальное или минимальное значение функции на заданном множестве. Задача безусловной оптимизации состоит в нахождении минимума или максимума функции в отсутствие каких-либо ограничений. Условная оптимизация -- поиск минимума или максимума функции при наличии ограничений. Безусловная оптимизация -- поиск минимума или максимума функции без наличия активных ограничений. Последовательность определенных и неотрицательных функций на множестве называют штрафом или штрафной функцией. Итерационный процесс -- многократно повторяющиеся действия (вычисления) до выполнения некоторого условия окончания. Целевая функция - функция, связывающая цель (оптимизируемую переменную) с управляемыми переменными в задаче оптимизации.
В данной работе решается задача поиска экстремума (максимума) функции нескольких переменных при наличии ограничения равенства. Для решения используется метод штрафных функций, который позволяет свести задачу поиска условного экстремума к решению последовательности задач на поиск безусловного экстремума вспомогательной функции.
Число страниц
22
Число рисунков
9
Число таблиц
2
Число приложений
2
Оглавление

Введение
1. Основная часть
1.1 Постановка задачи
1.2 Анализ задачи
1.3 Описание метода штрафных функций
1.4 Графическое решение задачи
1.5 Формализация расчетов
2. Структура приложения, предназначенного для решения задачи
3. Результаты вычислений
4. Выводы
5. Список литературы
6. Приложения
Введение

Математическое программирование - математическая дисциплина, изучающая теорию и методы решения задач о нахождении экстремумов функции на множествах конечномерного векторного пространства, определяемых линейными и нелинейными ограничениями (равенствами и неравенствами). В зависимости от природы множеств задачи математического программирования классифицируются как:
· задачи дискретного программирования (или комбинаторной оптимизации) - если множество конечно и счетно;
· задачи целочисленного программирования - если множество является подмножеством множества целых чисел;
· задачи линейного программирования - если все ограничения и целевая функция содержат лишь линейные функции;
· задачи нелинейного программирования - если ограничения или целевая функция содержат нелинейные функции и множество является подмножеством конечномерного векторного пространства.
Оптимизация - целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.
Математическое программирование используется при решении оптимизационных задач исследования операций. Способ нахождения экстремума полностью определяется классом поставленной задачи.
В данной работе поставлена задача условной оптимизации, т.е. задача, содержащая некоторые ограничения по независимым переменным на множестве G. Эти ограничения задаются совокупностью некоторых функций, удовлетворяющих равенствам или неравенствам. Ограничения - равенства выражают зависимость между проектными параметрами, которая должна учитываться при нахождении решения. Ограничения-неравенства устанавливают менее жесткие зависимости между проектными параметрами, позволяя им в некоторой части области G оставаться независимыми, а в остальной части проявляется зависимость друг от друга. Решение задачи условной оптимизации зачастую нельзя найти, используя аналитические методы решения, поэтому требуется использование дополнительных численных методов.
В настоящее время разработано множество численных методов для задач как безусловной, так и условной оптимизации.
Методы условной оптимизации, как правило, сводят решение исходной задачи к многократному решению вспомогательной задачи безусловной оптимизации.
Решение безусловной оптимизации является более простым и легко реализуется в современных математических пакетах. Для решения поставленной задачи использовались средства программы MathCAD. Данная программа позволяет выполнить как численные, так и аналитические вычисления, имеет удобный математически-ориентированный интерфейс и прекрасные средства графики. Система MathCAD изначально создавалась для численного решения математических задач, позже в нее были интегрированы инструменты символьной математики из системы Maple, что постепенно превратило MathCAD в универсальный инструмент решения математических задач. Поэтому выбор данного программного средства вполне обоснован.
1. Основая часть

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

Требуется найти точку такую, что
f( x*) = x1 ? 2x22 + 4x2 > max (1)
где (2)
с помощью метода штрафных функций.
1.2 Анализ задачи

Данная задача относится к классу задач нелинейного программирования. Решается методом штрафных функций. Этот метод заключается в сведении задачи, на условный экстремум, к решению последовательности задач на поиск безусловного экстремума вспомогательной функции, которая будет составлена по нижеописанным методам. Решение новой задачи проведем двумя методами безусловной оптимизации разного порядка. Для данного проекта были выбраны метод сопряженных направлений, который является методом нулевого порядка, и метод наискорейшего градиентного спуска, являющийся методом первого порядка.
Недостатком метода наискорейшего спуска является его низкая эффективность в оптимизации овражных функций. Применение данного метода допустимо, так как функция непрерывна на всей области определения (областью определения функции является вся плоскость (x1,x2)), и непрерывны ее частные производные первого порядка:
Оба метода безусловной оптимизации сводят задачу поиска наименьшего значения функции нескольких переменных к многократному решению одномерных задач оптимизации. Метод наискорейшего градиентного спуска гарантирует сходимость к точке минимума для сильновыпуклых функций. При уменьшении выпуклости уменьшается и скорость сходимости итерационного процесса. Если требуется найти глобальный минимум функции, то для строго выпуклой функции решение этой задачи аналогично поиску локального минимума. В случае существования нескольких минимумов, поиск глобального минимума сводится к перебору всех локальных минимумов. В методе сопряженных направлений используется тот факт, что минимум квадратичной функции может быть найден не более чем за n шагов при условии, что поиск ведется вдоль сопряженных относительно матрицы Гессе направлений. Так как достаточно большой класс целевых функций может быть представлен в окрестности точки минимума квадратичной аппроксимацией, описанная идея применяется и для неквадратичных функций. Исходная функция является строго выпуклой и, соответственно, имеет только один минимум, что оправдывает выбор методов для поиска безусловного экстремума. Методы безусловной оптимизации можно оценить по следующим параметрам:
1. Точность поиска - значение окрестности локального оптимума, в которую приводит алгоритм после выполнения заданного числа итераций.
2. Скорость сходимости - число итераций, необходимое для достижения заданной точности.
3. Время счета - время поиска на ЭВМ локального оптимума с заданной точностью, отнесенное к коэффициенту сложности задачи (или к быстродействию ЭВМ).
4. Стабильность - свойство алгоритма незначительно увеличивать число итераций при малых возмущениях выбора начальных точек, а также вследствие погрешности вычислений.
5. Надежность - свойство алгоритма приводить к оптимуму при многократном повторении поиска из разных начальных точек.
1.3 Описание метода штрафных функций
Идея метода штрафных функций заключается в сведении задачи (1-2) на условный экстремум к решению последовательности задач на поиск безусловного экстремума вспомогательной функции:
, (3)
где -штрафная функция, -параметр штрафа, задаваемый на каждой k-ой итерации (k=1, 2, 3,…).
Шаг 1. Задать начальную точку ; начальное значение параметра штрафа >0; число C>1 для увеличения параметра; малое число >0 для остановки алгоритма. Положить k=0.
Шаг 2. Составить вспомогательную функцию
Шаг 3. Найти точку безусловного минимума функции по х с помощью какого-либо метода (нулевого, первого или второго порядка):
При этом задать все требуемые этим методом параметры. В качестве начальной точки взять . Вычислить
Шаг 4. Проверить условие окончания:
а) если , процесс поиска закончить:
б) если, положить: и перейти к шагу 2.
1.4 Графическое решение задачи

Рис. 3. Изображение вспомогательной функции при r = 10 и т.д.................


Перейти к полному тексту работы



Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.