- •1.Понятие решения задачи мат. Программиров.
- •2. Основн. Формы злп. Правила сведения злп к канон.Форме. Геометр.Интерпретация злп. Понятие угловой точки мн-ва.
- •4. Определение базиса угловой точки. Невырожденные угловые точки. Примеры.
- •5. Связь между переменными задачи лп
- •6. Формула приращения целевой функции злп.
- •7. Достаточное условие оптимальности в злп. Достаточное условие неразрешимости злп
- •8. Итерация симплекс–метода
- •11. Нахождение базиса угловой точки. Пример
- •12. Постановка тз. Построение нач. Плана перевозок методом северо-западного угла, методом мин. Элемента.
- •13. Определение закрытой модели тз. Критерий существования решения тз.
- •14. Исследование мн-ва клеток транспортной таблицы
- •15. Достаточное условие минимальности стоимости перевозок
- •16. Классический метод решения задачи безусловной минимизации функции многих переменных. Пример.
- •17. Метод исключения решения задачи на условный минимум. Пример.
- •18. Обобщенное правило множителей Лагранжа в задаче оптимизации с ограничениями типа равенств.
- •19. Классическое правило множителей Лагранжа в задаче оптимизации с ограничениями типа равенств. Необходимые условия второго порядка в задаче оптимизации типа равенств.
- •20. Достаточные условия экстремума в задаче оптимизации с ограничениями типа равенств
- •21.Опр-ия выпуклого мн-ва, выпуклой функции. Св-ва выпуклых множеств. Сумма выпуклых функций. Св-во неотрицательности остатка выпуклой функции
- •22.Теорема о точках минимума выпуклой функции. Теорема о стационарной точке выпуклой функции
- •26.Теорема о седловой точке функции Лагранжа (достаточные условия оптимальности).
- •27. Критерий существования седловой точки функции Лагранжа для задачи выпуклого программирования.
- •28.Определение двойственной задачи к задаче математического программирования.
- •29. Связь между двойственной и прямой задачами математического программирования.
- •30.Пример решения задачи оптимизации с помощью теории двойственности
- •31.Основные определения в задаче одномерной минимизации. Примеры.
- •33. Метод золотого сечения решения задачи одномерной минимизации.
- •34. Обоснование метода ломаных решения задачи одномерной минимизации.
- •35. Алгоритм и условия сходимости метода ломаных решения задачи одномерной минимизации. Пример. Описание метода ломаных
- •36.Алгоритм метода скорейшего спуска решения змм.
- •37.Алгоритмы метода условного градиента и метода проекции градиента решения задачи многомерной условной минимизации.
- •38.Алгоритм метода покоординатного спуска решения задачи многомерной минимизации. Геометрическая иллюстрация.
- •39.Сходимость метода скорейшего спуска.
- •41. Метод вариаций Лагранжа
- •42. Уравнение Эйлера
- •43. Случаи интегрируемости ур-ния Эйлера. Примеры.
- •44.Задача вариационного исчисления с незакрепленными концами и фиксированным отрезком интегрирования.
- •45.Задача вариационного исчисления с незакрепленными концами и нефиксированным отрезком интегрирования
- •46. Задача вариационного исчисления с движущимся по кривой концом.
- •47. Примеры задач динамического программирования, их особенности
- •48.Принципы динамического программирования и функциональные уравнения Беллмана.
38.Алгоритм метода покоординатного спуска решения задачи многомерной минимизации. Геометрическая иллюстрация.
Рассм. задачу . Пусть выбрано некотороеначальное приближение. И методом покоординатного спуска было получено приближение. Ч/з,, обозначим координатные вектора(1 наj-ом месте). Положим и для , где определяется из условия. И след. приближение, если для некоторого, то процесс вычисления заканчивают, А тсчитают приближением к точке минимума.
Данный метод хорошо подходит для задач с параллепипедными ограничениями,
, . В этом случае при решении вспомагательной задачи минимизации,.
на альфа накладываются ограничения, не позволяющие точкам х выходить за пределы мн-ва Х
39.Сходимость метода скорейшего спуска.
Рассм. задачу (1). Пусть в (1) ф-ция f(x) непрерывно дифференцируема, ограничена снизу на мн-ве , ее градиент уд.векторному усл. Липшица с константой L, то есть для всex
Тогда при любом начальном приближении итерационный процесс метода скорейшего спуска является релаксационным,то есть уд.нер-ву
обладает св-вом
Если дополнительно предположить, что мн-во ограничено, то посл-ность {xk} сходится к непустому мн-ву S*стационарных точек ф-ции f(x)
Если кроме того, f(x) выпукла на то посл-ность{xk} явл. минимизирующей и сходится к непустому мн-ву X* решений задачи.
40.Постановка простейшей задачи вариационного исчисления. Примеры.
Говорят, что на некотором классе ф-ций задан функционал, если каждой ф-ции x=x(t) из этого класса, поставлено в соотв. число . Если кажд. Ф-циюx(t) рассматривать, как элемент некоторого пр-ва L, н/р пр-во непрерывных ф-кций, непрерывно дифференцируемых ф-кций, то ,где
В пр-ве L можно рассматривать некоторые мн-ва XL, н/р мн-во
Тогда можно рассматривать задачу оптимизации в функциональном пр-ве, кот.формально может быть записана в той же форме, что и задача мат. прогр:
Найти такое , что.(1)
Задача (1) понимается в глобальном смысле, если необходимо найти ф-цию, доставляющую линейному функционалу J(x) по всем xX и понимаемом в лок смысле, если,, где
Сформулируем зад.вариационного исчисления: Пусть на отрезке T=определена непрерывно дифференцируемая ф-цияx(t), принимающая на концах отрезка заданные значения:
Определим мн-во: (2)
И на этом мн-ве определена ф-ция:(3)
Где ф-ция определена и непрерывна по всем своим аргументам вместе с частными производными поx,,tдо 2-го порядка. Требуется найти ф-цию , такую что(4)
Ф-ции из мн-ва (2)наз. допустимыми,а ф-кия наз. минималью
Зад. (2)-(4) обычно понимается в локальном смысле, т.е. минимум ищется по ф-циям
если
то говорят о сильном локальном минимуме
если
то говорят о слабом локальном минимуме
Замечание.Если на некоторой кривойдостигается сильный локальный минимум, то на ней достигается и слабый локальный минимум, но не наоборот. Поэтому необходимые усл. слабого локального минимума будут явл. и необходимыми усл. сильного локального минимума, но не наоборот.
Пример: (зад.о бахистохроне – кривая наискорейшего времени )
На плоскости заданы 2-е точки А и B. Введем декартовую систему координат: т. А попадает в начало координат, а т.B имеет координаты .Из А вB скатывается тяжелая материальная точка.
Найти кривую x(t) по которой перемещение из А в B произойдет за минимальное время.
Начальная скорость . Точка скатывается под воздействием силы тяжести; сопротивление не учитывается, поэтому скорость точки зависит только от положения точки и не зависит от формы кривой.
По закону Галия: , гдеg- ускорение свободного падения. С другой стороны, скорость в каждый момент времени вычисляется, как отношение , гдеds- дифференциал дуги, которая будет пройденна точкой за время dt.
Известно, что Т.о.. Тогда время, которое необходимо точке для перехода из А вB определяется как .
Т.о. получаем следующую задачу вариационного исчисления: