Сравнительный анализ методов оптимизации

Сравнительный анализ методов оптимизации

Министерство образования и науки Республики Казахстан

Карагандинский Государственный Технический Университет

Кафедра

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

к курсовой работе по дисциплине: «Теория принятия решений»

Тема: Сравнительный анализ методов оптимизации

Выполнила

Студентка группы ______

______________________

Руководитель

______________________

Караганда-2009

Содержание

Введение

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

1 Прямые методы одномерной оптимизации

1.1 Метод дихотомии

1.2 Метод золотого сечения

2 Прямые методы безусловной оптимизации многомерной функции

2.1 Метод покоординатного циклического спуска

2.2 Метод Хука - Дживса

2.3 Метод правильного симплекса

2.4 Метод деформированного симплекса

3. Условная оптимизация

3.1 Метод преобразования целевой функции

3.2 Метод штрафных функций

4. Симплекс таблицы

Заключение

Список используемой литературы

Приложение А Листинг программ: Метод дихотомии, Метод золотого сечения, Метод покоординатного циклического спуска, Метод Хука – Дживса, Метод правильного симплекса

Приложение Б Листинг программы: Метод деформированного симплекса

Приложение В Листинг программы: Метод правильного трехмерного симплекса (максимизация объема фигуры)

Введение

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

Формулировка математической задачи оптимизации.

В достаточно общем виде математическую задачу оптимизации можно сформулировать следующим образом:

Минимизировать (максимизировать) целевую функцию с учетом ограничений на управляемые переменные.

Под минимизацией (максимизацией) функции n переменных f(x)=f(x1, ... ,xn) на заданном множестве U n-мерного векторного пространства En понимается определение хотя бы одной из точек минимума (максимума) этой функции на множестве U, а также, если это необходимо, и минимального (максимального) на U значения f(x).

При записи математических задач оптимизации в общем виде обычно используется следующая символика:

f(x) -> min (max),

x принадлежит U,

где f(x) - целевая функция, а U - допустимое множество, заданное ограничениями на управляемые переменные.

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

Целью данного курсового проекта является изучение методов оптимизации функции. Методов одномерной оптимизации: метод дихотомии, золотого сечения; многомерной безусловной оптимизации: покоординатный циклический спуск, метод Хука – Дживса, правильный симплекс, деформированный симплекс, а также методов условной оптимизации Метод преобразования целевой функции, метод штрафных функций, табличный симплекс – метод.

1. Прямые методы одномерной оптимизации

Задачи одномерной минимизации представляют собой простейшую математическую модель оптимизации, в которой целевая функция зависит от одной переменной, а допустимым множеством является отрезок вещественной оси:

f(x) -> min ,

x принадлежит [a, b].

Максимизация целевой функции эквивалента минимизации ( f(x) -> max ) эквивалентна минимизации противоположной величины ( -f(x) -> min ), поэтому, не умаляя общности можно рассматривать только задачи минимизации.

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

Для решения задачи минимизации функции f(x) на отрезке [a, b] на практике, как правило, применяют приближенные методы. Они позволяют найти решения этой задачи с необходимой точностью в результате определения конечного числа значений функции f(x) и ее производных в некоторых точках отрезка [a, b]. Методы, использующие только значения функции и не требующие вычисления ее производных, называются прямыми методами минимизации.

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

Рассмотрим наиболее распространенные на практике прямые методы поиска точки минимума. Самым слабым требованием на функцию f(x), позволяющим использовать эти методы, является ее унимодальность. Поэтому далее будем считать функцию f(x) унимодальной на отрезке [a, b].

Функция f(x) называется унимодальной на отрезке [a,b], если она непрерывна на [a,b] и существуют числа , , такие, что:

если , то на отрезке [a; ] функция f(x) монотонно убывает;

если , то на отрезке [; b] функция f(x) монотонно возрастает;

при

Для изучения прямых методов одномерной оптимизации была дана функция:

F(x)=8*cos(5*x)+ → min

a=2.7 b=3.9

И выбрано приближение ε=0,01, =0,02

1.1 Метод дихотомии

В этом методе точки x1 и х2 располагаются близко к середине очередного отрезка [а; b], т.е:

 , (2.11)

где d > 0 – малое число. При этом отношение длин нового и исходного отрезков

близко к 1/2, этим и объясняется название метода.

Отметим, что для любых точек x1 и х2 величина t > 1/2, поэтому указанный выбор пробных точек объясняется стремлением обеспечить максимально возможное относительное уменьшение отрезка на каждой итерации поиска х*.

В конце вычислений по методу дихотомии в качестве приближенного значения х* берут середину последнего из найденных отрезков [а; b], убедившись предварительно, что достигнуто неравенство

.

Опишем алгоритм метода деления отрезка пополам.

Шаг 1. Определить x1 и х2 по формулам (2.11). Вычислить f (x1) и f (x2).

Шаг 2. Сравнить f (x1) и f (x2). Если , то перейти к отрезку [а; x2], положив b = x2 , иначе – к отрезку [x1; b], положив а = x1 .

Шаг 3. Найти достигнутую точность

Если , то перейти к следующей итерации, вернувшись к шагу 1. Если , то завершить поиск х*, перейдя к шагу 4.

Шаг 4. Положить

.

Замечания:

1. Число d из (2.11) выбирают на интервале (0;2e) с учетом следующих соображений:

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

б) при чрезмерно малом d сравнение значений f (x) в точках x1 и х2 , отличающихся на величину d, становится затруднительным. Поэтому выбор d должен быть согласован с точностью определения f (x) и с количеством верных десятичных знаков при задании аргумента х.

В таблице 1 приведено решение задания по варианту.

Таблица 1 - Метод дихотомии

|a-b|=0.001<= ε, x*=(a+b)/2=3.139282, f(x*)=-5.8074527

Рисунок 1 – Результат выполнения программы (Метод дихотомии).

1.2 Метод золотого сечения

Метод золотого сечения. Рассмотрим такое симметричное расположение точек x1 и х2 на отрезке [а; b], при котором одна из них становится пробной точкой и на новом отрезке, полученном после исключения части исходного отрезка. Использование таких точек позволяет на каждой итерации метода исключения отрезков, кроме первой, ограничиться определением только одного значения f (x), так как другое значение уже найдено на одной из предыдущих итераций.

Найдем точки x1 и х2 , обладающие указанным свойством.

Рассмотрим сначала отрезок [0; 1] и для определенности предположим, что при его уменьшении исключается правая часть этого отрезка. Пусть х2 = t, тогда симметрично расположенная точка х1 = 1–t (рис. 2.7).

Рис. 2.7. Определение пробных точек в методе золотого сечения

Пробная точка х1 отрезка [0; 1] перейдет в пробную точку х2¢ = 1–t нового отрезка [0; т]. Чтобы точки х2 = t, и х2¢ = 1–t делили отрезки [0; 1] и [0; t] в одном и том же отношении, должно выполняться равенство

или

,

откуда находим положительное значение

…

Таким образом,

х1 = 1–t = , .

Для произвольного отрезка [а; b] выражения для пробных точек примут вид

;

В таблице 2 приведено решение задания по варианту.

Опишем алгоритм метода золотого сечения.

Шаг 1. Найти х1 и х2 по формулам (2.15). Вычислить f (x1) и f (x2). Положить  ,

.

Шаг 2. Проверка на окончание поиска: если en > e, то перейти к шагу 3, иначе – к шагу 4.

Шаг 3. Переход к новому отрезку и новым пробным точкам. Если f (x1) £ f (x2) то положить b=x2 , x2=x1 , f (x2) £ f (x1), x1=b–t(b–a) и вычислить f (x1), иначе – положить a=x1, x1= x2 , f (x1) = f (x2), x2=b+t(b–a) и вычислить f (x2). Положить en = ten и перейти к шагу 2.

Шаг 4. Окончание поиска: положить

, .

Результаты вычислений на остальных итерациях представлены в таблице 2 .

Таблица 2 - Метод золотого сечения

|a-b|=7.893370498E-3< ε, x*=(a+b)/2=3.1407091

Страницы: 1, 2, 3, 4