Будь умным!

У вас вопросы?
У нас ответы:) SamZan.net

тематического пакета и табличного процессора.

Работа добавлена на сайт samzan.net:


ПРАКТИЧЕСКАЯ работа №6

Методы оптимизации

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

Теоретические сведения

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

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

Заметим, что поиск максимума функции  эквивалентен поиску минимума функции . Поэтому далее сконцентрируем внимание именно на задаче минимизации.

Опишем два основных алгоритма одномерной оптимизации. Метод золотого сечения использует для своей работы только значения функции, сходится всегда, но обеспечивает лишь линейную скорость сходимости. Метод Ньютона использует значения первой и второй производных функции F(x), имеет квадратичную скорость сходимости, но может расходиться при плохом выборе начального приближения. Обычно в реальных задачах комбинируют оба метода, применяя для локализации корней метод золотого сечения, а затем на заключительном этапе – метод Ньютона.

Метод Ньютона. В основе метода Ньютона лежит приближение F(x) квадратичной функцией, экстремум которой находится явно и используется в качестве следующего начального приближения. Зададимся некоторым начальным приближением  и выпишем первые три члена ряда Тейлора функции F(x) в окрестности этой точки:

 (6.1)

Экстремум квадратичной функции в правой части (6.1) достигается при  Поэтому в качестве следующего приближения можно выбрать точку  Получаем итерационный процесс дающий алгоритм метода Ньютона

  (6.2)

Отметим, что при выборе начального приближения достаточно близко к точке экстремума метод Ньютона гарантированно сходится. Отметим также, что метод Ньютона может сходиться как к локальному минимуму, так и к локальному максимуму, поэтому в полученной точке экстремума x* требуется дополнительно вычислить . Если , то мы имеет дело с локальным минимумом, если же  – с локальным максимумом. Наконец, заметим, что если для некоторого окажется , то метод Ньютона завершится делением на 0.

Метод золотого сечения. Пусть функция F(x) определена на отрезке [a,b], строго убывает при  и строго возрастает при . Такая функция называется унимодальной на отрезке [a,b] и имеет на [a,b] единственный минимум. Заметим, что унимодальная функция не обязана быть непрерывной. Назовем интервал, на котором функция заведомо имеет минимум, интервалом неопределенности (ИН). Вначале ИН совпадает с отрезком [a,b]. Наша цель – уменьшить длину ИН до достижения заданной точности. Для этого вычислим функцию F(x) в точках .

Рис. 6.1    Рис. 6.2

Если  (рис. 3.1), то отрезок  заведомо содержит минимум, поэтому его можно выбрать в качестве нового ИН. В противном случае (рис. 6.2) – в качестве нового ИН выбирается отрезок . Для каждого последующего ИН функцию достаточно вычислять в одной точке, поскольку ее значение в другой точке внутри интервала известно с предыдущего шага. Например, в случае, изображенном на рис. 6.1, следует выбрать точку и сравнить  и . Этот процесс следует продолжать, пока длина интервала не окажется меньше наперед заданной точности .

Как выбирать точки так, чтобы за минимальное количество итераций максимально уменьшить ИН? Метод золотого сечения предлагает следующее решение этого вопроса.

Рис. 6.3

Пусть у нас имеется отрезок длины l (рис. 6.3). Разобьем его на части длины m и l–m (m > l–m) таким образом, что отношение длины большей части к длине всего отрезка равно отношению длины меньшей части к длине большей, т.е. выполняется пропорция золотого сечения:

     (6.3)

Учитывая, что и 0>m0>l, из (3.3) нетрудно получить:

Число  называется золотым сечением и является фундаментальным числом, возникающим во многих областях науки и техники.

Порядок выполнения работы

1. Используя табличный процессор и математический пакет выполнить оптимизацию нелинейной функции методом равномерного перебора

2. Создать программу в MathCAD для определения оптимального значения функции методом Ньютона и выполнить оптимизацию нелинейной функции этим методом

3. Создать программу в MathCAD для определения оптимального значения функции методом золотого сечения и выполнить оптимизацию нелинейной функции этим методом. Определите зависимость количества итераций от точности вычислений.

4. Сделать выводы

Варианты заданий

Вариант

Функция

Диапазон

