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

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

 

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

 

Логин:

Пароль:

 

Запомнить

 

 

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

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

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

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


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


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

Информация:

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

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


2
Министерство образования и науки Республики Казахстан
Карагандинский Государственный Технический Университет
Кафедра
Пояснительная записка
к курсовой работе по дисциплине: «Теория принятия решений»
Тема: Сравнительный анализ методов оптимизации
Выполнила
Студентка группы ______
______________________
Руководитель
______________________
Караганда-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)
где > 0 - малое число. При этом отношение длин нового и исходного отрезков
близко к 1/2, этим и объясняется название метода.
Отметим, что для любых точек x1 и х2 величина > 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. Число из (2.11) выбирают на интервале (0;2) с учетом следующих соображений:
а) чем меньше , тем больше относительное уменьшение длины отрезка на каждой итерации, т.е. при уменьшении достигается более высокая скорость сходимости метода дихотомии;
б) при чрезмерно малом сравнение значений f (x) в точках x1 и х2 , отличающихся на величину , становится затруднительным. Поэтому выбор должен быть согласован с точностью определения f (x) и с количеством верных десятичных знаков при задании аргумента х.
В таблице 1 приведено решение задания по варианту.
Таблица 1 - Метод дихотомии
№ шага
x1
x2
F(x1)
F(x2)
а
b
1
3.29
3.31
--3.3662671
-3.3081836
2.7
3.9
0.6
2
2.995
3.0015
-3.9477432
-3.9985552
2.7
3.301
0.3
3
3.1425
3.1525
-5.7966545
-5.7920936
2.995
3.301
0.15075
4
2.9995
3.15125
-5.3956845
-5.4206115
3.06875
3.1625
0.04687
5
3.1118125
3.1138125
-5.7344664
-5.7448499
3.074375
3.15125
0.03844
6
3.1305312
3.1325312
-5.8005444
-5.8034734
3.1118125
3.15125
0.01972
7
3.1398906
3.1418906
-5.8073633
-5.8065477
3.1305312
3.15125
0.01036
8
3.1352109
3.1372109
-5.8061441
-5.8072013
3.1305312
3.1418906
5.67969E-3
9
3.1309766
3.1509766
-5.8073015
-5.8074223
3.1352109
3.1418906
3.33984E-3
10
3.1387207
3.1407207
-5.8074693
-5.807122
3.1375508
3.1465703
2.16992E-3
11
3.1381357
3.1401357
-5.8074196
-5.8073064
3.1375508
3.1407207
1.585E-3
12
3.1384282
3.1404282
-5.807453
-5.8072227
3.1381357
3.1407207
1.292E-3
|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 = , тогда симметрично расположенная точка х1 = 1- (рис. 2.7).
Рис. 2.7. Определение пробных точек в методе золотого сечения
Пробная точка х1 отрезка [0; 1] перейдет в пробную точку х2 = 1- нового отрезка [0; т]. Чтобы точки х2 = , и х2 = 1- делили отрезки [0; 1] и [0; ] в одном и том же отношении, должно выполняться равенство
или
,
откуда находим положительное значение

Таким образом,
х1 = 1- = , .
Для произвольного отрезка [а; b] выражения для пробных точек примут вид
;
В таблице 2 приведено решение задания по варианту.
Опишем алгоритм метода золотого сечения.
Шаг 1. Найти х1 и х2 по формулам (2.15). Вычислить f (x1) и f (x2). Положить ,
.
Шаг 2. Проверка на окончание поиска: если n > , то перейти к шагу 3, иначе - к шагу 4.
Шаг 3. Переход к новому отрезку и новым пробным точкам. Если f (x1) f (x2) то положить b=x2 , x2=x1 , f (x2) f (x1), x1=b-(b-a) и вычислить f (x1), иначе - положить a=x1, x1= x2 , f (x1) = f (x2), x2=b+(b-a) и вычислить f (x2). Положить n = n и перейти к шагу 2.
Шаг 4. Окончание поиска: положить
, .
Результаты вычислений на остальных итерациях представлены в таблице 2 .
Таблица 2 - Метод золотого сечения
№ шага
a
b
x1
x2
F(x1)
F(x2)
1
2.7
3.9
3.1584
3.4416
-5.7694
1.79829
0.370820393
2
2.7
3.4416
2.98329
3.1583
-3.1542
-5.7698
0.229179607
3
2.9833
3.4416
3.158365
3.26652
-5.76957
-4.22659
4
2.98329
3.266546
3.09148
3.15833
-5.58444
-5.769704
5
3.09148
3.26652
3.15835
3.199661
-5.76962
-5.43999
6
3.09148
3.19966
3.13281
3.15834
-5.8039
-5.76967
7
3.09148
3.15834
3.11702
3.132801
-5.7600
-580399
8
3.11702
3.15834
3.13281
3.14256
-5.8039
-5.80627
9
3.13281
3.15834
3.14256
3.14859
-5.8063
-5.7982
10
3.13281
3.14859
3.1388
3.14856
-5.08076
-5.8063
11
3.13281
3.14256
3.13653
3.13883
-5.8071
-5.8076
12
3.13653
3.142557
3.13883
3.140255
-5.80764
-5.80745
13
|a-b|=7.893370498E-3< ?, x*=(a+b)/2=3.1407091
f(x*)=-5.807126299
Сравнив два метода, мы видим, что для данной функции лучше подходит метод дихотомии, т.к. он быстрее приводит к оптимальному решению.
2 Прямые методы безусловной оптимизации многомерной функции
Задача безусловной оптимизации состоит в нахождении минимума или максимума функции в отсутствие каких-либо ограничений. Несмотря на то что большинство практических задач оптимизации содержит ограничения, изучение методов безусловной оптимизации важно с нескольких точек зрения. Многие алгоритмы решения задачи с ограничениями предполагают сведение ее к последовательности задач безусловной оптимизации.
Рассмотрим методы решения минимизации функции нескольких переменных f, которые опираются только на вычисление значений функции f(x), не используют вычисление производных, т.е. прямые методы минимизации. В основном все методы заключаются в следующем. При заданном векторе х определяется допустимое направление d. Затем, отправляясь из точки х, функция f минимизируется вдоль направления d одним из методов одномерной минимизации. Будем предполагать, что точка минимума существует. Однако в реальных задачах это предположение может не выполняться.
Для изучения прямых методов безусловной оптимизации многомерной функции была дана функция:
F(x1,x2)=a*x*y+(b*y+c*x)/x*y > min
a=5 b=3.5 c=2.5
x1=
x2=
2.1 Метод покоординатного циклического спуска
Суть метода заключается в том, что в начальном базисе закрепляется значение одной координаты, а переменными считаются остальные, и по этой координате производится одномерная оптимизация
базисная точка переносится в
,
базисная точка переносится в
Циклы повторяются до тех пор, пока в ? окрестности найденной базисной точки будет улучшение функции. Решением поставленной задачи является точка в ? окрестности которой функция не принимает значение, лучшие, чем в этой точке.
Для решения поставленной задачи выбрано приближение ?=0,01 ?=0,15
Таблица 3 - Метод покоординатного циклического спуска
№ шага
x1
x2
Z(x1,x2)
?
0
2.1932884
1.6094917
20.7994602
0.5
1
1.6932884
1.6094917
17.2469375
0,5
2
1.1932884
1.6094917
14.0892956
0,5
3
0.6932884
1.6094917
12.1808992
0,5
4
0.6832884
1.6094917
12.1743085
0.01
5
0.6732884
1.6094917
12.1699126
0.01
6
0.6632884
1.6094917
12.1678107
0.01
7
0.6632884
1.1094917
11.2095884
0.5
8
0.6632884
1.0094917
11.1011539
0.1
9
0.6632884
0.9094917
11.041804
0,1
10
0.6632884
0.8094917
11.0497295
0,1
11
-0,183
0,827
-0,2137796
0,15
13
-0,183
0,677
-0,4082396
0,15
14
-0,183
0,527
-0,4631996
0,15
15
-0,108
0,527
-0,5887121
0,075
16
-0,033
0,527
-0,6860996
0,075
17
0,042
0,527
-0,7553621
0,075
18
0,117
0,527
-0,7964996
0,075
19
0,192
0,527
-0,8095121
0,075
20
0,192
0,452
-0,8409296
0,075
21
0,2295
0,452
-0,842513975
0,0375
22
0,2295
0,4145
-0,8479571
0,0375
?/2< ?, x1=0,2295 x2=0,4145 Z(x1,x2)= -0,8479571
2.2 Метод Хука - Дживса
Метод Хука и Дживса осуществляет два типа поиска - исследующий поиск и поиск по образцу. Первые две итерации процедуры показаны на рисунке 4.
Рисунок 4 - 1-поиск по образцу; 2- исследующий поиск вдоль координатных осей.
При заданном начальном векторе x1 исследующий поиск по координатным направлениям приводит в точку x2 . Последующий поиск по образцу в направлении x1- x2 приводит в точку y. Затем исследующий поиск, начинающийся из точки y, дает точку x3. Следующий этап поиска по образцу вдоль направления x3- x2 дает y*. Затем процесс повторяется.
Рассмотрим вариант метода, использующий одномерную минимизацию вдоль координатных направлений d1,..., dn и направлений поиска по образцу.
Начальный этап. Выбрать число eps > 0 для остановки алгоритма. Выбрать начальную точку x1, положить y1= x1, k=j=1 и перейти к основному этапу.
Основной этап.
Шаг 1. Вычилить lymj - оптимальное решение задачи минимизации f(yj+lym * dj) при условии lym принадлежит E1. Положить y[j+1]= yj+lymj*dj. Если j < n, то заменить j на j+1 и вернуться к шагу 1. Если j=n, то положить x[k+1] = y[n+1]. Если ||x[k+1] - xk|| < eps , то остановиться; в противном случае перейти к шагу 2.
Шаг 2. Положить d = x[k+1] - xk и найти lym - оптимальное решение задачи минимизации f(x[k+1]+lym*d) при условии lym принадлежит E1. Положить y1= x[k+1]+lym*d, j=1, заменить k на k+1 и перейти к шагу 1. Для решения поставленной задачи выбрано приближение ?=0,02, ?=0,15
Таблица 4 - Метод Хука-Дживса
№ шага
x1
x2
Z(x1,x2)
1
1,147
1,257
5,0057324
2
1,127
1,237
4,7420444
3
1,107
1,217
4,4844364
4
1,087
1,197
4,2329084
5
1,067
1,177
3,9874604
6
1,047
1,157
3,7480924
7
1,027
1,137
3,5148044
8
1,007
1,117
3,2875964
9
0,987
1,097
3,0664684
10
0,967
1,077
2,8514204
11
0,947
1,057
2,6424524
12
0,927
1,037
2,4395644
13
0,907
1,017
2,2427564
14
0,887
0,997
2,0520284
15
0,867
0,977
1,8673804
16
0,847
0,957
1,6888124
17
0,827
0,937
1,5163244
18
0,807
0,917
1,3499164
19
0,787
0,897
1,1895884
20
0,767
0,877
1,0353404
21
0,747
0,857
0,887172399999997
22
0,727
0,837
0,745084399999997
23
0,707
0,817
0,609076399999996
24
0,687
0,796999999999999
0,479148399999997
25
0,667
0,776999999999999
0,355300399999997
26
0,647
0,756999999999999
0,237532399999997
27
0,627
0,736999999999999
0,125844399999997
28
0,607
0,716999999999999
0,0202363999999973
29
0,587
0,696999999999999
-0,0792916000000026
30
0,567
0,676999999999999
-0,172739600000002
31
0,546999999999999
0,656999999999999
-0,260107600000002
32
0,526999999999999
0,636999999999999
-0,341395600000002
33
0,506999999999999
0,616999999999999
-0,416603600000002
34
0,486999999999999
0,596999999999999
-0,485731600000002
35
0,466999999999999
0,576999999999999
-0,548779600000002
36
0,446999999999999
0,556999999999999
-0,605747600000002
37
0,426999999999999
0,536999999999999
-0,656635600000002
38
0,406999999999999
0,516999999999999
-0,701443600000001
38
0,426999999999999
0,496999999999999
-0,699011600000001
Т.к в ? окрестности полученной на 38 шаге точке мы не получаем улучшения (уменьшения значения) функции, то примем x1=0,426999999999999 x2=0,496999999999999,
Z(x1,x2)= -0,699011600000001.
2.3 Метод правильного симплекса
Правильный симплекс в пространстве En называется множество из n+1 равноудаленных друг от друга точек (вершин симплекса). В пространстве Е2 правильным симплексом является совокупность вершин равностороннего треугольника, Е3 - правильного тетраэдра.
Поиск точки минимума функции f(x) с помощью правильных симплексов производят следующим образом. На каждой итерации сравниваются значения f(x) в вершинах симплекса. Затем проводят описанную выше процедуру отражения для этой вершины, в которой f(x) принимает наибольшее значение. Если в отраженной вершине получается меньшее значение функции, то переходят к новому симплексу. В противном случае выполняют еще одну попытку отражения для вершины со следующим по величине значением f(x). Если и она не приводит к уменьшению функции, то сокращают длину ребра симплекса и строят новый симплекс с новым ребром. В качестве базовой выбирают ту вершину х0 старого симплекса, которой функция принимает наименьшее значение. Поиск минимума f(x) заканчивают, когда либо ребро симплекса, либо разность между значениями функции в вершинах симплекса становятся достаточно малыми.
Начальный этап. Выбрать параметр точности eps, базовую точку x0, ребро a и построить начальный симплекс. Вычислить f(x0).
Основной этап.
Шаг 1. Вычислить значения f(x) в вершинах симплекса x1,..., xn.
Шаг 2. Упорядочить вершины симплекса x0,..., xn так, чтобы f(x0)<=f(x1)<=...<=f(x[n-1])<=f(xn).
Шаг 3. Проверим на окончание поиска
,
где
Это одно из возможных условий останова. Его выполнении соответствует либо малому ребру a симплекса, либо попаданию точки минимума x* внутрь симплекса, либо тому и другому одновременно.
Если это условие выполнено, то вычисления прекратить, полагая x*= x0. В противном случае перейти к шагу 4.
Шаг 4. Найти xс и выполнить отражение вершины xn : y=2*xс- xn. Если f(y)<f(xn), то положить xn=y и перейти к шагу 2. Иначе - перейти к шагу 5.
Шаг 5. Перейти к новому правильному симплексу с вдвое меньшим ребром, считая базовой вершиной x0. Остальные n вершин симплекса найти по формуле xi=( xi+ x0)/2, i=1,...,n. Перейти к шагу 1.
Для решения поставленной задачи выбрано приближение ?=0,01, ?=0,3
Таблица 5 - Метод симплекса
№ шага
Z(x0,y0)
Z(x1,y1)
Z(x2,y2)
?
1
5,2755004
7,4172004
5,62549807735416
0,3
2
5,2755004
5,62549807735416
3,76366398915256
0,3
3
3,76366398915256
5,2755004
3,5838004
0,3
4
3,5838004
3,76366398915256
2,35182990095096
0,3
5
2,35182990095096
3,5838004
2,3421004
0,3
6
2,3421004
2,35182990095096
1,38999581274936
0,3
7
1,38999581274936
2,3421004
1,5504004
0,3
8
1,38999581274936
1,5504004
0,878161724547756
0,3
9
0,878161724547756
1,38999581274936
0,657100646520204
0,3
10
0,657100646520204
0,878161724547756
0,425132470117002
0,3
11
0,425132470117002
0,657100646520204
0,143414901312537
0,3
12
0,143414901312537
0,425132470117002
0,191312636707734
0,3
13
0,143414901312537
0,191312636707734
-0,15106142287364
0,3
14
-0,15106142287364
0,143414901312537
-0,0288250700672363
0,3
15
-0,15106142287364
-0,0288250700672363
-0,383957885030324
0,3
16
-0,383957885030324
-0,15106142287364
-0,226328326038328
0,3
17
-0,383957885030324
-0,226328326038328
-0,519881278971922
0,3
18
-0,519881278971922
-0,383957885030324
-0,507376749762318
0,3
19
-0,519881278971922
-0,507376749762318
-0,703956634480828
0,3
20
-0,703956634480828
-0,521318017069623
-0,507376749762318
0,3
21
-0,703956634480828
-0,521318017069623
-0,778554392565042
0,3
22
-0,778554392565042
-0,703956634480828
-0,681327098177849
0,3
23
-0,778554392565042
-0,816581347038974
-0,681327098177849
0,3
24
-0,816581347038974
-0,778554392565042
-0,743674553224567
0,3
25
-0,816581347038974
-0,842357998475409
-0,743674553224567
0,3
26
-0,845848412956476
-0,846177360374865
-0,838238020383463
0,075
27
-0,846177360374865
-0,845848412956476
-0,843154372435278
0,075
28
и т.д.................


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



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


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