 |
|
Метод сканирования.
РАСЧЕТНО-ГРАФИЧЕСКАЯ РАБОТА
по дисциплине «Методы оптимальных решений»
Вариант 7
Выполнила:
студентка группы М-325з
Хасанова Э. И.
Приняла:
Ст. преподаватель
Закурдаева Е.А.
Уфа 2014
| Изм. |
| Лист |
| № докум. |
| Подпись |
| Дата |
| Лист |
| 2202.4.Ф.27.01.000.ПЗ |
| Разраб. |
| Провер. |
| Реценз. |
| Н. Контр. |
| Утверд. |
| Лит. |
| Листов |
1. Написать в среде Matlab функции, реализующие следующие три метода: сканирования, деления пополам, золотого сечения.
2. Выбрать для выполнения работы тестовую функцию, номер которой соответствует последней цифре Вашей зачётной книжки.
f(x) = 
→ min, x 
[0,1, 1].
3. Для выбранной функции и для каждого реализованного метода изучить зависимость скорости работы (числа вычислений функции N) от заданного значения точности ε. Провести сравнение методов. Объяснить полученные результаты.
4. Вычислить аналитическое значение координаты минимума выбранной функции с точностью до 4 значащих цифр.
5. Определить, сколько вычислений функции потребуется каждому методу, для того чтобы разность между численным и аналитическим решениями была меньше ε = 10-4.
6. Метод параллельных касательных.
Метод сканирования.
Условие: f(x) == → min, x [0,1, 1].
Ошибка по х: ε
| Изм. |
| Лист |
| № докум. |
| Подпись |
| Дата |
| Лист |
| 2202.4.Ф.60.01.000.ПЗ |
| Разраб. |
| Провер. |
| Реценз. |
| Н. Контр. |
| Утверд. |
| Лит. |
| Листов |
Разобьем весь интервал на 4подынтервала, координаты х будут []. Найти значение критериев.
F1 (0,325) = 10*0,325*(-1,1)+0,3252/2=-3,522
F2 (0,55) =10*0,55*(-0,59)+0,552/2=-3,093
F3 (0,775) =10*0,775*(-0,25)+0,7752/2=-1,6371
Следовательно, в качестве нового отрезка выбираем отрезок [0,1;0,325], т.к. внутри него находится минимальное значение F1= -3,522
F4(0,2125)= 10*0,2125*(-1,54)+0,21252/2=-3,249
Следовательно, в качестве нового отрезка выбираем отрезок [0,375;1,5], т.к. внутри него находится максимальное значение F4=23,0869
F5(0,9375)=20,079+2*0,8789+3*0,9315=24,6481
Следовательно, в качестве нового отрезка выбираем отрезок [0,6875;1,5], т.к. внутри него находится максимальное значение F5=24,6481
F6(1,0938)=20,079+2*1,1964+3*1,0938 =25,2843
Следовательно, в качестве нового отрезка выбираем отрезок [0,9375;1,5], т.к. внутри него находится максимальное значение F6=25,2843
F7(1,2186)=20,079+2*1,485+3*1,2186 =26,7048
Следовательно, в качестве нового отрезка выбираем отрезок [1,0938;1,5], т.к. внутри него находится максимальное значение F7=26,7048
F8(1,2969)=20,079+2*1,6819+3*1,2969 =27,3335
Следовательно, в качестве нового отрезка выбираем отрезок [1,2186;1,5], т.к. внутри него находится максимальное значение F8=27,3335
F9(1,3593)=20,079+2*1,8477+3*1,3593 =27,8523
Следовательно, в качестве нового отрезка выбираем отрезок [1,2969;1,5], т.к. внутри него находится максимальное значение F9=27,8523
F10(1,3985)=20,079+2*1,9558+3*1,3985=28,1861
Всего десять раз вычислялся критерий оптимальности.
Ответ: F*=28,1861
| Изм. |
| Лист |
| № докум. |
| Подпись |
| Дата |
| Лист |
| 2202.4.Ф.60.01.000.ПЗ |
| Разраб. |
| Провер. |
| Реценз. |
| Н. Контр. |
| Утверд. |
| Лит. |
| Листов |
| Изм. |
| Лист |
| № докум. |
| Подпись |
| Дата |
| Лист |
| 2202.4.Ф.60.01.000.ПЗ |
| Разраб. |
| Провер. |
| Реценз. |
| Н. Контр. |
| Утверд. |
| Лит. |
| Листов |
Условие: f(x) = е3 +2x2 +3х→ max, x [-1, 1,5].
Ошибка по х: ε =0,05.
R(x- ε /2) > (x+ ε /2)
0,25-0,05/2=0,225
0,25+0,05/2=0,275
F1(0,25)=20,079+2*0,0506 +3*0,225=20,85525
F2(0.25)= 20,079+2*0,0756+3*0,275=21.0552
Справа
Следовательно, в качестве нового отрезка выбираем отрезок [0.25;1.5].
0,875-0,05/2=0.85
0,875+0,05/2=0,9
F3(0,85)=20,079+2*0,7225+3*0,85=24,074
F4(0,9)=20,079+2*0,81+3*0,9=24,399
Справа
Следовательно, в качестве нового отрезка выбираем отрезок [0,875;1,5].
1,1875-0,05/2=1,1625
1,1875+005/2=1,2125
F5(1,1625)=20,079+2*1,3514+3*1,1625=26,2693
F6(1,2125)=20,079+2*1,4702+3*1,2125=26,6569
Справа
Следовательно, в качестве нового отрезка выбираем отрезок [1,1875;1,5].
1,3438-0.05/2=1,3188
1,3438+0.05/2=1,3688
F7(1,3188)=20.079+2*1,7392+3*1,3188=27,5138
F8(1,3688)=20.079+2*1,8736+3*1,3688=27,9326
Справа
Следовательно, в качестве нового отрезка выбираем отрезок [1,3438;1,5].
1,4219-0.05/2=1,3969
1,4219+0.05/2=1,4469
F9(1,3969)=20.079+2*1,9513+3*1,3363=28,2323
F10(1,4469)=20.079+2*2,0935+3*1,4469=28,6067
Следовательно, в качестве нового отрезка выбираем отрезок [1,4219;1,5].
1,461-0.05/2=1,436
1,461+0.05/2=1,486
F11(1,436)=20.079+2*2,0621+3*1,436=28,5082
F12(1,486)=20.079+2*2,2082+3*1,486=28,9534
Всего двенадцать раз (6*2=12) вычислялся критерий оптимальности.
Ответ: F*=28,9534
| Изм. |
| Лист |
| № докум. |
| Подпись |
| Дата |
| Лист |
| 2202.4.Ф.60.01.000.ПЗ |
| Разраб. |
| Провер. |
| Реценз. |
| Н. Контр. |
| Утверд. |
| Лит. |
| Листов |
| Изм. |
| Лист |
| № докум. |
| Подпись |
| Дата |
| Лист |
| 2202.4.Ф.60.01.000.ПЗ |
| Разраб. |
| Провер. |
| Реценз. |
| Н. Контр. |
| Утверд. |
| Лит. |
| Листов |
Условие: f(x) = е3 +2x2 +3х→ max, x [-1, 1,5].
Ошибка по х: ε =0,05.
Найдем 2 симметричные точки золотого сечения для отрезка[-1;1.5]
Х1=а+(в-а)*0,618=-1+(1,5-(-1))*0,618=0,545
Х2=в-(в-а)*0,618=1,5-(1,5-(-1))*0,618=-0,045
F1(0,545)= 20,079+2*0,297+3*0,545=22,308
F2(-0,045)=20,079+2*0,002+3*(-0,045)=19,948
Следовательно, в качестве нового отрезка выбираем отрезок [-1;0,545].
X3=-1+(0,545-(-1))*0.618=-0,0452
X4=0,545-(0,545-(-1))*0.618=-0,4098
F3(-0,0452)=20,079+2*0,002+3*(-0,0452)=19,9474
F4(-0,4098)=20,079+2*0,1679+3*(-0,4098) =19,1854
Всего четыре раз (2*2=4) вычислялся критерий оптимальности.
| Изм. |
| Лист |
| № докум. |
| Подпись |
| Дата |
| Лист |
| 2202.4.Ф.60.01.000.ПЗ |
| Разраб. |
| Провер. |
| Реценз. |
| Н. Контр. |
| Утверд. |
| Лит. |
| Листов |
Основным недостатком градиентного метода является необходимость частого вычисления производных от R(x). Этого недостатка лишен метод наискорейшего спуска, который заключается в следующем.
В текущей точке вычисляется grad R(x), и затем в направлении градиента ищется min R(x). Практически это может быть осуществлено любым методом одномерной оптимизации (поиск по одному направлению — направлению градиента), наиболее часто используется сканирование до первого локального минимума по направлению grad R(x).
В результате вдали от оптимума эффективность метода повышается, мы быстрее попадаем в район оптимума, в окрестности которого эффективность метода снижается из-за частой смены направления поиска и приближается к эффективности метода градиента.
Метод, как и все градиентные методы, обладает невысокой эффективностью в овражных функциях. В ряде случаев можно повысить скорость выхода в район оптимума предъявлением невысоких требований к точности поиска min по направлению (задается величиной h — шагом поиска по направлению).
Условием окончания может являться малость модуля градиента R(x) |grad R(x)|< Е. Можно также использовать и малость приращений по переменным в результате шага, но только в том случае, если на данном шаге мы "проскочили" оптимум, иначе может оказаться, что малость шага обусловлена не близостью к оптимуму, а малостью коэффициента пропорциональности шага h.
В ряде случаев используют уменьшение шага поиска оптимума по направлению после каждой смены направления. Это позволяет с большей точностью каждый раз находить оптимум, но резко снижает эффективность поиска в овражных функциях. Метод используется для локализации "дна оврага" в специальных овражных методах. Условием окончания поиска в этом случае является достижение заданной малой величины шага.