Geum.ru

Рабочая учебная программа по дисциплине «Методы оптимизации» Направление №230100 «Информатика и вычислительная техника»

Вид материалаРабочая учебная программа

Содержание


Цель и задачи дисциплины, ее место в учебном процессе
Содержание дисциплины
7 семестр (16 часов)
Лабораторные работы, их содержание и объем в часах
Градиентные методы оптимизации (методы первого порядка). Квазиньютоновские методы: Метод Дэвидона-Флетчера-Пауэлла (Д-Ф-П).
Курсовая работа, цель, содержание и объем
Самостоятельная работа
Учебно-методические материалы по дисциплине
9. Половинкин Е.С. Элементы выпуклого и сильно выпуклого анализа. М.: Физматлит, 2007.
Подобный материал:

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ


ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ


«МАТИ» - РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ

имени К.Э. ЦИОЛКОВСКОГО




Кафедра «Проектирование вычислительных комплексов»


РАБОЧАЯ УЧЕБНАЯ ПРОГРАММА


по дисциплине «Методы оптимизации»


Направление № 230100 «Информатика и вычислительная техника»

Шифр учебного плана: 230100.03пвк

Факультет № 6

Выпускающая кафедра: Проектирование вычислительных комплексов

Форма обучения: очная

Количество часов по дисциплине: 144

Цикл дисциплин: Е


Распределение времени студента по видам учебных занятий

(часы аудиторных занятий/самостоятельная работа)



Семестр
7



По учебному плану (АР/СР)
64/80



Лекции (АР/СР)
32/22



Лабораторные работы (АР/СР)
16/8



Практические занятия (АР/СР)
16/30



Курсовая работа (0/СР)
кр/20



Форма контроля
экзамен





Москва 2008 г.


  1. ^

    ЦЕЛЬ И ЗАДАЧИ ДИСЦИПЛИНЫ, ЕЕ МЕСТО В УЧЕБНОМ ПРОЦЕССЕ



Цель преподавания дисциплины


Обучение основам теории и численных методов оптимизации


    1. Задачи изучения дисциплины


Освоение постановок основных задач оптимизации

Изучение основ теории оптимизации и методов решения некоторых задач оптимизации аналитическими методами

Освоение базовых численных методов оптимизации

Создание навыков применения численных методов при решении типовых задач оптимизации


    1. Перечень тем и разделов предшествующих дисциплин, освоение которых необходимо для изучения данной дисциплины



Линейная алгебра: вектора и матрицы, конечномерные линейные пространства, линейные операторы в конечномерных линейных пространствах.

Математический анализ: дифференциальное исчисление; интегральное исчисление; теория обыкновенных дифференциальных уравнений; теория уравнений математической физики.

  1. ^ СОДЕРЖАНИЕ ДИСЦИПЛИНЫ



    1. Наименования разделов и тем, объем в часах лекционных занятий.


7 семестр (32 часа)



№
Тема и содержание
Кол-во

часов


Вводная лекция: основные понятия, примеры задач оптимизации, классификация оптимизационных задач, основные типы задач математического программирования.

2


Гладкая безусловная оптимизация. Постановка задачи, основные

понятия и особенности. Необходимое условие экстремума. Достаточные условия экстремума. Задачи условной оптимизации с ограничениями в виде равенств. Функции Лагранжа. Метод исключения переменных, задающих допустимую область. Другой подход – принцип метода множителей Лагранжа
2


Аналитические методы нелинейного программирования: необходимые и достаточные условия оптимальности в геометрической и алгебраической форме.

2


Задачи оптимизации со смешанными ограничениями.Постановка задачи. Геометрические условия оптимальности. Алгебраические условия оптимальности задачи со смешанными ограничениями (обобщенное правило Лагранжа, сведение общей задачи нелинейного программирования к задаче с ограничениями типа равенств, теорема Куна-Таккера)
2


Задача выпуклого программирования и ее особенность. Безусловная оптимизация. Условная оптимизация. Функция Лагранжа и седловые точки. Двойственность по Лагранжу. Квадратичное программирование.
2


Численная реализация методов конечномерной оптимизации. Линейный поиск экстремума унимодальной функции, методы прямого последовательного поиска (дихотомия, золотое сечение, метод чисел Фибоначчи), сравнение методов последовательного поиска; методы полиномиальной аппроксимации: квадратичная аппроксимация.
2


Численные методы безусловной оптимизации. Прямые методы поиска безусловного экстремума. Методы нулевого порядка (Хука – Дживса; Нелдера – Мида).
2


Численные методы безусловной оптимизации. Градиентные методы. Методы первого порядка: наискорейшего спуска; сопряженных направлений (Флетчера – Ривса; Полака – Рибьера); квазиньютоновские методы; Дэвидона – Флетчера – Пауэлла.
2


