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

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

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

что действия выполняются не с выражениями, а со значениями, когда

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

концах некоторого интервала имеет значения разных знаков, то внутри этого

интервала у нее есть корень (как минимум, один, но м.б. и несколько)". На базе этой теоремы построено численное нахождение приближенного значения корня функции. Обобщенно этот метод называется дихотомией, т.е. делением отрезка на две части.
Обобщенный алгоритм выглядит так:
Задать начальный интервал;
Убедиться, что на концах функция имеет разный знак;
Повторять пока не будет достигнута нужная точность:
выбрать внутри интервала точку;
сравнить знак функции в точке  со знаком функции в одном из концов;
если совпадает, то переместить этот конец интервала в точку,
иначе переместить в точку  другой конец интервала;

= 0,618
Х4 = 0,618 (Х2 – Х1)

2, F4 = 3.
Fn = Fn-1 + Fn-2 при n>2.
Погрешность

определяется

Скорость сужения интервала

на отрезке ab. Выбирается три точки Х1, Х2, Х3 –

любые. Через эти три точки проводиться парабола.

Постоим квадратный трехчлен:
Точку минимума можно определить, приравняв производную к 0:




очередное приближение


Затем переходят к новому отрезку

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

вблизи середины данного отрезка.
Если , то точка середины лежит на участке возрастания => необходимо исследовать отрезок ах.

найдется точка экстремума

используя метод касательных. В очередной точке строиться линейная аппроксимация.
Точка,

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

проверка каждой из точек, т.е. расчет или сравнение производных

в задачах с многими факторами. При изучении объектов с несколькими

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

При достижении частного экстремума перемещение производится по другому частному направлению,

причем если два последовательных шага улучшают значения выходного параметра, то шаг увеличивают в 1,618 раз.
Если же m шагов, где m = 3 k (k – фактор), не дают улучшения, то шаг уменьшают в 0,618 раз.

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

экстремумов.
Метод осуществляется поочередным варьированием каждого фактора (при постоянстве остальных) до достижения частного экстремума. Затем производиться поворот.

В исходной точке фиксируют все координаты x, кроме одной. Этой координате xi задают приращение в сторону ее увеличения и в сторону уменьшения и получают две точки. Вычисляют значение целевой функции f в этих точках и сравнивают между собой. Следующей исходной точкой будет та, для которой функция f будет иметь наибольшее значение.
В случае двумерной целевой функции происходят последовательные вычисления и движения смещение по координате x1, затем по x2.

и перемещаются в направлении убывания или возрастания.

выполняется одномерный поиск вдоль произвольного направления, приводящий в точку х[1] .

Затем выбирается точка х[2], не лежащая на прямой х[0] - х[1], и осуществляется одномерный поиск вдоль прямой, параллельной х[0] - х[1],. Полученная в результате точка х[3] вместе с точкой х[1] определяет направление x[1] - х[3] одномерного поиска, дающее точку экстремума х*. В случае квадратичной функции n переменных оптимальное значение находится за n итераций. Поиск минимума при этом в конечном счете осуществляется во взаимно сопряженных направлениях. В случае неквадратичной целевой функции направления поиска оказываются сопряженными относительно матрицы Гессе.
Алгоритм метода параллельных касательных состоит в следующем. Из точки Х0 к линии уровня (в точке Х1) строят касательную, затем параллельно этой прямой строят прямую 1 и на ней точку Х2, соответствующую точке касания 1 и линии уровня. Местоположение центра определяется вдоль линии Х1 Х2.

ряд Тейлора в окрестности точки хк. Поэтому поведение описывается квадратичной

функцией, т.е. сходимость быстрее, чем у метода grad. Этапы расчета следующие:
В этом методе 1) определяется grad функции; 2) определяется матрица вторых производных и обратная к ней матрица. Необходимо найти точку минимума аппроксимирующей квадратичной функции:

т.е. в направлении градиента целевой функции. Направление движения корректируется после

каждой серии опытов. При этом находят градиент функции, равный:



После нахождения состава grad (коэффициента уравнения) выполняется шаг по направлению к экстремуму:


 – параметр шага
Показателем выхода в область оптимума является малое значение grad, т. е. коэффициенты полинома близки к 0.

Фрагмент траектории поиска минимума функции градиентным методом с дроблением шага.

для нахождения уравнения
Находят базовый фактор
По нему нормируют остальные шаги
Производят

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

Некоторые из « мысленных » опытов
(обычно через 2-5) реализуются для того,
чтобы проверить соответствие
аппроксимации процесса
найденной зависимостью.

подвергаются анализу – содержит ли данное подмножество оптимальное решение или

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

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

присваиваются временные метки, которые затем по определенным правилам заменяются на постоянные метки. После этого из всех временных меток выбирается наименьшая, и она становится
постоянной меткой. Действия продолжаются, пока не будут найдены постоянные метки для всех вершин графа. Результаты действий на каждом шаге будем заносить в таблицу. В предпоследний столбец заносим вершину, получившую постоянную метку, в последний
столбец – величину этой метки (для данного шага).
Кратчайшие пути найдены, их длина приведена в последних двух столбцах расчетной таблицы. Дерево кратчайших путей – ребра
(1,2), (2,5), (5,4), (4,3), (5,6), (6,7), (7,8).

уравнений по шагам, который начинается с опорного решения и в

поисках лучшего варианта движется по угловым точкам области допустимого решения, улучшающих значение целевой функции до тех пор, пока целевая функция не достигнет оптимального значения.
Составление первого опорного плана. Переход к канонической форме задачи линейного программирования путем введения неотрицательных дополнительных балансовых переменных.
Проверка плана на оптимальность. Если найдется хотя бы один коэффициент индексной строки меньше нуля, то план не оптимальный, и его необходимо улучшить.
Определение ведущих столбца и строки. Из отрицательных коэффициентов индексной строки выбирается наибольший по абсолютной величине. Затем элементы столбца свободных членов симплексной таблицы делит на элементы того же знака ведущего столбца.
Построение нового опорного плана. Переход к новому плану осуществляется в результате пересчета симплексной таблицы методом Жордана—Гаусса.
Построение симплекс-таблиц продолжается до тех пор, пока не будет получено оптимальное решение.
Движение к точке оптимума осуществляется путем перехода от одной угловой точки к соседней, которая ближе и быстрее приближает к Xопт. Такую схему перебора точек, называемую симплекс-метод, предложил Р. Данцигом.