- •Одномерная оптимизация. Необходимые и достаточные условия оптимальности. Принцип сужения интервала неопределенности для унимодальных функций.
- •Одномерная оптимизация. Постановка задачи. Метод половинного деления. Оценка погрешности.
- •Одномерная оптимизация. Постановка задачи. Метод "золотого" сечения, Фибоначчи.
- •Одномерная оптимизация. Постановка задачи. Метод Ньютона-Рафсона.
- •6. Одномерная оптимизация. Постановка задачи. Метод квадратической аппроксимации.
- •7. Многомерная оптимизация. Основные определения и понятия функции нескольких переменных (фнп). Необходимые и достаточные условия экстремума.
- •8. Многомерная оптимизация. Основные определения и понятия функции нескольких переменных (фнп). Обусловленность задачи поиска минимума фнп.
- •9. Постановка задачи безусловной оптимизации фнп. Методы нулевого порядка. Метод покоординатного спуска.
- •1.2& Метод покоординатного спуска.
- •10. Постановка задачи безусловной оптимизации фнп. Метод многогранника. Алгоритм метода.
- •Постановка задачи безусловной оптимизации фнп. Метод Монтер-Карло. Алгоритм метода. Основные параметры метода.
- •12. Постановка задачи безусловной оптимизации фнп. Градиентные методы и метод наискорейшего спуска.
- •13. Постановка задачи безусловной оптимизации фнп. Градиентный метод с добрым шагом. Алгоритм выбора длины шага.
- •14. Постановка задачи безусловной оптимизации фнп. Овражный метод.
- •15. Постановка задачи безусловной оптимизации фнп. Методы второго порядка. Метод Ньютона.
- •16. Пз безусловной оптимизации фнп. Методы второго порядка. Метод Ньютона с дробным шагом. Алгоритм выбора длины шага.
- •17. Общая постановка задачи условной оптимизации. Постановки задач линейного и целочисленного программирования. Необходимые и достаточные условия оптимальности злп.
- •18. Общая и стандартная постановки злп. Переход от общей постановки задачи к стандартной.
- •19. Графическое решение злп. Основные понятия и идея решения задачи.
- •20. Симплекс-метод решения злп. Построение начальной симплекс-таблицы.
- •21.Оценка решения, представленного данной таблицей, на оптимальность и, если оптимум не достигается, поиск переменной, вводимой в базис.
- •22.Определение выводимой из базиса переменной.
- •23. Выбор начального решения
- •24. Анализ ресурсов.
- •25. Анализ цен
- •26. Целочисленное деление.
- •27. Постановка транспортной задачи. Балансировка задачи.
- •28. Сведение транспортной задачи к задаче линейного программирования.
- •29. Постановка транспортной задачи. Поиск допустимого нач.Решения. Метод с-з угла. Метод min стоимости.
- •35.Алгоритм Форда-Фалкерсона
7. Многомерная оптимизация. Основные определения и понятия функции нескольких переменных (фнп). Необходимые и достаточные условия экстремума.
Постановка задачи:
Дана непрерывно дифференцируемая функция F(x1,x2,...,xn) n переменных. Необходимо найти хотя бы одну точку локального оптимума этой функции:
F(x) ---> opt ,где x = (x1,x2,...,xn).
Необходимые и достаточные условия локального минимума
Определение 1:
- непрерывно-дифференцируема в точке Хо, если существует некоторый вектор - такой что
и
Определение 2:
- непрерывно дифференцированной области VcRn, если - непрерывно дифференцируема для любых
Определение 3:
- дважды непрерывно дифференцируема если существует , такие, что где
G(xo)=f’’(xo) – матрица Гессе 2-х производных
8. Многомерная оптимизация. Основные определения и понятия функции нескольких переменных (фнп). Обусловленность задачи поиска минимума фнп.
Рассмотрим функцию n действительных переменных
f(x1,x2,...,xn) = f(x)
Точка в n-мерном евклидовом пространстве с координатами x1,x2,x3,...,xn обозначается вектором-столбцом x. Градиент функции, т.е. вектор с компонентами
f/ x1, f/ x2,..., f/ xn,
обозначается f (x) или, иногда, g(x). Матрица Гессе (гессиан) функции f(x) обозначается как G(x) и является симметричной матрицей n x n элементов вида
Gij = 2 f/ xi xj
Функция f(x) имеет локальный минимум в точке x0, если существует окрестность точки x0, такая, что f(x) > f(x0) во всех точках этой окрестности, т.е. существует положительная величина , такая, что для |x - x0| < справедливо неравенство f(x) >= f(x0).
В случае глобального минимума в точке x* для всех x справедливо неравенство f(x) >= f(x*).
При таких определениях и очевидных предположениях относительно дифференцируемости можно обобщить уравнение (2.2) из темы №2 и получить:
f(x0+h)-f(x0)= hi (x1,x2,..,xn)+ hihj (x1,x2,..,xn)+... =h + hTG(x0)h+... (4)
Тогда, если x0 является точкой минимума функции f(x), то каждая первая частная производная f/ xi (i = 1,...,n) должна обращаться в нуль в точке x0. Если это не так, то соответствующим выбором hi можно добиться того, что разность f(x0 + h) - f(x0 ) будет отрицательна.
Следовательно, необходимым условием минимума в точке x0 является уравнение
f(x0)= 0;(5)
т.е.
f(x0) / xi = 0, (i=1,...,n), (6)
Тогда знак разности f(x0 + h) - f(x0) определяется членом:
1/2 hTG(x0)h (7)
Если матрица G(x0) положительно определена, то этот член положителен для всех h. Следовательно, необходимыми и достаточными условиями минимума являются:
f(x0) = 0, G(x0) положительно определена. (8)
Необходимыми и достаточными условиями максимума являются:
f(xm) = 0, G(xm) отрицательно определена. (9)
9. Постановка задачи безусловной оптимизации фнп. Методы нулевого порядка. Метод покоординатного спуска.
Постановка задачи:
Дана непрерывно дифференцируемая функция F(x1,x2,...,xn) n переменных. Необходимо найти хотя бы одну точку локального оптимума этой функции:
F(x) ---> opt ,где x = (x1,x2,...,xn).
Методы нулевого порядка.
В случае, когда свойства оптимизируемой функции неизвестны или она не является дифференцируемой во всей области поиска, то исследователь вынужден использовать методы нулевого порядка, опирающиеся только на значения функции.
Перед непосредственным применением методов прямого поиска необходимо провести ряд мероприятий по подготовке задачи к решению, а именно
исключить ограничения в виде равенств;
определить начальную допустимую точку.
Простейший способ исключения ограничений в виде равенств заключается в решении его относительно одной из переменных с последующим исключением этой переменной путем подстановки полученного выражения в соотношения, описывающие задачу. При этом следует учитывать, что границы значений исключаемых переменных сохраняются в задаче в виде ограничений - неравенств.
Для определения начальной допустимой точки целесообразно использовать процедуру случайного поиска, основная идея которого будет рассмотрена ниже.
После проведения процедуры подготовки задачи к решению следует приметить один из методов условной оптимизации. Рассмотрим методы прямого поиска: