Программа на 2014/2015 уч год по курсу «Методы оптимизации»



Скачать 27,06 Kb.
Дата28.10.2016
Размер27,06 Kb.
ТипПрограмма
ПРОГРАММА

на 2014/2015 уч. год по курсу «Методы оптимизации»

для студентов 3 потока 3 курса ММФ НГУ (6 семестр)

Лектор: д.ф.-м.н. доцент А.В.Пяткин

Программа лекций

  1. Введение. Постановка и общие методы решения задач оптимизации (1 лекция): Предмет изучения, основные термины и обозначения, связь с другими дисциплинами. Метод Лагранжа.

  2. Элементы выпуклого анализа (2 лекции): Выпуклые множества. Проекция и ее свойства. Теоремы отделимости. Конус. Теорема Фаркаша. Выпуклые и сильновыпуклые функции, их экстремальные свойства. Критерий сильной выпуклости. Теорема о существовании и единственности оптимального решения.

  3. Выпуклая оптимизация (2 лекции): Условия Слейтера. Седловая точка функции Лагранжа. Достаточный критерий оптимальности задачи выпуклого программирования. Теорема Куна-Такера и ее применение. Критерий оптимальности для задачи выпуклого программирования с линейными ограничениями.

  4. Линейное программирование, симплекс-метод (3 лекции): Задачи линейного программирования. Общая, каноническая и стандартная форма. Базисные и базисные допустимые решения. Существование оптимального базисного решения. Критерий разрешимости задачи линейного программирования. Элементарные преобразования базиса. Симплекс-метод. Свойства симплекс-метода. Вырожденность и конечность симплекс-метода. Лексикографический вариант симплекс-метода. Модифицированный симплекс-метод. Метод искусственного базиса.

  5. Двойственность в линейном программировании (2 лекции): Построение и свойства двойственных задач. Теоремы двойственности и их применение. Двойственный симплекс-метод, его применение

  6. Вычислительная сложность и метод эллипсоидов (1 лекция): Понятие алгоритмической сложности. Метод эллипсоидов для задач линейного программирования, его трудоемкость и геометрическая интерпретация.

  7. Численные методы решения задач оптимизации (4 лекции): Понятие о скорости сходимости. Методы нулевого, первого и второго порядков. Градиентные методы. Теоремы о сходимости градиентных методов. Метод Ньютона. Теорема о квадратичной скорости сходимости. Метод покоординатного спуска. Теорема о сходимости. Метод возможных направлений. Теорема о сходимости метода. Метод штрафных функций. Теорема о сходимости метода. Метод сопряженных направлений. Теоремы о сходимости.

Литература

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

  2. Васильев Ф.П. Численные методы решения экстремальных задач. -- М.: Наука, 1980.

  3. Карманов В.Г. Математическое программирование. -- М.: Наука, 1986.

  4. Моисеев Н.И., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. -- М.: Наука, 1978.

Программа практических занятий

  1. Безусловная оптимизация. Необходимые и достаточные условия локального экстремума. Задачи о наибольшем и наименьшем значении.

  2. Задачи с ограничениями равенствами. Функция Лагранжа. Метод множителей Лагранжа. Решение задач с ограничениями неравенствами.

  3. Выпуклые функции и множества. Доказательство выпуклости специальных множеств и функций. Квазивыпуклые функции и их свойства.

  4. Применение критерия оптимальности и понятия седловой точки для решения задач выпуклого программирования.

  5. Задача линейного программирования. Эквивалентность различных форм задачи. Геометрическая интерпретация задачи. Базисные решения. Симплекс-таблица и критерий оптимальности.

  6. Элементарные преобразования базиса. Алгоритм симплекс - метода. Метод искусственного базиса.

  7. Двойственные задачи линейного программирования. Теоремы двойственности.



Литература


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

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

  3. Заславский Ю.Л. Сборник задач по линейному программированию. -- М.: Наука,1969.

Программу составил



д.ф.-м.н., доцент А.В.Пяткин


Поделитесь с Вашими друзьями:


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

войти | регистрация
    Главная страница


загрузить материал