Численные методы безусловной оптимизации второго порядка: метод Ньютона и его модификации: Ньютона – Рафсона; Марквардта – Левенберга.
2


Задачи выпуклого программирования. Методы условной оптимизаци. Постановка задачи и общие замечания. Методы прямого поиска: модифицированный Хука – Дживса; комплексов Бокса. Методы случайного поиска: методы штрафных и барьерных функций; метод возможных направлений Зойтендейка.
2


Задачи линейного программирования. Постановка задачи. Базисные решения и их свойства. Геометрическая интерпретация основной задачи линейного программирования на плоскости.


2


Задачи линейного программирования. Симплекс-метод решения задачи линейного программирования. Этапы реализации симплекс-метода
2


Оптимизация на графах. Сетевое планирование. Основные понятия и определения. Критический путь. Ранний срок наступления завершающего события. Поздний срок наступления события. Резервы времени каждого события
2


Вариационное исчисление. Понятие функционала. Необходимые условия экстремума. Функциональные пространства. Линейный функционал. Вариация функционала. Необходимое условие экстремума функционала. Уравнение Эйлера. Вывод. Частные случаи уравнения Эйлера
2


Вариационное исчисление. Оптимизация функционалов, зависящих от производных высших порядков. Уравнение Эйлера – Пуассона. Вывод. Оптимизация функционала от n функций. Система дифференциальных уравнений Эйлера
2


Функционалы от функций нескольких переменных. Уравнение Эйлера – Остроградского. Вариационные задачи на условный экстремум

2



    1. Практические занятия, их содержание и объем в часах



^

7 семестр (16 часов)





№
Тема и содержание
Кол-во

часов


Решение экстремальных задач классическими методами дифференциального анализа.
2


Решение задач нелинейного программирования аналитическими методами. Функции Лагранжа (классические и обобщенные)
4


Решение задач линейного программирования. Базисные решения и их свойства. Геометрическая интерпретация основной задачи линейного программирования на плоскости.

2


Оптимизация на графах. Сетевое планирование. Основные понятия и определения. Критический путь. Ранний срок наступления завершающего события. Поздний срок наступления события. Резервы времени каждого события
2


Решение вариационных задач. Уравнение Эйлера и его решение. Частные случаи уравнения Эйлера
3


Оптимизация функционалов, зависящих от производных высших порядков. Решение уравнения Эйлера – Пуассона. Оптимизация функционала от функций. Решение систем дифференциальных уравнений Эйлера
2


Оптимизация функционалов, зависящих от функций нескольких переменных. Решение уравнения Эйлера – Остроградского. Вариационные задачи на условный экстремум

1



2.3. ^ Лабораторные работы, их содержание и объем в часах


7 семестр (16 часов)


№
Тема и содержание
Кол-во

часов

1.
Численные методы оптимизации нулевого порядка. Прямой метод поиска безусловного экстремума. Симплексный метод Нелдера-Мида (метод деформируемого многогранника)
2

2.
Градиентные методы оптимизации (методы первого порядка). Метод наискорейшего градиентного спуска.
2

3.
 ^

Градиентные методы оптимизации (методы первого порядка). Квазиньютоновские методы: Метод Дэвидона-Флетчера-Пауэлла (Д-Ф-П).
2

4.

Методы оптимизации второго порядка (ньютоновские). Метод Ньютона-Рафсона.
2

5.
Методы условной оптимизации (прямого поиска). Модифицированный методы Хука-Дживса.
2

6.
Методы условной оптимизации. Метод барьерной функции (внутренние штрафы).
3

7.
Методы условной оптимизации. Метод штрафных функций (внутренние штрафы).
3



    1. ^ Курсовая работа, цель, содержание и объем


Цель: Получение навыков численного решения задач оптимизации


Задачи: Изучение постановки выбранной задачи и выбранного метода (методов) решения; создание программы, реализующей метод решения задачи; исследование поведения программы, объяснение результатов.


Курсовая работа должна включать следующие пункты и разделы:

1). Наименование (название работы)

2). Постановка задачи

3). Общее описание метода

4). Описание подметода (если есть)

5). Описание входных данных в программе

6). Описание реализации метода (программы)

7). Реализация метода с разными входными данными

8). Список используемой литературы


