- •Элементы выпуклого анализа.
- •Начальные сведения о численных методах оптимизации.
- •4.Сходимость методов оптимизации.
- •5.Метод покоординатного спуска.
- •6.Метод случайного поиска. Алгоритм с возвратом при неудачном шаге.
- •7. Метод случайного поиска. Алгоритм наилучшей пробы.
- •8. Метод случайного поиска. Алгоритм статистического градиента.
- •9. Метод случайного поиска. Алгоритм покоординатного обучения.
- •10. Градиентный метод. Метод с постоянным шагом.
- •11. Градиентный метод. Метод с дроблением шага.
- •12. Градиентный метод. Метод наискорейшего спуска.
- •13. Метод Ньютона
- •14. Численные методы решения задач линейного программирования. Прямой симплекс-метод. Базис и базисное решение.
- •15. Численные методы решения задач линейного программирования. Прямой симплекс-метод. Элементарные преобразования. Симплекс-таблицы.
- •16. Численные методы решения задач линейного программирования. Прямой симплекс-метод. Алгоритм симплекс-метода.
- •17. Численные методы решения задач линейного программирования. Модифицированный симплекс-метод.
- •18. Численные методы решения задач линейного программирования. Лексикографический прямой симплекс-метод
- •19. Численные методы решения задач линейного программирования. Двойственный симплекс-метод.
- •20. Численные методы решения задач линейного программирования. Двойственный симплекс-метод.
- •22. Численные методы решения задач линейного программирования. Геометрическая интерпретация задач линейного программирования
- •23. Численные методы решения задач линейного программирования. Геометрическая интерпретация прямого симплекс-метода.
- •24. Численные методы условной оптимизации. Метод возможных направлений.
- •25. Численные методы условной оптимизации. Метод Келли и метод секущих плоскостей.
- •26. Численные методы условной оптимизации. Первый (циклический) алгоритм Гомори.
- •27. Численные методы условной оптимизации. Метод ветвей и границ
- •28. Численные методы условной оптимизации. Метод ветвей и границ для решения задач нелинейного программирования
- •29. Численные методы условной оптимизации. Метод внешних штрафов
- •30.Численные методы условной оптимизации. Метод внутренних штрафов или метод барьерных функций
- •31.Муравьиный алгоритм.
- •32.Генетические алгоритмы.
- •33.Задачи классического вариационного исчисления. Постановка задачи классического вариационного исчисления
- •Сильный и слабый экстремум в задачах классического вариационного исчисления.
- •Допустимые управления и управляемые процессы в задачах оптимального управления. Оптимальные процессы
- •Элементарный вывод необходимых условий экстремума для простейших задач классического вариационного исчисления
- •Задачи оптимального управления. Постановка задачи оптимального управления
- •Формулировка принципа максимума для линейной задачи быстродействия
- •Доказательство принципа максимума для линейной задачи быстродействия.
- •Достаточность принципа максимума
23. Численные методы решения задач линейного программирования. Геометрическая интерпретация прямого симплекс-метода.
Рассмотрим б.д.р. задачи P. ПустьB – его базисная матрица, а N, соответственно, небазисная матрица. Обозначим через П гиперплоскость, натянутую на расширенные вектора базиса , и проходящую через начало координат. Эта гиперплоскость однозначно определяется бази-сом B и ее направляющий вектор есть решение следующей системы урав-нений следовательно, . Оценки замещения симплекс-таблицы, соответствующей б.д.р. , образуют вектор . Таким образом, если на первом шаге итерации симплекс-таблица, соответствующая б.д.р. , является двойственно допустимой, тоесть , то вектор y является допустимым решением двойственной задачи, тогда и – оптимальные решения. Их геометрическая интерпретация содержится в предыдущем параграфе. Если существует номер s такой, что , то это означает, что недопустимое решение двойственной задачи, то есть симплекс-таблица не двойственно допустима, а неоптимальное решение. Геометрически это эквивалентно тому, что вектор расположен ниже гиперплоскости П. Рассмотрим конус , натянутый на вектора :
. Если коэффициенты замещения , то множество содержит луч, исходящий из точки . Это следует из существования параметрического семейства векторов , которое использовалось при обосновании симплекс-метода. В этом случае задача (1)-(3) не имеет оптимального решения. Заметим, что это возможно тогда и только тогда, когда конус содержит полуось . Если конус не содержит полуось , то тогда и множество является отрезком, который в вырожденном случае может оказаться точкой. Если задача (1)-(3) невырож-денная,то отрезок отличен от точки. Его крайняя верхняя точка является образом базисного допустимого решения и лежит на грани образованной векторами , так как . Это означает, что эта грань есть пересечение конуса с гиперплоскостью П. Тогда нижняя точка отрезка является геометрическим образом нового базисного допустимого решения и лежит на грани, порожденной векторами другими словами, – новый базис, образованный векторами . Точки пересечения конуса и прямой Q являются геометрическими образами решений, полученных из базисно допустимого решения x элементарным преобразованием, которое определяется вектором .
24. Численные методы условной оптимизации. Метод возможных направлений.
Методы безусловной оптимизации можно использовать для решения экс-тремальных задач условной оптимизации. Для этого необходимо доработать эти методы таким образом, чтобы учитывались ограничения задачи. В этом параграфе рассмотрен один из таких методов – методвозможных направлений.
Пусть имеется точка, удовлетворяющая ограничениям задачи. Выберем возможное направление движения, то есть такой ненулевой вектор, что
1. малое перемещение в этом направлении не выводит за пределы множе-ства допустимых решений;
2. целевая функция строго убывает в этом направлении.
Затем осуществляется перемещение в выбранном направлении до получения нового допустимого решения с лучшим значением целевой функции. Пред-ставленный ниже алгоритм был разработан голландским математиком Зой-тендейком [2, 3, 6], который предложил выбирать направление спуска из пересечения конусов возможных направлений и направлений убывания целевой функции. Особенность метода заключается в учете нелинейности ограниче-ний и в сравнении направлений не только по локальной скорости убывания целевой функции, но и по длинам шагов, которые удастся сделать вдоль них.
Представленный ниже алгоритм предназначается для поиска экстремума при наличии ограничений только типа неравенств. Рассмотрим задачу