Метод барьерных функций excel
Совершенно иной подход используется в методах штрафных и барьерных функций. Ограничения задачи специальным образом отражаются в критерии, в результате чего критерий модифицируется, а исходная задача на условный экстремум сводится к задаче на безусловный экстремум.
В методе штрафных функций в критерий вводится штраф при нарушении условий задачи. Пусть в общем случае имеем задачу
f(x) à min; (8.65)
ji(x) £ 0, ; (8.66)
yi(x) = 0 , . (8.67)
Тогда можно построить вспомогательную функцию
Q(x) = f(x) + a×H(x), (8.68)
где H(x)–функция штрафа, a - параметр штрафа.
Вспомогательная функция играет роль модифицированного критерия, который при выполнении всех ограничений должен совпадать с исходным. Поэтому необходимо, чтобы в допустимой области Н(х) равнялась нулю, а вне ее была положительной. Для задачи (8.65)-(8.67) функция штрафа включает две составляющие Н(х) =Нj(x) + Нy(x), учитывающие ограничения-неравенства и ограничения-равенства соответственно и удовлетворяющие условиям
Возможны разные конструкции функций, обладающих указанными свойствами. Типичные представители составляющих штрафной функции имеют вид
где р – натуральное число. Для дифференцируемости функций берут четные значения р, обычно р = 2.
Чем больше a, тем сильнее влияет функция штрафа и, значит, тем точнее выполняются условия задачи.
Пример 8.8. Дана задача
f(x) = x à min;
j(x)=3 – x £ 0.
Ответ очевиден: x * =3. Теперь сведем эту задачу к определению безусловного экстремума вспомогательной функции. Построим штрафную функцию в соответствии с (8.69): H = [max (0, 3-x)] 2 . Тогда приходим к задаче
Q=x+a[max (0, 3-x)] 2 ® min.
На рис. 8.41 и 8.42 показаны функции aH и Q для двух значений a. Видно, что точки минимума вспомогательной функции с увеличением a приближаются к точке условного минимума исходной задачи. Такой же вывод следует из аналитического решения. Действительно, при x
Q = x + a× (3 - x) 2 .
Находим минимум этой функции:
Пример 8.9. Рассмотрим влияние параметра шага в задаче
Здесь и На рис. 8.43 построены линии уровня функции q для разных значений a и линия ограничения y. При a=0 имеем q=f,и минимум q достигается в точке безусловного минимума f: x1=x2=1. С увеличением a меняется форма линий уровня q и положение минимума. При a=1 минимум q смещается к линии ограничения, а при a=1000 он практически точно совпадает с условным минимумом задачи.
В обоих примерах с увеличением a генерируемые точки приближаются к оптимальному решению извне допустимого множества. Поэтому ряд авторов называют рассматриваемый метод методом внешних штрафов.
Таким образом, чтобы безусловный минимум вспомогательной функции был близок к условному минимуму решаемой задачи, необходимо брать очень большое значение a, теоретически бесконечное. Однако при больших a возникают серьезные трудности при поиске минимума вспомогательной функции. Поэтому предлагается решать последовательность задач минимизации Q с возрастающими значениями a. При этом в качестве начальной точки следующей задачи берется оптимальная точка предыдущей. Такой прием использован в следующем алгоритме штрафных функций.
1. Задать: начальную точку x 0 , точность e, начальное значение a0 и число b > 1.
2. Минимизировать Q(x) одним из методов безусловной оптимизации, в результате чего определяется .
3. Проверить: если , то остановиться, приняв за оптимальное решение задачи.
4. Положить , за начальную точку принять и вернуться на шаг 2.▲
Рекомендуется выбирать значения параметров алгоритма из диапазонов: a0Î(0,1], bÎ(1,10]. Начальную точку следует задавать в недопустимой области.
Пример 8.10. Алгоритмом штрафных функций решить задачу
Возьмем начальную точку x 0 =(-5;5), a0=0,21, b=5 и e=0,0001. Применяя для минимизации Q метод Ньютона, получаем результаты, представленные в табл. 8.4.
№ итерации | a | x1 | x2 | f | Q | aH |
0.21 | -5 | 283.533 | 13.533 | |||
1.05 | -0.191 | -0.132 | -0.094 | 0.939 | 1.032 | |
5.25 | -0.209 | -0.169 | -0.09 | 5.035 | 5.125 | |
26.25 | -0.654553 | -1.059105 | 1.651353 | 13.504372 | 11.853019 | |
131.25 | -0.990765 | -1.731532 | 5.068137 | 7.691651 | 2.623514 | |
656.25 | -1.046856 | -1.843717 | 5.814225 | 6.343889 | 0.529664 | |
3281.25 | -1.057736 | -1.865478 | 5.964774 | 6.070887 | 0.106113 | |
16406.25 | -1.059899 | -1.869804 | 5.994933 | 6.016163 | 0.02123 | |
82031.25 | -1.060331 | -1.870668 | 6.000967 | 6.005213 | 0.004246 | |
410156.25 | -1.060417 | -1.870841 | 6.002174 | 6.003023 | 0.000849 | |
2050781.25 | -1.060434 | -1.870876 | 6.002415 | 6.002585 | 0.00017 | |
>10 7 | -1.060434 | -1.870884 | 6.002469 | 6.002503 | 3.397E-05 |
Как следует из таблицы, решение с заданной высокой точностью получено за 11 итераций алгоритма. Заметим, что несмотря на увеличение a значение aH сходится к нулю, обеспечивая сходимость алгоритма. Траектория поиска и линии уровня функции f изображены на рис. 8.44.▲
Другой пример поиска методом штрафных функций приведен на рис. 8.45 для задачи
Поиск проведен из начальной точки (-2;-7) с параметрами a0=0,1 и b=2. Здесь, как и в предыдущем примере, на первой итерации алгоритма движение направлено в сторону безусловного минимума целевой функции. Это объясняется небольшим начальным значением параметра штрафа, при котором основное влияние на направление оказывает целевая функция. С возрастанием a направление поиска ориентируется на условный экстремум.
Еще один пример поиска показан на рис. 8.46 для задачи
Здесь поиск производился при a0=1 и b=10. Такие параметры обусловили другой характер движения к условному минимуму: первая итерация уже не приводит в окрестность безусловного экстремума и траектория не имеет резких изменений направления поиска.
Таким образом, выбор параметров поиска имеет существенное влияние на эффективность алгоритма.
Метод барьерных функций
В отличие от метода штрафных функций, данный метод применим к задачам с ограничениями только в виде неравенств.
Суть метода заключается в том, что поиск начинается обязательно из внутренней точки и последующие точки не должны выходить из допустимой области. С этой целью задача модифицируется так, что при приближении к границе допустимой области растет барьер, препятствующий выходу на границу.
Исходная задача на условный экстремум задается в виде
f(x) à min; (8.70)
ji(x) £ 0, . (8.71)
Она преобразуется в задачу безусловной минимизации вспомогательной функции
Q(x) = f(x) + mB(x),
где B(x) – барьерная функция, m - параметр барьера.
Обязательное условие: внутренность области не должна быть пустой (имеются точки, в которых "ji (x) < 0).
Барьерная функция строится так, чтобы она была неотрицательной и непрерывной на допустимом множестве и стремилась к бесконечности при приближении изнутри к границе:
Как и в случае штрафной функции, существует несколько конструкций B(x), удовлетворяющих этим условиям. Но в основном используется барьерная функция в виде
Понятно, что решение вспомогательной задачи зависит от значения параметра барьера. Покажем на задаче из примера 8.7 влияние m на результат минимизации Q.
Пример 8.11. Исходная задача:
f(x) = x à min;
j(x)=3 – x £ 0.
Барьерную функцию строим согласно (8.72). Тогда вспомогательная функция имеет вид
Находим точку минимума Q:
Следовательно, с уменьшением m точки минимума вспомогательной функции приближаются к минимуму исходной задачи. Геометрическая иллюстрация решения приведена на рис. 8.47.
Как хорошо видно на рис. 8.47, при оптимуме исходной задачи на границе допустимого множества последовательность точек минимума Q с уменьшением m приближается к оптимальному решению изнутри допустимой области. По этой причине метод барьеров называют еще методом внутренних штрафов.
В связи с возможными трудностями поиска при малых значениях m решается не одна, а последовательность вспомогательных задач с уменьшающимися значениями параметра барьера.
1. Выбрать начальную точку x 0 так, чтобы "ji(x 0 )e, начальное значение m0 и число b Î (0, 1).
2. Минимизировать Q(x) одним из методов безусловной оптимизации, в результате чего определяется .
3. Проверить: если , то остановиться, приняв за оптимальное решение задачи.
5. Положить , за начальную точку принять и вернуться на 2.▲
Значение m0 можно брать из интервала [2, 10]. Важное замечание касается п.2 алгоритма: в процессе поиска минимума вблизи границы из-за дискретности шагов возможен выход за допустимую область, где барьерная функция становится отрицательной, что повлечет расхождение поиска. Поэтому необходима явная проверка на допустимость точек на каждом шаге при минимизации Q.
Пример 8.10 (Базара, Шетти). Исходная задача:
f(x) = (x1-2) 4 +( x1-2x2) 2 ® min;
j(x)= x2£ 0.
Решение находим, используя соответствующую вспомогательную функцию
За начальную точку возьмем допустимую точку (0;1), значения m и b принимаем равными 10. Результаты поиска алгоритмом барьерных функций представлены в табл. 8.5 и на рис. 8.48.
№ итерации | m | x1 | x2 | f | Q | mB |
0.7079 | 1.5315 | 8.3338 | 18.0388 | 9.705 | ||
1.0 | 0.8282 | 1.1098 | 3.8214 | 6.1805 | 2.3591 | |
0.1 | 0.8989 | 0.9638 | 2.5282 | 3.1701 | 0.6419 | |
0.01 | 0.9294 | 0.9162 | 2.1291 | 2.3199 | 0.1908 | |
0.001 | 0.9403 | 0.9011 | 2.0039 | 2.0629 | 0.0590 | |
0.0001 | 0.94389 | 0.89635 | 1.9645 | 1.9829 | 0.0184 |
Как и следовало ожидать, с уменьшением m значение mB стремится к нулю.
Завершая рассмотрение методов штрафных и барьерных функций, отметим, что можно построить алгоритм, использующий как штрафы, так и барьеры. Для этого достаточно записать смешанную вспомогательную функцию в виде
Q(x) = f(x) + mB(x) + где барьерная функция B(x) применяется к неравенствам, а штрафная функция Н(х) – к ограничениям-равенствам. Последовательность задач минимизации Q решается с уменьшающимися значениями параметра m.
Функция является штрафной. Необходимо, чтобы при нарушении ограничений она «штрафовала» функцию Z, т.е. увеличивала её значение.В этом случае минимум функции Z будет находиться внутри области ограничений. Функция , удовлетворяющая этому условию, может быть не единственной. Задачу минимизации можно сформулировать следующим образом:
Функцию удобно записать следующим образом:
где r – положительная величина.
Тогда функция принимает вид
Если х принимает допустимые значения, т.е. значения, для которых , то Z принимает значения, которые больше соответствующих значений (истинной целевой функции данной задачи), и разность можно уменьшить за счет того, что r может быть очень малой величиной. Но если х принимает значения, которые хотя и являются допустимыми, но близки к границе области ограничений, и по крайней мере одна из функций близка к нулю, тогда значения функции , и следовательно значения функции Z станут очень велики. Таким образом, влияние функции состоит в создании «гребня с крутыми краями» вдоль каждой границы области ограничений. Следовательно, если поиск начнется из допустимой точки и осуществляется поиск минимума функции без ограничений, то минимум, конечно, будет достигаться внутри допустимой области для задачи с ограничениями. Полагая r достаточно малой величиной, для того чтобы влияние было малым в точке минимума, мы можем сделать точку минимума функции без ограничений совпадающей с точкой минимума задачи с ограничениями.
Алгоритм метода штрафных функций
Пусть имеется следующая задача: Минимизировать при ограничениях ,.
Начальный этап Выбрать в качестве константы остановки, начальную допустимую точку ∈, для которой , , скаляр и . Положить k=1 и перейти к основному этапу.
Основной этап. k-я итерация.
Первый шаг. При исходной точке решить следующую задачу безусловной оптимизации:
- параметр, значения которого убывают с каждой итерации при ; - положительные весовые коэффициенты.
Примерами штрафных функций являются:
1) обратная функция
2) логарифмическая функция
Положить равным оптимальному решению задачи минимизации и перейти ко второму шагу.
Минимизация штрафной функцию может быть выполнена любым методом безусловной оптимизации, например, градиентным.
Если , то остановиться. Решение является искомым.
В противном случае положить . Изменить и перейти к первому шагу (k+1)-й итерации.
Метод барьерных функций
Изложение метода
Метод штрафных функций относится к группе методов внутренней точки, т.е. он начинает работать с допустимой точки и генерирует последовательность допустимых точек . Метод барьерных функций, наоборот, относится к группе методов внешней точки, он начинает поиск с недопустимой точки и генерирует последовательность недопустимых решений, которая приближается к оптимальному решению извне допустимой области.
Пусть имеется задача минимизировать при ограничениях
В частности, для искомых функций – ограничений целесообразно использовать барьерную функцию следующего вида:
- непрерывные функции, которые удовлетворяют условиям: , если и , если , , если и , если .
Типичными являются следующие выражения для функций :
, , где р – целое положительное число.
Далее от исходной задачи переходим к задачи безусловной оптимизации вспомогательной функции: минимизировать , где - штрафной коэффициент.
Пусть α– непрерывная функция. Обозначим .
Подход, связанный с барьерной функцией состоит в решении задачи вида:
максимизировать при ограничении
Алгоритм метода барьерных функций
Пусть имеется следующая задача:
Минимизировать при ограничениях ,, где функции .
Начальный этап Выбрать Выбрать начальную точку , параметр штрафа и число . Положить k=1 и перейти к основному этапу.
Основной этап. k-я итерация.
Первый шаг. При начальной точке и параметре штрафа решить следующую задачу:
Положить равным оптимальному решению задачи и перейти ко второму шагу.
Если , то остановиться.
В противном случае положить . Заменить k на k+1 и перейти к первому шагу.
Пример реализации
Рассмотрим задачу Розена-Сузуки и реализуем её решение с помощью метода штрафных функций. Задача Розена-Сузуки заключается в следующем: необходимо минимизировать функцию
со следующими ограничениями
Ниже приведена таблица промежуточных результатов алгоритма.
Число итераций | Значение миимизируемой функции | Координаты первой точки | Координаты второй точки | Координаты третьей точки | Координаты четвертой точки |
---|---|---|---|---|---|
0 | nfmin=-43.739500 | x1=-0.010000 | x2=0.990000 | x3=1.990000 | x4=-0.990000 |
10 | nfmin=-43.762449 | x1=-0.009498 | x2=0.990302 | x3=1.991304 | x4=-0.990502 |
20 | nfmin=-43.785381 | x1=-0.008996 | x2=0.990604 | x3=1.992607 | x4=-0.991004 |
30 | nfmin=-43.808298 | x1=-0.008494 | x2=0.990906 | x3=1.993910 | x4=-0.991506 |
40 | nfmin=-43.831199 | x1=-0.007993 | x2=0.991208 | x3=1.995212 | x4=-0.992007 |
50 | nfmin=-43.854084 | x1=-0.007491 | x2=0.991509 | x3=1.996514 | x4=-0.992509 |
Оптимальную точку мы получаем на 114й итерации с оптимальным значением функции
Рекомендация программисту
Использование штрафных функций для решения задач связано с определенной вычислительной трудностью. Прежде всего поиск может начинаться с допустимой точки х, для которой , .Для некоторых задач находить такую точку довольно сложно. Кроме того, вследствие использования в алгоритме оптимизации дискретных шагов около границы возможен шаг, который выводит за границы допустимой области. Он приводит к уменьшению значений функции , т.е. к фиктивному успеху. Таким образом, нужна явная проверка допустимости каждой последующей точки, для чего на каждой итерации необходимо вычислять значения функции ,.
На эффективность метода барьерных функций существенно влияют выбор начального значения и метод сокращения значений в процессе минимизации, а также выбор весовых коэффициентов . Если в функции значение , выбирают слишком малым, то уже на начальной стадии процесса приходят к минимуму функции , который вряд ли окажется вблизи действительного условного минимума в точке ,. С другой стороны, если значение , выбирается слишком большим, то на первых итерациях вычислительного процесса текущая точка неизбежно окажется слишком далеко за пределами допустимой области, и поиск из-за необходимости возврата в пределы допустимой области окажется весьма затяжным.
Даны дважды непрерывно дифференцируемые целевая функция f ( x ) = f ( x 1, . xn) и функции ограничений-неравенств gj( x ) ≤ 0, j = 1, . m , определяющие множество допустимых решений X .
Требуется найти локальный минимум целевой функции на множестве X , т. е. такую точку х *∈ X , что
Стратегия поиска
Идея метода заключается в сведении задачи на условный минимум к решению последовательности задач поиска минимума вспомогательной функции F ( x , rk) = f ( x ) + P ( x , rk), где P ( x , rk) — штрафная функция, rk> 0 — параметр штрафа.
Как правило, используются:
а) обратная штрафная функция (рис. 9.7, а);
б) логарифмическая штрафная функция (рис. 9.7, б ).
Рис 9.7
Обе штрафные функции определены и непрерывны внутри множества Х , т. е. на множестве < x | gj( x ) < 0, j = 1, . m >, и стремятся к бесконечности при приближении к границе множества изнутри. Поэтому они называются барьерными функциями . При rk> 0 штрафная функция, задаваемая обратной функцией, положительна. Логарифмическая штрафная функция положительна при –1 < g ( x ) < 0 и отрицательна при g ( x ) < –1, т. е. внутренним точкам области отдается предпочтение перед граничными точками.
Начальная точка задается только внутри множества X . На каждой k - й итерации ищется точка x *( rk) минимума вспомогательной функции F ( x , rk) при заданном параметре rkс помощью одного из методов безусловной минимизации. Полученная точка x *( rk) используется в качестве начальной на следующей итерации, выполняемой при уменьшающемся значении параметра штрафа. При rk → +0 последовательность точек x *( rk) стремится к точке условного минимума х *. Барьерные функции как бы препятствуют выходу из множества X , а если решение задачи лежит на границе, то процедура метода приводит к движению изнутри области к границе.
Заметим, что согласно описанной процедуре точки x *( rk) лежат внутри множества допустимых решений для каждого rk. Этим объясняется то, что метод барьерных функций иногда называется методом внутренних штрафов .
Шаг 1. Задать начальную точку х 0внутри области X ; начальное значение параметра штрафа rk≥ 0; число С > 1 для уменьшения параметра штрафа; малое число ε > 0 для остановки алгоритма. Положить k = 0.
Шаг 2. Составить вспомогательную функцию:
Шаг 3. Найти точку x *( rk) минимума функции F ( x , rk) с помощью какого-либо метода (нулевого, первого или второго порядка) поиска безусловного минимума с проверкой принадлежности текущей точки внутренности множества X . При этом задать все требуемые выбранным методом параметры. В качестве начальной точки взять х k. Вычислить:
Шаг 4. Проверить выполнение условия окончания:
а) если | P (х *( rk), rk) | ≤ ε, процесс поиска закончить: х *= x *( rk), f (х *) = f ( x *( rk));
б) если | P (х *( rk), rk) | > ε, положить и перейти к шагу 2.
Лазаренко Виктория Сергеевна студент 4 курса, Ставропольский государственный педагогический институт, РФ, г. Ставрополь Кузина Наталья николаевна научный руководитель, Старший преподаватель кафедры математики и информатики, Ставропольский государственный педагогический институт, РФ, г. Ставрополь
« РЕАЛИЗАЦИЯ МНОГОМЕРНЫХ ЗАДАЧ ОПТИМИЗАЦИИ В excel» Аннотация: В статье рассмотрены основные методы многомерной оптимизации, ПРИВЕДЁН ПРИМЕР РЕАЛИЗАЦИИ ЗАДАЧИ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ (МЕТОДА ПОКООРДИНАТНОГО СПУСКА) В среде Excel. КЛЮЧЕВЫЕ СЛОВА: многомерная оптимизация, условная оптимизация, БЕЗУСЛОВНАЯ ОПТИМИЗАЦИЯ.
Изучение задач многомерной оптимизации заключается в нахождении точек минимума функции почти всех переменных на всем промежутке определенной размерности.
Такая задача сложнее задачи минимизации функции одной переменной, в связи с тем, что с увеличением размерности места переменных, растёт размер вычислений и возникает трудность в построении алгоритмов, тем самым возникают трудности в изучении поведения мотивированной функции.
В данной статье мы рассмотрим численные методы оптимизации, т.е. способы построения алгоритмов нахождения оптимального (минимального или максимального) познания некой функции и для наглядности реализуем пример многомерной оптимизации в Excel. Ведь Excel – это одна из наиболее узнаваемых и известных программ, возможности которой разрешают стремительно отыскивать действенное решение, начиная с математических задач и заканчивая применением оптимизации в самых различных сферах работе человека.
Численные методы многомерной оптимизации
Существуют разные методы безусловной и условной оптимизации. К безусловной оптимизации относятся методы: покоординатного спуска, метод наискорейшего спуска и подпрограмма EXCEL “Поиск решения”. Линейное программирование, метод штрафных функций и подпрограмма EXCEL “Поиск решения” – это условная оптимизация.
Суть методов безусловной оптимизации состоит в поиске минимуму функции методом неоднократных вычислений, при разных значениях характеристик х = k>, где k = 0, 1, 2, . Методы условной оптимизации применяются при наличии ограничений. Задача условной оптимизации заключается в поиске минимального или максимального значения скалярной функции f(x) n-мерного векторного аргументах. Решение задачи основывается на линейной или квадратичной аппроксимации целевой функции для определения приращений x1, …,xn на каждой итерации.
Рассмотрим более подробно безусловную оптимизацию, её методы и реализацию примера в Excel.
Метод покоординатного спуска (метод прямого поиска), в котором используются лишь значения целевой функции. Чтобы воспользоваться этим методом, необходимо иметь такие исходные данные, как: формулу целевой функции, имеющую вид f(X1,X2, . , Xn); Е - точность нахождения значений независимых переменных, при которых функция достигает минимума; начальные приближения X10,X20 . , Xn0.
Стоит отметить, что метод покоординатного спуска сводит многомерную задачу оптимизации к многократному решению одномерных задач по каждой независящей переменной.
Приведём пример, чтобы показать наглядно сущность метода и его разрешение.
Условие задачи: число независимых переменных равняется двум. Ограничения отсутствуют. Требуется найти минимум функции
из начальной точки (0,5;0,5) c точностью 0,0001. Проанализировав функцию, заметим, что она будет иметь минимум, равный нулю. Для чего и первое, и второе слагаемое тоже должны быть равны нулю. Откуда координаты точки минимума (1;1).
Решим эту задачу на EXCEL. Откроем новый рабочий лист, где столбец А -значения X1, столбец В - значения X2, а столбец С - значения целевой функции и, наконец, столбец D - значения погрешности D.
Занесем в ячейки А3 и В3 значения начальных приближений, равных 0,5 и в ячейку С3 формулу =(В3-А3^2)^2+(1-A3)^2. Скопируем эту формулу в блок ячеек С4:С17. На этом заканчивается подготовительный этап.
Опишем первую итерацию, для этого скопируем содержимое ячейки В3 в ячейку В4. Сделаем текущей ячейку С4. Процесс одномерной оптимизации для нахождения X1 выполним с помощью подпрограммы EXCEL «Поиск решения». Вызовем эту подпрограмму командой меню Сервис - Поиск решения.
Теперь скопируем содержимое ячейки А4 в ячейку А5. Сделаем текущей ячейку С5. Зададим команду меню Сервис - Поиск решения. В открывшемся диалоге в поле Установить целевую ячейку занесем адрес С5, а в поле Изменяя ячейки - адрес В5. В результате в ячейке В5 получим числовое значение, при котором целевая функция достигает минимального значения в ячейке С5 по координате X2.
Вычислим погрешности решения на первом шаге, для этого внесём в ячейку D5 формулу =ABS(A3-A5)+ABS(B3-B5). На этом заканчивается первая итерация.
Вторая и все последующие итерации проводятся аналогично, но с учетом соответствующих адресов ячеек.
Можно построить диаграмму изменения на каждой итерации, на которой видны перпендикулярные ломаные линии движения от точки к точке параллельно одной из осей координат.
Реализация метода покоординатного спуска представлена в Excel на рисунке 1.
Рисунок 1. Метод покоординатного спуска в Excel
Можно сказать, что сегодня оптимизационные задачи и задачи принятия решений моделируются и решаются в самых различных областях[1], в связи с этим растёт необходимость развития математического аппарата оптимизации. Решение задач с помощью Excel, позволяем наглядно разобраться с задачей и решить её.
Практика порождает все новые и новые задачи оптимизации, причем их сложность растет. Требуются новые математические модели и методы, которые учитывают наличие многих критериев.
Список литературы
1. Корнеенко В. П. Методы оптимизации: Учебник / В. П. Корнеенко. - М.: Высш. шк., 2007.
2. Пантелеев А. В. Методы оптимизации в примерах и задачах: Учеб. пособие / А. В. Пантелеев, Т. А. Летова. - М.: Высш. шк., 2005.
3. Батищев Д. И. Оптимизация в САПР: Учебник / Д. И. Батищев, Я. Е. Львович, В. Н. Фролов. - Воронеж: Изд-во ВГУ, 1997.
Поскольку БПФ по сравнению с обычным анализом Фурье многократно уменьшает объём вычислений (см. выше), именно метод БПФ реализован в MS EXCEL инструментом «Анализ Фурье» (рис. 8.9).
Рис. 8.9. Окно инструмента «Анализ Фурье»
Эта процедура поддерживает также обратные преобразования, при этом инвертирование преобразованных данных возвращает исходные данные. Если установлен флажок в поле «Инверсия», то данные во входном диапазоне считаются преобразованными, и выполняется обратное преобразование, возвращающее их в выходной диапазон в исходном состоянии. Если флажок снят, то выполняется прямое преобразование.
Комплексные данные должны задаваться в формате х + yi. Число значений во входном интервале должно быть равно 2 k (см. выше). Если х является отрицательным числом, перед ним ставится апостроф ('). Максимальное число значений, предназначенных для БПФ в программе EXCEL, равно 4096.
Пример. Имеются исходные данные, представляющие собой результаты последовательных замеров толщины пластин (см. выше), заданные столбцами в файле «временные ряды». С помощью инструмента «Анализ Фурье» провести прямое и обратное преобразования, построить амплитудный и фазовый спектр.
Алгоритм действий следующий:
1. Формируем таблицу исходных данных:
Сервис - Анализ данных - Анализ Фурье - OK.
Задаём входной интервал в виде столбца данных длиной 2 k , например А10:А137 и выходной интервал (верхнее поле, начиная с которого будут приведены выходные данные) и нажимаем ОК.
Excel представит результаты прямого преобразования Фурье в виде столбца комплексных чисел в формате х + yi.
2. Для восстановления исходных данных после преобразования Фурье за входной интервал необходимо взять столбец результатов прямого преобразования Фурье и поставить флажок в поле «Инверсия».
3. Для построения значений амплитудного спектра воспользуемся функцией или формулой = MHИM.ABS. Сосчитаем с её помощью модуль комплексного числа, расположенного в верхней ячейке столбца комплексных чисел, полученных по п. 1. Затем, копируя ячейки, распространим эту формулу на весь столбец комплексных чисел. По полученному ряду (или столбцу) модулей комплексных чисел можно построить график амплитудного спектра, например, в виде столбчатой диаграммы («Мастер диаграмм» - «Линейчатая»).
4. Для построения значений фазового спектра воспользуемся функцией или формулой = МНИМ.АРГУМЕНТ, выражающей угол наклона вектора комплексного числа в радианах. Аналогично п. 3 распространим эту формулу на весь столбец результатов прямого преобразования Фурье (см. п. 1). По полученным данным аналогично п. 3 можно построить график амплитудного спектра.
Читайте также: