Рабочая программа дисциплины методы оптимизации для подготовки бакалавров по направлению 552800-" Информатика и вычислительная техника "
| Вид материала | Рабочая программа |
- Рабочая программа дисциплины сети ЭВМ и телекоммуникации для подготовки бакалавров, 155.67kb.
- Рабочая программа дисциплины компьютерная графика для подготовки бакалавров по направлению, 180.06kb.
- Рабочая программа дисциплины операционные системы для подготовки бакалавров по направлению, 274.73kb.
- Рабочая программа дисциплины микропроцессорные технологии для подготовки магистров, 174.5kb.
- Рабочая программа дисциплины «Методы оптимизации» по направлению подготовки дипломированного, 132.79kb.
- Образовательный стандарт по направлению 552800 «Информатика и вычислительная техника», 199.12kb.
- Образовательный стандарт по направлению 552800 «Информатика и вычислительная техника», 245.41kb.
- Рабочая программа дисциплины «Методы визуального и параллельного программирования», 102.66kb.
- Образовательный стандарт по направлению бакалавриата 552800 "Информатика и вычислительная, 565.08kb.
- Образовательный стандарт по направлению 552800 Информатика и вычислительная техника, 169.1kb.
Министерство образования Российской Федерации
Санкт-Петербургский государственный электротехнический
университет “ЛЭТИ”
РАБОЧАЯ ПРОГРАММА
дисциплины
МЕТОДЫ ОПТИМИЗАЦИИ
Для подготовки бакалавров по направлению 552800-“ Информатика и вычислительная техника ”.
Санкт-Петербург
2001
Санкт-Петербургский государственный электротехнический
университет “ЛЭТИ”
“УТВЕРЖДАЮ”
Проректор по учебной работе
проф. ___________ Ушаков В.Н.
“_____”_______________2001 г.
РАБОЧАЯ ПРОГРАММА
дисциплины
МЕТОДЫ ОПТИМИМЗАЦИИ
| Для | подготовки бакалавров по направлению 552800-“ Информатика и вычислительная техника ”. |
Факультет ФКТИ
Кафедра Математического обеспечения и применения ЭВМ
Курс – 3
Семестр(ы) – 5
| Лекции | 32 ч. | | Экзамен | 5 семестр |
| | | | | |
| Практические занятия | 16 ч. | | | |
| | | | | |
| Лабораторные занятия | 16 ч. | | Зачет | 5 семестр |
| | | | | |
| Аудиторные занятия | 64 ч. | |
| Самостоятельные занятия | 62 ч. | |
| Всего часов | 126 ч. | |
2001
Рабочая программа обсуждена на заседании кафедры Математического обеспечения и применения ЭВМ “____”_______________2001 г., протокол №______.
Рабочая программа составлена в соответствии с государственным образовательным стандартом по направлению 552800–”Информатика и вычислительная техника"
Рабочая программа согласована с рабочими программами изученных ранее дисциплин:
1) Математический анализ,
2) Программирование
Рабочая программа одобрена методической комиссией факультета ФКТИ
“____”_____________2001г.
Цели и задачи дисциплины
- Изучение математической базы решения оптимизационных задач.
- Формирование навыков экспериментальных исследований при выборе метода оптимизации.
Требования к уровню освоения дисциплины
В результате изучения дисциплины студенты должны:
- Знать основные понятия и постановки задач теории минимизации гладких функций, выпуклого и линейного программирования, переборных задач. Вариационного исчисления, методы решения типовых задач из указанных областей.
- Уметь решать вручную и с помощью ЭВМ типовые задачи небольшой размерности.
- Иметь представление о разнообразных постановках оптимизационных задач, а также о стандартных программных средствах решения типовых оптимизационных задач.
Содержание рабочей программы
Тема 1. Вводная.
Краткая характеристика дисциплины. Ее цели и задачи, порядок изучения материала, связь с другими дисциплинами учебного плана и место в подготовке инженера по специальности 2204.
Формы контроля самостоятельной работы. Краткая характеристика учебной литературы.
Основные понятия. Классификация допустимых множеств. Соответствие методов и допустимых множеств.
Тема 2. Безусловная оптимизация.
Постановка задачи. Общая схема безусловной оптимизации.
Методы первого порядка. Градиентный метод с постоянным шагом. Теорема о сходимости градиентного метода. Выпуклые функции и множества. Свойства выпуклых функций. Теорема о скорости сходимости градиентного метода. Градиентный метод с дроблением шага. Метод наискорейшего спуска. Масштабирование.
Метод Ньютона. Теорема о скорости сходимости метода Ньютона.
Сравнение градиентных методов. Понятие о числе обусловленности локального минимума.
Многошаговые (двухшаговые) методы. Метод тяжелого шарика. Метод сопряженных градиентов. Метод Полака-Ривьера.
Квазиньютоновские методы. Метод Давидона-Флетчера_Пауэлла. Метод Бройдена-Флетчера-Шенно.
Методы нулевого порядка. Методы аппроксимации. Метод покоординатного спуска. Метод симплексов (Нелдера-Мида). Метод Пауэлла.
Методы прямого поиска в задачах одномерной оптимизации. Метод квадратичной интерполяции. Метод дихотомии (половинного деления). Метод «золотого сечения». Метод Фибоначчи.
Тема 3. Условная оптимизация.
Постановка задачи нелинейного программирования. Ограничения типа равенств. Ограничения типа неравенств. Лемма Фаркаша. Теорема Каруша-Джона.
Задача выпуклого программирования. Функция Лагранжа. Теорема о седловой точке. Теорема Куна-Таккера.
Методы условной минимизации. Метод проекции градиента. Метод условного градиента. Метод модифицированной функции Лагранжа. Метод штрафных функций.
Двойственность задачи выпуклого программирования. Теорема двойственности. Двойственность задачи линейного программирования.
Тема 4. Линейное программирование.
Основные понятия. Теорема о представлении и о существовании оптимальной точки. Геометрическая интерпретация задачи линейного программирования. Условие оптимальности для задачи линейного программирования. Теорема об угловой точке.
Базис и базисное решение. Теорема о допустимом решении задачи линейного программирования. Симплекс-метод решения задачи линейного программирования.
Транспортная задача. Построение первоначального опорного плана. Построение оптимального плана методом потенциалов. Теорема о потенциалах. Алгоритм метода потенциалов. Представление транспортной задачи с помощью графов.
Тема 5. Решение переборных задач.
Метод ветвей и границ. Задача о коммивояжере.
Динамическое программирование. Вывод уравнения Беллмана. Примеры задач динамического программирования. Задача о ранце. Задача о распределении ресурсов.
Тема 6. Вариационное исчисление.
Постановка задачи. Уравнение Эйлера-Лагранжа. Частные случаи уравнения Эйлера-Лагранжа. Задача о брахистохроне.
Вариационные задачи на условный экстремум.
Принцип максимума Понтрягина. Принцип максимума в задаче о предельном быстродействии.
Тема 7. Заключительная.
Программная реализация системы оптимизации.
Основные тенденции развития методов оптимизации и краткая характеристика программных средств решения оптимизационных задач.
Интеллектуальные системы решения оптимизационных задач. Генетические алгоритмы. Оптимизация на нечетких множествах.
Перечень лабораторных работ
| № | Наименование работы | Номер темы |
| 1 | Методы безусловной минимизации. | 2 |
| 2 | Методы условной оптимизации | 3 |
| 3 | Пошаговое решение задачи линейного программирования | 4 |
| 4 | Формализация содержательных постановок задач, сводимых к задаче линейного программирования, и их решение. | 4 |
| 5 | Транспортная задача. | 4 |
| 6 | Метод ветвей и границ. Задача коммивояжера. | 5 |
| 7 | Динамическое программирование. | 5 |
Перечень практических занятий
| № | Наименование темы занятия | Номер темы программы |
| 1 | Дифференцирование сложных функций многих переменных. | 1 |
| 2 | Методы безусловной оптимизации. | 2 |
| 3 | Методы условной оптимизации. | 3 |
| 4 | Задача линейного программирования. Табличный метод решения задачи линейного программирования. Геометрическая интерпретация задачи линейного программирования. | 4 |
| 5 | Метод ветвей и границ. Задача коммивояжера. | 5 |
| 6 | Динамическое программирование. Задача о ранце. Задача о распределении ресурсов. | 5 |
| 7 | Вариационное исчисление. Уравнение Эйлера-Лагранжа. | 6 |
Распределение учебных часов по темам и видам занятий
| № темы | Название разделов и тем | Объем учебных часов | Семестр | |||||
| Лекции | Лабор. занятия | Практ. занятия | Аудит. занятия | Самост. работа | Всего | |||
| 1 | Введение | 1 | | 2 | 3 | 4 | 7 | 5 |
| 2 | Безусловная оптимизация | 8 | 4 | 3 | 15 | 10 | 25 | 5 |
| 3 | Условная оптимизация | 6 | 4 | 2 | 12 | 10 | 22 | 5 |
| 4 | Линейное программирование | 7 | 4 | 4 | 15 | 10 | 25 | 5 |
| 5 | Решение переборных задач | 4 | 4 | 3 | 11 | 10 | 21 | 5 |
| 6 | Вариационное исчисление | 4 | | 2 | 6 | 10 | 16 | 5 |
| 7 | Заключительная | 2 | | | 2 | 8 | 10 | 5 |
| ИТОГО: | 32 | 16 | 16 | 64 | 62 | 126 | | |
ЛИТЕРАТУРА
Основная
| № | Название, библиографическое описание | Л | Лр | Пз (С) | К-во экз. в библ. (на каф.) | Гриф |
| 1 | Балтрашевич В. Э., Барабанов Н. Е. Методы оптимизации: Учеб. пособие. СПб.: Изд-во СПбГЭТУ “ЛЭТИ”, 2001. 80 с. | 6 | 6 | 6 | 80 | Мин. образ. РФ |
| 2 | Методические указания к лабораторным работам по дисциплине «Исследование алгоритмов оптимизации»/Сост.: Барабанов Н.Е., Балтрашевич В.Э., Первозванский А.А.;ЛЭТИ. –С_Пб.,1991. | | 6 | 6 | Уч 16 Ф 4 | ГК СССР по нар.обр. |
| 3 | Поляк В.Т. Введение в оптимизацию. Учебник – М.: Наука, 1983. | 6 | 6 | 6 | 10 | МВ и ССО СССР |
| 4 | Карманов В.Г. Математическое программирование. Учебник – М.:Наука, 1986. | 6 | | | 9 | МВ и ССО СССР |
| 5 | Банди Б. Методы оптимизации. Вводный курс. – М.:Радио и связь, 1988 | 6 | 6 | 6 | Уч 7 Ф 5 | МВ и ССО СССР |
| 6 | Банди Б. Основы линейного программирования. Учебник – М.: Наука, 1983. | 6 | 6 | 6 | Уч 1 Ф 3 | МВ и ССО СССР |
Дополнительная
| № | Название, библиографическое описание | К-во экз. в библ. (на каф.) |
| 1 | Моисеев Н.Н., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. – М.: Наука, 1978. | 0 |
| 2 | Кузин Л.Г. Основы кибернетики. Т.1 – М.: Энергия, 1973. | 33 |
| 3 | Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. – М.: Наука, 1965. | 0 |
| 4 | Кузнецов Ю.И., Кузубов В.И., Волощенко А.Б. Математическое программирование. Учебник -–М. Высшая школа, 1980 | 0 |
| Автор: | |
| к.т.н., доцент | Балтрашевич В.Э. |
| | |
| Рецензент | |
| д.т.н., профессор | Постников Е.В. |
| | |
| Зав. Кафедрой МО ЭВМ | |
| д.т.н., профессор | Лисс А.Р. |
| | |
| Декан факультета ФКТИ | |
| д.т.н., профессор | Герасимов И.В. |
| | |
| | |
| Программа согласована: | |
| | |
| | |
| Зав. отделом учебной литературы (для технических дисциплин) | Смирнова О.Н. |
| | |
| Председатель методической комиссии факультета ФКТИ | Чугунов Л.А. |
| к.т.н., доцент | |
| | |
| Руководитель методического отдела | |
| к.т.н., доцент | Марасина Л.А. |
| | |