1612725639-6dc5754f085fb35085399cf24f2ed57a (Программа курса Плясунов)

ПРОГРАММАна 2014/15 уч. год по курсу «Методы оптимизации»для студентов 3 курса ММФ НГУ (6 семестр)Лектор: к.ф.-м.н., доцент А.В. Плясунов1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.Понятие экстремальной задачи [1-8]. Элементы алгоритмической теорииэкстремальных задач (только по лекциям). Задачи линейного программирования.Базисные решения и крайние точки линейного многогранного множества [1-7].Необходимые и достаточные условия разрешимости задачи линейного программирования [3]. Симплексная таблица. Элементарные преобразования базиса исимплексной таблицы. Симплекс-метод [1-7].Конечностьсимплекс-методаивырожденностьзадачилинейногопрограммирования.Лексикографическийвариантсимплекс-методаидоказательствоегоконечности.Методисскуственногобазиса.Модифицированный симплекс-метод [1-7].Двойственность в линейном программировании.

Первая теорема двойственности.Вторая теорема двойственности. Двойственный симплекс-метод [1, 3, 5].Теоремы отделимости. Выпуклые конусы. Сопряжённые конусы [3, 7].Теорема Дубовицкого-Милютина. Внутренние и предельные направления.Необходимые условия экстремума [3, 7].Обобщённое правило множителей Лагранжа [3, 7].Выпуклое программирование. Субградиенты выпуклых функций. Седловыеточки функции Лагранжа. Лемма о конусе, сопряжённом конусу направленийубывания выпуклой функции. Теорема Куна-Таккера для задачи выпуклогопрограммирования [3, 7].

Двойственные задачи нелинейного программирования[2].Метод градиентов. Теоремы сходимости. Метод Ньютона [1-4, 6-8].Метод покоординатного спуска [2].Преобразования и стратегии решения. Понятие координирующей задачи.Проекция экстремальной задачи. Алгоритм решения задачи о (r|p)-центроиде.Метод Такахаши (только по лекциям).Методы штрафных функций для задач с ограничениями.

Метод Келли [1, 2, 6].Метод декомпозиции для максиминных задач. Обобщённая декомпозицияБендерса. Декомпозиция Бендерса для смешанно целочисленных задач. Методветвей и границ. Метод ветвей и отсечений для смешано-целочисленной задачи(только по лекциям).Постановка задачи вариационного исчисления. Сильный и слабый экстремумы.Необходимые условия экстремума для простейших задач вариационногоисчисления [1, 2].ПринципмаксимумаПонтрягина.Линейнаязадачаоптимальногобыстродействия.

Необходимость и достаточность принципа максимума. Теоремыо числе переключений [1, 2].Темы семинарских занятий1. Ознакомительное занятие. Экстремальные задачи:основные определения,обозначения, классификация. Необходимые и достаточные условия экстремума.Метод множителей Лагранжа.2. Задачи Линейного программирования (ЛП). Типы задач. Сводимости. Базиснодопустимые решения, рёбра. Определение грани. Решение задач.3.

Симплекс-таблица (с.-т.). Прямо и двойственно допустимые с.-т. Случаи4.5.6.7.8.ограниченного и неограниченного рёбер. Решение задач.Симплекс-метод (с.-м.) и лексикографический с.-м. Решение задач.Контрольная (три вычислительных и одна теоретическая).Двойственность в ЛП.Теория двойственности ЛП.Контрольная.Учебно-методическое и информационное обеспечение дисциплиныа) основная литература:1. Алексеева Е.В., Кутненко О.А., Плясунов А.В. «Численные методы оптимизации»,НГУ, 2009.2.

Васильев Ф.П. «Методы оптимизации», М.: Факториал Пресс, 2002.3. Глебов Н.И., Кочетов Ю.А., Плясунов А.В. «Методы оптимизации». Учебноепособие. Новосибирск: НГУ, 2000.4. Карманов В. Г. «Математическое программирование», М.: Наука, 2004.5. Ларин Р.М., Плясунов А.В., Пяткин А.В. Методы оптимизации. Примеры и задачи.Учебное пособие.

Новосибирск: Новосибирский государственный университет,2009.6. Мину М. «Математическое программирование. Теория и алгоритмы», М.: Наука,1990.7. Моисеев Н.Н., Иванилов Ю.П., Столярова Е.М. «Методы оптимизации», М.:Наука, 1978.8. Сухарев А.Г., Тимохов А.В., Федоров В.В. «Курс методов оптимизации». М.: Мир,2005.б) Интернет-ресурсы:9. Глебов Н.И., Кочетов Ю.А., Плясунов А.В. «Методы оптимизации». Учебноепособие.

Новосибирск: НГУ, 2000. : url - http://www.math.nsc.ru/LBRT/k5/opt.html.10. Алексеева Е.В., Кутненко О.А., Плясунов А.В. «Численные методы оптимизации»,НГУ, 2009. : url - http://www.math.nsc.ru/LBRT/k5/Plyasunov/Posobie3.pdf.11. Ларин Р.М., Плясунов А.В., Пяткин А.В. Методы оптимизации. Примеры и задачи.Учебное пособие.

Новосибирск: Новосибирский государственный университет,2009: url - http://www.math.nsc.ru/LBRT/k5/Plyasunov/opt-2.html..