Д. Черных Общая постановка задачи оптимизации



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


  1. Глебов Н.И., Кочетов Ю.А., Плясунов А.В. Методы оптимизации. Учебное пособие. Изд. НГУ, Новосибирск, 2000.

  2. Демидович Б.П. Сборник задач и упражнений по математическому анализу. Изд. АСТ, 2007.

  3. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. Изд. Физматлит., 2005.

  4. Абрамов Л.М., Капустин В.Ф. Математическое программирование. СПб, Изд. СПбГУ, 2001.

  5. Ларин Р.М., Плясунов А.В., Пяткин А.В. Методы оптимизации. Примеры и задачи. Учебное пособие. Изд. НГУ, Новосибирск, 2003.





Похожие:

Д. Черных Общая постановка задачи оптимизации iconВопросы к экзамену по Методам Оптимизации. Классификация оптимизационных задач. Постановка задач оптимизации. Задачи конечномерной оптимизации. Дискретная оптимизация. Бесконечномерная оптимизация. Многокритериальные задачи
Методы безусловной оптимизации функций нескольких переменных. Методы ньютоновского типа (2-го порядка). Метод Ньютона Рафсона. Метод...
Д. Черных Общая постановка задачи оптимизации iconМногомерные задачи оптимизации
Мы рассмотрим одномерные задачи оптимизации, в которых ц ф зависит лишь от одного аргумента. В большинстве реальных задач оптимизации...
Д. Черных Общая постановка задачи оптимизации iconЗадачи оптимизации
Такие задачи называются задачами оптимизации, в отличие от задач анализа. В задачах анализа вычисляется выходное значение для заданного...
Д. Черных Общая постановка задачи оптимизации iconМетоды оптимизации «из коробки»
Способы оптимизации сильно зависят от конкретной задачи. Свою роль в выборе способов оптимизации играют набор используемых на сайте...
Д. Черных Общая постановка задачи оптимизации iconВопросы к экзамену Постановка задач оптимизации. Классификация
Методы одномерной оптимизации без использования информации о производной: (методы пассивного поиска, дихотомии, деления пополам,...
Д. Черных Общая постановка задачи оптимизации iconРеализация муравьиного алгоритма для решения задачи коммивояжера
На сегодня уже получены хорошие результаты муравьиной оптимизации таких сложных комбинаторных задач, как задача оптимизации маршрутов...
Д. Черных Общая постановка задачи оптимизации iconТранспортная задача линейного программирования
Транспортная задача. Общая постановка, цели, задачи. Основные типы, виды моделей
Д. Черных Общая постановка задачи оптимизации iconБорьба за жизнеспособность Общая постановка вопроса
Задачи, самая мысль о которых еще недавно представлялась если не безумием, то утопической фантазией, теперь сознательно выдвигаются,...
Д. Черных Общая постановка задачи оптимизации iconЛекция №10 Сетевые модели в оптимизации процессов и принятии управленческих решений. Раздел Сетевые модели
Задачи оптимизации управляемых процессов, или как они будут в дальнейшем называться, задачи оптимального управления, составляют один...
Д. Черных Общая постановка задачи оптимизации iconВопросы к экзамену по курсу "Вариационное исчисление"
Постановка простейшей задачи классического вариационного исчисления. Определение экстремума задачи
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org