Автор работы: Пользователь скрыл имя, 12 Декабря 2013 в 17:21, курсовая работа
Метод штрафных функций (внешние штрафы).
Цель:
изучить решение задач оптимизации с помощью метода «штрафных функций»
реализовать этот метод в программе Maple.
«МАТИ» - РОССИЙСКИЙ
ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ
имени К. Э. Циолковского
кафедра:
«Проектирование вычислительных комплексов»
Курсовая работа
по дисциплине: «Методы оптимизации»
тема: «Метод штрафных функций»
Москва 2008 г.
Лабораторная работа №7
Метод условной оптимизации.
Метод штрафных функций (внешние штрафы).
Цель:
1. Постановка задачи
Дана функция и ограничения на неё в виде функции . Требуется отыскать такие значения x, при которых функция принимает минимальное значение, а функция , при этом обращается в 0.
2. Стратегия поиска
Идея метода заключается в сведении задачи на условный минимум к решению последовательности задач поиска безусловного минимума вспомогательной функции:
где - штрафная функция, – параметр штрафа, задаваемый на каждой к итерации. Как правило, для ограничений типа равенств используется квадратичный штраф, а для ограничений типа неравенств – квадрат срезки.
,
где - срезка функции.
Начальная точка поиска задается обычно вне множества допустимых решений X. На каждой k-й итерации ищется точка минимума вспомогательной функции при заданном параметре с помощью одного из методов безусловной оптимизации. Полученная точка используется в качестве начальной для следующей итерации, выполняемой при возрастающем значении параметра штрафа. При неограниченном возрастании последовательность точек стремится к точке условного минимума .
Алгоритм
Шаг 1. Задать начальную точку ; начальное значение параметра штрафа ; число для увеличения параметра штрафа; малое число для остановки алгоритма. Положить .
Шаг 2. Составить вспомогательную функцию:
Шаг 3. Найти точку безусловного минимума функции по x с помощью какого-либо метода (нулевого, первого или второго порядка):
При этом задать все требуемые выбранным методом параметры. В качестве начальной точки взять . Вычислить
Шаг 4. Проверить условие окончания:
а) если , процесс поиска закончить:
, ;
б) положить , , и перейти к шагу 2
4. Моделирование в Maple
Целевая функция, в которой нужно найти локальный минимум, называется . Задаваемая функция ограничений называется . Штрафная функция называется , она вычисляется автоматически. В программе пользовательский интерфейс упрощен путем автоматического ввода функции. Рассмотрим работу данного метода на примере №1
1. Функция:
Штрафная функция:
a |
b |
c |
d | |
1 |
5.5 |
7 |
4.8 |
9.5 |
2 |
1.7 |
0.9 |
7.5 |
3.4 |
3 |
7.7 |
4 |
6.8 |
2.9 |
4 |
3.9 |
9 |
1.3 |
2.6 |
5 |
7.4 |
5.1 |
5.5 |
8.1 |
6 |
7.8 |
1.1 |
5.1 |
3.5 |
7 |
5.4 |
3.7 |
5 |
9.6 |
8 |
8 |
1.3 |
9.4 |
1.8 |
9 |
8.6 |
9.6 |
3 |
2.1 |
10 |
0.1 |
6.9 |
3 |
3.2 |
2. Функция:
Штрафная функция:
a |
b | |
1 |
1.6 |
7 |
2 |
8.3 |
0.9 |
3 |
8.2 |
4 |
4 |
10 |
9 |
5 |
4.6 |
5.1 |
6 |
3.7 |
1.1 |
7 |
7.2 |
3.7 |
8 |
4.3 |
1.3 |
9 |
4.7 |
9.6 |
3. Функция:
Штрафная функция:
a |
b |
с | |
1 |
9.7 |
0.7 |
4.6 |
2 |
8.3 |
4.9 |
7.5 |
3 |
8.2 |
1.3 |
8.6 |
4 |
3.4 |
0.8 |
0.1 |
5 |
4.6 |
9.1 |
2.4 |
6 |
8.6 |
1.3 |
7.2 |
7 |
7.2 |
8 |
0.9 |
8 |
4.3 |
1.1 |
2.1 |
9 |
0.8 |
2.6 |
0.2 |
10 |
8 |
1.6 |
9.1 |
4. Функция:
Штрафная функция:
a |
b | |
1 |
4.9 |
3.4 |
2 |
8.3 |
4.6 |
3 |
8.2 |
1.3 |
4 |
3.4 |
8.2 |
5 |
4.6 |
0.8 |
6 |
8.6 |
1.6 |
7 |
5.1 |
8 |
8 |
8.6 |
4.6 |
9 |
7.2 |
2.6 |
10 |
2.6 |
1.6 |
5. Функция:
Штрафная функция:
a |
b |
с | |
1 |
9.7 |
0.7 |
4.6 |
2 |
8.3 |
4.9 |
7.5 |
3 |
8.2 |
1.3 |
8.6 |
4 |
3.4 |
0.8 |
0.1 |
5 |
4.6 |
9.1 |
2.4 |
6 |
8.6 |
1.3 |
7.2 |
7 |
7.2 |
8 |
0.9 |
8 |
4.3 |
1.1 |
2.1 |
9 |
0.8 |
2.6 |
0.2 |
10 |
8 |
1.6 |
9.1 |