Задание: найти минимум функции, заданной тремя различными способами (в виде квадратичной, тригонометрической, показательной функции), одним из перечисленных ниже методов.

  1. Прямые методы поиска безусловного экстремума. Метод Хука-Дживса (метод конфигураций).
  2. Прямые методы поиска безусловного экстремума. Метод Розенброка.
  3. Прямые методы поиска безусловного экстремума. Метод сопряженных направлений.
  4. Метод случайного поиска (адаптивный метод, поиск с возвратом при неудачном шаге)
  5. Метод случайного поиска (Метод наилучшей пробы)
  6. Градиентные методы. Метод градиентного спуска с постоянным шагом.
  7. Градиентные методы (методы первого порядка). Метод покоординатного спуска.
  8. Градиентные методы (методы первого порядка). Метод Гаусса-Зейделя.
  9. Градиентные методы (методы первого порядка). Метод Флетчера-Ривса.
  10. Градиентные методы (методы первого порядка). Метод исчерпывающего спуска.
  11. Градиентные методы (методы первого порядка). Циклический покоординатный спуск
  12. Градиентные методы (методы первого порядка). Метод квадратичной аппроксимации.
  13. Градиентные методы (методы первого порядка). Метод Полака-Рибьера.
  14. Методы второго порядка. Метод Ньютона.
  15. Методы второго порядка (ньютоновские). Метод Марквардта-Левенберга.
  16. Метод условной оптимизации (прямого поиска). Метод комплексов (комплексный метод) Бокса.
  17. Метод условной оптимизации (прямого поиска). Методы случайного поиска.
  18. Метод условной оптимизации. Метод возможных направлений (метод Зойтендейка).
  19. Метод последовательной безусловной минимизации. Метод множителей.
  20. Метод последовательной безусловной минимизации. Комбинированный метод штрафных функций.
  21. Методы условной оптимизации. Метод проекции градиента.
  22. Методы условной оптимизации. Метод модифицированных функций Лагранжа. Точные гладкие штрафные функции. Метод последовательного квадратичного программирования.
  23. Задачи линейного программирования (ЗЛП). Симплекс-метод Данцига.
  24. Задачи линейного программирования (ЗЛП). Двухфазный симплекс-метод.
  25. Задачи линейного программирования (ЗЛП). Метод ветвей и границ.
  26. Задачи линейного программирования (ЗЛП). Метод Гомори.

Объем времени на выполнение работы 20 часов

Работа должна быть сдана в виде отчета, состоящего из двух файлов: теоретическая часть, практическая часть (программа). Объем отчета до10 страниц печатного текста шрифт 12 плюс электронный вариант реализации соответствующей программы оптимизации.


  1. ^

    САМОСТОЯТЕЛЬНАЯ РАБОТА

    1. Работа над конспектом лекций и рекомендуемой учебной литературой (22 часа).
    2. Решение задач домашних заданий, подготовка к практическим занятиям (15 часов)
    3. Подготовка к контрольным работам (6 часов).
    4. Выполнение курсовой работы (20 часов).
    5. Лабораторные работы (4 часа).
    6. Непосредственная подготовка к экзамену (15 часов)



  1. ^

    УЧЕБНО-МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ ПО ДИСЦИПЛИНЕ




    1. Обязательная литература


1. Алексеев В.М., Галеев Э.М., Тихомиров В.М. .Сборник задач по оптимизации. Теория. Примеры. Задачи. М.: Физматлит, 2007.

2. Федоров В.В., Сухарев А.Г., Тимохов А.В. Курс методов оптимизации. М.: Физматлит, 2008.

3. Пантелеев А.В, Летова Т.А, Методы оптимизации в примерах и задачах. М.: Высшая школа, 2005.

4. Данко П.Е., Попов А.Г., Кожевникова Т.Я. Высшая математика в упражнениях и задачах с решениями: в 2-х частях. М.: Мир и образование, 2008.

5. Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. М.: Факториал Пресс, 2008.

6. Демьянов В.Ф. Условия экстремума и вариационное исчисление. М.: Высшая школа, 2005.

7. Эльсгольц Л.Э. Вариационное исчисление. М.: КомКнига, 2006.

8. Харари Ф. Теория графов. М.: КомКнига, 2006.
^

9. Половинкин Е.С. Элементы выпуклого и сильно выпуклого анализа. М.: Физматлит, 2007.


10. Корнеенко В.П. Методы оптимизации. Учебник. М.: Высшая школа 4.2


4.2. Рекомендуемая литература


1. Бирюков С.И. Оптимизация. Элементы теории. Численные методы. - М.: «МЗ-Пресс». – 2004

2. Васильев Ф.П. Методы оптимизации. - М.:«Факториал Пресс». - 2003.

3. Васильев Ф.П. Численные методы решения экстремальных задач. – М.: «Наука». – 1988

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

4. Ашманов С.А. Линейное программирование. – М. «Наука». – 1981

5. Березина Л.Ю. Графы и их применение. М.: Просвещение, 1979.

6. Акулич И.Л. Математическое программирование в примерах и задачах. М.: Высшая школа, 1986.

7. Мухачева Э.А., Рубинштейн Г.М. Математическое программирование. Новосибирск: Наука, 1977.

8. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. М.: Мир, 1985.

9. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных задачах. М.: Наука, 1975.