шаг
  1.  

0…3

h=0,2
  1.  

4…4,5

h=0,05
  1.  

0…1

h=0,1
  1.  

5.1…5,9

h=0,05
  1.  

0…1

h=0,1
  1.  

0…10

h=0,5
  1.  

0…1

h=0,05
  1.  

0,5…1,5

h=0,1
  1.  

-1…0

h=0,1
  1.  

-1…0

h=0,1
  1.  

0…3

h=0,2

Пример выполнения работы

Дана функция , найти максимум функции. Диапазон поиска [0,2;3,2], шаг 0.3

1. Метод равномерного перебора

Используя Мастер функций MS Excel запишем функцию  в табличном процессоре (Ячейка А2) (рис. 6.4):

Рис. 6.4

Вычислим шаг, разбив диапазон 0,2…3,2 на 10. (Ячейка C2). Используя относительные и абсолютные ссылки на ячейки построим столбец для вычисления шага (Столбец В).

Используя функцию МАКС (поиск максимального значения в столбце) найдем максимальное значение функции. При помощи функции ВПР найдем значение Х, соответствующее максимальному значению функции (рис. 6.5).

Рис. 6.5

Используя математический пакет, построим график зависимости

 

Рис. 6.6

Сделаем выводы, о том, что оптимальное значение при заданных условиях равно 0.995 и достигается оно в точке х=2.3

2. Метод Ньютона

Установка точности вычислений

Функция newton возвращает значение аргумента, при котором функция f(x) имеет минимум или максимум. Кроме этого выводится количество итераций и значение функции f(x) при найденном х*. Аргументы функции newton:

· начальное приближение хо;

· имя функции, у которой ищется минимум (f);

· правое значение интервала неопределенности (b).

Задание функции

Задание начального приближения

Поиск максимума и вывод числа итераций и значение функции в точке максимума

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

Задание вспомогательной функции с именем ZOL_SECH, позволяющей поделить отрезок a-b (отрезок неопределенности) в золотом соотношении

Установка точности вычислений

Функция MIN_Z_S возвращает значение аргумента, при котором функция y имеет минимум, а также количество итераций. Минимум ищется циклически. Условие завершения цикла – сужение интервала неопределенности до величины, меньшей или равной значению TOL. В цикле интервал неопределенности делится в золотом соотношении, что позволяет при новом приближении к максимуму использовать данные предыдущего приближения.

Аргументы функции MIN_Z_S:

· имя функции, у которой ищется минимум (y);

· левое значение интервала неопределенности (a);

· правое значение интервала неопределенности (b).

Определение интервала

Задание функции

Поиск максимума и вывод числа итераций

Значение функции в точке максимума

Контрольные вопросы

1. Какие методы одномерной оптимизации Вам известны

2. Как найти оптимальное значение функции, если оно стремится к максимуму, а не к минимуму

3. Какие существуют ограничения у метода золотого сечения

4. Какие недостатки присущи методу последовательного перебора

5. Что влияет на сходимость метода Ньютона?




1. Основы трудового права 1.
2. Философия науки
3. темам автоматики в настоящей работе отнесены устройства АПВ АВР АЧР АРТ
4. УстьКулом С
5. Автоматизированные системы ведения истории болезни
6. Методические рекомендации по написанию оформлению и защите курсовых работ по психологии Направлени
7. 2 Состав структура и оценка фондов В соответствии с назначением в производственном процессе и правилами уч
8. Столыпинские реформы
9. Понятие национальной безопасности Конспект лекций
10. 01 район строительства г
11. а Хлеб крупы Хлеб ржаной 233 Хлеб пшеничный 255 Сухари сливочные 387 Булки городские 283
12. Начиная примерно со второй половины XX века т
13. миома матки является наиболее принятым потому что даёт представление о развитии опухоли из миометрия
14. Особенности нефтегазообразования в бассейнах восточного паратетиса
15. Классификация строительных процессов
16. 1 Кредитні операції Активні операції Пасивні операції
17. тема и источники жилищного права1
18. Русские православные монастыри и их роль в развитии национальной культуры
19. Реферат- Чип-карты
20. вариант 1.г. реализм 2

Материалы собраны группой SamZan и находятся в свободном доступе