Информатика и компьютеры

Численное решение задач оптимизации

Актуализация опорных знаний.

Численные методы одномерной оптимизации.

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

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

Метод Фибоначчи.

Встроенные функции MathCAD для поиска локального минимума/максимума.

Пример использования.

Условный экстремум.

Экстремум функции многих переменных.

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

Литература

Царегородцева, В. В. Вычислительная математика: лабораторный практикум по курсам «Численные методы» и «Вычислительная математика» для студентов всех специальностей и направлений подготовки / В. В. Царегородцева, Г. И. Севодина; Алт. гос. техн. ун-т, БТИ. – Бийск: Изд-во Алт. гос. техн. ун-та, 2014. – 78 с.

Актуализация опорных знаний

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

Оптимизируемую функцию f(x) называют целевой функцией, или критерием оптимальности.

Рассмотрим задачу поиска минимального значения функции f(x) одной переменной и запишем эту задачу следующим образом:

Значение х*, определяющее минимум целевой функции, называется оптимальным.

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

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

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

Рисунок 1 – Экстремумы функции

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

На данном занятии рассматриваются только некоторые безградиентные методы одномерного поиска экстремума.

Численные методы одномерной оптимизации

К численным методам одномерной оптимизации относятся методы:

- дихотомического деления,

- золотого сечения,

- чисел Фибоначчи,

- полиномиальной аппроксимации

и ряд их модификаций.

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

т. е. длина нового, суженного интервала поиска экстремума по модулю на i-й итерации меньше или равна заданной степени точности решения задачи.

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

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

Рисунок 2 – Одномерная минимизация:
а – дихотомическое деление; б – золотое сечение

Если окажется, что , то минимум находится на отрезке , если , то минимум – на , если ) – на . Таким образом, на следующем шаге вместо отрезка нужно исследовать суженный отрезок , или . Шаги повторяются, пока длина отрезка не уменьшится до величины погрешности . Таким образом, требуется не более n шагов, где n – ближайшее к целое значение, но на каждом шаге целевую функцию следует вычислять дважды.

Пример 1. Пусть задана функция одной переменной вида

Найти её минимальное значение на интервале [2, 5 ] с заданной точностью методом дихотомического деления.

Программа, реализованная в системе MathCAD, приведена на рисунке 3. Для получения результата с заданной степенью точности потребовалось выполнить 19 итераций.

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

В соответствии с методом золотого сечения (рис. 2, б) внутри отрезка выделяют две промежуточные точки и на расстоянии от его конечных точек, где – длина отрезка. Затем вычисляют значения целевой функции в точках и . Если , то то минимум находится на отрезке , если , то на отрезке , если , то на отрезке .

Рис. 3. Программа поиска минимума методом дихотомического деления

Следовательно, вместо отрезка теперь можно рассматривать отрезок , или , т. е. длина отрезка уменьшилась не менее чем в

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

Условие получения такого значения формулируется следующим образом:

откуда с учетом (*) имеем = 0,382. Это значение и называют золотым сечением.

Алгоритм поиска экстремума складывается из следующих этапов:

1) вычисляются значения функции на концах исходного интервала ;

2) вычисляются промежуточные точки интервала по формулам:

а также значения функции в этих точках;

3) по найденным значениям функции определяется её минимальное значение на интервале;

4) в зависимости от того в какой точке расположен минимум ( или ) определяется подынтервал, в котором локализован минимум – или ;

5) в новом интервале определяется точка по одной из формул п. 2 и итерационный процесс поиска продолжается с п. 3 до тех пор пока не будет достигнут критерий окончания поиска, например, такой:

Пример 2. Для функции (см. пример 1) найти минимальное значение методом золотого сечения. Программа поиска решения приведена на рисунке 4. Здесь интервал поиска задан вектором с, а точки деления интервала в заданном соотношении заданы вектором z.

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

Здесь задаётся число eps – точность решения задачи, вектор c и функция f. Как видно из приведенных результатов, для достижения заданной точности в методе золотого сечения требуется сделать 28 итераций. Этот метод гарантирует нахождение экстремума в самых неблагоприятных для поиска областях, однако обладает медленной сходимостью.

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

