Санкт-Петербургский государственный электротехнический
университет «ЛЭТИ»
Кафедра САПР
Отчет по лабораторной работе № 1
по учебной дисциплине «методы оптимизации»
на тему «Исследование методов одномерного поиска минимума унимодальных функций»
Вариант 1
Выполнили:
Золотарь М.О.
Климов К.С.
Группа: 0306
Факультет: КТИ
Преподаватель:
Марков М.В.
Санкт-Петербург 2012 г.
Оглавление:
Задание…………………………………………………………………………...3
Описание методов оптимизации……………………………………………..3
Блок-схемы методов оптимизации…………………………………………..4
Спецификация программы……………………………………………….......6
Текст программы………………………………………………………….......6
Пример работы программы………………………………………………………………….......8
Результаты тестирования……………………………………………………9
График Функции…………………………………………………………………………10
Выводы…………………………………………………………………………11
Ответы на контрольные вопросы………………………………………………………………………....11
Задание.
Целью работы является изучение методов одномерной минимизации функций одной переменной;
Описание методов оптимизации.
Метод Свенна:
С помощью этого метода получаем начальный интервал локализации минимума.
Начальный этап:
1) задать x0 – произвольная начальная точка.
2) выбрать шаг h равным 0.001 или 0.01*|x0|.
Основной этап:
Шаг 1:
Установить направление убывания целевой функции. Для этого надо взять x2=x1+h. Если f1<f2, то надо поменять направление движения(h=-h и взять x2=x1+h).
Шаг 2:
Вычислять fk в точках xk+1=xk+hk, где hk=2hk-1, k=2,3,…,n-1 до тех пор, пока не придём в точку xn такую что fn>fn-1.
Шаг 3:
Установить начальный интервал локализации минимума a1=xn-2 и b1=xn.
Метод Золотого Сечения 1:
Начальный этап:
1) Выбрать погрешность , начальный интервал [a1, b1].
2) Вычислить стартовые точки по формулам: 1 = b1 – (√5-1)(b1- a1)/2,
1 = a1 + (√5-1)(b1- a1)/2.
3) Принять k = 1.
Основной этап:
Шаг 1:
1)Сократит текущий интервал локализации рассмотрением двух ситуаций:
если f1<f2, то ak+1=ak,
bk+1=k,
k+1=k,
и найти k+1= bk+1 – (√5-1)(bk+1- ak+1)/2,
иначе f1>f2, то ak+1=k,
bk+1=bk,
k+1=k,
и найти k+1= ak+1 + (√5-1)(bk+1- ak+1)/2.
2) Положить k=k+1.
Шаг 2:
Проверить критерий окончания поиска:
если |a-b| < -остановиться, точнее фиксируем аппроксимирующий минимум x*=(a+b)/2.
Блок-схемы методов:
Метод Свенна 1:
Метод Золотого сечения 1:
Спецификация программы:
Каждый метод реализован в виде функции.
Переменные в программе:
a, b – текущий интервал локализации
h – размер шага
x0 – стартовая точка
x1, x2 - точки деления интервала локализации в методе лин. интерполяции и трехточечного поиска
k – счетчик числа итераций.
E-точность
Xm- координаты минимума