Оптимизационные методы минимизации и максимизации
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
о , и отрицателен при . Логарифмический штраф - это барьерная функция, неопределенная в точках, где . Поэтому на начальном этапе поиска, когда значение шага поиска невелико, необходимо обеспечить защиту процедуры от попадания рабочей точки в недопустимую область.
Штраф, заданный обратной функцией.
Как и предыдущий штраф, является барьерным. В допустимой области вблизи границы значение штрафа быстро убывает при продвижении внутрь допустимой области. На самой границе значение не определено, как и в предыдущем случае возможно появление недопустимых точек.
Штраф типа квадрата срезки.
,
Этот штраф является внешним, и недопустимые точки не создают проблем по сравнению с допустимыми. Различие заключается том, что в допустимых точках штраф равен нулю. Этот вид штрафа удобен тем, что непрерывна и определена всюду. Параметр положителен и увеличивается от итерации к итерации.
Алгоритм метода:
Шаг 1. Задать начальные данные:
- начальная точка
- начальное значение штраф параметра
- параметр окончания работы алгоритма
Шаг 2. Построить штрафную функцию:
Шаг 3. Находим , доставляющее экстремум , методом Ньютона.
Шаг 4. Выполняется ли условие:
Да: , процесс решения закончен.
Нет: перейти к шагу 5. Шаг 5. , перейти к шагу 2.
Нахождение минимума целевой функции :
Исходные данные:
Шаг 1.
- начальная точка;
Ограничение на решение:
Преобразуем целевую функцию введением в неё заданного квадратичного штрафа:
Шаг 2.
Шаг 3. Найдем минимум целевой функции с заданным квадратичным штрафом:
Совместное решение даёт:
Устремляя к нулю, получаем
То есть, при изменении от нуля до бесконечности, решение будет изменяться от минимума задачи с учётом ограничений до минимума функции без учёта ограничений.
Исследуем функцию при различных значениях параметра , то есть
Шаг 5,2-3.
1.
.
.
.
Сведем все данные в таблицу:
Решением задачи условной оптимизации является точка: , значение функции в которой равно: . Мы подтвердили, что при увеличении штрафного параметра все ограничения уменьшаются, что доставляет минимум задачи безусловной оптимизации. Наоборот, при уменьшении штрафного параметра до нуля вес ограничения возрастает, что доставляет минимум задачи условной оптимизации.
Рис 9. Графическое пояснение метода штрафных функций
Вывод: метод штрафных функций служит для решения задач условной оптимизации путем перевода их в задачу безусловной оптимизации. Как видно их рисунка, величина штрафного параметра сильно влияет на вид функции. При его увеличении "вес" ограничения в целевой функции уменьшается, и функция принимает свой обычный вид (без штрафной составляющей).
5. Разработка программного модуля
Цель работы: разработка программного продукта, находящего оптимум функции вида
при помощи метода Коши.
Требования к программе:
1.Возможность изменения исходных данных с клавиатуры.
2.Графическое отображение решения.
.Занесение результатов в таблицу.
Описание программы:
Рис 10.
Пользователю предоставляется возможность ввести начальные параметры. После ввода данных с помощью кнопки вычислить мы получаем решение. Результаты представлены в таблице, а так же ход решения можно пронаблюдать на графике. В пункте меню Справка можно получить информацию о методе и о разработчике программы. Для выхода из программы используется пункт меню Выход.
Рис 11.
Вывод: Представленный модуль удовлетворяет поставленным требованиям. Программа разработана в среде С++Builder 6.0. Код программы находится в приложении 2.
Заключение
Анализируя результаты исследования (сравнения) всех рассмотренных выше методов, можно прийти к выводу о том, что каждый из них имеет свои достоинства и недостатки и более применим для задач одних видов и менее - для других. Однако, пользователь всегда сможет найти подходящий алгоритм для решения своей конкретной проблемы, выбирая как из вышеприведенного множества методов, так и из огромного спектра их модифицированных, усовершенствованных и комбинированных вариантов.
Однако, есть целый класс проблем, где найти оптимум либо крайне сложно, либо вообще невозможно получить точное решение с помощью алгоритмов данных категорий. К таким задачам относится, например, моделирование глобальных социально-экономических процессов.
Мощным инструментом теоретического исследования алгоритмов являются теоремы о сходимости методов. Однако, как правило, формулировки таких теорем абстрактны, при их доказательстве используется аппарат современного функционального анализа. Кроме того, зачастую непросто установить связь полученных математических результатов с практикой вычислений. Дело в том, что условия теорем труднопроверяемы в конкретных задачах, сам факт сходимости мало что дает, а оценки скорости сходимости неточны и неэффективны. При реализации алгоритмов также возникает много дополнительных обстоятельств, строгий учет которых невозможен (ошибки округления, приближенное решение различных вспомогательных задач и т.д.) и которые м?/p>