Метод Фибоначчи

Рис. 5. Метод Фибоначчи

Встроенные функции MathCAD для поиска локального минимума/максимума

Для численного решения задач поиска локального максимума и минимума в MathCAD имеются встроенные функции Minerr, Minimize и Maximize.

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

Для поиска локальных экстремумов имеются две встроенные функции, которые могут применяться как в пределах вычислительного блока, так и автономно:

Пример использования

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

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

Условный экстремум

Экстремум функции многих переменных

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

1. Сформулируйте постановку задачи оптимизации.

2. Что такое локальный и глобальный экстремумы?

3. Какие ограничения имеет применение классических методов поиска оптимума?

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

5. Разберите алгоритмы методов одномерного поиска оптимума: дихотомии, золотого сечения, чисел Фибоначчи.

6. Сформулируйте критерий окончания поиска решения в итерационных методах.

7. Какие встроенные в MathCAD функции для решения задачи оптимизации вы знаете?

8. Какие функции могут применяться для решения задачи условной оптимизации?

Практическое занятие. Инструкционная карта на выполнение практического занятия по дисциплине "Компьютерная математика"

Тема: Численное решение задач оптимизации

Цель работы: освоить численное решение задач одномерной оптимизации различными методами; изучить возможности пакета MathCAD для поиска экстремума функции одной и двух переменных

Норма времени: 2 часа.

После выполненных работ студент должен

знать: основные методы одномерной оптимизации: дихотомии, золотого сечения, Фибоначчи;

уметь: решать задачи оптимизации с использованием пакета MathCAD.

Оснащение рабочего места: ПК, инструкционные карты, конспект.

Вводный инструктаж.

Метод дихотомии (половинного деления).

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

Метод Фибоначчи.

Встроенные функции MathCAD для поиска локального минимума/максимума.

Условный экстремум.

Экстремум функции нескольких переменных.

Задания для самостоятельного выполнения.

Задание 1 . Поиск минимума функции одной переменной.

Задание 2. Поиск оптимума функции двух переменных.

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

Литература:

Царегородцева, В. В. Вычислительная математика: лабораторный практикум по курсам «Численные методы» и «Вычислительная математика» для студентов всех специальностей и направлений подготовки / В. В. Царегородцева, Г. И. Севодина; Алт. гос. техн. ун-т, БТИ. – Бийск: Изд-во Алт. гос. техн. ун-та, 2014. – 78 с.

Вводный инструктаж

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

Оптимизируемую функцию f(x) называют целевой функцией, или критерием оптимальности.

К численным методам одномерной оптимизации относятся методы: дихотомического деления; золотого сечения; чисел Фибоначчи; полиномиальной аппроксимации.

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

т. е. длина нового, суженного интервала поиска экстремума по модулю на i-й итерации меньше или равна заданной степени точности решения задачи.

Метод дихотомии (половинного деления)

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

Если окажется, что  , то минимум находится на отрезке , если , то минимум – на , если )  – на  . Таким образом, на следующем шаге вместо отрезка  нужно исследовать суженный отрезок  или  . Шаги повторяются, пока длина отрезка не уменьшится до величины погрешности . Таким образом, требуется не более n шагов, где n – ближайшее к  целое значение, но на каждом шаге целевую функцию следует вычислять дважды.

Пример программы поиска минимума методом дихотомии приведен на рис.1.

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

В соответствии с методом золотого сечения внутри отрезка  выделяют две промежуточные точки  и  на расстоянии  от его конечных точек, где  – длина отрезка. Затем вычисляют значения целевой функции  в точках  и  . Если  , то то минимум находится на отрезке , если  , то на отрезке , если  , то на отрезке  .

Алгоритм метода золотого сечения складывается из следующих этапов:

1) вычисляются значения функции на концах исходного интервала  ;

2) вычисляются промежуточные точки интервала по формулам: , а также значения функции в этих точках;

3) по найденным значениям функции определяется её минимальное значение на интервале;

4) в зависимости от того в какой точке расположен минимум ( или  ) определяется подынтервал, в котором локализован минимум –  или  ;

5) в новом интервале определяется точка по одной из формул п. 2 и итерационный процесс поиска продолжается с п. 3 до тех пор пока не будет достигнут критерий окончания поиска, например, такой: 

Пример программы приведен на рис. 2.

 

Рис. 1. Программа поиска минимума методом дихотомического деления

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

Метод Фибоначчи

Согласно этому методу при разбиении отрезка используют числа Фибоначчи . Последовательность Фибоначчи образуется по правилу: 

Ряд Фибоначчи имеет вид: 1; 1; 2; 3; 5; 8; 13; 21; 34; 55; 89; 144 …

Алгоритм поиска с использованием числе Фибоначчи включает следующие шаги:

1) По заданной точности  рассчитывается вспомогательное число  ;

2) находится ближайшее к N число Фибоначчи  ;

3) определяется минимальный шаг поиска по формуле ;

4) задается начальное значение счетчика шагов i = 0;

5) вычисляются значения  и соответствующие значения функции в этих точках  и ;

6) в зависимости от соотношения  и  выбирается новый интервал локализации минимума:  или  ;

7) внутри полученного интервала (значение счетчика i увеличивается на 1) находится новая точка (x или x1) , симметричная к уже имеющейся точке и отстоящая от конца интервала на величину  , где i – номер шага. В этой точке рассчитывается значение f(x). Указанный процесс продолжается с пункта 5 до тех пор, пока не будут исчерпаны все числа Фибоначчи в убывающей последовательности  , i = 0; 1; 2; …, т. е. пока i не станет равно s – 2. Это будет соответствовать ситуации достижения решения с заданной точностью.

Пример программы приведен на рис. 3.

Рис. 3. Метод Фибоначчи

Встроенные функции MathCAD для поиска локального минимума/максимума

Для численного решения задач поиска локального максимума и минимума в MathCAD имеются встроенные функции Minerr, Minimize и Maximize. Пример приведен на рис.4.

 

Рис. 4. Поиск локальных экстремумов

Условный экстремум

В задачах на условный экстремум встроенные функции минимизации и максимиза-ции должны быть включены в вычислительный блок (solve block), который имеет следующую структуру:

Начальные приближения переменных

Given

Ограничительные условия

Выражения с функциями Minerr, Minimize или Maximize

Экстремум функции нескольких переменных

Вычисление экстремума функции многих переменных не несет принципиальных осо-бенностей по сравнению с функциями одной переменной. Пример нахождения максимума и минимума функции, показанной в виде графика трехмерной поверхности, приведен на рис. 5. Следует обратить внимание к тому, как с помощью неравенств, задается область на плоскости (x, y).

Задания для самостоятельного выполнения

Задание 1 . Поиск минимума функции одной переменной

Постройте графики функций одной переменной. Напишите программы в среде MathCAD и рассчитайте минимальное значение функции с заданной точностью  методами дихотомии, золотого сечения, с использованием чисел Фибоначчи, с помощью встроенной функции Minner. Сравните результаты. Оцените количество итераций, необходимых для достижения заданной точности (таблица 1).

Задание 2. Поиск оптимума функции двух переменных

С помощью встроенных функций MathCAD решите задачу поиска оптимума функции двух переменных F(x, y), предварительно исследовав функцию графически.

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

1. Сформулируйте постановку задачи оптимизации.

2. Что такое локальный и глобальный экстремумы?

3. Какие ограничения имеет применение классических методов поиска оптимума?

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

5. Разберите алгоритмы методов одномерного поиска оптимума: дихотомии, золотого сечения, чисел Фибоначчи.

6. Сформулируйте критерий окончания поиска решения в итерационных методах.

7. Какие встроенные в MathCAD функции для решения задачи оптимизации вы знаете?

8. Какие функции могут применяться для решения задачи условной оптимизации?

Добавить комментарий


Защитный код
Обновить