Без названия - 3.3.3. Методы оптимизации

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

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

В практической деятельности часто из многих возможных решений задачи необходимо выбрать оптимальный. Например, из нескольких вариантов перевозки сырья потребителям необходимо выбрать наиболее дешевый, но такой, который учитывает ограничения на допустимые термины поставок; из возможных планов раскроя материала выбрать такой, который позволит выполнить план при наименьшем количестве отходов и т.д.

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

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

Математическая формулировка задач оптимизации. Несмотря на то что прикладные задачи относятся к совершенно разным областям, они имеют общую форму. Все эти задачи можно классифицировать как задачи минимизации вещественнозначной функции f(x) N-мерного векторного аргумента x=(x1, x2,..., xn), компоненты которого удовлетворяют системе уравнений hk(x)=0, набору неравенств gi(x) 0, а также ограничены сверху и снизу, т.е. xi(u) xi xi(l). В последующем изложении функцию f(x) будем называть целевой функцией, уравнения hk(x)=0 – ограничениями в виде равенств, а неравенства gi(x) 0 – ограничениями в виде неравенств. При этом предполагается, что все фигурирующие в задаче функции являются вещественнозначными, а число ограничений конечно.

Задача общего вида: минимизировать f(x) при ограничениях

hk(x)=0, k=1, ..., K,

gj(x) 0 j=1, ..., J,

xi(u) xi xi(l), i=1, ..., N

называется задачей оптимизации с ограничениями или задачей условной оптимизации. Задача, в которой нет ограничений, т.е.

J=K=0;

xi(u)= - xi(l) = ∞, i=1, ..., N,

называется оптимизационной задачей без ограничений или задачей безусловной оптимизации.

Поиски оптимальных решений привели к созданию специальных математических методов и уже в 18 веке были заложены математические основы оптимизации (вариационное исчисление, численные методы и др). Однако до второй половины 20 века методы оптимизации во многих областях науки и техники применялись очень редко, поскольку практическое использование математических методов оптимизации требовало огромной вычислительной работы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев - невозможно. Особенно большие трудности возникали при решении задач оптимизации процессов в химической технологии из-за большого числа параметров и их сложной взаимосвязи между собой. При наличии ЭВМ задача заметно упрощается.

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

Методы одномерной оптимизации. Несмотря на то, что безусловная оптимизация функции одной переменной наиболее простой тип оптимизационных задач, она занимает центральное место в теории оптимизации как с теоретической, так и с практической точек зрения. Это связано с тем, что задачи однопараметрической оптимизации достаточно часто встречаются в инженерной практике и, кроме того, находят свое применение при реализации более сложных интерактивных процедур многопараметрической оптимизации.

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

Все методы одномерной оптимизации основаны на предположении, что исследуемая целевая функция в допустимой области по крайней мере обладает свойством унимодальности, так как для унимодальной функции W(x) сравнение значений W(t) в двух различных точках интервала поиска позволяет определить, в каком из заданных двумя указанными точками подинтервалов точки оптимума отсутствуют.

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

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

Методы с использованием производной. Целесообразно предположить, что эффективность поисковых процедур существенно повысится, если в дополнение к условию непрерывности ввести требование дифференцируемости целевой функции. Необходимое условие существования оптимума целевой функции в точке x*

W'(x*) = dW/dx f x=x* = 0.

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

К методам многомерной оптимизации относятся методы нулевого порядка ( покоординатного спуска, Хука-Дживса, симплексный метод Нелдера-Мида); методы первого порядка ( градиентный; наискорейшего спуска; сопряженных градиентов (метод Давидона-Флетчера-Пауэлла; метод Флетчера-Ривса).

Одними из методов нахождения минимума функции n-переменных являются методы прямого поиска. Методы прямого поиска являются методами, в которых используются только значения функции.

Одним из методов прямого поиска есть метод Хука-Дживса, который был разработан в 1961г, но до сих пор является весьма эффективным и оригинальным. Метод Хука-Дживса характеризуется несложной стратегией поиска, относительной простотой вычислений и невысоким уровнем требований к памяти ЭВМ. Это один из первых алгоритмов, в котором при определении нового направления поиска учитывается информация, полученная на предыдущих итерациях. Процедура Хука-Дживса представляет собой комбинацию исследующего поиска с циклическим изменением переменных и ускоряющего поиска по образцу.

Метод Нелдера-Мида (поиск по деформируемому многограннику) является развитием симплексного метода Спендли, Хекста и Химсворта. Множество (n+1)-й равноудаленной точки в n-мерном пространстве называется регулярным симплексом. Эта конфигурация рассматривается в методе Спендли, Хекста и Химсворта. Следовательно, в двумерном пространстве симплексом является равносторонний треугольник, а в трехмерном пространстве правильный тетраэдр. Идея метода состоит в сравнении значений функции в (n+1)вершинах симплекса и перемещении в направлении оптимальной точки с помощью итерационной процедуры. В симплексном методе, предложенном первоначально, регулярный симплекс использовался на каждом этапе. Нелдер и Мид предложили несколько модификаций этого метода, допускающих, чтобы симплексы были неправильными. В результате получился очень надежный метод прямого поиска, являющийся одним из самых эффективных, если n 6.

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

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

Метод Флетчера-Ривса основан на том, что для квадратичной функции n переменных n одномерных поисков вдоль взаимно сопряженных направлений позволяют найти минимум.

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

Методы решения задач нелинейного программирования (условной многопараметрической оптимизации) подразделяют следующим образом: методы прямого поиска (модифицированный метод Хука-Дживса; метод комплексов; метод случайного поиска.); методы штрафных функций; методы линеаризации.

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

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

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

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

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

Методы с использованием производных. Целесообразно предположить, что эффективность поисковых процедур существенно повысится, если в дополнение к условию непрерывности ввести требование дифференцируемости целевой функции. Необходимое условие существования оптимума целевой функции в точке x*

W'(x*) = dW/dx f x=x* = 0.

Метод хорд Ориентирован на нахождение корня уравнения W'(x) в интервале [a,b], в котором имеются две точки N и P, в которых знаки производных различны. Алгоритм метода хорд позволяет аппроксимировать функцию W'(x) "хордой" и найти точку, в которой секущая графика W'(x) пересекает ось абсцисс.

Метод касательных. Ориентирован на нахождение корня уравнения W'(x) в интервале [a,b], в котором имеются две точки N и P, в которых знаки производных различны. Работа алгоритма начинается из точки xo, которая представляет начальное приближение корня уравнения W'(x)=0. Далее строится линейная аппроксимация функции W'(x) в точке x1, и точка, в которой аппроксимирующая линейная функция обращается в нуль, принимается в качестве следующего приближения. Если точка xk принята в качестве текущего приближения к оптимальной точке, то линейная функция, аппроксимирующая функцию W'(x) в точке xk, записывается в виде

W'(x,xk) = W'(xk) + W''(xk)(x-xk).

Приравняв правую часть уравнения к нулю, получим следующее приближение к искомой точке.

Метод средней точки. Основан на алгоритме исключения интервалов, на каждой итерации которого рассматривается одна пробная точка R. Если в точке R выполняется неравенство W'(R) < 0, то в следствии унимодальности функции точка оптимума не может лежать левее точки R. Аналогично, если W'(R) > 0, то интервал x >R можно исключить.

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

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

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

LP88 - это автономная программа на машинном языке, не требующая какого-либо специального программного обеспечения.

B LP88 применяется модифицированный симплекс-алгоритм для эффективного решения задач линейного программирования.