Систематизация методов оптимизации

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Введение

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

Оптимизация - целенаправленная деятельность, заключающаяся в получении результатов при соответствующих условиях.

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

1. Систематизация методов оптимизации

оптимизация метод сканирование сечение

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

Основные методы оптимизации, наиболее широко используемые в химической технологии можно разделить на несколько групп:

Аналитические методы:

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

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

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

Принцип максимума.

Методы математического программирования:

Динамическое программирование.

Нелинейное программирование.

Линейное программирование.

Градиентные методы.

Статистические методы.

2. Статистические методы оптимизации

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

Существует две области изменения выходного параметра у:

Область, удаленная от оптимума, в которой происходит значительное изменение у.

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

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

3. Метод Бокса-Уилсона (метод крутого восхождения по поверхности отклика)

Постановка задачи оптимизации:

Определить координату оптимальной (экстремальной) точки (Х1опт, Х2опт, …, Хnопт) поверхности отклика y=f(x1,…, xn) - это градиентный метод. Метод градиента предусматривает движение к оптимуму по кратчайшему пути, т.е. по градиенту. Градиент - это вектор, направленный в сторону наибыстрейшего изменения функции. Метод Бокса-Уилсона - шаговый метод движения по поверхности отклика.

Уопт = а(Х1опт, Х2опт).

Рисунок 1 - Графическое представление метода Бокса-Уилсона

Пусть находимся в точке М (рис.1). В этой точке ставится полный факторный эксперимент (ПФЭ) или дробный факторный эксперимент (ДФЭ) для локального описания поверхности в точке М линейным уравнением (1):

(1).

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

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

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

Шаг по каждой оси дает частное производное по переменной Хi (2), (3):

(2); (3);

Чтобы двигаться к оптимуму мы должны делать шаги пропорциональные коэффициентам регрессии (4):

grad f = b1Дx1 + b2Дx2 (4).

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

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

Для базового фактора выбирают шаг варьирования крутого восхождения hа, оставляя прежний интервал варьирования ДХi или выбирая новый более мелкий.

Производят расчет шага для каждого фактора по выражению(5):

(5).

Коэффициенты берутся со своими знаками.

Движение начинают от основного уровня. При первом опыте факторы будут получать значения:

Хi = Хi0 + hi

4. Метод деления отрезка пополам (метод дихотомии)

Рассмотрим поиск максимума в данном случае на отрезке АВ (рис. 2):

Рисунок 2 - Графическое представление метода деления отрезка пополам

Алгоритм:

Делим отрезок АВ пополам точкой L и рассчитываем в точке L значение функции F(L).

Выбираем малое приращение или () и откладываем его влево или вправо от точки L и рассчитываем в точке Р значение функции.

Сравниваем значения функций F(L) и F(Р): если F(L)>F(Р), то максимум может находиться в левой части отрезка.

Отбрасываем ту часть отрезка, где максимума нет (в данном случае правую) и переносим точку В в точку Р или L.

Получили отрезок АВ. Алгоритм повторяется.

Новый отрезок АВ делится пополам. Если F(L)<F(Р), то отбрасываем левый отрезок.

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

Процедура продолжается до тех пор, пока не выполнится заданное условие:

.

5. Метод «Золотого сечения»

Поиск оптимума основан на делении отрезка на 2 части, при этом отношение длины всего отрезка к большей его части равно отношению большей части к меньшей:

- точка «Золотого сечения»

Рассмотрим поиск оптимума максимума методом «Золотого сечения».

Делим отрезок АВ слева и справа в отношении «Золотого сечения». Получаем точки L и Р (рис.3). Рассчитываем значения функций в точках L и Р и сравниваем их.

Рисунок 3 - Графическое представление метода «Золотого сечения»

Если F(L) > F(P), то максимум может находиться либо на участке АL, либо LP на участке PB максимума быть не может, если функция унимодальна.

Отбрасываем PB и переносим точку В в точку Р. Получаем новый отрезок АВ.

На новом отрезке уже есть точка L точка «Золотого сечения».

Процедура поиска продолжается до тех пор, пока не выполнится условие:

6. Метод сканирования

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

Сканированием можно исследовать как функцию одной, так и нескольких переменных.

Рассмотрим одномерное сканирование:

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

В данном методе точку экстремума не обязательно определять абсолютно точно, достаточно сильно сузить интервал.

Таким образом в одномерном случае задача поиска экстремума сводится к сужению интервала неопределенности.

Рисунок 4 - Графическое представление метода сканирования

Выберем целое число К значений целевой функции: и в точках рассчитываем значения функции.

Выбираем максимальное значение функции и сужаем интервал неопределенности до 2Дх симметричных относительно максимальной точки.

Переносим концы отрезка и получаем новый отрезок АВ.

Новый интервал неопределенности вновь разбивается на .

Интегрирование (поиск оптимума) продолжается до тех пор, пока мы не сузили интервал неопределенности до той точки, которую мы задали сами.

Заключение

Из всех представленных методов оптимизации удобнее всего применять метод дихотомии, так как при этом методе требуется произвести не большое число итераций. Метод Бокса-Уилсона наоборот, требует большого числа итераций и поэтому не удобен для практического применения.

Список использованных источников

1. Банди Б. Методы оптимизации (вводный курс). - М.: Радио и связь,1988.

2. Васильев Ф.П. Численные методы решения экстремальных задач. - М.: Наука, 2008.

3. Зангвилл У. Нелинейное программирование. Единый подход. - М.: Сов. радио, 2006.

4. Сеа Ж. Оптимизация. Теория и алгоритмы. - М.: Мир, 2011.

5. Лесин В.В., Лисовец Ю. П. Основы методов оптимизации. - М.: Изд-во МАИ, 2009.

Размещено на Allbest.ru