Д. Черных Общая постановка задачи оптимизации
|
Скачать 27.3 Kb.
|
| Методы оптимизации Лектор: доцент И. Д. Черных 1. Общая постановка задачи оптимизации. Общие методы решения задач оптимизации, метод исключения, метод неопределенных множителей Лагранжа. Постановка задач линейного и выпуклого программирования. 2. Элементы выпуклого анализа. Выпуклые множества. Проекция и ее свойства. Теоремы отделимости. Конус. Теорема Фаркаша. Выпуклые и сильно выпуклые функции, их экстремальные свойства. Критерий сильной выпуклости. 3. Выпуклая оптимизация. Условия Слейтера. Функция Лагранжа. Седловая точка и условия ее существования. Достаточный критерий оптимальности задачи выпуклого программирования. Теорема Куна-Такера. Ее применение. Эквивалентные критерии оптимальности. Критерий оптимальности задачи выпуклого программирования с линейными ограничениями. 4. Задачи линейного программирования. Общая, каноническая и стандартная форма. Их эквивалентность. Основные свойства задачи. Базисные и базисные допустимые решения. Существование оптимального базисного решения. Критерий разрешимости задачи линейного программирования. Геометрический метод решения ЗЛП. Элементарные преобразования базиса. Симплекс-метод. Свойства симплекс-метода. Вырожденность и конечность симплекс-метода. Лексикографический вариант симплекс-метода. Рандомизированный симплекс-метод. Метод искусственного базиса. Двойственность в задачах линейного программирования. Теоремы двойственности. Двойственный симплекс-метод, его применение. Алгоритмическая сложность. Метод эллипсоидов. 5. Численные методы решения задач оптимизации. Понятие о скорости сходимости. Методы нулевого, первого и второго порядков. Градиентные методы. Метод наискорейшего спуска. Метод с регулировкой шага. Теоремы о сходимости градиентных методов. Метод Ньютона. Теорема о квадратичной скорости сходимости. Метод Ньютона. Теорема о квадратичной скорости сходимости. Метод покоординатного спуска. Теорема о сходимости. Метод возможных направлений. Теорема о сходимости метода. Метод возможных направлений. Теорема о сходимости метода. Метод штрафных функций. Теорема о сходимости метода. Метод сопряженных направлений. Теоремы о сходимости. Программа практических занятий 1. Безусловная оптимизация. Необходимые и достаточные условия локального экстремума. Задачи о наибольшем и наименьшем значении. 2. Задачи с ограничениями – равенствами. Функция Лагранжа. Метод множителей Лагранжа. Решение задач с ограничениями – неравенствами. 3. Выпуклые функции и множества. Доказательство выпуклости специальных множеств и функций. Квазивыпуклые функции и их свойства. 4. Применение критерия оптимальности и понятия седловой точки для решения задач выпуклого программирования. 5. Задача линейного программирования. Эквивалентность различных форм задачи. Геометрическая интерпретация задачи. Базисные решения. Симплекс-таблица и критерий оптимальности. 6. Элементарные преобразования базиса. Алгоритм симплекс–метода. Геометрическая интерпретация. Метод искусственного базиса. 7. Двойственные задачи линейного программирования. Двойственный симплекс-метод. Геометрическая интерпретация. Литература
|
Похожие:
 | Вопросы к экзамену по Методам Оптимизации. Классификация оптимизационных задач. Постановка задач оптимизации. Задачи конечномерной оптимизации. Дискретная оптимизация. Бесконечномерная оптимизация. Многокритериальные задачи Методы безусловной оптимизации функций нескольких переменных. Методы ньютоновского типа (2-го порядка). Метод Ньютона Рафсона. Метод... | | Многомерные задачи оптимизации Мы рассмотрим одномерные задачи оптимизации, в которых ц ф зависит лишь от одного аргумента. В большинстве реальных задач оптимизации... |
| Задачи оптимизации Такие задачи называются задачами оптимизации, в отличие от задач анализа. В задачах анализа вычисляется выходное значение для заданного... |  | Методы оптимизации «из коробки» Способы оптимизации сильно зависят от конкретной задачи. Свою роль в выборе способов оптимизации играют набор используемых на сайте... |
| Вопросы к экзамену Постановка задач оптимизации. Классификация Методы одномерной оптимизации без использования информации о производной: (методы пассивного поиска, дихотомии, деления пополам,... | | Реализация муравьиного алгоритма для решения задачи коммивояжера На сегодня уже получены хорошие результаты муравьиной оптимизации таких сложных комбинаторных задач, как задача оптимизации маршрутов... |
 | Транспортная задача линейного программирования Транспортная задача. Общая постановка, цели, задачи. Основные типы, виды моделей | | Борьба за жизнеспособность Общая постановка вопроса Задачи, самая мысль о которых еще недавно представлялась если не безумием, то утопической фантазией, теперь сознательно выдвигаются,... |
| Лекция №10 Сетевые модели в оптимизации процессов и принятии управленческих решений. Раздел Сетевые модели Задачи оптимизации управляемых процессов, или как они будут в дальнейшем называться, задачи оптимального управления, составляют один... | | Вопросы к экзамену по курсу "Вариационное исчисление" Постановка простейшей задачи классического вариационного исчисления. Определение экстремума задачи |